alpha_lexical_terminal_nonharmonic_fifteen
The lexical sequence (2,1,2,2,1,1,1,2,1,1) has degree 14 and a lexical prefix of length two. Splitting the cell at index two is nonlexical, every later even-indexed elementary operation is also nonlexical, and the sequence is not the first harmonic u_o u of any sequence u.
Statement
theorem alpha_lexical_terminal_nonharmonic_fifteen : let a : List ℕ := [2,1,2,2,1,1,1,2,1,1] alpha_is_lexical a ∧ a.sum + 1 = 15 ∧ alpha_is_lexical (a.take 2) ∧ ¬ alpha_is_lexical (a.take 2 ++ [a.getD 2 0 - 1, 1] ++ a.drop 3) ∧ (∀ j : Fin 10, 2 < j.val → j.val % 2 = 0 → ¬ alpha_is_lexical (if 1 < a.getD j.val 0 then a.take j.val ++ [a.getD j.val 0 - 1, 1] ++ a.drop (j.val + 1) else a.take (j.val - 1) ++ [a.getD (j.val - 1) 0 + 1] ++ a.drop (j.val + 1))) ∧ ¬ ∃ u : List ℕ, a = (if u.length % 2 = 0 then u ++ [1] else u.dropLast ++ [u.getLastD 0 + 1]) ++ u
- Source
- Computed obstruction to a simplified periodicity route for OP-392, arXiv:2610.24758; lexical order, elementary operations and harmonics follow arXiv:0810.5205, Section 1.1 and Section 2.
- Verified
- 13 Nov 2026
- Axioms
Quot.soundpropext- Built on 2
- 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.
The proof, explained
The first five properties of the sequence w = (2,1,2,2,1,1,1,2,1,1)—its degree, lexicality, lexical prefix, and nonlexicality of all even elementary operations—are finite computations proved by decide. To show w is not harmonic (not of the form oddExt u ++ u), we equate list lengths to deduce that any witness u must have length 5. This forces u to be the suffix of length 5 of w, namely (1,1,2,1,1), but evaluating oddExt on this candidate yields a list starting with 1 rather than 2, a contradiction.
The lexicographic comparison relation alpha_lexical_lt is decidable.
Unfolding the definition expresses alpha_lexical_lt as a bounded search over list indices with decidable comparisons of signed cell values. Typeclass inference synthesizes the decidability instance.
unfold alpha_lexical_lt infer_instance
The lexicality property alpha_is_lexical is decidable.
Unfolding the definition expresses lexicality as list non-emptiness, positivity of all elements, and bounded lexicographic comparisons between suffixes and the sequence. Typeclass inference synthesizes decidability using the instance for alpha_lexical_lt.
unfold alpha_is_lexical infer_instance
The sequence w satisfies the five finite conditions on degree, lexicality, prefix, and elementary operations. automation
The sequence w = [2,1,2,2,1,1,1,2,1,1] is lexical, has degree 14 (sum + 1 = 15), has a lexical prefix of length 2, and all elementary operations at even indices j ≥ 2 yield nonlexical sequences. Since all these properties are decidable, the entire conjunction is verified by computational evaluation (decide).
∀ j : Fin 10, 2 < j.val → j.val % 2 = 0 → ¬ alpha_is_lexical (op w j.val) := by decide
To prove the theorem, it suffices to show that w is not of the form oddExt u ++ u for any sequence u.
The theorem statement is rephrased using the definitions w, op, and oddExt. The first five conjuncts are directly discharged by finiteFacts, leaving only the negation of the harmonic decomposition.
change alpha_is_lexical w ∧ w.sum + 1 = 15 ∧ alpha_is_lexical (w.take 2) ∧ ¬ alpha_is_lexical (op w 2) ∧ (∀ j : Fin 10, 2 < j.val → j.val % 2 = 0 → ¬ alpha_is_lexical (op w j.val)) ∧ ¬ ∃ u : List ℕ, w = oddExt u ++ u refine ⟨finiteFacts.1, finiteFacts.2.1, finiteFacts.2.2.1, finiteFacts.2.2.2.1, finiteFacts.2.2.2.2, ?_⟩
Any witness u such that w = oddExt u ++ u must have length 5.
Assume for contradiction that w = oddExt u ++ u. Taking lengths of both sides, w has length 10. If the length of u were even, oddExt u would have length |u| + 1, so the total length would be 2|u| + 1 = 10, which is impossible. Thus |u| must be odd, which gives |oddExt u| = |u| and 2|u| = 10, forcing |u| = 5.
uses
congrArg,List.length_cons,List.length_nil,List.length_append,List.length_dropLastrintro ⟨u, hu⟩ have hl := congrArg List.length hu have hlen : u.length = 5 := by simp only [w, List.length_cons, List.length_nil, List.length_append, oddExt] at hl split at hl <;> simp only [List.length_append, List.length_dropLast, List.length_cons, List.length_nil] at hl <;> omega
The odd extension of u also has length 5.
Since u has length 5, which is odd, oddExt u is formed by dropping the last element and appending a single incremented element, so its length is 5 - 1 + 1 = 5.
uses
List.length_dropLasthave hext : (oddExt u).length = 5 := by simp [oddExt, hlen, List.length_dropLast]
Dropping the first 5 elements of w yields u.
Since w = oddExt u ++ u and oddExt u has length 5, dropping the first 5 elements of w removes oddExt u and leaves u.
have hd : w.drop 5 = u := by rw [hu, ← hext] simp
u must be the list [1, 1, 2, 1, 1].
Dropping the first 5 elements from the explicit list w = [2, 1, 2, 2, 1, 1, 1, 2, 1, 1] leaves [1, 1, 2, 1, 1], so u = [1, 1, 2, 1, 1].
have heq : u = [1,1,2,1,1] := by simpa [w] using hd.symm
Contradiction: w is not equal to oddExt u ++ u. automation
Substituting u = [1, 1, 2, 1, 1], the odd extension oddExt u evaluates to [1, 1, 2, 1, 2], and oddExt u ++ u evaluates to [1, 1, 2, 1, 2, 1, 1, 2, 1, 1]. This differs from w = [2, 1, 2, 2, 1, 1, 1, 2, 1, 1] at the first element (1 vs 2). Evaluation by norm_num derives False.
rw [heq] at hu norm_num [w, oddExt] at hu
congrArg- Applying a function to both sides of an equality preserves the equality.
List.length_cons- The length of a prepended list is one plus the length of the tail.
List.length_nil- The length of the empty list is zero.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
List.length_dropLast- The length of a list with its last element removed is its original length minus one.
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.
set_option maxHeartbeats 1000000instance (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_instanceprivate def oddExt (u : List ℕ) : List ℕ := if u.length % 2 = 0 then u ++ [1] else u.dropLast ++ [u.getLastD 0 + 1]private def op (a : List ℕ) (i : ℕ) : List ℕ := if 1 < a.getD i 0 then a.take i ++ [a.getD i 0 - 1, 1] ++ a.drop (i + 1) else a.take (i-1) ++ [a.getD (i-1) 0 + 1] ++ a.drop (i + 1)private def w : List ℕ := [2,1,2,2,1,1,1,2,1,1]private theorem finiteFacts : alpha_is_lexical w ∧ w.sum + 1 = 15 ∧ alpha_is_lexical (w.take 2) ∧ ¬ alpha_is_lexical (op w 2) ∧ ∀ j : Fin 10, 2 < j.val → j.val % 2 = 0 → ¬ alpha_is_lexical (op w j.val) := by decidetheorem alpha_lexical_terminal_nonharmonic_fifteen : let a : List ℕ := [2,1,2,2,1,1,1,2,1,1] alpha_is_lexical a ∧ a.sum + 1 = 15 ∧ alpha_is_lexical (a.take 2) ∧ ¬ alpha_is_lexical (a.take 2 ++ [a.getD 2 0 - 1, 1] ++ a.drop 3) ∧ (∀ j : Fin 10, 2 < j.val → j.val % 2 = 0 → ¬ alpha_is_lexical (if 1 < a.getD j.val 0 then a.take j.val ++ [a.getD j.val 0 - 1, 1] ++ a.drop (j.val + 1) else a.take (j.val - 1) ++ [a.getD (j.val - 1) 0 + 1] ++ a.drop (j.val + 1))) ∧ ¬ ∃ u : List ℕ, a = (if u.length % 2 = 0 then u ++ [1] else u.dropLast ++ [u.getLastD 0 + 1]) ++ u := by change alpha_is_lexical w ∧ w.sum + 1 = 15 ∧ alpha_is_lexical (w.take 2) ∧ ¬ alpha_is_lexical (op w 2) ∧ (∀ j : Fin 10, 2 < j.val → j.val % 2 = 0 → ¬ alpha_is_lexical (op w j.val)) ∧ ¬ ∃ u : List ℕ, w = oddExt u ++ u refine ⟨finiteFacts.1, finiteFacts.2.1, finiteFacts.2.2.1, finiteFacts.2.2.2.1, finiteFacts.2.2.2.2, ?_⟩ rintro ⟨u, hu⟩ have hl := congrArg List.length hu have hlen : u.length = 5 := by simp only [w, List.length_cons, List.length_nil, List.length_append, oddExt] at hl split at hl <;> simp only [List.length_append, List.length_dropLast, List.length_cons, List.length_nil] at hl <;> omega have hext : (oddExt u).length = 5 := by simp [oddExt, hlen, List.length_dropLast] have hd : w.drop 5 = u := by rw [hu, ← hext] simp have heq : u = [1,1,2,1,1] := by simpa [w] using hd.symm rw [heq] at hu norm_num [w, oddExt] at hu