AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_forty_six_three

theoremverifiedoriginal

eq(C_46^3) = 4: the smallest case of the open problem (k = 3, n = 46 even, 4 ∤ 46, 46 ≥ 45), where the paper only knows eq ∈ {3, 4, 5}.

Statement

theorem simple_graph_equivalence_covering_number_cycle_power_forty_six_three :
    simple_graph_equivalence_covering_number (simple_graph_cycle_power 46 3) = 4
Related work
arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs): the smallest instance (k = 3, n = 46) of the case Theorems 1.3 and 1.4 do not cover; Theorem 1.4 does not apply below n = 164, so only 3 ≤ eq ≤ 5 is known. SAT search: experiment 708.
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

The proof establishes that the equivalence covering number of the cycle power C_46^3 is 4 by matching upper and lower bounds. The upper bound eq(C_46^3) ≤ 4 is obtained by exhibiting an explicit 4-equivalence cover (given by four lists of 46 vertex labels) and verifying its validity via finite kernel computation. The lower bound eq(C_46^3) ≥ 4 follows from a general parity theorem showing that C_n^3 admits no 3-cover whenever n ≥ 10 and 4 ∤ n, which rules out any cover of size t ≤ 3 for n = 46.

  1. Specify a candidate 4-equivalence cover for C_46^3, reducing the existence of a 4-cover to two finite verification subgoals.

    An equivalence cover of size 4 consists of four functions c_s : ℤ/46ℤ → ℤ/46ℤ mapping each vertex to its equivalence class representative. We supply four explicit lists of 46 labels to define these assignments and split the proof into checking that monochromatic pairs form cliques in C_46^3 and that every edge of C_46^3 is covered by at least one relation.

    lines 3–8

      have hcov : simple_graph_has_equivalence_cover (simple_graph_cycle_power 46 3) 4 := by
        refine ⟨fun s u => ((([[0, 0, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 12, 12, 12, 12, 16, 16, 16, 16, 20, 20, 20, 20, 24, 24, 24, 24, 28, 28, 28, 28, 32, 32, 32, 32, 36, 36, 36, 36, 40, 40, 40, 40, 0, 0],
          [0, 1, 2, 3, 1, 5, 3, 7, 5, 9, 7, 11, 9, 13, 11, 15, 13, 17, 15, 19, 17, 21, 19, 23, 21, 25, 23, 27, 25, 29, 27, 31, 29, 33, 31, 35, 33, 37, 35, 39, 37, 41, 39, 0, 41, 2],
          [0, 0, 0, 0, 4, 4, 6, 6, 6, 6, 10, 10, 10, 10, 14, 14, 14, 14, 18, 18, 18, 18, 22, 22, 22, 22, 26, 26, 26, 26, 30, 30, 30, 30, 34, 34, 34, 34, 38, 38, 38, 38, 42, 42, 42, 42],
          [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 10, 10, 10, 10, 14, 14, 14, 14, 18, 18, 18, 18, 22, 22, 22, 22, 26, 26, 26, 26, 30, 30, 30, 30, 34, 34, 34, 34, 38, 38, 38, 38, 42, 42, 42, 42]]
          : List (List ℕ)).getD s.val []).getD u.val 0 : ZMod 46), ?_, ?_⟩
  2. Each of the four equivalence relations induces cliques in C_46^3 (any two distinct vertices with the same label have cyclic distance at most 3). automation

    The clique condition states that for all s ∈ Fin 4 and distinct u, v ∈ ℤ/46ℤ, having the same label implies min((u - v).val, (v - u).val) ≤ 3. Because the domain Fin 4 × ℤ/46ℤ × ℤ/46ℤ is finite, this universal statement is decided by exhaustive computation in the Lean kernel (`decide +kernel`).

    lines 9–10

        · show ∀ (s : Fin 4) (u v : ZMod 46), u ≠ v → _ = _ → u ≠ v ∧ min (u - v).val (v - u).val ≤ 3
          decide +kernel
  3. Every edge of C_46^3 is covered by at least one of the four equivalence relations. automation

    The edge coverage condition states that whenever min((u - v).val, (v - u).val) ≤ 3 for u ≠ v, there exists some s ∈ Fin 4 such that u and v receive the same label. This finite check over all pairs in ℤ/46ℤ is similarly verified by exhaustive kernel computation (`decide +kernel`).

    lines 11–12

        · show ∀ (u v : ZMod 46), u ≠ v ∧ min (u - v).val (v - u).val ≤ 3 → ∃ s : Fin 4, _
          decide +kernel
  4. The equivalence covering number of C_46^3 equals 4 provided every cover has size at least 4.

    By antisymmetry (`le_antisymm`), showing the infimum equals 4 reduces to proving it is at most 4 and at least 4. The upper bound follows from the explicit 4-cover just established (`Nat.sInf_le`). Because the set of valid cover sizes is nonempty, the lower bound 4 ≤ sInf reduces by `le_csInf` to showing 4 ≤ t for any valid cover size t.

    line 13

    uses le_antisymm, Nat.sInf_le, le_csInf

      refine le_antisymm (Nat.sInf_le hcov) (le_csInf ⟨4, hcov⟩ fun t ht => ?_)
  5. Every valid equivalence cover of C_46^3 has size at least 4.

    Assume for contradiction (`by_contra`) that there is a cover of size t < 4, which implies t ≤ 3 by integer arithmetic (`omega`). By monotonicity of equivalence covers (`simple_graph_has_equivalence_cover_mono`), this would yield a 3-cover of C_46^3. However, theorem `simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd` states that C_n^3 has no 3-cover when n ≥ 10 and 4 ∤ n; since 10 ≤ 46 and 4 ∤ 46 (checked by `norm_num`), this produces a contradiction.

    lines 14–16

    uses simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd, simple_graph_has_equivalence_cover_mono

      by_contra hlt
      exact simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd 46 (by norm_num)
        (by norm_num) (simple_graph_has_equivalence_cover_mono _ (by omega) ht)
le_antisymm
in a partial order, if a ≤ b and b ≤ a, then a = b
Nat.sInf_le
an element belonging to a set of natural numbers is greater than or equal to the infimum of that set
le_csInf
in a conditionally complete lattice, if a set s is nonempty and a is a lower bound for s, then a ≤ sInf s
simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd
for n ≥ 10 with 4 ∤ n, the cycle power C_n^3 has no equivalence cover of size 3
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

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

theorem simple_graph_equivalence_covering_number_cycle_power_forty_six_three :    simple_graph_equivalence_covering_number (simple_graph_cycle_power 46 3) = 4 := by  have hcov : simple_graph_has_equivalence_cover (simple_graph_cycle_power 46 3) 4 := by    refine ⟨fun s u => ((([[0, 0, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 12, 12, 12, 12, 16, 16, 16, 16, 20, 20, 20, 20, 24, 24, 24, 24, 28, 28, 28, 28, 32, 32, 32, 32, 36, 36, 36, 36, 40, 40, 40, 40, 0, 0],      [0, 1, 2, 3, 1, 5, 3, 7, 5, 9, 7, 11, 9, 13, 11, 15, 13, 17, 15, 19, 17, 21, 19, 23, 21, 25, 23, 27, 25, 29, 27, 31, 29, 33, 31, 35, 33, 37, 35, 39, 37, 41, 39, 0, 41, 2],      [0, 0, 0, 0, 4, 4, 6, 6, 6, 6, 10, 10, 10, 10, 14, 14, 14, 14, 18, 18, 18, 18, 22, 22, 22, 22, 26, 26, 26, 26, 30, 30, 30, 30, 34, 34, 34, 34, 38, 38, 38, 38, 42, 42, 42, 42],      [0, 0, 2, 2, 2, 2, 6, 6, 6, 6, 10, 10, 10, 10, 14, 14, 14, 14, 18, 18, 18, 18, 22, 22, 22, 22, 26, 26, 26, 26, 30, 30, 30, 30, 34, 34, 34, 34, 38, 38, 38, 38, 42, 42, 42, 42]]      : List (List ℕ)).getD s.val []).getD u.val 0 : ZMod 46), ?_, ?_⟩    · show ∀ (s : Fin 4) (u v : ZMod 46), u ≠ v → _ = _ → u ≠ v ∧ min (u - v).val (v - u).val ≤ 3      decide +kernel    · show ∀ (u v : ZMod 46), u ≠ v ∧ min (u - v).val (v - u).val ≤ 3 → ∃ s : Fin 4, _      decide +kernel  refine le_antisymm (Nat.sInf_le hcov) (le_csInf ⟨4, hcov⟩ fun t ht => ?_)  by_contra hlt  exact simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd 46 (by norm_num)    (by norm_num) (simple_graph_has_equivalence_cover_mono _ (by omega) ht)
See it in the graphDiscuss this resultChallenge it