Documentation

ThreeMajority.AnyStartAsymptotics

The real inequalities of Theorem 4 of BCEKMN17 #

Phase 1 of Theorem 4 stops at k = ⌊n^{1/4} log^{1/8} n⌋ colours (phase1Colours n). For n large, 1 ≤ k ≤ n^{1/3 − 1/24}, and the two phases fit in O(n^{3/4} log^{7/8} n) rounds.

noncomputable def ThreeMajority.phase1Colours (n : ℕ) :

The number of colours at the end of Phase 1 of Theorem 4: ⌊n^{1/4} log^{1/8} n⌋.

Equations
Instances For
    theorem ThreeMajority.eventually_log_rpow_le_rpow (r : ℝ) {s : ℝ} (hs : 0 < s) :

    For s > 0, eventually log y ^ r ≤ y ^ s.

    The eventual conditions on y used for Theorem 4: 3 ≤ y, log y ≤ y^{1/4} and log^{1/8} y ≤ y^{1/24}.

    theorem ThreeMajority.rounds_le_of_bounds {A k x L M y : ℝ} (hA : 0 ≤ A) (hL : 1 ≤ L) (hkx : k ≤ x) (hxk : x ≤ 2 * k) (hLx : L ≤ x) (hM : 1 ≤ M) (hMx : M * x = y * L) (hx3 : x ^ 3 * √L = M) :
    24 * (y / k) * L + 1 + A * ((k ^ 2 * √L + k * L) * (k + L)) ≤ (49 + 4 * A) * M

    The algebra of the round count: if k ≤ x ≤ 2k, 1 ≤ L ≤ x, 1 ≤ M, M x = y L and x³ √L = M, the two phases take at most (49 + 4A) M rounds.

    theorem ThreeMajority.phase1_identities {y : ℝ} (hy : 3 ≤ y) (h1 : Real.log y ≤ y ^ (1 / 4)) :
    1 ≤ Real.log y ∧ Real.log y ≤ y ^ (1 / 4) * Real.log y ^ (1 / 8) ∧ 1 ≤ y ^ (3 / 4) * Real.log y ^ (7 / 8) ∧ y ^ (3 / 4) * Real.log y ^ (7 / 8) * (y ^ (1 / 4) * Real.log y ^ (1 / 8)) = y * Real.log y ∧ (y ^ (1 / 4) * Real.log y ^ (1 / 8)) ^ 3 * √(Real.log y) = y ^ (3 / 4) * Real.log y ^ (7 / 8)

    For real y ≥ 3 with log y ≤ y^{1/4}, x = y^{1/4} log^{1/8} y and M = y^{3/4} log^{7/8} y satisfy 1 ≤ log y ≤ x, 1 ≤ M, M x = y log y and x³ √(log y) = M.

    theorem ThreeMajority.anyStart_asymptotics (A : ℝ) (hA : 0 ≤ A) :
    ∃ (C : ℝ) (N : ℝ), ∀ (n : ℕ), N ≤ ↑n → 2 ≤ n ∧ 1 ≤ phase1Colours n ∧ ↑(phase1Colours n) ≤ ↑n ^ (1 / 3 - 1 / 24) ∧ 24 * (↑n / ↑(phase1Colours n)) * Real.log ↑n + 1 + A * ((↑(phase1Colours n) ^ 2 * √(Real.log ↑n) + ↑(phase1Colours n) * Real.log ↑n) * (↑(phase1Colours n) + Real.log ↑n)) ≤ C * ↑n ^ (3 / 4) * Real.log ↑n ^ (7 / 8)

    The asymptotic bookkeeping of Theorem 4: for n large, k = phase1Colours n satisfies 1 ≤ k ≤ n^{1/3 − 1/24}, and Phase 1 (24 (n/k) log n + 1 rounds) together with Phase 2 (A (k² √log n + k log n)(k + log n) rounds) fits in C n^{3/4} log^{7/8} n rounds.