alpha_elementary_cell_step_sum
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
- alpha_elementary_cell_stepOne source elementary split or conjugation, with a zero-based cell index.
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.
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.
uses
List.drop_eq_getElem_cons,List.getD_eq_getElem,List.take_append_drop,List.sum_append,List.sum_cons,Nat.add_assoclemma 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]
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.
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⟩
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.
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
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].
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]
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.
uses
List.sum_append,List.sum_cons,List.sum_nil,add_zerorw [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.
- In Lean, list indexing with a fallback value is written `l.getD i 0`, which equals the in-bounds element `l[i]` when `i < l.length`.
- Linear arithmetic (`omega`) automatically resolves inequalities and arithmetic simplifications such as `(a.getD i 0 - 1) + 1 = a.getD i 0` and `(i - 1) + 1 = i`.
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.
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