AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_class_model_tight_weights

theoremverified

Every rooted dyadic class of an optimal cover is tight: the dyadic class weight of the arc equals its cardinality.

Statement

theorem simple_graph_cycle_power_dyadic_class_model_tight_weights
    (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))
    (p : ℤ) :
    cycle_power_dyadic_class_weight m
        (fun a => decide (a < 2 ^ m ∧
          c (ell p) ((p : ZMod n) + (a : ZMod n)) = c (ell p) (p : ZMod n)))
      = (Finset.range (2 ^ m)).sum (fun a =>
          (decide (a < 2 ^ m ∧
            c (ell p) ((p : ZMod n) + (a : ZMod n)) = c (ell p) (p : ZMod n))).toNat)
Source
step towards simple_graph_cycle_power_dyadic_cover_class_model
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 1

The proof, explained

The proof reduces the tightness of dyadic class weights to a general combinatorial transfer theorem for periodic binary models (`cycle_power_dyadic_periodic_model_tight_of_counts`). First, the uniqueness of the covering relation for maximum-length chords implies that the relation assignment $\ell$ and the resulting indicator model $x$ are $n$-periodic. Next, two structural properties of optimal covers—that each vertex belongs to exactly $m + 1$ dyadic class intervals and that dyadic chords at each scale have an exact coverage count of $1$—verify the hypotheses of the transfer theorem, establishing that the weight of the rooted dyadic class at $p$ equals its cardinality.

  1. The relation $\ell(q)$ is the unique relation among the $m+1$ relations that covers the chord of length $2^m - 1$ at $q$.

    By `simple_graph_cycle_power_dyadic_cover_tight_long_edges`, every edge of maximum distance $2^m - 1$ in $C_n^{2^m - 1}$ is covered by a unique relation $s \in \{0, \dots, m\}$. By hypothesis (`hellroot`), $\ell(q)$ is chosen to cover the chord from $q$ to $q + (2^m - 1)$; hence, any relation $s$ identifying these endpoints must equal $\ell(q)$.

    lines 24–28

    uses simple_graph_cycle_power_dyadic_cover_tight_long_edges

      classical
      have ht := (simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov).1
      have huniq (q : ℤ) (s : Fin (m+1))
          (hs : c s ((q : ZMod n)+((2^m-1 : ℕ) : ZMod n)) = c s (q : ZMod n)) : s=ell q :=
        (ht (q : ZMod n)).unique hs.symm (hellroot q).symm
  2. The choice of covering relation $\ell$ is $n$-periodic: $\ell(q + n) = \ell(q)$ for all $q \in \mathbb{Z}$.

    Since $q + n \equiv q \pmod n$ in $\mathbb{Z}/n\mathbb{Z}$, the hypothesis `hellroot` evaluated at $q + n$ shows that $\ell(q + n)$ identifies $q$ and $q + (2^m - 1)$. By the uniqueness established in the previous step, $\ell(q + n)$ must equal $\ell(q)$.

    lines 29–31

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

      have hper (q : ℤ) : ell (q+(n : ℤ)) = ell q := by
        apply huniq q
        simpa only [Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero] using hellroot (q+(n : ℤ))
  3. The binary indicator model $x(q, a)$ is $n$-periodic in the root coordinate: $x(q + n, a) = x(q, a)$ for all $q \in \mathbb{Z}$ and $a \in \mathbb{N}$.

    We define $x(q, a)$ as the boolean condition $a < 2^m \land c(\ell(q), q + a) = c(\ell(q), q)$. Shifting the root $q$ by $n$ leaves $\ell(q)$ invariant by the periodicity established above, and shifts vertex indices in $\mathbb{Z}/n\mathbb{Z}$ by $n = 0$, leaving $x(q, a)$ unchanged.

    lines 32–35

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

      let x : ℤ → ℕ → Bool := fun q a => decide (a < 2^m ∧
        c (ell q) ((q : ZMod n)+(a : ZMod n)) = c (ell q) (q : ZMod n))
      have hxp (q : ℤ) (a : ℕ) : x (q+(n : ℤ)) a = x q a := by
        simp only [x, hper, Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero]
  4. Every vertex $v \in \mathbb{Z}$ belongs to exactly $m + 1$ dyadic class intervals: $\sum_{a=0}^{2^m - 1} x(v - a, a) = m + 1$.

    This is the vertex layer count property provided by `simple_graph_cycle_power_dyadic_class_model_vertex_layers`, applying the uniqueness of the covering relation for long chords.

    line 36

    uses simple_graph_cycle_power_dyadic_class_model_vertex_layers

      have hxc := simple_graph_cycle_power_dyadic_class_model_vertex_layers m n hm hn c hc hcov ell hellroot huniq
  5. For each scale $j < m$, the shifted dyadic chords of length $2^m - 2^j$ are uniquely covered: $\sum_{a=0}^{2^j - 1} x(v - a, a) \cdot x(v - a, a + 2^m - 2^j) = 1$ for all $v \in \mathbb{Z}$.

    This is the exact dyadic count property provided by `simple_graph_cycle_power_dyadic_class_model_exact_dyadic`, using the uniqueness of relation covers for intermediate chord lengths.

    line 37

    uses simple_graph_cycle_power_dyadic_class_model_exact_dyadic

      have hxe := simple_graph_cycle_power_dyadic_class_model_exact_dyadic m n hm hn c hc hcov ell hellroot huniq
  6. The dyadic class weight of the arc rooted at $p$ equals its cardinality.

    We invoke `cycle_power_dyadic_periodic_model_tight_of_counts`, which guarantees that any $n$-periodic binary model $x$ satisfying the total vertex layer count condition ($m + 1$) and the exact dyadic chord count condition ($1$ at each scale $j < m$) has tight dyadic class weight at every root $p$.

    line 38

    uses cycle_power_dyadic_periodic_model_tight_of_counts

      exact cycle_power_dyadic_periodic_model_tight_of_counts m n hm x hxp hxc hxe p
Int.cast_add
The canonical homomorphism from $\mathbb{Z}$ to an additive group with one distributes over addition: $\uparrow(m + n) = \uparrow m + \uparrow n$.
Int.cast_natCast
Casting a natural number through $\mathbb{Z}$ to a ring matches casting it directly: $\uparrow(\uparrow n) = \uparrow n$.
ZMod.natCast_self
In the modular ring $\mathbb{Z}/n\mathbb{Z}$, the modulus $n$ casts to zero: $(n : \mathbb{Z}/n\mathbb{Z}) = 0$.
add_zero
Adding zero to an element leaves it unchanged: $a + 0 = a$.
simple_graph_cycle_power_dyadic_cover_tight_long_edges
In any cover of the cycle power graph $C_n^{2^m-1}$ by $m+1$ relations, every chord of maximum length $2^m-1$ is covered by a unique relation, and every chord of length $2^m-2^j$ ($1 \le j < m$) is covered by a unique relation.
simple_graph_cycle_power_dyadic_class_model_vertex_layers
For any vertex $v$, the sum of indicators of dyadic class intervals ending at or containing $v$ across all offsets $a < 2^m$ equals $m + 1$.
simple_graph_cycle_power_dyadic_class_model_exact_dyadic
For each scale $j < m$ and vertex $v$, exactly one offset $a < 2^j$ has both $v$ and $v + 2^m - 2^j$ belonging to the dyadic class rooted at $v - a$.
cycle_power_dyadic_periodic_model_tight_of_counts
If a periodic binary model $x : \mathbb{Z} \to \mathbb{N} \to \text{Bool}$ satisfies the vertex layer count condition ($m+1$ at every vertex) and the exact dyadic count condition ($1$ for every scale $j < m$), then at every root $p$, the dyadic class weight of $x(p)$ equals the sum of its indicators.

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/-- Tight class weights: the dyadic class weight of an active arc equals its cardinality. -/theorem simple_graph_cycle_power_dyadic_class_model_tight_weights    (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))    (p : ℤ) :    cycle_power_dyadic_class_weight m        (fun a => decide (a < 2 ^ m ∧          c (ell p) ((p : ZMod n) + (a : ZMod n)) = c (ell p) (p : ZMod n)))      = (Finset.range (2 ^ m)).sum (fun a =>          (decide (a < 2 ^ m ∧            c (ell p) ((p : ZMod n) + (a : ZMod n)) = c (ell p) (p : ZMod n))).toNat) := by  classical  have ht := (simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov).1  have huniq (q : ℤ) (s : Fin (m+1))      (hs : c s ((q : ZMod n)+((2^m-1 : ℕ) : ZMod n)) = c s (q : ZMod n)) : s=ell q :=    (ht (q : ZMod n)).unique hs.symm (hellroot q).symm  have hper (q : ℤ) : ell (q+(n : ℤ)) = ell q := by    apply huniq q    simpa only [Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero] using hellroot (q+(n : ℤ))  let x : ℤ → ℕ → Bool := fun q a => decide (a < 2^m ∧    c (ell q) ((q : ZMod n)+(a : ZMod n)) = c (ell q) (q : ZMod n))  have hxp (q : ℤ) (a : ℕ) : x (q+(n : ℤ)) a = x q a := by    simp only [x, hper, Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero]  have hxc := simple_graph_cycle_power_dyadic_class_model_vertex_layers m n hm hn c hc hcov ell hellroot huniq  have hxe := simple_graph_cycle_power_dyadic_class_model_exact_dyadic m n hm hn c hc hcov ell hellroot huniq  exact cycle_power_dyadic_periodic_model_tight_of_counts m n hm x hxp hxc hxe p
See it in the graphDiscuss this resultChallenge it