AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_cover_class_model

theoremverified

Every optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and real layer colours, tight class weights, constant active counts, exact dyadic coverage, all ordinary coverage, and disjoint active classes of the same colour.

Statement

theorem simple_graph_cycle_power_dyadic_cover_class_model
    (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) :
    ∃ (x : ℤ → ℕ → Bool) (ell : ℤ → Fin (m + 1)),
      (∀ p a, x (p + (n : ℤ)) a = x p a) ∧
      (∀ p, ell (p + (n : ℤ)) = ell p) ∧
      (∀ p, x p 0 = true ∧ x p (2 ^ m - 1) = true) ∧
      (∀ p, cycle_power_dyadic_class_weight m (x p) =
        (Finset.range (2 ^ m)).sum (fun a => (x p a).toNat)) ∧
      (∀ v : ℤ, (Finset.range (2 ^ m)).sum
        (fun a => (x (v - (a : ℤ)) a).toNat) = m + 1) ∧
      (∀ j < m, ∀ v : ℤ, (Finset.range (2 ^ j)).sum (fun a =>
        (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1) ∧
      (∀ d : ℕ, 1 ≤ d → d < 2 ^ m → ∀ v : ℤ,
        ∃ a : ℕ, a < 2 ^ m - d ∧ x (v - (a : ℤ)) a = true ∧
          x (v - (a : ℤ)) (a + d) = true) ∧
      (∀ p a, x p a = true →
        c (ell p) ((p : ZMod n) + (a : ZMod n)) = c (ell p) (p : ZMod n)) ∧
      (∀ (v : ℤ) (a b : ℕ), a < 2 ^ m → b < 2 ^ m → a ≠ b →
        x (v - (a : ℤ)) a = true → x (v - (b : ℤ)) b = true →
        ell (v - (a : ℤ)) ≠ ell (v - (b : ℤ)))
Source
Uniform actual-cover to class-model bridge for OP-205 / RT-1, following arXiv:2610.15635. This packages the proved geometric and weight-saturation lemmas; it does not prove rigidity, pruning counts or the main conjecture. No research advance claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 20
Used by 1

The proof, explained

The theorem constructs a periodic integer class model (x, ℓ) from an optimal dyadic equivalence cover of a cycle power. It first uses simple_graph_cycle_power_dyadic_class_model_layer_choice to select the unique layer ℓ(p) connecting each root p to p + 2^m - 1, and defines x(p, a) as the boolean indicator that a < 2^m and p + a shares the color of p in layer ℓ(p). Periodicity and endpoint activity follow by direct calculation, while tight weights, constant vertex degrees, exact dyadic coverage, and ordinary coverage are imported from dedicated structural lemmas. Faithfulness follows from the definition of x, and disjointness of layer colors for overlapping classes is resolved by simple_graph_cycle_power_dyadic_class_model_disjoint_colours.

  1. Choose the layer selection map ℓ and define the class membership indicator x.

    Using classical logic, invoke simple_graph_cycle_power_dyadic_class_model_layer_choice to obtain an n-periodic layer map ℓ : ℤ → Fin (m + 1) such that for each p ∈ ℤ, layer ℓ(p) is the unique layer joining p to p + 2^m - 1 in the equivalence cover c. Then define x(p, a) : Bool to be true if and only if a < 2^m and p + a has the same color as p in layer ℓ(p) modulo n.

    lines 31–34

    uses simple_graph_cycle_power_dyadic_class_model_layer_choice

      classical
      obtain ⟨ell, hper, hroot, huniq⟩ := simple_graph_cycle_power_dyadic_class_model_layer_choice m n hm hn c hc hcov
      let x : ℤ → ℕ → Bool := fun p a => decide (a < 2^m ∧
        c (ell p) ((p : ZMod n)+(a : ZMod n)) = c (ell p) (p : ZMod n))
  2. The indicator function x is n-periodic in the root coordinate p.

    Expanding the definition of x, the layer map ℓ is n-periodic by hypothesis hper, and shifting p by n in ℤ/nℤ leaves the element unchanged because n maps to 0 in ℤ/nℤ (via Int.cast_add, Int.cast_natCast, ZMod.natCast_self, and add_zero).

    lines 35–36

    uses Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero

      have hxp (p : ℤ) (a : ℕ) : x (p+(n : ℤ)) a = x p a := by
        simp only [x, hper, Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero]
  3. Both endpoints a = 0 and a = 2^m - 1 are active for every root p.

    For a = 0, 0 < 2^m holds because 2^m > 0 (Nat.two_pow_pos), and p + 0 = p identically. For a = 2^m - 1, 2^m - 1 < 2^m by arithmetic using Nat.two_pow_pos, and c(ℓ(p))(p + 2^m - 1) = c(ℓ(p))(p) holds by construction of ℓ (hroot); decide_eq_true turns this true conjunction into a boolean true.

    lines 37–41

    uses Nat.two_pow_pos, decide_eq_true

      have hends (p : ℤ) : x p 0 = true ∧ x p (2^m-1) = true := by
        constructor
        · simp [x, Nat.two_pow_pos]
        · apply decide_eq_true
          exact ⟨by have := Nat.two_pow_pos m; omega, hroot p⟩
  4. The model satisfies tight class weights, constant active vertex counts, exact dyadic coverage, and ordinary distance coverage.

    These four structural properties are established by calling four modular theorems that analyze the interaction of the layer choice ℓ with the equivalence cover c: simple_graph_cycle_power_dyadic_class_model_tight_weights (tight class weights), simple_graph_cycle_power_dyadic_class_model_vertex_layers (active count is m + 1 at every vertex), simple_graph_cycle_power_dyadic_class_model_exact_dyadic (exact dyadic pair coverage), and simple_graph_cycle_power_dyadic_class_model_ordinary_cover (every distance in [1, 2^m) is covered).

    lines 42–45

    uses simple_graph_cycle_power_dyadic_class_model_tight_weights, simple_graph_cycle_power_dyadic_class_model_vertex_layers, simple_graph_cycle_power_dyadic_class_model_exact_dyadic, simple_graph_cycle_power_dyadic_class_model_ordinary_cover

      have htw := simple_graph_cycle_power_dyadic_class_model_tight_weights m n hm hn c hc hcov ell hroot
      have hct := simple_graph_cycle_power_dyadic_class_model_vertex_layers m n hm hn c hc hcov ell hroot huniq
      have hex := simple_graph_cycle_power_dyadic_class_model_exact_dyadic m n hm hn c hc hcov ell hroot huniq
      have hcv := simple_graph_cycle_power_dyadic_class_model_ordinary_cover m n hm hn c hc hcov ell hroot huniq
  5. Provide (x, ℓ) as the witness and instantiate the first seven properties of the model.

    The refine tactic supplies the witness pair (x, ℓ) and satisfies the first seven conjuncts of the existential goal using the facts established above, leaving faithfulness and disjointness of layer colors as the remaining two obligations.

    line 46

      refine ⟨x, ell, hxp, hper, hends, htw, hct, hex, hcv, ?_, ?_⟩
  6. The model is faithful: every active offset shares the layer color of the root.

    If x(p, a) = true, the definition of x implies that the underlying conjunction holds via of_decide_eq_true, whose second component is the desired color equality c(ℓ(p))(p + a) = c(ℓ(p))(p).

    lines 47–48

    uses of_decide_eq_true

      · intro p a ha
        exact (of_decide_eq_true ha).2
  7. Distinct active classes containing the same vertex receive different layer colors.

    Given two distinct active offsets a ≠ b < 2^m with x(v - a, a) = true and x(v - b, b) = true, of_decide_eq_true extracts the equality of colors between v - a and v, and between v - b and v. The modular theorem simple_graph_cycle_power_dyadic_class_model_disjoint_colours then guarantees that ℓ(v - a) ≠ ℓ(v - b).

    lines 49–51

    uses of_decide_eq_true, simple_graph_cycle_power_dyadic_class_model_disjoint_colours

      · intro v a b ha hb hab hxa hxb
        exact simple_graph_cycle_power_dyadic_class_model_disjoint_colours m n hm hn c hc hcov ell hroot huniq
          v a b ha hb hab (of_decide_eq_true hxa).2 (of_decide_eq_true hxb).2
simple_graph_cycle_power_dyadic_class_model_layer_choice
There exists an n-periodic layer choice function ℓ : ℤ → Fin(m+1) such that for each p, layer ℓ(p) connects p to p + 2^m - 1, and ℓ(p) is the unique such layer.
Int.cast_add
The canonical cast from ℤ to an additive group with one preserves addition: ↑(m + n) = ↑m + ↑n.
Int.cast_natCast
Casting a natural number to ℤ and then to a ring agrees with casting it directly to the ring: ↑(↑n) = ↑n.
ZMod.natCast_self
The natural number n maps to 0 when cast into ℤ/nℤ.
add_zero
Adding zero to any element leaves it unchanged: a + 0 = a.
Nat.two_pow_pos
For any natural number w, 2^w > 0.
decide_eq_true
If a decidable proposition p is true, then decide p = true.
simple_graph_cycle_power_dyadic_class_model_tight_weights
Under the layer choice ℓ, the dyadic class weight of each class equals the sum of its active indicators over range 2^m.
simple_graph_cycle_power_dyadic_class_model_vertex_layers
Under the layer choice ℓ, for every vertex v ∈ ℤ, the sum of active indicators of classes containing v is exactly m + 1.
simple_graph_cycle_power_dyadic_class_model_exact_dyadic
Under the layer choice ℓ, for every dyadic scale j < m and vertex v ∈ ℤ, exactly one active class contains both v and v + 2^m - 2^j.
simple_graph_cycle_power_dyadic_class_model_ordinary_cover
Under the layer choice ℓ, for every distance 1 ≤ d < 2^m and vertex v ∈ ℤ, there is an active class containing both v and v + d.
of_decide_eq_true
If decide p = true, then the proposition p holds.
simple_graph_cycle_power_dyadic_class_model_disjoint_colours
Under the layer choice ℓ, if two distinct active classes v - a and v - b (with a, b < 2^m and a ≠ b) both contain vertex v, then their assigned layers ℓ(v - a) and ℓ(v - b) are distinct.

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 4000theorem simple_graph_cycle_power_dyadic_cover_class_model    (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) :    ∃ (x : ℤ → ℕ → Bool) (ell : ℤ → Fin (m + 1)),      (∀ p a, x (p + (n : ℤ)) a = x p a) ∧      (∀ p, ell (p + (n : ℤ)) = ell p) ∧      (∀ p, x p 0 = true ∧ x p (2 ^ m - 1) = true) ∧      (∀ p, cycle_power_dyadic_class_weight m (x p) =        (Finset.range (2 ^ m)).sum (fun a => (x p a).toNat)) ∧      (∀ v : ℤ, (Finset.range (2 ^ m)).sum        (fun a => (x (v - (a : ℤ)) a).toNat) = m + 1) ∧      (∀ j < m, ∀ v : ℤ, (Finset.range (2 ^ j)).sum (fun a =>        (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1) ∧      (∀ d : ℕ, 1 ≤ d → d < 2 ^ m → ∀ v : ℤ,        ∃ a : ℕ, a < 2 ^ m - d ∧ x (v - (a : ℤ)) a = true ∧          x (v - (a : ℤ)) (a + d) = true) ∧      (∀ p a, x p a = true →        c (ell p) ((p : ZMod n) + (a : ZMod n)) = c (ell p) (p : ZMod n)) ∧      (∀ (v : ℤ) (a b : ℕ), a < 2 ^ m → b < 2 ^ m → a ≠ b →        x (v - (a : ℤ)) a = true → x (v - (b : ℤ)) b = true →        ell (v - (a : ℤ)) ≠ ell (v - (b : ℤ))) := by  classical  obtain ⟨ell, hper, hroot, huniq⟩ := simple_graph_cycle_power_dyadic_class_model_layer_choice m n hm hn c hc hcov  let x : ℤ → ℕ → Bool := fun p a => decide (a < 2^m ∧    c (ell p) ((p : ZMod n)+(a : ZMod n)) = c (ell p) (p : ZMod n))  have hxp (p : ℤ) (a : ℕ) : x (p+(n : ℤ)) a = x p a := by    simp only [x, hper, Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero]  have hends (p : ℤ) : x p 0 = true ∧ x p (2^m-1) = true := by    constructor    · simp [x, Nat.two_pow_pos]    · apply decide_eq_true      exact ⟨by have := Nat.two_pow_pos m; omega, hroot p⟩  have htw := simple_graph_cycle_power_dyadic_class_model_tight_weights m n hm hn c hc hcov ell hroot  have hct := simple_graph_cycle_power_dyadic_class_model_vertex_layers m n hm hn c hc hcov ell hroot huniq  have hex := simple_graph_cycle_power_dyadic_class_model_exact_dyadic m n hm hn c hc hcov ell hroot huniq  have hcv := simple_graph_cycle_power_dyadic_class_model_ordinary_cover m n hm hn c hc hcov ell hroot huniq  refine ⟨x, ell, hxp, hper, hends, htw, hct, hex, hcv, ?_, ?_⟩  · intro p a ha    exact (of_decide_eq_true ha).2  · intro v a b ha hb hab hxa hxb    exact simple_graph_cycle_power_dyadic_class_model_disjoint_colours m n hm hn c hc hcov ell hroot huniq      v a b ha hb hab (of_decide_eq_true hxa).2 (of_decide_eq_true hxb).2
See it in the graphDiscuss this resultChallenge it