AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique

theoremverified

In any clique labeling of the cycle power C_n^{2^m-1} with n ≥ 3(2^m-1)+1, each clique contains at most one pair at distance 2^m-1.

Statement

theorem simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique
    (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)
    (p q : ZMod n)
    (hp : c p = c (p + ((2 ^ m - 1 : ℕ) : ZMod n)))
    (hq : c q = c (q + ((2 ^ m - 1 : ℕ) : ZMod n)))
    (hpq : c p = c q) : p = q
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 5

The proof, explained

In a clique labeling of the cycle power C_n^k with k = 2^m - 1 and n ≥ 3k + 1, any clique containing a pair at distance k is shown to have at most one such pair. By a known rooted-arc lemma, any clique containing {p, p + k} is entirely confined to the forward arc [p, p + k]. Consequently, if another pair {q, q + k} shares the same clique, both vertices must lie on this arc, giving q = p + a and q + k = p + b with 0 ≤ a, b ≤ k. Cancelling p yields a + k ≡ b (mod n), which lifts to an equality a + k = b in ℕ because 2k < n. Since b ≤ k, this forces a = 0 and thus p = q.

  1. Both q and q + (2^m - 1) lie on the forward arc of length 2^m - 1 starting at p.

    Because c(p) = c(p + (2^m - 1)) and n ≥ 3(2^m - 1) + 1, the lemma simple_graph_cycle_power_rooted_clique_arc ensures that any vertex in the clique of p has the form p + x for some natural number x ≤ 2^m - 1. Since c(q) = c(p) and c(q + (2^m - 1)) = c(q) = c(p), this yields natural numbers a, b ≤ 2^m - 1 such that q = p + a and q + (2^m - 1) = p + b in ℤ/nℤ.

    lines 14–16

    uses simple_graph_cycle_power_rooted_clique_arc

      have harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc p hp
      obtain ⟨a, ha, hqa⟩ := harc q hpq.symm
      obtain ⟨b, hb, hqb⟩ := harc (q+((2^m-1 : ℕ) : ZMod n)) (hq.symm.trans hpq.symm)
  2. In ℤ/nℤ, the residue of a + (2^m - 1) equals the residue of b.

    Expanding p + (a + (2^m - 1)) in ℤ/nℤ gives (p + a) + (2^m - 1) = q + (2^m - 1) = p + b. Cancelling p from the left using add_left_cancel yields the equality a + (2^m - 1) = b in ℤ/nℤ.

    lines 17–22

    uses add_left_cancel

      have he : ((a+(2^m-1) : ℕ) : ZMod n) = (b : ZMod n) := by
        apply add_left_cancel (a := p)
        calc
          p+((a+(2^m-1) : ℕ) : ZMod n) = (p+(a : ZMod n))+((2^m-1 : ℕ) : ZMod n) := by push_cast; ring
          _ = q+((2^m-1 : ℕ) : ZMod n) := by rw [← hqa]
          _ = p+(b : ZMod n) := hqb
  3. The equality a + (2^m - 1) = b holds in the natural numbers ℕ.

    By ZMod.natCast_eq_natCast_iff, equality in ℤ/nℤ means a + (2^m - 1) ≡ b (mod n). Since a, b ≤ 2^m - 1 and n ≥ 3(2^m - 1) + 1, both a + (2^m - 1) ≤ 2(2^m - 1) < n and b < n are strictly less than n. By Nat.ModEq.eq_of_lt_of_lt, two natural numbers strictly less than n that are congruent modulo n must be equal in ℕ.

    lines 23–24

    uses Nat.ModEq.eq_of_lt_of_lt, ZMod.natCast_eq_natCast_iff

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

    Since a + (2^m - 1) = b and b ≤ 2^m - 1 for natural numbers a and b, linear arithmetic forces a ≤ 0, so a = 0. This deduction is closed by omega.

    line 25

      have ha0 : a=0 := by omega
  5. p = q.

    Substituting a = 0 into q = p + a simplifies via Nat.cast_zero and add_zero to q = p, which symmetrically gives p = q.

    lines 26–27

    uses Nat.cast_zero, add_zero

      have : q=p := by simpa only [ha0, Nat.cast_zero, add_zero] using hqa
      exact this.symm
simple_graph_cycle_power_rooted_clique_arc
In a clique coloring of the cycle power C_n^k with n ≥ 3k + 1, if c(p) = c(p + k), then every vertex u in the same clique (c(u) = c(p)) lies on the forward arc from p, meaning u = p + a for some natural number a ≤ k.
add_left_cancel
In an algebraic structure with left-cancellative addition, a + b = a + c implies b = c.
Nat.ModEq.eq_of_lt_of_lt
If two natural numbers a and b are congruent modulo m, and both are strictly less than m, then a = b.
ZMod.natCast_eq_natCast_iff
The natural casts of a and b into ℤ/cℤ are equal if and only if a ≡ b (mod c).
Nat.cast_zero
The cast of the natural number 0 into an additive monoid with one equals 0.
add_zero
Adding zero on the right leaves an element unchanged: a + 0 = a.

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/-- In any clique labeling of the cycle power C_n^{2^m-1} with n ≥ 3(2^m-1)+1, each clique contains at most one pair at distance 2^m-1. -/theorem simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique    (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)    (p q : ZMod n)    (hp : c p = c (p + ((2 ^ m - 1 : ℕ) : ZMod n)))    (hq : c q = c (q + ((2 ^ m - 1 : ℕ) : ZMod n)))    (hpq : c p = c q) : p = q := by  have harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc p hp  obtain ⟨a, ha, hqa⟩ := harc q hpq.symm  obtain ⟨b, hb, hqb⟩ := harc (q+((2^m-1 : ℕ) : ZMod n)) (hq.symm.trans hpq.symm)  have he : ((a+(2^m-1) : ℕ) : ZMod n) = (b : ZMod n) := by    apply add_left_cancel (a := p)    calc      p+((a+(2^m-1) : ℕ) : ZMod n) = (p+(a : ZMod n))+((2^m-1 : ℕ) : ZMod n) := by push_cast; ring      _ = q+((2^m-1 : ℕ) : ZMod n) := by rw [← hqa]      _ = p+(b : ZMod n) := hqb  have hen : a+(2^m-1)=b := Nat.ModEq.eq_of_lt_of_lt    ((ZMod.natCast_eq_natCast_iff _ _ n).mp he) (by omega) (by omega)  have ha0 : a=0 := by omega  have : q=p := by simpa only [ha0, Nat.cast_zero, add_zero] using hqa  exact this.symm
See it in the graphDiscuss this resultChallenge it