Documentation

Averaging.OpportunisticNonEphemeral

Non-ephemeral good nodes (Lemma 4.2): the probabilistic part #

theorem Averaging.Opportunistic.avg_fun_cutSum {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (F : ℝ → ℝ) :
(Dynamics.avg fun (σ : V → ℤˣ) => F (∑ v : V, cutVec V₁ v * signVec σ v)) = Dynamics.avg fun (σ : V → ℤˣ) => F (∑ v : V, signVec σ v)

The sum ⟨σ, χ⟩ has the law of a sum of independent uniform signs.

theorem Averaging.Opportunistic.IsClusteredRegular.avg_le_of_mul_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) {g : (V → ℤˣ) → ℝ} {a K : ℝ} (ha : 0 ≤ a) (hK : 0 ≤ K) (hg1 : ∀ (σ : V → ℤˣ), g σ ≤ 1) (hg : ∀ (σ : V → ℤˣ), g σ * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) ≤ a * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) + K ^ 2) :
Dynamics.avg g ≤ a + 1 / √(↑(Fintype.card V) + 1) + 2 * K * (1 + Real.log ↑(Fintype.card V))

Anti-concentration of ‖y⁽⁰⁾‖².

theorem Averaging.Opportunistic.IsClusteredRegular.avg_cross {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) :
(Dynamics.avg fun (e : G.Dart) => if IsCrossDart V₁ e then 1 else 0) = ↑b / ↑d

A uniformly random dart crosses the cut with probability b/d.

theorem Averaging.Opportunistic.IsClusteredRegular.avg_fst_mem {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (B : Finset V) :
(Dynamics.avg fun (e : G.Dart) => if e.toProd.1 ∈ B then 1 else 0) = ↑B.card / ↑(Fintype.card V)

The tail of a uniformly random dart lies in B with probability |B|/n.

theorem Averaging.Opportunistic.IsClusteredRegular.avg_snd_mem {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (B : Finset V) :
(Dynamics.avg fun (e : G.Dart) => if e.toProd.2 ∈ B then 1 else 0) = ↑B.card / ↑(Fintype.card V)

Arithmetic of the bound Yb #

theorem Averaging.Opportunistic.cutDevBound_le_small {N l2 l3 s z : ℝ} {T : ℕ} (hN : 16 ≤ N) (hl3 : 0 < l3) (hs : 0 ≤ s) (hz : 0 ≤ z) (hL0 : 0 ≤ ↑T * l2 / N) (hL : ↑T * l2 / N ≤ 1 / 8) (hr0 : 0 ≤ l2 / l3) (hr : l2 / l3 ≤ 1 / 8) :
cutDevBound N l2 l3 s z T ≤ 2 * (↑T * l2 / N) * s + l2 / l3 * z
theorem Averaging.Opportunistic.cutDevBound_le_start {N l2 l3 s z : ℝ} {T : ℕ} (hN : 16 ≤ N) (hl3 : 0 < l3) (hs : 0 ≤ s) (hz : 0 ≤ z) (hzN : z ≤ N) (hszN : s + z ≤ N) (hL0 : 0 ≤ ↑T * l2 / N) (hL : ↑T * l2 / N ≤ 1 / 8) (hr0 : 0 ≤ l2 / l3) (hr : l2 / l3 ≤ 1 / 8) :
cutDevBound N l2 l3 s z T ≤ 2 * (↑T * l2 / N) * s + 5 * (l2 / l3)

Expectation bounds for one choice of the initial signs #

theorem Averaging.Opportunistic.IsClusteredRegular.expList_cutDev_signVec_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) (σ : V → ℤˣ) (t₁ : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) :
(Dynamics.expList G.Dart t₁ fun (l : List G.Dart) => ↑(Fintype.card V) * (cutCoef V₁ (avgRun G (signVec σ) l) - cutCoef V₁ (signVec σ)) ^ 2) ≤ 2 * (↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V)) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) + 5 * (2 * ↑b / ↑d / lam3)

The cut coefficient moves little up to the start of the phase: E ‖y⁽ᵗ¹⁾ - y⁽⁰⁾‖² ≤ 2 L₁ ‖y⁽⁰⁾‖² + 5 λ₂/λ₃ with L₁ = λ₂ t₁/n.

theorem Averaging.Opportunistic.IsClusteredRegular.expList_restSq_signVec_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) (σ : V → ℤˣ) (t₁ : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) :
(Dynamics.expList G.Dart t₁ fun (l : List G.Dart) => restSq V₁ (avgRun G (signVec σ) l)) ≤ ↑(Fintype.card V) * (1 - lam3 / ↑(Fintype.card V)) ^ t₁ + 3 * (2 * ↑b / ↑d / lam3) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) + 10 * (2 * ↑b / ↑d / lam3) ^ 2

The rest component is small at the start of the phase: E ‖z⁽ᵗ¹⁾‖² ≤ n (1 - λ₃/n)^{t₁} + 3 r ‖y⁽⁰⁾‖² + 10 r² with r = λ₂/λ₃.

theorem Averaging.Opportunistic.IsClusteredRegular.expList_devVec_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) (x₁ : V → ℝ) (k : ℕ) (hL : ↑k * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) :
(Dynamics.expList G.Dart k fun (p : List G.Dart) => ∑ v : V, devVec V₁ x₁ (avgRun G x₁ p) v ^ 2) ≤ (5 / 2 * (↑k * (2 * ↑b / ↑d) / ↑(Fintype.card V)) + 2 * (2 * ↑b / ↑d / lam3)) * (↑(Fintype.card V) * cutCoef V₁ x₁ ^ 2) + 2 * restSq V₁ x₁

From an arbitrary state x₁ (the start of the phase): the deviation r after k more rounds satisfies E ‖r⁽ᵏ⁾‖² ≤ (2.5 L_k + 2 r) ‖y₁‖² + 2 ‖z₁‖², with L_k = λ₂ k/n.

The good event #

theorem Averaging.Opportunistic.card_badSet_mul_le {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (θ : ℝ) (x₁ x : V → ℝ) :
↑(badSet V₁ θ x₁ x).card * θ ≤ ∑ v : V, devVec V₁ x₁ x v ^ 2
theorem Averaging.Opportunistic.card_badSet_le {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (θ : ℝ) (x₁ x : V → ℝ) :
(badSet V₁ θ x₁ x).card ≤ Fintype.card V
theorem Averaging.Opportunistic.devVec_self {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (x₁ : V → ℝ) (v : V) :
devVec V₁ x₁ x₁ v = projRest V₁ x₁ v

At the reference state itself the deviation is the rest component.

theorem Averaging.Opportunistic.restSq_gt_of_card_badSet_gt {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} {θ ε : ℝ} (hθ : 0 ≤ θ) (hε : 0 ≤ ε) (x₁ : V → ℝ) (h : ε * ↑(Fintype.card V) < ↑(badSet V₁ θ x₁ x₁).card) :
ε * ↑(Fintype.card V) * θ < restSq V₁ x₁

Many bad nodes at the start force a large rest component: |B| > ε n gives ‖z₁‖² > ε n θ.

theorem Averaging.Opportunistic.avgRun_take_append {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} (x : V → ℝ) (l₁ l₂ : List G.Dart) {t : ℕ} (ht : l₁.length ≤ t) :
avgRun G x (List.take t (l₁ ++ l₂)) = avgRun G (avgRun G x l₁) (List.take (t - l₁.length) l₂)
noncomputable def Averaging.Opportunistic.thr {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (ε : ℝ) (x₀ : V → ℝ) :

The threshold θ = ε² ‖y⁽⁰⁾‖²/(4n) for the deviation.

Equations
Instances For
    def Averaging.Opportunistic.CutMoved {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (ε : ℝ) (x₀ x₁ : V → ℝ) :

    The cut coefficient has moved by the start of the phase: 4 n (β₁ - β₀)² > ε² ‖y⁽⁰⁾‖².

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      theorem Averaging.Opportunistic.card_good_ge {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x₀ : V → ℝ) {ε : ℝ} (l₁ l₂ : List G.Dart) (hF : 4 * ↑(Fintype.card V) * (cutCoef V₁ (avgRun G x₀ l₁) - cutCoef V₁ x₀) ^ 2 ≤ ε ^ 2 * (↑(Fintype.card V) * cutCoef V₁ x₀ ^ 2)) (hB : ↑(badSet V₁ (thr V₁ ε x₀) (avgRun G x₀ l₁) (avgRun G x₀ l₁)).card ≤ ε * ↑(Fintype.card V)) (hZ : ↑{k ∈ Finset.range l₂.length | IsBadRound V₁ (thr V₁ ε x₀) (avgRun G x₀ l₁) l₂ k}.card ≤ ε * ↑(Fintype.card V)) :
      (1 - 3 * ε) * ↑(Fintype.card V) ≤ ↑{v : V | ∀ (t : ℕ), l₁.length ≤ t → t ≤ l₁.length + l₂.length → (avgRun G x₀ (List.take t (l₁ ++ l₂)) v - (projOne x₀ v + projCut V₁ x₀ v)) ^ 2 ≤ ε ^ 2 / ↑(Fintype.card V) * ∑ w : V, projCut V₁ x₀ w ^ 2}.card

      Deterministic core of Lemma 4.2: if the cut coefficient has not moved much by the start of the phase (4 n (β₁ - β₀)² ≤ ε² ‖y⁽⁰⁾‖²), at most ε n nodes are bad at the start and at most ε n rounds of the phase are bad, then at least (1 - 3ε) n nodes are ε-good at every round of the phase.

      theorem Averaging.Opportunistic.IsClusteredRegular.avg_isBadStep_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (θ : ℝ) (x₁ y : V → ℝ) :
      (Dynamics.avg fun (e : G.Dart) => if IsBadStep V₁ θ x₁ y e then 1 else 0) ≤ ↑b / ↑d + 2 * (↑(badSet V₁ θ x₁ y).card / ↑(Fintype.card V))

      One bad round: P(bad) ≤ b/d + 2 |B|/n.

      theorem Averaging.Opportunistic.IsClusteredRegular.expList_good_ge {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (x₀ : V → ℝ) {ε : ℝ} (hε : 0 < ε) (t₁ M : ℕ) :
      ((1 - Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => if CutMoved V₁ ε x₀ (avgRun G x₀ l₁) then 1 else 0) - Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => if ε * ↑(Fintype.card V) < ↑(badSet V₁ (thr V₁ ε x₀) (avgRun G x₀ l₁) (avgRun G x₀ l₁)).card then 1 else 0) - 1 / (ε * ↑(Fintype.card V)) * ∑ k ∈ Finset.range M, (↑b / ↑d + 2 * Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => (if CutMoved V₁ ε x₀ (avgRun G x₀ l₁) then 0 else 1) * Dynamics.expList G.Dart k fun (p : List G.Dart) => ↑(badSet V₁ (thr V₁ ε x₀) (avgRun G x₀ l₁) (avgRun G (avgRun G x₀ l₁) p)).card / ↑(Fintype.card V)) ≤ Dynamics.expList G.Dart (t₁ + M) fun (l : List G.Dart) => if (1 - 3 * ε) * ↑(Fintype.card V) ≤ ↑{v : V | ∀ (t : ℕ), t₁ ≤ t → t ≤ t₁ + M → (avgRun G x₀ (List.take t l) v - (projOne x₀ v + projCut V₁ x₀ v)) ^ 2 ≤ ε ^ 2 / ↑(Fintype.card V) * ∑ w : V, projCut V₁ x₀ w ^ 2}.card then 1 else 0

      The good event, for fixed initial signs (proof of Lemma 4.2): the probability that at least (1 - 3ε) n nodes are ε-good throughout the phase [t₁, t₁ + M] is at least 1 - P(cut moved) - P(|B| > ε n) - (1/(ε n)) ∑_{k < M} (b/d + 2 E[1 - 1_moved; |B_k|/n]).

      Bounds for one choice of the initial signs, in the form used by anti-concentration #

      theorem Averaging.Opportunistic.IsClusteredRegular.cutMoved_bound {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) {ε : ℝ} (hε : 0 < ε) (σ : V → ℤˣ) (t₁ : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) :
      (Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => if CutMoved V₁ ε (signVec σ) (avgRun G (signVec σ) l₁) then 1 else 0) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) ≤ 8 * (↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V)) / ε ^ 2 * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) + 20 * (2 * ↑b / ↑d / lam3) / ε ^ 2

      The cut coefficient moves by the start of the phase with probability g₁ satisfying g₁ ‖y⁽⁰⁾‖² ≤ (8 L₁/ε²) ‖y⁽⁰⁾‖² + 20 r/ε².

      theorem Averaging.Opportunistic.IsClusteredRegular.manyBad_bound {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) {ε : ℝ} (hε : 0 < ε) (σ : V → ℤˣ) (t₁ : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) :
      (Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => if ε * ↑(Fintype.card V) < ↑(badSet V₁ (thr V₁ ε (signVec σ)) (avgRun G (signVec σ) l₁) (avgRun G (signVec σ) l₁)).card then 1 else 0) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) ≤ 12 * (2 * ↑b / ↑d / lam3) / ε ^ 3 * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) + 4 / ε ^ 3 * (↑(Fintype.card V) * (1 - lam3 / ↑(Fintype.card V)) ^ t₁ + 10 * (2 * ↑b / ↑d / lam3) ^ 2)

      Many bad nodes at the start: probability g₂ with g₂ ‖y⁽⁰⁾‖² ≤ (12 r/ε³) ‖y⁽⁰⁾‖² + (4/ε³)(n (1 - λ₃/n)^{t₁} + 10 r²).

      theorem Averaging.Opportunistic.IsClusteredRegular.badRound_bound {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) {ε : ℝ} (hε : 0 < ε) (hε1 : ε ≤ 1) (σ : V → ℤˣ) (t₁ k : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hLk : ↑k * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) :
      (Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => (if CutMoved V₁ ε (signVec σ) (avgRun G (signVec σ) l₁) then 0 else 1) * Dynamics.expList G.Dart k fun (p : List G.Dart) => ↑(badSet V₁ (thr V₁ ε (signVec σ)) (avgRun G (signVec σ) l₁) (avgRun G (avgRun G (signVec σ) l₁) p)).card / ↑(Fintype.card V)) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) ≤ 4 / ε ^ 2 * (25 / 4 * (↑k * (2 * ↑b / ↑d) / ↑(Fintype.card V)) + 11 * (2 * ↑b / ↑d / lam3)) * (↑(Fintype.card V) * cutCoef V₁ (signVec σ) ^ 2) + 8 / ε ^ 2 * (↑(Fintype.card V) * (1 - lam3 / ↑(Fintype.card V)) ^ t₁ + 10 * (2 * ↑b / ↑d / lam3) ^ 2)

      Bad rounds in the phase: g₃ ‖y⁽⁰⁾‖² ≤ (4/ε²)(6.25 L_k + 11 r) ‖y⁽⁰⁾‖² + (8/ε²)(n (1 - λ₃/n)^{t₁} + 10 r²), where g₃ is the expected fraction of bad nodes after t₁ + k rounds, on the event that the cut coefficient has not moved.

      Lemma 4.2 #

      theorem Averaging.Opportunistic.card_mul_pow_le_six {N l3 : ℝ} {T : ℕ} (hN : 0 < N) (hl3 : 0 < l3) (hq : 0 ≤ 1 - l3 / N) (hT : 6 * N / l3 * Real.log N ≤ ↑T) :
      N * (1 - l3 / N) ^ T ≤ 1 / N ^ 5

      n (1 - λ₃/n)ᵗ ≤ 1/n⁵ once λ₃ t/n ≥ 6 log n.

      theorem Averaging.Opportunistic.one_div_sqrt_le {N δ : ℝ} (hN : 0 ≤ N) (hδ : 0 < δ) (h : 1 ≤ δ ^ 2 * (N + 1)) :
      1 / √(N + 1) ≤ δ

      The final arithmetic of Lemma 4.2 #

      theorem Averaging.Opportunistic.arith_T1 {LN ε r L : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hL : L ≤ 7 * (r * LN)) (hrLN : 10 ^ 6 * (r * LN) ≤ 2 * ε ^ 4) :
      8 * L / ε ^ 2 ≤ ε / 100
      theorem Averaging.Opportunistic.arith_T2 {N LN ε u : ℝ} (hn : 0 < N) (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hLN1 : 1 ≤ LN) (hNε : 5 * 10 ^ 5 * LN ^ 2 ≤ N * ε ^ 4) (hu : u = 1 / √(N + 1)) :
      u ≤ ε / 100
      theorem Averaging.Opportunistic.arith_T3 {LN ε : ℝ} (hε0 : 0 < ε) (hLN1 : 1 ≤ LN) :
      2 * (ε / (100 * LN)) * (1 + LN) ≤ ε / 25
      theorem Averaging.Opportunistic.arith_T4 {LN ε r : ℝ} (hε0 : 0 < ε) (hLN1 : 1 ≤ LN) (hr0 : 0 ≤ r) (hrLN : 10 ^ 6 * (r * LN) ≤ 2 * ε ^ 4) :
      12 * r / ε ^ 3 ≤ ε / 100
      theorem Averaging.Opportunistic.arith_wLN {N LN ε w : ℝ} (hn : 0 < N) (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hLN1 : 1 ≤ LN) (hNbig : 5 * 10 ^ 5 ≤ N) (hNε : 5 * 10 ^ 5 * LN ^ 2 ≤ N * ε ^ 4) (hw : w * N ^ 2 = 1) :
      800 * (w * LN) ≤ ε ^ 3
      theorem Averaging.Opportunistic.arith_T5 {LN ε r w : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hLN1 : 1 ≤ LN) (hw0 : 0 ≤ w) (hr0 : 0 ≤ r) (hwLN : 800 * (w * LN) ≤ ε ^ 3) (hrLN : 10 ^ 6 * (r * LN) ≤ 2 * ε ^ 4) :
      2 * (2 * (w + 4 * r) / ε ^ 2) * (1 + LN) ≤ ε / 50
      theorem Averaging.Opportunistic.arith_T6 {LN l3 ε r : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hl3 : 0 < l3) {l2 : ℝ} (hr : r = l2 / l3) (hrLN : 10 ^ 6 * (r * LN) ≤ 2 * ε ^ 4) :
      6 * LN / (l3 * ε) * (l2 / 2) ≤ ε / 100
      theorem Averaging.Opportunistic.arith_T7 {LN l3 ε r : ℝ} (hε0 : 0 < ε) (hl3 : 0 < l3) (hLN1 : 1 ≤ LN) (hr0 : 0 ≤ r) (hrLN2 : 10 ^ 6 * (r * LN ^ 2) ≤ l3 * ε ^ 4) :
      6 * LN / (l3 * ε) * (2 * (4 / ε ^ 2 * (25 / 4 * (6 * (r * LN)) + 11 * r))) ≤ ε / 100
      theorem Averaging.Opportunistic.arith_T8 {N LN l3 ε u : ℝ} (hn : 0 < N) (hε0 : 0 < ε) (hl3 : 0 < l3) (hLN1 : 1 ≤ LN) (hC : 2 * 10 ^ 6 * LN ^ 2 ≤ N * l3 ^ 2 * ε ^ 4) (hu : u = 1 / √(N + 1)) :
      6 * LN / (l3 * ε) * (2 * u) ≤ ε / 20
      theorem Averaging.Opportunistic.arith_T9 {N LN l3 ε r w : ℝ} (hn : 0 < N) (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hl3 : 0 < l3) (hl3le : l3 ≤ 2) (hLN1 : 1 ≤ LN) (hw0 : 0 ≤ w) (hr0 : 0 ≤ r) (hw : w * N ^ 2 = 1) (hNbig : 5 * 10 ^ 5 ≤ N) (hC : 2 * 10 ^ 6 * LN ^ 2 ≤ N * l3 ^ 2 * ε ^ 4) (hrLN2 : 10 ^ 6 * (r * LN ^ 2) ≤ l3 * ε ^ 4) :
      6 * LN / (l3 * ε) * (2 * (2 * (3 * (w + 4 * r) / ε) * (1 + LN))) ≤ ε / 20
      theorem Averaging.Opportunistic.arith_K1 {LN ε r l3 : ℝ} (hε0 : 0 < ε) (hl3le : l3 ≤ 2) (hLN1 : 1 ≤ LN) (hcr : r * (10 ^ 6 * LN ^ 2) ≤ l3 * ε ^ 4) :
      20 * r / ε ^ 2 ≤ (ε / (100 * LN)) ^ 2
      theorem Averaging.Opportunistic.arith_K23 {ε r w Q : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hw0 : 0 ≤ w) (hr0 : 0 ≤ r) (hQ0 : 0 ≤ Q) (hQ : Q ≤ w ^ 2) :
      4 / ε ^ 3 * (Q + 10 * r ^ 2) ≤ (2 * (w + 4 * r) / ε ^ 2) ^ 2 ∧ 8 / ε ^ 2 * (Q + 10 * r ^ 2) ≤ (3 * (w + 4 * r) / ε) ^ 2
      theorem Averaging.Opportunistic.lemma42_arith {N LN l2 l3 ε u : ℝ} {t₁ M : ℕ} (hn : 0 < N) (hLN1 : 1 ≤ LN) (hl3 : 0 < l3) (hl3le : l3 ≤ 2) (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hl2 : 0 ≤ l2) (hcr : l2 / l3 * (10 ^ 6 * LN ^ 2) ≤ l3 * ε ^ 4) (hC : 2 * 10 ^ 6 * LN ^ 2 ≤ N * l3 ^ 2 * ε ^ 4) (hL1 : ↑t₁ * l2 / N ≤ 7 * (l2 / l3 * LN)) (hM : ↑M ≤ 6 * N / l3 * LN) (hu : u = 1 / √(N + 1)) :
      8 * (↑t₁ * l2 / N) / ε ^ 2 + u + 2 * (ε / (100 * LN)) * (1 + LN) + (12 * (l2 / l3) / ε ^ 3 + u + 2 * (2 * (1 / N ^ 2 + 4 * (l2 / l3)) / ε ^ 2) * (1 + LN)) + 1 / (ε * N) * (↑M * (l2 / 2 + 2 * (4 / ε ^ 2 * (25 / 4 * (6 * (l2 / l3 * LN)) + 11 * (l2 / l3)) + u + 2 * (3 * (1 / N ^ 2 + 4 * (l2 / l3)) / ε) * (1 + LN)))) ≤ ε

      The final arithmetic of Lemma 4.2 (c = 10⁶).

      Averaging over the initial signs #

      theorem Averaging.Opportunistic.IsClusteredRegular.expList_indicator_le_one {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (P : List G.Dart → Prop) [DecidablePred P] (T : ℕ) :
      (Dynamics.expList G.Dart T fun (l : List G.Dart) => if P l then 1 else 0) ≤ 1
      theorem Averaging.Opportunistic.IsClusteredRegular.avg_cutMoved_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) {ε : ℝ} (hε : 0 < ε) (t₁ : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) {K : ℝ} (hK : 0 ≤ K) (hKsq : 20 * (2 * ↑b / ↑d / lam3) / ε ^ 2 ≤ K ^ 2) :
      (Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => if CutMoved V₁ ε (signVec σ) (avgRun G (signVec σ) l₁) then 1 else 0) ≤ 8 * (↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V)) / ε ^ 2 + 1 / √(↑(Fintype.card V) + 1) + 2 * K * (1 + Real.log ↑(Fintype.card V))
      theorem Averaging.Opportunistic.IsClusteredRegular.avg_manyBad_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) {ε : ℝ} (hε : 0 < ε) (t₁ : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) {K : ℝ} (hK : 0 ≤ K) (hKsq : 4 / ε ^ 3 * (↑(Fintype.card V) * (1 - lam3 / ↑(Fintype.card V)) ^ t₁ + 10 * (2 * ↑b / ↑d / lam3) ^ 2) ≤ K ^ 2) :
      (Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => if ε * ↑(Fintype.card V) < ↑(badSet V₁ (thr V₁ ε (signVec σ)) (avgRun G (signVec σ) l₁) (avgRun G (signVec σ) l₁)).card then 1 else 0) ≤ 12 * (2 * ↑b / ↑d / lam3) / ε ^ 3 + 1 / √(↑(Fintype.card V) + 1) + 2 * K * (1 + Real.log ↑(Fintype.card V))
      theorem Averaging.Opportunistic.IsClusteredRegular.avg_badRound_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) (hl3 : 0 < lam3) (hN : 16 ≤ ↑(Fintype.card V)) {ε : ℝ} (hε : 0 < ε) (hε1 : ε ≤ 1) (t₁ k : ℕ) (hL : ↑t₁ * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hLk : ↑k * (2 * ↑b / ↑d) / ↑(Fintype.card V) ≤ 1 / 8) (hr : 2 * ↑b / ↑d / lam3 ≤ 1 / 8) {K A : ℝ} (hK : 0 ≤ K) (hA : 4 / ε ^ 2 * (25 / 4 * (↑k * (2 * ↑b / ↑d) / ↑(Fintype.card V)) + 11 * (2 * ↑b / ↑d / lam3)) ≤ A) (hKsq : 8 / ε ^ 2 * (↑(Fintype.card V) * (1 - lam3 / ↑(Fintype.card V)) ^ t₁ + 10 * (2 * ↑b / ↑d / lam3) ^ 2) ≤ K ^ 2) :
      (Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart t₁ fun (l₁ : List G.Dart) => (if CutMoved V₁ ε (signVec σ) (avgRun G (signVec σ) l₁) then 0 else 1) * Dynamics.expList G.Dart k fun (p : List G.Dart) => ↑(badSet V₁ (thr V₁ ε (signVec σ)) (avgRun G (signVec σ) l₁) (avgRun G (avgRun G (signVec σ) l₁) p)).card / ↑(Fintype.card V)) ≤ A + 1 / √(↑(Fintype.card V) + 1) + 2 * K * (1 + Real.log ↑(Fintype.card V))
      theorem Averaging.Opportunistic.IsClusteredRegular.nonEphemeral_aux {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} {lam3 : ℝ} (hG : IsClusteredRegular G V₁ d b) (h3 : ThirdEigenvalueLB G V₁ d lam3) {ε : ℝ} (hε0 : 0 < ε) (hε1 : ε ≤ 1) (hl3 : 0 < lam3) (hc : 2 * ↑b / ↑d / lam3 ≤ lam3 * ε ^ 4 / (10 ^ 6 * Real.log ↑(Fintype.card V) ^ 2)) (t₁ M : ℕ) (ht1 : 6 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) ≤ ↑t₁) (ht1' : ↑t₁ ≤ 6 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V) + 1) (hM : ↑t₁ + ↑M ≤ 12 * ↑(Fintype.card V) / lam3 * Real.log ↑(Fintype.card V)) :
      1 - ε ≤ Dynamics.avg fun (σ : V → ℤˣ) => Dynamics.expList G.Dart (t₁ + M) fun (l : List G.Dart) => if (1 - 3 * ε) * ↑(Fintype.card V) ≤ ↑{v : V | ∀ (t : ℕ), t₁ ≤ t → t ≤ t₁ + M → (avgRun G (signVec σ) (List.take t l) v - (projOne (signVec σ) v + projCut V₁ (signVec σ) v)) ^ 2 ≤ ε ^ 2 / ↑(Fintype.card V) * ∑ w : V, projCut V₁ (signVec σ) w ^ 2}.card then 1 else 0

      Lemma 4.2 with the constant c = 10⁶, for a phase [t₁, t₁ + M] with 6 (n/λ₃) log n ≤ t₁ ≤ 6 (n/λ₃) log n + 1 and t₁ + M ≤ 12 (n/λ₃) log n: with probability at least 1 - ε, at least (1 - 3ε) n nodes are ε-good at every round of the phase.