alpha_elementary_cell_step_binary_xor
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
- alpha_elementary_cell_stepOne source elementary split or conjugation, with a zero-based cell index.
- alpha_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
- alpha_binary_prefix_appendBinary encoding respects concatenation and the sum of the cells is the bit length.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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).
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.
theorem alpha_elementary_cell_step_binary_xor_singleton (c : ℕ) : alpha_binary_prefix [c] = 2 ^ (c - 1) := by simp [alpha_binary_prefix]
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.
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
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.
uses
List.mem_cons_self,List.mem_cons_of_mem,alpha_binary_prefix.eq_def,List.sum_constheorem 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
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).
uses
Nat.mul_le_mul_right,Nat.exists_eq_succ_of_ne_zero,Nat.succ_sub_one,pow_succ,Nat.one_le_two_powcalc 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
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.
uses
Nat.eq_of_testBit_eq,Nat.testBit_xor,Nat.testBit_two_pow_mul_add,Nat.xor_lt_two_pow,if_pos,if_negtheorem 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]
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.
uses
alpha_binary_prefix_append,Nat.even_pow,even_two,Even.mul_right,Even.addtheorem 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
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.
uses
Nat.xor_one_of_even,Nat.xor_assochave 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
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).
uses
alpha_binary_prefix_append,alpha_elementary_cell_step_binary_xor_xor_splitrw [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
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.
uses
List.take_append_drop,List.drop_eq_getElem_cons,List.getD_eq_getElemtheorem 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
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.
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_appendtheorem 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]
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).
uses
alpha_elementary_cell_step_binary_xor_take_droptheorem 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]
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).
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_droprefine 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))
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.
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]
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.
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_droprefine 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.
- The proof relies on zero-based indexing and the default fallback function `getD` to safely extract elements, with index validity verified by linear arithmetic (`omega`).
- Standard algebraic simplifications and bit-level linear arithmetic over ℕ are closed by automation (`omega`, `ring`, `nlinarith`).
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_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))