simple_graph_cycle_power_dyadic_class_model_tight_weights
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
- simple_graph_cycle_power_clique_arcFor n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the…
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- simple_graph_cycle_power_dyadic_cover_tight_long_edgesIn an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge…
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- simple_graph_cycle_power_dyadic_class_model_vertex_layersFor an optimal (m+1)-layer dyadic cover, with ell(p) the unique layer covering the endpoint pair (p, p+2^m-1) and the class of p cut to…
- simple_graph_cycle_power_dyadic_class_model_exact_dyadicFor every j < m and every integer vertex v there is exactly one offset a < 2^j such that the rooted class at a from v is active at both a…
- cycle_power_dyadic_periodic_model_tight_of_countsFor a positive exponent m, nonzero natural period n, and periodic Boolean profiles indexed by the integers, exact dyadic edge-owner sums…
- Used by 1
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
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.
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)$.
uses
simple_graph_cycle_power_dyadic_cover_tight_long_edgesclassical 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
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)$.
uses
Int.cast_add,Int.cast_natCast,ZMod.natCast_self,add_zerohave 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 : ℤ))
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.
uses
Int.cast_add,Int.cast_natCast,ZMod.natCast_self,add_zerolet 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]
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.
uses
simple_graph_cycle_power_dyadic_class_model_vertex_layershave hxc := simple_graph_cycle_power_dyadic_class_model_vertex_layers m n hm hn c hc hcov ell hellroot huniqFor 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.
uses
simple_graph_cycle_power_dyadic_class_model_exact_dyadichave hxe := simple_graph_cycle_power_dyadic_class_model_exact_dyadic m n hm hn c hc hcov ell hellroot huniqThe 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$.
uses
cycle_power_dyadic_periodic_model_tight_of_countsexact 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.
- The periodicity of $\ell$ and $x$ modulo $n$ relies on basic reduction in $\mathbb{Z}/n\mathbb{Z}$ via `simp`/`simpa`, using $n \equiv 0 \pmod n$.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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