alpha_prime_lexical_meet_nondvd_of_ne
For any distinct lexical sequences of the same prime degree, the meet degree is a proper nontrivial value and does not divide the ambient prime degree.
Statement
theorem alpha_prime_lexical_meet_nondvd_of_ne
(p : ℕ) (hp : p.Prime) (a b : List ℕ)
(ha : alpha_is_lexical a) (hb : alpha_is_lexical b)
(hsa : a.sum + 1 = p) (hsb : b.sum + 1 = p) (hne : a ≠ b) :
¬ ((alpha_lexical_meet a b).sum + 1) ∣ p- Source
- Proper-meet helpers for the published lexical adjacency criterion, arXiv:0810.5205v2, Theorem3.1 and Corollary3.3, supporting the run-length route for OP-392. These routine reductions do not prove the adjacency theorem and no research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- alpha_lexical_meet_sum_lt_of_ne_of_sum_eqThe common lexical meet of two distinct positive integer sequences of equal sum has strictly smaller sum than either input.
- alpha_lexical_meet_is_lexicalThe source common-prefix meet of two nonempty positive lexical sequences is lexical, even if their sums differ.
- alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
- alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
- alpha_lexical_meetThe common left factor, including the minimum value at the first unequal cell.
The proof, explained
The proof proceeds by contradiction: if the meet degree $(\text{alpha\_lexical\_meet}(a, b)).\text{sum} + 1$ divides the prime $p$, it must equal either $1$ or $p$. Because the meet of two lexical sequences is itself lexical, its elements are strictly positive, ruling out the value $1$. Furthermore, distinct lexical sequences of equal sum have a meet with strictly smaller sum, which rules out the value $p$.
The lexical meet of $a$ and $b$ is a lexical sequence.
Applying `alpha_lexical_meet_is_lexical` to the hypotheses that $a$ and $b$ are lexical shows that their meet is also lexical. By definition, this guarantees that the meet is non-empty and every entry in it is strictly positive.
uses
alpha_lexical_meet_is_lexicalhave hf := alpha_lexical_meet_is_lexical a b ha hbThe sum of the elements in the lexical meet of $a$ and $b$ is strictly positive.
We consider whether the meet list is empty (`nil`) or non-empty (`cons x xs`). If it were empty, this would contradict the fact that lexical sequences are non-empty, so `False.elim` rules it out. If it has head $x$ and tail $xs$, the head element $x$ belongs to the list and is therefore strictly positive by lexicality. Rewriting the list sum using `List.sum_cons`, linear arithmetic (`omega`) concludes that the sum is strictly positive.
uses
False.elim,List.sum_conshave hpos : 0 < (alpha_lexical_meet a b).sum := by cases he : alpha_lexical_meet a b with | nil => exact False.elim (hf.1 he) | cons x xs => have hx := hf.2.1 x (by rw [he]; simp) simp only [he, List.sum_cons] omega
The sum of the lexical meet is strictly less than the sum of $a$.
Since $a.\text{sum} + 1 = p$ and $b.\text{sum} + 1 = p$, linear arithmetic (`omega`) implies that $a.\text{sum} = b.\text{sum}$. Because $a$ and $b$ are distinct lexical sequences with all positive entries and equal sums, `alpha_lexical_meet_sum_lt_of_ne_of_sum_eq` proves that the sum of their lexical meet is strictly less than $a.\text{sum}$.
uses
alpha_lexical_meet_sum_lt_of_ne_of_sum_eqhave hlt := alpha_lexical_meet_sum_lt_of_ne_of_sum_eq a b ha.2.1 hb.2.1 hne (by omega)
The meet degree does not divide $p$.
Suppose, for contradiction, that $(\text{alpha\_lexical\_meet}(a, b)).\text{sum} + 1$ divides the prime $p$. By `hp.eq_one_or_self_of_dvd`, any divisor of $p$ must be either $1$ or $p$. If it equals $1$, the meet sum would be $0$, contradicting the fact that the sum is strictly positive. If it equals $p$, the meet sum would equal $a.\text{sum}$, contradicting the fact that the meet sum is strictly less than $a.\text{sum}$. In both cases, linear arithmetic (`omega`) derives a contradiction.
uses
hp.eq_one_or_self_of_dvdintro hd rcases hp.eq_one_or_self_of_dvd _ hd with he | he <;> omega
alpha_lexical_meet_is_lexical- If two sequences are lexical, then their lexical meet is also lexical.
False.elim- From a contradiction (False), any conclusion follows.
List.sum_cons- The sum of a list starting with head `x` and tail `xs` is `x + xs.sum`.
alpha_lexical_meet_sum_lt_of_ne_of_sum_eq- For two distinct sequences with all positive elements and equal sums, the sum of their lexical meet is strictly less than their sum.
hp.eq_one_or_self_of_dvd- Any natural number dividing a prime $p$ must equal either $1$ or $p$.
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_prime_lexical_meet_nondvd_of_ne (p : ℕ) (hp : p.Prime) (a b : List ℕ) (ha : alpha_is_lexical a) (hb : alpha_is_lexical b) (hsa : a.sum + 1 = p) (hsb : b.sum + 1 = p) (hne : a ≠ b) : ¬ ((alpha_lexical_meet a b).sum + 1) ∣ p := by have hf := alpha_lexical_meet_is_lexical a b ha hb have hpos : 0 < (alpha_lexical_meet a b).sum := by cases he : alpha_lexical_meet a b with | nil => exact False.elim (hf.1 he) | cons x xs => have hx := hf.2.1 x (by rw [he]; simp) simp only [he, List.sum_cons] omega have hlt := alpha_lexical_meet_sum_lt_of_ne_of_sum_eq a b ha.2.1 hb.2.1 hne (by omega) intro hd rcases hp.eq_one_or_self_of_dvd _ hd with he | he <;> omega