AFTD Auto-Formalizing Theoretical Domains

sharp_cyclic_and_compl_imp_antidiagonal

theoremverified

If 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 for both G and G^c, then the two-dimensional cyclic Fourier transform of the adjacency matrix of G vanishes whenever m + n ≠ 0.

Statement

theorem sharp_cyclic_and_compl_imp_antidiagonal (N : ℕ) [NeZero N]
    (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj]
    (he : ∃ u v, G.Adj u v) (hec : ∃ u v, Gᶜ.Adj u v)
    (hG : is_sharp_cyclic_labeling N G (Equiv.refl (ZMod N)))
    (hGc : is_sharp_cyclic_labeling N Gᶜ (Equiv.refl (ZMod N)))
    (m n : ZMod N) (hmn : m + n ≠ 0) :
    cyclic_matrix_fourier N (G.adjMatrix ℂ) m n = 0
Source
arXiv:2610.31807 Proposition 4.9 -- Additive energy and Fourier complexity of graphs
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • cyclic_matrix_fourier_compl_adjMatrixFor any simple graph G on ZMod N, the two-dimensional cyclic Fourier transform of the complement graph's adjacency matrix at (m,n) is…
  • is_sharp_cyclic_labelingA bijection π from ZMod N to the vertex set of a simple graph G is a sharp cyclic labeling if the two-dimensional Fourier transform of the…
  • 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)…
  • 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…

Read back from the Lean

For any positive natural number $N$ (with $[\\text{NeZero } N]$) and any simple graph $G$ on the vertex set $\\mathbb{Z}/N\\mathbb{Z}$ with decidable adjacency: Assume: 1. $G$ has at least one edge (there exist $u, v \\in \\mathbb{Z}/N\\mathbb{Z}$ such that $G.\\text{Adj } u\\ v$). 2. The complement graph $G^c$ has at least one edge (there exist $u, v \\in \\mathbb{Z}/N\\mathbb{Z}$ such that $G^c.\\text{Adj } u\\ v$). 3. The identity labeling on $\\mathbb{Z}/N\\mathbb{Z}$ is a sharp cyclic labeling for $G$ (i.e., the cyclic Fourier transform of the adjacency matrix of $G$ is a weighted partial permutation matrix, having at most one non-zero entry in each row and each column). 4. The identity labeling on $\\mathbb{Z}/N\\mathbb{Z}$ is a sharp cyclic labeling for $G^c$ (i.e., the cyclic Fourier transform of the adjacency matrix of $G^c$ is also a weighted partial permutation matrix). Then for all $m, n \\in \\mathbb{Z}/N\\mathbb{Z}$ such that $m + n \\neq 0$, the $(m, n)$-entry of the cyclic Fourier transform of the adjacency matrix of $G$ over $\\mathbb{C}$ is $0$ (i.e., the Fourier transform matrix is supported only on the anti-diagonal $m + n = 0$).

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 proof proceeds by contradiction. If the 2D cyclic Fourier transform of the adjacency matrix of G were non-zero at (m, n) with m + n ≠ 0, then column n would be the unique non-zero entry in row m, forcing the entry at (m, -m) to vanish. Using the identity relating the Fourier transform of a graph's complement to that of the graph, the Fourier transform of Gᶜ would then be non-zero at both (m, -m) and (m, n). This gives two distinct non-zero entries in row m of the Fourier transform of Gᶜ, contradicting the assumption that Gᶜ has a sharp cyclic labeling.

  1. The 2D cyclic Fourier transform of the adjacency matrix of G is a weighted partial permutation.

    By definition, the identity labeling Equiv.refl being sharp for G means that the Fourier transform of the matrix with entries 1 on edges and 0 on non-edges is a weighted partial permutation. Simplifying Equiv.refl_apply and recognizing this matrix as SimpleGraph.adjMatrix yields the claim.

    lines 9–15

    uses Equiv.refl_apply, SimpleGraph.adjMatrix

      have hFwpp : is_weighted_partial_permutation
          (cyclic_matrix_fourier N (G.adjMatrix ℂ)) := by
        unfold is_sharp_cyclic_labeling at hG
        simp only [Equiv.refl_apply] at hG
        change is_weighted_partial_permutation
          (cyclic_matrix_fourier N (Matrix.of fun i j => if G.Adj i j then (1:ℂ) else 0)) at hG
        simpa [SimpleGraph.adjMatrix] using hG
  2. The 2D cyclic Fourier transform of the adjacency matrix of the complement graph Gᶜ is a weighted partial permutation.

    By the same unfolding and simplification applied to the sharpness hypothesis for Gᶜ, the Fourier transform of the adjacency matrix of Gᶜ is also a weighted partial permutation.

    lines 16–22

    uses Equiv.refl_apply, SimpleGraph.adjMatrix

      have hEwpp : is_weighted_partial_permutation
          (cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ)) := by
        unfold is_sharp_cyclic_labeling at hGc
        simp only [Equiv.refl_apply] at hGc
        change is_weighted_partial_permutation
          (cyclic_matrix_fourier N (Matrix.of fun i j => if Gᶜ.Adj i j then (1:ℂ) else 0)) at hGc
        simpa [SimpleGraph.adjMatrix] using hGc
  3. Each row of the Fourier transform of the adjacency matrix of G (and of Gᶜ) contains at most one non-zero entry.

    By definition of a weighted partial permutation, the first conjunct (.1) states that for any row i, if the entries at columns j₁ and j₂ are both non-zero, then j₁ = j₂. We name these row properties hFrow and hErow respectively.

    lines 23–24

      have hFrow := hFwpp.1
      have hErow := hEwpp.1
  4. Assuming for contradiction that the Fourier transform of G at (m, n) is non-zero, we have n ≠ -m.

    We assume for contradiction that the (m, n) Fourier coefficient is non-zero. If n = -m, then m + n = 0, directly contradicting the theorem hypothesis m + n ≠ 0. Therefore, n ≠ -m.

    lines 25–28

      by_contra hFmn
      have hmn' : n ≠ -m := by
        intro h
        exact hmn (by rw [h]; simp)
  5. The Fourier transform of the adjacency matrix of G at (m, -m) equals 0.

    If the (m, -m) entry were non-zero, row m would have non-zero entries at both column n and column -m. The row property hFrow would then force n = -m, contradicting n ≠ -m.

    lines 29–31

      have hF_mneg : cyclic_matrix_fourier N (G.adjMatrix ℂ) m (-m) = 0 := by
        by_contra h
        exact hmn' (hFrow m n (-m) hFmn h)
  6. The scalar D(m, -m) = (if m = 0 ∧ -m = 0 then N else 0) - (if m + -m = 0 then 1 else 0) is non-zero.

    We split into cases on whether m = 0. If m ≠ 0, the first indicator is 0 and the second is 1, yielding -1 ≠ 0. If m = 0, the expression simplifies to N - 1; if N = 1, then ℤ/Nℤ would be a subsingleton, forcing n = 0 and hence m + n = 0, contradicting m + n ≠ 0. Thus N ≠ 1 and N - 1 ≠ 0.

    lines 32–46

    uses ZMod.subsingleton_iff, Subsingleton.elim, sub_ne_zero.mpr

      have hD_mneg : ((if m = 0 ∧ -m = 0 then (N : ℂ) else 0) -
          (if m + -m = 0 then 1 else 0)) ≠ 0 := by
        by_cases hm0 : m = 0
        · subst hm0
          have hN1 : (N : ℂ) - 1 ≠ 0 := by
            have hN : (N : ℂ) ≠ 1 := by
              intro h
              have hNnat : N = 1 := by exact_mod_cast h
              have hn0 : n = 0 := by
                have : Subsingleton (ZMod N) := (ZMod.subsingleton_iff).mpr hNnat
                exact Subsingleton.elim n 0
              exact hmn (by simpa [hn0])
            exact sub_ne_zero.mpr hN
          simpa using hN1
        · simp [hm0]
  7. The Fourier transform of the adjacency matrix of Gᶜ at (m, -m) is non-zero.

    By the complement formula cyclic_matrix_fourier_compl_adjMatrix, the Fourier coefficient of Gᶜ at (m, -m) equals D(m, -m) minus the Fourier coefficient of G at (m, -m). Since the latter is 0 and D(m, -m) ≠ 0, the result is non-zero.

    lines 47–50

    uses cyclic_matrix_fourier_compl_adjMatrix

      have hFc_mneg : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m (-m) ≠ 0 := by
        rw [cyclic_matrix_fourier_compl_adjMatrix]
        rw [hF_mneg]
        simpa using hD_mneg
  8. The scalar D(m, n) = (if m = 0 ∧ n = 0 then N else 0) - (if m + n = 0 then 1 else 0) equals 0.

    Since m + n ≠ 0, both condition m + n = 0 and condition (m = 0 ∧ n = 0) are false, so both indicators vanish, leaving 0 - 0 = 0.

    lines 51–56

      have hDmn : ((if m = 0 ∧ n = 0 then (N : ℂ) else 0) -
          (if m + n = 0 then 1 else 0)) = 0 := by
        have : ¬ (m = 0 ∧ n = 0) := by
          rintro ⟨hm, hn⟩
          exact hmn (by rw [hm, hn]; simp)
        simp [this, hmn]
  9. The Fourier transform of the adjacency matrix of Gᶜ at (m, n) is non-zero.

    By the complement formula cyclic_matrix_fourier_compl_adjMatrix, the Fourier coefficient of Gᶜ at (m, n) is D(m, n) - F(G)(m, n) = -F(G)(m, n). Since F(G)(m, n) ≠ 0 by assumption, this entry is non-zero.

    lines 57–60

    uses cyclic_matrix_fourier_compl_adjMatrix

      have hFc_mn : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m n ≠ 0 := by
        rw [cyclic_matrix_fourier_compl_adjMatrix]
        rw [hDmn]
        simpa using hFmn
  10. A contradiction is reached, concluding the proof.

    Row m of the Fourier transform of Gᶜ has non-zero entries at both column n and column -m. The row property hErow implies n = -m, which contradicts n ≠ -m.

    line 61

      exact hmn' (hErow m n (-m) hFc_mn hFc_mneg)
Equiv.refl_apply
Applying the identity equivalence `Equiv.refl` to an element `x` returns `x`.
SimpleGraph.adjMatrix
The adjacency matrix of a graph, with entry 1 for adjacent vertices and 0 otherwise.
ZMod.subsingleton_iff
The ring ℤ/nℤ has at most one element if and only if n = 1.
Subsingleton.elim
In any type with at most one element (a subsingleton), any two elements are equal.
sub_ne_zero.mpr
If a ≠ b, then a - b ≠ 0.
cyclic_matrix_fourier_compl_adjMatrix
The 2D cyclic Fourier transform of the complement graph's adjacency matrix at (m, n) equals (N · [m = 0 ∧ n = 0] - [m + n = 0]) - F(G)(m, n).

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

/-- Simultaneous sharpness for G and its complement implies the 2D Fourier transform is anti-diagonal. -/theorem sharp_cyclic_and_compl_imp_antidiagonal (N : ℕ) [NeZero N]    (G : SimpleGraph (ZMod N)) [DecidableRel G.Adj]    (he : ∃ u v, G.Adj u v) (hec : ∃ u v, Gᶜ.Adj u v)    (hG : is_sharp_cyclic_labeling N G (Equiv.refl (ZMod N)))    (hGc : is_sharp_cyclic_labeling N Gᶜ (Equiv.refl (ZMod N)))    (m n : ZMod N) (hmn : m + n ≠ 0) :    cyclic_matrix_fourier N (G.adjMatrix ℂ) m n = 0 := by  have hFwpp : is_weighted_partial_permutation      (cyclic_matrix_fourier N (G.adjMatrix ℂ)) := by    unfold is_sharp_cyclic_labeling at hG    simp only [Equiv.refl_apply] at hG    change is_weighted_partial_permutation      (cyclic_matrix_fourier N (Matrix.of fun i j => if G.Adj i j then (1:ℂ) else 0)) at hG    simpa [SimpleGraph.adjMatrix] using hG  have hEwpp : is_weighted_partial_permutation      (cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ)) := by    unfold is_sharp_cyclic_labeling at hGc    simp only [Equiv.refl_apply] at hGc    change is_weighted_partial_permutation      (cyclic_matrix_fourier N (Matrix.of fun i j => if Gᶜ.Adj i j then (1:ℂ) else 0)) at hGc    simpa [SimpleGraph.adjMatrix] using hGc  have hFrow := hFwpp.1  have hErow := hEwpp.1  by_contra hFmn  have hmn' : n ≠ -m := by    intro h    exact hmn (by rw [h]; simp)  have hF_mneg : cyclic_matrix_fourier N (G.adjMatrix ℂ) m (-m) = 0 := by    by_contra h    exact hmn' (hFrow m n (-m) hFmn h)  have hD_mneg : ((if m = 0 ∧ -m = 0 then (N : ℂ) else 0) -      (if m + -m = 0 then 1 else 0)) ≠ 0 := by    by_cases hm0 : m = 0    · subst hm0      have hN1 : (N : ℂ) - 1 ≠ 0 := by        have hN : (N : ℂ) ≠ 1 := by          intro h          have hNnat : N = 1 := by exact_mod_cast h          have hn0 : n = 0 := by            have : Subsingleton (ZMod N) := (ZMod.subsingleton_iff).mpr hNnat            exact Subsingleton.elim n 0          exact hmn (by simpa [hn0])        exact sub_ne_zero.mpr hN      simpa using hN1    · simp [hm0]  have hFc_mneg : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m (-m) ≠ 0 := by    rw [cyclic_matrix_fourier_compl_adjMatrix]    rw [hF_mneg]    simpa using hD_mneg  have hDmn : ((if m = 0 ∧ n = 0 then (N : ℂ) else 0) -      (if m + n = 0 then 1 else 0)) = 0 := by    have : ¬ (m = 0 ∧ n = 0) := by      rintro ⟨hm, hn⟩      exact hmn (by rw [hm, hn]; simp)    simp [this, hmn]  have hFc_mn : cyclic_matrix_fourier N (Gᶜ.adjMatrix ℂ) m n ≠ 0 := by    rw [cyclic_matrix_fourier_compl_adjMatrix]    rw [hDmn]    simpa using hFmn  exact hmn' (hErow m n (-m) hFc_mn hFc_mneg)
See it in the graphDiscuss this resultChallenge it