AFTD Auto-Formalizing Theoretical Domains

cyclic_fourier_col_zero_eq_zero_of_sharp

theoremverified

For any weighted partial permutation matrix whose (0,0) entry is non-zero, every other entry (m,0) in the 0-th column is zero.

Statement

theorem cyclic_fourier_col_zero_eq_zero_of_sharp (N : ℕ) [NeZero N]
    (M : Matrix (ZMod N) (ZMod N) ℂ) (hs : is_weighted_partial_permutation (cyclic_matrix_fourier N M))
    (h0 : cyclic_matrix_fourier N M 0 0 ≠ 0) (m : ZMod N) (hm : m ≠ 0) :
    cyclic_matrix_fourier N M m 0 = 0
Source
step towards sharp_cyclic_graph_is_regular
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • 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 result is proved by contradiction. By definition, each column of a weighted partial permutation matrix contains at most one non-zero entry. Assuming for contradiction that the $(m, 0)$ entry is non-zero alongside the non-zero $(0, 0)$ entry forces their row indices to coincide, giving $m = 0$ and contradicting the hypothesis $m \neq 0$.

  1. The entry of the Fourier transform matrix at $(m, 0)$ is zero.

    We argue by contradiction: suppose that the $(m, 0)$ entry is non-zero. By definition, a weighted partial permutation matrix has at most one non-zero entry in each column (`hs.2`). Because both $(0, 0)$ and $(m, 0)$ belong to column $0$ and are non-zero, their row indices must coincide, giving $0 = m$ and hence $m = 0$. This directly contradicts the hypothesis that $m \neq 0$ (`hm`).

    lines 6–7

      by_contra h
      exact hm (hs.2 0 0 m h0 h).symm

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

/-- If the 2D Fourier transform is a weighted partial permutation matrix and entry (0,0) is nonzero, then all other entries (m,0) with m ≠ 0 in the 0-th column must vanish. -/theorem cyclic_fourier_col_zero_eq_zero_of_sharp (N : ℕ) [NeZero N]    (M : Matrix (ZMod N) (ZMod N) ℂ) (hs : is_weighted_partial_permutation (cyclic_matrix_fourier N M))    (h0 : cyclic_matrix_fourier N M 0 0 ≠ 0) (m : ZMod N) (hm : m ≠ 0) :    cyclic_matrix_fourier N M m 0 = 0 := by  by_contra h  exact hm (hs.2 0 0 m h0 h).symm
See it in the graphDiscuss this resultChallenge it