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.
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)
:
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.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.