AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_class_model_disjoint_colours

theoremverified

Two active rooted classes at a common vertex with distinct offsets have distinct layer colours.

Statement

theorem simple_graph_cycle_power_dyadic_class_model_disjoint_colours
    (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)
    (v : ℤ) (a b : ℕ) (ha : a < 2 ^ m) (hb : b < 2 ^ m) (hab : a ≠ b)
    (hxa : c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) =
      c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n)))
    (hxb : c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n) + (b : ZMod n)) =
      c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n))) :
    ell (v - (a : ℤ)) ≠ ell (v - (b : ℤ))
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 3

The proof, explained

We argue by contradiction, assuming that two active rooted classes at vertex v with distinct offsets a ≠ b < 2^m share a layer colour s. Under this common colour, the active class assumptions imply that c s (v - a) = c s v = c s (v - b), while both v - a and v - b satisfy the root periodicity condition of step size 2^m - 1. Uniqueness of fibre endpoints in dyadic covers then forces v - a = v - b in ℤ/nℤ. Canceling v yields a ≡ b [MOD n], which forces a = b because both offsets are strictly less than n, contradicting a ≠ b.

  1. Under the assumption that ℓ(v - a) = ℓ(v - b), the vertices v - a and v - b have the same colour as v in this shared layer.

    We argue by contradiction and assume that ℓ(v - a) = ℓ(v - b) =: s (hypothesis `he`). In ℤ/nℤ, the offsets satisfy (v - a) + a = v and (v - b) + b = v (proved as `ha0` and `hb0` by pushing casts and ring normalization). Rewriting with these identities into the hypotheses `hxa` and `hxb`, and substituting ℓ(v - b) = s, gives c s v = c s (v - a) and c s v = c s (v - b).

    lines 25–29

      intro he
      have ha0 : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring
      have hb0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring
      rw [ha0] at hxa
      rw [hb0, ← he] at hxb
  2. The vertices v - a and v - b coincide in ℤ/nℤ.

    By the root condition `hellroot`, both v - a and v - b are endpoints of monochromatic intervals of length 2^m - 1 in layer s: c s (v - a) = c s ((v - a) + (2^m - 1)) and c s (v - b) = c s ((v - b) + (2^m - 1)). Since they also satisfy c s (v - a) = c s (v - b) via their common colour at v, the uniqueness theorem `simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique` applies, concluding that v - a = v - b in ℤ/nℤ.

    lines 30–36

    uses simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique

      have hpa := (hellroot (v-(a : ℤ))).symm
      have hpb := (hellroot (v-(b : ℤ))).symm
      rw [← he] at hpb
      have hroot := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn
        (c (ell (v-(a : ℤ)))) (hc (ell (v-(a : ℤ))))
        ((v-(a : ℤ) : ℤ) : ZMod n) ((v-(b : ℤ) : ℤ) : ZMod n)
        hpa hpb (hxa.symm.trans hxb)
  3. The offsets a and b are equal, contradicting a ≠ b.

    Simplifying integer and natural casts transforms v - a = v - b into v - a = v - b in ℤ/nℤ (`Int.cast_sub`, `Int.cast_natCast`). Canceling v on the left via `sub_right_inj.mp` gives a = b in ℤ/nℤ, which is equivalent to a ≡ b [MOD n] (`ZMod.natCast_eq_natCast_iff`). Because 1 ≤ m, a < 2^m, b < 2^m, and 3 * (2^m - 1) + 1 ≤ n, linear arithmetic shows both a < n and b < n. Thus a ≡ b [MOD n] implies a = b (`Nat.ModEq.eq_of_lt_of_lt`), which contradicts the assumption hab (a ≠ b).

    lines 37–41

    uses Int.cast_sub, Int.cast_natCast, sub_right_inj.mp, Nat.ModEq.eq_of_lt_of_lt, ZMod.natCast_eq_natCast_iff

      simp only [Int.cast_sub, Int.cast_natCast] at hroot
      have hcast : (a : ZMod n) = (b : ZMod n) := sub_right_inj.mp hroot
      have hnat : a=b := Nat.ModEq.eq_of_lt_of_lt
        ((ZMod.natCast_eq_natCast_iff _ _ n).mp hcast) (by omega) (by omega)
      exact hab hnat
Int.cast_natCast
Casting a natural number into a ring directly or via the integers yields the same element: ↑(↑n : ℤ) = ↑n.
Int.cast_sub
Casting an integer difference into a ring preserves subtraction: ↑(m - n) = ↑m - ↑n.
Nat.ModEq.eq_of_lt_of_lt
If two natural numbers are congruent modulo m and both are strictly less than m, then they are equal.
simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique
In the cycle power graph on ℤ/nℤ with n ≥ 3(2^m - 1) + 1, if every monochromatic pair under a colouring c is adjacent, and two points p and q each have the same colour as their shift by 2^m - 1, then c p = c q implies p = q.
sub_right_inj.mp
In an additive group, if x - y = x - z, then y = z.
ZMod.natCast_eq_natCast_iff
Two natural numbers cast to the same element in ℤ/cℤ if and only if they 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/-- At a common vertex, two distinct active rooted classes of an optimal dyadic cover never share a layer colour. -/theorem simple_graph_cycle_power_dyadic_class_model_disjoint_colours    (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)    (v : ℤ) (a b : ℕ) (ha : a < 2 ^ m) (hb : b < 2 ^ m) (hab : a ≠ b)    (hxa : c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) =      c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n)))    (hxb : c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n) + (b : ZMod n)) =      c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n))) :    ell (v - (a : ℤ)) ≠ ell (v - (b : ℤ)) := by  intro he  have ha0 : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring  have hb0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring  rw [ha0] at hxa  rw [hb0, ← he] at hxb  have hpa := (hellroot (v-(a : ℤ))).symm  have hpb := (hellroot (v-(b : ℤ))).symm  rw [← he] at hpb  have hroot := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn    (c (ell (v-(a : ℤ)))) (hc (ell (v-(a : ℤ))))    ((v-(a : ℤ) : ℤ) : ZMod n) ((v-(b : ℤ) : ℤ) : ZMod n)    hpa hpb (hxa.symm.trans hxb)  simp only [Int.cast_sub, Int.cast_natCast] at hroot  have hcast : (a : ZMod n) = (b : ZMod n) := sub_right_inj.mp hroot  have hnat : a=b := Nat.ModEq.eq_of_lt_of_lt    ((ZMod.natCast_eq_natCast_iff _ _ n).mp hcast) (by omega) (by omega)  exact hab hnat
See it in the graphDiscuss this resultChallenge it