alpha_lexical_lt_iff_inverse_prefix
On equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
Statement
theorem alpha_lexical_lt_iff_inverse_prefix (a b : List ℕ) (ha : ∀ v ∈ a, 0 < v) (hb : ∀ v ∈ b, 0 < v) (hs : a.sum = b.sum) : alpha_lexical_lt a b ↔ brgc_inverse a.sum (alpha_binary_prefix a) < brgc_inverse b.sum (alpha_binary_prefix b)- 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
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- alpha_lexical_ltThe source alternating lexicographic order on positive integer sequences.
- alpha_signed_cellA cell of a positive sequence, with alternating signs and zero padding.
- alpha_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
- brgc_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
- brgc_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
- brgc_inverse_alpha_binary_prefix_consThe inverse Gray rank of x :: xs equals 2^xs.sum * (2^x - 1) + (2^xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)).
- alpha_lexical_lt_cons_samePrepending the same head to both sequences reverses the alternating lexical order on their tails.
- brgc_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
- alpha_lexical_example_elevenKernel-checked encoding of the length-eleven example in arXiv:0810.5205, Example 3.2, including its one-bit completed words and the…
- alpha_binary_prefix_boundsThe encoding of a nonempty positive cell sequence has exactly sum(a) bits and starts with a one.
- Used by 3
- lexical_degree_seventeen_class_a_counterexampleThe lexical sequences a = (3,1,1,3,3,2,2,1) and b = (3,1,1,2,1,3,2,2,1) both have degree 16, are adjacent in the source lexical 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…
- 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 equivalence between signed-alternating lexical order and inverse Gray-rank order is proved by induction on the combined length of the two lists via an auxiliary lemma. When both lists begin with the same head element, the head is stripped: this reverses the signed-alternating lexical comparison on the tails, which matches the inversion produced by subtracting the tail's inverse Gray rank in the recurrence formula. When the heads differ, the lexical comparison is determined entirely by the first element, while an auxiliary lower bound on non-empty Gray ranks ensures the Gray-rank recurrence is dominated by the head term. Specializing the auxiliary lemma to the combined length yields the main theorem.
For any non-empty list xs of positive integers, 2^(xs.sum - 1) ≤ brgc_inverse xs.sum (alpha_binary_prefix xs).
Writing xs = z :: zs with z > 0, we expand the inverse Gray rank recurrence via brgc_inverse_alpha_binary_prefix_cons and List.sum_cons. Since z ≥ 1, we have 2^(z - 1) ≤ 2^z - 1 using pow_succ' and Nat.one_le_two_pow. Multiplying by 2^(zs.sum) gives 2^(z + zs.sum - 1) ≤ 2^(zs.sum) * (2^z - 1) by Nat.mul_le_mul_left and pow_add. Adding the non-negative tail remainder via Nat.le_add_right completes the lower bound.
uses
brgc_inverse_alpha_binary_prefix_cons,List.sum_cons,pow_succ',Nat.one_le_two_pow,pow_add,Nat.mul_le_mul_left,Nat.le_add_rightmatch xs, hne with | z :: zs, _ => have hz : 0 < z := hxs z (by simp) have hzs : ∀ v ∈ zs, 0 < v := fun v hv => hxs v (by simp [hv]) rw [brgc_inverse_alpha_binary_prefix_cons z zs hz hzs, List.sum_cons] have h1 : 2 ^ (z - 1) ≤ 2 ^ z - 1 := by have : 2 ^ z = 2 * 2 ^ (z - 1) := by rw [← pow_succ']; congr 1; omega have := Nat.one_le_two_pow (n := z - 1) omega calc 2 ^ (z + zs.sum - 1) = 2 ^ zs.sum * 2 ^ (z - 1) := by rw [← pow_add]; congr 1; omega _ ≤ 2 ^ zs.sum * (2 ^ z - 1) := Nat.mul_le_mul_left _ h1 _ ≤ _ := Nat.le_add_right _ _
Base case (n = 0): the equivalence holds when the sum of lengths is at most 0.
By induction on n. When n = 0, the hypothesis a.length + b.length ≤ 0 forces both a = [] and b = [] by List.eq_nil_of_length_eq_zero. The signed lexical comparison alpha_lexical_lt [] [] is false because no index exists below max 0 0 = 0. The strict inequality of inverse Gray ranks is also false by irreflexivity (lt_irrefl). Thus both sides are false.
uses
List.eq_nil_of_length_eq_zero,lt_irreflinduction n with | zero => intro a b hl ha hb hs have ha0 : a = [] := List.eq_nil_of_length_eq_zero (by omega) have hb0 : b = [] := List.eq_nil_of_length_eq_zero (by omega) subst ha0 hb0 constructor · rintro ⟨i, hi, -⟩; simp at hi · intro h; exact absurd h (lt_irrefl _)
In the inductive step, the equivalence holds whenever either list is empty.
In the step for n + 1, we case-split on a and b. If both are empty, both sides are false by lt_irrefl as in the base case. If one is empty and the other is a cons cell, the non-empty list has strictly positive sum since all entries are positive, while the empty list has sum 0 (List.sum_nil, List.sum_cons), contradicting a.sum = b.sum.
uses
lt_irrefl,List.sum_nil,List.sum_cons| succ n ih => intro a b hl ha hs' hs have hb := hs' cases a with | nil => cases b with | nil => constructor · rintro ⟨i, hi, -⟩; simp at hi · intro h; exact absurd h (lt_irrefl _) | cons y ys => have := hb y (by simp) simp only [List.sum_nil, List.sum_cons] at hs; omega | cons x xs => cases b with | nil => have := ha x (by simp) simp only [List.sum_nil, List.sum_cons] at hs; omega | cons y ys =>
For non-empty lists x :: xs and y :: ys, the inverse Gray rank expands by recurrence and each tail rank is strictly bounded by 2^tail.sum.
Extracting positivity of the heads (hx, hy) and tails (hxs, hys), we expand both sides of the Gray rank inequality using brgc_inverse_alpha_binary_prefix_cons. The rank of xs is strictly bounded by 2^(xs.sum) via brgc_inverse_lt_two_pow and alpha_binary_prefix_bounds_lt, and similarly for ys.
uses
brgc_inverse_alpha_binary_prefix_cons,brgc_inverse_lt_two_pow,alpha_binary_prefix_bounds_lthave hx : 0 < x := ha x (by simp) have hy : 0 < y := hb y (by simp) have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (by simp [hv]) have hys : ∀ v ∈ ys, 0 < v := fun v hv => hb v (by simp [hv]) have hs' : x + xs.sum = y + ys.sum := by simpa using hs rw [brgc_inverse_alpha_binary_prefix_cons x xs hx hxs, brgc_inverse_alpha_binary_prefix_cons y ys hy hys] have hNx : brgc_inverse xs.sum (alpha_binary_prefix xs) < 2 ^ xs.sum := brgc_inverse_lt_two_pow (alpha_binary_prefix_bounds_lt xs hxs) have hNy : brgc_inverse ys.sum (alpha_binary_prefix ys) < 2 ^ ys.sum := brgc_inverse_lt_two_pow (alpha_binary_prefix_bounds_lt ys hys)
When the heads are equal (x = y), the equivalence reduces to the tail comparison and follows from the induction hypothesis.
If x = y, then xs.sum = ys.sum and the tails have length sum at most n. By alpha_lexical_lt_cons_same, the lexical comparison on x :: xs and x :: ys is equivalent to the reversed comparison on tails, alpha_lexical_lt ys xs. By the inductive hypothesis applied to ys and xs, this is equivalent to inverse rank of ys being strictly less than that of xs. In the Gray rank recurrence, the matching leading terms 2^(xs.sum) * (2^x - 1) cancel, and the inequality 2^S - 1 - Nx < 2^S - 1 - Ny simplifies to Ny < Nx, matching the induction hypothesis.
uses
alpha_lexical_lt_cons_sameby_cases hxy : x = y · subst hxy have hS : ys.sum = xs.sum := by omega have hl' : ys.length + xs.length ≤ n := by simp at hl; omega rw [alpha_lexical_lt_cons_same, ih ys xs hl' hys hxs hS] rw [hS] at hNy ⊢ constructor <;> intro h <;> omega
When the heads differ (x ≠ y), the signed-alternating lexical order reduces to x < y.
Since the heads differ, the discrepancy in the definition of alpha_lexical_lt must occur at index 0. Because index 0 is even, the signed cell value is positive (+x and +y), so alpha_lexical_lt (x :: xs) (y :: ys) holds if and only if x < y.
· -- the first cells differ have hlt_iff : alpha_lexical_lt (x :: xs) (y :: ys) ↔ x < y := by constructor · rintro ⟨i, hi, heq, hlt⟩ cases i with | zero => simpa [alpha_signed_cell] using hlt | succ j => have := heq 0 (by omega) simp [alpha_signed_cell] at this exact absurd this hxy · intro h refine ⟨0, by simp, fun k hk => absurd hk (by omega), ?_⟩ simp [alpha_signed_cell]; exact_mod_cast h rw [hlt_iff]
If x < y and x + xs.sum = y + ys.sum, the inverse Gray rank of x :: xs is strictly less than that of y :: ys.
Let S = xs.sum and T = ys.sum. The assumptions x < y and x + S = y + T force T + 1 ≤ S, so xs ≠ []. Applying alpha_lexical_lt_iff_inverse_prefix_low to xs gives Nx ≥ 2^(S - 1). Rewriting powers with pow_add, add_comm, and pow_succ', we have 2^S * 2^x = 2^(x + S) = 2^T * 2^y, 2^S = 2 * 2^(S - 1), and 2^T ≤ 2^(S - 1) by Nat.pow_le_pow_right. Expanding with Nat.mul_sub, Nat.one_le_two_pow, and mul_one, the lower bound Nx ≥ 2^(S - 1) and the upper bound Ny < 2^T ≤ 2^(S - 1) allow linear arithmetic to deduce that the LHS is strictly less than the RHS.
uses
alpha_lexical_lt_iff_inverse_prefix_low,pow_add,add_comm,pow_succ',Nat.pow_le_pow_right,Nat.one_le_two_pow,Nat.mul_sub,mul_onehave key : ∀ (x y : ℕ) (xs ys : List ℕ), 0 < x → (∀ v ∈ xs, 0 < v) → x + xs.sum = y + ys.sum → x < y → brgc_inverse xs.sum (alpha_binary_prefix xs) < 2 ^ xs.sum → brgc_inverse ys.sum (alpha_binary_prefix ys) < 2 ^ ys.sum → 2 ^ xs.sum * (2 ^ x - 1) + (2 ^ xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)) < 2 ^ ys.sum * (2 ^ y - 1) + (2 ^ ys.sum - 1 - brgc_inverse ys.sum (alpha_binary_prefix ys)) := by intro x y xs ys hx hxs hs hlt hNx hNy have hne : xs ≠ [] := by rintro rfl; simp at hs; omega have hlow := alpha_lexical_lt_iff_inverse_prefix_low xs hne hxs set S := xs.sum set T := ys.sum have hTS : T + 1 ≤ S := by omega have hM1 : 2 ^ S * 2 ^ x = 2 ^ (x + S) := by rw [← pow_add, add_comm] have hM2 : 2 ^ T * 2 ^ y = 2 ^ (x + S) := by rw [← pow_add, hs, add_comm] have hS1 : 2 ^ S = 2 * 2 ^ (S - 1) := by rw [← pow_succ']; congr 1; omega have hT1 : 2 ^ T ≤ 2 ^ (S - 1) := Nat.pow_le_pow_right (by norm_num) (by omega) have hx1 : 1 ≤ 2 ^ x := Nat.one_le_two_pow have hy1 : 1 ≤ 2 ^ y := Nat.one_le_two_pow rw [Nat.mul_sub, Nat.mul_sub, mul_one, mul_one, hM1, hM2] have : 2 ^ S ≤ 2 ^ (x + S) := Nat.pow_le_pow_right (by norm_num) (by omega) have : 2 ^ T ≤ 2 ^ (x + S) := by omega omega
When x ≠ y, the equivalence between lexical order and Gray rank order holds.
By lt_or_gt_of_ne, either x < y or y < x. If x < y, both the lexical condition and the Gray rank inequality are true by the key lemma (true_iff). If y < x, the condition x < y is false (false_iff), while applying the key lemma with swapped arguments gives the reverse strict inequality, so by not_lt the forward strict inequality is false. Thus both sides are false.
uses
lt_or_gt_of_ne,true_iff,false_iff,not_ltrcases lt_or_gt_of_ne hxy with h | h · simp only [h, true_iff] exact key x y xs ys hx hxs hs' h hNx hNy · have := key y x ys xs hy hys hs'.symm h hNy hNx simp only [show ¬ x < y by omega, false_iff, not_lt] exact this.le
On equal-sum positive encodings, signed-alternating lexical order is equivalent to inverse Gray-rank order.
We instantiate the auxiliary theorem alpha_lexical_lt_iff_inverse_prefix_aux with the total length n = a.length + b.length, which satisfies the length hypothesis reflexively by le_rfl.
uses
alpha_lexical_lt_iff_inverse_prefix_aux,le_rfltheorem alpha_lexical_lt_iff_inverse_prefix (a b : List ℕ) (ha : ∀ v ∈ a, 0 < v) (hb : ∀ v ∈ b, 0 < v) (hs : a.sum = b.sum) : alpha_lexical_lt a b ↔ brgc_inverse a.sum (alpha_binary_prefix a) < brgc_inverse b.sum (alpha_binary_prefix b) := alpha_lexical_lt_iff_inverse_prefix_aux _ a b le_rfl ha hb hs
alpha_lexical_lt_iff_inverse_prefix_low- For any non-empty list of positive natural numbers, the inverse Gray rank of its binary prefix is at least 2^(sum - 1).
alpha_lexical_lt_iff_inverse_prefix_aux- For positive lists with length sum at most n and equal element sums, signed-alternating lexical order is equivalent to strict inequality of inverse Gray ranks.
List.sum_cons- The sum of a list starting with head a and tail l equals a + l.sum.
List.sum_nil- The sum of the empty list is 0.
List.eq_nil_of_length_eq_zero- A list of length 0 is the empty list.
pow_succ'- In any monoid, a^(n + 1) = a * a^n.
Nat.one_le_two_pow- For any natural number n, 1 ≤ 2^n.
pow_add- In any monoid, powers add under multiplication: a^(m + n) = a^m * a^n.
Nat.mul_le_mul_left- Multiplication on natural numbers preserves inequality: if n ≤ m, then k * n ≤ k * m.
Nat.le_add_right- For any natural numbers n and k, n ≤ n + k.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself.
brgc_inverse_alpha_binary_prefix_cons- Recurrence formula expressing the inverse Gray rank of x :: xs in terms of x, xs.sum, and the inverse Gray rank of xs.
brgc_inverse_lt_two_pow- If x < 2^n, then the n-bit inverse Gray rank of x is strictly less than 2^n.
alpha_binary_prefix_bounds_lt- The binary prefix encoding of a list of positive integers is strictly less than 2^sum.
alpha_lexical_lt_cons_same- Prepending the same element to two lists reverses their signed-alternating lexical order on the tails.
add_comm- Addition is commutative: a + b = b + a.
Nat.pow_le_pow_right- For base n > 0, if i ≤ j then n^i ≤ n^j.
Nat.mul_sub- Multiplication distributes over subtraction on natural numbers: n * (m - k) = n * m - n * k.
mul_one- Multiplying by 1 leaves an element unchanged: a * 1 = a.
lt_or_gt_of_ne- In a linear order, two unequal elements satisfy a < b or b < a.
true_iff- An equivalence between True and p simplifies to p.
false_iff- An equivalence between False and p simplifies to ¬p.
not_lt- In a linear order, ¬(a < b) is equivalent to b ≤ a.
le_rfl- The preorder relation is reflexive: a ≤ a.
- The proof relies on linear arithmetic (`omega`) to handle algebraic bounds on powers of two after rewriting expressions into forms where dominant powers cancel.
- Line 110 is a term-mode definition completing the induction wrapper rather than an interactive tactic.
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_lt_iff_inverse_prefix_low (xs : List ℕ) (hne : xs ≠ []) (hxs : ∀ v ∈ xs, 0 < v) : 2 ^ (xs.sum - 1) ≤ brgc_inverse xs.sum (alpha_binary_prefix xs) := by match xs, hne with | z :: zs, _ => have hz : 0 < z := hxs z (by simp) have hzs : ∀ v ∈ zs, 0 < v := fun v hv => hxs v (by simp [hv]) rw [brgc_inverse_alpha_binary_prefix_cons z zs hz hzs, List.sum_cons] have h1 : 2 ^ (z - 1) ≤ 2 ^ z - 1 := by have : 2 ^ z = 2 * 2 ^ (z - 1) := by rw [← pow_succ']; congr 1; omega have := Nat.one_le_two_pow (n := z - 1) omega calc 2 ^ (z + zs.sum - 1) = 2 ^ zs.sum * 2 ^ (z - 1) := by rw [← pow_add]; congr 1; omega _ ≤ 2 ^ zs.sum * (2 ^ z - 1) := Nat.mul_le_mul_left _ h1 _ ≤ _ := Nat.le_add_right _ _theorem alpha_lexical_lt_iff_inverse_prefix_aux (n : ℕ) : ∀ (a b : List ℕ), a.length + b.length ≤ n → (∀ v ∈ a, 0 < v) → (∀ v ∈ b, 0 < v) → a.sum = b.sum → (alpha_lexical_lt a b ↔ brgc_inverse a.sum (alpha_binary_prefix a) < brgc_inverse b.sum (alpha_binary_prefix b)) := by induction n with | zero => intro a b hl ha hb hs have ha0 : a = [] := List.eq_nil_of_length_eq_zero (by omega) have hb0 : b = [] := List.eq_nil_of_length_eq_zero (by omega) subst ha0 hb0 constructor · rintro ⟨i, hi, -⟩; simp at hi · intro h; exact absurd h (lt_irrefl _) | succ n ih => intro a b hl ha hs' hs have hb := hs' cases a with | nil => cases b with | nil => constructor · rintro ⟨i, hi, -⟩; simp at hi · intro h; exact absurd h (lt_irrefl _) | cons y ys => have := hb y (by simp) simp only [List.sum_nil, List.sum_cons] at hs; omega | cons x xs => cases b with | nil => have := ha x (by simp) simp only [List.sum_nil, List.sum_cons] at hs; omega | cons y ys => have hx : 0 < x := ha x (by simp) have hy : 0 < y := hb y (by simp) have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (by simp [hv]) have hys : ∀ v ∈ ys, 0 < v := fun v hv => hb v (by simp [hv]) have hs' : x + xs.sum = y + ys.sum := by simpa using hs rw [brgc_inverse_alpha_binary_prefix_cons x xs hx hxs, brgc_inverse_alpha_binary_prefix_cons y ys hy hys] have hNx : brgc_inverse xs.sum (alpha_binary_prefix xs) < 2 ^ xs.sum := brgc_inverse_lt_two_pow (alpha_binary_prefix_bounds_lt xs hxs) have hNy : brgc_inverse ys.sum (alpha_binary_prefix ys) < 2 ^ ys.sum := brgc_inverse_lt_two_pow (alpha_binary_prefix_bounds_lt ys hys) by_cases hxy : x = y · subst hxy have hS : ys.sum = xs.sum := by omega have hl' : ys.length + xs.length ≤ n := by simp at hl; omega rw [alpha_lexical_lt_cons_same, ih ys xs hl' hys hxs hS] rw [hS] at hNy ⊢ constructor <;> intro h <;> omega · -- the first cells differ have hlt_iff : alpha_lexical_lt (x :: xs) (y :: ys) ↔ x < y := by constructor · rintro ⟨i, hi, heq, hlt⟩ cases i with | zero => simpa [alpha_signed_cell] using hlt | succ j => have := heq 0 (by omega) simp [alpha_signed_cell] at this exact absurd this hxy · intro h refine ⟨0, by simp, fun k hk => absurd hk (by omega), ?_⟩ simp [alpha_signed_cell]; exact_mod_cast h rw [hlt_iff] have key : ∀ (x y : ℕ) (xs ys : List ℕ), 0 < x → (∀ v ∈ xs, 0 < v) → x + xs.sum = y + ys.sum → x < y → brgc_inverse xs.sum (alpha_binary_prefix xs) < 2 ^ xs.sum → brgc_inverse ys.sum (alpha_binary_prefix ys) < 2 ^ ys.sum → 2 ^ xs.sum * (2 ^ x - 1) + (2 ^ xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)) < 2 ^ ys.sum * (2 ^ y - 1) + (2 ^ ys.sum - 1 - brgc_inverse ys.sum (alpha_binary_prefix ys)) := by intro x y xs ys hx hxs hs hlt hNx hNy have hne : xs ≠ [] := by rintro rfl; simp at hs; omega have hlow := alpha_lexical_lt_iff_inverse_prefix_low xs hne hxs set S := xs.sum set T := ys.sum have hTS : T + 1 ≤ S := by omega have hM1 : 2 ^ S * 2 ^ x = 2 ^ (x + S) := by rw [← pow_add, add_comm] have hM2 : 2 ^ T * 2 ^ y = 2 ^ (x + S) := by rw [← pow_add, hs, add_comm] have hS1 : 2 ^ S = 2 * 2 ^ (S - 1) := by rw [← pow_succ']; congr 1; omega have hT1 : 2 ^ T ≤ 2 ^ (S - 1) := Nat.pow_le_pow_right (by norm_num) (by omega) have hx1 : 1 ≤ 2 ^ x := Nat.one_le_two_pow have hy1 : 1 ≤ 2 ^ y := Nat.one_le_two_pow rw [Nat.mul_sub, Nat.mul_sub, mul_one, mul_one, hM1, hM2] have : 2 ^ S ≤ 2 ^ (x + S) := Nat.pow_le_pow_right (by norm_num) (by omega) have : 2 ^ T ≤ 2 ^ (x + S) := by omega omega rcases lt_or_gt_of_ne hxy with h | h · simp only [h, true_iff] exact key x y xs ys hx hxs hs' h hNx hNy · have := key y x ys xs hy hys hs'.symm h hNy hNx simp only [show ¬ x < y by omega, false_iff, not_lt] exact this.letheorem alpha_lexical_lt_iff_inverse_prefix (a b : List ℕ) (ha : ∀ v ∈ a, 0 < v) (hb : ∀ v ∈ b, 0 < v) (hs : a.sum = b.sum) : alpha_lexical_lt a b ↔ brgc_inverse a.sum (alpha_binary_prefix a) < brgc_inverse b.sum (alpha_binary_prefix b) := alpha_lexical_lt_iff_inverse_prefix_aux _ a b le_rfl ha hb hs