AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_cover_tight_long_edges

theoremverified

In an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge is covered by exactly one layer.

Statement

theorem simple_graph_cycle_power_dyadic_cover_tight_long_edges
    (m n : ℕ) [NeZero n] (hm : 1 ≤ m)
    (hn : 3 * (2 ^ m - 1) + 1 ≤ n)
    (c : Fin (m + 1) → ZMod n → ZMod n)
    (hc : ∀ s u v, u ≠ v → c s u = c s v →
      (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)
    (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →
      ∃ s, c s u = c s v) :
    (∀ i : ZMod n, ∃! s : Fin (m + 1),
      c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n))) ∧
    ∀ j : ℕ, 1 ≤ j → j < m → ∀ i : ZMod n,
      ∃! s : Fin (m + 1),
        c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n))
Source
Uniform saturation step for OP-205 / RT-1 following arXiv:2610.15635. This is the arbitrary-bandwidth analogue of the exact-edge part of the proved k=3 and k=7 tight-cover helpers; no research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
Used by 5

The proof, explained

The proof is a double-counting and tightness argument on the total dyadic weight of the cover. By an established upper bound on individual layer weights, the total weight across all m+1 layers is at most (m+1) * n. On the other hand, since every edge must be covered by at least one layer, summing the contributions vertex by vertex yields at least 2 + (m - 1) = m + 1 per vertex, and hence at least (m+1) * n overall. The matching bounds force equality everywhere: every vertex achieves the minimum contribution, implying that each endpoint-distance edge and each long dyadic edge is covered by exactly one layer.

  1. Define dyadic chord offsets, coverage indicator functions, layer weights, and coverage multiplicity counters.

    We set d0 = 2^m - 1 and D(j) = 2^m - 2^j in ZMod n. For each layer s and vertex i, I0(s, i) indicates whether layer s covers (i, i + d0), and Ij(s, j, i) indicates whether it covers (i, i + D(j)). The weight W(s) assigns coefficient 2 to I0 and 1 to each Ij for j in J = {1, ..., m-1}, summed over all vertices i. Counters N0(i) and Nj(j, i) count how many layers cover the respective edges.

    lines 14–22

      classical
      let d0 : ZMod n := ((2 ^ m - 1 : ℕ) : ZMod n)
      let D : ℕ → ZMod n := fun j => ((2 ^ m - 2 ^ j : ℕ) : ZMod n)
      let I0 : Fin (m + 1) → ZMod n → ℕ := fun s i => if c s i = c s (i + d0) then 1 else 0
      let Ij : Fin (m + 1) → ℕ → ZMod n → ℕ := fun s j i => if c s i = c s (i + D j) then 1 else 0
      let W : Fin (m + 1) → ℕ := fun s => ∑ i : ZMod n, (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))
      let N0 : ZMod n → ℕ := fun i => ∑ s : Fin (m+1), I0 s i
      let Nj : ℕ → ZMod n → ℕ := fun j i => ∑ s : Fin (m+1), Ij s j i
      let J : Finset ℕ := (Finset.range m).filter (fun j => j ≠ 0)
  2. The maximum chord length 2^m - 1 is strictly less than n.

    Since m ≥ 1, we have 2 ≤ 2^m, so 2^m - 1 ≥ 1. Together with the hypothesis n ≥ 3(2^m - 1) + 1, linear arithmetic gives 2^m - 1 < n.

    lines 23–29

    uses Nat.pow_le_pow_right

      have hk_lt : 2 ^ m - 1 < n := by
        have hge : 1 ≤ 2 ^ m - 1 := by
          have h2 : 2 ≤ 2 ^ m := by
            calc 2 = 2 ^ 1 := by norm_num
              _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm
          omega
        omega
  3. For every vertex i, the pair (i, i + d0) is an edge in the cycle power graph.

    Since 2^m - 1 < n, vertices are adjacent in the cycle power graph of bandwidth 2^m - 1 if and only if their difference corresponds to a non-zero integer e with |e| ≤ 2^m - 1. Choosing e = 2^m - 1 gives a positive integer witness with |e| = 2^m - 1, establishing adjacency.

    lines 30–43

    uses simple_graph_cycle_power_adj_iff_of_bandwidth_lt, Nat.pow_le_pow_right, abs_of_nonneg

      have hadj0 : ∀ i : ZMod n,
          (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + d0) := by
        intro i
        rw [show d0 = ((2 ^ m - 1 : ℕ) : ZMod n) from rfl]
        rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt]
        refine ⟨((2 ^ m - 1 : ℕ) : ℤ), ?_, ?_, ?_⟩
        · have hge : 0 < 2 ^ m - 1 := by
            have h2 : 2 ≤ 2 ^ m := by
              calc 2 = 2 ^ 1 := by norm_num
                _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm
            omega
          omega
        · rw [abs_of_nonneg (by positivity : (0:ℤ) ≤ ((2 ^ m - 1 : ℕ) : ℤ))]
        · push_cast; ring
  4. For each j < m and every vertex i, the pair (i, i + D(j)) is an edge in the cycle power graph.

    For j < m, 2^j < 2^m, so 0 < 2^m - 2^j ≤ 2^m - 1 < n. The integer difference e = 2^m - 2^j is non-zero and has |e| ≤ 2^m - 1, establishing adjacency in the cycle power graph.

    lines 44–58

    uses simple_graph_cycle_power_adj_iff_of_bandwidth_lt, Nat.sub_pos_of_lt, Nat.pow_lt_pow_right, Nat.one_le_two_pow, abs_of_nonneg

      have hadjJ : ∀ (j : ℕ), j < m → ∀ i : ZMod n,
          (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + D j) := by
        intro j hj i
        rw [show D j = ((2 ^ m - 2 ^ j : ℕ) : ZMod n) from rfl]
        rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt]
        refine ⟨((2 ^ m - 2 ^ j : ℕ) : ℤ), ?_, ?_, ?_⟩
        · have hpos : 0 < 2 ^ m - 2 ^ j := Nat.sub_pos_of_lt (Nat.pow_lt_pow_right (by norm_num) hj)
          omega
        · have hle : 2 ^ m - 2 ^ j ≤ 2 ^ m - 1 := by
            have : 1 ≤ 2 ^ j := Nat.one_le_two_pow
            omega
          have hnn : (0:ℤ) ≤ ((2 ^ m - 2 ^ j : ℕ) : ℤ) := by positivity
          rw [abs_of_nonneg hnn]
          exact_mod_cast hle
        · push_cast; ring
  5. Every edge of distance d0 and every edge of distance D(j) for j ∈ J is covered by at least one layer.

    Because all these pairs are edges of the cycle power graph, the hypothesis hcov ensures that for each such edge there is some layer s making its endpoints monochromatic.

    lines 59–67

    uses Finset.mem_filter, Finset.mem_range

      have hcov0 : ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + d0) :=
        fun i => hcov i (i + d0) (hadj0 i)
      have hcovJ : ∀ j ∈ J, ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + D j) := by
        intro j hj i
        have hjm : j < m := by
          have hh : j ∈ (Finset.range m).filter (fun j => j ≠ 0) := hj
          rw [Finset.mem_filter, Finset.mem_range] at hh
          exact hh.1
        exact hcov i (i + D j) (hadjJ j hjm i)
  6. The sum of the weights of all m+1 layers is at most (m+1) * n.

    By simple_graph_cycle_power_dyadic_layer_weight_le, each layer has weight W(s) ≤ n. Summing over all m+1 layers in Fin (m+1) yields ∑ W(s) ≤ (m+1) * n.

    lines 68–73

    uses simple_graph_cycle_power_dyadic_layer_weight_le, Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul

      have hW_le : ∀ s : Fin (m+1), W s ≤ n := fun s =>
        simple_graph_cycle_power_dyadic_layer_weight_le m n hm hn (c s) (hc s)
      have hsum_le : ∑ s : Fin (m+1), W s ≤ (m+1) * n := by
        have h := Finset.sum_le_sum (fun s (_ : s ∈ (Finset.univ : Finset (Fin (m+1)))) => hW_le s)
        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] at h
        exact h
  7. Interchanging the sum over layers expresses the local weight at vertex i in terms of coverage counts, and |J| = m - 1.

    Distributing the sum over s ∈ Fin (m+1) across the terms expresses the total contribution at vertex i as 2 * N0(i) + ∑_{j ∈ range m, j ≠ 0} Nj(j, i). The set of non-zero offsets J has cardinality m - 1.

    lines 74–90

    uses Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_comm, Finset.sum_congr, Finset.sum_ite_irrel, if_neg, Finset.mem_range, Finset.filter_ne', Finset.card_erase_of_mem, Finset.card_range

      have hT_split : ∀ i : ZMod n,
          (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)))
          = 2 * N0 i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i) := by
        intro i
        rw [Finset.sum_add_distrib]
        rw [show (∑ s : Fin (m+1), 2 * I0 s i) = 2 * N0 i by rw [Finset.mul_sum]]
        congr 1
        rw [Finset.sum_comm]
        apply Finset.sum_congr rfl
        intro j hj
        rw [Finset.sum_ite_irrel]
        by_cases h : j = 0
        · simp [h]
        · simp only [if_neg h]; rfl
      have hJcard : J.card = m - 1 := by
        have hmem : 0 ∈ Finset.range m := by rw [Finset.mem_range]; omega
        simp only [J, Finset.filter_ne', Finset.card_erase_of_mem hmem, Finset.card_range]
  8. Every edge is covered at least once, and the layer contribution at each vertex is at least m + 1.

    Since each edge is covered by at least one layer, N0(i) ≥ 1 and Nj(j, i) ≥ 1 for all j ∈ J. Therefore, the sum across layers at vertex i satisfies 2 * N0(i) + ∑_{j ∈ J} Nj(j, i) ≥ 2(1) + |J|(1) = 2 + m - 1 = m + 1.

    lines 91–117

    uses Finset.single_le_sum, Nat.zero_le, Finset.mem_univ, Finset.sum_filter, Finset.sum_congr, Finset.sum_le_sum

      have hN0_ge : ∀ i, 1 ≤ N0 i := by
        intro i
        rcases hcov0 i with ⟨s, hs⟩
        have h := Finset.single_le_sum (f := fun x => I0 x i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s)
        rwa [show I0 s i = 1 by simp [I0, hs]] at h
      have hNJ_ge : ∀ j ∈ J, ∀ i, 1 ≤ Nj j i := by
        intro j hj i
        rcases hcovJ j hj i with ⟨s, hs⟩
        have h := Finset.single_le_sum (f := fun x => Ij x j i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s)
        rwa [show Ij s j i = 1 by simp [Ij, hs]] at h
      have hJsum : ∀ i,
          (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i)) = ∑ j ∈ J, Nj j i := by
        intro i
        change (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i))
          = ∑ j ∈ (Finset.range m).filter (fun j => j ≠ 0), Nj j i
        rw [Finset.sum_filter]
        apply Finset.sum_congr rfl
        intro j hj
        by_cases h : j = 0 <;> simp [h]
      have hT_ge : ∀ i, m + 1 ≤ ∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)) := by
        intro i
        rw [hT_split i, hJsum i]
        have hle : J.card ≤ ∑ j ∈ J, Nj j i := by
          have h := Finset.sum_le_sum (fun j hj => hNJ_ge j hj i)
          simpa using h
        have hn0 := hN0_ge i
        omega
  9. The total weight across all layers and vertices is exactly (m+1) * n.

    Exchanging the order of summation over vertices and layers shows that summing the local contributions over all n vertices equals ∑_s W(s). Since each vertex contributes at least m+1, the total sum is at least (m+1) * n. Combined with the upper bound ∑_s W(s) ≤ (m+1) * n, antisymmetry forces the sum to be exactly (m+1) * n.

    lines 118–130

    uses Finset.sum_comm, Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm, le_antisymm

      have hsumT : ∑ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)))
          = ∑ s : Fin (m+1), W s := by
        simp only [W]
        rw [Finset.sum_comm]
      have hsum_ge : (m+1) * n ≤ ∑ s : Fin (m+1), W s := by
        rw [← hsumT]
        have h := Finset.sum_le_sum (fun i (_ : i ∈ (Finset.univ : Finset (ZMod n))) => hT_ge i)
        have hc : ∑ _i : ZMod n, (m+1) = (m+1) * n := by
          rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm]
        rw [hc] at h
        exact h
      have hsum_eq : ∑ s : Fin (m+1), W s = (m+1) * n := le_antisymm hsum_le hsum_ge
      have hW_eq : ∀ s : Fin (m+1), W s = n := by
  10. Each layer has weight exactly n, and each vertex contributes exactly m + 1.

    If any layer had weight strictly less than n, the sum of weights would be strictly less than (m+1) * n, a contradiction. Similarly, if any vertex contributed strictly more than m+1, the total sum over all n vertices would strictly exceed (m+1) * n, another contradiction.

    lines 131–150

    uses lt_of_le_of_ne, Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul, Finset.sum_lt_sum, Finset.mem_univ, lt_irrefl, Ne.symm, ZMod.card, Nat.mul_comm

        intro s
        by_contra hne
        have hlt : W s < n := lt_of_le_of_ne (hW_le s) hne
        have hconst : ∑ _x : Fin (m+1), n = (m+1) * n := by
          rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul]
        have hstrict : ∑ x : Fin (m+1), W x < ∑ _x : Fin (m+1), n :=
          Finset.sum_lt_sum (fun x _ => hW_le x) ⟨s, Finset.mem_univ s, hlt⟩
        rw [hconst, hsum_eq] at hstrict
        exact lt_irrefl _ hstrict
      have hT_eq : ∀ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) = m + 1 := by
        intro i
        by_contra hne
        have hlt : m + 1 < (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) :=
          lt_of_le_of_ne (hT_ge i) (Ne.symm hne)
        have hconst : ∑ _i : ZMod n, (m+1) = (m+1) * n := by
          rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm]
        have hstrict : ∑ i : ZMod n, (m+1) < ∑ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) :=
          Finset.sum_lt_sum (fun i _ => hT_ge i) ⟨i, Finset.mem_univ i, hlt⟩
        rw [hconst, hsumT, hsum_eq] at hstrict
        exact lt_irrefl _ hstrict
  11. For every vertex i, N0(i) = 1, and for every j ∈ J, Nj(j, i) = 1.

    At each vertex i, 2 * N0(i) + ∑_{j ∈ J} Nj(j, i) = m + 1. Since N0(i) ≥ 1, Nj(j, i) ≥ 1, and |J| = m - 1, having N0(i) ≥ 2 would force the sum to be at least 4 + m - 1 = m + 3 > m + 1, so N0(i) = 1. Then ∑_{j ∈ J} Nj(j, i) = m - 1, meaning the sum of non-negative terms (Nj(j, i) - 1) is 0, which forces Nj(j, i) = 1 for every j ∈ J.

    lines 151–183

    uses Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_congr, Finset.sum_eq_zero_iff_of_nonneg

      have hN0_eq : ∀ i, N0 i = 1 := by
        intro i
        have hT := hT_eq i
        rw [hT_split i, hJsum i] at hT
        have hle : J.card ≤ ∑ j ∈ J, Nj j i := by
          have h := Finset.sum_le_sum (fun j hj => hNJ_ge j hj i)
          simpa using h
        have hn0 := hN0_ge i
        have hJc := hJcard
        omega
      have hNj_eq : ∀ j ∈ J, ∀ i, Nj j i = 1 := by
        intro j hj i
        have hT := hT_eq i
        rw [hT_split i, hJsum i] at hT
        have hn0 := hN0_eq i
        have hsum : ∑ x ∈ J, Nj x i = m - 1 := by
          have hJc := hJcard
          omega
        have hsub : ∑ x ∈ J, (Nj x i - 1) = 0 := by
          have h1 : ∑ x ∈ J, (Nj x i - 1) + ∑ x ∈ J, (1:ℕ) = ∑ x ∈ J, Nj x i := by
            rw [← Finset.sum_add_distrib]
            apply Finset.sum_congr rfl
            intro x hx
            have := hNJ_ge x hx i
            omega
          have hc1 : ∑ x ∈ J, (1:ℕ) = J.card := by simp
          have hJc := hJcard
          omega
        have hzero := (Finset.sum_eq_zero_iff_of_nonneg (s := J) (f := fun x => Nj x i - 1)
          (fun x hx => by have := hNJ_ge x hx i; omega)).mp hsub
        have := hzero j hj
        have := hNJ_ge j hj i
        omega
  12. If an indicator sum over Fin (m+1) equals 1, then exactly one element satisfies the predicate.

    The sum of the indicator over Fin (m+1) equals the cardinality of the filtered set {s | P s}. A finset has cardinality 1 if and only if it is a singleton {s}, which means there is a unique element satisfying P.

    lines 184–199

    uses Finset.card_filter, Finset.card_eq_one, Finset.ext_iff, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton

      have h_exists_unique : ∀ (P : Fin (m+1) → Prop) [DecidablePred P],
          (∑ s : Fin (m+1), (if P s then 1 else 0)) = 1 → ∃! s, P s := by
        intro P _ h
        have hcard : (Finset.univ.filter P).card = 1 := by
          have h1 : (∑ s : Fin (m+1), if P s then 1 else 0 : ℕ) = (Finset.univ.filter P).card := by
            rw [Finset.card_filter]
          rwa [← h1]
        rw [Finset.card_eq_one] at hcard
        rcases hcard with ⟨s, hs⟩
        use s
        have hp : ∀ x, P x ↔ x = s := by
          intro x
          have := Finset.ext_iff.mp hs x
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton] at this
          exact this
        exact ⟨(hp s).mpr rfl, fun x hx => (hp x).mp hx⟩
  13. Every endpoint-distance edge and every long dyadic edge is covered by a unique layer.

    For the endpoint-distance edges, N0(i) = 1 means the indicator sum is 1, so by the uniqueness lemma there is a unique layer s covering it. For any 1 ≤ j < m, j ∈ J and Nj(j, i) = 1 gives uniqueness of the covering layer.

    lines 200–210

    uses Finset.mem_filter, Finset.mem_range

      refine ⟨fun i => ?_, fun j hj1 hjm i => ?_⟩
      · have := hN0_eq i
        refine h_exists_unique (fun s => c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n))) ?_
        simpa [N0, I0, d0] using this
      · have hjJ : j ∈ J := by
          change j ∈ (Finset.range m).filter (fun j => j ≠ 0)
          rw [Finset.mem_filter, Finset.mem_range]
          exact ⟨hjm, by omega⟩
        have := hNj_eq j hjJ i
        refine h_exists_unique (fun s => c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n))) ?_
        simpa [Nj, Ij, D] using this
Nat.pow_le_pow_right
For a positive base n, i ≤ j implies n^i ≤ n^j.
simple_graph_cycle_power_adj_iff_of_bandwidth_lt
In the cycle power graph of bandwidth k < n, two vertices are adjacent if and only if their difference is a non-zero integer e with |e| ≤ k.
abs_of_nonneg
If an element is non-negative, its absolute value equals itself.
Nat.sub_pos_of_lt
If m < n for natural numbers, then n - m > 0.
Nat.pow_lt_pow_right
For base a > 1, exponent inequality m < n implies a^m < a^n.
Nat.one_le_two_pow
For any natural number n, 2^n ≥ 1.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_range
A natural number m belongs to Finset.range n if and only if m < n.
simple_graph_cycle_power_dyadic_layer_weight_le
Any single layer covering edges of the cycle power graph has total dyadic weight at most n.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finset, then the sum of f is at most the sum of g.
Finset.sum_const
The sum of a constant value b over a finset s equals |s| * b.
Finset.card_univ
The cardinality of the universal finset Finset.univ of a finite type equals the cardinality of the type.
Fintype.card_fin
The finite type Fin n has cardinality n.
Nat.nsmul_eq_mul
Scalar multiplication of a natural number by a count m • n equals m * n.
Finset.sum_add_distrib
The sum of a term-by-term addition over a finset distributes into the sum of each term.
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑ f(i) = ∑ (a * f(i)).
Finset.sum_comm
Double sums over finite sets can be interchanged.
Finset.sum_congr
Two finite sums are equal if their index sets and summands agree everywhere.
Finset.sum_ite_irrel
An if-then-else condition independent of the summation index can be factored outside the sum.
if_neg
If a proposition c is false, then if c then t else e simplifies to e.
Finset.filter_ne'
Filtering out an element b from a finset s yields s \ {b}.
Finset.card_erase_of_mem
Erasing an element present in a finset reduces its cardinality by 1.
Finset.card_range
The finset of numbers {0, ..., n - 1} has cardinality n.
Finset.single_le_sum
In a sum of non-negative terms over a finset, any single summand is at most the total sum.
Nat.zero_le
Every natural number is non-negative (0 ≤ n).
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.sum_filter
Summing over a filtered finset equals summing an indicator-weighted function over the original finset.
ZMod.card
The type ZMod n has cardinality n.
Nat.mul_comm
Multiplication of natural numbers is commutative (n * m = m * n).
le_antisymm
If a ≤ b and b ≤ a, then a = b.
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b.
Finset.sum_lt_sum
If f ≤ g everywhere and f(i) < g(i) at some element, then ∑ f < ∑ g.
lt_irrefl
Strict inequality is irreflexive: ¬(a < a).
Ne.symm
Inequality is symmetric: a ≠ b implies b ≠ a.
Finset.sum_eq_zero_iff_of_nonneg
A sum of non-negative terms equals 0 if and only if every term is 0.
Finset.card_filter
The cardinality of a filtered finset equals the sum of its indicator function.
Finset.card_eq_one
A finset has cardinality 1 if and only if it is a singleton {a}.
Finset.ext_iff
Two finsets are equal if and only if they contain the exact same elements.
true_and
The logical proposition True ∧ p is equivalent to p.
Finset.mem_singleton
An element b belongs to {a} if and only if b = a.

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

theorem simple_graph_cycle_power_dyadic_cover_tight_long_edges    (m n : ℕ) [NeZero n] (hm : 1 ≤ m)    (hn : 3 * (2 ^ m - 1) + 1 ≤ n)    (c : Fin (m + 1) → ZMod n → ZMod n)    (hc : ∀ s u v, u ≠ v → c s u = c s v →      (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)    (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →      ∃ s, c s u = c s v) :    (∀ i : ZMod n, ∃! s : Fin (m + 1),      c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n))) ∧    ∀ j : ℕ, 1 ≤ j → j < m → ∀ i : ZMod n,      ∃! s : Fin (m + 1),        c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) := by  classical  let d0 : ZMod n := ((2 ^ m - 1 : ℕ) : ZMod n)  let D : ℕ → ZMod n := fun j => ((2 ^ m - 2 ^ j : ℕ) : ZMod n)  let I0 : Fin (m + 1) → ZMod n → ℕ := fun s i => if c s i = c s (i + d0) then 1 else 0  let Ij : Fin (m + 1) → ℕ → ZMod n → ℕ := fun s j i => if c s i = c s (i + D j) then 1 else 0  let W : Fin (m + 1) → ℕ := fun s => ∑ i : ZMod n, (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))  let N0 : ZMod n → ℕ := fun i => ∑ s : Fin (m+1), I0 s i  let Nj : ℕ → ZMod n → ℕ := fun j i => ∑ s : Fin (m+1), Ij s j i  let J : Finset ℕ := (Finset.range m).filter (fun j => j ≠ 0)  have hk_lt : 2 ^ m - 1 < n := by    have hge : 1 ≤ 2 ^ m - 1 := by      have h2 : 2 ≤ 2 ^ m := by        calc 2 = 2 ^ 1 := by norm_num          _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm      omega    omega  have hadj0 : ∀ i : ZMod n,      (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + d0) := by    intro i    rw [show d0 = ((2 ^ m - 1 : ℕ) : ZMod n) from rfl]    rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt]    refine ⟨((2 ^ m - 1 : ℕ) : ℤ), ?_, ?_, ?_⟩    · have hge : 0 < 2 ^ m - 1 := by        have h2 : 2 ≤ 2 ^ m := by          calc 2 = 2 ^ 1 := by norm_num            _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm        omega      omega    · rw [abs_of_nonneg (by positivity : (0:ℤ) ≤ ((2 ^ m - 1 : ℕ) : ℤ))]    · push_cast; ring  have hadjJ : ∀ (j : ℕ), j < m → ∀ i : ZMod n,      (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + D j) := by    intro j hj i    rw [show D j = ((2 ^ m - 2 ^ j : ℕ) : ZMod n) from rfl]    rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt]    refine ⟨((2 ^ m - 2 ^ j : ℕ) : ℤ), ?_, ?_, ?_⟩    · have hpos : 0 < 2 ^ m - 2 ^ j := Nat.sub_pos_of_lt (Nat.pow_lt_pow_right (by norm_num) hj)      omega    · have hle : 2 ^ m - 2 ^ j ≤ 2 ^ m - 1 := by        have : 1 ≤ 2 ^ j := Nat.one_le_two_pow        omega      have hnn : (0:ℤ) ≤ ((2 ^ m - 2 ^ j : ℕ) : ℤ) := by positivity      rw [abs_of_nonneg hnn]      exact_mod_cast hle    · push_cast; ring  have hcov0 : ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + d0) :=    fun i => hcov i (i + d0) (hadj0 i)  have hcovJ : ∀ j ∈ J, ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + D j) := by    intro j hj i    have hjm : j < m := by      have hh : j ∈ (Finset.range m).filter (fun j => j ≠ 0) := hj      rw [Finset.mem_filter, Finset.mem_range] at hh      exact hh.1    exact hcov i (i + D j) (hadjJ j hjm i)  have hW_le : ∀ s : Fin (m+1), W s ≤ n := fun s =>    simple_graph_cycle_power_dyadic_layer_weight_le m n hm hn (c s) (hc s)  have hsum_le : ∑ s : Fin (m+1), W s ≤ (m+1) * n := by    have h := Finset.sum_le_sum (fun s (_ : s ∈ (Finset.univ : Finset (Fin (m+1)))) => hW_le s)    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] at h    exact h  have hT_split : ∀ i : ZMod n,      (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)))      = 2 * N0 i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i) := by    intro i    rw [Finset.sum_add_distrib]    rw [show (∑ s : Fin (m+1), 2 * I0 s i) = 2 * N0 i by rw [Finset.mul_sum]]    congr 1    rw [Finset.sum_comm]    apply Finset.sum_congr rfl    intro j hj    rw [Finset.sum_ite_irrel]    by_cases h : j = 0    · simp [h]    · simp only [if_neg h]; rfl  have hJcard : J.card = m - 1 := by    have hmem : 0 ∈ Finset.range m := by rw [Finset.mem_range]; omega    simp only [J, Finset.filter_ne', Finset.card_erase_of_mem hmem, Finset.card_range]  have hN0_ge : ∀ i, 1 ≤ N0 i := by    intro i    rcases hcov0 i with ⟨s, hs⟩    have h := Finset.single_le_sum (f := fun x => I0 x i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s)    rwa [show I0 s i = 1 by simp [I0, hs]] at h  have hNJ_ge : ∀ j ∈ J, ∀ i, 1 ≤ Nj j i := by    intro j hj i    rcases hcovJ j hj i with ⟨s, hs⟩    have h := Finset.single_le_sum (f := fun x => Ij x j i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s)    rwa [show Ij s j i = 1 by simp [Ij, hs]] at h  have hJsum : ∀ i,      (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i)) = ∑ j ∈ J, Nj j i := by    intro i    change (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i))      = ∑ j ∈ (Finset.range m).filter (fun j => j ≠ 0), Nj j i    rw [Finset.sum_filter]    apply Finset.sum_congr rfl    intro j hj    by_cases h : j = 0 <;> simp [h]  have hT_ge : ∀ i, m + 1 ≤ ∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)) := by    intro i    rw [hT_split i, hJsum i]    have hle : J.card ≤ ∑ j ∈ J, Nj j i := by      have h := Finset.sum_le_sum (fun j hj => hNJ_ge j hj i)      simpa using h    have hn0 := hN0_ge i    omega  have hsumT : ∑ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)))      = ∑ s : Fin (m+1), W s := by    simp only [W]    rw [Finset.sum_comm]  have hsum_ge : (m+1) * n ≤ ∑ s : Fin (m+1), W s := by    rw [← hsumT]    have h := Finset.sum_le_sum (fun i (_ : i ∈ (Finset.univ : Finset (ZMod n))) => hT_ge i)    have hc : ∑ _i : ZMod n, (m+1) = (m+1) * n := by      rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm]    rw [hc] at h    exact h  have hsum_eq : ∑ s : Fin (m+1), W s = (m+1) * n := le_antisymm hsum_le hsum_ge  have hW_eq : ∀ s : Fin (m+1), W s = n := by    intro s    by_contra hne    have hlt : W s < n := lt_of_le_of_ne (hW_le s) hne    have hconst : ∑ _x : Fin (m+1), n = (m+1) * n := by      rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul]    have hstrict : ∑ x : Fin (m+1), W x < ∑ _x : Fin (m+1), n :=      Finset.sum_lt_sum (fun x _ => hW_le x) ⟨s, Finset.mem_univ s, hlt⟩    rw [hconst, hsum_eq] at hstrict    exact lt_irrefl _ hstrict  have hT_eq : ∀ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) = m + 1 := by    intro i    by_contra hne    have hlt : m + 1 < (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) :=      lt_of_le_of_ne (hT_ge i) (Ne.symm hne)    have hconst : ∑ _i : ZMod n, (m+1) = (m+1) * n := by      rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm]    have hstrict : ∑ i : ZMod n, (m+1) < ∑ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) :=      Finset.sum_lt_sum (fun i _ => hT_ge i) ⟨i, Finset.mem_univ i, hlt⟩    rw [hconst, hsumT, hsum_eq] at hstrict    exact lt_irrefl _ hstrict  have hN0_eq : ∀ i, N0 i = 1 := by    intro i    have hT := hT_eq i    rw [hT_split i, hJsum i] at hT    have hle : J.card ≤ ∑ j ∈ J, Nj j i := by      have h := Finset.sum_le_sum (fun j hj => hNJ_ge j hj i)      simpa using h    have hn0 := hN0_ge i    have hJc := hJcard    omega  have hNj_eq : ∀ j ∈ J, ∀ i, Nj j i = 1 := by    intro j hj i    have hT := hT_eq i    rw [hT_split i, hJsum i] at hT    have hn0 := hN0_eq i    have hsum : ∑ x ∈ J, Nj x i = m - 1 := by      have hJc := hJcard      omega    have hsub : ∑ x ∈ J, (Nj x i - 1) = 0 := by      have h1 : ∑ x ∈ J, (Nj x i - 1) + ∑ x ∈ J, (1:ℕ) = ∑ x ∈ J, Nj x i := by        rw [← Finset.sum_add_distrib]        apply Finset.sum_congr rfl        intro x hx        have := hNJ_ge x hx i        omega      have hc1 : ∑ x ∈ J, (1:ℕ) = J.card := by simp      have hJc := hJcard      omega    have hzero := (Finset.sum_eq_zero_iff_of_nonneg (s := J) (f := fun x => Nj x i - 1)      (fun x hx => by have := hNJ_ge x hx i; omega)).mp hsub    have := hzero j hj    have := hNJ_ge j hj i    omega  have h_exists_unique : ∀ (P : Fin (m+1) → Prop) [DecidablePred P],      (∑ s : Fin (m+1), (if P s then 1 else 0)) = 1 → ∃! s, P s := by    intro P _ h    have hcard : (Finset.univ.filter P).card = 1 := by      have h1 : (∑ s : Fin (m+1), if P s then 1 else 0 : ℕ) = (Finset.univ.filter P).card := by        rw [Finset.card_filter]      rwa [← h1]    rw [Finset.card_eq_one] at hcard    rcases hcard with ⟨s, hs⟩    use s    have hp : ∀ x, P x ↔ x = s := by      intro x      have := Finset.ext_iff.mp hs x      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton] at this      exact this    exact ⟨(hp s).mpr rfl, fun x hx => (hp x).mp hx⟩  refine ⟨fun i => ?_, fun j hj1 hjm i => ?_⟩  · have := hN0_eq i    refine h_exists_unique (fun s => c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n))) ?_    simpa [N0, I0, d0] using this  · have hjJ : j ∈ J := by      change j ∈ (Finset.range m).filter (fun j => j ≠ 0)      rw [Finset.mem_filter, Finset.mem_range]      exact ⟨hjm, by omega⟩    have := hNj_eq j hjJ i    refine h_exists_unique (fun s => c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n))) ?_    simpa [Nj, Ij, D] using this
See it in the graphDiscuss this resultChallenge it