alpha_elementary_cell_step_length_parity
One elementary operation reverses the parity of the number of cells (source Lemma 2.3).
Statement
theorem alpha_elementary_cell_step_length_parity (a b : List ℕ) (i : ℕ) (h : alpha_elementary_cell_step a b i) : b.length % 2 = (a.length + 1) % 2- 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
Quot.soundpropext- Built on 1
- alpha_elementary_cell_stepOne source elementary split or conjugation, with a zero-based cell index.
The proof, explained
By definition, an elementary cell step is either a split operation that replaces one cell with two, or a merge operation that combines two cells into one. In the split case, the list length increases by 1 (|b| = |a| + 1), while in the merge case, the length decreases by 1 (|b| = |a| - 1). Evaluating the lengths of the sublists in both cases shows that |b| ≡ |a| + 1 (mod 2), reversing the parity of the number of cells.
The transition from a to b is either a cell split or a cell merge, with index i within bounds (i < |a|).
We unpack the definition of `alpha_elementary_cell_step a b i`, which requires i < |a| and gives two alternatives: either a cell of size > 1 at position i is split into two cells, or a cell of size 1 at position i > 0 is merged into the preceding cell.
rcases h with ⟨hi, hsplit | hconj⟩
In the cell-split case, |b| = |a| + 1, so |b| ≡ |a| + 1 (mod 2).
In the split case, b is constructed by taking the first i elements of a, inserting two cells [a[i] - 1, 1], and appending the remaining elements from index i + 1. Rewriting with the list length lemmas expresses |b| as min(i, |a|) + 2 + (|a| - (i + 1)). Since i < |a|, min(i, |a|) = i, so linear arithmetic (omega) simplifies |b| to |a| + 1, matching the required parity.
uses
List.length_append,List.length_take,List.length_drop,List.length_cons,List.length_nil· rcases hsplit with ⟨_, rfl⟩ simp only [List.length_append, List.length_take, List.length_drop, List.length_cons, List.length_nil] omega
In the cell-merge case, |b| = |a| - 1, so |b| ≡ |a| + 1 (mod 2).
In the merge case, 0 < i < |a| with a[i] = 1, and b replaces the two adjacent cells at indices i - 1 and i with the single merged cell [a[i-1] + 1]. Rewriting with the list length lemmas gives |b| = min(i - 1, |a|) + 1 + (|a| - (i + 1)) = (i - 1) + 1 + |a| - (i + 1) = |a| - 1. Since |a| - 1 and |a| + 1 have the same parity, linear integer arithmetic (omega) concludes that |b| % 2 = (|a| + 1) % 2.
uses
List.length_append,List.length_take,List.length_drop,List.length_cons,List.length_nil· rcases hconj with ⟨hi0, _, rfl⟩ simp only [List.length_append, List.length_take, List.length_drop, List.length_cons, List.length_nil] omega
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_cons- Prepending an element to a list increases its length by 1.
List.length_drop- The length of a list after dropping its first i elements is the list's length minus i.
List.length_nil- The empty list has length 0.
List.length_take- The length of the prefix of a list taking at most i elements is min(i, length).
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.
theorem alpha_elementary_cell_step_length_parity (a b : List ℕ) (i : ℕ) (h : alpha_elementary_cell_step a b i) : b.length % 2 = (a.length + 1) % 2 := by rcases h with ⟨hi, hsplit | hconj⟩ · rcases hsplit with ⟨_, rfl⟩ simp only [List.length_append, List.length_take, List.length_drop, List.length_cons, List.length_nil] omega · rcases hconj with ⟨hi0, _, rfl⟩ simp only [List.length_append, List.length_take, List.length_drop, List.length_cons, List.length_nil] omega