AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_example_eleven

theoremverified

Kernel-checked encoding of the length-eleven example in arXiv:0810.5205, Example 3.2, including its one-bit completed words and the uniform rotation to forward Gray ranks.

Statement

theorem alpha_lexical_example_eleven :
    alpha_is_lexical [3, 2, 3, 2] ∧
    alpha_is_lexical [3, 1, 1, 3, 2] ∧
    alpha_elementary_cell_step [3, 2, 3, 2] [3, 1, 1, 3, 2] 1 ∧
    alpha_lexical_lt [3, 2, 3, 2] [3, 1, 1, 3, 2] ∧
    alpha_lexical_meet [3, 2, 3, 2] [3, 1, 1, 3, 2] = [3, 1] ∧
    alpha_binary_prefix [3, 2, 3, 2] = 594 ∧
    alpha_binary_prefix [3, 1, 1, 3, 2] = 626 ∧
    (594 : ℕ) ^^^ 626 = 2 ^ 5 ∧
    (1189 : ℕ) ^^^ 1253 = 2 ^ 6 ∧
    brgc_word 1849 = 1189 ∧ brgc_word 1862 = 1253 ∧
    bitword_rotate 11 1189 = 331 ∧ bitword_rotate 11 1253 = 459 ∧
    brgc_word 397 = 331 ∧ brgc_word 370 = 459 ∧
    (331 : ℕ) ^^^ 459 = 2 ^ 7
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
Quot.soundpropext
Built on 8
  • 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_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_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • bitword_rotateCyclic rotation of an n-bit word x (a number below 2^n) by one position: the word is shifted up and its top bit moves to the bottom.
Used by 2

The proof, explained

The theorem verifies fifteen concrete combinatorial and arithmetic properties of the length-11 example (Example 3.2) from arXiv:0810.5205 via direct computational evaluation. The overall strategy reduces the mathematical claims to finite decidable checks: with decidability established for the signed lexical comparison, the lexicality predicate, and elementary cell transitions, each condition is decidable. Lean's kernel decision procedure decide then evaluates the entire fifteen-part conjunction to true by finite reduction.

  1. The transition relation alpha_elementary_cell_step a b i is decidable for any compositions a, b and index i. automation

    Unfolding the definition of alpha_elementary_cell_step reduces the transition condition to a finite propositional combination of bounds checks (i < |a|), list equalities involving slicing and concatenation, and natural number comparisons. Because list equality and arithmetic inequalities on ℕ are decidable, typeclass inference (infer_instance) automatically synthesizes the Decidable instance for this combination.

    lines 12–13

      unfold alpha_elementary_cell_step
      infer_instance
  2. All fifteen conditions of Example 3.2 from arXiv:0810.5205 hold: the words [3, 2, 3, 2] and [3, 1, 1, 3, 2] are lexical, form an elementary cell step at index 1, satisfy the signed lexical order and meet conditions, have binary prefix encodings 594 and 626 differing by 2^5, complete to 11-bit words 1189 and 1253 with binary reflected Gray code ranks 1849 and 1862, and rotate to 11-bit words 331 and 459 with Gray ranks 397 and 370 differing by 2^7. automation

    The goal is a conjunction of fifteen concrete claims: four relational assertions about lexicality, an elementary cell step, and signed lexical comparison; and eleven arithmetic and list equalities involving binary prefix sums, bitwise XOR, power-of-two evaluations, Gray code word computations, and cyclic word rotations. Because every predicate has a decidable instance and every function is computable on finite inputs, the decision procedure decide evaluates the entire conjunction by kernel normalization, reducing it directly to true.

    line 29

      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 alpha_lexical_lt_decidable (a b : List ℕ) : Decidable (alpha_lexical_lt a b) :=  inferInstanceAs (Decidable (∃ i < max a.length b.length,    (∀ j < i, alpha_signed_cell a j = alpha_signed_cell b j) ∧      alpha_signed_cell a i < alpha_signed_cell b i))instance alpha_is_lexical_decidable (a : List ℕ) : Decidable (alpha_is_lexical a) :=  inferInstanceAs (Decidable (a ≠ [] ∧ (∀ v ∈ a, 0 < v) ∧    ∀ k < a.length, 0 < k → alpha_lexical_lt (a.drop k) a))instance alpha_elementary_cell_step_decidable (a b : List ℕ) (i : ℕ) :    Decidable (alpha_elementary_cell_step a b i) := by  unfold alpha_elementary_cell_step  infer_instancetheorem alpha_lexical_example_eleven :    alpha_is_lexical [3, 2, 3, 2] ∧    alpha_is_lexical [3, 1, 1, 3, 2] ∧    alpha_elementary_cell_step [3, 2, 3, 2] [3, 1, 1, 3, 2] 1 ∧    alpha_lexical_lt [3, 2, 3, 2] [3, 1, 1, 3, 2] ∧    alpha_lexical_meet [3, 2, 3, 2] [3, 1, 1, 3, 2] = [3, 1] ∧    alpha_binary_prefix [3, 2, 3, 2] = 594 ∧    alpha_binary_prefix [3, 1, 1, 3, 2] = 626 ∧    (594 : ℕ) ^^^ 626 = 2 ^ 5 ∧    (1189 : ℕ) ^^^ 1253 = 2 ^ 6 ∧    brgc_word 1849 = 1189 ∧ brgc_word 1862 = 1253 ∧    bitword_rotate 11 1189 = 331 ∧ bitword_rotate 11 1253 = 459 ∧    brgc_word 397 = 331 ∧ brgc_word 370 = 459 ∧    (331 : ℕ) ^^^ 459 = 2 ^ 7 := by  decide
See it in the graphDiscuss this resultChallenge it