sgl_verifier_constructions
Definitionbppcomplexity-theorypolynomial-time
Executable verifier constructions used in the Sipser–Gács–Lautemann proof: a uniform ternary majority tree that infers each leaf width from the supplied random string, and the shifted-cover verifier that tests the polynomial-size family of translations. The definitions deliberately do not evaluate the abstract random-bit bound, which is assumed only to be polynomially bounded.
Definition code
import Definitions.Def_sipser_gacs_lautemann
import Mathlib.Data.List.GetD
import Mathlib.Data.Nat.Log
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Tactic.FinCases
namespace SipserGacsLautemann
def TernarySampleConstruction.{u} (Ω : Type u) : Nat → Type u
| 0 => Ω
| depth + 1 =>
TernarySampleConstruction Ω depth ×
TernarySampleConstruction Ω depth ×
TernarySampleConstruction Ω depth
def finThreeFunEquivTripleConstruction (α : Type*) :
(Fin 3 → α) ≃ α × α × α where
toFun f := (f 0, f 1, f 2)
invFun triple
| ⟨0, _⟩ => triple.1
| ⟨1, _⟩ => triple.2.1
| ⟨2, _⟩ => triple.2.2
left_inv f := by
funext i
fin_cases i <;> rfl
right_inv triple := by
rcases triple with ⟨a, b, c⟩
rfl
def ternaryPathsEquivConstruction (Ω : Type*) :
∀ depth,
TernarySampleConstruction Ω depth ≃
(Fin (3 ^ depth) → Ω)
| 0 => (Equiv.funUnique (Fin 1) Ω).symm
| depth + 1 =>
let child := ternaryPathsEquivConstruction Ω depth
((((Equiv.prodCongr child
(Equiv.prodCongr child child)).trans
(finThreeFunEquivTripleConstruction
(Fin (3 ^ depth) → Ω)).symm).trans
(Equiv.curry (Fin 3) (Fin (3 ^ depth)) Ω).symm).trans
(Equiv.arrowCongr finProdFinEquiv (Equiv.refl Ω))).trans
(Equiv.arrowCongr
(finCongr (by
rw [Nat.pow_succ]
omega))
(Equiv.refl Ω))
def flatTernaryEquivConstruction (randomBits depth : Nat) :
BitString (randomBits * 3 ^ depth) ≃
TernarySampleConstruction (BitString randomBits) depth :=
(((ternaryPathsEquivConstruction
(BitString randomBits) depth).trans
(Equiv.curry (Fin (3 ^ depth)) (Fin randomBits) Bool).symm).trans
(Equiv.arrowCongr finProdFinEquiv (Equiv.refl Bool))).trans
(Equiv.arrowCongr
(finCongr (Nat.mul_comm (3 ^ depth) randomBits))
(Equiv.refl Bool)) |>.symm
def majorityVoteConstruction (a b c : Bool) : Bool :=
(a && b) || (a && c) || (b && c)
def ternaryVoteConstruction {Ω : Type*} (vote : Ω → Bool) :
∀ depth, TernarySampleConstruction Ω depth → Bool
| 0 => vote
| depth + 1 => fun sample =>
majorityVoteConstruction
(ternaryVoteConstruction vote depth sample.1)
(ternaryVoteConstruction vote depth sample.2.1)
(ternaryVoteConstruction vote depth sample.2.2)
def paddedBitStringConstruction (length : Nat) (bits : List Bool) :
BitString length :=
fun i => bits.getD i.val false
def ternaryMapConstruction {α β : Type*} (map : α → β) :
∀ depth,
TernarySampleConstruction α depth →
TernarySampleConstruction β depth
| 0 => map
| depth + 1 => fun sample =>
(ternaryMapConstruction map depth sample.1,
ternaryMapConstruction map depth sample.2.1,
ternaryMapConstruction map depth sample.2.2)
def ternaryListTreeConstruction
(randomBits depth : Nat) (random : List Bool) :
TernarySampleConstruction (List Bool) depth :=
ternaryMapConstruction
(fun leaf : BitString randomBits => leaf.toList)
depth
(flatTernaryEquivConstruction randomBits depth
(paddedBitStringConstruction
(randomBits * 3 ^ depth) random))
def amplificationDepthConstruction (inputLength : Nat) : Nat :=
Nat.clog 2 (inputLength + 1) + 3
def ternaryAmplifiedVerifierConstruction
(verifier : List Bool → List Bool → Bool)
(input random : List Bool) : Bool :=
let depth := amplificationDepthConstruction input.length
let leafCount := 3 ^ depth
let randomBits := random.length / leafCount
ternaryVoteConstruction (verifier input) depth
(ternaryListTreeConstruction randomBits depth random)
def coverShiftCountConstruction (randomBits : Nat) : Nat :=
randomBits + 1
def decodeCoverTranslationConstruction
(randomBits : Nat) (encoded : List Bool)
(i : Fin (coverShiftCountConstruction randomBits)) : List Bool :=
List.ofFn fun j : Fin randomBits =>
encoded.getD (i.val * randomBits + j.val) false
def coverVerifierConstruction
(randomBits : Nat)
(verifier : List Bool → List Bool → Bool)
(input existential universal : List Bool) : Bool :=
decide
(∃ i : Fin (coverShiftCountConstruction randomBits),
verifier input
(List.zipWith (· != ·) universal
(decodeCoverTranslationConstruction
randomBits existential i)) = true)
end SipserGacsLautemann