Ternary sample-tree leaf predicates and length bounds
Definitionsgl_ternary_leaf_lengthscomplexity-theoryleansipser-gacs-lautemannturing-machines
This module packages structural lemmas for the mission ternary sample-tree construction. It defines an all-leaves predicate for TernarySampleConstruction, proves a leafwise congruence principle for ternaryVoteConstruction, and proves that every list leaf produced by ternaryListTreeConstruction randomBits depth random has length exactly randomBits.
It also records the resulting length bound for the two-tape virtual query (x,r): if a leaf block r is no longer than the original random tape, then the virtual two-tape input has total length at most the original two-tape input. These facts are used to justify replacing exact verifier clocks by explicit polynomial upper bounds in ternary scheduler reductions.
Definition code
import Definitions.Def_sgl_ternary_machine_vote_data
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Tactic
namespace SipserGacsLautemann
def TernaryAll {Ω : Type*} (predicate : Ω → Prop) :
∀ depth : Nat, TernarySampleConstruction Ω depth → Prop
| 0, sample => predicate sample
| depth + 1, sample =>
TernaryAll predicate depth sample.1 ∧
TernaryAll predicate depth sample.2.1 ∧
TernaryAll predicate depth sample.2.2
theorem TernaryAll.imp {Ω : Type*}
{predicate₁ predicate₂ : Ω → Prop}
(himp : ∀ sample, predicate₁ sample → predicate₂ sample) :
∀ (depth : Nat) (sample : TernarySampleConstruction Ω depth),
TernaryAll predicate₁ depth sample →
TernaryAll predicate₂ depth sample
| 0, sample, h => himp sample h
| depth + 1, sample, h =>
⟨TernaryAll.imp himp depth sample.1 h.1,
TernaryAll.imp himp depth sample.2.1 h.2.1,
TernaryAll.imp himp depth sample.2.2 h.2.2⟩
theorem ternaryVoteConstruction_congr_of_all {Ω : Type*}
(vote₁ vote₂ : Ω → Bool) :
∀ (depth : Nat) (sample : TernarySampleConstruction Ω depth),
TernaryAll (fun leaf => vote₁ leaf = vote₂ leaf)
depth sample →
ternaryVoteConstruction vote₁ depth sample =
ternaryVoteConstruction vote₂ depth sample
| 0, sample, h => h
| depth + 1, sample, h => by
simp only [ternaryVoteConstruction]
rw [ternaryVoteConstruction_congr_of_all
vote₁ vote₂ depth sample.1 h.1,
ternaryVoteConstruction_congr_of_all
vote₁ vote₂ depth sample.2.1 h.2.1,
ternaryVoteConstruction_congr_of_all
vote₁ vote₂ depth sample.2.2 h.2.2]
theorem ternaryMapConstruction_toList_all_lengths
(randomBits : Nat) :
∀ (depth : Nat)
(sample :
TernarySampleConstruction (BitString randomBits) depth),
TernaryAll
(fun leaf : List Bool => leaf.length = randomBits)
depth
(ternaryMapConstruction
(fun leaf : BitString randomBits => leaf.toList)
depth sample)
| 0, sample => by
simp [TernaryAll, ternaryMapConstruction,
BitString.toList]
exact List.length_ofFn (f := sample)
| depth + 1, sample =>
⟨ternaryMapConstruction_toList_all_lengths
randomBits depth sample.1,
ternaryMapConstruction_toList_all_lengths
randomBits depth sample.2.1,
ternaryMapConstruction_toList_all_lengths
randomBits depth sample.2.2⟩
theorem ternaryListTreeConstruction_all_leaf_lengths
(randomBits depth : Nat) (random : List Bool) :
TernaryAll
(fun leaf : List Bool => leaf.length = randomBits)
depth
(ternaryListTreeConstruction randomBits depth random) := by
unfold ternaryListTreeConstruction
exact
ternaryMapConstruction_toList_all_lengths
randomBits depth
(flatTernaryEquivConstruction randomBits depth
(paddedBitStringConstruction
(randomBits * 3 ^ depth) random))
theorem ternaryTwoTapeInput_totalInputLength_le
(input : Fin 2 → List Bool) (random : List Bool)
(hrandom : random.length ≤ (input 1).length) :
totalInputLength (ternaryTwoTapeInput input random) ≤
totalInputLength input := by
simp only [totalInputLength, List.sum_ofFn]
rw [Fin.sum_univ_two, Fin.sum_univ_two]
simp [ternaryTwoTapeInput]
omega
end SipserGacsLautemannSource
Prove2me Sipser--Gacs--Lautemann mission ternary-amplification sample-tree infrastructure.