Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_amplification_counting

Definition

by Henry Yuen · Jul 24, 2026 · Mathlib c5ea003 (Lean v4.30.0)

bppcomplexity-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 [BitString.toList, amplifiedRandomBitCount]
  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 [BitString.toList, amplifiedRandomBitCount]
  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
  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
  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 SipserGacsLautemann
Source
Standard BPP error reduction by independent repetition and majority, instantiated with a ternary majority tree for the Sipser–Gács–Lautemann mission.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me