AFTD Auto-Formalizing Theoretical Domains

alpha_lexical_lt_iff_inverse_prefix

theoremverified

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

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.

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

    lines 4–17

    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_right

      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 _ _
  2. 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.

    lines 20–28

    uses List.eq_nil_of_length_eq_zero, lt_irrefl

      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 _)
  3. 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.

    lines 29–47

    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 =>
  4. 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.

    lines 48–58

    uses brgc_inverse_alpha_binary_prefix_cons, brgc_inverse_lt_two_pow, alpha_binary_prefix_bounds_lt

          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)
  5. 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.

    lines 59–65

    uses alpha_lexical_lt_cons_same

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

    lines 66–79

          · -- 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]
  7. 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.

    lines 80–101

    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_one

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

    lines 102–108

    uses lt_or_gt_of_ne, true_iff, false_iff, not_lt

            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.le
    
  9. 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.

    lines 109–110

    uses alpha_lexical_lt_iff_inverse_prefix_aux, le_rfl

    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) :=
      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.

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