Documentation

ThreeMajority.Saturation

Saturation phase #

Once the dissent count U_t = n - X_t drops to ≤ n/4 (guaranteed whp by growth_phase1), the majority map contracts it by a factor ≤ 5/8 per round in expectation (Corollary saturation). Getting U_t all the way to exactly 0 needs three distinct stages, because a single Chernoff bound using a fixed relative margin has an absolute floor around Θ(log n) (Mathlib's Hoeffding-style bound is mean-scaled, not range-scaled, but a fixed ratio Chernoff argument still needs the mean itself to be Ω(log n) for a polynomially-small per-round failure probability):

theorem ThreeMajority.saturation_round_closed {n : ℕ} (hn : 1 ≤ n) (I : Finset (Fin n)) {M k : ℝ} (hM0 : 0 < M) (hM1 : M ≤ ↑n / 4) (hkM : 5 / 8 * M ≤ k) (hUI : ↑n - ↑I.card ≤ M) :
(avg fun (r : Tgt3 n) => if k ≤ ↑n - ↑(step I r).card then 1 else 0) ≤ Real.exp (k - 5 / 8 * M - k * Real.log (k / (5 / 8 * M)))

General per-round upper-tail bound: given a reference dissent bound U_t ≤ M (M ≤ n/4) and any target k ≥ (5/8)M (an upper bound on the true one-round mean), the probability of the next dissent count exceeding k decays according to the closed-form Chernoff exponent.

theorem ThreeMajority.saturation_round_generic {n : ℕ} (_hn : 1 ≤ n) (I : Finset (Fin n)) {μub k : ℝ} (hμub0 : 0 < μub) (hkμ : μub ≤ k) (hμ : ∑ v : Fin n, avg (Y_dis I v) ≤ μub) :
(avg fun (r : Tgt3 n) => if k ≤ ↑n - ↑(step I r).card then 1 else 0) ≤ Real.exp (k - μub - k * Real.log (k / μub))

Generic per-round upper-tail bound, parametrized directly by an upper bound μub on the true mean (rather than deriving it from M via the linear 5/8 estimate, as saturation_round_closed does). Used by stage 2b, where M is small and the quadratic estimate g(M) ≤ 3M²/n is the tight one — the linear 5/8·M bound is technically still valid but far too crude to be useful there.

theorem ThreeMajority.saturation_mean_quad {n : ℕ} (hn1 : 1 ≤ n) (I : Finset (Fin n)) {M : ℝ} (_hM0 : 0 ≤ M) (hUI : ↑n - ↑I.card ≤ M) :
∑ v : Fin n, avg (Y_dis I v) ≤ 3 * M ^ 2 / ↑n

Quadratic mean bound: for any dissent bound U_t ≤ M (M ≤ n), the true one-round mean is at most 3M²/n — the crude, but here tight, bound 1-p(x) ≤ 3(1-x)² (dropping the 5/8-type refinement).

theorem ThreeMajority.saturation_round_numeric {n : ℕ} (hn : 1 ≤ n) (I : Finset (Fin n)) {M k : ℝ} (hM0 : 0 < M) (hM1 : M ≤ ↑n / 4) (hkM : 5 / 8 * M ≤ k) (hk0 : 0 < k) (hUI : ↑n - ↑I.card ≤ M) :
(avg fun (r : Tgt3 n) => if k ≤ ↑n - ↑(step I r).card then 1 else 0) ≤ Real.exp (-(k - 5 / 8 * M) ^ 2 / (k + 5 / 8 * M))

Numeric per-round upper-tail bound: the closed-form Chernoff exponent of saturation_round_closed, simplified via the quadratic-tight Padé bound Real.le_log_one_add_of_nonneg to -λ²/(k+μub), λ = k - (5/8)M. This is the only place the upward direction needs a quadratic-tight log bound (the downward direction used log_ge_quadratic from Bounds.lean; here Mathlib's ready-made Padé bound suffices).

theorem ThreeMajority.saturation_round_contract {n : ℕ} (hn : 1 ≤ n) (I : Finset (Fin n)) {M : ℝ} (hM0 : 0 < M) (hM1 : M ≤ ↑n / 4) (hUI : ↑n - ↑I.card ≤ M) :
(avg fun (r : Tgt3 n) => if 7 / 10 * M ≤ ↑n - ↑(step I r).card then 1 else 0) ≤ Real.exp (-(1 / 250) * M)

Stage 2a per-round bound: guaranteed contraction factor 0.7 (vs. the true 5/8), with failure probability ≤ exp(-M/250).

noncomputable def ThreeMajority.satAfter (n : ℕ) (M : ℝ) (i : ℕ) :

The deterministic dissent-count target after i stage-2a rounds, starting from bound M, clamped below at the floor 500 log n. Written in closed form (not recursively) so that satAfter n M (i+1) and satAfter n (0.7*M) i-style shifts agree definitionally on the unclamped branch, and only need max-monotonicity on the clamped one.

Equations
Instances For
    theorem ThreeMajority.satAfter_ge_floor (n : ℕ) (M : ℝ) (i : ℕ) :
    500 * Real.log ↑n ≤ satAfter n M i
    theorem ThreeMajority.satAfter_zero (n : ℕ) (M : ℝ) (hM : 500 * Real.log ↑n ≤ M) :
    satAfter n M 0 = M
    theorem ThreeMajority.satAfter_le_of_le {n : ℕ} {M : ℝ} (hM0 : 0 ≤ M) (hM1 : M ≤ ↑n / 4) (hfloor4 : 500 * Real.log ↑n ≤ ↑n / 4) (i : ℕ) :
    satAfter n M i ≤ ↑n / 4
    theorem ThreeMajority.satAfter_contract_le {n : ℕ} (hn1 : 1 ≤ n) (M : ℝ) (i : ℕ) :
    7 / 10 * satAfter n M i ≤ satAfter n M (i + 1)
    theorem ThreeMajority.saturation_fail_le {n : ℕ} (hn2 : 2 ≤ n) {M : ℝ} (hM0 : 500 * Real.log ↑n ≤ M) (hM1 : M ≤ ↑n / 4) (hfloor4 : 500 * Real.log ↑n ≤ ↑n / 4) (j i : ℕ) (I : Finset (Fin n)) :
    ↑n - ↑I.card ≤ satAfter n M i → (expList (Tgt3 n) j fun (l : List (Tgt3 n)) => if satAfter n M (i + j) < ↑n - ↑(run I l).card then 1 else 0) ≤ ↑j * Real.exp (-2 * Real.log ↑n)

    Stage 2a, union bound over j rounds: starting from a dissent bound M (500 log n ≤ M ≤ n/4), offset i rounds in, the probability that the dissent count exceeds satAfter n M (i+j) after j further rounds is at most j · n⁻² (n⁻² = exp(-2 log n)). Mirrors growth_fail_le's expList-conditioning idiom exactly, with the tail direction flipped (dissent shrinking, not opinion-1 count growing).

    noncomputable def ThreeMajority.T2a (n : ℕ) :

    The number of stage-2a rounds.

    Equations
    Instances For
      theorem ThreeMajority.satAfter_quarter_le_floor {n : ℕ} (hn2 : 2 ≤ n) :
      satAfter n (↑n / 4) (T2a n) ≤ 500 * Real.log ↑n
      theorem ThreeMajority.saturation_stage2a {n : ℕ} (hn2 : 2 ≤ n) (hfloor4 : 500 * Real.log ↑n ≤ ↑n / 4) (I₀ : Finset (Fin n)) (hI₀ : ↑n - ↑I₀.card ≤ ↑n / 4) :
      (expList (Tgt3 n) (T2a n) fun (l : List (Tgt3 n)) => if 500 * Real.log ↑n < ↑n - ↑(run I₀ l).card then 1 else 0) ≤ ↑(T2a n) * Real.exp (-2 * Real.log ↑n)

      Stage 2a, wrapped: starting from any dissent bound ≤ n/4, after T2a n = ⌈6 log n⌉ rounds the dissent count exceeds the floor 500 log n with probability at most T2a n · n⁻².

      theorem ThreeMajority.saturation_stage2b {n : ℕ} (hbig : 30 ≤ Real.log ↑n) (I : Finset (Fin n)) (hUI : ↑n - ↑I.card ≤ 500 * Real.log ↑n) :
      (avg fun (r : Tgt3 n) => if 10 ≤ ↑n - ↑(step I r).card then 1 else 0) ≤ Real.exp (-Real.log ↑n)

      Stage 2b: one round, jumping from the Θ(log n) floor directly to the fixed constant 10. Requires log n to be moderately large (≥ 30 suffices) — not because the bound is delicate, but because μ (the true mean, Θ((log n)²/n)) must beat the polynomial-in-log n target 10; a degree-11 Taylor lower bound on exp (Real.pow_div_factorial_le_exp), combined with the tangent-line log-log bound log_log_le_of_pos (far tighter, near log n ≈ 30, than a bound tangent at the fixed point e), already secures this once log n ≥ 30 (a low-degree bound such as the cubic case, or a log-log bound tangent at e, would instead force log n to be astronomically large).

      theorem ThreeMajority.saturation_stage2c {n : ℕ} (hn1 : 1 ≤ n) (I : Finset (Fin n)) (hUI : ↑n - ↑I.card ≤ 10) :
      (avg fun (r : Tgt3 n) => if 1 ≤ ↑n - ↑(step I r).card then 1 else 0) ≤ 300 / ↑n

      Stage 2c: the last round, from U ≤ 10 to exactly U = 0, via ordinary Markov — U_{t+1} is a nonnegative integer, so P[U_{t+1}≥1] ≤ E[U_{t+1}] ≤ 300/n, no concentration needed at all.