alpha_lexical_example_eleven
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
- alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
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.
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.
unfold alpha_elementary_cell_step infer_instance
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.
decide
- The entire proof of alpha_lexical_example_eleven is executed by the automated decision procedure decide. All fifteen conjuncts—including lexicality verification, suffix comparisons, Gray code rankings, bitwise XOR differences, and word rotations—are checked by kernel reduction rather than deductive pencil-and-paper lemmas.
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.
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