Documentation

Dynamics.Scalar

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.

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 #

theorem Dynamics.ceil_add_ceil_le {a b c : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b) (h : a + b + 2 ≤ c) :

Two ceilings fit under a third: ⌈a⌉₊ + ⌈b⌉₊ ≤ ⌈c⌉₊ when a + b + 2 ≤ c. Replaces Median.ceil_add_ceil_le.

theorem Dynamics.mul_ceil_le_ceil {k : ℕ} {a b : ℝ} (ha : 0 ≤ a) (h : ↑k * (a + 1) ≤ b) :

k copies of ⌈a⌉₊ fit under ⌈b⌉₊ when k (a + 1) ≤ b. Replaces Median.mul_ceil_le_ceil.

theorem Dynamics.nat_ceil_mul_le_of_le {a b y : ℝ} (ha : 0 ≤ a) (hab : a ≤ b) :

⌈a y⌉₊ ≤ ⌈b y⌉₊ for 0 ≤ a ≤ b, whatever the sign of y (both vanish if y ≤ 0). Replaces Median.nat_ceil_mul_le_of_le.

Phase counts #

theorem Dynamics.le_pow_ceil_real {w : ℝ} (hw : 1 ≤ w) {q : ℝ} (hq : 1 < q) :

w ≤ q ^ ⌈log w / log q⌉₊ for w ≥ 1 and q > 1. Replaces Median.le_pow_ceil_real.

theorem Dynamics.le_pow_ceil {n : ℕ} (hn : 1 ≤ n) {q : ℝ} (hq : 1 < q) :

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.

theorem Dynamics.exists_lt_pow_mul {q : ℝ} (hq : 1 < q) {Δ N : ℝ} (hΔ : 0 < Δ) (hΔN : Δ ≤ N) :
∃ (T : ℕ), N < q ^ T * Δ ∧ ↑T ≤ Real.log (N / Δ) / Real.log q + 2

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.

theorem Dynamics.exists_le_two_pow_two_pow {N : ℝ} (hN : 2 ≤ N) :
∃ (T : ℕ), N ≤ 2 ^ 2 ^ T ∧ ↑T ≤ 2 * Real.log (Real.log N) + 3

Doubly exponential growth. If N ≥ 2, then N ≤ 2 ^ 2 ^ T for some T ≤ 2 log log N + 3. Replaces Median.exists_le_two_pow_two_pow.

Powers of logarithms #

theorem Dynamics.pow_three_le_of_log {c x : ℝ} (hc : 0 ≤ c) (hx : 0 < x) (h : 3 * c ≤ Real.log x) :
c ^ 3 ≤ x

c³ ≤ x as soon as 3c ≤ log x, since c ≤ eᶜ. Replaces Median.pow_three_le_of_log.

theorem Dynamics.log_cube_le {n : ℕ} (hn : 1 ≤ n) :
Real.log ↑n ^ 3 / 6 ≤ ↑n

(log n)³ / 6 ≤ n for n ≥ 1 (eˣ ≥ x³/6 at x = log n). Replaces Undecided.log_cube_le.

theorem Dynamics.log_pow_four_div_le {x : ℝ} (hx : 0 < x) (hL : 0 ≤ Real.log x) :
Real.log x ^ 4 / 24 ≤ x

(log x)⁴ / 24 ≤ x for x > 0 with log x ≥ 0. Replaces Median.log_pow_four_div_le.

theorem Dynamics.half_le_log_one_add {ε : ℝ} (h0 : 0 ≤ ε) (h1 : ε ≤ 1) :
ε / 2 ≤ Real.log (1 + ε)

ε/2 ≤ log (1 + ε) for 0 ≤ ε ≤ 1, from 1 - 1/x ≤ log x. Replaces Undecided.Plurality.half_le_log_one_add.

Failure budgets #

theorem Dynamics.mul_one_div_sq_le {N S C : ℝ} (hN : 0 < N) (hS : S ≤ C * N) :
S * (1 / N ^ 2) ≤ C / N

The failure budget. S · N⁻² ≤ C/N whenever S ≤ C N (and N > 0). Replaces Median.mul_one_div_sq_le.

theorem Dynamics.prod_one_sub_le_exp_neg_sum {ι : Type u_1} (s : Finset ι) (δ : ι → ℝ) (hδ : ∀ i ∈ s, δ i ≤ 1) :
∏ i ∈ s, (1 - δ i) ≤ Real.exp (-∑ i ∈ s, δ i)

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.