simple_graph_equivalence_covering_number_cycle_power_forty_six_three
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
- 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_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- simple_graph_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- 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_not_has_equivalence_cover_cycle_power_three_of_not_dvdFor every n ≥ 10 not divisible by 4, the cube C_n^3 of the n-cycle cannot be covered by 3 equivalence subgraphs; with the lower bound eq ≥…
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.
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.
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), ?_, ?_⟩
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`).
· show ∀ (s : Fin 4) (u v : ZMod 46), u ≠ v → _ = _ → u ≠ v ∧ min (u - v).val (v - u).val ≤ 3 decide +kernel
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`).
· show ∀ (u v : ZMod 46), u ≠ v ∧ min (u - v).val (v - u).val ≤ 3 → ∃ s : Fin 4, _ decide +kernel
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.
uses
le_antisymm,Nat.sInf_le,le_csInfrefine le_antisymm (Nat.sInf_le hcov) (le_csInf ⟨4, hcov⟩ fun t ht => ?_)
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.
uses
simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd,simple_graph_has_equivalence_cover_monoby_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
- The validity of the 4-equivalence cover in Steps 2 and 3 is verified entirely by computational reflection in the Lean kernel (`decide +kernel`), which exhaustively checks the clique condition on all vertex pairs and the edge coverage condition across all edges.
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.
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)