order_eight_hankel_admits_sharp_cyclic_labeling
Any simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} admits a sharp cyclic labeling.
Statement
theorem order_eight_hankel_admits_sharp_cyclic_labeling
(G : SimpleGraph (ZMod 8)) [DecidableRel G.Adj]
(hG : ∀ x y : ZMod 8, G.Adj x y ↔ (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5) :
admits_sharp_cyclic_labeling 8 G- Source
- step towards exists_non_circulant_sharp_cyclic_graph_order_eight
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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…
- Used by 1
- exists_non_circulant_sharp_cyclic_graph_order_eightThere exists a simple graph G on ZMod 8 with at least one edge that admits a sharp cyclic labeling and is not a circulant graph on ZMod 8.
The proof, explained
To prove that the given graph on ZMod 8 admits a sharp cyclic labeling, we choose the identity permutation as the labeling. Under this labeling, the adjacency matrix is a Hankel matrix whose (x, y) entry depends only on the sum x + y. The key move is that the 2D cyclic Fourier transform of any Hankel matrix is diagonal: by splitting the exponent mx + ny = n(x + y) + (m - n)x, the double sum factors, and character orthogonality forces the sum over the difference frequency m - n to vanish whenever m ≠ n. Since any diagonal matrix is a weighted partial permutation, the Fourier transform satisfies the sharp cyclic labeling condition.
The inverse standard additive character on ZMod N evaluates at a to exp(-2πi (a.val / N)).
We rewrite the inverse character as the reciprocal of the standard character, expand the standard character using the circle map toCircle(a) = exp(2πi (a.val / N)), and apply exp(-z) = (exp z)⁻¹ along with exponent ring arithmetic.
uses
AddChar.inv_apply',ZMod.stdAddChar_apply,ZMod.toCircle_apply,Complex.exp_negrw [AddChar.inv_apply', ZMod.stdAddChar_apply, ZMod.toCircle_apply, ← Complex.exp_neg] congr 1; ring
The inverse standard additive character on ZMod N is primitive.
Assume for contradiction that some non-zero a ∈ ZMod N satisfies that the shifted character x ↦ χ⁻¹(ax) is the trivial character 1. Evaluating at x = 1 yields χ⁻¹(a) = 1, and taking inverses gives χ(a) = 1. Since χ(0) = 1 and the standard additive character χ is injective, this implies a = 0, contradicting a ≠ 0.
uses
congrFun,congrArg,DFunLike.coe,AddChar.mulShift,AddChar.inv_apply',ZMod.injective_stdAddCharintro a ha h have h1 : ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) a = 1 := by have := congrFun (congrArg DFunLike.coe h) 1 simpa [AddChar.mulShift] using this rw [AddChar.inv_apply'] at h1 have h2 : ZMod.stdAddChar (N := N) a = 1 := by have := congrArg (fun z => z⁻¹) h1; simpa using this have h0 : ZMod.stdAddChar (N := N) 0 = 1 := by simp rw [← h0] at h2 exact ha (ZMod.injective_stdAddChar h2)
The (m, n) entry of the cyclic Fourier transform of the Hankel matrix (x, y) ↦ φ(x + y) equals (1/N) ∑_x ∑_y φ(x + y) χ⁻¹(mx + ny).
Unfolding the definition of cyclic_matrix_fourier and evaluating the matrix entry gives the exponential sum (1/N) ∑_{x, y} φ(x + y) exp(-2πi ((mx + ny).val / N)), which rewrites into the inverse standard additive character χ⁻¹(mx + ny) via order_eight_hankel_ph_apply.
uses
cyclic_matrix_fourier,Matrix.of_apply,Finset.sum_congr,order_eight_hankel_ph_applyrw [show cyclic_matrix_fourier N (Matrix.of fun x y => φ (x + y)) m n = 1 / (N:ℂ) * ∑ x, ∑ y, φ (x + y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (m*x + n*y) from by simp only [cyclic_matrix_fourier, Matrix.of_apply] congr 1 apply Finset.sum_congr rfl; intro x _ apply Finset.sum_congr rfl; intro y _ rw [order_eight_hankel_ph_apply]]
For each x, the inner sum over y simplifies to ∑_t φ(t) χ⁻¹(nt), which is independent of x.
We write the phase linear form as mx + ny = n(x + y) + (m - n)x. Using character multiplicativity, the summand factors into (φ(x + y) χ⁻¹(n(x + y))) · χ⁻¹((m - n)x). Reindexing the inner sum over y via the group translation y ↦ x + y (using Equiv.addLeft x) turns the first factor's sum into ∑_t φ(t) χ⁻¹(nt).
uses
AddChar.map_add_eq_mul,mul_assoc,Finset.sum_congr,Fintype.sum_equiv,Equiv.addLefthave hsplit : ∀ x y : ZMod N, m*x + n*y = n*(x+y) + (m-n)*x := by intro x y; ring have hfac : ∀ x y : ZMod N, φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (m*x+n*y) = (φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*(x+y))) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x) := by intro x y; rw [hsplit x y, AddChar.map_add_eq_mul, mul_assoc] rw [Finset.sum_congr rfl (fun x _ => Finset.sum_congr rfl (fun y _ => hfac x y))] have hchange : ∀ x : ZMod N, ∑ y, (φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*(x+y))) = ∑ t, φ t * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*t) := by intro x exact Fintype.sum_equiv (Equiv.addLeft x) _ _ (fun y => by simp)
The double sum factors into the product of the sum over t and the character sum over x.
Since the sum over t no longer depends on x, we factor it out of the sum over y using Finset.sum_mul, and then pull it entirely outside the outer sum over x using Finset.mul_sum.
uses
Finset.sum_mul,Finset.sum_congr,Finset.mul_sumhave step : ∀ x : ZMod N, (∑ y, (φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*(x+y))) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x)) = (∑ t, φ t * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*t)) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x) := by intro x; rw [← Finset.sum_mul]; rw [hchange x] rw [Finset.sum_congr rfl (fun x _ => step x)] rw [← Finset.mul_sum]
When m ≠ n, the character sum over x vanishes, so the Fourier transform entry is zero.
Since m ≠ n, the frequency difference m - n is non-zero. By character orthogonality for the primitive character χ⁻¹ (AddChar.sum_mulShift), the sum ∑_x χ⁻¹(x(m - n)) is zero. Multiplying by zero gives 0.
uses
Finset.sum_congr,mul_comm,AddChar.sum_mulShift,order_eight_hankel_ph_primitive,sub_ne_zero.mprrw [show (∑ x, ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x)) = 0 from by rw [show (∑ x : ZMod N, ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x)) = ∑ x, ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (x*(m-n)) from by apply Finset.sum_congr rfl; intro x _; rw [mul_comm]] rw [AddChar.sum_mulShift (m-n) (order_eight_hankel_ph_primitive N)] simp [sub_ne_zero.mpr hmn]] ring
Any matrix that vanishes off the diagonal is a weighted partial permutation.
A matrix is a weighted partial permutation if every row and every column contains at most one non-zero entry. For row i, if entries at j₁ and j₂ are non-zero, vanishing off the diagonal implies j₁ = i and j₂ = i, so j₁ = j₂. Symmetrically, for column j, if entries at i₁ and i₂ are non-zero, then i₁ = j and i₂ = j, so i₁ = i₂.
constructor · intro i j₁ j₂ hj₁ hj₂ have h1 : i = j₁ := by by_contra hc exact hj₁ (h i j₁ hc) have h2 : i = j₂ := by by_contra hc exact hj₂ (h i j₂ hc) rw [← h1, ← h2] · intro j i₁ i₂ hi₁ hi₂ have h1 : i₁ = j := by by_contra hc exact hi₁ (h i₁ j hc) have h2 : i₂ = j := by by_contra hc exact hi₂ (h i₂ j hc) rw [h1, h2]
Under the identity permutation, the relabeled adjacency matrix of G is the Hankel matrix (x, y) ↦ φ(x + y), where φ(s) = 1 if s.val ∈ {1, 3, 5} and 0 otherwise.
We witness the existential in admits_sharp_cyclic_labeling with the identity permutation Equiv.refl (ZMod 8). By definition, the relabeled adjacency matrix has entry (x, y) equal to 1 if G.Adj x y and 0 otherwise. By the hypothesis hG, G.Adj x y ↔ (x + y).val ∈ {1, 3, 5}, so entry (x, y) matches φ(x + y) identically.
uses
Equiv.refl,is_sharp_cyclic_labeling,Matrix.of_applyuse Equiv.refl (ZMod 8) rw [is_sharp_cyclic_labeling] let φ : ZMod 8 → ℂ := fun s => if s.val = 1 ∨ s.val = 3 ∨ s.val = 5 then 1 else 0 have hM : (Matrix.of fun x y => if G.Adj ((Equiv.refl (ZMod 8)) x) ((Equiv.refl (ZMod 8)) y) then (1 : ℂ) else 0) = (Matrix.of fun x y => φ (x + y)) := by ext x y simp only [Matrix.of_apply] change (if G.Adj x y then (1 : ℂ) else 0) = φ (x + y) have h_iff := hG x y dsimp [φ] split_ifs with h1 h2 h3 · rfl · exfalso; exact h2 (h_iff.mp h1) · exfalso; exact h1 (h_iff.mpr h3) · rfl rw [hM]
The cyclic Fourier transform of the adjacency matrix is a weighted partial permutation, so G admits a sharp cyclic labeling.
By order_eight_hankel_is_weighted_partial_permutation_of_diag, it suffices to show that the cyclic Fourier transform is zero off the diagonal (i ≠ j). For any Hankel matrix (x, y) ↦ φ(x + y), this was established by order_eight_hankel_fourier_eq_zero.
uses
order_eight_hankel_is_weighted_partial_permutation_of_diag,order_eight_hankel_fourier_eq_zeroapply order_eight_hankel_is_weighted_partial_permutation_of_diag intro i j hij exact order_eight_hankel_fourier_eq_zero φ hij
AddChar.inv_apply'- The inverse character ψ⁻¹ evaluated at a equals (ψ(a))⁻¹.
ZMod.stdAddChar_apply- The standard additive character evaluated at j equals the coercion to ℂ of the circle map toCircle(j).
ZMod.toCircle_apply- The circle map at j ∈ ZMod N equals exp(2πi (j.val / N)).
Complex.exp_neg- For any complex number x, exp(-x) = (exp x)⁻¹.
congrFun- Equal functions take equal values at any argument.
congrArg- A function applied to equal arguments gives equal values.
DFunLike.coe- Coercion of a bundled map or character to an underlying function.
AddChar.mulShift- The multiplicative shift of an additive character ψ by a is the character x ↦ ψ(ax).
ZMod.injective_stdAddChar- The standard additive character on ZMod N is injective.
cyclic_matrix_fourier- The cyclic Fourier transform of an N × N matrix M, whose (m, n) entry is (1/N) ∑_{x,y} M_{x,y} exp(-2πi (mx + ny)/N).
Matrix.of_apply- Evaluating the matrix formed from a function f at indices (i, j) yields f(i, j).
Finset.sum_congr- Sums over identical finite index sets are equal if their summands agree at every element.
order_eight_hankel_ph_apply- The inverse of the standard additive character on ZMod N evaluates at a to exp(-2πi (a.val / N)).
AddChar.map_add_eq_mul- An additive character maps addition to multiplication: ψ(x + y) = ψ(x) ψ(y).
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
Fintype.sum_equiv- A sum over a finite domain can be reindexed by an equivalence without changing its value.
Equiv.addLeft- Left translation y ↦ x + y in an additive group is a bijection (permutation).
Finset.sum_mul- Right multiplication distributes over a finite sum: (∑ f_i) * a = ∑ (f_i * a).
Finset.mul_sum- Left multiplication distributes over a finite sum: a * (∑ f_i) = ∑ (a * f_i).
mul_comm- Multiplication is commutative: a * b = b * a.
AddChar.sum_mulShift- The sum of a primitive additive character shifted by b equals the cardinality of the ring if b = 0, and vanishes otherwise.
order_eight_hankel_ph_primitive- The inverse of the standard additive character on ZMod N is a primitive character.
sub_ne_zero.mpr- If a ≠ b, then a - b ≠ 0.
Equiv.refl- The identity equivalence of a type with itself.
is_sharp_cyclic_labeling- A permutation π is a sharp cyclic labeling if the cyclic Fourier transform of the relabeled adjacency matrix is a weighted partial permutation.
order_eight_hankel_is_weighted_partial_permutation_of_diag- A matrix with zero entries off the main diagonal is a weighted partial permutation.
order_eight_hankel_fourier_eq_zero- The cyclic Fourier transform of a Hankel matrix (x, y) ↦ φ(x + y) vanishes off the diagonal (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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
private lemma order_eight_hankel_ph_apply {N : ℕ} [NeZero N] (a : ZMod N) : ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) a = Complex.exp (-2 * ↑Real.pi * Complex.I * (↑a.val / ↑N)) := by rw [AddChar.inv_apply', ZMod.stdAddChar_apply, ZMod.toCircle_apply, ← Complex.exp_neg] congr 1; ringprivate lemma order_eight_hankel_ph_primitive (N : ℕ) [NeZero N] : ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹).IsPrimitive := by intro a ha h have h1 : ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) a = 1 := by have := congrFun (congrArg DFunLike.coe h) 1 simpa [AddChar.mulShift] using this rw [AddChar.inv_apply'] at h1 have h2 : ZMod.stdAddChar (N := N) a = 1 := by have := congrArg (fun z => z⁻¹) h1; simpa using this have h0 : ZMod.stdAddChar (N := N) 0 = 1 := by simp rw [← h0] at h2 exact ha (ZMod.injective_stdAddChar h2)private lemma order_eight_hankel_fourier_eq_zero {N : ℕ} [NeZero N] (φ : ZMod N → ℂ) {m n : ZMod N} (hmn : m ≠ n) : cyclic_matrix_fourier N (Matrix.of fun x y => φ (x + y)) m n = 0 := by rw [show cyclic_matrix_fourier N (Matrix.of fun x y => φ (x + y)) m n = 1 / (N:ℂ) * ∑ x, ∑ y, φ (x + y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (m*x + n*y) from by simp only [cyclic_matrix_fourier, Matrix.of_apply] congr 1 apply Finset.sum_congr rfl; intro x _ apply Finset.sum_congr rfl; intro y _ rw [order_eight_hankel_ph_apply]] have hsplit : ∀ x y : ZMod N, m*x + n*y = n*(x+y) + (m-n)*x := by intro x y; ring have hfac : ∀ x y : ZMod N, φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (m*x+n*y) = (φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*(x+y))) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x) := by intro x y; rw [hsplit x y, AddChar.map_add_eq_mul, mul_assoc] rw [Finset.sum_congr rfl (fun x _ => Finset.sum_congr rfl (fun y _ => hfac x y))] have hchange : ∀ x : ZMod N, ∑ y, (φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*(x+y))) = ∑ t, φ t * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*t) := by intro x exact Fintype.sum_equiv (Equiv.addLeft x) _ _ (fun y => by simp) have step : ∀ x : ZMod N, (∑ y, (φ (x+y) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*(x+y))) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x)) = (∑ t, φ t * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (n*t)) * ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x) := by intro x; rw [← Finset.sum_mul]; rw [hchange x] rw [Finset.sum_congr rfl (fun x _ => step x)] rw [← Finset.mul_sum] rw [show (∑ x, ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x)) = 0 from by rw [show (∑ x : ZMod N, ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) ((m-n)*x)) = ∑ x, ((ZMod.stdAddChar : AddChar (ZMod N) ℂ)⁻¹) (x*(m-n)) from by apply Finset.sum_congr rfl; intro x _; rw [mul_comm]] rw [AddChar.sum_mulShift (m-n) (order_eight_hankel_ph_primitive N)] simp [sub_ne_zero.mpr hmn]] ringprivate lemma order_eight_hankel_is_weighted_partial_permutation_of_diag {n : Type*} (M : Matrix n n ℂ) (h : ∀ i j, i ≠ j → M i j = 0) : is_weighted_partial_permutation M := by constructor · intro i j₁ j₂ hj₁ hj₂ have h1 : i = j₁ := by by_contra hc exact hj₁ (h i j₁ hc) have h2 : i = j₂ := by by_contra hc exact hj₂ (h i j₂ hc) rw [← h1, ← h2] · intro j i₁ i₂ hi₁ hi₂ have h1 : i₁ = j := by by_contra hc exact hi₁ (h i₁ j hc) have h2 : i₂ = j := by by_contra hc exact hi₂ (h i₂ j hc) rw [h1, h2]/-- Any simple graph on ZMod 8 whose adjacency is given by (x + y).val ∈ {1, 3, 5} admits a sharp cyclic labeling. -/theorem order_eight_hankel_admits_sharp_cyclic_labeling (G : SimpleGraph (ZMod 8)) [DecidableRel G.Adj] (hG : ∀ x y : ZMod 8, G.Adj x y ↔ (x + y).val = 1 ∨ (x + y).val = 3 ∨ (x + y).val = 5) : admits_sharp_cyclic_labeling 8 G := by use Equiv.refl (ZMod 8) rw [is_sharp_cyclic_labeling] let φ : ZMod 8 → ℂ := fun s => if s.val = 1 ∨ s.val = 3 ∨ s.val = 5 then 1 else 0 have hM : (Matrix.of fun x y => if G.Adj ((Equiv.refl (ZMod 8)) x) ((Equiv.refl (ZMod 8)) y) then (1 : ℂ) else 0) = (Matrix.of fun x y => φ (x + y)) := by ext x y simp only [Matrix.of_apply] change (if G.Adj x y then (1 : ℂ) else 0) = φ (x + y) have h_iff := hG x y dsimp [φ] split_ifs with h1 h2 h3 · rfl · exfalso; exact h2 (h_iff.mp h1) · exfalso; exact h1 (h_iff.mpr h3) · rfl rw [hM] apply order_eight_hankel_is_weighted_partial_permutation_of_diag intro i j hij exact order_eight_hankel_fourier_eq_zero φ hij