AFTD Auto-Formalizing Theoretical Domains

alpha_elementary_cell_step_sum

theoremverified

Elementary splitting and conjugation preserve the degree.

Statement

theorem alpha_elementary_cell_step_sum (a b : List ℕ) (i : ℕ) (h : alpha_elementary_cell_step a b i) : b.sum = a.sum
Source
Run-length helpers for OP-392, arXiv:2610.24758, Conjecture 1; lexical sequences and elementary operations from arXiv:0810.5205, Definitions 1.1, Section 2, Theorem 3.1 and Corollary 3.3. No new research advance is claimed for these supporting statements.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

An elementary cell step transforms a list of natural numbers a into b either by splitting an entry a[i] > 1 into two entries a[i] - 1 and 1, or by merging an entry a[i] = 1 into its predecessor a[i - 1] as a[i - 1] + 1. The proof first establishes an auxiliary lemma decomposing the sum of any list into the prefix sum before index i, the element at index i, and the suffix sum after index i. In the splitting case, the two newly created elements sum to (a[i] - 1) + 1 = a[i], leaving the total sum unchanged. In the merging case, the merged entry has value a[i - 1] + 1 = a[i - 1] + a[i], which likewise preserves the sum.

  1. The sum of a list decomposes into the sum before index i, the element at index i, and the sum after index i.

    First, since i < l.length, the suffix l.drop i decomposes as l[i] :: l.drop (i + 1) using List.drop_eq_getElem_cons and List.getD_eq_getElem. Next, because l = l.take i ++ l.drop i by List.take_append_drop, the sum of l splits into the sum of the prefix and the sum of the suffix by List.sum_append. Substituting the decomposed suffix and applying List.sum_cons and Nat.add_assoc yields the desired three-part sum.

    lines 1–8

    uses List.drop_eq_getElem_cons, List.getD_eq_getElem, List.take_append_drop, List.sum_append, List.sum_cons, Nat.add_assoc

    lemma alpha_elementary_cell_step_sum_aux (l : List ℕ) (i : ℕ) (h : i < l.length) :
        l.sum = (l.take i).sum + l.getD i 0 + (l.drop (i + 1)).sum := by
      have hd : l.drop i = l.getD i 0 :: l.drop (i + 1) := by
        rw [List.drop_eq_getElem_cons h, List.getD_eq_getElem l 0 h]
      calc l.sum = (l.take i ++ l.drop i).sum := by rw [List.take_append_drop]
        _ = (l.take i).sum + (l.drop i).sum := List.sum_append
        _ = (l.take i).sum + (l.getD i 0 + (l.drop (i + 1)).sum) := by rw [hd, List.sum_cons]
        _ = (l.take i).sum + l.getD i 0 + (l.drop (i + 1)).sum := by rw [Nat.add_assoc]
  2. The elementary cell step hypothesis splits into two cases: splitting an entry greater than 1, or merging an entry equal to 1 into its predecessor.

    Unpacking the definition of alpha_elementary_cell_step gives the bound i < a.length and a disjunction: either a[i] > 1 and b splits this element into [a[i] - 1, 1], or i > 0 with a[i] = 1 and b merges this element into a[i - 1]. We proceed by case analysis on this disjunction.

    lines 10–11

    theorem alpha_elementary_cell_step_sum (a b : List ℕ) (i : ℕ) (h : alpha_elementary_cell_step a b i) : b.sum = a.sum := by
      rcases h with ⟨hi, h | h⟩
  3. In the splitting case, the sum of b equals the sum of a.

    We instantiate the auxiliary decomposition lemma for a at index i. Rewriting b with its definition replaces a[i] with [a[i] - 1, 1]. Expanding the sum of b using List.sum_append, List.sum_cons, List.sum_nil, and add_zero simplifies the sum to (a.take i).sum + (a[i] - 1 + 1) + (a.drop (i + 1)).sum. Since a[i] > 1, linear arithmetic (omega) simplifies (a[i] - 1) + 1 to a[i], matching the sum of a.

    lines 12–16

    uses alpha_elementary_cell_step_sum_aux, List.sum_append, List.sum_cons, List.sum_nil, add_zero

      · rcases h with ⟨hgt, hb⟩
        have ha := alpha_elementary_cell_step_sum_aux a i hi
        rw [hb]
        simp only [List.sum_append, List.sum_cons, List.sum_nil, add_zero]
        omega
  4. In the merging case, the prefix sum of a up to index i decomposes into the sum up to index i - 1 plus the element at index i - 1.

    We unpack the hypotheses i > 0, a[i] = 1, and the formula for b, and instantiate the auxiliary decomposition lemma for a. Since 0 < i < a.length, we have i - 1 < a.length. Using List.take_append_getElem, List.getD_eq_getElem, and Nat.sub_add_cancel, the prefix a.take i decomposes as a.take (i - 1) ++ [a[i - 1]]. Taking the sum of both sides via List.sum_append and List.sum_singleton shows that (a.take i).sum = (a.take (i - 1)).sum + a[i - 1].

    lines 17–24

    uses alpha_elementary_cell_step_sum_aux, List.getD_eq_getElem, List.take_append_getElem, Nat.sub_add_cancel, List.sum_append, List.sum_singleton

      · rcases h with ⟨hpos, hget, hb⟩
        have ha := alpha_elementary_cell_step_sum_aux a i hi
        have hlt : i - 1 < a.length := by omega
        have htake : a.take i = a.take (i - 1) ++ [a.getD (i - 1) 0] := by
          rw [List.getD_eq_getElem a 0 hlt, List.take_append_getElem hlt,
            Nat.sub_add_cancel (by omega : 1 ≤ i)]
        have hsum_take : (a.take i).sum = (a.take (i - 1)).sum + a.getD (i - 1) 0 := by
          rw [htake, List.sum_append, List.sum_singleton]
  5. In the merging case, the sum of b equals the sum of a.

    Substituting the definition of b and simplifying the sum across list concatenations with List.sum_append, List.sum_cons, List.sum_nil, and add_zero gives b.sum = (a.take (i - 1)).sum + (a[i - 1] + 1) + (a.drop (i + 1)).sum. Combining this with the prefix sum decomposition and the fact that a[i] = 1, linear arithmetic (omega) closes the goal b.sum = a.sum.

    lines 25–27

    uses List.sum_append, List.sum_cons, List.sum_nil, add_zero

        rw [hb]
        simp only [List.sum_append, List.sum_cons, List.sum_nil, add_zero]
        omega
List.drop_eq_getElem_cons
Dropping i elements from a list of length greater than i yields the element at index i followed by dropping i + 1 elements.
List.getD_eq_getElem
Accessing a list with default value d at an index within bounds equals the element at that index.
List.take_append_drop
Concatenating the prefix of length i and the suffix after i elements reconstructs the original list.
List.sum_append
The sum of the concatenation of two lists is the sum of their individual sums.
List.sum_cons
The sum of a list with head a and tail l is a plus the sum of l.
Nat.add_assoc
Addition of natural numbers is associative: (n + m) + k = n + (m + k).
alpha_elementary_cell_step_sum_aux
For any list l and in-bounds index i, the sum of l splits into the sum of elements before index i, the element at index i, and the sum of elements after index i.
List.sum_nil
The sum of the empty list is zero.
add_zero
Adding zero to any element leaves it unchanged.
List.take_append_getElem
Appending the element at index i to the prefix of length i yields the prefix of length i + 1.
Nat.sub_add_cancel
If m ≤ n, then (n - m) + m = n.
List.sum_singleton
The sum of a singleton list [x] is x.

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

lemma alpha_elementary_cell_step_sum_aux (l : List ℕ) (i : ℕ) (h : i < l.length) :    l.sum = (l.take i).sum + l.getD i 0 + (l.drop (i + 1)).sum := by  have hd : l.drop i = l.getD i 0 :: l.drop (i + 1) := by    rw [List.drop_eq_getElem_cons h, List.getD_eq_getElem l 0 h]  calc l.sum = (l.take i ++ l.drop i).sum := by rw [List.take_append_drop]    _ = (l.take i).sum + (l.drop i).sum := List.sum_append    _ = (l.take i).sum + (l.getD i 0 + (l.drop (i + 1)).sum) := by rw [hd, List.sum_cons]    _ = (l.take i).sum + l.getD i 0 + (l.drop (i + 1)).sum := by rw [Nat.add_assoc]theorem alpha_elementary_cell_step_sum (a b : List ℕ) (i : ℕ) (h : alpha_elementary_cell_step a b i) : b.sum = a.sum := by  rcases h with ⟨hi, h | h⟩  · rcases h with ⟨hgt, hb⟩    have ha := alpha_elementary_cell_step_sum_aux a i hi    rw [hb]    simp only [List.sum_append, List.sum_cons, List.sum_nil, add_zero]    omega  · rcases h with ⟨hpos, hget, hb⟩    have ha := alpha_elementary_cell_step_sum_aux a i hi    have hlt : i - 1 < a.length := by omega    have htake : a.take i = a.take (i - 1) ++ [a.getD (i - 1) 0] := by      rw [List.getD_eq_getElem a 0 hlt, List.take_append_getElem hlt,        Nat.sub_add_cancel (by omega : 1 ≤ i)]    have hsum_take : (a.take i).sum = (a.take (i - 1)).sum + a.getD (i - 1) 0 := by      rw [htake, List.sum_append, List.sum_singleton]    rw [hb]    simp only [List.sum_append, List.sum_cons, List.sum_nil, add_zero]    omega
See it in the graphDiscuss this resultChallenge it