cyclic_matrix_fourier_zero_zero_ne_zero
For 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 adjacency matrix is nonzero.
Statement
theorem cyclic_matrix_fourier_zero_zero_ne_zero {V : Type*} [Fintype V] (N : ℕ) [NeZero N] (G : SimpleGraph V) [DecidableRel G.Adj] (π : ZMod N ≃ V) (he : ∃ u v, G.Adj u v) : cyclic_matrix_fourier N (Matrix.of fun x y => if G.Adj (π x) (π y) then (1 : ℂ) else 0) 0 0 ≠ 0
- Source
- step towards sharp_cyclic_graph_is_regular
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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)…
- Used by 1
- sharp_cyclic_graph_is_regularEvery finite simple graph G with at least one edge that admits a sharp cyclic labeling on ZMod N is regular of some degree d.
The proof, explained
The (0,0) entry of the cyclic 2D Fourier transform evaluates to (1/N) times the total sum of vertex degrees in G, because the phase factors exp(0) equal 1. Since N is nonzero, this entry vanishes only if the sum of degrees is zero. However, an edge u ~ v guarantees that u has degree at least 1, which provides a strictly positive lower bound on the sum of non-negative degrees and yields a contradiction.
It suffices to show that the sum of vertex degrees is nonzero in ℂ.
Unfolding the cyclic Fourier transform at indices $(0, 0)$, the phase factor simplifies to $\exp(0) = 1$. The sum over the indicator of $G.\mathrm{Adj}(\pi(x), \pi(y))$ simplifies to the cardinality of the neighbor set of $\pi(x)$. Because $N \neq 0$ (via `NeZero.ne`), the scalar factor $1/N$ is nonzero, so the transform entry is nonzero if and only if the sum of all vertex degrees is nonzero.
uses
NeZero.neunfold cyclic_matrix_fourier simp refine ⟨NeZero.ne N, ?_⟩
Assume for contradiction that the sum of degrees is zero in ℕ, and fix an edge in G.
Assuming for contradiction that the sum of degrees is zero in ℂ, we push the coercion inside the sum using `Nat.cast_sum` and reflect it to ℕ using `Nat.cast_eq_zero`. We also unpack the hypothesis `he` to obtain two adjacent vertices $u, v \in V$.
uses
Nat.cast_sum,Nat.cast_eq_zerointro h rw [← Nat.cast_sum, Nat.cast_eq_zero] at h rcases he with ⟨u, v, huv⟩
The vertex u has strictly positive degree.
To show that the neighbor set of $\pi^{-1}(u)$ has cardinality strictly greater than 0, it suffices by `Finset.card_pos` to show it is nonempty. The preimage $\pi^{-1}(v)$ serves as a witness: it belongs to the universal set (`Finset.mem_univ`) and its image $v = \pi(\pi^{-1}(v))$ is adjacent to $u = \pi(\pi^{-1}(u))$ by the edge hypothesis (`Finset.mem_filter`).
uses
Finset.card_pos,Finset.mem_filter,Finset.mem_univhave hpos_card : 0 < (Finset.filter (fun y => G.Adj (π (π.symm u)) (π y)) Finset.univ).card := by rw [Finset.card_pos] refine ⟨π.symm v, ?_⟩ rw [Finset.mem_filter] refine ⟨Finset.mem_univ _, ?_⟩ simpa using huv
The degree of u is bounded above by the total sum of degrees.
Because every degree is non-negative (`Nat.zero_le`), any single term in the sum—namely the term for $\pi^{-1}(u) \in \text{Finset.univ}$—is bounded above by the total sum over all vertices (`Finset.single_le_sum`).
uses
Finset.single_le_sum,Nat.zero_le,Finset.mem_univhave hle := Finset.single_le_sum (f := fun x => (Finset.filter (fun y => G.Adj (π x) (π y)) Finset.univ).card) (fun _ _ => Nat.zero_le _) (Finset.mem_univ (π.symm u))
Contradiction. automation
We have $0 < \operatorname{deg}(u) \le \sum_x \operatorname{deg}(\pi(x)) = 0$, which is impossible. Linear integer arithmetic (`omega`) closes the goal.
omega
NeZero.ne- An element with a `NeZero` instance is nonzero.
Nat.cast_sum- The coercion of a finite sum of natural numbers into an additive structure with one equals the sum of the coerced terms.
Nat.cast_eq_zero- In a ring of characteristic zero, the coercion of a natural number is zero if and only if the number is zero.
Finset.card_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.mem_filter- An element belongs to a filtered finset if and only if it is in the original finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.single_le_sum- A single term in a finite sum of non-negative elements in an ordered monoid is bounded above by the total sum.
Nat.zero_le- Every natural number is greater than or equal to zero.
- In line 6, `simp` simultaneously evaluates the complex exponential at zero to 1, reduces the sum of the adjacency indicators over $y$ to the cardinality of the neighbor set, and splits the nonzeroness of the product $(1/N) \cdot \sum \text{card}$ into $N \neq 0$ and the sum being nonzero.
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.
/-- If G has at least one edge, the (0,0) entry of its cyclic Fourier transform under any bijection π is nonzero, because it is (1/N) times the positive sum of non-negative adjacency indicators. -/theorem cyclic_matrix_fourier_zero_zero_ne_zero {V : Type*} [Fintype V] (N : ℕ) [NeZero N] (G : SimpleGraph V) [DecidableRel G.Adj] (π : ZMod N ≃ V) (he : ∃ u v, G.Adj u v) : cyclic_matrix_fourier N (Matrix.of fun x y => if G.Adj (π x) (π y) then (1 : ℂ) else 0) 0 0 ≠ 0 := by unfold cyclic_matrix_fourier simp refine ⟨NeZero.ne N, ?_⟩ intro h rw [← Nat.cast_sum, Nat.cast_eq_zero] at h rcases he with ⟨u, v, huv⟩ have hpos_card : 0 < (Finset.filter (fun y => G.Adj (π (π.symm u)) (π y)) Finset.univ).card := by rw [Finset.card_pos] refine ⟨π.symm v, ?_⟩ rw [Finset.mem_filter] refine ⟨Finset.mem_univ _, ?_⟩ simpa using huv have hle := Finset.single_le_sum (f := fun x => (Finset.filter (fun y => G.Adj (π x) (π y)) Finset.univ).card) (fun _ _ => Nat.zero_le _) (Finset.mem_univ (π.symm u)) omega