AFTD Auto-Formalizing Theoretical Domains

cycle_wrap_set_compl_eq_Icc_and_sum

theoremverifiedformalization

For 1 ≤ i < j ≤ n, the complement in {1,…,n} of the wrap set W = {j,…,n} ∪ {1,…,i} of the n-cycle is the standard interval {i+1,…,j−1} (empty when j = i+1), and its element sum is T_n − W*, where T_n = n(n+1)/2 and W* is the element sum of W.

Statement

theorem cycle_wrap_set_compl_eq_Icc_and_sum (n i j : ℕ) (hi : 1 ≤ i) (hij : i < j) (hj : j ≤ n) :
    Finset.Icc 1 n \ (Finset.Icc j n ∪ Finset.Icc 1 i) = Finset.Icc (i + 1) (j - 1) ∧
    ∑ x ∈ Finset.Icc 1 n \ (Finset.Icc j n ∪ Finset.Icc 1 i), x =
      n * (n + 1) / 2 - ∑ x ∈ Finset.Icc j n ∪ Finset.Icc 1 i, x
Formalizes
arXiv:2610.08889 (Consecutive Cycle Sums), Lemma 1. Wrap sets and standard intervals are written out as Finset.Icc unions; the empty interval for j = i+1 is Icc (i+1) i.
Verified
12 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof establishes that the wrap set W = {j,…,n} ∪ {1,…,i} is a subset of {1,…,n}, then splits the theorem into the set identity and the sum formula. The set identity is proved by extensionality, showing that an element in {1,…,n} outside W must lie between i+1 and j-1 via linear arithmetic. Finally, the sum of {1,…,n} is shown by induction to be n(n+1)/2, from which the complement sum is obtained by subtracting the sum over W.

  1. The wrap set W = {j,…,n} ∪ {1,…,i} is a subset of {1,…,n}.

    Take an element x in the union. By definition of Finset union and closed intervals (Finset.mem_union, Finset.mem_Icc), x satisfies j ≤ x ≤ n or 1 ≤ x ≤ i. Since 1 ≤ i < j ≤ n, in either case 1 ≤ x ≤ n, which linear integer arithmetic (omega) verifies.

    lines 5–8

    uses Finset.mem_union, Finset.mem_Icc

      have hsub : Finset.Icc j n ∪ Finset.Icc 1 i ⊆ Finset.Icc 1 n := by
        intro x hx
        simp only [Finset.mem_union, Finset.mem_Icc] at hx ⊢
        omega
  2. The complement {1,…,n} \ ({j,…,n} ∪ {1,…,i}) equals the interval {i+1,…,j-1}.

    Split the goal into the set identity and the sum identity (refine). By extensionality (ext x), unfold the definitions of difference, union, and interval membership (Finset.mem_sdiff, Finset.mem_union, Finset.mem_Icc). An element x belongs to the set difference if and only if (1 ≤ x ≤ n) and ¬(j ≤ x ≤ n ∨ 1 ≤ x ≤ i), which linear arithmetic (omega) simplifies to i + 1 ≤ x ≤ j - 1 given 1 ≤ i < j ≤ n.

    lines 9–12

    uses Finset.mem_sdiff, Finset.mem_union, Finset.mem_Icc

      refine ⟨?_, ?_⟩
      · ext x
        simp only [Finset.mem_sdiff, Finset.mem_union, Finset.mem_Icc]
        omega
  3. For every natural number m, twice the sum of {1,…,m} equals m(m+1).

    By induction on m. The base case m = 0 is trivial since the interval is empty (simp). For the successor m + 1, split off the top term m + 1 using Finset.sum_Icc_succ_top, distribute multiplication by 2 over addition using add_mul, apply the induction hypothesis, and conclude by algebraic ring simplification (ring).

    lines 13–17

    uses Finset.sum_Icc_succ_top, add_mul

      · have hg : ∀ m : ℕ, (∑ x ∈ Finset.Icc 1 m, x) * 2 = m * (m + 1) := by
          intro m
          induction m with
          | zero => simp
          | succ m ih => rw [Finset.sum_Icc_succ_top (by omega), add_mul, ih]; ring
  4. The sum of the integers from 1 to n is n(n+1)/2.

    Applying Nat.div_eq_of_eq_mul_left with 0 < 2 converts the identity 2 * ∑_{x=1}^n x = n(n+1) into the closed-form division ∑_{x=1}^n x = n(n+1)/2.

    lines 18–19

    uses Nat.div_eq_of_eq_mul_left

        have htot : ∑ x ∈ Finset.Icc 1 n, x = n * (n + 1) / 2 :=
          (Nat.div_eq_of_eq_mul_left (by norm_num) (hg n).symm).symm
  5. The sum over the complement is n(n+1)/2 − ∑_{x ∈ W} x.

    Using the inclusion W ⊆ {1,…,n}, partition the sum over {1,…,n} into the sum over {1,…,n} \ W plus the sum over W (Finset.sum_sdiff). Rewriting with the total sum n(n+1)/2 reduces the equation to the natural number identity (A + B) − B = A, which omega finishes.

    lines 20–21

    uses Finset.sum_sdiff

        rw [← htot, ← Finset.sum_sdiff hsub]
        omega
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to either set: x ∈ s ∪ t ↔ x ∈ s ∨ x ∈ t.
Finset.mem_Icc
An element x belongs to the closed interval [a, b] if and only if a ≤ x ≤ b.
Finset.mem_sdiff
An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
Finset.sum_Icc_succ_top
A sum over an interval [a, b+1] can be split into the sum over [a, b] plus the top term at b+1, provided a ≤ b+1.
add_mul
Right distributivity of multiplication over addition: (a + b) * c = a * c + b * c.
Nat.div_eq_of_eq_mul_left
If 0 < n and m = k * n, then m / n = k for natural numbers.
Finset.sum_sdiff
If s₁ ⊆ s₂, the sum of a function over s₂ \ s₁ plus its sum over s₁ equals the sum over s₂.

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 cycle_wrap_set_compl_eq_Icc_and_sum (n i j : ℕ) (hi : 1 ≤ i) (hij : i < j) (hj : j ≤ n) :    Finset.Icc 1 n \ (Finset.Icc j n ∪ Finset.Icc 1 i) = Finset.Icc (i + 1) (j - 1) ∧    ∑ x ∈ Finset.Icc 1 n \ (Finset.Icc j n ∪ Finset.Icc 1 i), x =      n * (n + 1) / 2 - ∑ x ∈ Finset.Icc j n ∪ Finset.Icc 1 i, x := by  have hsub : Finset.Icc j n ∪ Finset.Icc 1 i ⊆ Finset.Icc 1 n := by    intro x hx    simp only [Finset.mem_union, Finset.mem_Icc] at hx ⊢    omega  refine ⟨?_, ?_⟩  · ext x    simp only [Finset.mem_sdiff, Finset.mem_union, Finset.mem_Icc]    omega  · have hg : ∀ m : ℕ, (∑ x ∈ Finset.Icc 1 m, x) * 2 = m * (m + 1) := by      intro m      induction m with      | zero => simp      | succ m ih => rw [Finset.sum_Icc_succ_top (by omega), add_mul, ih]; ring    have htot : ∑ x ∈ Finset.Icc 1 n, x = n * (n + 1) / 2 :=      (Nat.div_eq_of_eq_mul_left (by norm_num) (hg n).symm).symm    rw [← htot, ← Finset.sum_sdiff hsub]    omega
See it in the graphDiscuss this resultChallenge it