AFTD Auto-Formalizing Theoretical Domains

cyclic_matrix_fourier_zero_zero_ne_zero

theoremverified

For any finite graph G with at least one edge and any bijection π : ZMod N ≃ V, the (0,0) entry of the cyclic 2D Fourier transform of the adjacency matrix is nonzero.

Statement

theorem cyclic_matrix_fourier_zero_zero_ne_zero {V : Type*} [Fintype V] (N : ℕ) [NeZero N]
    (G : SimpleGraph V) [DecidableRel G.Adj] (π : ZMod N ≃ V) (he : ∃ u v, G.Adj u v) :
    cyclic_matrix_fourier N (Matrix.of fun x y => if G.Adj (π x) (π y) then (1 : ℂ) else 0) 0 0 ≠ 0
Source
step towards sharp_cyclic_graph_is_regular
Verified
27 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_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 (0,0) entry of the cyclic 2D Fourier transform evaluates to (1/N) times the total sum of vertex degrees in G, because the phase factors exp(0) equal 1. Since N is nonzero, this entry vanishes only if the sum of degrees is zero. However, an edge u ~ v guarantees that u has degree at least 1, which provides a strictly positive lower bound on the sum of non-negative degrees and yields a contradiction.

  1. It suffices to show that the sum of vertex degrees is nonzero in ℂ.

    Unfolding the cyclic Fourier transform at indices $(0, 0)$, the phase factor simplifies to $\exp(0) = 1$. The sum over the indicator of $G.\mathrm{Adj}(\pi(x), \pi(y))$ simplifies to the cardinality of the neighbor set of $\pi(x)$. Because $N \neq 0$ (via `NeZero.ne`), the scalar factor $1/N$ is nonzero, so the transform entry is nonzero if and only if the sum of all vertex degrees is nonzero.

    lines 5–7

    uses NeZero.ne

      unfold cyclic_matrix_fourier
      simp
      refine ⟨NeZero.ne N, ?_⟩
  2. Assume for contradiction that the sum of degrees is zero in ℕ, and fix an edge in G.

    Assuming for contradiction that the sum of degrees is zero in ℂ, we push the coercion inside the sum using `Nat.cast_sum` and reflect it to ℕ using `Nat.cast_eq_zero`. We also unpack the hypothesis `he` to obtain two adjacent vertices $u, v \in V$.

    lines 8–10

    uses Nat.cast_sum, Nat.cast_eq_zero

      intro h
      rw [← Nat.cast_sum, Nat.cast_eq_zero] at h
      rcases he with ⟨u, v, huv⟩
  3. The vertex u has strictly positive degree.

    To show that the neighbor set of $\pi^{-1}(u)$ has cardinality strictly greater than 0, it suffices by `Finset.card_pos` to show it is nonempty. The preimage $\pi^{-1}(v)$ serves as a witness: it belongs to the universal set (`Finset.mem_univ`) and its image $v = \pi(\pi^{-1}(v))$ is adjacent to $u = \pi(\pi^{-1}(u))$ by the edge hypothesis (`Finset.mem_filter`).

    lines 11–16

    uses Finset.card_pos, Finset.mem_filter, Finset.mem_univ

      have hpos_card : 0 < (Finset.filter (fun y => G.Adj (π (π.symm u)) (π y)) Finset.univ).card := by
        rw [Finset.card_pos]
        refine ⟨π.symm v, ?_⟩
        rw [Finset.mem_filter]
        refine ⟨Finset.mem_univ _, ?_⟩
        simpa using huv
  4. The degree of u is bounded above by the total sum of degrees.

    Because every degree is non-negative (`Nat.zero_le`), any single term in the sum—namely the term for $\pi^{-1}(u) \in \text{Finset.univ}$—is bounded above by the total sum over all vertices (`Finset.single_le_sum`).

    lines 17–18

    uses Finset.single_le_sum, Nat.zero_le, Finset.mem_univ

      have hle := Finset.single_le_sum (f := fun x => (Finset.filter (fun y => G.Adj (π x) (π y)) Finset.univ).card)
        (fun _ _ => Nat.zero_le _) (Finset.mem_univ (π.symm u))
  5. Contradiction. automation

    We have $0 < \operatorname{deg}(u) \le \sum_x \operatorname{deg}(\pi(x)) = 0$, which is impossible. Linear integer arithmetic (`omega`) closes the goal.

    line 19

      omega
NeZero.ne
An element with a `NeZero` instance is nonzero.
Nat.cast_sum
The coercion of a finite sum of natural numbers into an additive structure with one equals the sum of the coerced terms.
Nat.cast_eq_zero
In a ring of characteristic zero, the coercion of a natural number is zero if and only if the number is zero.
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.mem_filter
An element belongs to a filtered finset if and only if it is in the original finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.single_le_sum
A single term in a finite sum of non-negative elements in an ordered monoid is bounded above by the total sum.
Nat.zero_le
Every natural number is greater than or equal to zero.

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 G has at least one edge, the (0,0) entry of its cyclic Fourier transform under any bijection π is nonzero, because it is (1/N) times the positive sum of non-negative adjacency indicators. -/theorem cyclic_matrix_fourier_zero_zero_ne_zero {V : Type*} [Fintype V] (N : ℕ) [NeZero N]    (G : SimpleGraph V) [DecidableRel G.Adj] (π : ZMod N ≃ V) (he : ∃ u v, G.Adj u v) :    cyclic_matrix_fourier N (Matrix.of fun x y => if G.Adj (π x) (π y) then (1 : ℂ) else 0) 0 0 ≠ 0 := by  unfold cyclic_matrix_fourier  simp  refine ⟨NeZero.ne N, ?_⟩  intro h  rw [← Nat.cast_sum, Nat.cast_eq_zero] at h  rcases he with ⟨u, v, huv⟩  have hpos_card : 0 < (Finset.filter (fun y => G.Adj (π (π.symm u)) (π y)) Finset.univ).card := by    rw [Finset.card_pos]    refine ⟨π.symm v, ?_⟩    rw [Finset.mem_filter]    refine ⟨Finset.mem_univ _, ?_⟩    simpa using huv  have hle := Finset.single_le_sum (f := fun x => (Finset.filter (fun y => G.Adj (π x) (π y)) Finset.univ).card)    (fun _ _ => Nat.zero_le _) (Finset.mem_univ (π.symm u))  omega
See it in the graphDiscuss this resultChallenge it