simple_graph_cycle_power_three_layer_weight_le
Let n ≥ 10 and let c label the vertices of C_n^3 so that every label class is a clique. Then Σ_i (2·[i and i+3 share a class] + [i and i+2 share a class]) ≤ n: each class K contributes 2·(its pairs at distance 3) + (its pairs at distance 2) ≤ |K|.
Statement
theorem simple_graph_cycle_power_three_layer_weight_le (n : ℕ) [NeZero n] (hn : 10 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n 3).Adj u v) : ∑ i : ZMod n, (2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0)) ≤ n
- Source
- Step toward simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd (the k = 3 case of OP-205, arXiv:2610.15635): the double-counting proof found in thread RT-1.
- Verified
- 17 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - simple_graph_cycle_power_three_adj_iffFor n ≥ 10, u and v are adjacent in C_n^3 iff v = u + e for an integer e with 0 < |e| ≤ 3.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - zmod_intCast_eq_intCast_iff_of_abs_sub_ltTwo integers a, b with |a − b| < n are equal modulo n only if they are equal.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 2
- simple_graph_cycle_power_three_layer_weight_eq_impIn the situation of the weight inequality, if Σ_i (2·[c i = c(i+3)] + [c i = c(i+2)]) = n then every class contains a pair at distance 3…
- simple_graph_cycle_power_three_cover_three_tightIf three equivalence subgraphs (labellings c_0, c_1, c_2 with clique classes) cover C_n^3, n ≥ 10, then every pair at distance 3 and every…
The proof, explained
The proof partitions the total sum over all vertices in $\mathbb{Z}/n\mathbb{Z}$ into contributions from each monochromatic label class (fiber) $K = c^{-1}(\ell)$. Because each label class is a clique in the cycle power $C_n^3$ and $n \ge 10$, the vertices in any non-empty fiber can be uniquely represented relative to a base vertex by an offset set $S \subseteq \{-3, \dots, 3\} \subset \mathbb{Z}$ of diameter at most 3. The fiber's contribution to the sum matches an integer weight on $S$, which is bounded by $|S| = |K|$ via an exhaustive finite check on all diameter-3 subsets using `decide`. Summing these bounds over all colors yields $\sum_\ell |c^{-1}(\ell)| = n$, establishing the inequality.
Any subset $S \subseteq \{-3, \dots, 3\}$ of diameter at most 3 has weight at most $|S|$. automation
The condition $S \subseteq \{-3, \dots, 3\}$ places $S$ in the finite powerset of the interval (line 10). Reverting the variables produces a fully universal, bounded statement (line 11), which Lean's `decide` tactic verifies by exhaustively checking all $2^7 = 128$ candidate subsets (line 12).
uses
mem_powerset.mprhave h_univ : S ∈ (Icc (-3 : ℤ) 3).powerset := mem_powerset.mpr hS revert S hS hdiam h_univ decide
Define the color class $K = c^{-1}(\ell)$, and assume $K$ is non-empty with a chosen base vertex $m \in K$.
We define the fiber $K = \{x \in \mathbb{Z}/n\mathbb{Z} \mid c(x) = \ell\}$ (line 21) and split into cases on whether $K$ is non-empty (line 22). When $K$ is non-empty, we pick an element $m \in K$, so $c(m) = \ell$ (lines 23–24).
uses
mem_filterset K := univ.filter (fun x => c x = ℓ) by_cases hK : K.Nonempty · obtain ⟨m, hm_mem⟩ := hK have hm : c m = ℓ := (mem_filter.mp hm_mem).2
Define the offset set $S \subseteq \{-3, \dots, 3\}$ and show that every vertex in $K$ is represented as $m + e$ for some $e \in \{-3, \dots, 3\}$.
We define $S$ as the set of integer offsets $e \in [-3, 3]$ such that $c(m + e) = \ell$, so $S \subseteq [-3, 3]$ holds by definition (lines 25–26). For any $z \in K$, either $z = m$ (which corresponds to $e = 0$, lines 29–30), or $z \neq m$. In the latter case, because $c(m) = c(z) = \ell$, the hypothesis $hc$ implies $m$ and $z$ are adjacent in $C_n^3$ (line 31). By `simple_graph_cycle_power_three_adj_iff` with $n \ge 10$, adjacency means $z = m + e$ for some integer $e \in [-3, 3]$ (lines 32–34).
uses
filter_subset,Ne.symm,simple_graph_cycle_power_three_adj_iff,abs_leset S : Finset ℤ := (Icc (-3 : ℤ) 3).filter (fun (e : ℤ) => c (m + (e : ZMod n)) = ℓ) have hS_sub : S ⊆ Icc (-3 : ℤ) 3 := filter_subset _ _ have h_mem : ∀ z, c z = ℓ → ∃ e : ℤ, e ∈ Icc (-3 : ℤ) 3 ∧ z = m + (e : ZMod n) := by intro z hz by_cases hzm : z = m · refine ⟨0, by simp, by simp [hzm]⟩ · have hadj : (simple_graph_cycle_power n 3).Adj m z := hc m z (Ne.symm hzm) (by rw [hm, hz]) obtain ⟨e, he0, he3, rfl⟩ := (simple_graph_cycle_power_three_adj_iff n hn m z).mp hadj rw [abs_le] at he3 refine ⟨e, by simp [he3], rfl⟩
The offset set $S$ has diameter at most 3: $|a - b| \le 3$ for all $a, b \in S$.
Given $a, b \in S$, if $a = b$ the distance is 0 (lines 41–42). If $a \neq b$, then $m + a \neq m + b$ because $a, b \in [-3, 3]$ and $n \ge 10$, so $|a - b| \le 6 < n$ prevents modular wrap-around (lines 43–48). Since both vertices have color $\ell$, they are adjacent in $C_n^3$ (lines 49–50), so $m + b = m + a + d$ for some $d \in \mathbb{Z}$ with $|d| \le 3$ (lines 51–53). The bound $|b - (a + d)| \le |b| + |a| + |d| \le 9 < n$ implies that $b = a + d$ holds in $\mathbb{Z}$ (lines 54–61). Hence $|a - b| = |-d| = |d| \le 3$ (lines 62–65).
uses
mem_filter,add_left_cancel_iff,mem_Icc,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lt,simple_graph_cycle_power_three_adj_iff,abs_le,add_left_cancel,abs_neghave h_diam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 3 := by intro a ha b hb have ha_icc : a ∈ Icc (-3 : ℤ) 3 := (mem_filter.mp ha).1 have hb_icc : b ∈ Icc (-3 : ℤ) 3 := (mem_filter.mp hb).1 have hca : c (m + (a : ZMod n)) = ℓ := (mem_filter.mp ha).2 have hcb : c (m + (b : ZMod n)) = ℓ := (mem_filter.mp hb).2 by_cases hab : a = b · subst hab; simp · have hne : m + (a : ZMod n) ≠ m + (b : ZMod n) := by intro h rw [add_left_cancel_iff] at h rw [mem_Icc] at ha_icc hb_icc have hlt : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact hab ((zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b hlt).mp h) have hadj : (simple_graph_cycle_power n 3).Adj (m + (a : ZMod n)) (m + (b : ZMod n)) := hc _ _ hne (by rw [hca, hcb]) obtain ⟨d, hd0, hd3, hd_eq⟩ := (simple_graph_cycle_power_three_adj_iff n hn _ _).mp hadj rw [mem_Icc] at ha_icc hb_icc rw [abs_le] at hd3 have h_diff : |b - (a + d)| < n := by rw [abs_lt]; constructor <;> omega have h_eq' : ((b : ℤ) : ZMod n) = (((a + d : ℤ) : ZMod n)) := by have hd_eq' : m + (b : ZMod n) = m + ((a + d : ℤ) : ZMod n) := by calc m + (b : ZMod n) = m + (a : ZMod n) + (d : ZMod n) := hd_eq _ = m + (((a + d : ℤ) : ZMod n)) := by push_cast; ring exact add_left_cancel hd_eq' have hbd : b = a + d := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n b (a + d) h_diff).mp h_eq' rw [hbd] have : a - (a + d) = -d := by ring rw [this, abs_neg, abs_le] exact ⟨by omega, by omega⟩
For $e \in S$ and $k \in \{2, 3\}$, the shifted vertex $m + e + k$ has color $\ell$ if and only if $e + k \in S$.
The backward direction holds by definition of $S$ (lines 85–86). In the forward direction, if $c(m + (e + k)) = \ell$, then by representation of $K$ there is an offset $e' \in [-3, 3]$ such that $m + (e + k) = m + e'$ (lines 74–77). Because $e \in [-3, 3]$ and $k \in \{2, 3\}$, we have $e + k \in [-1, 6]$, and since $e' \in [-3, 3]$, the difference $|(e + k) - e'| \le 9 < n$ (lines 78–81). Thus $e + k = e' \in [-3, 3]$ in $\mathbb{Z}$, which shows $e + k \in S$ (lines 82–84).
uses
mem_filter,add_left_cancel,mem_Icc,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lthave h_shift : ∀ e ∈ S, ∀ (k : ℤ), k = 2 ∨ k = 3 → (c (m + (e : ZMod n) + (k : ZMod n)) = ℓ ↔ e + k ∈ S) := by intro e he k hk have he_icc : e ∈ Icc (-3 : ℤ) 3 := (mem_filter.mp he).1 have hk_cast : m + (e : ZMod n) + (k : ZMod n) = m + ((e + k : ℤ) : ZMod n) := by push_cast; ring rw [hk_cast, mem_filter] constructor · intro hc_shift refine ⟨?_, hc_shift⟩ obtain ⟨e', he', he'_eq⟩ := h_mem (m + ((e + k : ℤ) : ZMod n)) hc_shift have he_eq' : ((e + k : ℤ) : ZMod n) = ((e' : ℤ) : ZMod n) := add_left_cancel he'_eq rw [mem_Icc] at he_icc he' have hdiff : |(e + k) - e'| < n := by rw [abs_lt] rcases hk with rfl | rfl <;> omega have hek_eq : e + k = e' := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (e + k) e' hdiff).mp he_eq' rw [hek_eq] exact mem_Icc.mpr he' · rintro ⟨h1, h2⟩ exact h2
The map $e \mapsto m + e$ is a bijection from $S$ to $K$, so $|S| = |K|$.
We establish a bijection via `card_bij` (line 88). The map lands in $K$ by definition of $S$ (lines 89–91). It is injective because $m + e_1 = m + e_2$ in $\mathbb{Z}/n\mathbb{Z}$ with $e_1, e_2 \in [-3, 3]$ implies $e_1 = e_2$ in $\mathbb{Z}$, since $|e_1 - e_2| \le 6 < n$ (lines 92–99). It is surjective onto $K$ because every element of $K$ has the form $m + e$ for some $e \in [-3, 3]$, which by definition must be in $S$ (lines 100–104).
uses
card_bij,mem_filter,mem_univ,add_left_cancel_iff,mem_Icc,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lthave h_card : #S = #K := by apply card_bij (fun (e : ℤ) _ => m + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro e₁ he₁ e₂ he₂ heq rw [add_left_cancel_iff] at heq have he₁' : e₁ ∈ Icc (-3 : ℤ) 3 := hS_sub he₁ have he₂' : e₂ ∈ Icc (-3 : ℤ) 3 := hS_sub he₂ rw [mem_Icc] at he₁' he₂' have hdiff : |e₁ - e₂| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e₁ e₂ hdiff).mp heq · intro b hb rw [mem_filter] at hb obtain ⟨e, he_icc, he_eq⟩ := h_mem b hb.2 refine ⟨e, mem_filter.mpr ⟨he_icc, ?_⟩, he_eq.symm⟩ rw [← he_eq]; exact hb.2
When $K$ is non-empty, the fiber sum is at most $|K|$.
We define the terms $g(i)$ on $\mathbb{Z}/n\mathbb{Z}$ and $f(e)$ on $\mathbb{Z}$ (lines 105–108). Using `sum_bij` along the bijection $e \mapsto m + e$, the shift equivalence from line 66 shows that $g(m + e) = f(e)$ for each $e \in S$, matching the sum over $K$ with `simple_graph_cycle_power_three_layer_weight_int_weight` $S$ (lines 109–141). Substituting $|S| = |K|$, the bound follows from the exhaustive check lemma `simple_graph_cycle_power_three_layer_weight_decide_diam` (lines 142–143).
uses
sum_bij,mem_filter,mem_univ,add_left_cancel_iff,mem_Icc,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lt,eq_comm,Or.inr,Or.inl,if_congr,simple_graph_cycle_power_three_layer_weight_decide_diamset g := fun (i : ZMod n) => 2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0) set f := fun (e : ℤ) => 2 * (if e + 3 ∈ S then 1 else 0) + (if e + 2 ∈ S then 1 else 0) have h_sum : ∑ i ∈ K, g i = simple_graph_cycle_power_three_layer_weight_int_weight S := by have h_bij : ∑ e ∈ S, f e = ∑ i ∈ K, g i := by apply sum_bij (fun (e : ℤ) _ => m + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro e₁ he₁ e₂ he₂ heq rw [add_left_cancel_iff] at heq have he₁' : e₁ ∈ Icc (-3 : ℤ) 3 := hS_sub he₁ have he₂' : e₂ ∈ Icc (-3 : ℤ) 3 := hS_sub he₂ rw [mem_Icc] at he₁' he₂' have hdiff : |e₁ - e₂| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e₁ e₂ hdiff).mp heq · intro b hb rw [mem_filter] at hb obtain ⟨e, he_icc, he_eq⟩ := h_mem b hb.2 refine ⟨e, mem_filter.mpr ⟨he_icc, ?_⟩, he_eq.symm⟩ rw [← he_eq]; exact hb.2 · intro e he have he_c : c (m + (e : ZMod n)) = ℓ := (mem_filter.mp he).2 have h3_cast : (3 : ZMod n) = ((3 : ℤ) : ZMod n) := by push_cast; rfl have h2_cast : (2 : ZMod n) = ((2 : ℤ) : ZMod n) := by push_cast; rfl have h3 : (c (m + (e : ZMod n)) = c (m + (e : ZMod n) + 3)) ↔ e + 3 ∈ S := by rw [he_c, eq_comm, h3_cast] exact h_shift e he 3 (Or.inr rfl) have h2 : (c (m + (e : ZMod n)) = c (m + (e : ZMod n) + 2)) ↔ e + 2 ∈ S := by rw [he_c, eq_comm, h2_cast] exact h_shift e he 2 (Or.inl rfl) dsimp [f, g] rw [if_congr h3 rfl rfl, if_congr h2 rfl rfl] rw [← h_bij] rfl rw [h_sum, ← h_card] exact simple_graph_cycle_power_three_layer_weight_decide_diam S hS_sub h_diam
When $K$ is empty, the fiber inequality holds trivially ($0 \le 0$).
If $K$ is not non-empty, then $K = \emptyset$ (line 144). Substituting $K = \emptyset$, both the sum and the cardinality evaluate to 0 by simplification (lines 145–146).
uses
not_nonempty_iff_eq_empty· rw [not_nonempty_iff_eq_empty] at hK rw [hK] simp
The total sum decomposes fiberwise over the colors.
By `sum_fiberwise`, summing over all $i \in \mathbb{Z}/n\mathbb{Z}$ is equivalent to summing over each color $j \in \mathbb{Z}/n\mathbb{Z}$ and then summing over vertices with $c(i) = j$ (lines 152–154).
uses
sum_fiberwisehave h_fiber := sum_fiberwise (s := univ) c (fun i => 2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0)) rw [← h_fiber]
The total sum is bounded by the sum of fiber cardinalities $\sum_j |c^{-1}(j)|$.
Applying `sum_le_sum` reduces the double sum inequality to bounding each fiber's sum by its cardinality (lines 158–159). This is precisely the lemma `simple_graph_cycle_power_three_layer_weight_fiber_le` established above (line 160).
uses
sum_le_sum,simple_graph_cycle_power_three_layer_weight_fiber_lehave h_le : (∑ j : ZMod n, ∑ i with c i = j, (2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0))) ≤ ∑ j : ZMod n, #{i | c i = j} := by apply sum_le_sum intro ℓ _ exact simple_graph_cycle_power_three_layer_weight_fiber_le n hn c hc ℓ
The sum of fiber cardinalities equals $n$, completing the proof.
The sum of fiber cardinalities $\sum_j |c^{-1}(j)|$ equals the total number of vertices $|\mathbb{Z}/n\mathbb{Z}|$ by `card_eq_sum_card_fiberwise`, which evaluates to $n$ via `card_univ` and `ZMod.card` (lines 161–163). Linear arithmetic (`omega`) closes the goal (line 164).
uses
card_eq_sum_card_fiberwise,card_univ,ZMod.cardhave h_card : (∑ j : ZMod n, #{i | c i = j}) = n := by have := card_eq_sum_card_fiberwise (s := univ) (t := univ) (f := c) (fun _ _ => mem_univ _) rw [← this, card_univ, ZMod.card] omega
mem_powerset.mpr- An element $s$ belongs to the powerset of $t$ if $s \subseteq t$.
filter_subset- Filtering a finite set by a predicate yields a subset of the original set.
Ne.symm- Inequality is symmetric: if $a \neq b$, then $b \neq a$.
simple_graph_cycle_power_three_adj_iff- In the cycle power $C_n^3$ with $n \ge 10$, two vertices are adjacent if and only if they differ by a non-zero offset of absolute value at most 3.
abs_le- $|a| \le b$ if and only if $-b \le a \le b$.
mem_filter- An element is in a filtered set if and only if it belongs to the set and satisfies the predicate.
add_left_cancel_iff- Left addition is injective: $a + b = a + c \iff b = c$.
mem_Icc- An integer $x$ belongs to the closed interval $[a, b]$ if and only if $a \le x \le b$.
abs_lt- $|a| < b$ if and only if $-b < a < b$.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- Two integers with difference $|a - b| < n$ are congruent modulo $n$ if and only if they are equal in $\mathbb{Z}$.
add_left_cancel- If $a + b = a + c$, then $b = c$.
abs_neg- The absolute value of $-a$ equals the absolute value of $a$.
card_bij- Two finite sets have the same cardinality if there is an injection between them that is also surjective.
mem_univ- Every element of a finite type belongs to the universal set `univ`.
sum_bij- Two finite sums are equal if their index sets are in bijection and corresponding terms match.
eq_comm- Equality is symmetric: $a = b \iff b = a$.
Or.inr- Disjunction introduction right: $Q$ implies $P \lor Q$.
Or.inl- Disjunction introduction left: $P$ implies $P \lor Q$.
if_congr- Congruence for `if-then-else`: if the conditions are equivalent and the branches agree, the expressions are equal.
simple_graph_cycle_power_three_layer_weight_decide_diam- Any subset $S \subseteq \{-3, \dots, 3\}$ of diameter at most 3 has weight $\sum_{e \in S} (2 \cdot [e+3 \in S] + [e+2 \in S]) \le |S|$.
not_nonempty_iff_eq_empty- A finite set is not non-empty if and only if it is the empty set.
sum_fiberwise- A sum over a finite set can be partitioned into a double sum over the fibers of any function.
sum_le_sum- If $f(x) \le g(x)$ for all elements of a set, then $\sum f(x) \le \sum g(x)$.
simple_graph_cycle_power_three_layer_weight_fiber_le- Each monochromatic label class (fiber) contributes at most its cardinality to the layer weight sum.
card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum of the cardinalities of its fibers under any function.
card_univ- The cardinality of the universal set of a finite type equals the cardinality of the type.
ZMod.card- The cardinality of $\mathbb{Z}/n\mathbb{Z}$ is $n$.
- The base case lemma `simple_graph_cycle_power_three_layer_weight_decide_diam` relies entirely on Lean's `decide` tactic, which verifies the inequality by finite exhaustion over all $2^7 = 128$ subsets of the integer interval $\{-3, \dots, 3\}$.
- The condition $n \ge 10$ ensures that cyclic distances bounded by 3 cannot wrap around modulo $n$, allowing the local graph structure in $\mathbb{Z}/n\mathbb{Z}$ to be faithfully identified with integer offsets in $\mathbb{Z}$.
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 Finsetdef simple_graph_cycle_power_three_layer_weight_int_weight (T : Finset ℤ) : ℕ := ∑ e ∈ T, (2 * (if e + 3 ∈ T then 1 else 0) + (if e + 2 ∈ T then 1 else 0))theorem simple_graph_cycle_power_three_layer_weight_decide_diam (S : Finset ℤ) (hS : S ⊆ Icc (-3 : ℤ) 3) (hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 3) : simple_graph_cycle_power_three_layer_weight_int_weight S ≤ #S := by have h_univ : S ∈ (Icc (-3 : ℤ) 3).powerset := mem_powerset.mpr hS revert S hS hdiam h_univ decidelemma simple_graph_cycle_power_three_layer_weight_fiber_le (n : ℕ) [NeZero n] (hn : 10 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n 3).Adj u v) (ℓ : ZMod n) : ∑ i ∈ univ.filter (fun x => c x = ℓ), (2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0)) ≤ #(univ.filter (fun x => c x = ℓ)) := by set K := univ.filter (fun x => c x = ℓ) by_cases hK : K.Nonempty · obtain ⟨m, hm_mem⟩ := hK have hm : c m = ℓ := (mem_filter.mp hm_mem).2 set S : Finset ℤ := (Icc (-3 : ℤ) 3).filter (fun (e : ℤ) => c (m + (e : ZMod n)) = ℓ) have hS_sub : S ⊆ Icc (-3 : ℤ) 3 := filter_subset _ _ have h_mem : ∀ z, c z = ℓ → ∃ e : ℤ, e ∈ Icc (-3 : ℤ) 3 ∧ z = m + (e : ZMod n) := by intro z hz by_cases hzm : z = m · refine ⟨0, by simp, by simp [hzm]⟩ · have hadj : (simple_graph_cycle_power n 3).Adj m z := hc m z (Ne.symm hzm) (by rw [hm, hz]) obtain ⟨e, he0, he3, rfl⟩ := (simple_graph_cycle_power_three_adj_iff n hn m z).mp hadj rw [abs_le] at he3 refine ⟨e, by simp [he3], rfl⟩ have h_diam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 3 := by intro a ha b hb have ha_icc : a ∈ Icc (-3 : ℤ) 3 := (mem_filter.mp ha).1 have hb_icc : b ∈ Icc (-3 : ℤ) 3 := (mem_filter.mp hb).1 have hca : c (m + (a : ZMod n)) = ℓ := (mem_filter.mp ha).2 have hcb : c (m + (b : ZMod n)) = ℓ := (mem_filter.mp hb).2 by_cases hab : a = b · subst hab; simp · have hne : m + (a : ZMod n) ≠ m + (b : ZMod n) := by intro h rw [add_left_cancel_iff] at h rw [mem_Icc] at ha_icc hb_icc have hlt : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact hab ((zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b hlt).mp h) have hadj : (simple_graph_cycle_power n 3).Adj (m + (a : ZMod n)) (m + (b : ZMod n)) := hc _ _ hne (by rw [hca, hcb]) obtain ⟨d, hd0, hd3, hd_eq⟩ := (simple_graph_cycle_power_three_adj_iff n hn _ _).mp hadj rw [mem_Icc] at ha_icc hb_icc rw [abs_le] at hd3 have h_diff : |b - (a + d)| < n := by rw [abs_lt]; constructor <;> omega have h_eq' : ((b : ℤ) : ZMod n) = (((a + d : ℤ) : ZMod n)) := by have hd_eq' : m + (b : ZMod n) = m + ((a + d : ℤ) : ZMod n) := by calc m + (b : ZMod n) = m + (a : ZMod n) + (d : ZMod n) := hd_eq _ = m + (((a + d : ℤ) : ZMod n)) := by push_cast; ring exact add_left_cancel hd_eq' have hbd : b = a + d := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n b (a + d) h_diff).mp h_eq' rw [hbd] have : a - (a + d) = -d := by ring rw [this, abs_neg, abs_le] exact ⟨by omega, by omega⟩ have h_shift : ∀ e ∈ S, ∀ (k : ℤ), k = 2 ∨ k = 3 → (c (m + (e : ZMod n) + (k : ZMod n)) = ℓ ↔ e + k ∈ S) := by intro e he k hk have he_icc : e ∈ Icc (-3 : ℤ) 3 := (mem_filter.mp he).1 have hk_cast : m + (e : ZMod n) + (k : ZMod n) = m + ((e + k : ℤ) : ZMod n) := by push_cast; ring rw [hk_cast, mem_filter] constructor · intro hc_shift refine ⟨?_, hc_shift⟩ obtain ⟨e', he', he'_eq⟩ := h_mem (m + ((e + k : ℤ) : ZMod n)) hc_shift have he_eq' : ((e + k : ℤ) : ZMod n) = ((e' : ℤ) : ZMod n) := add_left_cancel he'_eq rw [mem_Icc] at he_icc he' have hdiff : |(e + k) - e'| < n := by rw [abs_lt] rcases hk with rfl | rfl <;> omega have hek_eq : e + k = e' := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (e + k) e' hdiff).mp he_eq' rw [hek_eq] exact mem_Icc.mpr he' · rintro ⟨h1, h2⟩ exact h2 have h_card : #S = #K := by apply card_bij (fun (e : ℤ) _ => m + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro e₁ he₁ e₂ he₂ heq rw [add_left_cancel_iff] at heq have he₁' : e₁ ∈ Icc (-3 : ℤ) 3 := hS_sub he₁ have he₂' : e₂ ∈ Icc (-3 : ℤ) 3 := hS_sub he₂ rw [mem_Icc] at he₁' he₂' have hdiff : |e₁ - e₂| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e₁ e₂ hdiff).mp heq · intro b hb rw [mem_filter] at hb obtain ⟨e, he_icc, he_eq⟩ := h_mem b hb.2 refine ⟨e, mem_filter.mpr ⟨he_icc, ?_⟩, he_eq.symm⟩ rw [← he_eq]; exact hb.2 set g := fun (i : ZMod n) => 2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0) set f := fun (e : ℤ) => 2 * (if e + 3 ∈ S then 1 else 0) + (if e + 2 ∈ S then 1 else 0) have h_sum : ∑ i ∈ K, g i = simple_graph_cycle_power_three_layer_weight_int_weight S := by have h_bij : ∑ e ∈ S, f e = ∑ i ∈ K, g i := by apply sum_bij (fun (e : ℤ) _ => m + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro e₁ he₁ e₂ he₂ heq rw [add_left_cancel_iff] at heq have he₁' : e₁ ∈ Icc (-3 : ℤ) 3 := hS_sub he₁ have he₂' : e₂ ∈ Icc (-3 : ℤ) 3 := hS_sub he₂ rw [mem_Icc] at he₁' he₂' have hdiff : |e₁ - e₂| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e₁ e₂ hdiff).mp heq · intro b hb rw [mem_filter] at hb obtain ⟨e, he_icc, he_eq⟩ := h_mem b hb.2 refine ⟨e, mem_filter.mpr ⟨he_icc, ?_⟩, he_eq.symm⟩ rw [← he_eq]; exact hb.2 · intro e he have he_c : c (m + (e : ZMod n)) = ℓ := (mem_filter.mp he).2 have h3_cast : (3 : ZMod n) = ((3 : ℤ) : ZMod n) := by push_cast; rfl have h2_cast : (2 : ZMod n) = ((2 : ℤ) : ZMod n) := by push_cast; rfl have h3 : (c (m + (e : ZMod n)) = c (m + (e : ZMod n) + 3)) ↔ e + 3 ∈ S := by rw [he_c, eq_comm, h3_cast] exact h_shift e he 3 (Or.inr rfl) have h2 : (c (m + (e : ZMod n)) = c (m + (e : ZMod n) + 2)) ↔ e + 2 ∈ S := by rw [he_c, eq_comm, h2_cast] exact h_shift e he 2 (Or.inl rfl) dsimp [f, g] rw [if_congr h3 rfl rfl, if_congr h2 rfl rfl] rw [← h_bij] rfl rw [h_sum, ← h_card] exact simple_graph_cycle_power_three_layer_weight_decide_diam S hS_sub h_diam · rw [not_nonempty_iff_eq_empty] at hK rw [hK] simptheorem simple_graph_cycle_power_three_layer_weight_le (n : ℕ) [NeZero n] (hn : 10 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n 3).Adj u v) : ∑ i : ZMod n, (2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0)) ≤ n := by have h_fiber := sum_fiberwise (s := univ) c (fun i => 2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0)) rw [← h_fiber] have h_le : (∑ j : ZMod n, ∑ i with c i = j, (2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0))) ≤ ∑ j : ZMod n, #{i | c i = j} := by apply sum_le_sum intro ℓ _ exact simple_graph_cycle_power_three_layer_weight_fiber_le n hn c hc ℓ have h_card : (∑ j : ZMod n, #{i | c i = j}) = n := by have := card_eq_sum_card_fiberwise (s := univ) (t := univ) (f := c) (fun _ _ => mem_univ _) rw [← this, card_univ, ZMod.card] omega