alpha_elementary_lexical_meet
Proposed helper discharging the lexical common-prefix hypothesis in the published adjacency criterion for a valid negative-cell elementary operation.
Statement
theorem alpha_elementary_lexical_meet (a b : List ℕ) (i : ℕ)
(ha : alpha_is_lexical a) (hb : alpha_is_lexical b)
(hi : i % 2 = 1) (hstep : alpha_elementary_cell_step a b i) :
alpha_is_lexical (alpha_lexical_meet a b) ∧
1 < (alpha_lexical_meet a b).sum + 1 ∧
(alpha_lexical_meet a b).sum + 1 < a.sum + 1- 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 6
- alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
- alpha_elementary_cell_stepOne source elementary split or conjugation, with a zero-based cell index.
- alpha_lexical_meetThe common left factor, including the minimum value at the first unequal cell.
- alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
- alpha_signed_cellA cell of a positive sequence, with alternating signs and zero padding.
- alpha_lexical_meet_is_lexicalThe source common-prefix meet of two nonempty positive lexical sequences is lexical, even if their sums differ.
- Used by 1
- alpha_prime_elementary_meet_nondvdFor a lexical elementary negative-cell step of prime degree, the meet degree cannot divide the ambient prime degree.
The proof, explained
The theorem proves that an elementary cell step from a lexical list a to another lexical list b at an odd index i produces a lexical meet alpha_lexical_meet a b that is lexical, has sum plus one strictly greater than 1, and has sum plus one strictly less than a.sum + 1. Lexicality of the meet is handled directly by the library theorem alpha_lexical_meet_is_lexical. The proof splits into the two cases of an elementary operation: splitting a cell of value at least 2 into two cells, or merging a cell of value 1 into its left neighbour. In each case, a and b share a common prefix and diverge at the modified cell, allowing an auxiliary lemma to express their meet as the common prefix followed by the smaller cell value. Finally, positivity of the elements ensures the meet's sum is at least 1, while omission of positive trailing entries guarantees the meet's sum is strictly smaller than that of a.
If two lists share a common prefix p and differ at the next position (x ≠ y), their lexical meet is p ++ [min x y].
We prove the auxiliary lemma `alpha_elementary_lexical_meet_aux_meet` by induction on the prefix `p`. When `p` is empty, the lists diverge at the very first element with distinct values `x` and `y`, so `alpha_lexical_meet` directly yields `[min x y]` by definition. When `p = z :: p'`, both lists begin with `z`, so the definition preserves `z` and recurses on `p'`; the induction hypothesis then shows that the result is `(z :: p') ++ [min x y]`.
theorem alpha_elementary_lexical_meet_aux_meet (p s t : List ℕ) (x y : ℕ) (hxy : x ≠ y) : alpha_lexical_meet (p ++ x :: s) (p ++ y :: t) = p ++ [min x y] := by induction p with | nil => simp [alpha_lexical_meet, hxy] | cons z p ih => simp [alpha_lexical_meet, ih]
The lexical meet alpha_lexical_meet a b satisfies alpha_is_lexical.
We unpack the assumption that `a` is lexical into non-emptiness, positivity of all entries, and the signed lexical condition for drops. We also unpack the step hypothesis into the bound `i < a.length` and the disjunction describing the elementary cell operation. Applying the known lemma `alpha_lexical_meet_is_lexical` to the lexical lists `a` and `b` establishes that their meet is lexical.
uses
alpha_lexical_meet_is_lexicaltheorem alpha_elementary_lexical_meet (a b : List ℕ) (i : ℕ) (ha : alpha_is_lexical a) (hb : alpha_is_lexical b) (hi : i % 2 = 1) (hstep : alpha_elementary_cell_step a b i) : alpha_is_lexical (alpha_lexical_meet a b) ∧ 1 < (alpha_lexical_meet a b).sum + 1 ∧ (alpha_lexical_meet a b).sum + 1 < a.sum + 1 := by obtain ⟨hane, hapos, halex⟩ := ha obtain ⟨hl, hstep'⟩ := hstep have hlex : alpha_is_lexical (alpha_lexical_meet a b) := alpha_lexical_meet_is_lexical a b ⟨hane, hapos, halex⟩ hb
In the split cell case (a[i] > 1), a decomposes as take i a ++ (a[i] :: drop (i + 1) a) and b decomposes as take i a ++ ((a[i] - 1) :: 1 :: drop (i + 1) a).
In the first branch of the cell operation, cell `i` has value at least 2 and is split into `a[i] - 1` and `1`. Using `List.drop_eq_getElem_cons` and `List.getD_eq_getElem`, `List.drop i a` expands as `a[i] :: List.drop (i + 1) a`. Recombining with `List.take i a` via `List.take_append_drop` yields the decomposed form of `a`. Rewriting with the definition of `b` from the hypothesis gives the corresponding decomposition of `b`.
uses
List.drop_eq_getElem_cons,List.getD_eq_getElem,List.take_append_droprcases hstep' with ⟨hgt, hbeq⟩ | ⟨hipos, h1, hbeq⟩ · have hdrop : List.drop i a = a.getD i 0 :: List.drop (i + 1) a := by rw [List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl] have haeq : a = List.take i a ++ (a.getD i 0 :: List.drop (i + 1) a) := by have h := List.take_append_drop i a rw [hdrop] at h exact h.symm have hbeq' : b = List.take i a ++ ((a.getD i 0 - 1) :: (1 :: List.drop (i + 1) a)) := by rw [hbeq]; simp
In the split case, the lexical meet is take i a ++ [a[i] - 1], with sum (take i a).sum + (a[i] - 1), while a has sum (take i a).sum + a[i] + (drop (i + 1) a).sum.
Since `a[i] > 1`, we have `a[i] ≠ a[i] - 1` and `min a[i] (a[i] - 1) = a[i] - 1`. Both `a` and `b` share the prefix `take i a` and diverge at index `i` with values `a[i]` and `a[i] - 1`. Applying `alpha_elementary_lexical_meet_aux_meet` shows their meet is `take i a ++ [a[i] - 1]`. Computing the sum of this list and the sum of `a` from their decompositions gives the explicit sum formulas, using `Nat.add_assoc` to reassociate the terms.
uses
alpha_elementary_lexical_meet_aux_meet,Nat.add_assochave hmin : min (a.getD i 0) (a.getD i 0 - 1) = a.getD i 0 - 1 := by omega have hmeet : alpha_lexical_meet a b = List.take i a ++ [a.getD i 0 - 1] := by conv_lhs => rw [haeq, hbeq'] rw [alpha_elementary_lexical_meet_aux_meet (List.take i a) (List.drop (i + 1) a) (1 :: List.drop (i + 1) a) (a.getD i 0) (a.getD i 0 - 1) (by omega), hmin] have hsum_meet : (alpha_lexical_meet a b).sum = (List.take i a).sum + (a.getD i 0 - 1) := by rw [hmeet]; simp have hsum_a : a.sum = (List.take i a).sum + a.getD i 0 + (List.drop (i + 1) a).sum := by conv_lhs => rw [haeq] simp [Nat.add_assoc]
In the split case, the sum of the meet plus 1 is strictly between 1 and a.sum + 1.
Because `a[i] ≥ 2`, the term `a[i] - 1` is at least 1, so the sum of the meet is at least 1, which implies `1 < (meet).sum + 1`. Moreover, `a[i] - 1 < a[i]` and the remaining tail entries are nonnegative, so `(meet).sum + 1 < a.sum + 1`. Both inequalities are closed by `omega`.
exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩
In the merged cell case (i > 0 and a[i] = 1), a decomposes around indices i - 1 and i, while b replaces a[i - 1] with a[i - 1] + 1 and removes a[i].
In the second branch of the cell operation, `i > 0` and `a[i] = 1`, and cell `i` is merged into cell `i - 1`. Applying `List.drop_eq_getElem_cons` twice (at `i - 1` and at `i`) together with `List.getD_eq_getElem` decomposes `List.drop (i - 1) a` into `a[i - 1] :: a[i] :: List.drop (i + 1) a`. Recombining with `List.take (i - 1) a` via `List.take_append_drop` yields the decomposed form of `a`. Substituting into the formula for `b` from the hypothesis gives `take (i - 1) a ++ ((a[i - 1] + 1) :: drop (i + 1) a)`.
uses
List.drop_eq_getElem_cons,List.getD_eq_getElem,List.take_append_drop· have hlt1 : i - 1 < a.length := by omega have hsub : i - 1 + 1 = i := by omega have hdrop1 : List.drop (i - 1) a = a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a) := by rw [List.getD_eq_getElem a 0 hlt1, List.drop_eq_getElem_cons hlt1, hsub, List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl] have haeq : a = List.take (i - 1) a ++ (a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a)) := by have h := List.take_append_drop (i - 1) a rw [hdrop1] at h exact h.symm have hbeq' : b = List.take (i - 1) a ++ ((a.getD (i - 1) 0 + 1) :: List.drop (i + 1) a) := by rw [hbeq]; simp
In the merged case, the lexical meet is take (i - 1) a ++ [a[i - 1]], with sum (take (i - 1) a).sum + a[i - 1], while a has sum (take (i - 1) a).sum + a[i - 1] + a[i] + (drop (i + 1) a).sum.
Lists `a` and `b` share the prefix `take (i - 1) a` and diverge at index `i - 1` with values `a[i - 1]` and `a[i - 1] + 1`. By `alpha_elementary_lexical_meet_aux_meet`, their meet is `take (i - 1) a ++ [min a[i - 1] (a[i - 1] + 1)]`. Since `a[i - 1] ≤ a[i - 1] + 1`, `Nat.min_eq_left` reduces the minimum to `a[i - 1]`. Summing both lists gives the explicit sum formulas, reassociated with `Nat.add_assoc`.
uses
alpha_elementary_lexical_meet_aux_meet,Nat.min_eq_left,Nat.add_assochave hmeet : alpha_lexical_meet a b = List.take (i - 1) a ++ [a.getD (i - 1) 0] := by conv_lhs => rw [haeq, hbeq'] rw [alpha_elementary_lexical_meet_aux_meet (List.take (i - 1) a) (a.getD i 0 :: List.drop (i + 1) a) (List.drop (i + 1) a) (a.getD (i - 1) 0) (a.getD (i - 1) 0 + 1) (by omega), Nat.min_eq_left (by omega)] have hsum_meet : (alpha_lexical_meet a b).sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 := by rw [hmeet]; simp have hsum_a : a.sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 + a.getD i 0 + (List.drop (i + 1) a).sum := by conv_lhs => rw [haeq] simp [Nat.add_assoc]
In the merged case, the sum of the meet plus 1 is strictly between 1 and a.sum + 1, completing the proof.
Since `a` is lexical, all its elements are strictly positive; in particular, `a[i - 1] > 0` (via `List.getElem_mem` and `List.getD_eq_getElem`). Therefore the sum of the meet is at least `a[i - 1] ≥ 1`, showing `1 < (meet).sum + 1`. In addition, `a` contains the extra positive entry `a[i] = 1`, making the sum of `a` strictly larger than that of the meet, so `(meet).sum + 1 < a.sum + 1`. Both bounds are verified by `omega`.
uses
List.getD_eq_getElem,List.getElem_memhave hypos : 0 < a.getD (i - 1) 0 := hapos _ (by rw [List.getD_eq_getElem a 0 hlt1]; exact List.getElem_mem hlt1) exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩
alpha_lexical_meet_is_lexical- The lexical meet of two lexical lists is itself lexical.
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 getD at a valid index equals indexing with getElem.
List.take_append_drop- Concatenating the prefix of length i and the suffix dropping i elements reconstructs the original list.
alpha_elementary_lexical_meet_aux_meet- If two lists share a prefix p and differ at the next elements x and y (with x ≠ y), their lexical meet equals p ++ [min x y].
Nat.add_assoc- Addition of natural numbers is associative: (n + m) + k = n + (m + k).
Nat.min_eq_left- If a ≤ b, then min a b = a.
List.getElem_mem- Any element accessed by valid indexing belongs to the list.
- The arithmetic bounds on the list sums in Step 5 and Step 8 are discharged by `omega` using linear integer arithmetic from the explicit sum expansions.
- Rewriting the meet via `conv_lhs` in lines 28, 34, 51, 59 targets only the left-hand side before applying the prefix lemma.
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_lexical_meet_aux_meet (p s t : List ℕ) (x y : ℕ) (hxy : x ≠ y) : alpha_lexical_meet (p ++ x :: s) (p ++ y :: t) = p ++ [min x y] := by induction p with | nil => simp [alpha_lexical_meet, hxy] | cons z p ih => simp [alpha_lexical_meet, ih]theorem alpha_elementary_lexical_meet (a b : List ℕ) (i : ℕ) (ha : alpha_is_lexical a) (hb : alpha_is_lexical b) (hi : i % 2 = 1) (hstep : alpha_elementary_cell_step a b i) : alpha_is_lexical (alpha_lexical_meet a b) ∧ 1 < (alpha_lexical_meet a b).sum + 1 ∧ (alpha_lexical_meet a b).sum + 1 < a.sum + 1 := by obtain ⟨hane, hapos, halex⟩ := ha obtain ⟨hl, hstep'⟩ := hstep have hlex : alpha_is_lexical (alpha_lexical_meet a b) := alpha_lexical_meet_is_lexical a b ⟨hane, hapos, halex⟩ hb rcases hstep' with ⟨hgt, hbeq⟩ | ⟨hipos, h1, hbeq⟩ · have hdrop : List.drop i a = a.getD i 0 :: List.drop (i + 1) a := by rw [List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl] have haeq : a = List.take i a ++ (a.getD i 0 :: List.drop (i + 1) a) := by have h := List.take_append_drop i a rw [hdrop] at h exact h.symm have hbeq' : b = List.take i a ++ ((a.getD i 0 - 1) :: (1 :: List.drop (i + 1) a)) := by rw [hbeq]; simp have hmin : min (a.getD i 0) (a.getD i 0 - 1) = a.getD i 0 - 1 := by omega have hmeet : alpha_lexical_meet a b = List.take i a ++ [a.getD i 0 - 1] := by conv_lhs => rw [haeq, hbeq'] rw [alpha_elementary_lexical_meet_aux_meet (List.take i a) (List.drop (i + 1) a) (1 :: List.drop (i + 1) a) (a.getD i 0) (a.getD i 0 - 1) (by omega), hmin] have hsum_meet : (alpha_lexical_meet a b).sum = (List.take i a).sum + (a.getD i 0 - 1) := by rw [hmeet]; simp have hsum_a : a.sum = (List.take i a).sum + a.getD i 0 + (List.drop (i + 1) a).sum := by conv_lhs => rw [haeq] simp [Nat.add_assoc] exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩ · have hlt1 : i - 1 < a.length := by omega have hsub : i - 1 + 1 = i := by omega have hdrop1 : List.drop (i - 1) a = a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a) := by rw [List.getD_eq_getElem a 0 hlt1, List.drop_eq_getElem_cons hlt1, hsub, List.getD_eq_getElem a 0 hl, List.drop_eq_getElem_cons hl] have haeq : a = List.take (i - 1) a ++ (a.getD (i - 1) 0 :: (a.getD i 0 :: List.drop (i + 1) a)) := by have h := List.take_append_drop (i - 1) a rw [hdrop1] at h exact h.symm have hbeq' : b = List.take (i - 1) a ++ ((a.getD (i - 1) 0 + 1) :: List.drop (i + 1) a) := by rw [hbeq]; simp have hmeet : alpha_lexical_meet a b = List.take (i - 1) a ++ [a.getD (i - 1) 0] := by conv_lhs => rw [haeq, hbeq'] rw [alpha_elementary_lexical_meet_aux_meet (List.take (i - 1) a) (a.getD i 0 :: List.drop (i + 1) a) (List.drop (i + 1) a) (a.getD (i - 1) 0) (a.getD (i - 1) 0 + 1) (by omega), Nat.min_eq_left (by omega)] have hsum_meet : (alpha_lexical_meet a b).sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 := by rw [hmeet]; simp have hsum_a : a.sum = (List.take (i - 1) a).sum + a.getD (i - 1) 0 + a.getD i 0 + (List.drop (i + 1) a).sum := by conv_lhs => rw [haeq] simp [Nat.add_assoc] have hypos : 0 < a.getD (i - 1) 0 := hapos _ (by rw [List.getD_eq_getElem a 0 hlt1]; exact List.getElem_mem hlt1) exact ⟨hlex, by rw [hsum_meet]; omega, by rw [hsum_meet, hsum_a]; omega⟩