alpha_lexical_meet_is_lexical
The source common-prefix meet of two nonempty positive lexical sequences is lexical, even if their sums differ.
Statement
theorem alpha_lexical_meet_is_lexical (a b : List ℕ) (ha : alpha_is_lexical a)
(hb : alpha_is_lexical b) : alpha_is_lexical (alpha_lexical_meet a b)- Source
- A helper for the lexical-sequence route to OP-392, arXiv:2610.24758, Conjecture 1. It discharges the lexical-meet hypothesis of arXiv:0810.5205, Theorem 3.1. This proof is supplied directly; no research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- alpha_signed_cellA cell of a positive sequence, with alternating signs and zero padding.
- alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
- alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
- alpha_lexical_meetThe common left factor, including the minimum value at the first unequal cell.
- Used by 2
- alpha_prime_lexical_meet_nondvd_of_neFor any distinct lexical sequences of the same prime degree, the meet degree is a proper nontrivial value and does not divide the ambient…
- alpha_elementary_lexical_meetProposed helper discharging the lexical common-prefix hypothesis in the published adjacency criterion for a valid negative-cell elementary…
The proof, explained
To show that the common-prefix meet of two lexical sequences a and b is lexical, we first classify its possible forms: it either equals a or b, or branches at their first difference as p ++ [min x y] where x ≠ y. In the branching case with x < y, the truncated sequence f = p ++ [x] is shown to be lexical by analyzing its proper suffixes f.drop k of remaining length q = |f| - k. Any such suffix either inherits an alternating lexicographical decrease from a before position q, or hits the boundary at index q: if q is even, the truncated suffix has 0 while f has a strictly positive value, and if q is odd, the parity and prefix agreements would force b.drop k not to be lexicographically smaller than b, contradicting that b is lexical.
The j-th entry of a.drop k equals the (k + j)-th entry of a.
By unfolding the default-valued list lookup into optional lookup followed by getD and applying the lemma that index j in a dropped list corresponds to index k + j in the original list, the equality holds immediately.
uses
List.getD_eq_getElem?_getD,List.getElem?_dropsimp only [List.getD_eq_getElem?_getD, List.getElem?_drop]Equal entries at index i have equal signed cell values.
The signed cell at index i is determined entirely by the entry at index i (multiplied by +1 if i is even and -1 if i is odd), so equal entries give equal signed cells.
simp only [alpha_signed_cell, h]If a and b agree on all signed cells before i and signed(b, i) < signed(a, i), then a is not strictly lexicographically smaller than b.
Suppose for contradiction that a <_{lex} b, witnessed by a first differing index j. By trichotomy on j and i: if j < i, the two sequences must agree at j, contradicting strict inequality; if j = i, signed(a, i) < signed(b, i) directly contradicts the assumption; if j > i, the two sequences must agree at i, again contradicting the assumption.
uses
lt_trichotomyrintro ⟨j, hj, he', hl⟩ rcases lt_trichotomy j i with hji | rfl | hij · have := he j hji omega · omega · have := he' i hij omega
To show f is lexical, it suffices to show f.drop k <_{lex} f for each shift 0 < k < |f|, and a and f share signed cells on this range.
Nonemptiness and entry-wise positivity of f hold by assumption. For an arbitrary shift 0 < k < |f|, we set q = |f| - k, noting that 0 < q < |f| and k + q = |f|. Since a and f agree on all indices j < |f|, their signed cells match at all such positions.
uses
alpha_meet_aux_signed_eqrefine ⟨hfne, hfpos, ?_⟩ intro k hk hk0 let q := f.length - k have hq0 : 0 < q := by dsimp [q]; omega have hql : q < f.length := by dsimp [q]; omega have hqk : k + q = f.length := by dsimp [q]; omega have hfa (j : ℕ) (hj : j < f.length) : alpha_signed_cell a j = alpha_signed_cell f j := alpha_meet_aux_signed_eq (haf j hj)
The shifted sequences a.drop k and f.drop k agree on the first q signed cells, and a provides a witness i that a.drop k <_{lex} a.
For any index j < q, the shifted index k + j is strictly less than |f| ≤ |a|, so a.drop k and f.drop k share the entry at j and consequently their signed cells agree. Because a is lexical, there is an index i witnessing that a.drop k <_{lex} a.
uses
alpha_meet_aux_signed_eq,alpha_meet_aux_get_d_drophave hfad (j : ℕ) (hj : j < q) : alpha_signed_cell (a.drop k) j = alpha_signed_cell (f.drop k) j := by apply alpha_meet_aux_signed_eq simp only [alpha_meet_aux_get_d_drop] exact haf _ (by omega) obtain ⟨i, hi, he, hlt⟩ := ha.2.2 k (by omega) hk0
If the witness index i satisfies i < q, then i also witnesses f.drop k <_{lex} f.
When i < q, every index j ≤ i falls within the range where f matches a and f.drop k matches a.drop k. Rewriting the signed cells of a and a.drop k to those of f and f.drop k preserves the prefix agreement for all j < i and the strict decrease at index i.
uses
lt_of_lt_of_le,le_max_rightby_cases hiq : i < q · refine ⟨i, ?_, ?_, ?_⟩ · have : i < f.length := by omega exact lt_of_lt_of_le this (le_max_right _ _) · intro j hj rw [← hfad j (by omega), ← hfa j (by omega)] exact he j hj · rw [← hfad i hiq, ← hfa i (by omega)] exact hlt
If i ≥ q and q is even, then q witnesses f.drop k <_{lex} f.
Since i ≥ q, f.drop k and f agree on all signed cells before index q. Because |f.drop k| = q, looking up index q in f.drop k yields the default 0, giving signed cell 0 at the even index q. In contrast, q < |f| holds, so f has a strictly positive entry at index q, producing a strictly positive signed cell. Hence signed(f.drop k, q) = 0 < signed(f, q).
uses
lt_of_lt_of_le,le_max_right,List.getD_eq_getElem,List.getElem_mem,List.getD_eq_default,List.length_drop,le_rfl,if_true,Nat.cast_zero· have hborder (j : ℕ) (hj : j < q) : alpha_signed_cell (f.drop k) j = alpha_signed_cell f j := by rw [← hfad j hj, ← hfa j (by omega)] exact he j (by omega) by_cases hqe : q % 2 = 0 · refine ⟨q, lt_of_lt_of_le hql (le_max_right _ _), hborder, ?_⟩ have hmem : f.getD q 0 ∈ f := by rw [List.getD_eq_getElem _ _ hql] exact List.getElem_mem hql have hp := hfpos _ hmem have hd : (f.drop k).getD q 0 = 0 := List.getD_eq_default _ _ (by simpa only [List.length_drop] using (le_rfl : f.length - k ≤ f.length - k)) simp only [alpha_signed_cell, hqe, if_true, hd, Nat.cast_zero] exact_mod_cast hp
The subcase where i ≥ q and q is odd is impossible, as it contradicts that b is lexical.
When q is odd, q - 1 is even, and the shift identity k + (q - 1) = |f| - 1 gives f[q - 1] = f[|f| - 1]. Since b matches f before |f| - 1, b.drop k and b agree on all signed cells before q - 1. But at the even index q - 1, signed(b, q - 1) = f[|f| - 1] < b[|f| - 1] = signed(b.drop k, q - 1). By alpha_meet_aux_not_lt_of_first_difference, this implies b.drop k is not strictly lexicographically smaller than b, contradicting that b is lexical.
uses
if_true,alpha_meet_aux_get_d_drop,alpha_meet_aux_signed_eq,False.elim,alpha_meet_aux_not_lt_of_first_difference· have hj0 : (q - 1) % 2 = 0 := by omega have hjl : q - 1 < f.length - 1 := by omega have hjk : k + (q - 1) = f.length - 1 := by omega have hcross : f.getD (q - 1) 0 = f.getD (f.length - 1) 0 := by have h := hborder (q - 1) (by omega) simp only [alpha_signed_cell, hj0, if_true, alpha_meet_aux_get_d_drop, hjk] at h omega have hpre : ∀ j < q - 1, alpha_signed_cell (b.drop k) j = alpha_signed_cell b j := by intro j hj have h1 : alpha_signed_cell b j = alpha_signed_cell f j := alpha_meet_aux_signed_eq (hbf j (by omega)) have h2 : alpha_signed_cell (b.drop k) j = alpha_signed_cell (f.drop k) j := by apply alpha_meet_aux_signed_eq simp only [alpha_meet_aux_get_d_drop] exact hbf _ (by omega) rw [h2, h1] exact hborder j (by omega) have hgreater : alpha_signed_cell b (q - 1) < alpha_signed_cell (b.drop k) (q - 1) := by simp only [alpha_signed_cell, hj0, if_true, alpha_meet_aux_get_d_drop, hjk] rw [hbf _ hjl, hcross] exact_mod_cast hlast exact False.elim ((alpha_meet_aux_not_lt_of_first_difference (b.drop k) b (q - 1) hpre hgreater) (hb.2.2 k (by omega) hk0))
The meet of any two lists a and b is either a, b, or p ++ [min x y] where a = p ++ x :: s and b = p ++ y :: t with x ≠ y.
We proceed by structural induction on a generalizing b. If either list is empty, the meet is empty (matching the empty list). If both lists are nonempty, we compare their head elements: if they are equal, the head is prepended to the meet of the tails; if they differ, the meet is [min x y] with an empty common prefix p = [].
uses
Or.inl,Or.inrinduction a generalizing b with | nil => exact Or.inl rfl | cons x xs ih => cases b with | nil => exact Or.inr (Or.inl rfl) | cons y ys => by_cases hxy : x = y · subst y rcases ih ys with h | h | ⟨p, u, v, s, t, huv, hx, hy, hf⟩ · exact Or.inl (by simp [alpha_lexical_meet, h]) · exact Or.inr (Or.inl (by simp [alpha_lexical_meet, h])) · right; right exact ⟨x :: p, u, v, s, t, huv, by simp [hx], by simp [hy], by simp [alpha_lexical_meet, hf]⟩ · exact Or.inr (Or.inr ⟨[], x, y, xs, ys, hxy, rfl, rfl, by simp [alpha_lexical_meet, hxy]⟩)
If x < y and both p ++ x :: s and p ++ y :: t are lexical, then p ++ [x] is lexical.
We apply alpha_meet_aux_lexical_of_prefix_branch to f = p ++ [x], a = p ++ x :: s, and b = p ++ y :: t. The list f is nonempty and inherits positivity from a. It is a prefix of a of length |p| + 1, agrees with b along the common prefix p of length |f| - 1, and satisfies f[|f| - 1] = x < y = b[|f| - 1] at the branching index.
uses
alpha_meet_aux_lexical_of_prefix_branch,List.mem_append.mp,List.mem_append.mpr,Or.inl,List.append_assoc,List.singleton_append,List.getD_append,List.length_append,List.length_singleton,Nat.add_sub_cancel,List.getD_append_right,le_reflapply alpha_meet_aux_lexical_of_prefix_branch (p ++ [x]) (p ++ x :: s) (p ++ y :: t) · simp · intro v hv apply ha.2.1 v rcases List.mem_append.mp hv with hv | hv · exact List.mem_append.mpr (Or.inl hv) · have : v = x := by simpa using hv subst v simp · simp · simp · exact ha · exact hb · intro j hj have he : p ++ x :: s = (p ++ [x]) ++ s := by simp only [List.append_assoc, List.singleton_append] rw [he, List.getD_append _ _ _ _ hj] · intro j hj have hj' : j < p.length := by simpa using hj rw [List.getD_append p (y :: t) 0 j hj', List.getD_append p [x] 0 j hj'] · simp only [List.length_append, List.length_singleton, Nat.add_sub_cancel] rw [List.getD_append_right _ _ _ _ (le_refl _), List.getD_append_right _ _ _ _ (le_refl _)] simpa using hxy
The lexical meet of two lexical sequences is lexical.
By the shape classification, the meet is either a, b, or p ++ [min x y] with x ≠ y. In the first two cases the meet is lexical by hypothesis. In the branching case, either x < y, so min x y = x and p ++ [x] is lexical by alpha_meet_aux_branch, or y < x, so min x y = y and p ++ [y] is lexical by the same lemma with the roles of a and b swapped.
uses
alpha_meet_aux_shape,lt_or_gt_of_ne,min_eq_left,le_of_lt,alpha_meet_aux_branch,min_eq_rightrcases alpha_meet_aux_shape a b with h | h | ⟨p, x, y, s, t, hxy, rfl, rfl, hf⟩ · rwa [h] · rwa [h] · rw [hf] rcases lt_or_gt_of_ne hxy with hlt | hgt · rw [min_eq_left (le_of_lt hlt)] exact alpha_meet_aux_branch p s t x y hlt ha hb · rw [min_eq_right (le_of_lt hgt)] exact alpha_meet_aux_branch p t s y x hgt hb ha
List.getD_eq_getElem?_getD- Looking up an element with a default value equals looking up the optional element and extracting it with the default.
List.getElem?_drop- The optional j-th element of xs.drop i is the optional (i + j)-th element of xs.
lt_trichotomy- In any linear order, exactly one of a < b, a = b, or b < a holds.
alpha_meet_aux_signed_eq- If two lists agree at index i, their signed cells at index i are equal.
alpha_meet_aux_get_d_drop- The j-th entry of a.drop k with default 0 equals the (k + j)-th entry of a with default 0.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
le_max_right- Any element b is less than or equal to max a b.
List.getD_eq_getElem- For an in-bounds index n < |l|, looking up n with a default value returns l[n].
List.getElem_mem- Any valid index lookup l[n] is an element of l.
List.getD_eq_default- Looking up an out-of-bounds index n ≥ |l| returns the default value.
List.length_drop- The length of l.drop i is |l| - i.
le_rfl- The inequality relation is reflexive: a ≤ a.
if_true- An if-then-else whose condition is true evaluates to the then-branch.
Nat.cast_zero- The natural number 0 coerced to an additive monoid with one equals 0.
False.elim- From a contradiction (False), any statement follows.
alpha_meet_aux_not_lt_of_first_difference- If two sequences agree on all signed cells before index i and the signed cell of b at i is strictly smaller than that of a, then a is not strictly lexicographically smaller than b.
Or.inl- A proof of a proves the disjunction a ∨ b.
Or.inr- A proof of b proves the disjunction a ∨ b.
alpha_meet_aux_lexical_of_prefix_branch- A nonempty positive sequence f is lexical if it is a prefix of lexical a, agrees with lexical b up to the penultimate element, and has a strictly smaller last element than b.
List.mem_append.mp- An element of l₁ ++ l₂ belongs to l₁ or to l₂.
List.mem_append.mpr- An element belonging to l₁ or to l₂ belongs to their concatenation l₁ ++ l₂.
List.append_assoc- List concatenation is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
List.singleton_append- Prepending a singleton [x] to l equals x :: l.
List.getD_append- Looking up an index n < |l| in l ++ l' equals looking up n in l.
List.length_append- The length of as ++ bs is |as| + |bs|.
List.length_singleton- A singleton list [a] has length 1.
Nat.add_sub_cancel- For natural numbers, n + m - m = n.
List.getD_append_right- Looking up an index n ≥ |l| in l ++ l' corresponds to index n - |l| in l'.
le_refl- Reflexivity of preorder: a ≤ a.
alpha_meet_aux_shape- The meet of two lists is either a, b, or of the form p ++ [min x y] where p is their common prefix and x ≠ y are the first differing entries.
lt_or_gt_of_ne- Two unequal elements in a linear order satisfy a < b or b < a.
min_eq_left- If a ≤ b, then min a b = a.
le_of_lt- A strict inequality a < b implies a ≤ b.
alpha_meet_aux_branch- If x < y and both p ++ x :: s and p ++ y :: t are lexical, then p ++ [x] is lexical.
min_eq_right- If b ≤ a, then min a b = b.
- The alternating lexicographical order defines signed cells with alternating signs: at even indices the values compare directly, while at odd indices the comparison is inverted because of the negative sign.
- Entries beyond the end of a list evaluate to 0 via default-valued lookup (getD), so at an even boundary index q = |f| - k, the truncated suffix has signed cell 0 while the original sequence has a strictly positive signed cell.
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_meet_aux_get_d_drop (a : List ℕ) (k j : ℕ) : (a.drop k).getD j 0 = a.getD (k + j) 0 := by simp only [List.getD_eq_getElem?_getD, List.getElem?_drop]theorem alpha_meet_aux_signed_eq {a b : List ℕ} {i : ℕ} (h : a.getD i 0 = b.getD i 0) : alpha_signed_cell a i = alpha_signed_cell b i := by simp only [alpha_signed_cell, h]theorem alpha_meet_aux_not_lt_of_first_difference (a b : List ℕ) (i : ℕ) (he : ∀ j < i, alpha_signed_cell a j = alpha_signed_cell b j) (hg : alpha_signed_cell b i < alpha_signed_cell a i) : ¬ alpha_lexical_lt a b := by rintro ⟨j, hj, he', hl⟩ rcases lt_trichotomy j i with hji | rfl | hij · have := he j hji omega · omega · have := he' i hij omegatheorem alpha_meet_aux_lexical_of_prefix_branch (f a b : List ℕ) (hfne : f ≠ []) (hfpos : ∀ v ∈ f, 0 < v) (hla : f.length ≤ a.length) (hlb : f.length ≤ b.length) (ha : alpha_is_lexical a) (hb : alpha_is_lexical b) (haf : ∀ j < f.length, a.getD j 0 = f.getD j 0) (hbf : ∀ j < f.length - 1, b.getD j 0 = f.getD j 0) (hlast : f.getD (f.length - 1) 0 < b.getD (f.length - 1) 0) : alpha_is_lexical f := by refine ⟨hfne, hfpos, ?_⟩ intro k hk hk0 let q := f.length - k have hq0 : 0 < q := by dsimp [q]; omega have hql : q < f.length := by dsimp [q]; omega have hqk : k + q = f.length := by dsimp [q]; omega have hfa (j : ℕ) (hj : j < f.length) : alpha_signed_cell a j = alpha_signed_cell f j := alpha_meet_aux_signed_eq (haf j hj) have hfad (j : ℕ) (hj : j < q) : alpha_signed_cell (a.drop k) j = alpha_signed_cell (f.drop k) j := by apply alpha_meet_aux_signed_eq simp only [alpha_meet_aux_get_d_drop] exact haf _ (by omega) obtain ⟨i, hi, he, hlt⟩ := ha.2.2 k (by omega) hk0 by_cases hiq : i < q · refine ⟨i, ?_, ?_, ?_⟩ · have : i < f.length := by omega exact lt_of_lt_of_le this (le_max_right _ _) · intro j hj rw [← hfad j (by omega), ← hfa j (by omega)] exact he j hj · rw [← hfad i hiq, ← hfa i (by omega)] exact hlt · have hborder (j : ℕ) (hj : j < q) : alpha_signed_cell (f.drop k) j = alpha_signed_cell f j := by rw [← hfad j hj, ← hfa j (by omega)] exact he j (by omega) by_cases hqe : q % 2 = 0 · refine ⟨q, lt_of_lt_of_le hql (le_max_right _ _), hborder, ?_⟩ have hmem : f.getD q 0 ∈ f := by rw [List.getD_eq_getElem _ _ hql] exact List.getElem_mem hql have hp := hfpos _ hmem have hd : (f.drop k).getD q 0 = 0 := List.getD_eq_default _ _ (by simpa only [List.length_drop] using (le_rfl : f.length - k ≤ f.length - k)) simp only [alpha_signed_cell, hqe, if_true, hd, Nat.cast_zero] exact_mod_cast hp · have hj0 : (q - 1) % 2 = 0 := by omega have hjl : q - 1 < f.length - 1 := by omega have hjk : k + (q - 1) = f.length - 1 := by omega have hcross : f.getD (q - 1) 0 = f.getD (f.length - 1) 0 := by have h := hborder (q - 1) (by omega) simp only [alpha_signed_cell, hj0, if_true, alpha_meet_aux_get_d_drop, hjk] at h omega have hpre : ∀ j < q - 1, alpha_signed_cell (b.drop k) j = alpha_signed_cell b j := by intro j hj have h1 : alpha_signed_cell b j = alpha_signed_cell f j := alpha_meet_aux_signed_eq (hbf j (by omega)) have h2 : alpha_signed_cell (b.drop k) j = alpha_signed_cell (f.drop k) j := by apply alpha_meet_aux_signed_eq simp only [alpha_meet_aux_get_d_drop] exact hbf _ (by omega) rw [h2, h1] exact hborder j (by omega) have hgreater : alpha_signed_cell b (q - 1) < alpha_signed_cell (b.drop k) (q - 1) := by simp only [alpha_signed_cell, hj0, if_true, alpha_meet_aux_get_d_drop, hjk] rw [hbf _ hjl, hcross] exact_mod_cast hlast exact False.elim ((alpha_meet_aux_not_lt_of_first_difference (b.drop k) b (q - 1) hpre hgreater) (hb.2.2 k (by omega) hk0))theorem alpha_meet_aux_shape (a b : List ℕ) : alpha_lexical_meet a b = a ∨ alpha_lexical_meet a b = b ∨ ∃ p x y s t, x ≠ y ∧ a = p ++ x :: s ∧ b = p ++ y :: t ∧ alpha_lexical_meet a b = p ++ [min x y] := by induction a generalizing b with | nil => exact Or.inl rfl | cons x xs ih => cases b with | nil => exact Or.inr (Or.inl rfl) | cons y ys => by_cases hxy : x = y · subst y rcases ih ys with h | h | ⟨p, u, v, s, t, huv, hx, hy, hf⟩ · exact Or.inl (by simp [alpha_lexical_meet, h]) · exact Or.inr (Or.inl (by simp [alpha_lexical_meet, h])) · right; right exact ⟨x :: p, u, v, s, t, huv, by simp [hx], by simp [hy], by simp [alpha_lexical_meet, hf]⟩ · exact Or.inr (Or.inr ⟨[], x, y, xs, ys, hxy, rfl, rfl, by simp [alpha_lexical_meet, hxy]⟩)theorem alpha_meet_aux_branch (p s t : List ℕ) (x y : ℕ) (hxy : x < y) (ha : alpha_is_lexical (p ++ x :: s)) (hb : alpha_is_lexical (p ++ y :: t)) : alpha_is_lexical (p ++ [x]) := by apply alpha_meet_aux_lexical_of_prefix_branch (p ++ [x]) (p ++ x :: s) (p ++ y :: t) · simp · intro v hv apply ha.2.1 v rcases List.mem_append.mp hv with hv | hv · exact List.mem_append.mpr (Or.inl hv) · have : v = x := by simpa using hv subst v simp · simp · simp · exact ha · exact hb · intro j hj have he : p ++ x :: s = (p ++ [x]) ++ s := by simp only [List.append_assoc, List.singleton_append] rw [he, List.getD_append _ _ _ _ hj] · intro j hj have hj' : j < p.length := by simpa using hj rw [List.getD_append p (y :: t) 0 j hj', List.getD_append p [x] 0 j hj'] · simp only [List.length_append, List.length_singleton, Nat.add_sub_cancel] rw [List.getD_append_right _ _ _ _ (le_refl _), List.getD_append_right _ _ _ _ (le_refl _)] simpa using hxytheorem alpha_lexical_meet_is_lexical (a b : List ℕ) (ha : alpha_is_lexical a) (hb : alpha_is_lexical b) : alpha_is_lexical (alpha_lexical_meet a b) := by rcases alpha_meet_aux_shape a b with h | h | ⟨p, x, y, s, t, hxy, rfl, rfl, hf⟩ · rwa [h] · rwa [h] · rw [hf] rcases lt_or_gt_of_ne hxy with hlt | hgt · rw [min_eq_left (le_of_lt hlt)] exact alpha_meet_aux_branch p s t x y hlt ha hb · rw [min_eq_right (le_of_lt hgt)] exact alpha_meet_aux_branch p t s y x hgt hb ha