is_sharp_cyclic_labeling
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
- order_eight_hankel_admits_sharp_cyclic_labelingAny simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} admits a sharp cyclic labeling.
- admits_sharp_cyclic_labelingA simple graph G on N vertices admits a sharp cyclic labeling if there exists a bijection π from ZMod N to V(G) such that…
- circulant_graph_admits_sharp_cyclic_labelingFor every N ≥ 1 and every subset s of ZMod N, if the circulant graph SimpleGraph.circulantGraph s has at least one edge, then it admits a…
- 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.
- 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 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))