AFTD Auto-Formalizing Theoretical Domains

row_sum_eq_of_fourier_col_zero_vanish

theoremverified

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.

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

    lines 5–12

    uses Matrix.of_apply, one_div, zero_mul, add_zero, Finset.sum_congr, Finset.sum_mul

      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
  2. 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))⁻¹.

    lines 13–18

    uses ZMod.stdAddChar_apply, ZMod.toCircle_apply, Complex.exp_neg

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

    lines 23–28

    uses ZMod.dft_apply, Finset.sum_congr, smul_eq_mul, AddChar.map_neg_eq_inv

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

    lines 35–42

    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_comm

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

    lines 43–52

    uses LinearEquiv.symm_apply_apply, ZMod.invDFT_apply, Finset.sum_eq_single, smul_zero, Finset.mem_univ

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

    line 53

      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.

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

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