AFTD Auto-Formalizing Theoretical Domains

circulant_graph_admits_sharp_cyclic_labeling

theoremverifiedformalization

For 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 labeling on ZMod N.

Statement

theorem circulant_graph_admits_sharp_cyclic_labeling (N : ℕ) [NeZero N]
    (s : Set (ZMod N)) [DecidablePred (· ∈ s)]
    (he : ∃ u v, (SimpleGraph.circulantGraph s).Adj u v) :
    admits_sharp_cyclic_labeling N (SimpleGraph.circulantGraph s)
Formalizes
arXiv:2610.31807 Theorem 4.6 and Proposition 8.3
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…

Read back from the Lean

Let $N$ be a non-zero natural number ([NeZero N]), and let $s \subseteq \mathbb{Z}/N\mathbb{Z}$ be a subset with decidable membership ([DecidablePred (· ∈ s)]). Assume that the circulant graph SimpleGraph.circulantGraph s has at least one edge (there exist vertices $u, v \in \mathbb{Z}/N\mathbb{Z}$ that are adjacent). Then SimpleGraph.circulantGraph s admits a sharp cyclic labeling: that is, there exists a bijection $\pi : \mathbb{Z}/N\mathbb{Z} \simeq \mathbb{Z}/N\mathbb{Z}$ such that the 2D discrete Fourier transform of the $\pi$-permuted adjacency matrix of the graph is a weighted partial permutation (has at most one non-zero entry in each row and at most one non-zero entry in each column).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof demonstrates that any circulant graph on ZMod N admits a sharp cyclic labeling by choosing the identity permutation as the labeling. Under this permutation, the graph's adjacency matrix is circulant, meaning each entry (x, y) depends solely on the difference x - y. Character orthogonality on ZMod N ensures that the two-dimensional cyclic Fourier transform of any circulant matrix vanishes off the anti-diagonal (where m + n ≠ 0). Consequently, each row and each column of the Fourier matrix contains at most one non-zero entry, satisfying the weighted partial permutation condition.

  1. The inverse standard additive character on ZMod N is given explicitly by a ↦ exp(-2πi a.val / N).

    Unfolding the definition of the inverse character as pointwise inversion, the standard character evaluates to exp(2πi a.val / N). Using (exp z)⁻¹ = exp(-z) and ring arithmetic in the exponent yields the desired exponential formula.

    lines 3–8

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

    private lemma circulant_graph_admits_sharp_cyclic_labeling_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; ring
    
  2. The inverse standard additive character on ZMod N is primitive.

    Suppose for contradiction that some non-zero a ∈ ZMod N defines the trivial multiplicative shift. Evaluating that shift at 1 implies that the inverse character at a is 1, so the standard character at a is 1. Since the standard character evaluates to 1 at 0 and is injective, a must be 0, a contradiction.

    lines 9–21

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

    private lemma circulant_graph_admits_sharp_cyclic_labeling_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)
    
  3. The 2D cyclic Fourier transform entry of a circulant matrix factors into a term depending on x - y and a term depending on x.

    Writing the Fourier transform in terms of the inverse standard character and using the identity m*x + n*y = -n*(x - y) + (m + n)*x, the homomorphism property splits the character into a product of ψ⁻¹(-n*(x - y)) and ψ⁻¹((m + n)*x).

    lines 22–38

    uses cyclic_matrix_fourier, Matrix.of_apply, circulant_graph_admits_sharp_cyclic_labeling_ph_apply, Finset.sum_congr, AddChar.map_add_eq_mul, mul_assoc

    private lemma circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero {N : ℕ} [NeZero N] (φ : ZMod N → ℂ) {m n : ZMod N}
        (hmn : m + n ≠ 0) :
        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 [circulant_graph_admits_sharp_cyclic_labeling_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))]
  4. The double sum factors into a product of a constant sum over difference elements and a character sum over x.

    For each fixed x, substituting t = x - y via the bijection Equiv.subLeft x shows the inner sum over y equals the fixed sum ∑_t φ(t) ψ⁻¹(-n*t), which is independent of x and factors out of the sum over x.

    lines 39–51

    uses Fintype.sum_equiv, Equiv.subLeft, Finset.sum_mul, Finset.sum_congr, Finset.mul_sum

      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.subLeft 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]
  5. If m + n ≠ 0, the Fourier entry of the circulant matrix vanishes.

    The remaining sum ∑_x ψ⁻¹((m + n)*x) is the sum over ZMod N of the shift by m + n of the primitive character ψ⁻¹. Because m + n ≠ 0, character orthogonality (AddChar.sum_mulShift) shows this sum is 0, which zeroes out the entire product.

    lines 52–59

    uses Finset.sum_congr, mul_comm, AddChar.sum_mulShift, circulant_graph_admits_sharp_cyclic_labeling_ph_primitive

      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) (circulant_graph_admits_sharp_cyclic_labeling_ph_primitive N)]
            simp [hmn]]
      ring
    
  6. The identity permutation on ZMod N is chosen as the cyclic labeling candidate.

    We choose Equiv.refl (ZMod N) as the labeling permutation. Unfolding is_sharp_cyclic_labeling reduces the goal to showing that the Fourier transform of the relabeled adjacency matrix is a weighted partial permutation, and we define φ as the indicator function of the connection set.

    lines 60–68

    uses Equiv.refl, is_sharp_cyclic_labeling

    /-- Every circulant graph with at least one edge admits a sharp cyclic labeling. -/
    theorem circulant_graph_admits_sharp_cyclic_labeling (N : ℕ) [NeZero N]
        (s : Set (ZMod N)) [DecidablePred (· ∈ s)]
        (he : ∃ u v, (SimpleGraph.circulantGraph s).Adj u v) :
        admits_sharp_cyclic_labeling N (SimpleGraph.circulantGraph s) := by
      have _ := he
      use Equiv.refl (ZMod N)
      rw [is_sharp_cyclic_labeling]
      let φ : ZMod N → ℂ := fun z => if (z ≠ 0 ∧ (z ∈ s ∨ -z ∈ s)) then 1 else 0
  7. The adjacency matrix of the circulant graph under the identity labeling is the circulant matrix M_{x, y} = φ(x - y).

    Vertices x and y are adjacent in the circulant graph iff x ≠ y and either x - y ∈ s or y - x ∈ s. Since x ≠ y is equivalent to x - y ≠ 0 and y - x = -(x - y), this adjacency predicate coincides precisely with the indicator φ(x - y).

    lines 69–85

    uses Matrix.of_apply, ne_eq, sub_ne_zero

      have hM : (Matrix.of fun x y => if (SimpleGraph.circulantGraph s).Adj ((Equiv.refl (ZMod N)) x) ((Equiv.refl (ZMod N)) y) then (1 : ℂ) else 0)
              = (Matrix.of fun x y => φ (x - y)) := by
        ext x y
        simp only [Matrix.of_apply]
        change (if (SimpleGraph.circulantGraph s).Adj x y then (1 : ℂ) else 0) = φ (x - y)
        have h_iff : (SimpleGraph.circulantGraph s).Adj x y ↔ (x - y ≠ 0 ∧ (x - y ∈ s ∨ -(x - y) ∈ s)) := by
          change (x ≠ y ∧ (x - y ∈ s ∨ y - x ∈ s)) ↔ (x - y ≠ 0 ∧ (x - y ∈ s ∨ -(x - y) ∈ s))
          have h1 : x ≠ y ↔ x - y ≠ 0 := by rw [ne_eq, sub_ne_zero]
          have h2 : y - x = -(x - y) := by ring
          rw [h1, h2]
        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]
  8. Every row of the Fourier matrix has at most one non-zero entry.

    If entries at columns j₁ and j₂ in row i are non-zero, then by the vanishing lemma neither i + j₁ nor i + j₂ can be non-zero. Hence i + j₁ = 0 and i + j₂ = 0, which implies j₁ = -i and j₂ = -i, so j₁ = j₂.

    lines 86–99

    uses is_weighted_partial_permutation, circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero, eq_neg_of_add_eq_zero_right

      dsimp [is_weighted_partial_permutation]
      constructor
      · intros i j₁ j₂ hj₁ hj₂
        have h1 : i + j₁ = 0 := by
          by_contra hc
          have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc
          exact hj₁ hz
        have h2 : i + j₂ = 0 := by
          by_contra hc
          have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc
          exact hj₂ hz
        have ej₁ := eq_neg_of_add_eq_zero_right h1
        have ej₂ := eq_neg_of_add_eq_zero_right h2
        rw [ej₁, ej₂]
  9. Every column of the Fourier matrix has at most one non-zero entry, completing the proof.

    Similarly, if entries at rows i₁ and i₂ in column j are non-zero, the vanishing lemma forces i₁ + j = 0 and i₂ + j = 0. Therefore i₁ = -j and i₂ = -j, so i₁ = i₂, establishing that the Fourier matrix is a weighted partial permutation.

    lines 100–111

    uses circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero, eq_neg_of_add_eq_zero_left

      · intros j i₁ i₂ hi₁ hi₂
        have h1 : i₁ + j = 0 := by
          by_contra hc
          have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc
          exact hi₁ hz
        have h2 : i₂ + j = 0 := by
          by_contra hc
          have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc
          exact hi₂ hz
        have ei₁ := eq_neg_of_add_eq_zero_left h1
        have ei₂ := eq_neg_of_add_eq_zero_left h2
        rw [ei₁, ei₂]
AddChar.inv_apply'
The value of the inverse additive character ψ⁻¹ at an element a is the multiplicative inverse (ψ(a))⁻¹ of its value at a.
ZMod.stdAddChar_apply
The standard additive character on ZMod N evaluates at j to the canonical embedding of its circle group element.
ZMod.toCircle_apply
The circle group representation of j ∈ ZMod N evaluates to exp(2πi j.val / N).
Complex.exp_neg
The complex exponential of -x is the multiplicative inverse (exp x)⁻¹.
congrFun
Equal functions take equal values at any argument.
congrArg
Applying a function to equal arguments yields equal results.
DFunLike.coe
Coercion of a bundled morphism or character to an ordinary function.
AddChar.mulShift
The multiplicative shift of an additive character ψ by a scalar b, given by x ↦ ψ(b * x).
ZMod.injective_stdAddChar
The standard additive character on ZMod N is an injective function.
cyclic_matrix_fourier
The two-dimensional cyclic Fourier transform of a matrix indexed by ZMod N × ZMod N.
Matrix.of_apply
The (i, j)-entry of a matrix defined by a function f is f i j.
circulant_graph_admits_sharp_cyclic_labeling_ph_apply
The inverse standard additive character on ZMod N evaluates at a to exp(-2πi a.val / N).
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on all elements.
AddChar.map_add_eq_mul
An additive character maps a sum of ring elements to the product of their character values.
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
Fintype.sum_equiv
A finite sum can be reindexed along an equivalence between index types.
Equiv.subLeft
In an additive group, the map y ↦ x - y is a bijection for any fixed x.
Finset.sum_mul
Multiplication distributes from the right over a finite sum.
Finset.mul_sum
Multiplication distributes from the left over a finite sum.
mul_comm
Multiplication is commutative: a * b = b * a.
AddChar.sum_mulShift
The sum of a primitive additive character shifted by b over a finite ring is zero if b ≠ 0, and the cardinality of the ring if b = 0.
circulant_graph_admits_sharp_cyclic_labeling_ph_primitive
The inverse of the standard additive character on ZMod N is a primitive character.
Equiv.refl
The identity bijection on a type.
is_sharp_cyclic_labeling
A labeling bijection π is sharp if the cyclic Fourier transform of the relabeled adjacency matrix is a weighted partial permutation.
ne_eq
Inequality a ≠ b is defined as the negation of equality ¬(a = b).
sub_ne_zero
The difference a - b is non-zero if and only if a ≠ b.
is_weighted_partial_permutation
A matrix is a weighted partial permutation if every row and every column contains at most one non-zero entry.
circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero
The two-dimensional cyclic Fourier transform of any circulant matrix over ZMod N vanishes at all pairs (m, n) with m + n ≠ 0.
eq_neg_of_add_eq_zero_right
If a + b = 0 in a subtraction monoid, then b = -a.
eq_neg_of_add_eq_zero_left
If a + b = 0 in a subtraction monoid, then a = -b.

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

open scoped BigOperatorsprivate lemma circulant_graph_admits_sharp_cyclic_labeling_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 circulant_graph_admits_sharp_cyclic_labeling_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 circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero {N : ℕ} [NeZero N] (φ : ZMod N → ℂ) {m n : ZMod N}    (hmn : m + n ≠ 0) :    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 [circulant_graph_admits_sharp_cyclic_labeling_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.subLeft 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) (circulant_graph_admits_sharp_cyclic_labeling_ph_primitive N)]        simp [hmn]]  ring/-- Every circulant graph with at least one edge admits a sharp cyclic labeling. -/theorem circulant_graph_admits_sharp_cyclic_labeling (N : ℕ) [NeZero N]    (s : Set (ZMod N)) [DecidablePred (· ∈ s)]    (he : ∃ u v, (SimpleGraph.circulantGraph s).Adj u v) :    admits_sharp_cyclic_labeling N (SimpleGraph.circulantGraph s) := by  have _ := he  use Equiv.refl (ZMod N)  rw [is_sharp_cyclic_labeling]  let φ : ZMod N → ℂ := fun z => if (z ≠ 0 ∧ (z ∈ s ∨ -z ∈ s)) then 1 else 0  have hM : (Matrix.of fun x y => if (SimpleGraph.circulantGraph s).Adj ((Equiv.refl (ZMod N)) x) ((Equiv.refl (ZMod N)) y) then (1 : ℂ) else 0)          = (Matrix.of fun x y => φ (x - y)) := by    ext x y    simp only [Matrix.of_apply]    change (if (SimpleGraph.circulantGraph s).Adj x y then (1 : ℂ) else 0) = φ (x - y)    have h_iff : (SimpleGraph.circulantGraph s).Adj x y ↔ (x - y ≠ 0 ∧ (x - y ∈ s ∨ -(x - y) ∈ s)) := by      change (x ≠ y ∧ (x - y ∈ s ∨ y - x ∈ s)) ↔ (x - y ≠ 0 ∧ (x - y ∈ s ∨ -(x - y) ∈ s))      have h1 : x ≠ y ↔ x - y ≠ 0 := by rw [ne_eq, sub_ne_zero]      have h2 : y - x = -(x - y) := by ring      rw [h1, h2]    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]  dsimp [is_weighted_partial_permutation]  constructor  · intros i j₁ j₂ hj₁ hj₂    have h1 : i + j₁ = 0 := by      by_contra hc      have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc      exact hj₁ hz    have h2 : i + j₂ = 0 := by      by_contra hc      have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc      exact hj₂ hz    have ej₁ := eq_neg_of_add_eq_zero_right h1    have ej₂ := eq_neg_of_add_eq_zero_right h2    rw [ej₁, ej₂]  · intros j i₁ i₂ hi₁ hi₂    have h1 : i₁ + j = 0 := by      by_contra hc      have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc      exact hi₁ hz    have h2 : i₂ + j = 0 := by      by_contra hc      have hz := circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero φ hc      exact hi₂ hz    have ei₁ := eq_neg_of_add_eq_zero_left h1    have ei₂ := eq_neg_of_add_eq_zero_left h2    rw [ei₁, ei₂]
See it in the graphDiscuss this resultChallenge it