AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_even_split_prime_obstruction

theoremverified

At degree parameter 13 there are two ordered lexical sequences of degree 12 with lexical meet (3,1). Splitting the later sequence at its even zero-based index 2 produces a nonlexical sequence, even though the prefix before the split is lexical. The witnesses are (3,2,2,3,2), (3,1,2,1,3,1,1), and (3,1,1,1,1,3,1,1). No claim of adjacency is made.

Statement

theorem alpha_lexical_even_split_prime_obstruction :
  let a : List ℕ := [3,2,2,3,2]
  let b : List ℕ := [3,1,2,1,3,1,1]
  let c : List ℕ := [3,1,1,1,1,3,1,1]
  alpha_is_lexical a ∧ alpha_is_lexical b ∧ alpha_lexical_lt a b ∧
  a.sum + 1 = 13 ∧ b.sum + 1 = 13 ∧ Nat.Prime 13 ∧
  alpha_lexical_meet a b = [3,1] ∧ alpha_is_lexical (b.take 2) ∧
  alpha_elementary_cell_step b c 2 ∧ ¬ alpha_is_lexical c
Source
Computed obstruction to a possible structural route for OP-392, arXiv:2610.24758; lexical definitions from arXiv:0810.5205, Section 2.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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.
  • alpha_elementary_cell_stepOne source elementary split or conjugation, with a zero-based cell index.

The proof, explained

The theorem is established by finite computational reflection. Decidability instances for the signed lexicographic comparison, the lexical predicate, and the elementary cell transitions are first registered by unfolding their definitions into bounded quantifiers and invoking typeclass synthesis. The kernel's `decide` tactic then evaluates the full conjunction on the explicit witnesses $a = [3,2,2,3,2]$, $b = [3,1,2,1,3,1,1]$, and $c = [3,1,1,1,1,3,1,1]$, verifying that $b$ is lexical of prime degree parameter 13, but splitting its cell at even index 2 yields $c$, which fails to be lexical despite having a lexical prefix.

  1. The signed lexicographic relation `alpha_lexical_lt a b` is decidable for all lists $a$ and $b$.

    Unfolding the definition of `alpha_lexical_lt` expresses the relation as an existential quantifier bounded by $\max(|a|, |b|)$, asserting the existence of an index $i$ where all preceding signed cells match and the $i$-th signed cell of $a$ is strictly less than that of $b$. Since all quantifiers are bounded and integer arithmetic comparisons are decidable, typeclass resolution (`infer_instance`) automatically synthesizes the decision procedure.

    lines 2–3

      unfold alpha_lexical_lt
      infer_instance
  2. The property `alpha_is_lexical a` is decidable for any list $a$.

    Unfolding `alpha_is_lexical` reduces the condition to three checks: non-emptiness of $a$, positivity of each element $v \in a$, and the requirement that every non-empty proper suffix $a.\text{drop}(k)$ ($0 < k < |a|$) satisfies `alpha_lexical_lt (a.drop k) a`. Each check is bounded over the finite list $a$, and the decidability of `alpha_lexical_lt` was established in the preceding instance, allowing typeclass resolution (`infer_instance`) to synthesize the decider.

    lines 5–6

      unfold alpha_is_lexical
      infer_instance
  3. The elementary cell transition `alpha_elementary_cell_step a b i` is decidable for all lists $a, b$ and index $i$.

    Unfolding `alpha_elementary_cell_step` reveals a finite disjunction of conditions: index validity $i < |a|$, comparisons with 1, and equality of $b$ with explicit list reconstructions via `take`, `drop`, and concatenation. Because equality of lists of natural numbers and arithmetic comparisons are decidable, typeclass resolution (`infer_instance`) automatically synthesizes the decision procedure.

    lines 8–9

      unfold alpha_elementary_cell_step
      infer_instance
  4. The prime obstruction holds: sequences $a = [3,2,2,3,2]$, $b = [3,1,2,1,3,1,1]$, and $c = [3,1,1,1,1,3,1,1]$ satisfy all ten conjuncts, proving that splitting $b$ at even index 2 yields a nonlexical sequence $c$. automation

    The `decide` tactic discharges the entire goal by computational reflection in the Lean kernel, evaluating the boolean decision procedures established above on the explicit lists $a$, $b$, and $c$. The kernel verifies: (1) $a$ and $b$ are lexical; (2) $a < b$ in the signed lexical order, since their first discrepancy occurs at odd index 1 where $-a[1] = -2 < -1 = -b[1]$; (3) both entries sum to 12, so the degree parameter $12 + 1 = 13$ is prime; (4) the lexical meet of $a$ and $b$ is $[3, \min(2, 1)] = [3, 1]$; (5) the prefix $b.\text{take}(2) = [3, 1]$ is lexical; (6) $c$ is obtained from $b$ by splitting cell 2 ($b[2] = 2$ becomes $[1, 1]$); and (7) $c$ is not lexical, because its suffix $c.\text{drop}(5) = [3, 1, 1]$ is strictly greater than $c$ under the signed lexical order (at index 3, the odd-indexed signed cell gives $0 > -1$).

    line 18

      alpha_elementary_cell_step b c 2 ∧ ¬ alpha_is_lexical c := by decide

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

instance (a b : List ℕ) : Decidable (alpha_lexical_lt a b) := by  unfold alpha_lexical_lt  infer_instanceinstance (a : List ℕ) : Decidable (alpha_is_lexical a) := by  unfold alpha_is_lexical  infer_instanceinstance (a b : List ℕ) (i : ℕ) : Decidable (alpha_elementary_cell_step a b i) := by  unfold alpha_elementary_cell_step  infer_instancetheorem alpha_lexical_even_split_prime_obstruction :  let a : List ℕ := [3,2,2,3,2]  let b : List ℕ := [3,1,2,1,3,1,1]  let c : List ℕ := [3,1,1,1,1,3,1,1]  alpha_is_lexical a ∧ alpha_is_lexical b ∧ alpha_lexical_lt a b ∧  a.sum + 1 = 13 ∧ b.sum + 1 = 13 ∧ Nat.Prime 13 ∧  alpha_lexical_meet a b = [3,1] ∧ alpha_is_lexical (b.take 2) ∧  alpha_elementary_cell_step b c 2 ∧ ¬ alpha_is_lexical c := by decide
See it in the graphDiscuss this resultChallenge it