AFTD Auto-Formalizing Theoretical Domains

cyclic_matrix_fourier_compl_adjMatrix

theoremverified

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

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.

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

    lines 3–11

    uses mul_add, neg_add, AddChar.map_add_eq_mul

    private 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
    
  2. 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.

    lines 12–18

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

    private 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
    
  3. 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$.

    lines 19–29

    uses congrArg, AddChar.map_zero_eq_one, ZMod.injective_stdAddChar

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

    lines 30–37

    uses ZMod.card, if_neg, AddChar.sum_eq_zero_of_ne_one, cyclic_matrix_fourier_compl_adjMatrix_char_ne_one

    private 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)]
    
  5. 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)$.

    lines 38–48

    uses cyclic_matrix_fourier_compl_adjMatrix_exp_eq_stdAddChar_neg, cyclic_matrix_fourier_compl_adjMatrix_char_mem, AddChar.map_add_eq_mul, neg_add

    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]
    
  6. 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)$.

    lines 49–59

    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_mul

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

    lines 60–68

    uses cyclic_matrix_fourier_compl_adjMatrix_exp_eq_char_mul, Finset.sum_mul_sum, cyclic_matrix_fourier_compl_adjMatrix_char_sum

    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]
    
  8. 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`).

    lines 69–86

    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_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]
    
  9. 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)$.

    lines 87–97

    uses SimpleGraph.adjMatrix, SimpleGraph.compl_adj

    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]
    
  10. 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$.

    lines 98–106

    uses NeZero.ne, if_true

    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]
    
  11. 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$.

    lines 107–114

    uses NeZero.ne

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

    lines 116–133

    uses cyclic_matrix_fourier, Matrix.of_apply, cyclic_matrix_fourier_compl_adjMatrix_compl_apply

    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
  13. 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`.

    lines 134–136

    uses Finset.sum_sub_distrib, cyclic_matrix_fourier_compl_adjMatrix_sum_const, cyclic_matrix_fourier_compl_adjMatrix_sum_ident

      simp only [key, Finset.sum_sub_distrib]
      rw [cyclic_matrix_fourier_compl_adjMatrix_sum_const,
        cyclic_matrix_fourier_compl_adjMatrix_sum_ident]
  14. 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.

    lines 137–139

    uses mul_sub, cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite_mul_ite, cyclic_matrix_fourier_compl_adjMatrix_one_div_mul_ite

      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]
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$.

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

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