row_sum_eq_of_fourier_col_zero_vanish
If 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.
Statement
theorem row_sum_eq_of_fourier_col_zero_vanish (N : ℕ) [NeZero N]
(M : Matrix (ZMod N) (ZMod N) ℂ)
(hF : ∀ m : ZMod N, m ≠ 0 → cyclic_matrix_fourier N M m 0 = 0) (x : ZMod N) :
∑ y : ZMod N, M x y = ∑ y : ZMod N, M 0 y- 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-th column of the 2D cyclic Fourier transform of a matrix M corresponds to the 1D discrete Fourier transform (DFT) of its row-sum function. Vanishing of this column away from m = 0 means that the DFT of the row-sum function is supported solely at frequency 0. By discrete Fourier inversion, any function whose Fourier transform is supported only at the origin is constant, so all row sums of M are equal.
Evaluating the cyclic 2D Fourier transform of M at column index 0 isolates the row sum ∑ y, M x y for each row x.
Unfolding the definition of `cyclic_matrix_fourier` at column 0 sets the second coordinate to zero, simplifying the phase exponent m * x + n * y to m * x. Factoring the exponential weight out of the inner sum over y leaves the row sum ∑ y, M x y multiplied by the exponential factor.
uses
Matrix.of_apply,one_div,zero_mul,add_zero,Finset.sum_congr,Finset.sum_mulsimp only [cyclic_matrix_fourier, Matrix.of_apply, one_div, zero_mul, add_zero] congr 1 apply Finset.sum_congr rfl intro x hx rw [Finset.sum_mul] apply Finset.sum_congr rfl intro y hy congr 1
The exponential phase factor equals the inverse of the standard additive character, establishing row_sum_eq_of_fourier_col_zero_vanish_fourier_eq.
By `ZMod.stdAddChar_apply` and `ZMod.toCircle_apply`, the character value `stdAddChar(m * x)` is exp(2π i (m * x) / N). Using `Complex.exp_neg`, the factor exp(-2π i (m * x) / N) in the Fourier transform formula is rewritten as (stdAddChar(m * x))⁻¹.
uses
ZMod.stdAddChar_apply,ZMod.toCircle_apply,Complex.exp_negrw [show (ZMod.stdAddChar (m * x)) = Complex.exp (2 * ↑Real.pi * Complex.I * (↑(m * x).val : ℂ) / ↑N) from by rw [ZMod.stdAddChar_apply, ZMod.toCircle_apply]] rw [← Complex.exp_neg] congr 1 ring_nf
The 1D discrete Fourier transform of a row-sum function r at frequency m equals ∑ x, (stdAddChar(m * x))⁻¹ * r(x).
Expanding `ZMod.dft_apply` yields ∑ x, stdAddChar(-(x * m)) • r(x). Since additive characters satisfy ψ(-a) = (ψ(a))⁻¹ via `AddChar.map_neg_eq_inv` and scalar multiplication on ℂ is standard multiplication, this matches the required character-inverse sum.
uses
ZMod.dft_apply,Finset.sum_congr,smul_eq_mul,AddChar.map_neg_eq_invrw [ZMod.dft_apply] apply Finset.sum_congr rfl intro x hx rw [smul_eq_mul, ← AddChar.map_neg_eq_inv] congr 1 ring_nf
The discrete Fourier transform of the row-sum function vanishes at every non-zero frequency m ≠ 0.
For any m ≠ 0, the assumption gives that the cyclic matrix Fourier transform vanishes at (m, 0). Rewriting this using the two helper lemmas gives (N : ℂ)⁻¹ * ZMod.dft r m = 0. Since N ≠ 0, its inverse is non-zero, so the DFT factor itself must be zero.
uses
row_sum_eq_of_fourier_col_zero_vanish_fourier_eq,row_sum_eq_of_fourier_col_zero_vanish_dft_eq,mul_eq_zero.mp,inv_ne_zero,NeZero.ne,mul_commhave hFr : ∀ m : ZMod N, m ≠ 0 → ZMod.dft (fun x => ∑ y : ZMod N, M x y) m = 0 := by intro m hm have h := hF m hm rw [row_sum_eq_of_fourier_col_zero_vanish_fourier_eq] at h rw [row_sum_eq_of_fourier_col_zero_vanish_dft_eq] rcases mul_eq_zero.mp h with h1 | h2 · exact absurd h1 (inv_ne_zero (by exact_mod_cast NeZero.ne N)) · simpa [mul_comm] using h2
Every row sum ∑ z, M y z is equal to (N : ℂ)⁻¹ * ZMod.dft r 0.
By Fourier inversion on ℤ/Nℤ (`LinearEquiv.symm_apply_apply`), the row-sum function r is reconstructed from its DFT via the inverse DFT formula (`ZMod.invDFT_apply`). In this sum over all frequencies j, every term with j ≠ 0 vanishes by the previous step. Using `Finset.sum_eq_single 0`, the sum collapses to the single term at frequency 0, where stdAddChar(0 * y) = 1.
uses
LinearEquiv.symm_apply_apply,ZMod.invDFT_apply,Finset.sum_eq_single,smul_zero,Finset.mem_univhave key : ∀ y : ZMod N, (∑ z : ZMod N, M y z) = (N : ℂ)⁻¹ * ZMod.dft (fun x => ∑ y : ZMod N, M x y) 0 := by intro y change (fun x => ∑ z : ZMod N, M x z) y = _ rw [← LinearEquiv.symm_apply_apply ZMod.dft (fun x => ∑ z : ZMod N, M x z)] rw [ZMod.invDFT_apply] rw [Finset.sum_eq_single 0] · simp · intro b _ hb; rw [hFr b hb, smul_zero] · intro h; exact absurd (Finset.mem_univ 0) h
All row sums of M are equal to the sum of the 0-th row.
Applying the identity proved in the previous step to row x and to row 0 shows that both row sums evaluate to the identical constant (N : ℂ)⁻¹ * ZMod.dft r 0.
rw [key x, key 0]
Matrix.of_apply- Evaluating a matrix constructed from a function f at indices (i, j) yields f i j.
one_div- Division of 1 by a equals the multiplicative inverse a⁻¹.
zero_mul- Multiplying zero by any element yields zero.
add_zero- Adding zero to any element leaves it unchanged.
Finset.sum_congr- Two finite sums over equal index sets are equal if their summands agree at every index.
Finset.sum_mul- Multiplication by a factor from the right distributes over a finite sum.
ZMod.stdAddChar_apply- The standard additive character on ℤ/Nℤ maps an element to its canonical image in the circle group.
ZMod.toCircle_apply- The circle group image of an element j ∈ ℤ/Nℤ is given by the complex exponential exp(2π i j / N).
Complex.exp_neg- The complex exponential of -x is the multiplicative inverse of exp(x).
ZMod.dft_apply- The discrete Fourier transform of a function Φ at frequency k is the sum over j of Φ(j) weighted by stdAddChar(-(j * k)).
smul_eq_mul- Scalar multiplication of complex numbers coincides with standard complex multiplication.
AddChar.map_neg_eq_inv- An additive character maps the negation of an element to its multiplicative inverse.
row_sum_eq_of_fourier_col_zero_vanish_fourier_eq- The 0-th column entry (m, 0) of the cyclic matrix Fourier transform of M equals N⁻¹ times the sum over rows x of the row sum times (stdAddChar(m * x))⁻¹.
row_sum_eq_of_fourier_col_zero_vanish_dft_eq- The discrete Fourier transform of a function r at frequency m is ∑ x, (stdAddChar(m * x))⁻¹ * r(x).
mul_eq_zero.mp- If a product of two numbers is zero, at least one of the factors is zero.
inv_ne_zero- The multiplicative inverse of a non-zero element is non-zero.
NeZero.ne- An element with a NeZero typeclass instance is not equal to zero.
mul_comm- Multiplication in a commutative magma satisfies a * b = b * a.
LinearEquiv.symm_apply_apply- The inverse of a linear equivalence applied to its forward image is the identity.
ZMod.invDFT_apply- The inverse discrete Fourier transform of Ψ at index k is N⁻¹ times the sum over j of Ψ(j) modulated by stdAddChar(j * k).
Finset.sum_eq_single- A finite sum over a set collapses to the single term at index a if all terms at other indices vanish.
smul_zero- Scalar multiplication of the zero vector by any scalar yields zero.
Finset.mem_univ- Every element of a finite type belongs to the universal finset univ.
- In step 5, line 50 uses `simp` to evaluate `ZMod.stdAddChar (0 * y) = 1` and convert scalar multiplication over ℂ into standard complex multiplication.
- The proof proves two private helper lemmas (`row_sum_eq_of_fourier_col_zero_vanish_fourier_eq` and `row_sum_eq_of_fourier_col_zero_vanish_dft_eq`) to bridge the explicit exponential definition of `cyclic_matrix_fourier` with Mathlib's character-based definition of `ZMod.dft`.
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.
private lemma row_sum_eq_of_fourier_col_zero_vanish_fourier_eq (N : ℕ) [NeZero N] (M : Matrix (ZMod N) (ZMod N) ℂ) (m : ZMod N) : cyclic_matrix_fourier N M m 0 = (N : ℂ)⁻¹ * ∑ x : ZMod N, (∑ y : ZMod N, M x y) * (ZMod.stdAddChar (m * x))⁻¹ := by simp only [cyclic_matrix_fourier, Matrix.of_apply, one_div, zero_mul, add_zero] congr 1 apply Finset.sum_congr rfl intro x hx rw [Finset.sum_mul] apply Finset.sum_congr rfl intro y hy congr 1 rw [show (ZMod.stdAddChar (m * x)) = Complex.exp (2 * ↑Real.pi * Complex.I * (↑(m * x).val : ℂ) / ↑N) from by rw [ZMod.stdAddChar_apply, ZMod.toCircle_apply]] rw [← Complex.exp_neg] congr 1 ring_nfprivate lemma row_sum_eq_of_fourier_col_zero_vanish_dft_eq (N : ℕ) [NeZero N] (r : ZMod N → ℂ) (m : ZMod N) : ZMod.dft r m = ∑ x : ZMod N, (ZMod.stdAddChar (m * x))⁻¹ * r x := by rw [ZMod.dft_apply] apply Finset.sum_congr rfl intro x hx rw [smul_eq_mul, ← AddChar.map_neg_eq_inv] congr 1 ring_nf/-- If the 0-th column of the cyclic Fourier transform of a matrix M vanishes away from m=0, then all row sums of M are equal (Fourier inversion implies the row-sum function is constant). -/theorem row_sum_eq_of_fourier_col_zero_vanish (N : ℕ) [NeZero N] (M : Matrix (ZMod N) (ZMod N) ℂ) (hF : ∀ m : ZMod N, m ≠ 0 → cyclic_matrix_fourier N M m 0 = 0) (x : ZMod N) : ∑ y : ZMod N, M x y = ∑ y : ZMod N, M 0 y := by have hFr : ∀ m : ZMod N, m ≠ 0 → ZMod.dft (fun x => ∑ y : ZMod N, M x y) m = 0 := by intro m hm have h := hF m hm rw [row_sum_eq_of_fourier_col_zero_vanish_fourier_eq] at h rw [row_sum_eq_of_fourier_col_zero_vanish_dft_eq] rcases mul_eq_zero.mp h with h1 | h2 · exact absurd h1 (inv_ne_zero (by exact_mod_cast NeZero.ne N)) · simpa [mul_comm] using h2 have key : ∀ y : ZMod N, (∑ z : ZMod N, M y z) = (N : ℂ)⁻¹ * ZMod.dft (fun x => ∑ y : ZMod N, M x y) 0 := by intro y change (fun x => ∑ z : ZMod N, M x z) y = _ rw [← LinearEquiv.symm_apply_apply ZMod.dft (fun x => ∑ z : ZMod N, M x z)] rw [ZMod.invDFT_apply] rw [Finset.sum_eq_single 0] · simp · intro b _ hb; rw [hFr b hb, smul_zero] · intro h; exact absurd (Finset.mem_univ 0) h rw [key x, key 0]