sharp_cyclic_graph_is_regular
Every finite simple graph G with at least one edge that admits a sharp cyclic labeling on ZMod N is regular of some degree d.
Statement
theorem sharp_cyclic_graph_is_regular {V : Type*} [Fintype V] (N : ℕ) [NeZero N] (G : SimpleGraph V) [DecidableRel G.Adj] (he : ∃ u v, G.Adj u v) (hs : admits_sharp_cyclic_labeling N G) : ∃ d : ℕ, G.IsRegularOfDegree d
- Formalizes
- arXiv:2610.31807 Theorem 3.14
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- admits_sharp_cyclic_labelingA simple graph G on N vertices admits a sharp cyclic labeling if there exists a bijection π from ZMod N to V(G) such that…
- cyclic_matrix_fourier_zero_zero_ne_zeroFor any finite graph G with at least one edge and any bijection π : ZMod N ≃ V, the (0,0) entry of the cyclic 2D Fourier transform of the…
- cyclic_fourier_col_zero_eq_zero_of_sharpFor any weighted partial permutation matrix whose (0,0) entry is non-zero, every other entry (m,0) in the 0-th column is zero.
- row_sum_eq_of_fourier_col_zero_vanishIf the cyclic 2D Fourier transform of M has vanishing entries at (m,0) for all m ≠ 0, then all row sums of M are equal.
- cyclic_matrix_fourierThe two-dimensional unitary Fourier transform of a matrix M indexed by ZMod N has (m,n)-entry equal to (1/N) ∑_{x,y} M(x,y)…
- is_sharp_cyclic_labelingA bijection π from ZMod N to the vertex set of a simple graph G is a sharp cyclic labeling if the two-dimensional Fourier transform of the…
Read back from the Lean
Let $V$ be a finite type and $N$ a non-zero natural number. Let $G$ be a simple graph on $V$ with decidable adjacency. Assume that: 1. $G$ contains at least one edge (there exist vertices $u, v \in V$ such that $G.\mathrm{Adj}(u, v)$); 2. $G$ admits a sharp cyclic labeling of size $N$, meaning there exists a bijection $\pi : \mathbb{Z}/N\mathbb{Z} \simeq V$ such that the 2D discrete Fourier transform of the adjacency matrix pulled back by $\pi$ is a weighted partial permutation matrix (at most one non-zero entry per row and per column). Then $G$ is a regular graph (there exists a natural number $d$ such that $G$ is regular of degree $d$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof constructs the adjacency matrix M of G indexed by ZMod N via the sharp cyclic labeling π. Because G has an edge, the (0, 0) entry of the Fourier transform of M is non-zero, which forces all other entries in column 0 of the transform to vanish since the transform is a weighted partial permutation. Fourier analysis then implies that all row sums of M are constant and equal to the row sum of row 0. Finally, identifying the row sums of M with the degrees of the vertices in G via π shows that every vertex has the same degree as π 0, proving that G is regular.
Extract the sharp cyclic labeling π and define the adjacency matrix M on ZMod N.
From the hypothesis that G admits a sharp cyclic labeling, we extract the bijection π : ZMod N ≃ V whose Fourier transform is a weighted partial permutation. We then define M as the adjacency matrix of G pulled back by π, where M x y = 1 if π x and π y are adjacent in G, and 0 otherwise.
obtain ⟨π, hπ⟩ := hs let M : Matrix (ZMod N) (ZMod N) ℂ := Matrix.of fun x y => if G.Adj (π x) (π y) then (1:ℂ) else 0
The Fourier coefficient of M at (0, 0) is non-zero, and every other entry in column 0 of the Fourier transform vanishes.
Because G has at least one edge, the total sum of the entries of M is non-zero, so the (0, 0) Fourier coefficient is non-zero by cyclic_matrix_fourier_zero_zero_ne_zero. Since π is a sharp cyclic labeling, the Fourier transform of M is a weighted partial permutation, having at most one non-zero entry per column. With the (0, 0) entry non-zero, cyclic_fourier_col_zero_eq_zero_of_sharp implies that every other entry in column 0 must vanish.
uses
cyclic_matrix_fourier_zero_zero_ne_zero,cyclic_fourier_col_zero_eq_zero_of_sharphave h0 : cyclic_matrix_fourier N M 0 0 ≠ 0 := cyclic_matrix_fourier_zero_zero_ne_zero N G π he have hF : ∀ m : ZMod N, m ≠ 0 → cyclic_matrix_fourier N M m 0 = 0 := fun m hm => cyclic_fourier_col_zero_eq_zero_of_sharp N M hπ h0 m hm
All row sums of M are equal to the sum of row 0.
Because all entries in column 0 of the cyclic Fourier transform vanish away from the origin, row_sum_eq_of_fourier_col_zero_vanish guarantees that every row sum ∑ y, M x y is equal to the row sum ∑ y, M 0 y.
uses
row_sum_eq_of_fourier_col_zero_vanishhave hrow : ∀ x : ZMod N, (∑ y : ZMod N, M x y) = ∑ y : ZMod N, M 0 y := fun x => row_sum_eq_of_fourier_col_zero_vanish N M hF x
For every x : ZMod N, the row sum ∑ y, M x y equals the degree of π x in G.
Using Matrix.of_apply and Finset.sum_boole, the row sum ∑ y, M x y is first shown to be the cardinality of the filtered set {y | G.Adj (π x) (π y)}. Next, via Finset.card_bij and SimpleGraph.card_neighborFinset_eq_degree, π is shown to define a bijection from this set onto the neighbor finset of π x: it maps into the neighbors (using SimpleGraph.mem_neighborFinset, Finset.mem_filter, Finset.mem_univ, and true_and), is injective since π is an equivalence, and is surjective since any neighbor v has preimage π.symm v in the set. Combining these identities equates the row sum to the vertex degree.
uses
Matrix.of_apply,Finset.sum_boole,SimpleGraph.card_neighborFinset_eq_degree,Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_and,SimpleGraph.mem_neighborFinsethave hdeg : ∀ x : ZMod N, (∑ y : ZMod N, M x y) = (G.degree (π x) : ℂ) := by intro x have h1 : (∑ y : ZMod N, M x y) = ((Finset.univ.filter (fun y => G.Adj (π x) (π y))).card : ℂ) := by simp only [M, Matrix.of_apply] rw [Finset.sum_boole] have h2 : (Finset.univ.filter (fun y : ZMod N => G.Adj (π x) (π y))).card = G.degree (π x) := by rw [← SimpleGraph.card_neighborFinset_eq_degree] apply Finset.card_bij (fun y _ => π y) · intro y hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy exact (SimpleGraph.mem_neighborFinset G (π x) (π y)).mpr hy · intro y1 _ y2 _ h exact π.injective h · intro v hv simp only [SimpleGraph.mem_neighborFinset] at hv exact ⟨π.symm v, by simp [hv], by simp⟩ rw [h1, h2]
G is regular of degree d = G.degree (π 0).
We choose d = G.degree (π 0) as the witness. For any vertex v in V, writing v = π (π.symm v) allows us to equate the degree of v (as a complex number) to the row sum at π.symm v, which equals the row sum at 0 by the constancy of row sums, which in turn equals the degree of π 0. Finally, exact_mod_cast casts this equality from ℂ to ℕ, proving that every vertex has degree d.
refine ⟨G.degree (π 0), ?_⟩ intro v have hd1 : (G.degree v : ℂ) = (G.degree (π 0) : ℂ) := by rw [← π.apply_symm_apply v, ← hdeg (π.symm v), ← hdeg 0] exact hrow (π.symm v) exact_mod_cast hd1
cyclic_matrix_fourier_zero_zero_ne_zero- If a simple graph has at least one edge, the (0, 0) entry of the Fourier transform of its adjacency matrix under any vertex bijection is non-zero.
cyclic_fourier_col_zero_eq_zero_of_sharp- If the cyclic Fourier transform of a matrix is a weighted partial permutation and its (0, 0) entry is non-zero, then all other entries in column 0 vanish.
row_sum_eq_of_fourier_col_zero_vanish- If all non-zero entries in column 0 of the cyclic Fourier transform of a matrix vanish, then every row sum of the matrix equals the row sum of row 0.
Matrix.of_apply- Evaluating the matrix constructed from a function at indices i and j yields the function value f(i, j).
Finset.sum_boole- The sum of indicator functions (1 if p(x) else 0) over a finite set equals the cardinality of the subset of elements satisfying p.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex v in a simple graph equals its degree.
Finset.card_bij- Two finite sets have the same cardinality if there is a well-defined, injective, and surjective map between them.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
true_and- The conjunction of True and any proposition p is logically equivalent to p.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
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.
/-- Every simple graph with at least one edge admitting a sharp cyclic labeling is regular. -/theorem sharp_cyclic_graph_is_regular {V : Type*} [Fintype V] (N : ℕ) [NeZero N] (G : SimpleGraph V) [DecidableRel G.Adj] (he : ∃ u v, G.Adj u v) (hs : admits_sharp_cyclic_labeling N G) : ∃ d : ℕ, G.IsRegularOfDegree d := by obtain ⟨π, hπ⟩ := hs let M : Matrix (ZMod N) (ZMod N) ℂ := Matrix.of fun x y => if G.Adj (π x) (π y) then (1:ℂ) else 0 have h0 : cyclic_matrix_fourier N M 0 0 ≠ 0 := cyclic_matrix_fourier_zero_zero_ne_zero N G π he have hF : ∀ m : ZMod N, m ≠ 0 → cyclic_matrix_fourier N M m 0 = 0 := fun m hm => cyclic_fourier_col_zero_eq_zero_of_sharp N M hπ h0 m hm have hrow : ∀ x : ZMod N, (∑ y : ZMod N, M x y) = ∑ y : ZMod N, M 0 y := fun x => row_sum_eq_of_fourier_col_zero_vanish N M hF x have hdeg : ∀ x : ZMod N, (∑ y : ZMod N, M x y) = (G.degree (π x) : ℂ) := by intro x have h1 : (∑ y : ZMod N, M x y) = ((Finset.univ.filter (fun y => G.Adj (π x) (π y))).card : ℂ) := by simp only [M, Matrix.of_apply] rw [Finset.sum_boole] have h2 : (Finset.univ.filter (fun y : ZMod N => G.Adj (π x) (π y))).card = G.degree (π x) := by rw [← SimpleGraph.card_neighborFinset_eq_degree] apply Finset.card_bij (fun y _ => π y) · intro y hy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hy exact (SimpleGraph.mem_neighborFinset G (π x) (π y)).mpr hy · intro y1 _ y2 _ h exact π.injective h · intro v hv simp only [SimpleGraph.mem_neighborFinset] at hv exact ⟨π.symm v, by simp [hv], by simp⟩ rw [h1, h2] refine ⟨G.degree (π 0), ?_⟩ intro v have hd1 : (G.degree v : ℂ) = (G.degree (π 0) : ℂ) := by rw [← π.apply_symm_apply v, ← hdeg (π.symm v), ← hdeg 0] exact hrow (π.symm v) exact_mod_cast hd1