Cover single-shift preprocessing transform
Definitionsgl_cover_preprocess_transformThis module defines the data-level transform used by one decoded cover-shift verifier call. For a four-tape input it constructs the query , where is decoded from at index , places that query on tape 2, and leaves tapes 0, 1, and 3 unchanged. It proves that this transform preserves total input length, which is needed when padding a delegated verifier machine by a polynomial clock.
Definition code
import Definitions.Def_sgl_verifier_constructions
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Data.List.Zip
import Mathlib.Tactic.FinCases
namespace SipserGacsLautemann
def coverSingleShiftQuery (input : Fin 4 → List Bool) :
List Bool :=
List.zipWith (· != ·) (input 2)
(decodeCoverTranslationConstruction
(input 2).length (input 1)
⟨min (input 3).length (input 2).length,
Nat.lt_succ_of_le
(Nat.min_le_right (input 3).length
(input 2).length)⟩)
def coverSingleShiftPreprocessInput
(input : Fin 4 → List Bool) :
Fin 4 → List Bool :=
fun j =>
if j = 0 then input 0
else if j = 1 then input 1
else if j = 2 then coverSingleShiftQuery input
else input 3
theorem coverSingleShiftQuery_length
(input : Fin 4 → List Bool) :
(coverSingleShiftQuery input).length = (input 2).length := by
simp [coverSingleShiftQuery,
decodeCoverTranslationConstruction, List.length_zipWith]
@[simp]
theorem coverSingleShiftPreprocessInput_zero
(input : Fin 4 → List Bool) :
coverSingleShiftPreprocessInput input 0 = input 0 := by
simp [coverSingleShiftPreprocessInput]
@[simp]
theorem coverSingleShiftPreprocessInput_one
(input : Fin 4 → List Bool) :
coverSingleShiftPreprocessInput input 1 = input 1 := by
simp [coverSingleShiftPreprocessInput]
@[simp]
theorem coverSingleShiftPreprocessInput_two
(input : Fin 4 → List Bool) :
coverSingleShiftPreprocessInput input 2 =
coverSingleShiftQuery input := by
simp [coverSingleShiftPreprocessInput]
@[simp]
theorem coverSingleShiftPreprocessInput_three
(input : Fin 4 → List Bool) :
coverSingleShiftPreprocessInput input 3 = input 3 := by
simp [coverSingleShiftPreprocessInput]
theorem coverSingleShiftPreprocessInput_length
(input : Fin 4 → List Bool) (i : Fin 4) :
(coverSingleShiftPreprocessInput input i).length =
(input i).length := by
fin_cases i
· simp
· simp
· simp [coverSingleShiftQuery_length]
· simp
theorem totalInputLength_coverSingleShiftPreprocessInput
(input : Fin 4 → List Bool) :
totalInputLength (coverSingleShiftPreprocessInput input) =
totalInputLength input := by
simp only [totalInputLength, List.sum_ofFn]
apply Finset.sum_congr rfl
intro i _
exact coverSingleShiftPreprocessInput_length input i
theorem totalInputLength_coverSingleShiftPreprocessInput_le
(input : Fin 4 → List Bool) :
totalInputLength (coverSingleShiftPreprocessInput input) ≤
totalInputLength input := by
rw [totalInputLength_coverSingleShiftPreprocessInput]
end SipserGacsLautemann
Source
Prove2me Sipser--Gács--Lautemann mission cover-verifier construction.