AFTD Auto-Formalizing Theoretical Domains

alpha_elementary_cell_step_length_parity

theoremverified

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

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.

  1. 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.

    line 2

      rcases h with ⟨hi, hsplit | hconj⟩
  2. 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.

    lines 3–5

    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
  3. 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.

    lines 6–8

    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

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
See it in the graphDiscuss this resultChallenge it