AFTD Auto-Formalizing Theoretical Domains

alpha_elementary_cell_step_binary_xor

theoremverified

An elementary operation changes exactly the boundary bit immediately before the untouched suffix.

Statement

theorem alpha_elementary_cell_step_binary_xor (a b : List ℕ) (i : ℕ) (ha : ∀ v ∈ a, 0 < v) (h : alpha_elementary_cell_step a b i) : alpha_binary_prefix a ^^^ alpha_binary_prefix b = 2 ^ (a.drop (i + 1)).sum
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
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

An elementary cell step between integer lists a and b at index i modifies a single cell by either splitting a[i] > 1 into [a[i] - 1, 1] or merging [a[i - 1], 1] into a[i - 1] + 1, leaving the prefix before and the suffix after untouched. In both cases, the middle components have equal sum, and their prefix values differ by exactly 1 between an even integer X and X + 1, whose bitwise XOR is 1. Because the untouched suffix evaluates to strictly less than 2^(suf.sum), bitwise XOR separates cleanly across the high and low bit fields, leaving exactly 2^((a.drop (i + 1)).sum).

  1. The prefix encoding of a singleton list [c] is 2^(c - 1).

    Unfolding the definition `alpha_binary_prefix [c]` gives 2^(c - 1 + [].sum) + alpha_binary_prefix [] = 2^(c - 1 + 0) + 0 = 2^(c - 1), which `simp` simplifies directly.

    lines 1–3

    theorem alpha_elementary_cell_step_binary_xor_singleton (c : ℕ) :
        alpha_binary_prefix [c] = 2 ^ (c - 1) := by
      simp [alpha_binary_prefix]
  2. For c ≥ 1, the prefix encoding of the two-element list [c, 1] is 2^c + 1.

    Unfolding `alpha_binary_prefix [c, 1]` yields 2^(c - 1 + 1) + 2^(1 - 1 + 0) + 0 = 2^((c - 1) + 1) + 1. Since c ≥ 1, (c - 1) + 1 = c, which `omega` resolves.

    lines 5–8

    theorem alpha_elementary_cell_step_binary_xor_two (c : ℕ) (hc : 1 ≤ c) :
        alpha_binary_prefix [c, 1] = 2 ^ c + 1 := by
      simp [alpha_binary_prefix]
      omega
  3. Setting up induction to show alpha_binary_prefix a < 2^(a.sum) for any list a of positive integers.

    We proceed by induction on a. For the base case a = [], alpha_binary_prefix [] = 0 < 1 = 2^0 holds immediately. For the inductive step a = x :: xs, all elements in xs are positive, giving the induction hypothesis alpha_binary_prefix xs < 2^(xs.sum). We unfold the definition of alpha_binary_prefix (x :: xs) to 2^(x - 1 + xs.sum) + alpha_binary_prefix xs.

    lines 10–20

    uses List.mem_cons_self, List.mem_cons_of_mem, alpha_binary_prefix.eq_def, List.sum_cons

    theorem alpha_elementary_cell_step_binary_xor_lt_pow_sum (a : List ℕ)
        (ha : ∀ v ∈ a, 0 < v) : alpha_binary_prefix a < 2 ^ a.sum := by
      induction a with
      | nil => simp [alpha_binary_prefix]
      | cons x xs ih =>
        have hx : 0 < x := ha x (List.mem_cons_self ..)
        have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (List.mem_cons_of_mem _ hv)
        have hih := ih hxs
        rw [alpha_binary_prefix.eq_def]
        simp only [List.sum_cons]
        have hx1 : 1 ≤ x := hx
  4. Completing the induction step to bound alpha_binary_prefix (x :: xs) strictly below 2^((x :: xs).sum).

    By the induction hypothesis, 2^(x - 1 + xs.sum) + alpha_binary_prefix xs < 2^(x - 1 + xs.sum) + 2^(xs.sum) = (2^(x - 1) + 1) * 2^(xs.sum). Since x ≥ 1, writing x = y + 1 gives 2^(x - 1) + 1 = 2^y + 1 ≤ 2^y * 2 = 2^x using 1 ≤ 2^y. Multiplying both sides by 2^(xs.sum) yields (2^(x - 1) + 1) * 2^(xs.sum) ≤ 2^x * 2^(xs.sum) = 2^(x + xs.sum).

    lines 21–33

    uses Nat.mul_le_mul_right, Nat.exists_eq_succ_of_ne_zero, Nat.succ_sub_one, pow_succ, Nat.one_le_two_pow

        calc 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs
            < 2 ^ (x - 1 + xs.sum) + 2 ^ xs.sum := by omega
          _ = (2 ^ (x - 1) + 1) * 2 ^ xs.sum := by ring
          _ ≤ 2 ^ x * 2 ^ xs.sum := by
            apply Nat.mul_le_mul_right
            have h2 : 2 ^ (x - 1) + 1 ≤ 2 ^ x := by
              rcases Nat.exists_eq_succ_of_ne_zero (by omega : x ≠ 0) with ⟨y, rfl⟩
              simp only [Nat.succ_sub_one]
              rw [pow_succ]
              have := Nat.one_le_two_pow (n := y)
              nlinarith
            exact h2
          _ = 2 ^ (x + xs.sum) := by ring
  5. Bitwise XOR distributes across high and low bit fields of width s: (2^s * P + x) ^^^ (2^s * Q + y) = 2^s * (P ^^^ Q) + (x ^^^ y) whenever x, y < 2^s.

    Two natural numbers are equal if their bits match at every position (Nat.eq_of_testBit_eq). The j-th bit of 2^s * A + b with b < 2^s is b.testBit j for j < s, and A.testBit (j - s) for j ≥ s. Since bitwise XOR operates bit-by-bit, testing each bit for j < s and j ≥ s matches the two sides identically.

    lines 35–46

    uses Nat.eq_of_testBit_eq, Nat.testBit_xor, Nat.testBit_two_pow_mul_add, Nat.xor_lt_two_pow, if_pos, if_neg

    theorem alpha_elementary_cell_step_binary_xor_xor_split (s P Q x y : ℕ)
        (hx : x < 2 ^ s) (hy : y < 2 ^ s) :
        (2 ^ s * P + x) ^^^ (2 ^ s * Q + y) = 2 ^ s * (P ^^^ Q) + (x ^^^ y) := by
      apply Nat.eq_of_testBit_eq
      intro j
      rw [Nat.testBit_xor]
      rw [Nat.testBit_two_pow_mul_add P hx j, Nat.testBit_two_pow_mul_add Q hy j]
      have hxy : x ^^^ y < 2 ^ s := Nat.xor_lt_two_pow hx hy
      rw [Nat.testBit_two_pow_mul_add (P ^^^ Q) hxy j]
      by_cases hj : j < s
      · rw [if_pos hj, if_pos hj, if_pos hj, Nat.testBit_xor]
      · rw [if_neg hj, if_neg hj, if_neg hj, Nat.testBit_xor]
  6. In a list decomposition p ++ u, the prefix value of p ++ v is alpha_binary_prefix (p ++ u) + 1, and alpha_binary_prefix (p ++ u) is an even number.

    Using alpha_binary_prefix (p ++ u) = 2^(u.sum) * alpha_binary_prefix p + alpha_binary_prefix u and u.sum = v.sum, replacing u by v with alpha_binary_prefix v = alpha_binary_prefix u + 1 increases the combined prefix value by 1. Because u.sum > 0, 2^(u.sum) is even, so 2^(u.sum) * alpha_binary_prefix p is even. Adding the even number alpha_binary_prefix u makes the sum alpha_binary_prefix (p ++ u) even.

    lines 48–67

    uses alpha_binary_prefix_append, Nat.even_pow, even_two, Even.mul_right, Even.add

    theorem alpha_elementary_cell_step_binary_xor_shift (p u v suf : List ℕ)
        (hsum : u.sum = v.sum)
        (hmid : alpha_binary_prefix v = alpha_binary_prefix u + 1)
        (heven : Even (alpha_binary_prefix u))
        (hpos : 0 < u.sum)
        (hsuf : alpha_binary_prefix suf < 2 ^ suf.sum) :
        alpha_binary_prefix (p ++ u ++ suf) ^^^ alpha_binary_prefix (p ++ v ++ suf) = 2 ^ suf.sum := by
      have hpu : alpha_binary_prefix (p ++ u) = 2 ^ u.sum * alpha_binary_prefix p + alpha_binary_prefix u := by
        rw [alpha_binary_prefix_append]
      have hpv : alpha_binary_prefix (p ++ v) = 2 ^ u.sum * alpha_binary_prefix p + alpha_binary_prefix v := by
        rw [alpha_binary_prefix_append, hsum]
      have hX : alpha_binary_prefix (p ++ v) = alpha_binary_prefix (p ++ u) + 1 := by
        rw [hpu, hpv, hmid]; omega
      have hevenX : Even (alpha_binary_prefix (p ++ u)) := by
        rw [hpu]
        have h2 : Even (2 ^ u.sum) := by
          rw [Nat.even_pow]
          exact ⟨even_two, by omega⟩
        have h2m := Even.mul_right h2 (alpha_binary_prefix p)
        exact Even.add h2m heven
  7. The bitwise XOR of an even number and its successor is 1: alpha_binary_prefix (p ++ u) ^^^ (alpha_binary_prefix (p ++ u) + 1) = 1.

    Because alpha_binary_prefix (p ++ u) is even, its least significant bit is 0, so alpha_binary_prefix (p ++ u) ^^^ 1 = alpha_binary_prefix (p ++ u) + 1 by Nat.xor_one_of_even. Taking XOR with alpha_binary_prefix (p ++ u) on both sides and using associativity and self-cancellation gives alpha_binary_prefix (p ++ u) ^^^ (alpha_binary_prefix (p ++ u) + 1) = 1.

    lines 68–72

    uses Nat.xor_one_of_even, Nat.xor_assoc

      have hxor : alpha_binary_prefix (p ++ u) ^^^ (alpha_binary_prefix (p ++ u) + 1) = 1 := by
        have h1 : alpha_binary_prefix (p ++ u) ^^^ 1 = alpha_binary_prefix (p ++ u) + 1 :=
          Nat.xor_one_of_even hevenX
        rw [← h1, ← Nat.xor_assoc]
        simp
  8. Appending suffix suf yields alpha_binary_prefix (p ++ u ++ suf) ^^^ alpha_binary_prefix (p ++ v ++ suf) = 2^(suf.sum).

    The append formula expresses the concatenated values as 2^(suf.sum) * X + alpha_binary_prefix suf and 2^(suf.sum) * (X + 1) + alpha_binary_prefix suf with X = alpha_binary_prefix (p ++ u). Since alpha_binary_prefix suf < 2^(suf.sum), the XOR split lemma separates the high parts and low parts: 2^(suf.sum) * (X ^^^ (X + 1)) + (alpha_binary_prefix suf ^^^ alpha_binary_prefix suf) = 2^(suf.sum) * 1 + 0 = 2^(suf.sum).

    lines 73–78

    uses alpha_binary_prefix_append, alpha_elementary_cell_step_binary_xor_xor_split

      rw [alpha_binary_prefix_append (p ++ u) suf, alpha_binary_prefix_append (p ++ v) suf, hX]
      rw [alpha_elementary_cell_step_binary_xor_xor_split suf.sum (alpha_binary_prefix (p ++ u))
            (alpha_binary_prefix (p ++ u) + 1) (alpha_binary_prefix suf) (alpha_binary_prefix suf)
            hsuf hsuf]
      rw [hxor]
      simp
  9. Any list a decomposes at index i < a.length as a.take i ++ [a[i]] ++ a.drop (i + 1).

    Starting from a = a.take i ++ a.drop i, expanding a.drop i into its head a[i] followed by a.drop (i + 1) yields the three-part decomposition.

    lines 80–85

    uses List.take_append_drop, List.drop_eq_getElem_cons, List.getD_eq_getElem

    theorem alpha_elementary_cell_step_binary_xor_take_drop (a : List ℕ) (i : ℕ)
        (hi : i < a.length) :
        a = a.take i ++ [a.getD i 0] ++ a.drop (i + 1) := by
      conv_lhs => rw [← List.take_append_drop i a]
      rw [List.drop_eq_getElem_cons hi, List.getD_eq_getElem a 0 hi]
      simp
  10. If i < a.length, i > 0, and a[i] = 1, then a decomposes as a.take (i - 1) ++ [a[i - 1], 1] ++ a.drop (i + 1).

    Applying the single-element decomposition to a.take i splits off its last element a[i - 1], expressing a.take i as a.take (i - 1) ++ [a[i - 1]]. Substituting this and a[i] = 1 into the decomposition of a at index i gives the desired form.

    lines 87–95

    uses List.getD_eq_getElem, List.take_append_getElem, Nat.sub_add_cancel, alpha_elementary_cell_step_binary_xor_take_drop, List.append_assoc, List.cons_append, List.nil_append

    theorem alpha_elementary_cell_step_binary_xor_take_drop_two (a : List ℕ) (i : ℕ)
        (hi : i < a.length) (hpos : 0 < i) (hget : a.getD i 0 = 1) :
        a = a.take (i - 1) ++ [a.getD (i - 1) 0, 1] ++ a.drop (i + 1) := by
      have hlt : i - 1 < a.length := by omega
      have htake : a.take i = a.take (i - 1) ++ [a.getD (i - 1) 0] := by
        rw [List.getD_eq_getElem a 0 hlt, List.take_append_getElem hlt,
          Nat.sub_add_cancel (by omega : 1 ≤ i)]
      conv_lhs => rw [alpha_elementary_cell_step_binary_xor_take_drop a i hi, hget, htake]
      simp only [List.append_assoc, List.cons_append, List.nil_append]
  11. In the cell-splitting case (a[i] > 1), decomposing a and b around cell i.

    We case split on alpha_elementary_cell_step. In the first case, a[i] > 1 and b replaces a[i] with [a[i] - 1, 1]. Using alpha_elementary_cell_step_binary_xor_take_drop, a decomposes into a.take i ++ [a[i]] ++ a.drop (i + 1), matching b = a.take i ++ [a[i] - 1, 1] ++ a.drop (i + 1).

    lines 97–104

    uses alpha_elementary_cell_step_binary_xor_take_drop

    theorem alpha_elementary_cell_step_binary_xor (a b : List ℕ) (i : ℕ) (ha : ∀ v ∈ a, 0 < v) (h : alpha_elementary_cell_step a b i) : alpha_binary_prefix a ^^^ alpha_binary_prefix b = 2 ^ (a.drop (i + 1)).sum := by
      rcases h with ⟨hi, hsplit | hconj⟩
      · rcases hsplit with ⟨hc, hb⟩
        have hdecomp := alpha_elementary_cell_step_binary_xor_take_drop a i hi
        have hga : alpha_binary_prefix a
            = alpha_binary_prefix (a.take i ++ [a.getD i 0] ++ a.drop (i + 1)) := by
          conv_lhs => rw [hdecomp]
        rw [hga, hb]
  12. Verifying the preconditions of the shift lemma and concluding the cell-splitting case.

    We apply alpha_elementary_cell_step_binary_xor_shift with prefix p = a.take i, middle u = [a[i]] and v = [a[i] - 1, 1], and suffix suf = a.drop (i + 1). The preconditions are verified: u.sum = a[i] = (a[i] - 1) + 1 = v.sum; alpha_binary_prefix v = 2^(a[i] - 1) + 1 = alpha_binary_prefix u + 1; alpha_binary_prefix u = 2^(a[i] - 1) is even because a[i] > 1; u.sum = a[i] > 0; and alpha_binary_prefix suf < 2^(suf.sum) by alpha_elementary_cell_step_binary_xor_lt_pow_sum. The shift lemma concludes that the XOR equals 2^((a.drop (i + 1)).sum).

    lines 105–116

    uses alpha_elementary_cell_step_binary_xor_shift, List.sum_cons, List.sum_nil, add_zero, alpha_elementary_cell_step_binary_xor_singleton, alpha_elementary_cell_step_binary_xor_two, Nat.even_pow, even_two, alpha_elementary_cell_step_binary_xor_lt_pow_sum, List.mem_of_mem_drop

        refine alpha_elementary_cell_step_binary_xor_shift (a.take i) [a.getD i 0]
          [a.getD i 0 - 1, 1] (a.drop (i + 1)) ?_ ?_ ?_ ?_ ?_
        · simp only [List.sum_cons, List.sum_nil, add_zero]
          omega
        · rw [alpha_elementary_cell_step_binary_xor_singleton,
            alpha_elementary_cell_step_binary_xor_two (a.getD i 0 - 1) (by omega)]
        · rw [alpha_elementary_cell_step_binary_xor_singleton, Nat.even_pow]
          exact ⟨even_two, by omega⟩
        · simp only [List.sum_cons, List.sum_nil, add_zero]
          omega
        · exact alpha_elementary_cell_step_binary_xor_lt_pow_sum _
            (fun v hv => ha v (List.mem_of_mem_drop hv))
  13. In the cell-merging case (a[i] = 1, i > 0), decomposing a and b and applying commutativity of XOR.

    In the second case, i > 0, a[i] = 1, and b = a.take (i - 1) ++ [a[i - 1] + 1] ++ a.drop (i + 1). Using alpha_elementary_cell_step_binary_xor_take_drop_two, a decomposes into a.take (i - 1) ++ [a[i - 1], 1] ++ a.drop (i + 1). By commutativity of XOR (Nat.xor_comm), we swap a and b to align with the shift lemma where the singleton list is the first argument.

    lines 117–126

    uses List.getD_eq_getElem, List.getElem_mem, alpha_elementary_cell_step_binary_xor_take_drop_two, Nat.xor_comm

      · rcases hconj with ⟨hpos, hget, hb⟩
        have hlt : i - 1 < a.length := by omega
        have hdpos : 0 < a.getD (i - 1) 0 := by
          rw [List.getD_eq_getElem a 0 hlt]
          exact ha _ (List.getElem_mem hlt)
        have hdecomp := alpha_elementary_cell_step_binary_xor_take_drop_two a i hi hpos hget
        have hga : alpha_binary_prefix a
            = alpha_binary_prefix (a.take (i - 1) ++ [a.getD (i - 1) 0, 1] ++ a.drop (i + 1)) := by
          conv_lhs => rw [hdecomp]
        rw [hga, hb, Nat.xor_comm]
  14. Verifying the preconditions of the shift lemma and concluding the cell-merging case.

    We apply alpha_elementary_cell_step_binary_xor_shift with prefix p = a.take (i - 1), middle u = [a[i - 1] + 1] and v = [a[i - 1], 1], and suffix suf = a.drop (i + 1). The preconditions hold: u.sum = a[i - 1] + 1 = v.sum; alpha_binary_prefix v = 2^(a[i - 1]) + 1 = alpha_binary_prefix u + 1; alpha_binary_prefix u = 2^(a[i - 1]) is even because a[i - 1] > 0; u.sum > 0; and alpha_binary_prefix suf < 2^(suf.sum) by alpha_elementary_cell_step_binary_xor_lt_pow_sum. The shift lemma yields 2^((a.drop (i + 1)).sum), completing the proof.

    lines 127–141

    uses alpha_elementary_cell_step_binary_xor_shift, List.sum_cons, List.sum_nil, add_zero, alpha_elementary_cell_step_binary_xor_two, alpha_elementary_cell_step_binary_xor_singleton, Nat.even_pow, even_two, alpha_elementary_cell_step_binary_xor_lt_pow_sum, List.mem_of_mem_drop

        refine alpha_elementary_cell_step_binary_xor_shift (a.take (i - 1)) [a.getD (i - 1) 0 + 1]
          [a.getD (i - 1) 0, 1] (a.drop (i + 1)) ?_ ?_ ?_ ?_ ?_
        · simp only [List.sum_cons, List.sum_nil, add_zero]
        · rw [alpha_elementary_cell_step_binary_xor_two (a.getD (i - 1) 0) (by omega),
            alpha_elementary_cell_step_binary_xor_singleton]
          have hd : a.getD (i - 1) 0 + 1 - 1 = a.getD (i - 1) 0 := by omega
          rw [hd]
        · rw [alpha_elementary_cell_step_binary_xor_singleton, Nat.even_pow]
          constructor
          · exact even_two
          · omega
        · simp only [List.sum_cons, List.sum_nil, add_zero]
          omega
        · exact alpha_elementary_cell_step_binary_xor_lt_pow_sum _
            (fun v hv => ha v (List.mem_of_mem_drop hv))
add_zero
Adding zero to any element leaves it unchanged: a + 0 = a.
alpha_binary_prefix.eq_def
The recursive definition of alpha_binary_prefix: 0 on the empty list, and 2^(a - 1 + as.sum) + alpha_binary_prefix as on a non-empty list a :: as.
alpha_binary_prefix_append
The prefix encoding of the concatenation a ++ b equals 2^(b.sum) * alpha_binary_prefix a + alpha_binary_prefix b.
alpha_elementary_cell_step_binary_xor_lt_pow_sum
For any list a of strictly positive integers, alpha_binary_prefix a is strictly less than 2^(a.sum).
alpha_elementary_cell_step_binary_xor_shift
Under equal middle sums and a unit step between an even prefix and its successor, the bitwise XOR of the full concatenated lists equals 2^(suf.sum).
alpha_elementary_cell_step_binary_xor_singleton
The prefix encoding of a singleton list [c] equals 2^(c - 1).
alpha_elementary_cell_step_binary_xor_take_drop
Decomposes a list at index i < a.length into its prefix of length i, the element a[i], and the suffix starting at i + 1.
alpha_elementary_cell_step_binary_xor_take_drop_two
Decomposes a list where entry i equals 1 into its prefix of length i - 1, the pair [a[i - 1], 1], and the suffix after i.
alpha_elementary_cell_step_binary_xor_two
The prefix encoding of a two-element list [c, 1] with c ≥ 1 equals 2^c + 1.
alpha_elementary_cell_step_binary_xor_xor_split
Bitwise XOR of numbers partitioned into high and low blocks of bit-width s splits into the XOR of the high blocks and the XOR of the low blocks.
Even.add
The sum of two even numbers is even.
Even.mul_right
The product of an even number with any number is even.
even_two
The number 2 is even.
if_neg
An if-then-else expression reduces to the else-branch when the condition is false.
if_pos
An if-then-else expression reduces to the then-branch when the condition is true.
List.append_assoc
List concatenation is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
List.cons_append
Cons distributes over list append: a :: (as ++ bs) = (a :: as) ++ bs.
List.drop_eq_getElem_cons
Dropping i elements from a list of length > i equals the i-th element followed by dropping i + 1 elements.
List.getD_eq_getElem
The getD fallback access equals the indexed element when the index is within bounds.
List.getElem_mem
Any element indexed within bounds belongs to the list.
List.mem_cons_self
An element belongs to any list of which it is the head: a ∈ a :: l.
List.mem_cons_of_mem
If an element belongs to a list, it belongs to the list prepended with another element: a ∈ l → a ∈ y :: l.
List.mem_of_mem_drop
Any element belonging to a dropped suffix of a list also belongs to the original list.
List.nil_append
Prepending the empty list leaves a list unchanged: [] ++ as = as.
List.sum_cons
The sum of a non-empty list is its head plus the sum of its tail: (a :: l).sum = a + l.sum.
List.sum_nil
The sum of the empty list of natural numbers is 0.
List.take_append_drop
Taking the first i elements of a list and appending the remainder reconstructs the original list.
List.take_append_getElem
Appending the i-th element to the take of length i produces the take of length i + 1.
Nat.eq_of_testBit_eq
Two natural numbers are equal if and only if their bits match at every position.
Nat.even_pow
A power m^n is even if and only if m is even and n ≠ 0.
Nat.mul_le_mul_right
Multiplying both sides of an inequality by a natural number preserves the inequality.
Nat.one_le_two_pow
Any power of 2 is at least 1: 1 ≤ 2^n.
Nat.sub_add_cancel
Subtracting m and adding m recovers n, provided m ≤ n.
Nat.succ_sub_one
Subtracting 1 from n + 1 yields n: (n + 1) - 1 = n.
Nat.testBit_two_pow_mul_add
For b < 2^i, the j-th bit of 2^i * a + b is b.testBit j for j < i, and a.testBit (j - i) for j ≥ i.
Nat.testBit_xor
The i-th bit of a bitwise XOR is the boolean XOR of the i-th bits of the operands.
Nat.xor_assoc
Bitwise XOR is associative: (x ^^^ y) ^^^ z = x ^^^ (y ^^^ z).
Nat.xor_comm
Bitwise XOR is commutative: x ^^^ y = y ^^^ x.
Nat.xor_lt_two_pow
The bitwise XOR of two numbers strictly bounded by 2^n is strictly bounded by 2^n.
Nat.xor_one_of_even
The bitwise XOR of an even number with 1 equals that number plus 1: n ^^^ 1 = n + 1.
Nat.exists_eq_succ_of_ne_zero
Every non-zero natural number is the successor of some natural number.
pow_succ
Successor powers in a monoid satisfy a^(n + 1) = a^n * 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_elementary_cell_step_binary_xor_singleton (c : ℕ) :    alpha_binary_prefix [c] = 2 ^ (c - 1) := by  simp [alpha_binary_prefix]theorem alpha_elementary_cell_step_binary_xor_two (c : ℕ) (hc : 1 ≤ c) :    alpha_binary_prefix [c, 1] = 2 ^ c + 1 := by  simp [alpha_binary_prefix]  omegatheorem alpha_elementary_cell_step_binary_xor_lt_pow_sum (a : List ℕ)    (ha : ∀ v ∈ a, 0 < v) : alpha_binary_prefix a < 2 ^ a.sum := by  induction a with  | nil => simp [alpha_binary_prefix]  | cons x xs ih =>    have hx : 0 < x := ha x (List.mem_cons_self ..)    have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (List.mem_cons_of_mem _ hv)    have hih := ih hxs    rw [alpha_binary_prefix.eq_def]    simp only [List.sum_cons]    have hx1 : 1 ≤ x := hx    calc 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs        < 2 ^ (x - 1 + xs.sum) + 2 ^ xs.sum := by omega      _ = (2 ^ (x - 1) + 1) * 2 ^ xs.sum := by ring      _ ≤ 2 ^ x * 2 ^ xs.sum := by        apply Nat.mul_le_mul_right        have h2 : 2 ^ (x - 1) + 1 ≤ 2 ^ x := by          rcases Nat.exists_eq_succ_of_ne_zero (by omega : x ≠ 0) with ⟨y, rfl⟩          simp only [Nat.succ_sub_one]          rw [pow_succ]          have := Nat.one_le_two_pow (n := y)          nlinarith        exact h2      _ = 2 ^ (x + xs.sum) := by ringtheorem alpha_elementary_cell_step_binary_xor_xor_split (s P Q x y : ℕ)    (hx : x < 2 ^ s) (hy : y < 2 ^ s) :    (2 ^ s * P + x) ^^^ (2 ^ s * Q + y) = 2 ^ s * (P ^^^ Q) + (x ^^^ y) := by  apply Nat.eq_of_testBit_eq  intro j  rw [Nat.testBit_xor]  rw [Nat.testBit_two_pow_mul_add P hx j, Nat.testBit_two_pow_mul_add Q hy j]  have hxy : x ^^^ y < 2 ^ s := Nat.xor_lt_two_pow hx hy  rw [Nat.testBit_two_pow_mul_add (P ^^^ Q) hxy j]  by_cases hj : j < s  · rw [if_pos hj, if_pos hj, if_pos hj, Nat.testBit_xor]  · rw [if_neg hj, if_neg hj, if_neg hj, Nat.testBit_xor]theorem alpha_elementary_cell_step_binary_xor_shift (p u v suf : List ℕ)    (hsum : u.sum = v.sum)    (hmid : alpha_binary_prefix v = alpha_binary_prefix u + 1)    (heven : Even (alpha_binary_prefix u))    (hpos : 0 < u.sum)    (hsuf : alpha_binary_prefix suf < 2 ^ suf.sum) :    alpha_binary_prefix (p ++ u ++ suf) ^^^ alpha_binary_prefix (p ++ v ++ suf) = 2 ^ suf.sum := by  have hpu : alpha_binary_prefix (p ++ u) = 2 ^ u.sum * alpha_binary_prefix p + alpha_binary_prefix u := by    rw [alpha_binary_prefix_append]  have hpv : alpha_binary_prefix (p ++ v) = 2 ^ u.sum * alpha_binary_prefix p + alpha_binary_prefix v := by    rw [alpha_binary_prefix_append, hsum]  have hX : alpha_binary_prefix (p ++ v) = alpha_binary_prefix (p ++ u) + 1 := by    rw [hpu, hpv, hmid]; omega  have hevenX : Even (alpha_binary_prefix (p ++ u)) := by    rw [hpu]    have h2 : Even (2 ^ u.sum) := by      rw [Nat.even_pow]      exact ⟨even_two, by omega⟩    have h2m := Even.mul_right h2 (alpha_binary_prefix p)    exact Even.add h2m heven  have hxor : alpha_binary_prefix (p ++ u) ^^^ (alpha_binary_prefix (p ++ u) + 1) = 1 := by    have h1 : alpha_binary_prefix (p ++ u) ^^^ 1 = alpha_binary_prefix (p ++ u) + 1 :=      Nat.xor_one_of_even hevenX    rw [← h1, ← Nat.xor_assoc]    simp  rw [alpha_binary_prefix_append (p ++ u) suf, alpha_binary_prefix_append (p ++ v) suf, hX]  rw [alpha_elementary_cell_step_binary_xor_xor_split suf.sum (alpha_binary_prefix (p ++ u))        (alpha_binary_prefix (p ++ u) + 1) (alpha_binary_prefix suf) (alpha_binary_prefix suf)        hsuf hsuf]  rw [hxor]  simptheorem alpha_elementary_cell_step_binary_xor_take_drop (a : List ℕ) (i : ℕ)    (hi : i < a.length) :    a = a.take i ++ [a.getD i 0] ++ a.drop (i + 1) := by  conv_lhs => rw [← List.take_append_drop i a]  rw [List.drop_eq_getElem_cons hi, List.getD_eq_getElem a 0 hi]  simptheorem alpha_elementary_cell_step_binary_xor_take_drop_two (a : List ℕ) (i : ℕ)    (hi : i < a.length) (hpos : 0 < i) (hget : a.getD i 0 = 1) :    a = a.take (i - 1) ++ [a.getD (i - 1) 0, 1] ++ a.drop (i + 1) := by  have hlt : i - 1 < a.length := by omega  have htake : a.take i = a.take (i - 1) ++ [a.getD (i - 1) 0] := by    rw [List.getD_eq_getElem a 0 hlt, List.take_append_getElem hlt,      Nat.sub_add_cancel (by omega : 1 ≤ i)]  conv_lhs => rw [alpha_elementary_cell_step_binary_xor_take_drop a i hi, hget, htake]  simp only [List.append_assoc, List.cons_append, List.nil_append]theorem alpha_elementary_cell_step_binary_xor (a b : List ℕ) (i : ℕ) (ha : ∀ v ∈ a, 0 < v) (h : alpha_elementary_cell_step a b i) : alpha_binary_prefix a ^^^ alpha_binary_prefix b = 2 ^ (a.drop (i + 1)).sum := by  rcases h with ⟨hi, hsplit | hconj⟩  · rcases hsplit with ⟨hc, hb⟩    have hdecomp := alpha_elementary_cell_step_binary_xor_take_drop a i hi    have hga : alpha_binary_prefix a        = alpha_binary_prefix (a.take i ++ [a.getD i 0] ++ a.drop (i + 1)) := by      conv_lhs => rw [hdecomp]    rw [hga, hb]    refine alpha_elementary_cell_step_binary_xor_shift (a.take i) [a.getD i 0]      [a.getD i 0 - 1, 1] (a.drop (i + 1)) ?_ ?_ ?_ ?_ ?_    · simp only [List.sum_cons, List.sum_nil, add_zero]      omega    · rw [alpha_elementary_cell_step_binary_xor_singleton,        alpha_elementary_cell_step_binary_xor_two (a.getD i 0 - 1) (by omega)]    · rw [alpha_elementary_cell_step_binary_xor_singleton, Nat.even_pow]      exact ⟨even_two, by omega⟩    · simp only [List.sum_cons, List.sum_nil, add_zero]      omega    · exact alpha_elementary_cell_step_binary_xor_lt_pow_sum _        (fun v hv => ha v (List.mem_of_mem_drop hv))  · rcases hconj with ⟨hpos, hget, hb⟩    have hlt : i - 1 < a.length := by omega    have hdpos : 0 < a.getD (i - 1) 0 := by      rw [List.getD_eq_getElem a 0 hlt]      exact ha _ (List.getElem_mem hlt)    have hdecomp := alpha_elementary_cell_step_binary_xor_take_drop_two a i hi hpos hget    have hga : alpha_binary_prefix a        = alpha_binary_prefix (a.take (i - 1) ++ [a.getD (i - 1) 0, 1] ++ a.drop (i + 1)) := by      conv_lhs => rw [hdecomp]    rw [hga, hb, Nat.xor_comm]    refine alpha_elementary_cell_step_binary_xor_shift (a.take (i - 1)) [a.getD (i - 1) 0 + 1]      [a.getD (i - 1) 0, 1] (a.drop (i + 1)) ?_ ?_ ?_ ?_ ?_    · simp only [List.sum_cons, List.sum_nil, add_zero]    · rw [alpha_elementary_cell_step_binary_xor_two (a.getD (i - 1) 0) (by omega),        alpha_elementary_cell_step_binary_xor_singleton]      have hd : a.getD (i - 1) 0 + 1 - 1 = a.getD (i - 1) 0 := by omega      rw [hd]    · rw [alpha_elementary_cell_step_binary_xor_singleton, Nat.even_pow]      constructor      · exact even_two      · omega    · simp only [List.sum_cons, List.sum_nil, add_zero]      omega    · exact alpha_elementary_cell_step_binary_xor_lt_pow_sum _        (fun v hv => ha v (List.mem_of_mem_drop hv))
See it in the graphDiscuss this resultChallenge it