simple_graph_cycle_power_dyadic_cover_class_model
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
- 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…
- 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_adj_iff_of_bandwidth_ltWhen k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of…
- 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…
- 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…
- simple_graph_cycle_power_dyadic_cover_class_spanningEvery label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class…
- simple_graph_cycle_power_dyadic_layer_weight_leIn any clique labelling of a cycle power with dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, the total layer…
- cycle_power_dyadic_int_weight_le_cardFor a finite integer set of diameter at most 2^m-1, weight its endpoint-distance pairs by two and its other dyadic long-distance pairs by…
- zmod_intCast_eq_intCast_iff_of_abs_sub_ltTwo integers a, b with |a − b| < n are equal modulo n only if they are equal.
- simple_graph_cycle_power_dyadic_cover_fibre_endpoint_uniqueIn 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.
- simple_graph_cycle_power_dyadic_cover_layer_root_uniqueIn an optimal (m+1)-layer cover of C_n^{2^m-1}, for each layer s and each vertex v, there is a unique offset a ≤ 2^m-1 such that v-a is…
- simple_graph_cycle_power_dyadic_cover_edge_spanIf a monochromatic clique contains v and v+d with 1 ≤ d < 2^m, its root v-a (with a ≤ 2^m-1) satisfies a < 2^m - d, so the entire edge {v,…
- zmod_sum_sub_eq_sumSummation of any natural function over ZMod n is invariant under subtraction by a constant residue.
- cycle_power_dyadic_class_weight_eq_of_sum_eqIf the total sum of dyadic class weights over all residues equals the total sum of active counts, then pointwise equality holds for every…
- simple_graph_cycle_power_dyadic_class_model_disjoint_coloursTwo active rooted classes at a common vertex with distinct offsets have distinct layer colours.
- 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…
- simple_graph_cycle_power_dyadic_class_model_ordinary_coverFor every distance 1 ≤ d < 2^m and every integer vertex v there is a rooted offset a < 2^m - d whose class is active at both v-a and v-a+d.
- simple_graph_cycle_power_dyadic_class_model_tight_weightsEvery rooted dyadic class of an optimal cover is tight: the dyadic class weight of the arc equals its cardinality.
- simple_graph_cycle_power_dyadic_class_model_layer_choiceThere is a periodic integer layer map ell assigning to each integer p the unique layer covering the endpoint pair (p, p+2^m-1), with…
- Used by 1
- simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shapeUnder the numerical hypotheses of OP-205, the equivalence covering number is m+2 PROVIDED that every tight, exactly dyadically covered,…
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.
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.
uses
simple_graph_cycle_power_dyadic_class_model_layer_choiceclassical 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))
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).
uses
Int.cast_add,Int.cast_natCast,ZMod.natCast_self,add_zerohave 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]
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.
uses
Nat.two_pow_pos,decide_eq_truehave 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⟩
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).
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_coverhave 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
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.
refine ⟨x, ell, hxp, hper, hends, htw, hct, hex, hcv, ?_, ?_⟩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).
uses
of_decide_eq_true· intro p a ha exact (of_decide_eq_true ha).2
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).
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
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 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