AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_odd_completion_iff_rotation_max

theoremverified

For any length n at least three, a nonempty positive sequence of sum n−1 is lexical if and only if its odd-parity binary completion is nonconstant and has strictly greater inverse Gray rank than each of its nontrivial cyclic rotations. No primality assumption is required.

Statement

theorem alpha_lexical_odd_completion_iff_rotation_max (n : ℕ)
    (hn3 : 3 ≤ n) (a : List ℕ) (hne : a ≠ [])
    (ha : ∀ v ∈ a, 0 < v) (hs : a.sum + 1 = n) :
    alpha_is_lexical a ↔
      let x := 2 * alpha_binary_prefix a + (a.length + 1) % 2
      0 < x ∧ x < 2 ^ n - 1 ∧
        ∀ r : ℕ, 0 < r → r < n →
          brgc_inverse n ((bitword_rotate n)^[r] x) < brgc_inverse n x
Source
The existing proof of alpha_lexical_odd_completion_iff_rotation_max_of_prime uses no primality hypothesis; the result is needed to check composite-degree examples arising from OP-392, arXiv:2610.24758.
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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…
  • alpha_is_lexicalA nonempty positive sequence strictly larger than all its proper nonempty suffixes.
  • brgc_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
  • 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.
  • alpha_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
  • alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
Used by 1

The proof, explained

The theorem characterizes when a positive sequence a of sum n - 1 is lexical in terms of its completed binary word x. The proof proceeds by case analysis on the parity of the length of a. In each case, a is completed to a sequence C of sum n (by appending 1 if the length is even, or by incrementing the last entry if the length is odd) such that x equals the binary prefix of C. The bridge lemma `alpha_rot_glue` translates the inverse Gray rank bit-rotation maximality condition on x into a cyclic rotation condition on C, which parity-specific reduction lemmas (`alpha_rot_core_even` and `alpha_rot_core_odd`) then show to be equivalent to a being lexical.

  1. The equivalence is split into two cases based on the parity of the length of a.

    Expanding the local definition of x yields 2 * alpha_binary_prefix a + (|a| + 1) % 2. By `Nat.mod_two_eq_zero_or_one`, the length of a is either even (|a| % 2 = 0) or odd (|a| % 2 = 1).

    lines 9–10

    uses Nat.mod_two_eq_zero_or_one

      dsimp only
      rcases Nat.mod_two_eq_zero_or_one a.length with hev | hodd
  2. When a has even length, the completed sequence C = a ++ [1] satisfies x = alpha_binary_prefix C, with strictly positive entries summing to n.

    Since |a| is even, (|a| + 1) % 2 = 1, so x = 2 * alpha_binary_prefix a + 1. By `alpha_rot_completion_even`, this matches the binary prefix of C = a ++ [1]. Every element of C is strictly positive by `List.mem_append.mp` (since entries of a are positive and 1 > 0), and the sum of C is a.sum + 1 = n.

    lines 11–16

    uses alpha_rot_completion_even, List.mem_append.mp

      · rw [show (a.length + 1) % 2 = 1 by omega, alpha_rot_completion_even a]
        have hCpos : ∀ v ∈ a ++ [1], 0 < v := by
          intro v hv; rcases List.mem_append.mp hv with h | h
          · exact ha v h
          · simp at h; omega
        have hCsum : (a ++ [1]).sum = n := by simp; omega
  3. In the even-length case, a is lexical if and only if x is nonconstant and strictly maximal under inverse Gray code bit-rotations.

    Applying `alpha_rot_glue` turns the Gray rank rotation condition on x = alpha_binary_prefix (a ++ [1]) into the condition that every nontrivial cyclic rotation of a ++ [1] is strictly lexically smaller than a ++ [1]. Concurrently, `alpha_rot_core_even` characterizes `alpha_is_lexical a` as saying that for all 0 < k < |a| + 1, the split drop k a ++ [1] ++ take k a is lexically smaller than a ++ [1]. After expanding lengths using `List.length_append` and `List.length_singleton`, `alpha_rot_even_R_eq` shows that these split lists coincide with the standard cyclic rotations of a ++ [1], completing the equivalence in both directions.

    lines 17–21

    uses alpha_rot_glue, alpha_rot_core_even, List.length_append, List.length_singleton, alpha_rot_even_R_eq

        rw [← alpha_rot_glue n _ hCpos hCsum hn3, alpha_rot_core_even a hne ha hev]
        simp only [List.length_append, List.length_singleton]
        constructor
        · intro H k hk0 hk; rw [alpha_rot_even_R_eq a k (by omega)]; exact H k hk0 hk
        · intro H k hk0 hk; rw [← alpha_rot_even_R_eq a k (by omega)]; exact H k hk0 hk
  4. When a has odd length, it can be decomposed as a' ++ [c] with c > 0.

    By `List.eq_nil_or_concat'`, a is either empty or of the form a' ++ [c]. Since a is nonempty, it must be a' ++ [c], and its final element c is strictly positive because all entries of a are positive.

    lines 22–24

    uses List.eq_nil_or_concat'

      · rcases List.eq_nil_or_concat' a with h | ⟨a', c, rfl⟩
        · exact absurd h hne
        have hc : 0 < c := ha c (by simp)
  5. When a = a' ++ [c] has odd length, the completion C = a' ++ [c + 1] satisfies x = alpha_binary_prefix C, with strictly positive entries summing to n.

    Since |a| is odd, (|a| + 1) % 2 = 0. Using `add_zero`, x simplifies to 2 * alpha_binary_prefix (a' ++ [c]), which equals alpha_binary_prefix (a' ++ [c + 1]) by `alpha_rot_completion_odd`. We verify that all entries in a' ++ [c + 1] are strictly positive using `List.mem_append.mp` and that their sum is (a' ++ [c]).sum + 1 = n.

    lines 25–31

    uses add_zero, alpha_rot_completion_odd, List.mem_append.mp

        rw [show ((a' ++ [c]).length + 1) % 2 = 0 by omega, add_zero,
          alpha_rot_completion_odd a' c hc]
        have hCpos : ∀ v ∈ a' ++ [c + 1], 0 < v := by
          intro v hv; rcases List.mem_append.mp hv with h | h
          · exact ha v (by simp [h])
          · simp at h; omega
        have hCsum : (a' ++ [c + 1]).sum = n := by simp at hs ⊢; omega
  6. In the odd-length case, a is lexical if and only if x is nonconstant and strictly maximal under inverse Gray code bit-rotations.

    By `alpha_rot_glue`, the Gray rank rotation condition on x = alpha_binary_prefix (a' ++ [c + 1]) is equivalent to every nontrivial cyclic rotation of a' ++ [c + 1] being strictly lexically smaller than a' ++ [c + 1]. By `alpha_rot_core_odd`, a' ++ [c] is lexical if and only if this cyclic rotation condition holds for 0 < k < |a'| + 1. Rewriting the length of a' ++ [c + 1] to |a'| + 1 with `List.length_append` and `List.length_singleton` makes both sides identical, closing the proof.

    lines 32–33

    uses alpha_rot_glue, alpha_rot_core_odd, List.length_append, List.length_singleton

        rw [← alpha_rot_glue n _ hCpos hCsum hn3, alpha_rot_core_odd a' c ha hodd]
        simp only [List.length_append, List.length_singleton]
Nat.mod_two_eq_zero_or_one
Every natural number modulo 2 is either 0 or 1.
alpha_rot_completion_even
Twice the binary prefix of a list plus 1 equals the binary prefix of that list with 1 appended.
List.mem_append.mp
An element of a concatenated list belongs to the first list or the second list.
alpha_rot_glue
For any sequence C of positive integers summing to n ≥ 3, every nontrivial cyclic rotation of C is strictly lexically smaller than C if and only if the binary prefix of C is nonconstant (between 0 and 2^n - 1) and strictly maximizes the inverse Gray code rank among all nontrivial bit-rotations.
alpha_rot_core_even
A nonempty positive sequence a of even length is lexical if and only if for all 0 < k < |a| + 1, the list formed by dropping k elements, inserting 1, and appending the first k elements is strictly lexically smaller than a ++ [1].
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
List.length_singleton
The length of a singleton list is 1.
alpha_rot_even_R_eq
For k ≤ |a|, cyclically rotating a ++ [1] by k positions is identical to dropping k elements from a, inserting 1, and appending the first k elements of a.
List.eq_nil_or_concat'
Every list is either empty or the concatenation of an initial sublist and a final element.
add_zero
Adding zero to any element leaves it unchanged.
alpha_rot_completion_odd
For c > 0, twice the binary prefix of a ++ [c] equals the binary prefix of a ++ [c + 1].
alpha_rot_core_odd
A positive sequence a' ++ [c] of odd length is lexical if and only if every cyclic rotation of a' ++ [c + 1] by 0 < k < |a'| + 1 is strictly lexically smaller than a' ++ [c + 1].

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

theorem alpha_lexical_odd_completion_iff_rotation_max (n : ℕ)    (hn3 : 3 ≤ n) (a : List ℕ) (hne : a ≠ [])    (ha : ∀ v ∈ a, 0 < v) (hs : a.sum + 1 = n) :    alpha_is_lexical a ↔      let x := 2 * alpha_binary_prefix a + (a.length + 1) % 2      0 < x ∧ x < 2 ^ n - 1 ∧        ∀ r : ℕ, 0 < r → r < n →          brgc_inverse n ((bitword_rotate n)^[r] x) < brgc_inverse n x := by  dsimp only  rcases Nat.mod_two_eq_zero_or_one a.length with hev | hodd  · rw [show (a.length + 1) % 2 = 1 by omega, alpha_rot_completion_even a]    have hCpos : ∀ v ∈ a ++ [1], 0 < v := by      intro v hv; rcases List.mem_append.mp hv with h | h      · exact ha v h      · simp at h; omega    have hCsum : (a ++ [1]).sum = n := by simp; omega    rw [← alpha_rot_glue n _ hCpos hCsum hn3, alpha_rot_core_even a hne ha hev]    simp only [List.length_append, List.length_singleton]    constructor    · intro H k hk0 hk; rw [alpha_rot_even_R_eq a k (by omega)]; exact H k hk0 hk    · intro H k hk0 hk; rw [← alpha_rot_even_R_eq a k (by omega)]; exact H k hk0 hk  · rcases List.eq_nil_or_concat' a with h | ⟨a', c, rfl⟩    · exact absurd h hne    have hc : 0 < c := ha c (by simp)    rw [show ((a' ++ [c]).length + 1) % 2 = 0 by omega, add_zero,      alpha_rot_completion_odd a' c hc]    have hCpos : ∀ v ∈ a' ++ [c + 1], 0 < v := by      intro v hv; rcases List.mem_append.mp hv with h | h      · exact ha v (by simp [h])      · simp at h; omega    have hCsum : (a' ++ [c + 1]).sum = n := by simp at hs ⊢; omega    rw [← alpha_rot_glue n _ hCpos hCsum hn3, alpha_rot_core_odd a' c ha hodd]    simp only [List.length_append, List.length_singleton]
See it in the graphDiscuss this resultChallenge it