Documentation

ThreeMajority.Main

Main theorem: 3-majority reaches consensus in O(log n) rounds w.h.p. #

Glues growth_phase1 (10 rounds) to the three saturation stages (saturation_stage2a, 2b, 2c; T2a n + 2 rounds total) via the same expList-conditioning idiom the push protocol's Main.lean uses to glue its own two phases (prNotAllInformed_le).

I ≠ univ iff there is at least one dissenting agent.

theorem ThreeMajority.hfloor4_of_hbig {n : ℕ} (hbig : 30 ≤ Real.log ↑n) :
500 * Real.log ↑n ≤ ↑n / 4

log n ≥ 30 already forces 500 log n ≤ n/4: makes an explicit hfloor4 hypothesis redundant everywhere it appears alongside hbig.

theorem ThreeMajority.saturation_2b2c {n : ℕ} (hbig : 30 ≤ Real.log ↑n) (I : Finset (Fin n)) (hUI : ↑n - ↑I.card ≤ 500 * Real.log ↑n) :
(expList (Tgt3 n) 2 fun (l : List (Tgt3 n)) => if 1 ≤ ↑n - ↑(run I l).card then 1 else 0) ≤ Real.exp (-Real.log ↑n) + 300 / ↑n

Stages 2b and 2c combined: two rounds, from U ≤ 500 log n to exactly U = 0.

theorem ThreeMajority.saturation_2a2b2c {n : ℕ} (hbig : 30 ≤ Real.log ↑n) (I₀ : Finset (Fin n)) (hI₀ : ↑n - ↑I₀.card ≤ ↑n / 4) :
(expList (Tgt3 n) (T2a n + 2) fun (l : List (Tgt3 n)) => if 1 ≤ ↑n - ↑(run I₀ l).card then 1 else 0) ≤ ↑(T2a n) * Real.exp (-2 * Real.log ↑n) + (Real.exp (-Real.log ↑n) + 300 / ↑n)

All three saturation stages combined: T2a n + 2 rounds, from U ≤ n/4 to exactly U = 0.

theorem ThreeMajority.majority3_consensus_fail_le {n : ℕ} (hbig : 30 ≤ Real.log ↑n) (I₀ : Finset (Fin n)) (hI₀ : ↑n * (3 / 5) ≤ ↑I₀.card) :
(expList (Tgt3 n) (10 + (T2a n + 2)) fun (l : List (Tgt3 n)) => if 1 ≤ ↑n - ↑(run I₀ l).card then 1 else 0) ≤ 10 * Real.exp (-(1 / 10 ^ 7) * ↑n) + (↑(T2a n) * Real.exp (-2 * Real.log ↑n) + (Real.exp (-Real.log ↑n) + 300 / ↑n))

Main theorem: 3-majority reaches consensus in 10 + T2a n + 2 = O(log n) rounds, with failure probability bounded by an explicit, n-dependent constant that → 0 as n → ∞. Combines growth_phase1 (10 rounds) with saturation_2a2b2c (T2a n + 2 rounds) exactly as the push protocol's prNotAllInformed_le combines its own two phases.

theorem ThreeMajority.majority3_consensus_fail_le_clean {n : ℕ} (hbig : 30 ≤ Real.log ↑n) (I₀ : Finset (Fin n)) (hI₀ : ↑n * (3 / 5) ≤ ↑I₀.card) :
(expList (Tgt3 n) (10 + (T2a n + 2)) fun (l : List (Tgt3 n)) => if 1 ≤ ↑n - ↑(run I₀ l).card then 1 else 0) ≤ 500 / ↑n

Clean numeric bound: the total failure probability is at most 500/n.

theorem ThreeMajority.majority3_consensus_whp {n : ℕ} (hbig : 30 ≤ Real.log ↑n) (I₀ : Finset (Fin n)) (hI₀ : ↑n * (3 / 5) ≤ ↑I₀.card) :
1 - 500 / ↑n ≤ expList (Tgt3 n) (10 + (T2a n + 2)) fun (l : List (Tgt3 n)) => if run I₀ l = Finset.univ then 1 else 0

Consensus with high probability: starting from an initial opinion-1 majority of at least 60%, and for n large enough (log n ≥ 30 suffices), 3-majority reaches full consensus within 10 + T2a n + 2 = O(log n) rounds with probability at least 1 - 500/n.