simple_graph_cycle_power_dyadic_layer_weight_le
In any clique labelling of a cycle power with dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, the total layer weight (two for endpoint-distance pairs, one for other dyadic long distances) is at most n.
Statement
theorem simple_graph_cycle_power_dyadic_layer_weight_le (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) : (∑ i : ZMod n, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) ≤ n
- Source
- Uniform weighted-cover reduction for OP-205 / RT-1 following arXiv:2610.15635. This is the arbitrary-bandwidth analogue of the proved k=3 and k=7 layer-weight helpers; no research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_clique_arcFor n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the…
- cycle_power_dyadic_int_weight_le_cardFor a finite integer set of diameter at most 2^m-1, weight its endpoint-distance pairs by two and its other dyadic long-distance pairs by…
- 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.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
- Used by 4
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
- simple_graph_cycle_power_dyadic_cover_card_boundFor dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, every equivalence cover of the cycle power uses at least m+1…
- simple_graph_cycle_power_dyadic_cover_class_spanningEvery label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class…
- simple_graph_cycle_power_dyadic_cover_tight_long_edgesIn an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge…
The proof, explained
The proof proceeds by partitioning the vertices of the cycle into fibers of the labelling c (the sets of vertices sharing each label) and bounding the layer weight on each fiber individually. For any nonempty fiber F = c⁻¹(l), the hypothesis ensures that F is a clique in the cycle power graph, which by `simple_graph_cycle_power_clique_arc` must lie entirely within an arc of length 2^m - 1. Because n ≥ 3(2^m - 1) + 1, this arc does not wrap around the cycle, allowing F to be identified with a subset of integers T' ⊂ ℤ of diameter at most 2^m - 1 where dyadic jump conditions correspond exactly to integer shifts. Applying the integer bound `cycle_power_dyadic_int_weight_le_card` shows that the layer weight of each fiber is at most its cardinality |F|. Summing this bound over all labels yields a total weight of at most ∑_l |F_l| = n.
For a fixed label l, the fiber problem reduces to showing that the sum of the layer weight W over the fiber F = c⁻¹(l) is at most |F|.
We define F as the fiber of vertices in ℤ/nℤ with label l, and define W(i) as the layer weight at vertex i. Rewriting the goal using these definitions restates the inequality as ∑_{i ∈ F} W(i) ≤ |F|.
classical set F := Finset.univ.filter (fun i : ZMod n => c i = l) with hFdef set W : ZMod n → ℕ := fun i => 2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) with hWdef change (∑ i ∈ F, W i) ≤ F.card
We split into cases depending on whether the fiber F is nonempty.
If F is empty, the sum and cardinality are both 0. We first analyze the primary case where F is nonempty.
by_cases hne : F.NonemptyThe fiber F is a clique and is therefore contained in an arc of length 2^m - 1 starting at some vertex p ∈ F.
Since all vertices in F share the same label l, the coloring hypothesis hc implies that every pair of distinct vertices in F is adjacent in the cycle power graph, meaning F is a clique. Since n ≥ 3(2^m - 1) + 1, `simple_graph_cycle_power_clique_arc` guarantees that F is contained in an arc: there exists p ∈ F such that every u ∈ F can be expressed as p + a with a ≤ 2^m - 1.
uses
simple_graph_cycle_power_clique_arc,Finset.mem_filter,Finset.mem_univ,true_and· obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn F hne (by intro u hu v hv huv rw [hFdef] at hu hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu hv exact hc u v huv (by rw [hu, hv]))
The fiber F is parameterized by natural offsets T ⊆ {0, ..., 2^m - 1} and integer offsets T' ⊂ ℤ.
We define T as the set of offsets a < 2^m such that p + a ∈ F, and T' as its cast into ℤ. Since m ≥ 1 and n ≥ 3(2^m - 1) + 1, we establish several arithmetic bounds: 2^m - 1 < n and 2(2^m - 1) < n, ensuring no modular wraparound occurs on the arc. We also verify that membership of an integer in T' is equivalent to its underlying natural number belonging to T.
uses
Nat.one_lt_two_pow,Nat.cast_sub,Finset.mem_range,Finset.mem_image,Int.ofNat_inj.mpset T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a => p + (a : ZMod n) ∈ F) with hTdef set T' : Finset ℤ := T.image (fun a : ℕ => (a : ℤ)) with hT'def have h1 : 1 ≤ 2 ^ m := by have := Nat.one_lt_two_pow (by omega : m ≠ 0); omega have hKlt : 2 ^ m - 1 < n := by omega have h2Klt : 2 * (2 ^ m - 1) < n := by omega have hsub : ((2 ^ m - 1 : ℕ) : ℤ) = (2 ^ m : ℤ) - 1 := by rw [Nat.cast_sub h1]; norm_num have hmemF : ∀ u : ZMod n, u ∈ F ↔ c u = l := by intro u; rw [hFdef]; simp have hpF' : c p = l := (hmemF p).mp hpF have hW' : ∀ i : ZMod n, W i = 2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by intro i; rw [hWdef] have hT_mem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by intro a; rw [hTdef]; simp [Finset.mem_range] have hT'_mem : ∀ e : ℕ, ((e : ℤ) ∈ T') ↔ e ∈ T := by intro e rw [hT'def, Finset.mem_image] constructor · rintro ⟨b, hb, hbe⟩ have hbe' : b = e := Int.ofNat_inj.mp hbe rwa [hbe'] at hb · intro he; exact ⟨e, he, rfl⟩
The map a ↦ p + a is a bijection from T to F, so |F| = |T| = |T'| and the sum over F equals the sum over T.
Since a, b < 2^m < n, p + a = p + b in ℤ/nℤ implies a = b in ℕ, so the shift map is injective on T. Because F is contained in the arc of length 2^m - 1 starting at p, F is precisely the image of T under this map. Consequently, |F| = |T| = |T'|, and the sum of W over F is identical to the sum of W(p + a) over a ∈ T.
uses
add_left_cancel,ZMod.natCast_eq_natCast_iff,Nat.ModEq.eq_of_lt_of_lt,Finset.card_image_of_injOn,Finset.sum_image,Int.ofNat_inj.mphave hinj : Set.InjOn (fun a : ℕ => p + (a : ZMod n)) ↑T := by intro a ha b hb hab have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1 have hb_lt : b < 2 ^ m := ((hT_mem b).mp hb).1 have hcast : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab have han : a < n := by omega have hbn : b < n := by omega rw [ZMod.natCast_eq_natCast_iff] at hcast exact Nat.ModEq.eq_of_lt_of_lt hcast han hbn have hF_eq : F = T.image (fun a : ℕ => p + (a : ZMod n)) := by ext u rw [Finset.mem_image] constructor · intro hu obtain ⟨a, ha_le, ha_eq⟩ := harc u hu refine ⟨a, ?_, ha_eq.symm⟩ rw [hT_mem] exact ⟨by omega, by rw [← ha_eq]; exact hu⟩ · rintro ⟨a, ha, rfl⟩ exact ((hT_mem a).mp ha).2 have hcard1 : F.card = T.card := by rw [hF_eq, Finset.card_image_of_injOn hinj] have hcard2 : T'.card = T.card := by rw [hT'def, Finset.card_image_of_injOn (by intro x _ y _ h; exact Int.ofNat_inj.mp h)] have hsum1 : ∑ i ∈ F, W i = ∑ a ∈ T, W (p + (a : ZMod n)) := by rw [hF_eq, Finset.sum_image hinj]
For any offset d < 2^m and a ∈ T, the condition c(p + a) = c(p + a + d) is equivalent to a + d ∈ T' in ℤ.
Because p + a ∈ F, c(p + a) = l, so the label condition holds if and only if p + (a + d) ∈ F. Since a < 2^m and d < 2^m, the sum a + d is strictly less than n. Since F is entirely contained in the arc from p, p + (a + d) ∈ F if and only if a + d ∈ T, which translates directly to (a : ℤ) + (d : ℤ) ∈ T'.
uses
add_left_cancel,ZMod.natCast_eq_natCast_iff,Nat.ModEq.eq_of_lt_of_lt,eq_comm,Nat.cast_add,if_congrhave hshift : ∀ a d : ℕ, a < 2 ^ m → d < 2 ^ m → (p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T) := by intro a d ha hd constructor · intro hmem obtain ⟨b, hb_le, hb_eq⟩ := harc _ hmem have hcast : ((a + d : ℕ) : ZMod n) = (b : ZMod n) := add_left_cancel hb_eq have hadn : a + d < n := by omega have hbn : b < n := by omega rw [ZMod.natCast_eq_natCast_iff] at hcast have hab : a + d = b := Nat.ModEq.eq_of_lt_of_lt hcast hadn hbn rw [hT_mem] exact ⟨by omega, hmem⟩ · intro hmem exact ((hT_mem (a + d)).mp hmem).2 have hif : ∀ d : ℕ, d < 2 ^ m → ∀ a ∈ T, (if c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) then (1:ℕ) else 0) = (if (a : ℤ) + (d : ℤ) ∈ T' then 1 else 0) := by intro d hd a ha have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1 have haF : p + (a : ZMod n) ∈ F := ((hT_mem a).mp ha).2 have hca : c (p + (a : ZMod n)) = l := (hmemF _).mp haF have hstep : p + (a : ZMod n) + (d : ZMod n) = p + ((a + d : ℕ) : ZMod n) := by push_cast; ring have hiff : c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) ↔ ((a : ℤ) + (d : ℤ) ∈ T') := by rw [hstep, hca] have e1 : l = c (p + ((a + d : ℕ) : ZMod n)) ↔ p + ((a + d : ℕ) : ZMod n) ∈ F := by rw [hmemF]; exact eq_comm have e2 : p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T := hshift a d ha_lt hd have e3 : (a + d) ∈ T ↔ ((a + d : ℕ) : ℤ) ∈ T' := (hT'_mem (a + d)).symm have e4 : ((a + d : ℕ) : ℤ) ∈ T' ↔ ((a : ℤ) + (d : ℤ)) ∈ T' := by rw [Nat.cast_add] exact e1.trans (e2.trans (e3.trans e4)) exact if_congr hiff rfl rfl
The fiber sum ∑_{a ∈ T} W(p + a) equals the integer layer weight of the set T' ⊂ ℤ.
Applying the indicator shift equivalence to the bandwidth d = 2^m - 1 and each dyadic offset d = 2^m - 2^j for j ≥ 1, each term W(p + a) matches the corresponding integer dyadic layer weight term at a. Reindexing the sum from T ⊂ ℕ to T' ⊂ ℤ expresses the fiber sum as the integer layer weight of T'.
uses
Nat.two_pow_pos,Finset.sum_congr,if_neg,Int.ofNat_inj.mp,Finset.sum_imagehave hterm : ∀ a ∈ T, W (p + (a : ZMod n)) = 2 * (if ((a : ℤ) + ((2 ^ m - 1 : ℕ) : ℤ)) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if ((a : ℤ) + ((2 ^ m - 2 ^ j : ℕ) : ℤ)) ∈ T' then 1 else 0) := by intro a ha rw [hW', hif (2 ^ m - 1) (by have := Nat.two_pow_pos m; omega) a ha] congr 1 apply Finset.sum_congr rfl intro j hj by_cases hj0 : j = 0 · simp [hj0] · rw [if_neg hj0, if_neg hj0] exact hif (2 ^ m - 2 ^ j) (by have := Nat.two_pow_pos m; have := Nat.two_pow_pos j; omega) a ha have hinjT' : Set.InjOn (fun a : ℕ => (a : ℤ)) ↑T := by intro x _ y _ h; exact Int.ofNat_inj.mp h have hsum2 : ∑ a ∈ T, W (p + (a : ZMod n)) = ∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) := by rw [Finset.sum_congr rfl hterm, ← Finset.sum_image (f := fun e => 2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) hinjT', ← hT'def]
The diameter of T' in ℤ is at most 2^m - 1, which bounds the fiber sum by |T'| = |F|.
Since every element e ∈ T' satisfies 0 ≤ e ≤ 2^m - 1, any two elements have distance |a - b| ≤ 2^m - 1. Applying `cycle_power_dyadic_int_weight_le_card` to T' shows that its integer dyadic layer weight is at most |T'|. Since |T'| = |F|, this proves ∑_{i ∈ F} W(i) ≤ |F| for nonempty fibers.
uses
abs_le,cycle_power_dyadic_int_weight_le_cardhave hdiam : ∀ a ∈ T', ∀ b ∈ T', |a - b| ≤ ((2 ^ m - 1 : ℕ) : ℤ) := by intro a ha b hb rw [hT'def, Finset.mem_image] at ha hb obtain ⟨a', ha', rfl⟩ := ha obtain ⟨b', hb', rfl⟩ := hb have ha'_lt : a' < 2 ^ m := ((hT_mem a').mp ha').1 have hb'_lt : b' < 2 ^ m := ((hT_mem b').mp hb').1 have ha'_le : (a' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by have : (a' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast ha'_lt omega have hb'_le : (b' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by have : (b' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast hb'_lt omega rw [abs_le, hsub] constructor <;> omega have hbound := cycle_power_dyadic_int_weight_le_card m hm T' hdiam rw [hsum1, hsum2] calc (∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0))) ≤ T'.card := hbound _ = F.card := by rw [hcard2, ← hcard1]
If the fiber F is empty, the inequality holds trivially as 0 ≤ 0.
When F = ∅, the sum over F is the empty sum (0) and the cardinality of F is 0, closing the remaining case of the fiber lemma.
uses
Finset.not_nonempty_iff_eq_empty· rw [Finset.not_nonempty_iff_eq_empty] at hne simp [hne]
Summing the fiber bounds over all labels proves that the total dyadic layer weight is at most n.
Using `Finset.sum_fiberwise`, we partition the sum over all vertices i ∈ ℤ/nℤ into a sum of fiber sums over all labels l ∈ ℤ/nℤ. Applying `simple_graph_cycle_power_dyadic_layer_weight_le_fiber` to each fiber via `Finset.sum_le_sum` bounds the total weight by the sum of fiber cardinalities. Finally, the sum of all fiber cardinalities equals the total number of vertices |ℤ/nℤ| = n, by `Finset.card_eq_sum_card_fiberwise` and `ZMod.card`.
uses
Finset.sum_fiberwise,Finset.sum_le_sum,simple_graph_cycle_power_dyadic_layer_weight_le_fiber,Finset.card_eq_sum_card_fiberwise,ZMod.cardclassical calc (∑ i : ZMod n, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = ∑ l : ZMod n, ∑ i ∈ Finset.univ.filter (fun i => c i = l), (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)) := by rw [Finset.sum_fiberwise] _ ≤ ∑ l : ZMod n, (Finset.univ.filter (fun i => c i = l)).card := Finset.sum_le_sum (fun l _ => simple_graph_cycle_power_dyadic_layer_weight_le_fiber m n hm hn c hc l) _ = n := by rw [← Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ) (f := c) (by intro x _; simp)] simp [ZMod.card]
simple_graph_cycle_power_clique_arc- In a cycle power graph on ℤ/nℤ with bandwidth k, if n ≥ 3k + 1, any nonempty clique K is contained in an arc of length k: there exists p ∈ K such that every u ∈ K can be written as p + a with a ≤ k.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set.
true_and- Conjunction with True simplifies to the proposition itself.
Nat.one_lt_two_pow- For any nonzero natural number n, 2^n > 1.
Nat.cast_sub- Subtraction of natural numbers casts to subtraction in an additive group with one, provided the subtrahend is at most the minuend.
Finset.mem_range- A natural number m belongs to the range {0, ..., n-1} if and only if m < n.
Finset.mem_image- An element is in the image of a finite set under f if and only if it is the image of some element in that set.
Int.ofNat_inj.mp- The canonical injection from natural numbers into integers is injective.
add_left_cancel- Left addition in a cancellation group is injective: a + b = a + c implies b = c.
ZMod.natCast_eq_natCast_iff- The natural number casts into ℤ/cℤ are equal if and only if the numbers are congruent modulo c.
Nat.ModEq.eq_of_lt_of_lt- If two natural numbers strictly less than m are congruent modulo m, they are equal.
Finset.card_image_of_injOn- The image of a finite set under a function injective on that set has the same cardinality as the set.
Finset.sum_image- A sum over the image of a set under an injective map equals the sum over the original set composed with the map.
eq_comm- Equality is symmetric.
Nat.cast_add- The cast of a sum of natural numbers into an additive monoid with one equals the sum of the casts.
if_congr- Two conditional expressions are equal if their conditions are equivalent and their corresponding branches are equal.
Nat.two_pow_pos- Any power of 2 is strictly positive.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on all elements.
if_neg- A conditional expression evaluates to its false branch when the condition is false.
abs_le- The absolute value |a| is at most b if and only if -b ≤ a ≤ b.
cycle_power_dyadic_int_weight_le_card- For any finite set of integers S with diameter at most 2^m - 1 (where m ≥ 1), the dyadic layer weight of S is at most |S|.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is empty.
Finset.sum_fiberwise- Summing a function over a set can be computed by partitioning into fibers of a map g and summing over all fibers.
Finset.sum_le_sum- If one summand is pointwise bounded by another on a finite set, the total sum is bounded by the sum of the upper bounds.
simple_graph_cycle_power_dyadic_layer_weight_le_fiber- In a clique labelling of a cycle power with bandwidth 2^m - 1 and n ≥ 3(2^m - 1) + 1, the dyadic layer weight summed over any single fiber c⁻¹(l) is at most the cardinality of that fiber.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum of the cardinalities of its fibers under any map.
ZMod.card- The number of elements in the ring ℤ/nℤ is n.
- The theorem is established by first proving an auxiliary lemma (`simple_graph_cycle_power_dyadic_layer_weight_le_fiber`) that bounds the layer weight on each individual fiber $c^{-1}(l)$ by the fiber's cardinality.
- The definition of the dyadic layer weight explicitly treats the $j = 0$ term as zero, so the dyadic sum runs effectively over $1 ≤ j < m$.
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.
private theorem simple_graph_cycle_power_dyadic_layer_weight_le_fiber (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) (l : ZMod n) : (∑ i ∈ Finset.univ.filter (fun i => c i = l), (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) ≤ (Finset.univ.filter (fun i => c i = l)).card := by classical set F := Finset.univ.filter (fun i : ZMod n => c i = l) with hFdef set W : ZMod n → ℕ := fun i => 2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) with hWdef change (∑ i ∈ F, W i) ≤ F.card by_cases hne : F.Nonempty · obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn F hne (by intro u hu v hv huv rw [hFdef] at hu hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu hv exact hc u v huv (by rw [hu, hv])) set T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a => p + (a : ZMod n) ∈ F) with hTdef set T' : Finset ℤ := T.image (fun a : ℕ => (a : ℤ)) with hT'def have h1 : 1 ≤ 2 ^ m := by have := Nat.one_lt_two_pow (by omega : m ≠ 0); omega have hKlt : 2 ^ m - 1 < n := by omega have h2Klt : 2 * (2 ^ m - 1) < n := by omega have hsub : ((2 ^ m - 1 : ℕ) : ℤ) = (2 ^ m : ℤ) - 1 := by rw [Nat.cast_sub h1]; norm_num have hmemF : ∀ u : ZMod n, u ∈ F ↔ c u = l := by intro u; rw [hFdef]; simp have hpF' : c p = l := (hmemF p).mp hpF have hW' : ∀ i : ZMod n, W i = 2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by intro i; rw [hWdef] have hT_mem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by intro a; rw [hTdef]; simp [Finset.mem_range] have hT'_mem : ∀ e : ℕ, ((e : ℤ) ∈ T') ↔ e ∈ T := by intro e rw [hT'def, Finset.mem_image] constructor · rintro ⟨b, hb, hbe⟩ have hbe' : b = e := Int.ofNat_inj.mp hbe rwa [hbe'] at hb · intro he; exact ⟨e, he, rfl⟩ have hinj : Set.InjOn (fun a : ℕ => p + (a : ZMod n)) ↑T := by intro a ha b hb hab have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1 have hb_lt : b < 2 ^ m := ((hT_mem b).mp hb).1 have hcast : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab have han : a < n := by omega have hbn : b < n := by omega rw [ZMod.natCast_eq_natCast_iff] at hcast exact Nat.ModEq.eq_of_lt_of_lt hcast han hbn have hF_eq : F = T.image (fun a : ℕ => p + (a : ZMod n)) := by ext u rw [Finset.mem_image] constructor · intro hu obtain ⟨a, ha_le, ha_eq⟩ := harc u hu refine ⟨a, ?_, ha_eq.symm⟩ rw [hT_mem] exact ⟨by omega, by rw [← ha_eq]; exact hu⟩ · rintro ⟨a, ha, rfl⟩ exact ((hT_mem a).mp ha).2 have hcard1 : F.card = T.card := by rw [hF_eq, Finset.card_image_of_injOn hinj] have hcard2 : T'.card = T.card := by rw [hT'def, Finset.card_image_of_injOn (by intro x _ y _ h; exact Int.ofNat_inj.mp h)] have hsum1 : ∑ i ∈ F, W i = ∑ a ∈ T, W (p + (a : ZMod n)) := by rw [hF_eq, Finset.sum_image hinj] have hshift : ∀ a d : ℕ, a < 2 ^ m → d < 2 ^ m → (p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T) := by intro a d ha hd constructor · intro hmem obtain ⟨b, hb_le, hb_eq⟩ := harc _ hmem have hcast : ((a + d : ℕ) : ZMod n) = (b : ZMod n) := add_left_cancel hb_eq have hadn : a + d < n := by omega have hbn : b < n := by omega rw [ZMod.natCast_eq_natCast_iff] at hcast have hab : a + d = b := Nat.ModEq.eq_of_lt_of_lt hcast hadn hbn rw [hT_mem] exact ⟨by omega, hmem⟩ · intro hmem exact ((hT_mem (a + d)).mp hmem).2 have hif : ∀ d : ℕ, d < 2 ^ m → ∀ a ∈ T, (if c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) then (1:ℕ) else 0) = (if (a : ℤ) + (d : ℤ) ∈ T' then 1 else 0) := by intro d hd a ha have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1 have haF : p + (a : ZMod n) ∈ F := ((hT_mem a).mp ha).2 have hca : c (p + (a : ZMod n)) = l := (hmemF _).mp haF have hstep : p + (a : ZMod n) + (d : ZMod n) = p + ((a + d : ℕ) : ZMod n) := by push_cast; ring have hiff : c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) ↔ ((a : ℤ) + (d : ℤ) ∈ T') := by rw [hstep, hca] have e1 : l = c (p + ((a + d : ℕ) : ZMod n)) ↔ p + ((a + d : ℕ) : ZMod n) ∈ F := by rw [hmemF]; exact eq_comm have e2 : p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T := hshift a d ha_lt hd have e3 : (a + d) ∈ T ↔ ((a + d : ℕ) : ℤ) ∈ T' := (hT'_mem (a + d)).symm have e4 : ((a + d : ℕ) : ℤ) ∈ T' ↔ ((a : ℤ) + (d : ℤ)) ∈ T' := by rw [Nat.cast_add] exact e1.trans (e2.trans (e3.trans e4)) exact if_congr hiff rfl rfl have hterm : ∀ a ∈ T, W (p + (a : ZMod n)) = 2 * (if ((a : ℤ) + ((2 ^ m - 1 : ℕ) : ℤ)) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if ((a : ℤ) + ((2 ^ m - 2 ^ j : ℕ) : ℤ)) ∈ T' then 1 else 0) := by intro a ha rw [hW', hif (2 ^ m - 1) (by have := Nat.two_pow_pos m; omega) a ha] congr 1 apply Finset.sum_congr rfl intro j hj by_cases hj0 : j = 0 · simp [hj0] · rw [if_neg hj0, if_neg hj0] exact hif (2 ^ m - 2 ^ j) (by have := Nat.two_pow_pos m; have := Nat.two_pow_pos j; omega) a ha have hinjT' : Set.InjOn (fun a : ℕ => (a : ℤ)) ↑T := by intro x _ y _ h; exact Int.ofNat_inj.mp h have hsum2 : ∑ a ∈ T, W (p + (a : ZMod n)) = ∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) := by rw [Finset.sum_congr rfl hterm, ← Finset.sum_image (f := fun e => 2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) hinjT', ← hT'def] have hdiam : ∀ a ∈ T', ∀ b ∈ T', |a - b| ≤ ((2 ^ m - 1 : ℕ) : ℤ) := by intro a ha b hb rw [hT'def, Finset.mem_image] at ha hb obtain ⟨a', ha', rfl⟩ := ha obtain ⟨b', hb', rfl⟩ := hb have ha'_lt : a' < 2 ^ m := ((hT_mem a').mp ha').1 have hb'_lt : b' < 2 ^ m := ((hT_mem b').mp hb').1 have ha'_le : (a' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by have : (a' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast ha'_lt omega have hb'_le : (b' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by have : (b' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast hb'_lt omega rw [abs_le, hsub] constructor <;> omega have hbound := cycle_power_dyadic_int_weight_le_card m hm T' hdiam rw [hsum1, hsum2] calc (∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0))) ≤ T'.card := hbound _ = F.card := by rw [hcard2, ← hcard1] · rw [Finset.not_nonempty_iff_eq_empty] at hne simp [hne]theorem simple_graph_cycle_power_dyadic_layer_weight_le (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) : (∑ i : ZMod n, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) ≤ n := by classical calc (∑ i : ZMod n, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = ∑ l : ZMod n, ∑ i ∈ Finset.univ.filter (fun i => c i = l), (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)) := by rw [Finset.sum_fiberwise] _ ≤ ∑ l : ZMod n, (Finset.univ.filter (fun i => c i = l)).card := Finset.sum_le_sum (fun l _ => simple_graph_cycle_power_dyadic_layer_weight_le_fiber m n hm hn c hc l) _ = n := by rw [← Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ) (f := c) (by intro x _; simp)] simp [ZMod.card]