cyclic_matrix_fourier_compl_adjMatrix
For any simple graph G on ZMod N, the two-dimensional cyclic Fourier transform of the complement graph's adjacency matrix at (m,n) is equal to (if m = 0 and n = 0 then N else 0) - (if m + n = 0 then 1 else 0) minus the 2D cyclic Fourier transform of G's adjacency matrix at (m,n).
Statement
theorem cyclic_matrix_fourier_compl_adjMatrix (N : ℕ) [NeZero N] (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj] (m n : ZMod N) : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m n = (if m = 0 ∧ n = 0 then (N : ℂ) else 0) - (if m + n = 0 then 1 else 0) - cyclic_matrix_fourier N (G.adjMatrix ℂ) m n
- Source
- arXiv:2610.31807 Proposition 4.9 -- Additive energy and Fourier complexity of graphs
- Verified
- 29 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_and_compl_imp_antidiagonalIf G is a simple graph on ZMod N such that both G and its complement G^c have at least one edge, and the standard cyclic labeling is sharp…
Read back from the Lean
For any non-zero natural number $N$, any simple graph $G$ on the vertex set $\mathbb{Z}/N\mathbb{Z}$ with decidable adjacency, and any elements $m, n \in \mathbb{Z}/N\mathbb{Z}$, the $(m, n)$-th entry of the cyclic matrix Fourier transform of the complex adjacency matrix of the complement graph $G^c$ is equal to: $(N \text{ if } m = 0 \text{ and } n = 0 \text{ else } 0) - (1 \text{ if } m + n = 0 \text{ else } 0) - (\text{the } (m, n)\text{-th entry of the cyclic matrix Fourier transform of the complex adjacency matrix of } G)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem computes the two-dimensional cyclic Fourier transform of the complement graph's adjacency matrix by exploiting the matrix identity $A_{G^c} = J - I - A_G$, where $J$ is the all-ones matrix and $I$ is the identity matrix. By linearity of the Fourier transform, the transform of $A_{G^c}$ decomposes into the transform of $J$ minus the transform of $I$ minus the transform of $A_G$. The transform of $J$ factors into a product of two one-dimensional character sums, evaluating to $N$ when $m = n = 0$ and $0$ otherwise. The transform of $I$ collapses along the diagonal to a single character sum, evaluating to $1$ when $m + n = 0$ and $0$ otherwise. Combining these three components yields the desired formula.
Definition of the additive character $\chi_k(x) = \psi(-kx)$ on $\mathbb{Z}/N\mathbb{Z}$ and verification of the character axioms
We define $\chi_k : \mathbb{Z}/N\mathbb{Z} \to \mathbb{C}^\times$ by evaluating the standard additive character $\psi$ at $-kx$. The map preserves $0$ because $-k \cdot 0 = 0$ and $\psi(0) = 1$ (by `simp`), and preserves addition by distributing multiplication over addition (`mul_add`), distributing negation (`neg_add`), and using the multiplicativity of additive characters (`AddChar.map_add_eq_mul`). Line 10 records the definitional equality for convenience.
uses
mul_add,neg_add,AddChar.map_add_eq_mulprivate noncomputable def cyclic_matrix_fourier_compl_adjMatrix_char (N : ℕ) [NeZero N] (k : ZMod N) : AddChar (ZMod N) ℂ where toFun x := ZMod.stdAddChar (-(k * x)) map_zero_eq_one' := by simp map_add_eq_mul' x y := by rw [mul_add, neg_add, AddChar.map_add_eq_mul] private lemma cyclic_matrix_fourier_compl_adjMatrix_char_mem (N : ℕ) [NeZero N] (k x : ZMod N) : cyclic_matrix_fourier_compl_adjMatrix_char N k x = ZMod.stdAddChar (-(k * x)) := rfl
The exponential Fourier kernel coincides with the additive character evaluated at $-s$: $\exp(-2\pi i (s.val / N)) = \psi(-s)$
By definition, the standard character $\psi(s)$ embeds $s$ into the circle group as $\exp(2\pi i (s.val / N))$ via `ZMod.stdAddChar_apply` and `ZMod.toCircle_apply`. Negation in the domain inverts the character (`AddChar.map_neg_eq_inv`), which corresponds to negating the complex exponent (`Complex.exp_neg`). Ring arithmetic over $\mathbb{C}$ then shows that the exponents match.
uses
AddChar.map_neg_eq_inv,ZMod.stdAddChar_apply,ZMod.toCircle_apply,Complex.exp_negprivate lemma cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg (N : ℕ) [NeZero N] (s : ZMod N) : Complex.exp (-2 * Real.pi * Complex.I * ((s.val : ℂ) / (N : ℂ))) = ZMod.stdAddChar (-s) := by rw [AddChar.map_neg_eq_inv, ZMod.stdAddChar_apply, ZMod.toCircle_apply, ← Complex.exp_neg] congr 1 ring
For $k \neq 0$, the character $\chi_k$ is non-trivial ($\chi_k \neq 1$)
Suppose for contradiction that $\chi_k = 1$. Evaluating both sides at $1 \in \mathbb{Z}/N\mathbb{Z}$ using `congrArg` gives $\psi(-k) = 1$. Since $\psi(0) = 1$ by `AddChar.map_zero_eq_one`, the injectivity of the standard additive character (`ZMod.injective_stdAddChar`) implies $-k = 0$, so $k = 0$, directly contradicting the hypothesis $k \neq 0$.
uses
congrArg,AddChar.map_zero_eq_one,ZMod.injective_stdAddCharprivate lemma cyclic_matrix_fourier_compl_adjMatrix_char_ne_one (N : ℕ) [NeZero N] (k : ZMod N) (hk : k ≠ 0) : cyclic_matrix_fourier_compl_adjMatrix_char N k ≠ 1 := by intro h have h1 : ZMod.stdAddChar (-k) = 1 := by have := congrArg (fun f => f 1) h simpa [cyclic_matrix_fourier_compl_adjMatrix_char] using this rw [← AddChar.map_zero_eq_one (ZMod.stdAddChar (N := N))] at h1 have : (-k : ZMod N) = 0 := ZMod.injective_stdAddChar h1 simp at this exact hk this
Orthogonality of $\chi_k$: $\sum_{x \in \mathbb{Z}/N\mathbb{Z}} \chi_k(x)$ equals $N$ if $k = 0$ and $0$ if $k \neq 0$
We split into cases on whether $k = 0$. If $k = 0$, then $\chi_0(x) = 1$ identically, so summing over the $N$ elements of $\mathbb{Z}/N\mathbb{Z}$ (`ZMod.card`) yields $N$. If $k \neq 0$, then $\chi_k$ is a non-trivial additive character by `cyclic_matrix_fourier_compl_adjMatrix_char_ne_one`, and the sum of any non-trivial character over a finite abelian group vanishes by `AddChar.sum_eq_zero_of_ne_one`.
uses
ZMod.card,if_neg,AddChar.sum_eq_zero_of_ne_one,cyclic_matrix_fourier_compl_adjMatrix_char_ne_oneprivate lemma cyclic_matrix_fourier_compl_adjMatrix_char_sum (N : ℕ) [NeZero N] (k : ZMod N) : ∑ x : ZMod N, cyclic_matrix_fourier_compl_adjMatrix_char N k x = if k = 0 then (N : ℂ) else 0 := by by_cases hk : k = 0 · subst hk; simp [cyclic_matrix_fourier_compl_adjMatrix_char, ZMod.card] · rw [if_neg hk, AddChar.sum_eq_zero_of_ne_one (cyclic_matrix_fourier_compl_adjMatrix_char_ne_one N k hk)]
The two-dimensional exponential kernel factors into a product of characters: $\exp(-2\pi i (ax+by)/N) = \chi_a(x) \chi_b(y)$
We rewrite the exponential as $\psi(-(ax+by))$ using `cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg`. Distributing the negation gives $-(ax) + -(by)$ via `neg_add`, and applying the character homomorphism property (`AddChar.map_add_eq_mul`) separates the expression into $\chi_a(x) \chi_b(y)$.
uses
cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg,cyclic_matrix_fourier_compl_adjMatrix_char_mem,AddChar.map_add_eq_mul,neg_addprivate lemma cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul (N : ℕ) [NeZero N] (a b x y : ZMod N) : Complex.exp (-2 * Real.pi * Complex.I * (((a * x + b * y).val : ℂ) / (N : ℂ))) = cyclic_matrix_fourier_compl_adjMatrix_char N a x * cyclic_matrix_fourier_compl_adjMatrix_char N b y := by rw [cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg, cyclic_matrix_fourier_compl_adjMatrix_char_mem, cyclic_matrix_fourier_compl_adjMatrix_char_mem, ← AddChar.map_add_eq_mul] congr 1 rw [neg_add]
Along the diagonal $y = x$, the exponential kernel simplifies to a single character: $\exp(-2\pi i (ax+bx)/N) = \chi_{a+b}(x)$
Using the factorization from the previous lemma, the kernel on the diagonal evaluates to $\chi_a(x) \chi_b(x) = \psi(-ax)\psi(-bx) = \psi(-(ax+bx))$. By ring distributivity (`add_mul`), $-(ax + bx) = -((a+b)x)$, which matches the definition of $\chi_{a+b}(x)$.
uses
cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul,cyclic_matrix_fourier_compl_adjMatrix_char_mem,AddChar.map_add_eq_mul,neg_add,add_mulprivate lemma cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_two (N : ℕ) [NeZero N] (a b x : ZMod N) : Complex.exp (-2 * Real.pi * Complex.I * (((a * x + b * x).val : ℂ) / (N : ℂ))) = cyclic_matrix_fourier_compl_adjMatrix_char N (a + b) x := by rw [cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul, cyclic_matrix_fourier_compl_adjMatrix_char_mem, cyclic_matrix_fourier_compl_adjMatrix_char_mem, cyclic_matrix_fourier_compl_adjMatrix_char_mem, ← AddChar.map_add_eq_mul] congr 1 rw [← neg_add, add_mul]
The double sum of the Fourier kernel over all $x, y$ evaluates to $(N \text{ if } m = 0 \text{ else } 0) \times (N \text{ if } n = 0 \text{ else } 0)$
Factoring the exponential kernel into $\chi_m(x) \chi_n(y)$ enables the double sum to decouple into a product of two independent single sums $(\sum_x \chi_m(x))(\sum_y \chi_n(y))$ by `Finset.sum_mul_sum`. Applying character orthogonality (`cyclic_matrix_fourier_compl_adjMatrix_char_sum`) to each factor yields the result.
uses
cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul,Finset.sum_mul_sum,cyclic_matrix_fourier_compl_adjMatrix_char_sumprivate lemma cyclic_matrix_fourier_compl_adjMatrix_sum_const (N : ℕ) [NeZero N] (m n : ZMod N) : ∑ x : ZMod N, ∑ y : ZMod N, Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = (if m = 0 then (N : ℂ) else 0) * (if n = 0 then (N : ℂ) else 0) := by simp only [cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul] rw [← Finset.sum_mul_sum] rw [cyclic_matrix_fourier_compl_adjMatrix_char_sum, cyclic_matrix_fourier_compl_adjMatrix_char_sum]
The double sum of the Fourier kernel weighted by the identity matrix $\delta_{x,y}$ evaluates to $N$ if $m + n = 0$ and $0$ otherwise
For each fixed $x$, the inner sum over $y$ has only one nonzero term, namely when $y = x$ (`Finset.sum_eq_single`), reducing the inner sum to $\chi_{m+n}(x)$ by `cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_two`. Summing $\chi_{m+n}(x)$ over all $x \in \mathbb{Z}/N\mathbb{Z}$ gives $N$ if $m + n = 0$ and $0$ otherwise by character orthogonality (`cyclic_matrix_fourier_compl_adjMatrix_char_sum`).
uses
Finset.sum_eq_single,if_pos,one_mul,cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_two,if_neg,zero_mul,Finset.mem_univ,cyclic_matrix_fourier_compl_adjMatrix_char_sumprivate lemma cyclic_matrix_fourier_compl_adjMatrix_sum_ident (N : ℕ) [NeZero N] (m n : ZMod N) : ∑ x : ZMod N, ∑ y : ZMod N, (if x = y then (1:ℂ) else 0) * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = if m + n = 0 then (N : ℂ) else 0 := by have h : ∀ x : ZMod N, ∑ y : ZMod N, (if x = y then (1:ℂ) else 0) * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = cyclic_matrix_fourier_compl_adjMatrix_char N (m + n) x := by intro x rw [Finset.sum_eq_single x] · rw [if_pos rfl, one_mul, cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_two] · intro b _ hb rw [if_neg (fun h => hb h.symm), zero_mul] · intro hx; exact absurd (Finset.mem_univ x) hx simp only [h] rw [cyclic_matrix_fourier_compl_adjMatrix_char_sum]
The adjacency matrix of the complement graph satisfies $A_{G^c}(x, y) = 1 - \delta_{x,y} - A_G(x, y)$
We split into cases on whether $x = y$. If $x = y$, simple graphs have no self-loops, so both $A_{G^c}(x, x) = 0$ and $A_G(x, x) = 0$, satisfying $0 = 1 - 1 - 0$. If $x \neq y$, then $\delta_{x,y} = 0$, and vertices are adjacent in $G^c$ if and only if they are not adjacent in $G$ (`SimpleGraph.compl_adj`), so $A_{G^c}(x, y) = 1 - 0 - A_G(x, y)$.
uses
SimpleGraph.adjMatrix,SimpleGraph.compl_adjprivate lemma cyclic_matrix_fourier_compl_adjMatrix_compl_apply (N : ℕ) (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj] (x y : ZMod N) : SimpleGraph.adjMatrix ℂ Gᶜ x y = 1 - (if x = y then (1:ℂ) else 0) - SimpleGraph.adjMatrix ℂ G x y := by by_cases hxy : x = y · subst hxy simp [SimpleGraph.adjMatrix, SimpleGraph.compl_adj] · by_cases h : G.Adj x y · simp [SimpleGraph.adjMatrix, SimpleGraph.compl_adj, hxy, h] · simp [SimpleGraph.adjMatrix, SimpleGraph.compl_adj, hxy, h]
Scaling a conditional $N$-value by $1/N$ yields a conditional $1$-value: $\frac{1}{N} (N \text{ if } P \text{ else } 0) = (1 \text{ if } P \text{ else } 0)$
Since $N \neq 0$ (`NeZero.ne`), we case split on the proposition $P$. If $P$ holds, $\frac{1}{N} \cdot N = 1$; if $P$ is false, $\frac{1}{N} \cdot 0 = 0$.
uses
NeZero.ne,if_trueprivate lemma cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite (N : ℕ) [NeZero N] (P : Prop) [Decidable P] : (1 / (N:ℂ)) * (if P then (N:ℂ) else 0) = if P then 1 else 0 := by have hN : (N : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr (NeZero.ne N) by_cases hP : P · simp only [hP, if_true] field_simp · simp [hP]
Scaling a product of two conditional $N$-values by $1/N$ yields $N$ if both conditions hold and $0$ otherwise
Since $N \neq 0$ (`NeZero.ne`), we split on all truth value combinations of $P$ and $Q$. When both are true, $\frac{1}{N}(N \cdot N) = N$; otherwise, at least one factor is $0$, making the product $0$.
uses
NeZero.neprivate lemma cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite (N : ℕ) [NeZero N] (P Q : Prop) [Decidable P] [Decidable Q] : (1 / (N:ℂ)) * ((if P then (N:ℂ) else 0) * (if Q then (N:ℂ) else 0)) = if P ∧ Q then (N:ℂ) else 0 := by have hN : (N : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr (NeZero.ne N) by_cases hP : P <;> by_cases hQ : Q <;> simp [hP, hQ] · field_simp
Unfold the definition of the 2D cyclic Fourier transform and expand the complement graph's summand point-by-point
We unfold the definition of `cyclic_matrix_fourier` and evaluate the matrix entry via `Matrix.of_apply`. In the summand, substituting the complement formula $A_{G^c}(x, y) = 1 - \delta_{x,y} - A_G(x, y)$ (`cyclic_matrix_fourier_compl_adjMatrix_compl_apply`) and expanding algebraically with `ring` produces three terms: the pure exponential kernel, the diagonal-restricted kernel, and the original graph summand.
uses
cyclic_matrix_fourier,Matrix.of_apply,cyclic_matrix_fourier_compl_adjMatrix_compl_applytheorem cyclic_matrix_fourier_compl_adjMatrix (N : ℕ) [NeZero N] (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj] (m n : ZMod N) : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m n = (if m = 0 ∧ n = 0 then (N : ℂ) else 0) - (if m + n = 0 then 1 else 0) - cyclic_matrix_fourier N (G.adjMatrix ℂ) m n := by simp only [cyclic_matrix_fourier, Matrix.of_apply] have key : ∀ x y : ZMod N, SimpleGraph.adjMatrix ℂ Gᶜ x y * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) - (if x = y then (1:ℂ) else 0) * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) - SimpleGraph.adjMatrix ℂ G x y * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) := by intro x y rw [cyclic_matrix_fourier_compl_adjMatrix_compl_apply] ring
Distribute the double summation across the three terms and evaluate the all-ones and diagonal components
Distributing the double sum across the subtractions using `Finset.sum_sub_distrib` decomposes the expression into three double sums. The first sum (the transform of the all-ones matrix) evaluates to $(N \text{ if } m = 0 \text{ else } 0) \times (N \text{ if } n = 0 \text{ else } 0)$ by `cyclic_matrix_fourier_compl_adjMatrix_sum_const`, and the second sum (the transform of the identity matrix) evaluates to $N$ if $m + n = 0$ and $0$ otherwise by `cyclic_matrix_fourier_compl_adjMatrix_sum_ident`.
uses
Finset.sum_sub_distrib,cyclic_matrix_fourier_compl_adjMatrix_sum_const,cyclic_matrix_fourier_compl_adjMatrix_sum_identsimp only [key, Finset.sum_sub_distrib] rw [cyclic_matrix_fourier_compl_adjMatrix_sum_const, cyclic_matrix_fourier_compl_adjMatrix_sum_ident]
Distribute the normalization factor $1/N$ to obtain the final formula
Multiplying the scalar $1/N$ through the subtraction using `mul_sub`, the first term $\frac{1}{N}(N \cdot \mathbf{1}_{m=0})(N \cdot \mathbf{1}_{n=0})$ simplifies to $N \cdot \mathbf{1}_{m=0 \land n=0}$ via `cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite`. The second term $\frac{1}{N}(N \cdot \mathbf{1}_{m+n=0})$ simplifies to $\mathbf{1}_{m+n=0}$ via `cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite`. The remaining term is precisely the definition of the 2D cyclic Fourier transform of $A_G$, concluding the theorem.
uses
mul_sub,cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite,cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_iterw [mul_sub, mul_sub, cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite, cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite]
mul_add- Multiplication distributes over addition on the left: $a * (b + c) = a * b + a * c$.
neg_add- The negation of a sum is the sum of the negations: $-(a + b) = -a + -b$.
AddChar.map_add_eq_mul- An additive character turns group addition into multiplication: $\psi(x + y) = \psi(x) * \psi(y)$.
AddChar.map_neg_eq_inv- An additive character maps the group negative to the multiplicative inverse: $\psi(-a) = (\psi(a))^{-1}$.
ZMod.stdAddChar_apply- The standard additive character on $\mathbb{Z}/N\mathbb{Z}$ evaluates to the canonical embedding into the circle group: $\psi(j) = \text{toCircle}(j)$.
ZMod.toCircle_apply- The circle embedding of $j \in \mathbb{Z}/N\mathbb{Z}$ is the complex exponential $\exp(2\pi i j.val / N)$.
Complex.exp_neg- The complex exponential of a negated number is its reciprocal: $\exp(-x) = (\exp(x))^{-1}$.
congrArg- Functions respect equality: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
AddChar.map_zero_eq_one- An additive character maps the group identity $0$ to $1$: $\psi(0) = 1$.
ZMod.injective_stdAddChar- The standard additive character on $\mathbb{Z}/N\mathbb{Z}$ is an injective function.
ZMod.card- The cardinality of the finite type $\mathbb{Z}/n\mathbb{Z}$ is $n$.
if_neg- If the condition $c$ is false, the conditional expression $\text{if } c \text{ then } t \text{ else } e$ evaluates to $e$.
AddChar.sum_eq_zero_of_ne_one- The sum of any non-trivial additive character over a finite abelian group is zero: if $\psi \neq 1$, then $\sum_a \psi(a) = 0$.
cyclic_matrix_fourier_compl_adjMatrix_char_ne_one- If $k \neq 0$ in $\mathbb{Z}/N\mathbb{Z}$, then the character $\chi_k$ is not the trivial character $1$.
cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg- The exponential kernel with negative phase $\exp(-2\pi i (s.val / N))$ equals the standard additive character evaluated at $-s$.
cyclic_matrix_fourier_compl_adjMatrix_char_mem- The value of $\chi_k$ at $x$ is definitionally equal to the standard character at $-(kx)$.
add_mul- Multiplication distributes over addition on the right: $(a + b) * c = a * c + b * c$.
cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul- The 2D exponential kernel $\exp(-2\pi i (ax + by)/N)$ factors into the product of characters $\chi_a(x) * \chi_b(y)$.
Finset.sum_mul_sum- The product of two finite sums equals the double sum of their pointwise products: $(\sum_i f(i)) * (\sum_j g(j)) = \sum_i \sum_j f(i) * g(j)$.
cyclic_matrix_fourier_compl_adjMatrix_char_sum- The sum of the character $\chi_k(x)$ over all $x \in \mathbb{Z}/N\mathbb{Z}$ equals $N$ if $k = 0$ and $0$ otherwise.
Finset.sum_eq_single- A finite sum collapses to the single value $f(a)$ if every other term in the domain vanishes.
if_pos- If the condition $c$ is true, the conditional expression $\text{if } c \text{ then } t \text{ else } e$ evaluates to $t$.
one_mul- Multiplying by $1$ on the left is the identity: $1 * a = a$.
cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_two- Restricting the 2D exponential kernel to the diagonal $y = x$ gives the character $\chi_{a+b}(x)$.
zero_mul- Multiplying by $0$ on the left yields zero: $0 * a = 0$.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
SimpleGraph.adjMatrix- The adjacency matrix of a graph, whose $(u, v)$ entry is $1$ if $u \sim v$ and $0$ otherwise.
SimpleGraph.compl_adj- Two vertices are adjacent in the complement graph $G^c$ if and only if they are distinct and not adjacent in $G$.
NeZero.ne- An element of a type with a `NeZero` instance is nonzero (here, $N \neq 0$).
if_true- A conditional with condition `True` evaluates to its then branch: $\text{if True then } t \text{ else } e = t$.
cyclic_matrix_fourier- The two-dimensional cyclic Fourier transform of an $N \times N$ matrix, defined by $\frac{1}{N} \sum_{x, y} M(x, y) \exp(-2\pi i (mx+ny)/N)$.
Matrix.of_apply- Evaluating a matrix constructed from a bivariate function `Matrix.of f` at $(i, j)$ yields $f(i, j)$.
cyclic_matrix_fourier_compl_adjMatrix_compl_apply- The $(x, y)$ entry of the complement graph's adjacency matrix equals $1 - \delta_{x, y} - A_G(x, y)$.
Finset.sum_sub_distrib- The sum of term-by-term differences equals the difference of the sums: $\sum (f(x) - g(x)) = \sum f(x) - \sum g(x)$.
cyclic_matrix_fourier_compl_adjMatrix_sum_const- The double sum of the Fourier kernel over all $x, y \in \mathbb{Z}/N\mathbb{Z}$ equals $(N \text{ if } m = 0 \text{ else } 0) * (N \text{ if } n = 0 \text{ else } 0)$.
cyclic_matrix_fourier_compl_adjMatrix_sum_ident- The double sum of the Fourier kernel along the diagonal $\delta_{x,y}$ equals $N$ if $m + n = 0$ and $0$ otherwise.
mul_sub- Multiplication distributes over subtraction on the left: $a * (b - c) = a * b - a * c$.
cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite- Scaling the product of two conditionals by $1/N$ gives $\frac{1}{N}(N \cdot \mathbf{1}_P)(N \cdot \mathbf{1}_Q) = N \cdot \mathbf{1}_{P \land Q}$.
cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite- Scaling a single conditional by $1/N$ gives $\frac{1}{N}(N \cdot \mathbf{1}_P) = \mathbf{1}_P$.
- The formalization defines an auxiliary character $\chi_k(x) = \psi(-kx)$ via Mathlib's `ZMod.stdAddChar` to directly invoke character orthogonality theorems (`AddChar.sum_eq_zero_of_ne_one`).
- Because simple graphs in Mathlib have irreflexive adjacency relations ($x \not\sim x$), the diagonal of the adjacency matrix is identically zero; hence the complement graph's adjacency matrix is algebraically represented as $A_{G^c} = J - I - A_G$ where $J$ is the all-ones matrix and $I$ is the identity matrix.
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.
open scoped BigOperatorsprivate noncomputable def cyclic_matrix_fourier_compl_adjMatrix_char (N : ℕ) [NeZero N] (k : ZMod N) : AddChar (ZMod N) ℂ where toFun x := ZMod.stdAddChar (-(k * x)) map_zero_eq_one' := by simp map_add_eq_mul' x y := by rw [mul_add, neg_add, AddChar.map_add_eq_mul]private lemma cyclic_matrix_fourier_compl_adjMatrix_char_mem (N : ℕ) [NeZero N] (k x : ZMod N) : cyclic_matrix_fourier_compl_adjMatrix_char N k x = ZMod.stdAddChar (-(k * x)) := rflprivate lemma cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg (N : ℕ) [NeZero N] (s : ZMod N) : Complex.exp (-2 * Real.pi * Complex.I * ((s.val : ℂ) / (N : ℂ))) = ZMod.stdAddChar (-s) := by rw [AddChar.map_neg_eq_inv, ZMod.stdAddChar_apply, ZMod.toCircle_apply, ← Complex.exp_neg] congr 1 ringprivate lemma cyclic_matrix_fourier_compl_adjMatrix_char_ne_one (N : ℕ) [NeZero N] (k : ZMod N) (hk : k ≠ 0) : cyclic_matrix_fourier_compl_adjMatrix_char N k ≠ 1 := by intro h have h1 : ZMod.stdAddChar (-k) = 1 := by have := congrArg (fun f => f 1) h simpa [cyclic_matrix_fourier_compl_adjMatrix_char] using this rw [← AddChar.map_zero_eq_one (ZMod.stdAddChar (N := N))] at h1 have : (-k : ZMod N) = 0 := ZMod.injective_stdAddChar h1 simp at this exact hk thisprivate lemma cyclic_matrix_fourier_compl_adjMatrix_char_sum (N : ℕ) [NeZero N] (k : ZMod N) : ∑ x : ZMod N, cyclic_matrix_fourier_compl_adjMatrix_char N k x = if k = 0 then (N : ℂ) else 0 := by by_cases hk : k = 0 · subst hk; simp [cyclic_matrix_fourier_compl_adjMatrix_char, ZMod.card] · rw [if_neg hk, AddChar.sum_eq_zero_of_ne_one (cyclic_matrix_fourier_compl_adjMatrix_char_ne_one N k hk)]private lemma cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul (N : ℕ) [NeZero N] (a b x y : ZMod N) : Complex.exp (-2 * Real.pi * Complex.I * (((a * x + b * y).val : ℂ) / (N : ℂ))) = cyclic_matrix_fourier_compl_adjMatrix_char N a x * cyclic_matrix_fourier_compl_adjMatrix_char N b y := by rw [cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg, cyclic_matrix_fourier_compl_adjMatrix_char_mem, cyclic_matrix_fourier_compl_adjMatrix_char_mem, ← AddChar.map_add_eq_mul] congr 1 rw [neg_add]private lemma cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_two (N : ℕ) [NeZero N] (a b x : ZMod N) : Complex.exp (-2 * Real.pi * Complex.I * (((a * x + b * x).val : ℂ) / (N : ℂ))) = cyclic_matrix_fourier_compl_adjMatrix_char N (a + b) x := by rw [cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul, cyclic_matrix_fourier_compl_adjMatrix_char_mem, cyclic_matrix_fourier_compl_adjMatrix_char_mem, cyclic_matrix_fourier_compl_adjMatrix_char_mem, ← AddChar.map_add_eq_mul] congr 1 rw [← neg_add, add_mul]private lemma cyclic_matrix_fourier_compl_adjMatrix_sum_const (N : ℕ) [NeZero N] (m n : ZMod N) : ∑ x : ZMod N, ∑ y : ZMod N, Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = (if m = 0 then (N : ℂ) else 0) * (if n = 0 then (N : ℂ) else 0) := by simp only [cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul] rw [← Finset.sum_mul_sum] rw [cyclic_matrix_fourier_compl_adjMatrix_char_sum, cyclic_matrix_fourier_compl_adjMatrix_char_sum]private lemma cyclic_matrix_fourier_compl_adjMatrix_sum_ident (N : ℕ) [NeZero N] (m n : ZMod N) : ∑ x : ZMod N, ∑ y : ZMod N, (if x = y then (1:ℂ) else 0) * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = if m + n = 0 then (N : ℂ) else 0 := by have h : ∀ x : ZMod N, ∑ y : ZMod N, (if x = y then (1:ℂ) else 0) * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = cyclic_matrix_fourier_compl_adjMatrix_char N (m + n) x := by intro x rw [Finset.sum_eq_single x] · rw [if_pos rfl, one_mul, cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_two] · intro b _ hb rw [if_neg (fun h => hb h.symm), zero_mul] · intro hx; exact absurd (Finset.mem_univ x) hx simp only [h] rw [cyclic_matrix_fourier_compl_adjMatrix_char_sum]private lemma cyclic_matrix_fourier_compl_adjMatrix_compl_apply (N : ℕ) (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj] (x y : ZMod N) : SimpleGraph.adjMatrix ℂ Gᶜ x y = 1 - (if x = y then (1:ℂ) else 0) - SimpleGraph.adjMatrix ℂ G x y := by by_cases hxy : x = y · subst hxy simp [SimpleGraph.adjMatrix, SimpleGraph.compl_adj] · by_cases h : G.Adj x y · simp [SimpleGraph.adjMatrix, SimpleGraph.compl_adj, hxy, h] · simp [SimpleGraph.adjMatrix, SimpleGraph.compl_adj, hxy, h]private lemma cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite (N : ℕ) [NeZero N] (P : Prop) [Decidable P] : (1 / (N:ℂ)) * (if P then (N:ℂ) else 0) = if P then 1 else 0 := by have hN : (N : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr (NeZero.ne N) by_cases hP : P · simp only [hP, if_true] field_simp · simp [hP]private lemma cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite (N : ℕ) [NeZero N] (P Q : Prop) [Decidable P] [Decidable Q] : (1 / (N:ℂ)) * ((if P then (N:ℂ) else 0) * (if Q then (N:ℂ) else 0)) = if P ∧ Q then (N:ℂ) else 0 := by have hN : (N : ℂ) ≠ 0 := Nat.cast_ne_zero.mpr (NeZero.ne N) by_cases hP : P <;> by_cases hQ : Q <;> simp [hP, hQ] · field_simp/-- The 2D cyclic Fourier transform of the complement graph's adjacency matrix. -/theorem cyclic_matrix_fourier_compl_adjMatrix (N : ℕ) [NeZero N] (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj] (m n : ZMod N) : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m n = (if m = 0 ∧ n = 0 then (N : ℂ) else 0) - (if m + n = 0 then 1 else 0) - cyclic_matrix_fourier N (G.adjMatrix ℂ) m n := by simp only [cyclic_matrix_fourier, Matrix.of_apply] have key : ∀ x y : ZMod N, SimpleGraph.adjMatrix ℂ Gᶜ x y * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) = Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) - (if x = y then (1:ℂ) else 0) * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) - SimpleGraph.adjMatrix ℂ G x y * Complex.exp (-2 * Real.pi * Complex.I * (((m * x + n * y).val : ℂ) / (N : ℂ))) := by intro x y rw [cyclic_matrix_fourier_compl_adjMatrix_compl_apply] ring simp only [key, Finset.sum_sub_distrib] rw [cyclic_matrix_fourier_compl_adjMatrix_sum_const, cyclic_matrix_fourier_compl_adjMatrix_sum_ident] rw [mul_sub, mul_sub, cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite, cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite]