AFTD Auto-Formalizing Theoretical Domains

sharp_cyclic_graph_is_regular

theoremverifiedformalization

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.

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

    lines 6–7

      obtain ⟨π, hπ⟩ := hs
      let M : Matrix (ZMod N) (ZMod N) ℂ := Matrix.of fun x y => if G.Adj (π x) (π y) then (1:ℂ) else 0
  2. 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.

    lines 8–11

    uses cyclic_matrix_fourier_zero_zero_ne_zero, cyclic_fourier_col_zero_eq_zero_of_sharp

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

    lines 12–13

    uses row_sum_eq_of_fourier_col_zero_vanish

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

    lines 14–32

    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_neighborFinset

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

    lines 33–38

      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

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