simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape
Under the numerical hypotheses of OP-205, the equivalence covering number is m+2 PROVIDED that every tight, exactly dyadically covered, fully ordinarily covered integer Boolean model at exponent m with exactly m+1 active classes at each vertex has no selected island. This structural implication is an explicit additional hypothesis; the theorem does not prove it or settle OP-205.
Statement
theorem simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape (k m n : ℕ) (hm : 1 ≤ m) (hkm : k+1 = 2^m) (hn : max (2*k+2) (k^2*(k+2)) ≤ n) (hev : Even n) (hnd : ¬(k+1) ∣ n) (hshape : ∀ (x : ℤ → ℕ → Bool), (∀ p, cycle_power_dyadic_class_weight m (x p) = (Finset.range (2^m)).sum (fun a => (x p a).toNat)) → (∀ 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) → (∀ v : ℤ, (Finset.range (2^m)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = m+1) → ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m → x p a = false → x p b = true → x p c = true) : simple_graph_equivalence_covering_number (simple_graph_cycle_power n k) = m+2
- Source
- Uniform formal assembly for OP-205 / RT-1 following arXiv:2610.15635 Proposition3.2. The explicit upper covers formalize a published construction. The final reduction keeps the still-unproved pure class-shape theorem as an EXPLICIT additional hypothesis. No unconditional graph covering result or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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…
- 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_has_equivalence_cover_monoIf G is covered by s equivalence subgraphs, it is covered by any larger number t of them (pad with the edgeless equivalence subgraph).
- simple_graph_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- 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.
- cycle_power_dyadic_model_dvd_of_no_islandA periodic optimally counted tight dyadic class model with proper class labels, exact dyadic edges and full ordinary coverage has period…
- simple_graph_has_equivalence_cover_cycle_power_dyadic_upperFor natural k at least one with k+1 equal to2 to the power m and n at least max(2k+2,twice the square of k), the k-th cycle power on n…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - simple_graph_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 3
- simple_graph_equivalence_covering_number_cycle_power_fifteen_of_not_dvdFor every even n ≥ 3825 = 15²·17 not divisible by 16, the equivalence covering number of the 15th power of the n-cycle is 6 = 2 + ⌈log₂…
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_endpointConditional reduction of OP-205 to alternation and endpoint-only classes: if for every m ≥ 5 every tight, exactly dyadically covered,…
- simple_graph_equivalence_covering_number_cycle_power_two_pow_even_not_dvd_of_alternating_pairedConditional resolution of OP-205: if, for every m ≥ 5, every tight, exactly dyadically covered, fully ordinarily covered integer Boolean…
The proof, explained
The equivalence covering number of the cycle power graph Cₙᵏ is proven to be m + 2 by matching upper and lower bounds. An explicit construction provides an equivalence cover of size m + 2, establishing the upper bound. For the lower bound, any hypothetical cover of size at most m + 1 induces a periodic integer Boolean class model; the structural hypothesis `hshape` guarantees this model has no selected islands, which implies 2ᵐ ∣ n, directly contradicting the numerical assumption that k + 1 does not divide n.
m ≠ 1, so m ≥ 2.
Suppose, for contradiction, that m = 1. Then k + 1 = 2¹ = 2, so k = 1. Since n is even, 2 ∣ n, which means k + 1 ∣ n. This directly contradicts the hypothesis that k + 1 does not divide n.
uses
Nat.reduceAddhave hm1 : m ≠ 1 := by intro he have hk1 : k=1 := by norm_num [he] at hkm; omega have h2 : 2 ∣ n := by rcases hev with ⟨a, ha⟩ exact ⟨a, by omega⟩ apply hnd simpa only [hk1, Nat.reduceAdd] using h2
2 ≤ m, 4 ≤ 2ᵐ, and 3 ≤ k.
From 1 ≤ m and m ≠ 1, integer arithmetic gives 2 ≤ m. Monotonicity of powers (`Nat.pow_le_pow_right`) yields 4 = 2² ≤ 2ᵐ. Since k + 1 = 2ᵐ ≥ 4, we also have k ≥ 3.
uses
Nat.pow_le_pow_righthave hm2 : 2 ≤ m := by omega have hD4 : 4 ≤ 2^m := by calc 4 = 2^2 := by decide _ ≤ 2^m := Nat.pow_le_pow_right (by decide) hm2 have hk3 : 3 ≤ k := by omega
max(2k + 2, 2k²) ≤ n.
From n ≥ max(2k + 2, k²(k + 2)), we extract 2k + 2 ≤ n and k²(k + 2) ≤ n using `le_max_left` and `le_max_right`. Since 2 ≤ k + 2, multiplying by k² via `Nat.mul_le_mul_left` yields 2k² ≤ k²(k + 2) ≤ n. Combining these two inequalities with `max_le_iff.mpr` establishes max(2k + 2, 2k²) ≤ n.
uses
le_max_left,le_max_right,Nat.mul_le_mul_left,max_le_iff.mprhave hnA : 2*k+2 ≤ n := (le_max_left _ _).trans hn have hnB : k^2*(k+2) ≤ n := (le_max_right _ _).trans hn have hnB2 : 2*k^2 ≤ n := by calc 2*k^2 = k^2*2 := by ring _ ≤ k^2*(k+2) := Nat.mul_le_mul_left (k^2) (by omega) _ ≤ n := hnB have hnu : max (2*k+2) (2*k^2) ≤ n := max_le_iff.mpr ⟨hnA, hnB2⟩
The cycle power graph has an equivalence cover of size m + 2, and showing the covering number equals m + 2 reduces to proving m + 2 ≤ t for any valid cover size t.
By `simple_graph_has_equivalence_cover_cycle_power_dyadic_upper`, the graph admits an equivalence cover of size m + 2. The covering number is defined as the infimum of all cover sizes. By `le_antisymm`, it is at most m + 2 (using `Nat.sInf_le`), and proving equality reduces via `le_csInf` to establishing that every cover size t satisfies m + 2 ≤ t.
uses
simple_graph_has_equivalence_cover_cycle_power_dyadic_upper,le_antisymm,Nat.sInf_le,le_csInfhave hupper := simple_graph_has_equivalence_cover_cycle_power_dyadic_upper k m n (by omega) hkm hnu letI : NeZero n := ⟨by omega⟩ refine le_antisymm (Nat.sInf_le hupper) (le_csInf ⟨m+2, hupper⟩ fun t ht => ?_)
Assuming a cover of size t < m + 2 exists, there is an equivalence cover with m + 1 relations, and k = 2ᵐ - 1.
Suppose for contradiction that t < m + 2, which gives t ≤ m + 1. By monotonicity of equivalence covers (`simple_graph_has_equivalence_cover_mono`), the cover of size t extends to an equivalence cover c of size m + 1. In addition, k + 1 = 2ᵐ gives k = 2ᵐ - 1.
uses
simple_graph_has_equivalence_cover_monoby_contra hbad have htle : t ≤ m+1 := by omega obtain ⟨c, hc, hcov⟩ := simple_graph_has_equivalence_cover_mono (simple_graph_cycle_power n k) htle ht have hkD : k=2^m-1 := by omega
3(2ᵐ - 1) + 1 ≤ n.
Since 3 ≤ k, multiplying by k via `Nat.mul_le_mul_right` gives 3k ≤ k². Nonlinear arithmetic with 2k² ≤ n then yields 3k + 1 ≤ n. Rewriting k as 2ᵐ - 1 gives 3(2ᵐ - 1) + 1 ≤ n, satisfying the lower bound required for the model construction.
uses
Nat.mul_le_mul_righthave hn3k : 3*k+1 ≤ n := by have hsq := Nat.mul_le_mul_right k hk3 nlinarith [hnB2] have hn3 : 3*(2^m-1)+1 ≤ n := by simpa only [← hkD] using hn3k rw [hkD] at hc hcov
The (m + 1)-cover induces a periodic integer Boolean class model (x, ℓ) satisfying dyadic coverage and separation properties.
Applying `simple_graph_cycle_power_dyadic_cover_class_model` to the cover c on Cₙ^(2ᵐ - 1) produces a Boolean model x : ℤ → ℕ → Bool and class coloring ℓ : ℤ → Fin(m + 1). The model is n-periodic, tight, has vertex count m + 1, covers all dyadic scales j < m, covers every distance d < 2ᵐ, and assigns distinct class indices to distinct active classes at each vertex.
uses
simple_graph_cycle_power_dyadic_cover_class_modelobtain ⟨x, ell, hxp, hep, hends, htw, hct, hex, hcv, hfaith, hsep⟩ := simple_graph_cycle_power_dyadic_cover_class_model m n (by omega) hn3 c hc hcov
The model forces 2ᵐ ∣ n, contradicting ¬(k + 1 ∣ n).
Applying the structural hypothesis `hshape` to x shows that x has no selected islands. Then `cycle_power_dyadic_model_dvd_of_no_island` deduces that 2ᵐ ∣ n. Since k + 1 = 2ᵐ, this means k + 1 ∣ n, which contradicts the hypothesis ¬(k + 1 ∣ n).
uses
cycle_power_dyadic_model_dvd_of_no_islandhave hs := hshape x htw hex hcv hct have hdvd := cycle_power_dyadic_model_dvd_of_no_island m n hm2 (by omega) x ell hxp hep htw hct hex hcv hsep hs apply hnd simpa only [hkm] using hdvd
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
le_csInf- For a nonempty set bounded below, if a is a lower bound for every element in s, then a ≤ inf s.
le_max_left- Any element a is less than or equal to max(a, b).
le_max_right- Any element b is less than or equal to max(a, b).
max_le_iff.mpr- If both a ≤ c and b ≤ c, then max(a, b) ≤ c.
Nat.mul_le_mul_left- Multiplying an inequality n ≤ m on the left by k preserves the inequality, k · n ≤ k · m.
Nat.mul_le_mul_right- Multiplying an inequality n ≤ m on the right by k preserves the inequality, n · k ≤ m · k.
Nat.pow_le_pow_right- For a positive base n > 0, exponentiation nⁱ ≤ nʲ is monotonic with respect to exponents i ≤ j.
Nat.reduceAdd- Evaluates addition of natural number literals directly, reducing 1 + 1 to 2.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element belonging to the set.
simple_graph_has_equivalence_cover_cycle_power_dyadic_upper- For dyadic k + 1 = 2ᵐ and sufficiently large cycle size n ≥ max(2k+2, 2k²), the cycle power graph Cₙᵏ has an equivalence cover of size m + 2.
simple_graph_has_equivalence_cover_mono- If a graph has an equivalence cover of size s and s ≤ t, then it also has an equivalence cover of size t.
simple_graph_cycle_power_dyadic_cover_class_model- An equivalence cover of Cₙ^(2ᵐ - 1) using m + 1 relations induces an n-periodic integer Boolean class model (x, ℓ) that is tight, has vertex degree m + 1, exactly covers dyadic scales, covers all distances, and has separated class labels at every vertex.
cycle_power_dyadic_model_dvd_of_no_island- For m ≥ 2, any tight, dyadically covered, distance-covering periodic integer Boolean model with m + 1 classes per vertex that has no selected island must satisfy 2ᵐ ∣ n.
- The theorem does not settle Open Problem 205 unconditionally: it relies on the explicit structural hypothesis `hshape` asserting that any tight, dyadically covered, distance-covering integer Boolean model with m+1 active classes per vertex has no selected island (the monotonicity condition on class profiles).
- The inequality 3k + 1 ≤ n in Step 6 is discharged by nonlinear arithmetic (`nlinarith`) combining 2k² ≤ n and k ≥ 3.
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_equivalence_covering_number_cycle_power_dyadic_of_class_shape (k m n : ℕ) (hm : 1 ≤ m) (hkm : k+1 = 2^m) (hn : max (2*k+2) (k^2*(k+2)) ≤ n) (hev : Even n) (hnd : ¬(k+1) ∣ n) (hshape : ∀ (x : ℤ → ℕ → Bool), (∀ p, cycle_power_dyadic_class_weight m (x p) = (Finset.range (2^m)).sum (fun a => (x p a).toNat)) → (∀ 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) → (∀ v : ℤ, (Finset.range (2^m)).sum (fun a => (x (v-(a : ℤ)) a).toNat) = m+1) → ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < 2^m → x p a = false → x p b = true → x p c = true) : simple_graph_equivalence_covering_number (simple_graph_cycle_power n k) = m+2 := by have hm1 : m ≠ 1 := by intro he have hk1 : k=1 := by norm_num [he] at hkm; omega have h2 : 2 ∣ n := by rcases hev with ⟨a, ha⟩ exact ⟨a, by omega⟩ apply hnd simpa only [hk1, Nat.reduceAdd] using h2 have hm2 : 2 ≤ m := by omega have hD4 : 4 ≤ 2^m := by calc 4 = 2^2 := by decide _ ≤ 2^m := Nat.pow_le_pow_right (by decide) hm2 have hk3 : 3 ≤ k := by omega have hnA : 2*k+2 ≤ n := (le_max_left _ _).trans hn have hnB : k^2*(k+2) ≤ n := (le_max_right _ _).trans hn have hnB2 : 2*k^2 ≤ n := by calc 2*k^2 = k^2*2 := by ring _ ≤ k^2*(k+2) := Nat.mul_le_mul_left (k^2) (by omega) _ ≤ n := hnB have hnu : max (2*k+2) (2*k^2) ≤ n := max_le_iff.mpr ⟨hnA, hnB2⟩ have hupper := simple_graph_has_equivalence_cover_cycle_power_dyadic_upper k m n (by omega) hkm hnu letI : NeZero n := ⟨by omega⟩ refine le_antisymm (Nat.sInf_le hupper) (le_csInf ⟨m+2, hupper⟩ fun t ht => ?_) by_contra hbad have htle : t ≤ m+1 := by omega obtain ⟨c, hc, hcov⟩ := simple_graph_has_equivalence_cover_mono (simple_graph_cycle_power n k) htle ht have hkD : k=2^m-1 := by omega have hn3k : 3*k+1 ≤ n := by have hsq := Nat.mul_le_mul_right k hk3 nlinarith [hnB2] have hn3 : 3*(2^m-1)+1 ≤ n := by simpa only [← hkD] using hn3k rw [hkD] at hc hcov obtain ⟨x, ell, hxp, hep, hends, htw, hct, hex, hcv, hfaith, hsep⟩ := simple_graph_cycle_power_dyadic_cover_class_model m n (by omega) hn3 c hc hcov have hs := hshape x htw hex hcv hct have hdvd := cycle_power_dyadic_model_dvd_of_no_island m n hm2 (by omega) x ell hxp hep htw hct hex hcv hsep hs apply hnd simpa only [hkm] using hdvd