AFTD Auto-Formalizing Theoretical Domains

cyclic_matrix_fourier

def

The 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) exp(-2πi(mx+ny)/N).

Statement

noncomputable def cyclic_matrix_fourier (N : ℕ) [NeZero N] (M : Matrix (ZMod N) (ZMod N) ℂ) :
    Matrix (ZMod N) (ZMod N) ℂ
Defined in
arXiv:2610.31807 Section 3, Equation (3.1)
Verified
26 Oct 2026
Axioms
none listed
Used by 9

Read back from the Lean

For a natural number $N$ satisfying $N \neq 0$ (via [NeZero N]) and a matrix $M$ with rows and columns indexed by $\mathbb{Z}/N\mathbb{Z}$ and entries in $\mathbb{C}$, cyclic_matrix_fourier N M is defined as the $(\mathbb{Z}/N\mathbb{Z}) \times (\mathbb{Z}/N\mathbb{Z})$ matrix over $\mathbb{C}$ whose entry at row $m$ and column $n$ is $$\frac{1}{N} \sum_{x \in \mathbb{Z}/N\mathbb{Z}} \sum_{y \in \mathbb{Z}/N\mathbb{Z}} M_{x, y} \exp\left( -2 \pi i \frac{(m x + n y)\mathrm{.val}}{N} \right),$$ where $m x + n y$ is computed in the ring $\mathbb{Z}/N\mathbb{Z}$ and then converted via .val to a natural number in $\{0, \dots, N-1\}$ before being coerced to $\mathbb{C}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Two-dimensional unitary Fourier transform of a matrix on ZMod N x ZMod N. -/
noncomputable def cyclic_matrix_fourier (N : ℕ) [NeZero N] (M : Matrix (ZMod N) (ZMod N) ℂ) :
    Matrix (ZMod N) (ZMod N) ℂ := Matrix.of fun m n => (1 / (N : ℂ)) * ∑ x : ZMod N, ∑ y : ZMod N,
    M x y * Complex.exp (-2 * Real.pi * Complex.I * ((m * x + n * y).val / (N : ℂ)))
See it in the graphDiscuss this resultChallenge it