AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_terminal_nonharmonic_fifteen

theoremverified

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.

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

    lines 4–5

      unfold alpha_lexical_lt
      infer_instance
  2. 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.

    lines 7–8

      unfold alpha_is_lexical
      infer_instance
  3. 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).

    line 19

        ∀ j : Fin 10, 2 < j.val → j.val % 2 = 0 → ¬ alpha_is_lexical (op w j.val) := by decide
  4. 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.

    lines 32–37

      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, ?_⟩
  5. 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.

    lines 38–43

    uses congrArg, List.length_cons, List.length_nil, List.length_append, List.length_dropLast

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

    lines 44–45

    uses List.length_dropLast

      have hext : (oddExt u).length = 5 := by
        simp [oddExt, hlen, List.length_dropLast]
  7. 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.

    lines 46–48

      have hd : w.drop 5 = u := by
        rw [hu, ← hext]
        simp
  8. 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].

    lines 49–50

      have heq : u = [1,1,2,1,1] := by
        simpa [w] using hd.symm
  9. 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.

    lines 51–52

      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

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