AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_cover_edge_span

theoremverified

If a monochromatic clique contains v and v+d with 1 ≤ d < 2^m, its root v-a (with a ≤ 2^m-1) satisfies a < 2^m - d, so the entire edge {v, v+d} is contained in the span of v-a.

Statement

theorem simple_graph_cycle_power_dyadic_cover_edge_span
    (m n : ℕ) [NeZero n] (hn : 3 * (2 ^ m - 1) + 1 ≤ n)
    (c : ZMod n → ZMod n)
    (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)
    (v : ZMod n) (d : ℕ) (hd1 : 1 ≤ d) (hd2 : d < 2 ^ m)
    (hcd : c v = c (v + (d : ZMod n)))
    (a : ℕ) (ha : a ≤ 2 ^ m - 1)
    (hroot : c (v - (a : ZMod n)) = c v)
    (hend : c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n))) :
    a < 2 ^ m - d ∧ c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((a + d : ℕ) : ZMod n))
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 3

The proof, explained

The rooted monochromatic clique starting at v - a extends along the cycle to an arc of length 2^m - 1. Because v + d shares the clique's color, it lies on this arc at position (v - a) + b for some b ≤ 2^m - 1. Since n ≥ 3(2^m - 1) + 1 is large enough, the congruence (v - a) + (a + d) = (v - a) + b in ℤ/nℤ lifts to an exact integer equality a + d = b, which immediately yields a < 2^m - d. The color of (v - a) + (a + d) matches that of v - a because both equal c(v).

  1. The vertex v + d lies on the arc of length 2^m - 1 starting at v - a, so v + d = (v - a) + b for some natural number b ≤ 2^m - 1.

    By `simple_graph_cycle_power_rooted_clique_arc` applied to the root v - a, every vertex with color c(v - a) must be of the form (v - a) + b with b ≤ 2^m - 1. Since c(v + d) = c(v) = c(v - a) by transitivity, v + d has this color, yielding a witness b ≤ 2^m - 1 such that v + d = (v - a) + b.

    lines 16–18

    uses simple_graph_cycle_power_rooted_clique_arc

      have harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc
        (v-(a : ZMod n)) hend
      obtain ⟨b, hb, hvb⟩ := harc (v+(d : ZMod n)) (hcd.symm.trans hroot.symm)
  2. a + d = b in ℤ/nℤ.

    In ℤ/nℤ, (v - a) + (a + d) simplifies to v + d, which equals (v - a) + b. Cancelling v - a from both sides with `add_left_cancel` yields a + d = b in ℤ/nℤ.

    lines 19–23

    uses add_left_cancel

      have he : ((a+d : ℕ) : ZMod n) = (b : ZMod n) := by
        apply add_left_cancel (a := v-(a : ZMod n))
        calc
          (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring
          _ = (v-(a : ZMod n))+(b : ZMod n) := hvb
  3. a + d = b as natural numbers.

    By `ZMod.natCast_eq_natCast_iff`, equality in ℤ/nℤ is equivalent to congruence modulo n. Since a ≤ 2^m - 1 and d < 2^m, and b ≤ 2^m - 1, both a + d and b are strictly less than n (using the hypothesis 3(2^m - 1) + 1 ≤ n, verified by `omega`). Hence `Nat.ModEq.eq_of_lt_of_lt` establishes exact equality a + d = b in ℕ.

    lines 24–25

    uses Nat.ModEq.eq_of_lt_of_lt, ZMod.natCast_eq_natCast_iff

      have hen : a+d=b := Nat.ModEq.eq_of_lt_of_lt
        ((ZMod.natCast_eq_natCast_iff _ _ n).mp he) (by omega) (by omega)
  4. a < 2^m - d. automation

    Linear arithmetic (`omega`) deduces a < 2^m - d from a + d = b and b ≤ 2^m - 1, establishing the first conjunct.

    line 26

      refine ⟨by omega, ?_⟩
  5. c(v - a) = c((v - a) + (a + d)).

    Because (v - a) + (a + d) = v + d in ℤ/nℤ, the required equality reduces to c(v - a) = c(v + d), which follows directly from the hypotheses c(v - a) = c(v) and c(v) = c(v + d) by transitivity.

    lines 27–29

      have hv : (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring
      rw [hv]
      exact hroot.trans hcd
simple_graph_cycle_power_rooted_clique_arc
In an edge coloring of the cycle power graph where monochromatic pairs are adjacent, if a vertex p shares its color with p + k, then every vertex with that color lies on the arc of length k starting at p.
add_left_cancel
In an additive structure with left cancellation, a + b = a + c implies b = c.
Nat.ModEq.eq_of_lt_of_lt
Two natural numbers that are congruent modulo m and both strictly less than m are equal.
ZMod.natCast_eq_natCast_iff
The images of two natural numbers in ℤ/cℤ are equal if and only if the numbers are congruent modulo c.

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/-- If a monochromatic clique contains v and v+d with 1 ≤ d < 2^m, its root v-a (with a ≤ 2^m-1) satisfies a < 2^m - d, so the entire edge {v, v+d} is contained in the span of v-a. -/theorem simple_graph_cycle_power_dyadic_cover_edge_span    (m n : ℕ) [NeZero n] (hn : 3 * (2 ^ m - 1) + 1 ≤ n)    (c : ZMod n → ZMod n)    (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)    (v : ZMod n) (d : ℕ) (hd1 : 1 ≤ d) (hd2 : d < 2 ^ m)    (hcd : c v = c (v + (d : ZMod n)))    (a : ℕ) (ha : a ≤ 2 ^ m - 1)    (hroot : c (v - (a : ZMod n)) = c v)    (hend : c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n))) :    a < 2 ^ m - d ∧ c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((a + d : ℕ) : ZMod n)) := by  have harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc    (v-(a : ZMod n)) hend  obtain ⟨b, hb, hvb⟩ := harc (v+(d : ZMod n)) (hcd.symm.trans hroot.symm)  have he : ((a+d : ℕ) : ZMod n) = (b : ZMod n) := by    apply add_left_cancel (a := v-(a : ZMod n))    calc      (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring      _ = (v-(a : ZMod n))+(b : ZMod n) := hvb  have hen : a+d=b := Nat.ModEq.eq_of_lt_of_lt    ((ZMod.natCast_eq_natCast_iff _ _ n).mp he) (by omega) (by omega)  refine ⟨by omega, ?_⟩  have hv : (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring  rw [hv]  exact hroot.trans hcd
See it in the graphDiscuss this resultChallenge it