AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_three_layer_weight_eq_imp

theoremverified

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
Used by 1

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}.

  1. 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.

    lines 9–11

    uses mem_powerset

      have h_univ : S ∈ (Icc (-3 : ℤ) 3).powerset := mem_powerset.mpr hS
      revert S hS hdiam heq hne h_univ
      decide
  2. 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.

    lines 19–20

      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)
  3. 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.

    lines 21–24

    uses sum_fiberwise, card_eq_sum_card_fiberwise, mem_univ, card_univ, ZMod.card

      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]
  4. 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.

    lines 25–29

    uses simple_graph_cycle_power_three_layer_weight_fiber_le

      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]
  5. 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.

    lines 30–35

    uses lt_of_le_of_ne, sum_lt_sum, mem_univ

      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
  6. 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].

    lines 36–38

    uses filter_subset

      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 _ _
  7. 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.

    lines 39–61

    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_le

      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⟩
  8. 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.

    lines 62–90

    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_neg

      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
  9. 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.

    lines 91–99

    uses mem_filter, mem_Icc, Ne.symm, simple_graph_cycle_power_three_adj_iff, abs_le

      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⟩
  10. 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.

    lines 100–122

    uses mem_filter, mem_Icc, mem_univ, add_left_cancel, abs_lt, zmod_intCast_eq_intCast_iff_of_abs_sub_lt

      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
  11. 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.

    lines 123–163

    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_congr

      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]
  12. 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|.

    lines 164–166

      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)
  13. 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.

    lines 167–170

    uses mem_filter, mem_Icc

      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⟩
  14. 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.

    lines 171–176

    uses simple_graph_cycle_power_three_layer_weight_decide_diam_tight

      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
  15. 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.

    lines 177–187

    uses Int.toNat_of_nonneg, Int.cast_natCast, Int.cast_neg, mem_filter, sub_neg_eq_add

      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]
  16. 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).

    lines 188–194

    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.

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

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]
See it in the graphDiscuss this resultChallenge it