circulant_graph_admits_sharp_cyclic_labeling
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.
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.
uses
AddChar.inv_apply',ZMod.stdAddChar_apply,ZMod.toCircle_apply,Complex.exp_negprivate 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
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.
uses
congrFun,congrArg,DFunLike.coe,AddChar.mulShift,AddChar.inv_apply',ZMod.injective_stdAddCharprivate 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)
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).
uses
cyclic_matrix_fourier,Matrix.of_apply,circulant_graph_admits_sharp_cyclic_labeling_ph_apply,Finset.sum_congr,AddChar.map_add_eq_mul,mul_assocprivate 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))]
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.
uses
Fintype.sum_equiv,Equiv.subLeft,Finset.sum_mul,Finset.sum_congr,Finset.mul_sumhave 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]
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.
uses
Finset.sum_congr,mul_comm,AddChar.sum_mulShift,circulant_graph_admits_sharp_cyclic_labeling_ph_primitiverw [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
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.
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
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).
uses
Matrix.of_apply,ne_eq,sub_ne_zerohave 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]
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₂.
uses
is_weighted_partial_permutation,circulant_graph_admits_sharp_cyclic_labeling_fourier_eq_zero,eq_neg_of_add_eq_zero_rightdsimp [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₂]
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.
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.
- The hypothesis `he` asserting that the graph has at least one edge is retained in the theorem signature but unused in the formal argument (noted by `have _ := he`), since an empty graph would also trivially satisfy the condition.
- The Fourier transform of the matrix is phrased using Mathlib's bundled additive character `AddChar (ZMod N) ℂ` rather than raw complex exponentials, which enables direct application of character orthogonality lemmas.
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.
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₂]