alpha_lexical_odd_completion_iff_rotation_max
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
- alpha_lexical_terminal_predecessor_simple_star_obstructionThe two displayed lexical sequences are adjacent among sequences of degree 19 and have meet f=(2,1,1). The later sequence has a lexical…
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.
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).
uses
Nat.mod_two_eq_zero_or_onedsimp only rcases Nat.mod_two_eq_zero_or_one a.length with hev | hodd
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.
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
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.
uses
alpha_rot_glue,alpha_rot_core_even,List.length_append,List.length_singleton,alpha_rot_even_R_eqrw [← 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
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.
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)
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.
uses
add_zero,alpha_rot_completion_odd,List.mem_append.mprw [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
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.
uses
alpha_rot_glue,alpha_rot_core_odd,List.length_append,List.length_singletonrw [← 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].
- Linear arithmetic automation (`omega`) is used to discharge parity calculations, index inequalities, and list sum equalities.
- List simplification (`simp`) is used to evaluate list sums, list lengths, and membership in singleton lists.
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.
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]