Scalar facts shared by the packages #
Real and natural-number inequalities that several model packages used to prove locally, mostly to count rounds and phases in high-probability statements. No probability is involved.
- Round budgets: ceilings add up (
ceil_add_ceil_le,mul_ceil_le_ceil), and⌈a y⌉₊ ≤ ⌈b y⌉₊for0 ≤ a ≤ b(nat_ceil_mul_le_of_le). - Phase counts:
w ≤ q ^ ⌈log w / log q⌉₊forq > 1(le_pow_ceil_real, andle_pow_ceilforw = n : ℕ); geometric growth by a factorqpassesNwithinlog (N/Δ) / log q + 2steps (exists_lt_pow_mul), and2 ^ 2 ^ TpassesN ≥ 2within2 log log N + 3steps (exists_le_two_pow_two_pow). - Powers of logarithms:
c³ ≤ xonce3c ≤ log x(pow_three_le_of_log),log n ^ 3 / 6 ≤ n(log_cube_le) andlog x ^ 4 / 24 ≤ x(log_pow_four_div_le), all from Mathlib'sReal.pow_div_factorial_le_exp; andε/2 ≤ log (1 + ε)on[0, 1](half_le_log_one_add). - The failure budget
S · N⁻² ≤ C/NforS ≤ C N(mul_one_div_sq_le), and products of survival factors∏ (1 - δ_t) ≤ exp (-∑ δ_t)forδ_t ≤ 1(prod_one_sub_le_exp_neg_sum).
The bounds 1/2 ≤ log 2 ≤ 1 and the monotonicity of √(ℓ x) in x are used directly from
Mathlib (Real.log_two_gt_d9, Real.log_two_lt_d9, Real.sqrt_le_sqrt). Each docstring names
the package lemmas that the statement replaces.
Round budgets #
Phase counts #
n ≤ q ^ ⌈log n / log q⌉₊ for n ≥ 1 and q > 1: after that many phases of growth by a
factor q, a quantity starting at 1 exceeds n. Replaces Median.le_pow_ceil,
Plurality.le_pow_ceil and Undecided.le_pow_ceil.
Geometric growth. Growing by a factor q > 1 per step from Δ > 0, the value exceeds
N ≥ Δ after some T ≤ log (N/Δ) / log q + 2 steps. Replaces Median.exists_lt_pow_mul.
Powers of logarithms #
(log n)³ / 6 ≤ n for n ≥ 1 (eˣ ≥ x³/6 at x = log n). Replaces
Undecided.log_cube_le.
ε/2 ≤ log (1 + ε) for 0 ≤ ε ≤ 1, from 1 - 1/x ≤ log x. Replaces
Undecided.Plurality.half_le_log_one_add.
Failure budgets #
Products of survival factors: ∏ (1 - δ_t) ≤ exp (-∑ δ_t) when every δ_t ≤ 1, factor by
factor from 1 - x ≤ e^{-x}. Replaces the product step of Voter.prod_one_sub_le.