AFTD Auto-Formalizing Theoretical Domains

is_sharp_cyclic_labeling

def

A 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 adjacency matrix under π is a weighted partial permutation matrix.

Statement

noncomputable def is_sharp_cyclic_labeling {V : Type*} (N : ℕ) [NeZero N]
    (G : SimpleGraph V) [DecidableRel G.Adj] (π : ZMod N ≃ V) : Prop
Defined in
arXiv:2610.31807 Definition 3.12 and Theorem 3.13
Verified
26 Oct 2026
Axioms
none listed
Built on 2
  • 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…
  • 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 5

Read back from the Lean

For a type V, a positive natural number N (NeZero N), a simple graph G on V with decidable adjacency, and an equivalence (bijection) π : ZMod N ≃ V, is_sharp_cyclic_labeling N G π is the proposition that the 2D discrete Fourier transform of the adjacency matrix of G (pulled back to ZMod N × ZMod N via π) is a weighted partial permutation matrix (meaning every row has at most one non-zero entry, and every column has at most one non-zero entry).

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

/-- A cyclic labeling π : ZMod N ≃ V is sharp for a simple graph G if the Fourier transform of its adjacency matrix is a weighted partial permutation matrix. -/
noncomputable def is_sharp_cyclic_labeling {V : Type*} (N : ℕ) [NeZero N]
    (G : SimpleGraph V) [DecidableRel G.Adj] (π : ZMod N ≃ V) : Prop := is_weighted_partial_permutation (cyclic_matrix_fourier N (Matrix.of fun x y => if G.Adj (π x) (π y) then 1 else 0))
See it in the graphDiscuss this resultChallenge it