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):
- Stage 2a (
saturation_stage2a): geometric descent, contraction factor0.7(vs. the true5/8), fromn/4down to a floor of500 log n, over⌈6 log n⌉rounds, each with failure≤ n⁻². - Stage 2b (
saturation_stage2b): one round, jumping directly from theΘ(log n)floor to the fixed constant10(not scaled to the current mean) — since the mean is already tiny, this one round has astronomically small failure probability. - Stage 2c (
saturation_stage2c): the last round, fromU ≤ 10to exactlyU = 0, via ordinary Markov (E[U] = O(1/n), no concentration needed at all for the very last step).
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.
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.
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).
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).
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.
Instances For
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).
The number of stage-2a rounds.
Instances For
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⁻².
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).