AFTD Auto-Formalizing Theoretical Domains

order_eight_hankel_admits_sharp_cyclic_labeling

theoremverified

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

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.

  1. 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.

    lines 4–5

    uses AddChar.inv_apply', ZMod.stdAddChar_apply, ZMod.toCircle_apply, Complex.exp_neg

      rw [AddChar.inv_apply', ZMod.stdAddChar_apply, ZMod.toCircle_apply, ← Complex.exp_neg]
      congr 1; ring
  2. 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.

    lines 9–18

    uses congrFun, congrArg, DFunLike.coe, AddChar.mulShift, AddChar.inv_apply', ZMod.injective_stdAddChar

      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)
  3. 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.

    lines 23–30

    uses cyclic_matrix_fourier, Matrix.of_apply, Finset.sum_congr, order_eight_hankel_ph_apply

      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]]
  4. 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).

    lines 31–41

    uses AddChar.map_add_eq_mul, mul_assoc, Finset.sum_congr, Fintype.sum_equiv, Equiv.addLeft

      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)
  5. 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.

    lines 42–49

    uses Finset.sum_mul, Finset.sum_congr, Finset.mul_sum

      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]
  6. 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.

    lines 50–56

    uses Finset.sum_congr, mul_comm, AddChar.sum_mulShift, order_eight_hankel_ph_primitive, sub_ne_zero.mpr

      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]]
      ring
  7. 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₂.

    lines 60–76

      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]
  8. 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.

    lines 83–98

    uses Equiv.refl, is_sharp_cyclic_labeling, Matrix.of_apply

      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]
  9. 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.

    lines 99–101

    uses order_eight_hankel_is_weighted_partial_permutation_of_diag, order_eight_hankel_fourier_eq_zero

      apply 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

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
See it in the graphDiscuss this resultChallenge it