Documentation

Plurality.Lower

The lower bound for 3-majority (Section 4.1) #

From a balanced coloring, where every color has at most n/k + b nodes, no color can gain much in one round: its count exceeds n/k + (1 + 3/k) b with probability at most 1/n² (Lemma 4.1, lemma_4_1). The expectation bound uses ∑ₕ cₕ² ≥ n²/k (Cauchy–Schwarz), and the deviation bound is Hoeffding's inequality.

Theorem 4.2 (theorem_4_2): following the schedule b_t = (1 + 3/k)^t b, a union bound over rounds (Dynamics.expList_escape) and colors shows that as long as b (1 + 3/k)^T ≤ n/k, no color has more than 2n/k nodes after T rounds except with probability k T / n²; in particular the coloring is not monochromatic when k ≥ 3. theorem_4_2_log turns the condition into T ≤ (k/3) log (n / (k b)).

Range of k #

Lemma 4.1 needs b ≥ k √(n log n), so the schedule starts at b ≥ max ((n/k)^{1-ε}, k √(n log n)), and the number of rounds obtained is (k/3) log (n / (k b)). This is Ω(k log n) when k ≤ n^{1/4 - δ}, but it degenerates as k approaches (n / log n)^{1/4}, where n/k = k √(n log n). The paper states the theorem for all k ≤ (n / log n)^{1/4}; see FORMALIZATION_DIFFERENCES.md.

theorem Plurality.sq_div_le_sum_sq {n k : ℕ} (hk : 1 ≤ k) (x : Config n k) :
↑n ^ 2 / ↑k ≤ ∑ h : Fin k, ↑(count x h) ^ 2

∑ₕ cₕ² ≥ n²/k, by Cauchy–Schwarz.

theorem Plurality.mu_le_of_count_le {n k : ℕ} (hn : 1 ≤ n) (hk : 1 ≤ k) (x : Config n k) (j : Fin k) {b : ℝ} (hb0 : 0 ≤ b) (hb1 : b ≤ ↑n / ↑k) (hx : ↑(count x j) ≤ ↑n / ↑k + b) :
mu n (count x) j ≤ ↑n / ↑k + (1 + 2 / ↑k) * b

The expected count of a color with at most n/k + b nodes is at most n/k + (1 + 2/k) b, for 0 ≤ b ≤ n/k.

theorem Plurality.lemma_4_1 {n k : ℕ} (hn : 1 ≤ n) (hk : 1 ≤ k) (x : Config n k) (j : Fin k) {b : ℝ} (hb0 : ↑k * √(↑n * Real.log ↑n) ≤ b) (hb1 : b ≤ ↑n / ↑k) (hx : ↑(count x j) ≤ ↑n / ↑k + b) :
(Dynamics.avg fun (r : ThreeMajority.Tgt3 n) => if ↑n / ↑k + (1 + 3 / ↑k) * b ≤ ↑(count (step x r) j) then 1 else 0) ≤ 1 / ↑n ^ 2

Lemma 4.1. If color j has at most n/k + b nodes, where k √(n log n) ≤ b ≤ n/k, then after one round it has at least n/k + (1 + 3/k) b nodes with probability at most 1/n².

def Plurality.balancedSet (n : ℕ) {k : ℕ} (j : Fin k) (b : ℝ) (t : ℕ) :
Set (Config n k)

The threshold of round t: n/k + b (1 + 3/k)^t.

Equations
Instances For
    theorem Plurality.color_stays_small {n k : ℕ} (hn : 1 ≤ n) (hk : 1 ≤ k) (x : Config n k) (j : Fin k) {b : ℝ} (hb0 : ↑k * √(↑n * Real.log ↑n) ≤ b) (hx : ↑(count x j) ≤ ↑n / ↑k + b) {T : ℕ} (hT : b * (1 + 3 / ↑k) ^ T ≤ ↑n / ↑k) :
    (Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if run x l ∈ balancedSet n j b T then 0 else 1) ≤ ↑T * (1 / ↑n ^ 2)

    One color stays small. If color j starts with at most n/k + b nodes, b ≥ k √(n log n) and b (1 + 3/k)^T ≤ n/k, then after T rounds it has more than n/k + b (1 + 3/k)^T nodes with probability at most T/n².

    theorem Plurality.theorem_4_2 {n k : ℕ} (hn : 1 ≤ n) (hk : 3 ≤ k) (x : Config n k) {b : ℝ} (hb0 : ↑k * √(↑n * Real.log ↑n) ≤ b) (hx : ∀ (j : Fin k), ↑(count x j) ≤ ↑n / ↑k + b) {T : ℕ} (hT : b * (1 + 3 / ↑k) ^ T ≤ ↑n / ↑k) :
    (Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if Monochromatic (run x l) then 1 else 0) ≤ ↑k * ↑T / ↑n ^ 2

    Theorem 4.2 (lower bound for 3-majority). Let k ≥ 3 and suppose every color starts with at most n/k + b nodes, where b ≥ k √(n log n). If b (1 + 3/k)^T ≤ n/k, then the coloring after T rounds is monochromatic with probability at most k T / n².

    theorem Plurality.theorem_4_2_log {n k : ℕ} (hn : 1 ≤ n) (hk : 3 ≤ k) (x : Config n k) {b : ℝ} (hb0 : ↑k * √(↑n * Real.log ↑n) ≤ b) (hbpos : 0 < b) (hx : ∀ (j : Fin k), ↑(count x j) ≤ ↑n / ↑k + b) {T : ℕ} (hT : ↑T ≤ ↑k / 3 * Real.log (↑n / (↑k * b))) :
    (Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if Monochromatic (run x l) then 1 else 0) ≤ ↑k * ↑T / ↑n ^ 2

    Theorem 4.2, logarithmic form. Under the hypotheses of theorem_4_2, the coloring is still not monochromatic after T ≤ (k/3) log (n / (k b)) rounds, except with probability k T / n². With b = max ((n/k)^{1-ε}, k √(n log n)) and k ≤ n^{1/4-δ}, this is Ω(k log n) rounds.