simple_graph_cycle_power_seven_layer_weight_le
Let n ≥ 22 and let c label the vertices of C_n^7 so that every label class is a clique. Then Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4]) ≤ n, where i ~ j means same class: each class K contributes 2·(pairs at distance 7) + (pairs at distance 6) + (pairs at distance 4) ≤ |K|.
Statement
theorem simple_graph_cycle_power_seven_layer_weight_le (n : ℕ) [NeZero n] (hn : 22 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n 7).Adj u v) : ∑ i : ZMod n, (2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) ≤ n
- Source
- step toward the k = 7 case of OP-205 (arXiv:2610.15635), research thread RT-1, case k = 7 (k + 1 = 8): the weights (w_4, w_6, w_7) = (1, 1, 2) are the unique half-integral optimum of the class LP, with value 4 (exp 1084)
- 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_seven_adj_iffFor n ≥ 22, u and v are adjacent in C_n^7 iff v = u + e for an integer e with 0 < |e| ≤ 7.
- 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.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 3
- simple_graph_cycle_power_seven_cover_four_tightIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every pair at distance 7, 6 or 4 is covered by exactly one layer, and every…
- simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_sixLet c label the vertices of C_n^7 (n ≥ 22) so that every label class is a clique, with total weight Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~…
- simple_graph_cycle_power_seven_cover_four_layer_weight_eqIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every layer has weight exactly n: the sum over i of 2·[i ~ i+7] + [i ~ i+6] +…
The proof, explained
To bound the total weight ∑_i (2·[c(i) = c(i+7)] + [c(i) = c(i+6)] + [c(i) = c(i+4)]) ≤ n, the sum is decomposed fiberwise into contributions from each color class K = c⁻¹(ℓ). Because each color class is a clique in C_n^7 and n ≥ 22, fixing a base vertex in K embeds K bijectively into an integer set of offsets S ⊂ ℤ of diameter at most 7, where color matches correspond exactly to integer shifts. Shifting S to start at 0 places it inside {0, ..., 7}, where the weight inequality is verified by exhaustive computation on all 256 subsets. Summing the resulting fiber bounds weight(K) ≤ |K| across all color classes yields the bound n.
For every subset S ⊆ {0, 1, ..., 7} ⊂ ℤ, the integer weight of S is at most |S| automation
The interval {0, ..., 7} has 8 elements and therefore 256 subsets. The `decide` tactic checks the inequality by exhaustive finite evaluation of the weight definition on all 256 subsets.
decideThe integer weight function is invariant under translation: weight(T + d) = weight(T) for any finite set T ⊂ ℤ and d ∈ ℤ
Unfolding the definition of weight, the sum over T + d is transformed via `sum_map` into a sum over e ∈ T evaluated at e + d. For each chord shift k ∈ {7, 6, 4}, the condition (e + d) + k ∈ T + d is equivalent to e + k ∈ T. Substituting these equivalences shows that each summand at e + d matches the original summand at e, so the sums are equal.
uses
sum_map,addRightEmbedding_apply,mem_mapunfold simple_graph_cycle_power_seven_layer_weight_int_weight rw [sum_map] simp only [addRightEmbedding_apply] congr 1 ext e have h1 : e + d + 7 ∈ T.map (addRightEmbedding d) ↔ e + 7 ∈ T := by rw [mem_map] simp only [addRightEmbedding_apply] constructor · rintro ⟨a, ha, h⟩ have : a = e + 7 := by omega subst this; exact ha · intro h; exact ⟨e + 7, h, by omega⟩ have h2 : e + d + 6 ∈ T.map (addRightEmbedding d) ↔ e + 6 ∈ T := by rw [mem_map] simp only [addRightEmbedding_apply] constructor · rintro ⟨a, ha, h⟩ have : a = e + 6 := by omega subst this; exact ha · intro h; exact ⟨e + 6, h, by omega⟩ have h3 : e + d + 4 ∈ T.map (addRightEmbedding d) ↔ e + 4 ∈ T := by rw [mem_map] simp only [addRightEmbedding_apply] constructor · rintro ⟨a, ha, h⟩ have : a = e + 4 := by omega subst this; exact ha · intro h; exact ⟨e + 4, h, by omega⟩ simp only [h1, h2, h3]
Any finite set S ⊂ ℤ with diameter at most 7 satisfies weight(S) ≤ |S|
If S is empty, both weight and cardinality are 0. If S is nonempty, let m = min S and shift S by -m to obtain S' = S - m. Since m ≤ y and |y - m| ≤ 7 for all y ∈ S, every element of S' is between 0 and 7, so S' ⊆ {0, ..., 7}. By the exhaustive check `simple_graph_cycle_power_seven_layer_weight_decide_256`, weight(S') ≤ |S'|. Since weight and cardinality are invariant under shift (via `simple_graph_cycle_power_seven_layer_weight_int_weight_map_add` and `card_map`), weight(S) ≤ |S|.
uses
min'_mem,mem_map,addRightEmbedding_apply,mem_Icc,min'_le,abs_of_nonneg,simple_graph_cycle_power_seven_layer_weight_decide_256,mem_powerset,simple_graph_cycle_power_seven_layer_weight_int_weight_map_add,card_map,not_nonempty_iff_eq_emptyby_cases hne : S.Nonempty · set m := S.min' hne have hm : m ∈ S := min'_mem S hne set S' := S.map (addRightEmbedding (-m)) have hS' : S' ⊆ Icc 0 7 := by intro x hx rw [mem_map] at hx rcases hx with ⟨y, hy, rfl⟩ simp only [addRightEmbedding_apply, mem_Icc] have h1 : m ≤ y := min'_le S y hy have h2 : |y - m| ≤ 7 := hdiam y hy m hm constructor · omega · rw [abs_of_nonneg (by omega)] at h2 omega have h_le := simple_graph_cycle_power_seven_layer_weight_decide_256 S' (mem_powerset.mpr hS') rw [simple_graph_cycle_power_seven_layer_weight_int_weight_map_add S (-m)] at h_le rw [card_map] at h_le exact h_le · rw [not_nonempty_iff_eq_empty] at hne subst hne unfold simple_graph_cycle_power_seven_layer_weight_int_weight simp
For any nonempty color class K = c⁻¹(ℓ), fixing a base vertex m ∈ K, every u ∈ K can be written as m + e for an offset e in S = {e ∈ [-7, 7] ∩ ℤ | c(m + e) = ℓ}
If u = m, taking e = 0 gives the result. If u ≠ m, then c(u) = c(m) = ℓ, so by the clique hypothesis u and m are adjacent in C_n^7. By `simple_graph_cycle_power_seven_adj_iff`, u = m + e' for some nonzero integer offset e' with |e'| ≤ 7. Then e' ∈ [-7, 7] and c(m + e') = c(u) = ℓ, so e' ∈ S.
uses
mem_filter,mem_Icc,Ne.symm,simple_graph_cycle_power_seven_adj_iff,abs_casesset K := univ.filter (fun x => c x = ℓ) by_cases hK : K.Nonempty · rcases hK with ⟨m, hm⟩ have hcm : c m = ℓ := (mem_filter.mp hm).2 set S : Finset ℤ := (Icc (-7 : ℤ) 7).filter (fun e => c (m + (e : ZMod n)) = ℓ) have hsurj : ∀ u ∈ K, ∃ e ∈ S, m + (e : ZMod n) = u := by intro u hu rw [mem_filter] at hu by_cases hum : u = m · subst hum; use 0; refine ⟨?_, by simp⟩ rw [mem_filter, mem_Icc]; refine ⟨by omega, by simp [hcm]⟩ · have hadj := hc m u (Ne.symm hum) (by rw [hu.2, hcm]) rw [simple_graph_cycle_power_seven_adj_iff n hn] at hadj rcases hadj with ⟨e', -, he'_le, he'_eq⟩ use e' have he'_Icc : e' ∈ Icc (-7 : ℤ) 7 := by rw [mem_Icc] rcases abs_cases e' with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega refine ⟨?_, he'_eq.symm⟩ rw [mem_filter]; refine ⟨he'_Icc, ?_⟩ rw [← he'_eq, hu.2]
The offset representation e ↦ m + e from S to K is injective, and S has diameter at most 7
For injectivity, if m + e₁ = m + e₂ in ℤ/nℤ, then e₁ ≡ e₂ (mod n). Since e₁, e₂ ∈ [-7, 7], |e₁ - e₂| ≤ 14 < 22 ≤ n, which implies e₁ = e₂ by `zmod_intCast_eq_intCast_iff_of_abs_sub_lt`. For the diameter, for any distinct a, b ∈ S, the vertices m + a and m + b are distinct and have the same color ℓ, hence are adjacent in C_n^7. Thus their difference (m + b) - (m + a) ≡ b - a (mod n) is an offset e with |e| ≤ 7. Since |(b - a) - e| < n, `zmod_intCast_eq_intCast_iff_of_abs_sub_lt` gives b - a = e, so |a - b| = |e| ≤ 7.
uses
add_left_cancel,mem_filter,mem_Icc,abs_cases,zmod_intCast_eq_intCast_iff_of_abs_sub_lt,simple_graph_cycle_power_seven_adj_iffhave hinj : ∀ e1 ∈ S, ∀ e2 ∈ S, m + (e1 : ZMod n) = m + (e2 : ZMod n) → e1 = e2 := by intro e1 he1 e2 he2 h have heq : (e1 : ZMod n) = (e2 : ZMod n) := add_left_cancel h have he1_Icc := (mem_filter.mp he1).1 have he2_Icc := (mem_filter.mp he2).1 rw [mem_Icc] at he1_Icc he2_Icc have hnZ : (22 : ℤ) ≤ (n : ℤ) := by exact_mod_cast hn have hdiff : |e1 - e2| < (n : ℤ) := by rcases abs_cases (e1 - e2) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e1 e2 hdiff).mp heq have h_diam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 7 := by intro a ha b hb have ha_Icc := (mem_filter.mp ha).1 have hb_Icc := (mem_filter.mp hb).1 rw [mem_Icc] at ha_Icc hb_Icc by_cases hab : a = b · subst hab; simp · have hnZ : (22 : ℤ) ≤ (n : ℤ) := by exact_mod_cast hn have hdiff_ab : |a - b| < (n : ℤ) := by rcases abs_cases (a - b) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have hne : m + (a : ZMod n) ≠ m + (b : ZMod n) := by intro h apply hab exact hinj a ha b hb h have hadj := hc (m + (a : ZMod n)) (m + (b : ZMod n)) hne (by rw [(mem_filter.mp ha).2, (mem_filter.mp hb).2]) rw [simple_graph_cycle_power_seven_adj_iff n hn] at hadj rcases hadj with ⟨e, -, he_le, he_eq⟩ have heq : ((b - a : ℤ) : ZMod n) = (e : ZMod n) := by calc ((b - a : ℤ) : ZMod n) _ = (b : ZMod n) - (a : ZMod n) := by push_cast; rfl _ = (m + (b : ZMod n)) - (m + (a : ZMod n)) := by ring _ = (m + (a : ZMod n) + (e : ZMod n)) - (m + (a : ZMod n)) := by rw [he_eq] _ = (e : ZMod n) := by ring have he_cases : -7 ≤ e ∧ e ≤ 7 := by rcases abs_cases e with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have hdiff_sub : |(b - a) - e| < (n : ℤ) := by rcases abs_cases ((b - a) - e) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have he_eq2 : b - a = e := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (b - a) e hdiff_sub).mp heq rcases abs_cases (a - b) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega
For e ∈ S and d ∈ {0, ..., 7}, the vertices m + e and m + e + d share color ℓ if and only if e + d ∈ S
If c(m + e) = c(m + e + d), then m + e + d ∈ K. By surjectivity, m + e + d = m + e' for some e' ∈ S ⊆ [-7, 7]. Because e ∈ [-7, 7] and 0 ≤ d ≤ 7, the difference |(e + d) - e'| ≤ 14 - (-7) = 21 < n, so e + d = e' ∈ S by `zmod_intCast_eq_intCast_iff_of_abs_sub_lt`. Conversely, if e + d ∈ S, then c(m + e + d) = ℓ = c(m + e) by definition of S.
uses
mem_filter,mem_univ,add_left_cancel,mem_Icc,abs_cases,zmod_intCast_eq_intCast_iff_of_abs_sub_lthave h_shift : ∀ (d : ℤ) (_ : 0 ≤ d) (_ : d ≤ 7) (e : ℤ) (he_in_S : e ∈ S), c (m + (e : ZMod n)) = c (m + (e : ZMod n) + (d : ZMod n)) ↔ e + d ∈ S := by intro d hd_ge hd_le e he_in_S have he := mem_filter.mp he_in_S constructor · intro h have h_target : c (m + (e : ZMod n) + (d : ZMod n)) = ℓ := by rw [← h]; exact he.2 have hu_in_K : m + (e : ZMod n) + (d : ZMod n) ∈ K := by rw [mem_filter]; exact ⟨mem_univ _, h_target⟩ rcases hsurj (m + (e : ZMod n) + (d : ZMod n)) hu_in_K with ⟨e', he', he'_eq⟩ have heq_mod : (((e + d : ℤ) : ZMod n) : ZMod n) = (e' : ZMod n) := by have : m + (((e + d : ℤ) : ZMod n)) = m + (e' : ZMod n) := by calc m + (((e + d : ℤ) : ZMod n)) _ = m + (e : ZMod n) + (d : ZMod n) := by push_cast; ring _ = m + (e' : ZMod n) := he'_eq.symm exact add_left_cancel this have he_Icc := he.1 have he'_Icc := (mem_filter.mp he').1 rw [mem_Icc] at he_Icc he'_Icc have hnZ : (22 : ℤ) ≤ (n : ℤ) := by exact_mod_cast hn have hdiff : |(e + d) - e'| < (n : ℤ) := by rcases abs_cases ((e + d) - e') with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have heq_int : e + d = e' := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (e + d) e' hdiff).mp heq_mod subst heq_int exact he' · intro hed have hed_val := (mem_filter.mp hed).2 have h1 : c (m + (e : ZMod n)) = ℓ := he.2 have h2 : c (m + (e : ZMod n) + (d : ZMod n)) = ℓ := by have : m + (e : ZMod n) + (d : ZMod n) = m + ((e + d : ℤ) : ZMod n) := by push_cast; ring rw [this, hed_val] rw [h1, h2]
The contribution of each color class K = c⁻¹(ℓ) to the weight sum is at most |K|
When K is empty, the sum is trivially 0 ≤ 0. When K is nonempty, the bijection e ↦ m + e translates each indicator [c(i) = c(i + d)] on K (for d ∈ {7, 6, 4}) into the integer membership condition [e + d ∈ S] via `if_congr`. By `sum_bij`, the color match sum on K equals the integer weight of S, and by `card_bij`, |K| = |S|. Since S has diameter at most 7, `simple_graph_cycle_power_seven_layer_weight_le_card_of_diam` gives weight(S) ≤ |S| = |K|.
uses
sum_bij,mem_filter,mem_univ,if_congr,card_bij,simple_graph_cycle_power_seven_layer_weight_le_card_of_diam,not_nonempty_iff_eq_empty,sum_empty,card_emptyhave h_sum : ∑ i ∈ K, (2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) = simple_graph_cycle_power_seven_layer_weight_int_weight S := by unfold simple_graph_cycle_power_seven_layer_weight_int_weight have h_bij := sum_bij (s := S) (t := K) (f := fun e => 2 * (if e + 7 ∈ S then 1 else 0) + (if e + 6 ∈ S then 1 else 0) + (if e + 4 ∈ S then 1 else 0)) (g := fun i => 2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) (fun e _ => m + (e : ZMod n)) (by intro e he; rw [mem_filter]; exact ⟨mem_univ _, (mem_filter.mp he).2⟩) (by intro e1 he1 e2 he2 heq; exact hinj e1 he1 e2 he2 heq) (by intro u hu; rcases hsurj u hu with ⟨e, he, he_eq⟩; exact ⟨e, he, he_eq⟩) (by intro e he have h7 := h_shift 7 (by omega) (by omega) e he have h6 := h_shift 6 (by omega) (by omega) e he have h4 := h_shift 4 (by omega) (by omega) e he rw [if_congr h7.symm rfl rfl] rw [if_congr h6.symm rfl rfl] rw [if_congr h4.symm rfl rfl] push_cast rfl) exact h_bij.symm have h_card : #K = #S := by have := card_bij (s := S) (t := K) (fun e _ => m + (e : ZMod n)) (by intro e he; rw [mem_filter]; exact ⟨mem_univ _, (mem_filter.mp he).2⟩) (by intro e1 he1 e2 he2 heq; exact hinj e1 he1 e2 he2 heq) (by intro u hu; rcases hsurj u hu with ⟨e, he, he_eq⟩; exact ⟨e, he, he_eq⟩) exact this.symm rw [h_sum, h_card] exact simple_graph_cycle_power_seven_layer_weight_le_card_of_diam S h_diam · rw [not_nonempty_iff_eq_empty] at hK rw [hK, sum_empty, card_empty]
The total weight across all vertices in ℤ/nℤ is at most n
By `sum_fiberwise`, the total sum over vertices i ∈ ℤ/nℤ is partitioned into sums over each color fiber j = c(i). By `simple_graph_cycle_power_seven_layer_weight_fiber_le` and `sum_le_sum`, each fiber sum is bounded by the size of the fiber |c⁻¹(j)|. By `card_eq_sum_card_fiberwise` and `ZMod.card`, the sum of all fiber sizes is |ℤ/nℤ| = n. Linear arithmetic (`omega`) completes the inequality.
uses
sum_fiberwise,sum_le_sum,simple_graph_cycle_power_seven_layer_weight_fiber_le,card_eq_sum_card_fiberwise,mem_univ,card_univ,ZMod.cardhave h_fiber := sum_fiberwise (s := univ) c (fun i => 2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) rw [← h_fiber] have h_le : (∑ j : ZMod n, ∑ i with c i = j, (2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0))) ≤ ∑ j : ZMod n, #{i | c i = j} := by apply sum_le_sum intro ℓ _ exact simple_graph_cycle_power_seven_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
addRightEmbedding_apply- The embedding of addition on the right applies as (x ↦ x + d)
add_left_cancel- In an additive group, a + b = a + c implies b = c
abs_cases- For any linearly ordered additive group element a, either |a| = a and 0 ≤ a, or |a| = -a and a < 0
abs_of_nonneg- The absolute value of a non-negative element equals itself
card_bij- If there is a bijection between two finite sets, their cardinalities are equal
card_empty- The cardinality of the empty set is 0
card_eq_sum_card_fiberwise- The cardinality of a finite set s equals the sum of the cardinalities of the fibers of any function f on s
card_map- The cardinality of the image of a finite set under an embedding equals the cardinality of the original set
card_univ- The cardinality of the universal set of a finite type equals the cardinality of the type
if_congr- Congruence rule for conditionals: if the conditions are equivalent and the branches agree, the conditionals are equal
mem_Icc- An element x belongs to the closed interval [a, b] if and only if a ≤ x and x ≤ b
mem_filter- An element a belongs to filter p s if and only if a ∈ s and p a holds
mem_map- An element b belongs to the image map f s if and only if b = f a for some a ∈ s
mem_powerset- A finite set s belongs to the powerset of t if and only if s ⊆ t
mem_univ- Every element of a finite type belongs to its universal set univ
min'_le- Every element of a finite set is greater than or equal to the minimum of the set
min'_mem- The minimum of a nonempty finite set belongs to the set
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a
not_nonempty_iff_eq_empty- A set is not nonempty if and only if it is empty
simple_graph_cycle_power_seven_adj_iff- In the 7th cycle power graph on ℤ/nℤ with n ≥ 22, two vertices u and v are adjacent if and only if v = u + e for some nonzero integer e with |e| ≤ 7
simple_graph_cycle_power_seven_layer_weight_decide_256- Every subset of {0, ..., 7} ⊂ ℤ has integer weight at most its cardinality
simple_graph_cycle_power_seven_layer_weight_fiber_le- For each color class in a clique partition of the 7th cycle power graph with n ≥ 22, the sum of chord weights is at most the class size
simple_graph_cycle_power_seven_layer_weight_int_weight_map_add- The integer weight of any finite subset of ℤ is invariant under translation
simple_graph_cycle_power_seven_layer_weight_le_card_of_diam- Any finite subset of ℤ with diameter at most 7 has weight at most its cardinality
sum_bij- If a map restricts to a bijection between finite sets preserving summand values, their sums are equal
sum_empty- The sum of any function over the empty set is 0
sum_fiberwise- A sum over a finite set can be partitioned according to the fibers of a function on the indexing set
sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set, then the sum of f is at most the sum of g
sum_map- Summing a function over the image map e s under an embedding e equals the sum of f(e(x)) over x ∈ s
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- For integers a, b with |a - b| < n, their residues modulo n are equal if and only if a = b
ZMod.card- The cardinality of ℤ/nℤ is n
- In the base case lemma `simple_graph_cycle_power_seven_layer_weight_decide_256`, the inequality for all 256 subsets of {0, ..., 7} is proved by exhaustive evaluation in the kernel using `decide`.
- The hypothesis n ≥ 22 guarantees that any difference between offsets in [-7, 7] has absolute value at most 14 < 22 ≤ n, preventing modular wraparound and establishing the injectivity of the offset map.
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_seven_layer_weight_int_weight (T : Finset ℤ) : ℕ := ∑ e ∈ T, (2 * (if e + 7 ∈ T then 1 else 0) + (if e + 6 ∈ T then 1 else 0) + (if e + 4 ∈ T then 1 else 0))theorem simple_graph_cycle_power_seven_layer_weight_decide_256 : ∀ S ∈ (Icc (0 : ℤ) 7).powerset, simple_graph_cycle_power_seven_layer_weight_int_weight S ≤ #S := by decidelemma simple_graph_cycle_power_seven_layer_weight_int_weight_map_add (T : Finset ℤ) (d : ℤ) : simple_graph_cycle_power_seven_layer_weight_int_weight (T.map (addRightEmbedding d)) = simple_graph_cycle_power_seven_layer_weight_int_weight T := by unfold simple_graph_cycle_power_seven_layer_weight_int_weight rw [sum_map] simp only [addRightEmbedding_apply] congr 1 ext e have h1 : e + d + 7 ∈ T.map (addRightEmbedding d) ↔ e + 7 ∈ T := by rw [mem_map] simp only [addRightEmbedding_apply] constructor · rintro ⟨a, ha, h⟩ have : a = e + 7 := by omega subst this; exact ha · intro h; exact ⟨e + 7, h, by omega⟩ have h2 : e + d + 6 ∈ T.map (addRightEmbedding d) ↔ e + 6 ∈ T := by rw [mem_map] simp only [addRightEmbedding_apply] constructor · rintro ⟨a, ha, h⟩ have : a = e + 6 := by omega subst this; exact ha · intro h; exact ⟨e + 6, h, by omega⟩ have h3 : e + d + 4 ∈ T.map (addRightEmbedding d) ↔ e + 4 ∈ T := by rw [mem_map] simp only [addRightEmbedding_apply] constructor · rintro ⟨a, ha, h⟩ have : a = e + 4 := by omega subst this; exact ha · intro h; exact ⟨e + 4, h, by omega⟩ simp only [h1, h2, h3]lemma simple_graph_cycle_power_seven_layer_weight_le_card_of_diam (S : Finset ℤ) (hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 7) : simple_graph_cycle_power_seven_layer_weight_int_weight S ≤ #S := by by_cases hne : S.Nonempty · set m := S.min' hne have hm : m ∈ S := min'_mem S hne set S' := S.map (addRightEmbedding (-m)) have hS' : S' ⊆ Icc 0 7 := by intro x hx rw [mem_map] at hx rcases hx with ⟨y, hy, rfl⟩ simp only [addRightEmbedding_apply, mem_Icc] have h1 : m ≤ y := min'_le S y hy have h2 : |y - m| ≤ 7 := hdiam y hy m hm constructor · omega · rw [abs_of_nonneg (by omega)] at h2 omega have h_le := simple_graph_cycle_power_seven_layer_weight_decide_256 S' (mem_powerset.mpr hS') rw [simple_graph_cycle_power_seven_layer_weight_int_weight_map_add S (-m)] at h_le rw [card_map] at h_le exact h_le · rw [not_nonempty_iff_eq_empty] at hne subst hne unfold simple_graph_cycle_power_seven_layer_weight_int_weight simplemma simple_graph_cycle_power_seven_layer_weight_fiber_le (n : ℕ) [NeZero n] (hn : 22 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n 7).Adj u v) (ℓ : ZMod n) : ∑ i ∈ univ.filter (fun x => c x = ℓ), (2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) ≤ #(univ.filter (fun x => c x = ℓ)) := by set K := univ.filter (fun x => c x = ℓ) by_cases hK : K.Nonempty · rcases hK with ⟨m, hm⟩ have hcm : c m = ℓ := (mem_filter.mp hm).2 set S : Finset ℤ := (Icc (-7 : ℤ) 7).filter (fun e => c (m + (e : ZMod n)) = ℓ) have hsurj : ∀ u ∈ K, ∃ e ∈ S, m + (e : ZMod n) = u := by intro u hu rw [mem_filter] at hu by_cases hum : u = m · subst hum; use 0; refine ⟨?_, by simp⟩ rw [mem_filter, mem_Icc]; refine ⟨by omega, by simp [hcm]⟩ · have hadj := hc m u (Ne.symm hum) (by rw [hu.2, hcm]) rw [simple_graph_cycle_power_seven_adj_iff n hn] at hadj rcases hadj with ⟨e', -, he'_le, he'_eq⟩ use e' have he'_Icc : e' ∈ Icc (-7 : ℤ) 7 := by rw [mem_Icc] rcases abs_cases e' with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega refine ⟨?_, he'_eq.symm⟩ rw [mem_filter]; refine ⟨he'_Icc, ?_⟩ rw [← he'_eq, hu.2] have hinj : ∀ e1 ∈ S, ∀ e2 ∈ S, m + (e1 : ZMod n) = m + (e2 : ZMod n) → e1 = e2 := by intro e1 he1 e2 he2 h have heq : (e1 : ZMod n) = (e2 : ZMod n) := add_left_cancel h have he1_Icc := (mem_filter.mp he1).1 have he2_Icc := (mem_filter.mp he2).1 rw [mem_Icc] at he1_Icc he2_Icc have hnZ : (22 : ℤ) ≤ (n : ℤ) := by exact_mod_cast hn have hdiff : |e1 - e2| < (n : ℤ) := by rcases abs_cases (e1 - e2) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e1 e2 hdiff).mp heq have h_diam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ 7 := by intro a ha b hb have ha_Icc := (mem_filter.mp ha).1 have hb_Icc := (mem_filter.mp hb).1 rw [mem_Icc] at ha_Icc hb_Icc by_cases hab : a = b · subst hab; simp · have hnZ : (22 : ℤ) ≤ (n : ℤ) := by exact_mod_cast hn have hdiff_ab : |a - b| < (n : ℤ) := by rcases abs_cases (a - b) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have hne : m + (a : ZMod n) ≠ m + (b : ZMod n) := by intro h apply hab exact hinj a ha b hb h have hadj := hc (m + (a : ZMod n)) (m + (b : ZMod n)) hne (by rw [(mem_filter.mp ha).2, (mem_filter.mp hb).2]) rw [simple_graph_cycle_power_seven_adj_iff n hn] at hadj rcases hadj with ⟨e, -, he_le, he_eq⟩ have heq : ((b - a : ℤ) : ZMod n) = (e : ZMod n) := by calc ((b - a : ℤ) : ZMod n) _ = (b : ZMod n) - (a : ZMod n) := by push_cast; rfl _ = (m + (b : ZMod n)) - (m + (a : ZMod n)) := by ring _ = (m + (a : ZMod n) + (e : ZMod n)) - (m + (a : ZMod n)) := by rw [he_eq] _ = (e : ZMod n) := by ring have he_cases : -7 ≤ e ∧ e ≤ 7 := by rcases abs_cases e with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have hdiff_sub : |(b - a) - e| < (n : ℤ) := by rcases abs_cases ((b - a) - e) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have he_eq2 : b - a = e := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (b - a) e hdiff_sub).mp heq rcases abs_cases (a - b) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have h_shift : ∀ (d : ℤ) (_ : 0 ≤ d) (_ : d ≤ 7) (e : ℤ) (he_in_S : e ∈ S), c (m + (e : ZMod n)) = c (m + (e : ZMod n) + (d : ZMod n)) ↔ e + d ∈ S := by intro d hd_ge hd_le e he_in_S have he := mem_filter.mp he_in_S constructor · intro h have h_target : c (m + (e : ZMod n) + (d : ZMod n)) = ℓ := by rw [← h]; exact he.2 have hu_in_K : m + (e : ZMod n) + (d : ZMod n) ∈ K := by rw [mem_filter]; exact ⟨mem_univ _, h_target⟩ rcases hsurj (m + (e : ZMod n) + (d : ZMod n)) hu_in_K with ⟨e', he', he'_eq⟩ have heq_mod : (((e + d : ℤ) : ZMod n) : ZMod n) = (e' : ZMod n) := by have : m + (((e + d : ℤ) : ZMod n)) = m + (e' : ZMod n) := by calc m + (((e + d : ℤ) : ZMod n)) _ = m + (e : ZMod n) + (d : ZMod n) := by push_cast; ring _ = m + (e' : ZMod n) := he'_eq.symm exact add_left_cancel this have he_Icc := he.1 have he'_Icc := (mem_filter.mp he').1 rw [mem_Icc] at he_Icc he'_Icc have hnZ : (22 : ℤ) ≤ (n : ℤ) := by exact_mod_cast hn have hdiff : |(e + d) - e'| < (n : ℤ) := by rcases abs_cases ((e + d) - e') with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega have heq_int : e + d = e' := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (e + d) e' hdiff).mp heq_mod subst heq_int exact he' · intro hed have hed_val := (mem_filter.mp hed).2 have h1 : c (m + (e : ZMod n)) = ℓ := he.2 have h2 : c (m + (e : ZMod n) + (d : ZMod n)) = ℓ := by have : m + (e : ZMod n) + (d : ZMod n) = m + ((e + d : ℤ) : ZMod n) := by push_cast; ring rw [this, hed_val] rw [h1, h2] have h_sum : ∑ i ∈ K, (2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) = simple_graph_cycle_power_seven_layer_weight_int_weight S := by unfold simple_graph_cycle_power_seven_layer_weight_int_weight have h_bij := sum_bij (s := S) (t := K) (f := fun e => 2 * (if e + 7 ∈ S then 1 else 0) + (if e + 6 ∈ S then 1 else 0) + (if e + 4 ∈ S then 1 else 0)) (g := fun i => 2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) (fun e _ => m + (e : ZMod n)) (by intro e he; rw [mem_filter]; exact ⟨mem_univ _, (mem_filter.mp he).2⟩) (by intro e1 he1 e2 he2 heq; exact hinj e1 he1 e2 he2 heq) (by intro u hu; rcases hsurj u hu with ⟨e, he, he_eq⟩; exact ⟨e, he, he_eq⟩) (by intro e he have h7 := h_shift 7 (by omega) (by omega) e he have h6 := h_shift 6 (by omega) (by omega) e he have h4 := h_shift 4 (by omega) (by omega) e he rw [if_congr h7.symm rfl rfl] rw [if_congr h6.symm rfl rfl] rw [if_congr h4.symm rfl rfl] push_cast rfl) exact h_bij.symm have h_card : #K = #S := by have := card_bij (s := S) (t := K) (fun e _ => m + (e : ZMod n)) (by intro e he; rw [mem_filter]; exact ⟨mem_univ _, (mem_filter.mp he).2⟩) (by intro e1 he1 e2 he2 heq; exact hinj e1 he1 e2 he2 heq) (by intro u hu; rcases hsurj u hu with ⟨e, he, he_eq⟩; exact ⟨e, he, he_eq⟩) exact this.symm rw [h_sum, h_card] exact simple_graph_cycle_power_seven_layer_weight_le_card_of_diam S h_diam · rw [not_nonempty_iff_eq_empty] at hK rw [hK, sum_empty, card_empty]theorem simple_graph_cycle_power_seven_layer_weight_le (n : ℕ) [NeZero n] (hn : 22 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n 7).Adj u v) : ∑ i : ZMod n, (2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) ≤ n := by have h_fiber := sum_fiberwise (s := univ) c (fun i => 2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0)) rw [← h_fiber] have h_le : (∑ j : ZMod n, ∑ i with c i = j, (2 * (if c i = c (i + 7) then 1 else 0) + (if c i = c (i + 6) then 1 else 0) + (if c i = c (i + 4) then 1 else 0))) ≤ ∑ j : ZMod n, #{i | c i = j} := by apply sum_le_sum intro ℓ _ exact simple_graph_cycle_power_seven_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