AFTD Auto-Formalizing Theoretical Domains

alpha_prime_lexical_meet_nondvd_of_ne

theoremverified

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

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

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

    line 6

    uses alpha_lexical_meet_is_lexical

      have hf := alpha_lexical_meet_is_lexical a b ha hb
  2. The 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.

    lines 7–13

    uses False.elim, List.sum_cons

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

    lines 14–15

    uses alpha_lexical_meet_sum_lt_of_ne_of_sum_eq

      have hlt := alpha_lexical_meet_sum_lt_of_ne_of_sum_eq a b ha.2.1 hb.2.1 hne
        (by omega)
  4. 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.

    lines 16–17

    uses hp.eq_one_or_self_of_dvd

      intro 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

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