AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_class_model_exact_dyadic

theoremverified

For every j < m and every integer vertex v there is exactly one offset a < 2^j such that the rooted class at a from v is active at both a and a+(2^m-2^j).

Statement

theorem simple_graph_cycle_power_dyadic_class_model_exact_dyadic
    (m n : ℕ) [NeZero n] (hm : 1 ≤ m)
    (hn : 3 * (2 ^ m - 1) + 1 ≤ n)
    (c : Fin (m + 1) → ZMod n → ZMod n)
    (hc : ∀ s u v, u ≠ v → c s u = c s v →
      (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)
    (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →
      ∃ s, c s u = c s v)
    (ell : ℤ → Fin (m + 1))
    (hellroot : ∀ p : ℤ,
      c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n))
    (helluniq : ∀ (p : ℤ) (s : Fin (m + 1)),
      c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p)
    (j : ℕ) (hj : j < m) (v : ℤ) :
    (Finset.range (2 ^ j)).sum (fun a =>
      (decide (a < 2 ^ m ∧
          c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) =
            c (ell (v - (a : ℤ))) ((v - (a : ℤ) : ℤ) : ZMod n)) &&
        decide (a + 2 ^ m - 2 ^ j < 2 ^ m ∧
          c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + ((a + 2 ^ m - 2 ^ j : ℕ) : ZMod n)) =
            c (ell (v - (a : ℤ))) ((v - (a : ℤ) : ℤ) : ZMod n))).toNat) = 1
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 2

The proof, explained

The theorem shows that for every scale j < m and integer vertex v, exactly one offset a < 2^j yields a rooted class active at both a and a + (2^m - 2^j). The proof first reformulates the summation as counting offsets satisfying this joint activity predicate for step distance d = 2^m - 2^j. Existence of an active offset a < 2^j is supplied by an ordinary covering lemma. Uniqueness follows because any active offset forces its color to cover the tight long edge between v and v + d, which has a unique monochromatic color, whereas distinct active offsets are known to have distinct colors.

  1. Define the scale parameters D = 2^m, R = 2^j, and d = D - R, and establish the bounds 0 < R < D and 1 ≤ d < D.

    We assume classical logic. Because j < m, the inequality R < D follows from strict monotonicity of powers of 2 (Nat.pow_lt_pow_right), and R > 0 holds since powers of 2 are strictly positive (Nat.two_pow_pos). These bounds imply 1 ≤ d < D for d = D - R by linear integer arithmetic.

    lines 27–34

    uses Nat.pow_lt_pow_right, Nat.two_pow_pos

      classical
      let D := 2^m
      let R := 2^j
      let d := D-R
      have hRD : R < D := Nat.pow_lt_pow_right (by decide) hj
      have hR : 0 < R := Nat.two_pow_pos j
      have hd : 1 ≤ d := by dsimp [d]; omega
      have hdD : d < 2^m := by change D-R < D; omega
  2. Define the joint activity predicate T(a) and rephrase the goal as ∑_{a < R} (T(a)).toNat = 1.

    We define x(p, a) to be the boolean test for whether the rooted class at p is active at offset a, and T(a) to test whether the class rooted at v - a is active at both a and a + d. Since a + 2^m - 2^j = a + d, the summation in the theorem simplifies to summing (T(a)).toNat over a ∈ Finset.range R.

    lines 35–41

      let x : ℤ → ℕ → Bool := fun p a => decide (a < D ∧
        c (ell p) ((p : ZMod n)+(a : ZMod n)) = c (ell p) (p : ZMod n))
      let T : ℕ → Bool := fun a => x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+d)
      have hnat (a : ℕ) : a+2^m-2^j = a+d := by dsimp [D, R, d]; omega
      change (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1
      simp_rw [hnat]
      change (range R).sum (fun a => (T a).toNat) = 1
  3. There exists an offset a < R such that T(a) = true.

    Applying simple_graph_cycle_power_dyadic_class_model_ordinary_cover to the distance d = D - R provides an offset a < D - d = R whose rooted class at v - a is active at both a and a + d. Unfolding T and simplifying with Bool.true_and shows T(a) = true.

    lines 42–45

    uses simple_graph_cycle_power_dyadic_class_model_ordinary_cover, Bool.true_and

      obtain ⟨a, ha, h0, h1⟩ := simple_graph_cycle_power_dyadic_class_model_ordinary_cover
        m n hm hn c hc hcov ell hellroot helluniq d hd hdD v
      have haR : a < R := by change a < D-(D-R) at ha; omega
      have hTa : T a = true := by simp only [T, x, D] at *; simp only [h0, h1, Bool.true_and]
  4. Any offset b with T(b) = true makes the pair (v, v + d) monochromatic under color ℓ(v - b).

    If T(b) = true, both activity conditions hold (Bool.and_eq_true_iff.mp, of_decide_eq_true). The first condition gives c_{ℓ(v - b)}((v - b) + b) = c_{ℓ(v - b)}(v - b), which simplifies to c_{ℓ(v - b)}(v) = c_{ℓ(v - b)}(v - b). The second gives c_{ℓ(v - b)}((v - b) + (b + d)) = c_{ℓ(v - b)}(v - b), simplifying to c_{ℓ(v - b)}(v + d) = c_{ℓ(v - b)}(v - b). By transitivity and symmetry, c_{ℓ(v - b)}(v) = c_{ℓ(v - b)}(v + d).

    lines 46–56

    uses Bool.and_eq_true_iff.mp, of_decide_eq_true

      have hcovering (b : ℕ) (hTb : T b = true) :
          c (ell (v-(b : ℤ))) (v : ZMod n) =
            c (ell (v-(b : ℤ))) ((v : ZMod n)+(d : ZMod n)) := by
        have hbits : x (v-(b : ℤ)) b = true ∧ x (v-(b : ℤ)) (b+d) = true := Bool.and_eq_true_iff.mp hTb
        have hb0 := (of_decide_eq_true hbits.1).2
        have hb1 := (of_decide_eq_true hbits.2).2
        have hv0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring
        have hv1 : ((v-(b : ℤ) : ℤ) : ZMod n)+((b+d : ℕ) : ZMod n) = (v : ZMod n)+(d : ZMod n) := by push_cast; ring
        rw [hv0] at hb0
        rw [hv1] at hb1
        exact hb0.trans hb1.symm
  5. There is a unique color s ∈ Fin (m + 1) such that c_s(v) = c_s(v + d).

    By simple_graph_cycle_power_dyadic_cover_tight_long_edges, tight long edges are covered by a unique color class. If j = 0, d = 2^m - 1 (using pow_zero), which matches the first clause of the lemma; if j > 0, then 1 ≤ j < m and the second clause applies.

    lines 57–62

    uses simple_graph_cycle_power_dyadic_cover_tight_long_edges, pow_zero

      have hu : ∃! s : Fin (m+1), c s (v : ZMod n) = c s ((v : ZMod n)+(d : ZMod n)) := by
        have hh := simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov
        by_cases hj0 : j=0
        · subst j
          simpa only [d, D, R, pow_zero] using hh.1 (v : ZMod n)
        · simpa only [d, D, R] using hh.2 j (by omega) hj (v : ZMod n)
  6. Any active offset b < R must equal a.

    If b < R and T(b) = true, both ℓ(v - b) and ℓ(v - a) make (v, v + d) monochromatic. The uniqueness of such a color implies ℓ(v - b) = ℓ(v - a). If b ≠ a, then since both offsets are strictly less than D and their classes are active at v, simple_graph_cycle_power_dyadic_class_model_disjoint_colours would force ℓ(v - b) ≠ ℓ(v - a), a contradiction. Hence b = a.

    lines 63–72

    uses Bool.and_eq_true_iff.mp, of_decide_eq_true, simple_graph_cycle_power_dyadic_class_model_disjoint_colours

      have huniq (b : ℕ) (hb : b < R) (hTb : T b = true) : b=a := by
        have he : ell (v-(b : ℤ)) = ell (v-(a : ℤ)) := hu.unique (hcovering b hTb) (hcovering a hTa)
        have hbitsb := (Bool.and_eq_true_iff.mp hTb).1
        have hbitsa := (Bool.and_eq_true_iff.mp hTa).1
        have hPb := (of_decide_eq_true hbitsb).2
        have hPa := (of_decide_eq_true hbitsa).2
        by_contra hne
        exact (simple_graph_cycle_power_dyadic_class_model_disjoint_colours
          m n hm hn c hc hcov ell hellroot helluniq v b a (by dsimp [D] at hRD; omega)
          (by dsimp [D] at hRD; omega) hne hPb hPa) he
  7. The sum over a < R evaluates to 1.

    Using sum_eq_single a, the sum over Finset.range R reduces to the single term at a. At a, T(a) = true contributes 1 (Bool.toNat_true). For every other b in Finset.range R (mem_range.mp), uniqueness implies T(b) = false (Bool.eq_false_iff.mpr), which contributes 0 (Bool.toNat_false). Lastly, a ∈ Finset.range R holds because a < R (mem_range.mpr).

    lines 73–79

    uses sum_eq_single, Bool.toNat_true, Bool.eq_false_iff.mpr, mem_range.mp, Bool.toNat_false, mem_range.mpr

      rw [sum_eq_single a]
      · simp only [hTa, Bool.toNat_true]
      · intro b hb hba
        have he : T b = false := Bool.eq_false_iff.mpr (fun hTb => hba (huniq b (mem_range.mp hb) hTb))
        simp only [he, Bool.toNat_false]
      · intro hnot
        exact (hnot (mem_range.mpr haR)).elim
Nat.pow_lt_pow_right
For base a > 1, m < n implies a^m < a^n
Nat.two_pow_pos
For any natural number w, 2^w > 0
simple_graph_cycle_power_dyadic_class_model_ordinary_cover
For any distance 1 ≤ d < 2^m, there exists an offset a < 2^m - d whose rooted class is active at both a and a + d
Bool.true_and
The boolean expression true && b evaluates to b
Bool.and_eq_true_iff.mp
If b₁ && b₂ = true, then both b₁ = true and b₂ = true
of_decide_eq_true
If decide P = true, then proposition P holds
simple_graph_cycle_power_dyadic_cover_tight_long_edges
Tight long edges of length 2^m - 1 or 2^m - 2^j (1 ≤ j < m) are covered by a unique color class s ∈ Fin (m + 1)
pow_zero
Any element raised to the power 0 equals 1
simple_graph_cycle_power_dyadic_class_model_disjoint_colours
Distinct active offsets a ≠ b < 2^m passing through v have distinct colors ℓ(v - a) ≠ ℓ(v - b)
sum_eq_single
A finite sum over a set where all terms except a evaluate to 0 equals the value at a
Bool.toNat_true
The numerical conversion of true is 1
Bool.eq_false_iff.mpr
A boolean not equal to true is false
mem_range.mp
Membership in Finset.range n implies being strictly less than n
Bool.toNat_false
The numerical conversion of false is 0
mem_range.mpr
Being strictly less than n implies membership in Finset.range n

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000/-- Exact dyadic coverage: for each j < m and each vertex, exactly one rooted class is active at both offsets a and a+(2^m-2^j). -/theorem simple_graph_cycle_power_dyadic_class_model_exact_dyadic    (m n : ℕ) [NeZero n] (hm : 1 ≤ m)    (hn : 3 * (2 ^ m - 1) + 1 ≤ n)    (c : Fin (m + 1) → ZMod n → ZMod n)    (hc : ∀ s u v, u ≠ v → c s u = c s v →      (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)    (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →      ∃ s, c s u = c s v)    (ell : ℤ → Fin (m + 1))    (hellroot : ∀ p : ℤ,      c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n))    (helluniq : ∀ (p : ℤ) (s : Fin (m + 1)),      c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p)    (j : ℕ) (hj : j < m) (v : ℤ) :    (Finset.range (2 ^ j)).sum (fun a =>      (decide (a < 2 ^ m ∧          c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) =            c (ell (v - (a : ℤ))) ((v - (a : ℤ) : ℤ) : ZMod n)) &&        decide (a + 2 ^ m - 2 ^ j < 2 ^ m ∧          c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + ((a + 2 ^ m - 2 ^ j : ℕ) : ZMod n)) =            c (ell (v - (a : ℤ))) ((v - (a : ℤ) : ℤ) : ZMod n))).toNat) = 1 := by  classical  let D := 2^m  let R := 2^j  let d := D-R  have hRD : R < D := Nat.pow_lt_pow_right (by decide) hj  have hR : 0 < R := Nat.two_pow_pos j  have hd : 1 ≤ d := by dsimp [d]; omega  have hdD : d < 2^m := by change D-R < D; omega  let x : ℤ → ℕ → Bool := fun p a => decide (a < D ∧    c (ell p) ((p : ZMod n)+(a : ZMod n)) = c (ell p) (p : ZMod n))  let T : ℕ → Bool := fun a => x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+d)  have hnat (a : ℕ) : a+2^m-2^j = a+d := by dsimp [D, R, d]; omega  change (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1  simp_rw [hnat]  change (range R).sum (fun a => (T a).toNat) = 1  obtain ⟨a, ha, h0, h1⟩ := simple_graph_cycle_power_dyadic_class_model_ordinary_cover    m n hm hn c hc hcov ell hellroot helluniq d hd hdD v  have haR : a < R := by change a < D-(D-R) at ha; omega  have hTa : T a = true := by simp only [T, x, D] at *; simp only [h0, h1, Bool.true_and]  have hcovering (b : ℕ) (hTb : T b = true) :      c (ell (v-(b : ℤ))) (v : ZMod n) =        c (ell (v-(b : ℤ))) ((v : ZMod n)+(d : ZMod n)) := by    have hbits : x (v-(b : ℤ)) b = true ∧ x (v-(b : ℤ)) (b+d) = true := Bool.and_eq_true_iff.mp hTb    have hb0 := (of_decide_eq_true hbits.1).2    have hb1 := (of_decide_eq_true hbits.2).2    have hv0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring    have hv1 : ((v-(b : ℤ) : ℤ) : ZMod n)+((b+d : ℕ) : ZMod n) = (v : ZMod n)+(d : ZMod n) := by push_cast; ring    rw [hv0] at hb0    rw [hv1] at hb1    exact hb0.trans hb1.symm  have hu : ∃! s : Fin (m+1), c s (v : ZMod n) = c s ((v : ZMod n)+(d : ZMod n)) := by    have hh := simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov    by_cases hj0 : j=0    · subst j      simpa only [d, D, R, pow_zero] using hh.1 (v : ZMod n)    · simpa only [d, D, R] using hh.2 j (by omega) hj (v : ZMod n)  have huniq (b : ℕ) (hb : b < R) (hTb : T b = true) : b=a := by    have he : ell (v-(b : ℤ)) = ell (v-(a : ℤ)) := hu.unique (hcovering b hTb) (hcovering a hTa)    have hbitsb := (Bool.and_eq_true_iff.mp hTb).1    have hbitsa := (Bool.and_eq_true_iff.mp hTa).1    have hPb := (of_decide_eq_true hbitsb).2    have hPa := (of_decide_eq_true hbitsa).2    by_contra hne    exact (simple_graph_cycle_power_dyadic_class_model_disjoint_colours      m n hm hn c hc hcov ell hellroot helluniq v b a (by dsimp [D] at hRD; omega)      (by dsimp [D] at hRD; omega) hne hPb hPa) he  rw [sum_eq_single a]  · simp only [hTa, Bool.toNat_true]  · intro b hb hba    have he : T b = false := Bool.eq_false_iff.mpr (fun hTb => hba (huniq b (mem_range.mp hb) hTb))    simp only [he, Bool.toNat_false]  · intro hnot    exact (hnot (mem_range.mpr haR)).elim
See it in the graphDiscuss this resultChallenge it