simple_graph_cycle_power_three_layer_weight_eq_imp
In 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 with all its elements between them: every vertex i lies in the class of some j ∈ {i-3, ..., i} with c j = c (j+3).
Statement
theorem simple_graph_cycle_power_three_layer_weight_eq_imp (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) (heq : ∑ 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) : ∀ i : ZMod n, ∃ d : ℕ, d ≤ 3 ∧ c (i - d) = c (i - d + 3) ∧ c (i - d) = c i
- 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
- 29 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…
- simple_graph_cycle_power_three_layer_weight_leLet 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…
- 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.
- Used by 1
- 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 first establishes an auxiliary lemma by finite exhaustion (decide): any nonempty subset S ⊆ {-3, ..., 3} of diameter at most 3 with integer weight equal to its cardinality is tightly bounded between a and a + 3 for some a, a + 3 ∈ S. For the main theorem, the total weight of ZMod n is decomposed fiberwise; since the total weight is n and each fiber has weight at most its size, every fiber K = c⁻¹(c(i)) must achieve equality. Mapping K to integer offsets S ⊆ {-3, ..., 3} via e ↦ i + e preserves weights and sizes and forces S to have diameter at most 3. Applying the tight classification lemma yields a ∈ S with a + 3 ∈ S and 0 ∈ [a, a + 3], giving the required offset d = -a ∈ {0, 1, 2, 3}.
For any nonempty subset S ⊆ [-3, 3] ⊂ ℤ of diameter at most 3 whose integer weight equals its cardinality, there exists a ∈ S such that a + 3 ∈ S and S ⊆ [a, a + 3]. automation
Since S ⊆ [-3, 3], S belongs to the finite powerset of [-3, 3] by mem_powerset. Reverting all hypotheses frames the statement as a decidable property over the finite powerset of [-3, 3], which Lean's decide tactic verifies by exhaustive check.
uses
mem_powersethave h_univ : S ∈ (Icc (-3 : ℤ) 3).powerset := mem_powerset.mpr hS revert S hS hdiam heq hne h_univ decide
Fix an arbitrary vertex i ∈ ZMod n and define the local weight function W.
We introduce the vertex i for which the witness offset d is sought, and define W(x) = 2 · [c(x) = c(x+3)] + [c(x) = c(x+2)] for every x ∈ ZMod n.
intro i let W : ZMod n → ℕ := fun i => 2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0)
The sum of the sizes of all color classes (fibers of c) equals n.
Partitioning the vertices of ZMod n into fibers of c using card_eq_sum_card_fiberwise shows that the sum of fiber sizes is the cardinality of univ (card_univ), which equals n by ZMod.card. We also record sum_fiberwise to decompose sums over ZMod n into fiberwise sums.
uses
sum_fiberwise,card_eq_sum_card_fiberwise,mem_univ,card_univ,ZMod.cardhave h_fiber := sum_fiberwise (s := univ) c W have h_card : (∑ j : ZMod n, #{x | c x = j}) = n := by have := card_eq_sum_card_fiberwise (s := univ) (t := univ) (f := c) (fun _ _ => mem_univ _) rw [← this, card_univ, ZMod.card]
The sum of all fiber weights equals the sum of all fiber sizes.
By simple_graph_cycle_power_three_layer_weight_fiber_le, the sum of weights in any single color fiber j is at most the cardinality of that fiber. Rewriting the total sum using the fiber decomposition h_fiber, the hypothesis heq that total weight is n, and the total cardinality h_card shows that the sum of fiber weights equals the sum of fiber sizes.
uses
simple_graph_cycle_power_three_layer_weight_fiber_lehave h_le : ∀ j, ∑ x with c x = j, W x ≤ #{x | c x = j} := by intro j exact simple_graph_cycle_power_three_layer_weight_fiber_le n hn c hc j have h_sum_W : (∑ j : ZMod n, ∑ x with c x = j, W x) = ∑ j : ZMod n, #{x | c x = j} := by rw [h_fiber, heq, h_card]
For every color ℓ, the weight of its fiber equals its cardinality.
Since each individual fiber has weight at most its size, if any fiber ℓ had strictly smaller weight (lt_of_le_of_ne), the sum of weights across all fibers would be strictly less than the sum of fiber sizes by sum_lt_sum. This contradicts the equality established in the previous step, so equality must hold for every fiber.
uses
lt_of_le_of_ne,sum_lt_sum,mem_univhave h_fiber_eq : ∀ ℓ, ∑ x with c x = ℓ, W x = #{x | c x = ℓ} := by intro ℓ by_contra hne have hlt : (∑ x with c x = ℓ, W x) < #{x | c x = ℓ} := lt_of_le_of_ne (h_le ℓ) hne have h_sum_lt := sum_lt_sum (s := univ) (fun j _ => h_le j) ⟨ℓ, mem_univ ℓ, hlt⟩ omega
Define the color class K of vertex i and its local offset set S ⊆ {-3, ..., 3} ⊂ ℤ.
We define K = {x ∈ ZMod n | c(x) = c(i)} as the fiber of i, and S = {e ∈ {-3, ..., 3} | c(i + e) = c(i)} ⊆ ℤ as the set of integer offsets relative to i whose corresponding vertices have color c(i). By filter_subset, S ⊆ [-3, 3].
uses
filter_subsetlet K := univ.filter (fun x => c x = c i) let S : Finset ℤ := (Icc (-3 : ℤ) 3).filter (fun (e : ℤ) => c (i + (e : ZMod n)) = c i) have hS_sub : S ⊆ Icc (-3 : ℤ) 3 := filter_subset _ _
The map e ↦ i + e is a bijection between S and K, so |S| = |K|.
We apply Finset.card_bij. The map lands in K by definition of S (mem_filter). It is injective because if i + a = i + b for a, b ∈ [-3, 3], then (a : ZMod n) = (b : ZMod n); since n ≥ 10 and a, b ∈ [-3, 3], |a - b| ≤ 6 < n by abs_lt, so a = b by zmod_intCast_eq_intCast_iff_of_abs_sub_lt. It is surjective because any y ∈ K is either i (offset 0 ∈ S) or distinct from i, in which case hc gives adjacency in C_n^3, which by simple_graph_cycle_power_three_adj_iff means y = i + e with 1 ≤ |e| ≤ 3, so e ∈ S.
uses
Finset.card_bij,mem_filter,mem_univ,mem_Icc,add_left_cancel,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lt,Ne.symm,simple_graph_cycle_power_three_adj_iff,abs_lehave h_card_eq : #S = #K := by apply Finset.card_bij (s := S) (t := K) (fun e _ => i + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro a ha b hb hab have ha_icc := (mem_filter.mp ha).1 have hb_icc := (mem_filter.mp hb).1 rw [mem_Icc] at ha_icc hb_icc have hab_eq : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab have h_diff : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h_diff).mp hab_eq · intro y hy have hy_c : c y = c i := (mem_filter.mp hy).2 by_cases hyi : y = i · subst hyi; refine ⟨0, ?_, by simp⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, by simp⟩ · have hadj := hc i y (Ne.symm hyi) (hy_c.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn i y).mp hadj with ⟨e, he0, he3, rfl⟩ rw [abs_le] at he3 refine ⟨e, ?_, rfl⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, hy_c⟩
The diameter of S in ℤ is at most 3: for all a, b ∈ S, |a - b| ≤ 3.
If a = b, |a - b| = 0 ≤ 3. If a ≠ b, the vertices i + a and i + b are distinct in ZMod n (since |a - b| < n). Because both lie in K, they have the same color c(i), so by hc they are adjacent in C_n^3. By simple_graph_cycle_power_three_adj_iff, (i + b) - (i + a) = d in ZMod n for some non-zero integer d with |d| ≤ 3. Since |b - (a + d)| < n, zmod_intCast_eq_intCast_iff_of_abs_sub_lt forces b = a + d in ℤ, hence |a - b| = |d| ≤ 3.
uses
mem_filter,mem_Icc,add_left_cancel,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lt,simple_graph_cycle_power_three_adj_iff,abs_le,abs_neghave hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 3 := by intro a ha b hb have ha_icc := (mem_filter.mp ha).1 have hb_icc := (mem_filter.mp hb).1 have ha_c := (mem_filter.mp ha).2 have hb_c := (mem_filter.mp hb).2 rw [mem_Icc] at ha_icc hb_icc by_cases hab : a = b · subst hab; simp · have hne : (i + (a : ZMod n)) ≠ (i + (b : ZMod n)) := by intro heq' have hab_eq : (a : ZMod n) = (b : ZMod n) := add_left_cancel heq' have h_diff : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact hab ((zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h_diff).mp hab_eq) have hadj := hc (i + (a : ZMod n)) (i + (b : ZMod n)) hne (ha_c.trans hb_c.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn (i + (a : ZMod n)) (i + (b : ZMod n))).mp hadj with ⟨d, hd0, hd3, hdeq⟩ 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 : i + (b : ZMod n) = i + ((a + d : ℤ) : ZMod n) := by rw [hdeq]; push_cast; ring exact add_left_cancel this have h_bd := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n b (a + d) h_diff).mp h_eq' subst h_bd have : a - (a + d) = -d := by ring rw [this, abs_neg, abs_le] constructor <;> omega
Every element z ∈ K can be written as i + e for some e ∈ [-3, 3] ⊂ ℤ.
If z = i, we can take e = 0. If z ≠ i, the monochromatic condition implies z is adjacent to i in C_n^3, so by simple_graph_cycle_power_three_adj_iff there is some e ∈ ℤ with |e| ≤ 3 such that z = i + e.
uses
mem_filter,mem_Icc,Ne.symm,simple_graph_cycle_power_three_adj_iff,abs_lehave h_mem : ∀ z ∈ K, ∃ e ∈ Icc (-3 : ℤ) 3, z = i + (e : ZMod n) := by intro z hz rw [mem_filter] at hz by_cases hzi : z = i · subst hzi; refine ⟨0, by simp [mem_Icc], by simp⟩ · have hadj := hc i z (Ne.symm hzi) (hz.2.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn i z).mp hadj with ⟨e, he0, he3, rfl⟩ rw [abs_le] at he3 refine ⟨e, by rw [mem_Icc]; constructor <;> omega, rfl⟩
For e ∈ S and k ∈ {2, 3}, the vertex i + e + k has color c(i) if and only if e + k ∈ S.
If c(i + e + k) = c(i), then i + e + k ∈ K, so by h_mem it equals i + e' for some e' ∈ [-3, 3]. Since e ∈ [-3, 3] and k ∈ {2, 3}, |(e + k) - e'| ≤ 9 < n (abs_lt), so zmod_intCast_eq_intCast_iff_of_abs_sub_lt implies e + k = e' ∈ [-3, 3], which means e + k ∈ S. The converse holds by definition of S.
uses
mem_filter,mem_Icc,mem_univ,add_left_cancel,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lthave h_shift : ∀ e ∈ S, ∀ (k : ℤ), k = 2 ∨ k = 3 → (c (i + (e : ZMod n) + (k : ZMod n)) = c i ↔ e + k ∈ S) := by intro e he k hk have he_icc := (mem_filter.mp he).1 rw [mem_Icc] at he_icc rw [mem_filter, mem_Icc] have hk_cast : i + (e : ZMod n) + (k : ZMod n) = i + ((e + k : ℤ) : ZMod n) := by push_cast; ring rw [hk_cast] constructor · intro hc_shift have hz_mem : i + ((e + k : ℤ) : ZMod n) ∈ K := by rw [mem_filter]; exact ⟨mem_univ _, hc_shift⟩ rcases h_mem _ hz_mem with ⟨e', he', he'_eq⟩ have he_eq' : ((e + k : ℤ) : ZMod n) = (e' : ZMod n) := add_left_cancel he'_eq rw [mem_Icc] at he' have hdiff : |(e + k) - e'| < n := by rw [abs_lt] rcases hk with rfl | rfl <;> constructor <;> omega have h_eq : e + k = e' := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (e + k) e' hdiff).mp he_eq' subst h_eq exact ⟨he', hc_shift⟩ · intro h exact h.2
The sum of weights ∑_{x ∈ K} W(x) equals the integer weight of S.
Using sum_bij via the bijection e ↦ i + e, each term W(i + e) = 2 · [c(i+e) = c(i+e+3)] + [c(i+e) = c(i+e+2)] simplifies because c(i+e) = c(i). By the shift equivalence from h_shift (using Or.inl, Or.inr, eq_comm, if_congr), c(i+e) = c(i+e+k) is equivalent to e + k ∈ S for k ∈ {2, 3}. This matches the definition of integer weight of S.
uses
sum_bij,mem_filter,mem_univ,mem_Icc,add_left_cancel,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lt,Ne.symm,simple_graph_cycle_power_three_adj_iff,abs_le,Or.inr,Or.inl,eq_comm,if_congrhave h_sum : ∑ x ∈ K, W x = simple_graph_cycle_power_three_layer_weight_int_weight S := by unfold simple_graph_cycle_power_three_layer_weight_int_weight symm apply sum_bij (s := S) (t := K) (fun e _ => i + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro a ha b hb hab have ha_icc := (mem_filter.mp ha).1 have hb_icc := (mem_filter.mp hb).1 rw [mem_Icc] at ha_icc hb_icc have hab_eq : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab have h_diff : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h_diff).mp hab_eq · intro y hy have hy_c := (mem_filter.mp hy).2 by_cases hyi : y = i · subst hyi; refine ⟨0, ?_, by simp⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, by simp⟩ · have hadj := hc i y (Ne.symm hyi) (hy_c.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn i y).mp hadj with ⟨e, he0, he3, rfl⟩ rw [abs_le] at he3 refine ⟨e, ?_, rfl⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, hy_c⟩ · intro e he have he_c : c (i + (e : ZMod n)) = c i := (mem_filter.mp he).2 have h3 := h_shift e he 3 (Or.inr rfl) have h2 := h_shift e he 2 (Or.inl rfl) have h3_eq : (c (i + (e : ZMod n)) = c (i + (e : ZMod n) + 3)) ↔ (e + 3 ∈ S) := by rw [he_c] have : (3 : ZMod n) = ((3 : ℤ) : ZMod n) := by push_cast; rfl rw [this, eq_comm] exact h3 have h2_eq : (c (i + (e : ZMod n)) = c (i + (e : ZMod n) + 2)) ↔ (e + 2 ∈ S) := by rw [he_c] have : (2 : ZMod n) = ((2 : ℤ) : ZMod n) := by push_cast; rfl rw [this, eq_comm] exact h2 dsimp [W] rw [if_congr h3_eq rfl rfl, if_congr h2_eq rfl rfl]
The integer weight of S equals |S|.
From h_fiber_eq, the weight of fiber K equals |K|. Since the weight of K equals the integer weight of S (h_sum) and |K| = |S| (h_card_eq), the integer weight of S equals |S|.
have h_weight_eq : simple_graph_cycle_power_three_layer_weight_int_weight S = #S := by rw [← h_sum, h_card_eq] exact h_fiber_eq (c i)
0 ∈ S, so S is nonempty.
Since 0 ∈ [-3, 3] and c(i + 0) = c(i), 0 ∈ S by mem_filter and mem_Icc, showing S is nonempty.
uses
mem_filter,mem_Icchave h0_in_S : (0 : ℤ) ∈ S := by rw [mem_filter, mem_Icc] refine ⟨⟨by omega, by omega⟩, by simp⟩ have hne : S.Nonempty := ⟨0, h0_in_S⟩
There exists a ∈ S such that a + 3 ∈ S and S ⊆ [a, a + 3], which implies -3 ≤ a ≤ 0.
Applying the classification lemma simple_graph_cycle_power_three_layer_weight_decide_diam_tight to S ⊆ [-3, 3] (which has diameter at most 3, weight equal to cardinality, and is nonempty) yields an element a ∈ S with a + 3 ∈ S such that every x ∈ S satisfies a ≤ x ≤ a + 3. Since 0 ∈ S, we have a ≤ 0 ≤ a + 3, which implies -3 ≤ a ≤ 0, so d = (-a).toNat ≤ 3.
uses
simple_graph_cycle_power_three_layer_weight_decide_diam_tightrcases simple_graph_cycle_power_three_layer_weight_decide_diam_tight S hS_sub hdiam h_weight_eq hne with ⟨a, ha, ha3, h_bounds⟩ have ha_bounds := h_bounds 0 h0_in_S have ha_le_0 : a ≤ 0 := ha_bounds.1 have h_0_le_a3 : 0 ≤ a + 3 := ha_bounds.2 have h_d_le_3 : (-a).toNat ≤ 3 := by omega
For d = (-a).toNat ≤ 3, we have c(i - d) = c(i - d + 3).
Since 0 ≤ -a, Int.toNat_of_nonneg gives d = -a, so in ZMod n, i - d = i + a and i - d + 3 = i + a + 3 (using Int.cast_natCast, Int.cast_neg, and sub_neg_eq_add). Because a ∈ S and a + 3 ∈ S, both c(i + a) and c(i + a + 3) equal c(i), so they are equal to each other.
uses
Int.toNat_of_nonneg,Int.cast_natCast,Int.cast_neg,mem_filter,sub_neg_eq_addrefine ⟨(-a).toNat, h_d_le_3, ?_, ?_⟩ · have ha_eq : ((-a).toNat : ℤ) = -a := Int.toNat_of_nonneg (by omega) have ha_cast : (((-a).toNat : ℕ) : ZMod n) = - (a : ZMod n) := by rw [← Int.cast_natCast, ha_eq, Int.cast_neg] have ha_mem : c (i + (a : ZMod n)) = c i := (mem_filter.mp ha).2 have ha3_mem : c (i + ((a + 3 : ℤ) : ZMod n)) = c i := (mem_filter.mp ha3).2 have h1 : i - (((-a).toNat : ℕ) : ZMod n) = i + (a : ZMod n) := by rw [ha_cast, sub_neg_eq_add] have h2 : i - (((-a).toNat : ℕ) : ZMod n) + 3 = i + ((a + 3 : ℤ) : ZMod n) := by rw [h1]; push_cast; ring rw [h2, h1, ha_mem, ha3_mem]
The vertex i - d also satisfies c(i - d) = c(i).
As in the previous step, i - d = i + a in ZMod n. Since a ∈ S, by definition of S we have c(i + a) = c(i).
uses
Int.toNat_of_nonneg,Int.cast_natCast,Int.cast_neg,mem_filter,sub_neg_eq_add· have ha_eq : ((-a).toNat : ℤ) = -a := Int.toNat_of_nonneg (by omega) have ha_cast : (((-a).toNat : ℕ) : ZMod n) = - (a : ZMod n) := by rw [← Int.cast_natCast, ha_eq, Int.cast_neg] have ha_mem : c (i + (a : ZMod n)) = c i := (mem_filter.mp ha).2 have h1 : i - (((-a).toNat : ℕ) : ZMod n) = i + (a : ZMod n) := by rw [ha_cast, sub_neg_eq_add] rw [h1, ha_mem]
mem_powerset- A finset s belongs to the powerset of t if and only if s is a subset of t.
sum_fiberwise- Summing a function fiberwise over the fibers of a map g equals the sum over the entire set.
card_eq_sum_card_fiberwise- The cardinality of a finite set is the sum of the cardinalities of the fibers of a map on it.
mem_univ- Every element of a finite type belongs to the universal finset univ.
card_univ- The cardinality of univ equals the cardinality of the underlying finite type.
ZMod.card- The number of elements in ZMod n is n.
simple_graph_cycle_power_three_layer_weight_fiber_le- The sum of weights in any single color fiber is at most the cardinality of that fiber.
lt_of_le_of_ne- If a ≤ b and a ≠ b, then a < b.
sum_lt_sum- If f ≤ g everywhere on s and f < g at at least one element, the sum of f is strictly less than the sum of g.
filter_subset- Filtering a finset produces a subset of the original finset.
Finset.card_bij- A well-defined, injective, and surjective map between finite sets implies their cardinalities are equal.
mem_filter- An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
mem_Icc- An element belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
add_left_cancel- Left addition in an additive group is cancelable.
abs_lt- The absolute value |a| < b if and only if -b < a and a < b.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- For integers a, b with |a - b| < n, their casts to ZMod n are equal if and only if a = b.
Ne.symm- Inequality is symmetric: if a ≠ b then b ≠ a.
simple_graph_cycle_power_three_adj_iff- Two vertices u, v in ZMod n (with n ≥ 10) are adjacent in the cycle power C_n^3 if and only if v = u + e for some non-zero integer e with |e| ≤ 3.
abs_le- The absolute value |a| ≤ b if and only if -b ≤ a and a ≤ b.
abs_neg- The absolute value of -a equals the absolute value of a.
sum_bij- A bijection between two finite sets that preserves summands equates their sums.
Or.inr- Right disjunction introduction: if b holds, then a ∨ b holds.
Or.inl- Left disjunction introduction: if a holds, then a ∨ b holds.
eq_comm- Equality is symmetric: a = b is equivalent to b = a.
if_congr- Congruence rule for if-then-else expressions: if the conditions are equivalent and the branches agree, the conditionals are equal.
simple_graph_cycle_power_three_layer_weight_decide_diam_tight- For any nonempty subset S ⊆ [-3, 3] of diameter at most 3 whose integer weight equals |S|, there exists a ∈ S such that a + 3 ∈ S and S ⊆ [a, a + 3].
Int.toNat_of_nonneg- For a non-negative integer a, converting to ℕ and casting back to ℤ yields a.
Int.cast_natCast- Casting a natural number to ℤ and then to a ring equals casting directly to the ring.
Int.cast_neg- Casting the negation of an integer to a ring yields the negation of the cast.
sub_neg_eq_add- Subtracting the negation of b equals adding b.
- The auxiliary lemma simple_graph_cycle_power_three_layer_weight_decide_diam_tight is proved entirely by exhaustive computational evaluation (decide) over all subsets of {-3, ..., 3}.
- Several steps rely on omega to verify that integer differences remain strictly smaller than n (since n ≥ 10 and offsets lie in {-3, ..., 3}), justifying the equivalence between equality in ZMod n and equality in ℤ.
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 Finsettheorem simple_graph_cycle_power_three_layer_weight_decide_diam_tight (S : Finset ℤ) (hS : S ⊆ Icc (-3 : ℤ) 3) (hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 3) (heq : simple_graph_cycle_power_three_layer_weight_int_weight S = #S) (hne : S.Nonempty) : ∃ a ∈ S, a + 3 ∈ S ∧ ∀ x ∈ S, a ≤ x ∧ x ≤ a + 3 := by have h_univ : S ∈ (Icc (-3 : ℤ) 3).powerset := mem_powerset.mpr hS revert S hS hdiam heq hne h_univ decidetheorem simple_graph_cycle_power_three_layer_weight_eq_imp (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) (heq : ∑ 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) : ∀ i : ZMod n, ∃ d : ℕ, d ≤ 3 ∧ c (i - d) = c (i - d + 3) ∧ c (i - d) = c i := by intro i let W : ZMod n → ℕ := fun i => 2 * (if c i = c (i + 3) then 1 else 0) + (if c i = c (i + 2) then 1 else 0) have h_fiber := sum_fiberwise (s := univ) c W have h_card : (∑ j : ZMod n, #{x | c x = j}) = n := by have := card_eq_sum_card_fiberwise (s := univ) (t := univ) (f := c) (fun _ _ => mem_univ _) rw [← this, card_univ, ZMod.card] have h_le : ∀ j, ∑ x with c x = j, W x ≤ #{x | c x = j} := by intro j exact simple_graph_cycle_power_three_layer_weight_fiber_le n hn c hc j have h_sum_W : (∑ j : ZMod n, ∑ x with c x = j, W x) = ∑ j : ZMod n, #{x | c x = j} := by rw [h_fiber, heq, h_card] have h_fiber_eq : ∀ ℓ, ∑ x with c x = ℓ, W x = #{x | c x = ℓ} := by intro ℓ by_contra hne have hlt : (∑ x with c x = ℓ, W x) < #{x | c x = ℓ} := lt_of_le_of_ne (h_le ℓ) hne have h_sum_lt := sum_lt_sum (s := univ) (fun j _ => h_le j) ⟨ℓ, mem_univ ℓ, hlt⟩ omega let K := univ.filter (fun x => c x = c i) let S : Finset ℤ := (Icc (-3 : ℤ) 3).filter (fun (e : ℤ) => c (i + (e : ZMod n)) = c i) have hS_sub : S ⊆ Icc (-3 : ℤ) 3 := filter_subset _ _ have h_card_eq : #S = #K := by apply Finset.card_bij (s := S) (t := K) (fun e _ => i + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro a ha b hb hab have ha_icc := (mem_filter.mp ha).1 have hb_icc := (mem_filter.mp hb).1 rw [mem_Icc] at ha_icc hb_icc have hab_eq : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab have h_diff : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h_diff).mp hab_eq · intro y hy have hy_c : c y = c i := (mem_filter.mp hy).2 by_cases hyi : y = i · subst hyi; refine ⟨0, ?_, by simp⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, by simp⟩ · have hadj := hc i y (Ne.symm hyi) (hy_c.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn i y).mp hadj with ⟨e, he0, he3, rfl⟩ rw [abs_le] at he3 refine ⟨e, ?_, rfl⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, hy_c⟩ have hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 3 := by intro a ha b hb have ha_icc := (mem_filter.mp ha).1 have hb_icc := (mem_filter.mp hb).1 have ha_c := (mem_filter.mp ha).2 have hb_c := (mem_filter.mp hb).2 rw [mem_Icc] at ha_icc hb_icc by_cases hab : a = b · subst hab; simp · have hne : (i + (a : ZMod n)) ≠ (i + (b : ZMod n)) := by intro heq' have hab_eq : (a : ZMod n) = (b : ZMod n) := add_left_cancel heq' have h_diff : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact hab ((zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h_diff).mp hab_eq) have hadj := hc (i + (a : ZMod n)) (i + (b : ZMod n)) hne (ha_c.trans hb_c.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn (i + (a : ZMod n)) (i + (b : ZMod n))).mp hadj with ⟨d, hd0, hd3, hdeq⟩ 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 : i + (b : ZMod n) = i + ((a + d : ℤ) : ZMod n) := by rw [hdeq]; push_cast; ring exact add_left_cancel this have h_bd := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n b (a + d) h_diff).mp h_eq' subst h_bd have : a - (a + d) = -d := by ring rw [this, abs_neg, abs_le] constructor <;> omega have h_mem : ∀ z ∈ K, ∃ e ∈ Icc (-3 : ℤ) 3, z = i + (e : ZMod n) := by intro z hz rw [mem_filter] at hz by_cases hzi : z = i · subst hzi; refine ⟨0, by simp [mem_Icc], by simp⟩ · have hadj := hc i z (Ne.symm hzi) (hz.2.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn i z).mp hadj with ⟨e, he0, he3, rfl⟩ rw [abs_le] at he3 refine ⟨e, by rw [mem_Icc]; constructor <;> omega, rfl⟩ have h_shift : ∀ e ∈ S, ∀ (k : ℤ), k = 2 ∨ k = 3 → (c (i + (e : ZMod n) + (k : ZMod n)) = c i ↔ e + k ∈ S) := by intro e he k hk have he_icc := (mem_filter.mp he).1 rw [mem_Icc] at he_icc rw [mem_filter, mem_Icc] have hk_cast : i + (e : ZMod n) + (k : ZMod n) = i + ((e + k : ℤ) : ZMod n) := by push_cast; ring rw [hk_cast] constructor · intro hc_shift have hz_mem : i + ((e + k : ℤ) : ZMod n) ∈ K := by rw [mem_filter]; exact ⟨mem_univ _, hc_shift⟩ rcases h_mem _ hz_mem with ⟨e', he', he'_eq⟩ have he_eq' : ((e + k : ℤ) : ZMod n) = (e' : ZMod n) := add_left_cancel he'_eq rw [mem_Icc] at he' have hdiff : |(e + k) - e'| < n := by rw [abs_lt] rcases hk with rfl | rfl <;> constructor <;> omega have h_eq : e + k = e' := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (e + k) e' hdiff).mp he_eq' subst h_eq exact ⟨he', hc_shift⟩ · intro h exact h.2 have h_sum : ∑ x ∈ K, W x = simple_graph_cycle_power_three_layer_weight_int_weight S := by unfold simple_graph_cycle_power_three_layer_weight_int_weight symm apply sum_bij (s := S) (t := K) (fun e _ => i + (e : ZMod n)) · intro e he rw [mem_filter] exact ⟨mem_univ _, (mem_filter.mp he).2⟩ · intro a ha b hb hab have ha_icc := (mem_filter.mp ha).1 have hb_icc := (mem_filter.mp hb).1 rw [mem_Icc] at ha_icc hb_icc have hab_eq : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab have h_diff : |a - b| < n := by rw [abs_lt]; constructor <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b h_diff).mp hab_eq · intro y hy have hy_c := (mem_filter.mp hy).2 by_cases hyi : y = i · subst hyi; refine ⟨0, ?_, by simp⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, by simp⟩ · have hadj := hc i y (Ne.symm hyi) (hy_c.symm) rcases (simple_graph_cycle_power_three_adj_iff n hn i y).mp hadj with ⟨e, he0, he3, rfl⟩ rw [abs_le] at he3 refine ⟨e, ?_, rfl⟩ rw [mem_filter, mem_Icc]; refine ⟨⟨by omega, by omega⟩, hy_c⟩ · intro e he have he_c : c (i + (e : ZMod n)) = c i := (mem_filter.mp he).2 have h3 := h_shift e he 3 (Or.inr rfl) have h2 := h_shift e he 2 (Or.inl rfl) have h3_eq : (c (i + (e : ZMod n)) = c (i + (e : ZMod n) + 3)) ↔ (e + 3 ∈ S) := by rw [he_c] have : (3 : ZMod n) = ((3 : ℤ) : ZMod n) := by push_cast; rfl rw [this, eq_comm] exact h3 have h2_eq : (c (i + (e : ZMod n)) = c (i + (e : ZMod n) + 2)) ↔ (e + 2 ∈ S) := by rw [he_c] have : (2 : ZMod n) = ((2 : ℤ) : ZMod n) := by push_cast; rfl rw [this, eq_comm] exact h2 dsimp [W] rw [if_congr h3_eq rfl rfl, if_congr h2_eq rfl rfl] have h_weight_eq : simple_graph_cycle_power_three_layer_weight_int_weight S = #S := by rw [← h_sum, h_card_eq] exact h_fiber_eq (c i) have h0_in_S : (0 : ℤ) ∈ S := by rw [mem_filter, mem_Icc] refine ⟨⟨by omega, by omega⟩, by simp⟩ have hne : S.Nonempty := ⟨0, h0_in_S⟩ rcases simple_graph_cycle_power_three_layer_weight_decide_diam_tight S hS_sub hdiam h_weight_eq hne with ⟨a, ha, ha3, h_bounds⟩ have ha_bounds := h_bounds 0 h0_in_S have ha_le_0 : a ≤ 0 := ha_bounds.1 have h_0_le_a3 : 0 ≤ a + 3 := ha_bounds.2 have h_d_le_3 : (-a).toNat ≤ 3 := by omega refine ⟨(-a).toNat, h_d_le_3, ?_, ?_⟩ · have ha_eq : ((-a).toNat : ℤ) = -a := Int.toNat_of_nonneg (by omega) have ha_cast : (((-a).toNat : ℕ) : ZMod n) = - (a : ZMod n) := by rw [← Int.cast_natCast, ha_eq, Int.cast_neg] have ha_mem : c (i + (a : ZMod n)) = c i := (mem_filter.mp ha).2 have ha3_mem : c (i + ((a + 3 : ℤ) : ZMod n)) = c i := (mem_filter.mp ha3).2 have h1 : i - (((-a).toNat : ℕ) : ZMod n) = i + (a : ZMod n) := by rw [ha_cast, sub_neg_eq_add] have h2 : i - (((-a).toNat : ℕ) : ZMod n) + 3 = i + ((a + 3 : ℤ) : ZMod n) := by rw [h1]; push_cast; ring rw [h2, h1, ha_mem, ha3_mem] · have ha_eq : ((-a).toNat : ℤ) = -a := Int.toNat_of_nonneg (by omega) have ha_cast : (((-a).toNat : ℕ) : ZMod n) = - (a : ZMod n) := by rw [← Int.cast_natCast, ha_eq, Int.cast_neg] have ha_mem : c (i + (a : ZMod n)) = c i := (mem_filter.mp ha).2 have h1 : i - (((-a).toNat : ℕ) : ZMod n) = i + (a : ZMod n) := by rw [ha_cast, sub_neg_eq_add] rw [h1, ha_mem]