sharp_cyclic_and_compl_imp_antidiagonal
If G is a simple graph on ZMod N such that both G and its complement G^c have at least one edge, and the standard cyclic labeling is sharp for both G and G^c, then the two-dimensional cyclic Fourier transform of the adjacency matrix of G vanishes whenever m + n ≠ 0.
Statement
theorem sharp_cyclic_and_compl_imp_antidiagonal (N : ℕ) [NeZero N]
(G : SimpleGraph (ZMod N)) [DecidableRel G.Adj]
(he : ∃ u v, G.Adj u v) (hec : ∃ u v, Gᶜ.Adj u v)
(hG : is_sharp_cyclic_labeling N G (Equiv.refl (ZMod N)))
(hGc : is_sharp_cyclic_labeling N Gᶜ (Equiv.refl (ZMod N)))
(m n : ZMod N) (hmn : m + n ≠ 0) :
cyclic_matrix_fourier N (G.adjMatrix ℂ) m n = 0- Source
- arXiv:2610.31807 Proposition 4.9 -- Additive energy and Fourier complexity of graphs
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- cyclic_matrix_fourier_compl_adjMatrixFor any simple graph G on ZMod N, the two-dimensional cyclic Fourier transform of the complement graph's adjacency matrix at (m,n) is…
- 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…
- 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_weighted_partial_permutationA square complex matrix M is a weighted partial permutation matrix if for every row index i, any two column indices with nonzero entries…
Read back from the Lean
For any positive natural number $N$ (with $[\\text{NeZero } N]$) and any simple graph $G$ on the vertex set $\\mathbb{Z}/N\\mathbb{Z}$ with decidable adjacency: Assume: 1. $G$ has at least one edge (there exist $u, v \\in \\mathbb{Z}/N\\mathbb{Z}$ such that $G.\\text{Adj } u\\ v$). 2. The complement graph $G^c$ has at least one edge (there exist $u, v \\in \\mathbb{Z}/N\\mathbb{Z}$ such that $G^c.\\text{Adj } u\\ v$). 3. The identity labeling on $\\mathbb{Z}/N\\mathbb{Z}$ is a sharp cyclic labeling for $G$ (i.e., the cyclic Fourier transform of the adjacency matrix of $G$ is a weighted partial permutation matrix, having at most one non-zero entry in each row and each column). 4. The identity labeling on $\\mathbb{Z}/N\\mathbb{Z}$ is a sharp cyclic labeling for $G^c$ (i.e., the cyclic Fourier transform of the adjacency matrix of $G^c$ is also a weighted partial permutation matrix). Then for all $m, n \\in \\mathbb{Z}/N\\mathbb{Z}$ such that $m + n \\neq 0$, the $(m, n)$-entry of the cyclic Fourier transform of the adjacency matrix of $G$ over $\\mathbb{C}$ is $0$ (i.e., the Fourier transform matrix is supported only on the anti-diagonal $m + n = 0$).
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 proceeds by contradiction. If the 2D cyclic Fourier transform of the adjacency matrix of G were non-zero at (m, n) with m + n ≠ 0, then column n would be the unique non-zero entry in row m, forcing the entry at (m, -m) to vanish. Using the identity relating the Fourier transform of a graph's complement to that of the graph, the Fourier transform of Gᶜ would then be non-zero at both (m, -m) and (m, n). This gives two distinct non-zero entries in row m of the Fourier transform of Gᶜ, contradicting the assumption that Gᶜ has a sharp cyclic labeling.
The 2D cyclic Fourier transform of the adjacency matrix of G is a weighted partial permutation.
By definition, the identity labeling Equiv.refl being sharp for G means that the Fourier transform of the matrix with entries 1 on edges and 0 on non-edges is a weighted partial permutation. Simplifying Equiv.refl_apply and recognizing this matrix as SimpleGraph.adjMatrix yields the claim.
uses
Equiv.refl_apply,SimpleGraph.adjMatrixhave hFwpp : is_weighted_partial_permutation (cyclic_matrix_fourier N (G.adjMatrix ℂ)) := by unfold is_sharp_cyclic_labeling at hG simp only [Equiv.refl_apply] at hG change is_weighted_partial_permutation (cyclic_matrix_fourier N (Matrix.of fun i j => if G.Adj i j then (1:ℂ) else 0)) at hG simpa [SimpleGraph.adjMatrix] using hG
The 2D cyclic Fourier transform of the adjacency matrix of the complement graph Gᶜ is a weighted partial permutation.
By the same unfolding and simplification applied to the sharpness hypothesis for Gᶜ, the Fourier transform of the adjacency matrix of Gᶜ is also a weighted partial permutation.
uses
Equiv.refl_apply,SimpleGraph.adjMatrixhave hEwpp : is_weighted_partial_permutation (cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ)) := by unfold is_sharp_cyclic_labeling at hGc simp only [Equiv.refl_apply] at hGc change is_weighted_partial_permutation (cyclic_matrix_fourier N (Matrix.of fun i j => if Gᶜ.Adj i j then (1:ℂ) else 0)) at hGc simpa [SimpleGraph.adjMatrix] using hGc
Each row of the Fourier transform of the adjacency matrix of G (and of Gᶜ) contains at most one non-zero entry.
By definition of a weighted partial permutation, the first conjunct (.1) states that for any row i, if the entries at columns j₁ and j₂ are both non-zero, then j₁ = j₂. We name these row properties hFrow and hErow respectively.
have hFrow := hFwpp.1 have hErow := hEwpp.1
Assuming for contradiction that the Fourier transform of G at (m, n) is non-zero, we have n ≠ -m.
We assume for contradiction that the (m, n) Fourier coefficient is non-zero. If n = -m, then m + n = 0, directly contradicting the theorem hypothesis m + n ≠ 0. Therefore, n ≠ -m.
by_contra hFmn have hmn' : n ≠ -m := by intro h exact hmn (by rw [h]; simp)
The Fourier transform of the adjacency matrix of G at (m, -m) equals 0.
If the (m, -m) entry were non-zero, row m would have non-zero entries at both column n and column -m. The row property hFrow would then force n = -m, contradicting n ≠ -m.
have hF_mneg : cyclic_matrix_fourier N (G.adjMatrix ℂ) m (-m) = 0 := by by_contra h exact hmn' (hFrow m n (-m) hFmn h)
The scalar D(m, -m) = (if m = 0 ∧ -m = 0 then N else 0) - (if m + -m = 0 then 1 else 0) is non-zero.
We split into cases on whether m = 0. If m ≠ 0, the first indicator is 0 and the second is 1, yielding -1 ≠ 0. If m = 0, the expression simplifies to N - 1; if N = 1, then ℤ/Nℤ would be a subsingleton, forcing n = 0 and hence m + n = 0, contradicting m + n ≠ 0. Thus N ≠ 1 and N - 1 ≠ 0.
uses
ZMod.subsingleton_iff,Subsingleton.elim,sub_ne_zero.mprhave hD_mneg : ((if m = 0 ∧ -m = 0 then (N : ℂ) else 0) - (if m + -m = 0 then 1 else 0)) ≠ 0 := by by_cases hm0 : m = 0 · subst hm0 have hN1 : (N : ℂ) - 1 ≠ 0 := by have hN : (N : ℂ) ≠ 1 := by intro h have hNnat : N = 1 := by exact_mod_cast h have hn0 : n = 0 := by have : Subsingleton (ZMod N) := (ZMod.subsingleton_iff).mpr hNnat exact Subsingleton.elim n 0 exact hmn (by simpa [hn0]) exact sub_ne_zero.mpr hN simpa using hN1 · simp [hm0]
The Fourier transform of the adjacency matrix of Gᶜ at (m, -m) is non-zero.
By the complement formula cyclic_matrix_fourier_compl_adjMatrix, the Fourier coefficient of Gᶜ at (m, -m) equals D(m, -m) minus the Fourier coefficient of G at (m, -m). Since the latter is 0 and D(m, -m) ≠ 0, the result is non-zero.
uses
cyclic_matrix_fourier_compl_adjMatrixhave hFc_mneg : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m (-m) ≠ 0 := by rw [cyclic_matrix_fourier_compl_adjMatrix] rw [hF_mneg] simpa using hD_mneg
The scalar D(m, n) = (if m = 0 ∧ n = 0 then N else 0) - (if m + n = 0 then 1 else 0) equals 0.
Since m + n ≠ 0, both condition m + n = 0 and condition (m = 0 ∧ n = 0) are false, so both indicators vanish, leaving 0 - 0 = 0.
have hDmn : ((if m = 0 ∧ n = 0 then (N : ℂ) else 0) - (if m + n = 0 then 1 else 0)) = 0 := by have : ¬ (m = 0 ∧ n = 0) := by rintro ⟨hm, hn⟩ exact hmn (by rw [hm, hn]; simp) simp [this, hmn]
The Fourier transform of the adjacency matrix of Gᶜ at (m, n) is non-zero.
By the complement formula cyclic_matrix_fourier_compl_adjMatrix, the Fourier coefficient of Gᶜ at (m, n) is D(m, n) - F(G)(m, n) = -F(G)(m, n). Since F(G)(m, n) ≠ 0 by assumption, this entry is non-zero.
uses
cyclic_matrix_fourier_compl_adjMatrixhave hFc_mn : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m n ≠ 0 := by rw [cyclic_matrix_fourier_compl_adjMatrix] rw [hDmn] simpa using hFmn
A contradiction is reached, concluding the proof.
Row m of the Fourier transform of Gᶜ has non-zero entries at both column n and column -m. The row property hErow implies n = -m, which contradicts n ≠ -m.
exact hmn' (hErow m n (-m) hFc_mn hFc_mneg)
Equiv.refl_apply- Applying the identity equivalence `Equiv.refl` to an element `x` returns `x`.
SimpleGraph.adjMatrix- The adjacency matrix of a graph, with entry 1 for adjacent vertices and 0 otherwise.
ZMod.subsingleton_iff- The ring ℤ/nℤ has at most one element if and only if n = 1.
Subsingleton.elim- In any type with at most one element (a subsingleton), any two elements are equal.
sub_ne_zero.mpr- If a ≠ b, then a - b ≠ 0.
cyclic_matrix_fourier_compl_adjMatrix- The 2D cyclic Fourier transform of the complement graph's adjacency matrix at (m, n) equals (N · [m = 0 ∧ n = 0] - [m + n = 0]) - F(G)(m, n).
- The hypotheses `he` (that G has an edge) and `hec` (that Gᶜ has an edge) appear in the theorem statement but are not used in the formal proof.
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.
/-- Simultaneous sharpness for G and its complement implies the 2D Fourier transform is anti-diagonal. -/theorem sharp_cyclic_and_compl_imp_antidiagonal (N : ℕ) [NeZero N] (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj] (he : ∃ u v, G.Adj u v) (hec : ∃ u v, Gᶜ.Adj u v) (hG : is_sharp_cyclic_labeling N G (Equiv.refl (ZMod N))) (hGc : is_sharp_cyclic_labeling N Gᶜ (Equiv.refl (ZMod N))) (m n : ZMod N) (hmn : m + n ≠ 0) : cyclic_matrix_fourier N (G.adjMatrix ℂ) m n = 0 := by have hFwpp : is_weighted_partial_permutation (cyclic_matrix_fourier N (G.adjMatrix ℂ)) := by unfold is_sharp_cyclic_labeling at hG simp only [Equiv.refl_apply] at hG change is_weighted_partial_permutation (cyclic_matrix_fourier N (Matrix.of fun i j => if G.Adj i j then (1:ℂ) else 0)) at hG simpa [SimpleGraph.adjMatrix] using hG have hEwpp : is_weighted_partial_permutation (cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ)) := by unfold is_sharp_cyclic_labeling at hGc simp only [Equiv.refl_apply] at hGc change is_weighted_partial_permutation (cyclic_matrix_fourier N (Matrix.of fun i j => if Gᶜ.Adj i j then (1:ℂ) else 0)) at hGc simpa [SimpleGraph.adjMatrix] using hGc have hFrow := hFwpp.1 have hErow := hEwpp.1 by_contra hFmn have hmn' : n ≠ -m := by intro h exact hmn (by rw [h]; simp) have hF_mneg : cyclic_matrix_fourier N (G.adjMatrix ℂ) m (-m) = 0 := by by_contra h exact hmn' (hFrow m n (-m) hFmn h) have hD_mneg : ((if m = 0 ∧ -m = 0 then (N : ℂ) else 0) - (if m + -m = 0 then 1 else 0)) ≠ 0 := by by_cases hm0 : m = 0 · subst hm0 have hN1 : (N : ℂ) - 1 ≠ 0 := by have hN : (N : ℂ) ≠ 1 := by intro h have hNnat : N = 1 := by exact_mod_cast h have hn0 : n = 0 := by have : Subsingleton (ZMod N) := (ZMod.subsingleton_iff).mpr hNnat exact Subsingleton.elim n 0 exact hmn (by simpa [hn0]) exact sub_ne_zero.mpr hN simpa using hN1 · simp [hm0] have hFc_mneg : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m (-m) ≠ 0 := by rw [cyclic_matrix_fourier_compl_adjMatrix] rw [hF_mneg] simpa using hD_mneg have hDmn : ((if m = 0 ∧ n = 0 then (N : ℂ) else 0) - (if m + n = 0 then 1 else 0)) = 0 := by have : ¬ (m = 0 ∧ n = 0) := by rintro ⟨hm, hn⟩ exact hmn (by rw [hm, hn]; simp) simp [this, hmn] have hFc_mn : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m n ≠ 0 := by rw [cyclic_matrix_fourier_compl_adjMatrix] rw [hDmn] simpa using hFmn exact hmn' (hErow m n (-m) hFc_mn hFc_mneg)