sgl_amplification_counting
Definitionbppcomplexity-theorycountingprobability
A sorry-free Lean library for ternary-majority error amplification. It proves the exact majority-of-three bad-set cardinality, the iterated contraction estimate, logarithmic-depth exponential error reduction, polynomial seed growth, and the final conditional amplification theorem for the executable verifier construction.
Definition code
import Definitions.Def_sipser_gacs_lautemann
import Definitions.Def_sgl_verifier_constructions
import Mathlib.Data.Fintype.BigOperators
import Mathlib.Data.Fintype.EquivFin
import Mathlib.Data.Fintype.Prod
import Mathlib.Data.List.GetD
import Mathlib.Logic.Equiv.Fin.Basic
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Data.Nat.Log
import Mathlib.Tactic.FinCases
import Mathlib.Tactic.Ring
namespace SipserGacsLautemann
def badCard {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad] : Nat :=
(Finset.univ.filter bad).card
theorem card_filter_eq_sum_indicator {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad] :
badCard bad = ∑ x : Ω, if bad x then 1 else 0 := by
classical
simp [badCard, Finset.sum_ite]
theorem sum_ite_predicate {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad] (yes no : Nat) :
(∑ x : Ω, if bad x then yes else no) =
badCard bad * yes +
(Fintype.card Ω - badCard bad) * no := by
classical
let badSet := (Finset.univ : Finset Ω).filter bad
let goodSet := (Finset.univ : Finset Ω).filter fun x => ¬bad x
have hsplit :
(∑ x : Ω, if bad x then yes else no) =
(∑ x ∈ badSet, yes) + ∑ x ∈ goodSet, no := by
rw [← Finset.sum_filter_add_sum_filter_not
(s := (Finset.univ : Finset Ω)) (p := bad)
(f := fun x => if bad x then yes else no)]
congr 1
· apply Finset.sum_congr rfl
intro x hx
simp [badSet] at hx
simp [hx]
· apply Finset.sum_congr rfl
intro x hx
simp [goodSet] at hx
simp [hx]
rw [hsplit]
simp only [Finset.sum_const, Nat.nsmul_eq_mul]
have hcards :=
Finset.card_filter_add_card_filter_not
(s := (Finset.univ : Finset Ω)) bad
have hsumBad :
(∑ x ∈ badSet, yes) = badSet.card * yes := by
simp
have hsumGood :
(∑ x ∈ goodSet, no) = goodSet.card * no := by
simp
have hgoodCard :
goodSet.card = Fintype.card Ω - badSet.card := by
dsimp [badSet, goodSet] at hcards ⊢
omega
rw [hgoodCard]
rfl
def majorityBad {Ω : Type*} (bad : Ω → Prop)
(sample : Ω × Ω × Ω) : Prop :=
(bad sample.1 ∧ bad sample.2.1) ∨
(bad sample.1 ∧ bad sample.2.2) ∨
(bad sample.2.1 ∧ bad sample.2.2)
instance majorityBad_decidable {Ω : Type*}
(bad : Ω → Prop) [DecidablePred bad] :
DecidablePred (majorityBad bad) := by
intro sample
unfold majorityBad
infer_instance
theorem majorityBad_card {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad] :
badCard (majorityBad bad) =
3 * (badCard bad) ^ 2 *
(Fintype.card Ω - badCard bad) +
(badCard bad) ^ 3 := by
classical
rw [card_filter_eq_sum_indicator]
rw [Fintype.sum_prod_type]
simp_rw [Fintype.sum_prod_type]
have hinner :
∀ a b : Ω,
(∑ c : Ω,
if majorityBad bad (a, b, c) then 1 else 0) =
if bad a then
(if bad b then Fintype.card Ω else badCard bad)
else
(if bad b then badCard bad else 0) := by
intro a b
by_cases ha : bad a <;> by_cases hb : bad b
· simp [majorityBad, ha, hb]
· simp [majorityBad, ha, hb,
← card_filter_eq_sum_indicator bad]
· simp [majorityBad, ha, hb,
← card_filter_eq_sum_indicator bad]
· simp [majorityBad, ha, hb]
simp_rw [hinner]
have hmiddle :
∀ a : Ω,
(∑ b : Ω,
if bad a then
(if bad b then Fintype.card Ω else badCard bad)
else
(if bad b then badCard bad else 0)) =
if bad a then
badCard bad * Fintype.card Ω +
(Fintype.card Ω - badCard bad) * badCard bad
else
(badCard bad) ^ 2 := by
intro a
by_cases ha : bad a
· simp only [ha, if_true]
exact
sum_ite_predicate bad (Fintype.card Ω) (badCard bad)
· simp only [ha, if_false]
rw [sum_ite_predicate bad (badCard bad) 0]
simp [pow_two]
simp_rw [hmiddle]
rw [sum_ite_predicate bad
(badCard bad * Fintype.card Ω +
(Fintype.card Ω - badCard bad) * badCard bad)
((badCard bad) ^ 2)]
have hbadLe : badCard bad ≤ Fintype.card Ω := by
exact Finset.card_le_univ _
have hsplit :
badCard bad + (Fintype.card Ω - badCard bad) =
Fintype.card Ω := Nat.add_sub_of_le hbadLe
have hproduct :
badCard bad * Fintype.card Ω =
badCard bad *
(badCard bad + (Fintype.card Ω - badCard bad)) :=
congrArg (fun n => badCard bad * n) hsplit.symm
rw [hproduct]
ring
abbrev TernarySample := TernarySampleConstruction
abbrev finThreeFunEquivTriple :=
finThreeFunEquivTripleConstruction
abbrev ternaryPathsEquiv := ternaryPathsEquivConstruction
abbrev flatTernaryEquiv := flatTernaryEquivConstruction
instance ternarySampleFintype {Ω : Type*} [Fintype Ω] :
∀ depth, Fintype (TernarySample Ω depth)
| 0 => ‹Fintype Ω›
| depth + 1 =>
let sampleFintype := ternarySampleFintype (Ω := Ω) depth
@instFintypeProd
(TernarySample Ω depth)
(TernarySample Ω depth × TernarySample Ω depth)
sampleFintype
(@instFintypeProd
(TernarySample Ω depth)
(TernarySample Ω depth)
sampleFintype sampleFintype)
def ternaryBad {Ω : Type*} (bad : Ω → Prop) :
∀ depth, TernarySample Ω depth → Prop
| 0 => bad
| depth + 1 => majorityBad (ternaryBad bad depth)
instance ternaryBadDecidable {Ω : Type*}
(bad : Ω → Prop) [DecidablePred bad] :
∀ depth, DecidablePred (ternaryBad bad depth)
| 0 => inferInstanceAs (DecidablePred bad)
| depth + 1 =>
letI := ternaryBadDecidable bad depth
majorityBad_decidable (ternaryBad bad depth)
theorem ternarySample_card {Ω : Type*} [Fintype Ω]
(depth : Nat) :
Fintype.card (TernarySample Ω depth) =
(Fintype.card Ω) ^ (3 ^ depth) := by
induction depth with
| zero =>
change Fintype.card Ω = (Fintype.card Ω) ^ (3 ^ 0)
simp
| succ depth ih =>
change
Fintype.card
(TernarySample Ω depth ×
TernarySample Ω depth × TernarySample Ω depth) =
_
rw [Fintype.card_prod, Fintype.card_prod, ih]
rw [pow_succ, pow_mul]
ring
theorem ternaryBad_card_succ {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad] (depth : Nat) :
badCard (ternaryBad bad (depth + 1)) =
3 * (badCard (ternaryBad bad depth)) ^ 2 *
(Fintype.card (TernarySample Ω depth) -
badCard (ternaryBad bad depth)) +
(badCard (ternaryBad bad depth)) ^ 3 := by
change badCard (majorityBad (ternaryBad bad depth)) = _
exact majorityBad_card (ternaryBad bad depth)
theorem ternaryBad_card_succ_le {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad] (depth : Nat) :
badCard (ternaryBad bad (depth + 1)) ≤
3 * (badCard (ternaryBad bad depth)) ^ 2 *
Fintype.card (TernarySample Ω depth) := by
rw [ternaryBad_card_succ]
have hbad :
badCard (ternaryBad bad depth) ≤
Fintype.card (TernarySample Ω depth) :=
Finset.card_le_univ _
let b := badCard (ternaryBad bad depth)
let n := Fintype.card (TernarySample Ω depth)
have hsplit : b + (n - b) = n :=
Nat.add_sub_of_le hbad
calc
3 * b ^ 2 * (n - b) + b ^ 3
≤ 3 * b ^ 2 * (n - b) + 3 * b ^ 3 := by
gcongr
omega
_ = 3 * b ^ 2 * ((n - b) + b) := by ring
_ = 3 * b ^ 2 * n := by rw [Nat.add_comm, hsplit]
theorem majority_seed_arithmetic (bad total : Nat)
(hthird : 3 * bad ≤ total) :
27 * (3 * bad ^ 2 * (total - bad) + bad ^ 3) ≤
7 * total ^ 3 := by
obtain ⟨extra, htotal⟩ :=
Nat.exists_eq_add_of_le hthird
rw [htotal]
have hsub :
3 * bad + extra - bad = 2 * bad + extra := by omega
rw [hsub]
ring_nf
omega
theorem ternaryBad_seed {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad]
(hthird : 3 * badCard bad ≤ Fintype.card Ω) :
3 * 9 ^ 1 * badCard (ternaryBad bad 1) ≤
7 ^ 1 * Fintype.card (TernarySample Ω 1) := by
rw [ternaryBad_card_succ]
simp only [ternaryBad]
rw [ternarySample_card (Ω := Ω) 0,
ternarySample_card (Ω := Ω) 1]
norm_num
exact majority_seed_arithmetic _ _ hthird
theorem ternarySample_card_succ_cube {Ω : Type*} [Fintype Ω]
(depth : Nat) :
Fintype.card (TernarySample Ω (depth + 1)) =
Fintype.card (TernarySample Ω depth) ^ 3 := by
rw [ternarySample_card, ternarySample_card]
rw [pow_succ, pow_mul]
theorem ternaryBad_contraction {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad]
(depth exponent : Nat)
(hinvariant :
3 * 9 ^ exponent * badCard (ternaryBad bad depth) ≤
7 ^ exponent * Fintype.card (TernarySample Ω depth)) :
3 * 9 ^ (2 * exponent) *
badCard (ternaryBad bad (depth + 1)) ≤
7 ^ (2 * exponent) *
Fintype.card (TernarySample Ω (depth + 1)) := by
let b := badCard (ternaryBad bad depth)
let total := Fintype.card (TernarySample Ω depth)
have hbadStep :
badCard (ternaryBad bad (depth + 1)) ≤
3 * b ^ 2 * total := by
simpa [b, total] using ternaryBad_card_succ_le bad depth
rw [ternarySample_card_succ_cube]
change
3 * 9 ^ (2 * exponent) *
badCard (ternaryBad bad (depth + 1)) ≤
7 ^ (2 * exponent) * total ^ 3
calc
3 * 9 ^ (2 * exponent) *
badCard (ternaryBad bad (depth + 1))
≤ 3 * 9 ^ (2 * exponent) * (3 * b ^ 2 * total) := by
gcongr
_ = (3 * 9 ^ exponent * b) ^ 2 * total := by
have h9 :
9 ^ (2 * exponent) = (9 ^ exponent) ^ 2 := by
rw [Nat.mul_comm, Nat.pow_mul]
rw [h9]
ring
_ ≤ (7 ^ exponent * total) ^ 2 * total := by
gcongr
_ = 7 ^ (2 * exponent) * total ^ 3 := by
have h7 :
7 ^ (2 * exponent) = (7 ^ exponent) ^ 2 := by
rw [Nat.mul_comm, Nat.pow_mul]
rw [h7]
ring
theorem ternaryBad_iterated_invariant {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad]
(hthird : 3 * badCard bad ≤ Fintype.card Ω)
(rounds : Nat) :
3 * 9 ^ (2 ^ rounds) *
badCard (ternaryBad bad (rounds + 1)) ≤
7 ^ (2 ^ rounds) *
Fintype.card (TernarySample Ω (rounds + 1)) := by
induction rounds with
| zero =>
simpa using ternaryBad_seed bad hthird
| succ rounds ih =>
have hstep :=
ternaryBad_contraction bad (rounds + 1) (2 ^ rounds) ih
simpa [pow_succ, Nat.mul_comm, Nat.mul_left_comm,
Nat.mul_assoc] using hstep
theorem two_pow_clog_lt_twice (x : Nat) (hx : 0 < x) :
2 ^ Nat.clog 2 x < 2 * x := by
by_cases hxone : x = 1
· subst x
norm_num
· have hxlarge : 1 < x := by omega
have hclog :
0 < Nat.clog 2 x :=
Nat.clog_pos (by decide) hxlarge
have hpred :
2 ^ (Nat.clog 2 x).pred < x :=
Nat.pow_pred_clog_lt_self (by decide) hxlarge
have hdecompose :
Nat.clog 2 x = (Nat.clog 2 x).pred + 1 :=
(Nat.succ_pred_eq_of_pos hclog).symm
rw [hdecompose, pow_succ]
rw [Nat.mul_comm (2 ^ (Nat.clog 2 x).pred) 2]
exact (Nat.mul_lt_mul_left (by decide : 0 < (2 : Nat))).2 hpred
theorem amplification_exponent_large (n : Nat) :
4 * (n + 1) ≤
2 ^ (Nat.clog 2 (n + 1) + 2) := by
calc
4 * (n + 1) ≤
4 * 2 ^ Nat.clog 2 (n + 1) := by
gcongr
exact
Nat.le_pow_clog (b := 2)
(by decide : 1 < (2 : Nat)) (n + 1)
_ = 2 ^ (Nat.clog 2 (n + 1) + 2) := by
rw [pow_add]
norm_num
ring
theorem seven_four_dominated :
2 * 7 ^ 4 ≤ 9 ^ 4 := by decide
theorem error_ratio_power
(inputLength exponent : Nat)
(hexponent : 4 * (inputLength + 1) ≤ exponent) :
2 ^ (inputLength + 1) * 7 ^ exponent ≤
9 ^ exponent := by
obtain ⟨extra, rfl⟩ :=
Nat.exists_eq_add_of_le hexponent
have hbase :
2 ^ (inputLength + 1) *
7 ^ (4 * (inputLength + 1)) ≤
9 ^ (4 * (inputLength + 1)) := by
calc
2 ^ (inputLength + 1) *
7 ^ (4 * (inputLength + 1))
= (2 * 7 ^ 4) ^ (inputLength + 1) := by
rw [mul_pow, Nat.pow_mul]
_ ≤ (9 ^ 4) ^ (inputLength + 1) :=
Nat.pow_le_pow_left seven_four_dominated _
_ = 9 ^ (4 * (inputLength + 1)) := by
rw [← Nat.pow_mul]
calc
2 ^ (inputLength + 1) *
7 ^ (4 * (inputLength + 1) + extra)
=
(2 ^ (inputLength + 1) *
7 ^ (4 * (inputLength + 1))) * 7 ^ extra := by
rw [pow_add]
ring
_ ≤ 9 ^ (4 * (inputLength + 1)) * 7 ^ extra := by
gcongr
_ ≤ 9 ^ (4 * (inputLength + 1)) * 9 ^ extra := by
exact Nat.mul_le_mul_left _
(Nat.pow_le_pow_left (by decide : (7 : Nat) ≤ 9) _)
_ = 9 ^ (4 * (inputLength + 1) + extra) := by
rw [pow_add]
theorem invariant_implies_target
(inputLength bad total exponent : Nat)
(hinvariant :
3 * 9 ^ exponent * bad ≤ 7 ^ exponent * total)
(hexponent : 4 * (inputLength + 1) ≤ exponent) :
2 ^ (inputLength + 1) * bad ≤ total := by
have hratio :=
error_ratio_power inputLength exponent hexponent
have hscaled :
7 ^ exponent *
(2 ^ (inputLength + 1) * bad) ≤
7 ^ exponent * total := by
calc
7 ^ exponent *
(2 ^ (inputLength + 1) * bad)
=
(2 ^ (inputLength + 1) * 7 ^ exponent) * bad := by ring
_ ≤ 9 ^ exponent * bad := by
gcongr
_ ≤ 3 * 9 ^ exponent * bad := by
have h :
9 ^ exponent * bad ≤
3 * (9 ^ exponent * bad) := by omega
simpa [Nat.mul_assoc] using h
_ ≤ 7 ^ exponent * total := hinvariant
exact
Nat.le_of_mul_le_mul_left hscaled (Nat.pow_pos (by decide))
abbrev amplificationDepth := amplificationDepthConstruction
theorem ternaryBad_amplified_bound {Ω : Type*} [Fintype Ω]
(bad : Ω → Prop) [DecidablePred bad]
(hthird : 3 * badCard bad ≤ Fintype.card Ω)
(inputLength : Nat) :
2 ^ (inputLength + 1) *
badCard
(ternaryBad bad (amplificationDepth inputLength)) ≤
Fintype.card
(TernarySample Ω (amplificationDepth inputLength)) := by
let rounds := Nat.clog 2 (inputLength + 1) + 2
have hinvariant :=
ternaryBad_iterated_invariant bad hthird rounds
have hdepth :
rounds + 1 = amplificationDepth inputLength := by
simp [rounds, amplificationDepthConstruction]
rw [hdepth] at hinvariant
apply
invariant_implies_target inputLength _ _ (2 ^ rounds)
hinvariant
simpa [rounds] using amplification_exponent_large inputLength
theorem ternary_leaf_count_polynomial (n : Nat) :
3 ^ amplificationDepth n ≤ 108 * (n + 1) ^ 2 := by
let c := Nat.clog 2 (n + 1)
have htwo :
2 ^ c < 2 * (n + 1) := by
simpa [c] using two_pow_clog_lt_twice (n + 1) (Nat.succ_pos n)
have hthreeFour :
3 ^ c ≤ 4 ^ c :=
Nat.pow_le_pow_left (by omega) _
have hfour :
4 ^ c = (2 ^ c) ^ 2 := by
calc
4 ^ c = (2 ^ 2) ^ c := by norm_num
_ = 2 ^ (2 * c) := by rw [Nat.pow_mul]
_ = 2 ^ (c * 2) := by rw [Nat.mul_comm]
_ = (2 ^ c) ^ 2 := by rw [Nat.pow_mul]
change 3 ^ (c + 3) ≤ 108 * (n + 1) ^ 2
rw [pow_add]
norm_num
calc
3 ^ c * 27 ≤ 4 ^ c * 27 := by gcongr
_ = (2 ^ c) ^ 2 * 27 := by rw [hfour]
_ ≤ (2 * (n + 1)) ^ 2 * 27 := by
gcongr
_ = 108 * (n + 1) ^ 2 := by ring
theorem badCard_congr {Ω : Type*} [Fintype Ω]
{bad₁ bad₂ : Ω → Prop}
[DecidablePred bad₁] [DecidablePred bad₂]
(h : ∀ sample, bad₁ sample ↔ bad₂ sample) :
badCard bad₁ = badCard bad₂ := by
unfold badCard
congr 1
ext sample
simp only [Finset.mem_filter, Finset.mem_univ, true_and]
exact h sample
theorem badCard_comp_equiv {α β : Type*}
[Fintype α] [Fintype β]
(equiv : α ≃ β)
(bad : β → Prop) [DecidablePred bad] :
badCard (fun sample => bad (equiv sample)) =
badCard bad := by
classical
unfold badCard
rw [← Fintype.card_subtype, ← Fintype.card_subtype]
exact
Fintype.card_congr
(equiv.subtypeEquiv fun _ => Iff.rfl)
abbrev majorityVote := majorityVoteConstruction
abbrev ternaryVote := @ternaryVoteConstruction
theorem majorityVote_eq_true_iff (a b c : Bool) :
majorityVote a b c = true ↔
majorityBad (fun x : Bool => x = true) (a, b, c) := by
cases a <;> cases b <;> cases c <;>
decide
theorem majorityVote_eq_false_iff (a b c : Bool) :
majorityVote a b c = false ↔
majorityBad (fun x : Bool => x = false) (a, b, c) := by
cases a <;> cases b <;> cases c <;>
decide
theorem ternaryVote_eq_true_iff {Ω : Type*}
(vote : Ω → Bool) (depth : Nat)
(sample : TernarySample Ω depth) :
ternaryVote vote depth sample = true ↔
ternaryBad (fun leaf => vote leaf = true) depth sample := by
induction depth with
| zero => rfl
| succ depth ih =>
change
majorityVote
(ternaryVote vote depth sample.1)
(ternaryVote vote depth sample.2.1)
(ternaryVote vote depth sample.2.2) = true ↔
_
rw [majorityVote_eq_true_iff]
simp only [majorityBad, ternaryBad]
simp_rw [ih]
theorem ternaryVote_eq_false_iff {Ω : Type*}
(vote : Ω → Bool) (depth : Nat)
(sample : TernarySample Ω depth) :
ternaryVote vote depth sample = false ↔
ternaryBad (fun leaf => vote leaf = false) depth sample := by
induction depth with
| zero => rfl
| succ depth ih =>
change
majorityVote
(ternaryVote vote depth sample.1)
(ternaryVote vote depth sample.2.1)
(ternaryVote vote depth sample.2.2) = false ↔
_
rw [majorityVote_eq_false_iff]
simp only [majorityBad, ternaryBad]
simp_rw [ih]
abbrev paddedBitString := paddedBitStringConstruction
theorem paddedBitString_toList {length : Nat}
(bits : BitString length) :
paddedBitString length bits.toList = bits := by
funext i
simp [paddedBitStringConstruction, BitString.toList,
List.getD_eq_getElem]
abbrev ternaryMap := @ternaryMapConstruction
theorem ternaryVote_ternaryMap {α β : Type*}
(map : α → β) (vote : β → Bool)
(depth : Nat) (sample : TernarySample α depth) :
ternaryVote vote depth (ternaryMap map depth sample) =
ternaryVote (fun leaf => vote (map leaf)) depth sample := by
induction depth with
| zero => rfl
| succ depth ih =>
change
∀ sample,
ternaryVoteConstruction vote depth
(ternaryMapConstruction map depth sample) =
ternaryVoteConstruction
(fun leaf => vote (map leaf)) depth sample at ih
simp only [ternaryMapConstruction, ternaryVoteConstruction]
rw [ih, ih, ih]
abbrev ternaryListTree := ternaryListTreeConstruction
theorem ternaryListTree_toList
(randomBits depth : Nat)
(flat : BitString (randomBits * 3 ^ depth)) :
ternaryListTree randomBits depth flat.toList =
ternaryMap
(fun leaf : BitString randomBits => leaf.toList)
depth
(flatTernaryEquiv randomBits depth flat) := by
change
ternaryListTreeConstruction randomBits depth flat.toList =
ternaryMapConstruction
(fun leaf : BitString randomBits => leaf.toList)
depth
(flatTernaryEquivConstruction randomBits depth flat)
unfold ternaryListTreeConstruction
exact
congrArg
(fun encoded =>
ternaryMapConstruction
(fun leaf : BitString randomBits => leaf.toList)
depth
(flatTernaryEquivConstruction
randomBits depth encoded))
(paddedBitString_toList flat)
def amplifiedRandomBitCount
(randomBits : Nat → Nat) (inputLength : Nat) : Nat :=
randomBits inputLength * 3 ^ amplificationDepth inputLength
abbrev ternaryAmplifiedVerifier :=
ternaryAmplifiedVerifierConstruction
theorem ternaryAmplifiedVerifier_toList_eq_true_iff
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(input : List Bool)
(flat :
BitString
(amplifiedRandomBitCount randomBits input.length)) :
ternaryAmplifiedVerifier verifier
input flat.toList = true ↔
ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = true)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat) := by
simp only [ternaryAmplifiedVerifierConstruction,
amplifiedRandomBitCount]
have hpositive :
0 < 3 ^ amplificationDepth input.length :=
pow_pos (by decide) _
have hlength :
flat.toList.length =
randomBits input.length *
3 ^ amplificationDepth input.length := by
simp only [BitString.toList]
exact List.length_ofFn
have hwidth :
flat.toList.length /
3 ^ amplificationDepth input.length =
randomBits input.length := by
rw [hlength]
rw [Nat.mul_comm]
exact Nat.mul_div_right _ hpositive
have htree :
ternaryListTree
(flat.toList.length /
3 ^ amplificationDepth input.length)
(amplificationDepth input.length) flat.toList =
ternaryListTree
(randomBits input.length)
(amplificationDepth input.length) flat.toList :=
congrArg
(fun width =>
ternaryListTree width
(amplificationDepth input.length) flat.toList)
hwidth
have hvote :
ternaryVote (verifier input)
(amplificationDepth input.length)
(ternaryListTree
(flat.toList.length /
3 ^ amplificationDepth input.length)
(amplificationDepth input.length) flat.toList) =
ternaryVote
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat) := by
calc
_ = ternaryVote (verifier input)
(amplificationDepth input.length)
(ternaryListTree
(randomBits input.length)
(amplificationDepth input.length) flat.toList) :=
congrArg
(fun tree =>
ternaryVote (verifier input)
(amplificationDepth input.length) tree)
htree
_ = ternaryVote (verifier input)
(amplificationDepth input.length)
(ternaryMap
(fun leaf : BitString (randomBits input.length) =>
leaf.toList)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat)) :=
congrArg
(fun tree =>
ternaryVote (verifier input)
(amplificationDepth input.length) tree)
(ternaryListTree_toList
(randomBits input.length)
(amplificationDepth input.length) flat)
_ = _ := ternaryVote_ternaryMap _ _ _ _
constructor
· intro h
apply (ternaryVote_eq_true_iff _ _ _).mp
exact hvote.symm.trans h
· intro h
exact
hvote.trans
((ternaryVote_eq_true_iff _ _ _).mpr h)
theorem ternaryAmplifiedVerifier_toList_eq_false_iff
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(input : List Bool)
(flat :
BitString
(amplifiedRandomBitCount randomBits input.length)) :
ternaryAmplifiedVerifier verifier
input flat.toList = false ↔
ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = false)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat) := by
simp only [ternaryAmplifiedVerifierConstruction,
amplifiedRandomBitCount]
have hpositive :
0 < 3 ^ amplificationDepth input.length :=
pow_pos (by decide) _
have hlength :
flat.toList.length =
randomBits input.length *
3 ^ amplificationDepth input.length := by
simp only [BitString.toList]
exact List.length_ofFn
have hwidth :
flat.toList.length /
3 ^ amplificationDepth input.length =
randomBits input.length := by
rw [hlength]
rw [Nat.mul_comm]
exact Nat.mul_div_right _ hpositive
have htree :
ternaryListTree
(flat.toList.length /
3 ^ amplificationDepth input.length)
(amplificationDepth input.length) flat.toList =
ternaryListTree
(randomBits input.length)
(amplificationDepth input.length) flat.toList :=
congrArg
(fun width =>
ternaryListTree width
(amplificationDepth input.length) flat.toList)
hwidth
have hvote :
ternaryVote (verifier input)
(amplificationDepth input.length)
(ternaryListTree
(flat.toList.length /
3 ^ amplificationDepth input.length)
(amplificationDepth input.length) flat.toList) =
ternaryVote
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat) := by
calc
_ = ternaryVote (verifier input)
(amplificationDepth input.length)
(ternaryListTree
(randomBits input.length)
(amplificationDepth input.length) flat.toList) :=
congrArg
(fun tree =>
ternaryVote (verifier input)
(amplificationDepth input.length) tree)
htree
_ = ternaryVote (verifier input)
(amplificationDepth input.length)
(ternaryMap
(fun leaf : BitString (randomBits input.length) =>
leaf.toList)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat)) :=
congrArg
(fun tree =>
ternaryVote (verifier input)
(amplificationDepth input.length) tree)
(ternaryListTree_toList
(randomBits input.length)
(amplificationDepth input.length) flat)
_ = _ := ternaryVote_ternaryMap _ _ _ _
constructor
· intro h
apply (ternaryVote_eq_false_iff _ _ _).mp
exact hvote.symm.trans h
· intro h
exact
hvote.trans
((ternaryVote_eq_false_iff _ _ _).mpr h)
theorem acceptingCard_ternaryAmplifiedVerifier
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(input : List Bool) :
acceptingCard
(ternaryAmplifiedVerifier verifier)
input (amplifiedRandomBitCount randomBits input.length) =
badCard
(ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = true)
(amplificationDepth input.length)) := by
classical
letI :
DecidablePred fun flat :
BitString (amplifiedRandomBitCount randomBits input.length) =>
ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = true)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat) :=
fun flat => ternaryBadDecidable _ _ _
change
badCard
(fun flat :
BitString
(amplifiedRandomBitCount randomBits input.length) =>
ternaryAmplifiedVerifier verifier
input flat.toList = true) = _
calc
badCard
(fun flat :
BitString
(amplifiedRandomBitCount randomBits input.length) =>
ternaryAmplifiedVerifier verifier
input flat.toList = true)
=
badCard
(fun flat =>
ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = true)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat)) :=
badCard_congr fun flat =>
ternaryAmplifiedVerifier_toList_eq_true_iff
randomBits verifier input flat
_ = _ :=
badCard_comp_equiv
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length))
(ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = true)
(amplificationDepth input.length))
theorem rejectingCard_ternaryAmplifiedVerifier
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(input : List Bool) :
rejectingCard
(ternaryAmplifiedVerifier verifier)
input (amplifiedRandomBitCount randomBits input.length) =
badCard
(ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = false)
(amplificationDepth input.length)) := by
classical
letI :
DecidablePred fun flat :
BitString (amplifiedRandomBitCount randomBits input.length) =>
ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = false)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat) :=
fun flat => ternaryBadDecidable _ _ _
change
badCard
(fun flat :
BitString
(amplifiedRandomBitCount randomBits input.length) =>
ternaryAmplifiedVerifier verifier
input flat.toList = false) = _
calc
badCard
(fun flat :
BitString
(amplifiedRandomBitCount randomBits input.length) =>
ternaryAmplifiedVerifier verifier
input flat.toList = false)
=
badCard
(fun flat =>
ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = false)
(amplificationDepth input.length)
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length) flat)) :=
badCard_congr fun flat =>
ternaryAmplifiedVerifier_toList_eq_false_iff
randomBits verifier input flat
_ = _ :=
badCard_comp_equiv
(flatTernaryEquiv
(randomBits input.length)
(amplificationDepth input.length))
(ternaryBad
(fun leaf : BitString (randomBits input.length) =>
verifier input leaf.toList = false)
(amplificationDepth input.length))
theorem polynomiallyBounded_amplifiedRandomBitCount
{randomBits : Nat → Nat}
(hrandomBits : PolynomiallyBounded randomBits) :
PolynomiallyBounded
(amplifiedRandomBitCount randomBits) := by
rcases hrandomBits with ⟨coefficient, degree, hbound⟩
refine ⟨108 * coefficient, degree + 2, ?_⟩
intro n
calc
amplifiedRandomBitCount randomBits n =
randomBits n * 3 ^ amplificationDepth n := rfl
_ ≤ (coefficient * (n + 1) ^ degree) *
(108 * (n + 1) ^ 2) := by
gcongr
· exact hbound n
· exact ternary_leaf_count_polynomial n
_ = (108 * coefficient) * (n + 1) ^ (degree + 2) := by
rw [pow_add]
ring
theorem acceptingCard_add_rejectingCard_amp
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBitCount : Nat) :
acceptingCard verifier input randomBitCount +
rejectingCard verifier input randomBitCount =
Fintype.card (BitString randomBitCount) := by
classical
unfold acceptingCard rejectingCard
let accepts : BitString randomBitCount → Prop :=
fun random => verifier input random.toList = true
have hpartition :=
Finset.card_filter_add_card_filter_not
(s := (Finset.univ : Finset (BitString randomBitCount)))
accepts
rw [show
(Finset.univ.filter fun random : BitString randomBitCount =>
verifier input random.toList = false) =
Finset.univ.filter fun random => ¬ accepts random by
ext random
simp only [Finset.mem_filter, Finset.mem_univ, true_and,
accepts]
cases verifier input random.toList <;> simp]
exact hpartition
theorem rejectingCard_third_of_accepting_two_thirds
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBitCount : Nat)
(haccept :
3 * acceptingCard verifier input randomBitCount ≥
2 * Fintype.card (BitString randomBitCount)) :
3 * rejectingCard verifier input randomBitCount ≤
Fintype.card (BitString randomBitCount) := by
have hpartition :=
acceptingCard_add_rejectingCard_amp
verifier input randomBitCount
omega
theorem acceptingCard_third_of_rejecting_two_thirds
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBitCount : Nat)
(hreject :
3 * rejectingCard verifier input randomBitCount ≥
2 * Fintype.card (BitString randomBitCount)) :
3 * acceptingCard verifier input randomBitCount ≤
Fintype.card (BitString randomBitCount) := by
have hpartition :=
acceptingCard_add_rejectingCard_amp
verifier input randomBitCount
omega
theorem badCard_rejecting
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBitCount : Nat) :
badCard
(fun random : BitString randomBitCount =>
verifier input random.toList = false) =
rejectingCard verifier input randomBitCount := by
rfl
theorem badCard_accepting
(verifier : List Bool → List Bool → Bool)
(input : List Bool) (randomBitCount : Nat) :
badCard
(fun random : BitString randomBitCount =>
verifier input random.toList = true) =
acceptingCard verifier input randomBitCount := by
rfl
theorem flatTernary_card
(randomBitCount depth : Nat) :
Fintype.card
(TernarySample (BitString randomBitCount) depth) =
Fintype.card
(BitString (randomBitCount * 3 ^ depth)) := by
exact
(Fintype.card_congr
(flatTernaryEquiv randomBitCount depth)).symm
theorem bounded_error_verifier_amplification_of_dpt
(language : Language)
(randomBits : Nat → Nat)
(verifier : List Bool → List Bool → Bool)
(hrandomBits : PolynomiallyBounded randomBits)
(hboundedError :
∀ input : List Bool,
(input ∈ language →
3 * acceptingCard verifier input (randomBits input.length) ≥
2 * Fintype.card
(BitString (randomBits input.length))) ∧
(input ∉ language →
3 * rejectingCard verifier input (randomBits input.length) ≥
2 * Fintype.card
(BitString (randomBits input.length))))
(hamplifiedVerifier :
DecidesInPolynomialTime
(fun input : Fin 2 → List Bool =>
ternaryAmplifiedVerifier verifier
(input 0) (input 1) = true)) :
∃ (amplifiedRandomBits : Nat → Nat)
(amplifiedVerifier : List Bool → List Bool → Bool),
PolynomiallyBounded amplifiedRandomBits ∧
DecidesInPolynomialTime
(fun input : Fin 2 → List Bool =>
amplifiedVerifier (input 0) (input 1) = true) ∧
∀ input : List Bool,
(input ∈ language →
2 ^ (input.length + 1) *
rejectingCard amplifiedVerifier input
(amplifiedRandomBits input.length) ≤
Fintype.card
(BitString (amplifiedRandomBits input.length))) ∧
(input ∉ language →
2 ^ (input.length + 1) *
acceptingCard amplifiedVerifier input
(amplifiedRandomBits input.length) ≤
Fintype.card
(BitString (amplifiedRandomBits input.length))) := by
refine
⟨amplifiedRandomBitCount randomBits,
ternaryAmplifiedVerifier verifier,
polynomiallyBounded_amplifiedRandomBitCount hrandomBits,
hamplifiedVerifier, ?_⟩
intro input
constructor
· intro hmember
rw [rejectingCard_ternaryAmplifiedVerifier]
have hthird :
3 *
badCard
(fun random : BitString (randomBits input.length) =>
verifier input random.toList = false) ≤
Fintype.card (BitString (randomBits input.length)) := by
rw [badCard_rejecting]
exact
rejectingCard_third_of_accepting_two_thirds
verifier input (randomBits input.length)
((hboundedError input).1 hmember)
have hbound :=
ternaryBad_amplified_bound
(fun random : BitString (randomBits input.length) =>
verifier input random.toList = false)
hthird input.length
rw [flatTernary_card] at hbound
exact hbound
· intro hnonmember
rw [acceptingCard_ternaryAmplifiedVerifier]
have hthird :
3 *
badCard
(fun random : BitString (randomBits input.length) =>
verifier input random.toList = true) ≤
Fintype.card (BitString (randomBits input.length)) := by
rw [badCard_accepting]
exact
acceptingCard_third_of_rejecting_two_thirds
verifier input (randomBits input.length)
((hboundedError input).2 hnonmember)
have hbound :=
ternaryBad_amplified_bound
(fun random : BitString (randomBits input.length) =>
verifier input random.toList = true)
hthird input.length
rw [flatTernary_card] at hbound
exact hbound
end SipserGacsLautemannSource
Standard BPP error reduction by independent repetition and majority, instantiated with a ternary majority tree for the Sipser–Gács–Lautemann mission.