AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shape

theoremverified

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
Used by 3

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.

  1. 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.

    lines 21–28

    uses Nat.reduceAdd

      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
  2. 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.

    lines 29–34

    uses Nat.pow_le_pow_right

      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
  3. 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.

    lines 35–42

    uses le_max_left, le_max_right, Nat.mul_le_mul_left, max_le_iff.mpr

      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⟩
  4. 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.

    lines 43–45

    uses simple_graph_has_equivalence_cover_cycle_power_dyadic_upper, le_antisymm, Nat.sInf_le, le_csInf

      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 => ?_)
  5. 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.

    lines 46–50

    uses simple_graph_has_equivalence_cover_mono

      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
  6. 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.

    lines 51–55

    uses Nat.mul_le_mul_right

      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
  7. 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.

    lines 56–57

    uses simple_graph_cycle_power_dyadic_cover_class_model

      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
  8. 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).

    lines 58–62

    uses cycle_power_dyadic_model_dvd_of_no_island

      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
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.

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_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
See it in the graphDiscuss this resultChallenge it