brgc_inverse_lt_two_pow
The inverse prefix-parity transform of an n-bit word has an n-bit rank.
Statement
theorem brgc_inverse_lt_two_pow {n x : ℕ} (hx : x < 2 ^ n) : brgc_inverse n x < 2 ^ n- Source
- Prefix-parity inverse and supporting arithmetic for OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- brgc_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
- Used by 9
- brgc_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
- alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
- brgc_inverse_flip_preserves_cut_maxIf an n-bit word has strictly greater inverse Gray rank than every nontrivial cyclic cut, toggling its last bit has at least as great an…
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- 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_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
- 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…
- brgc_inverse_rotate_tent_formulaIn inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
The proof, explained
The proof proceeds by induction on $n$, keeping $x$ general. In the base case $n = 0$, the inverse transform is $0$, which is strictly less than $2^0 = 1$. In the inductive step, the transform definition gives $\mathrm{brgc\_inverse}(n + 1, x) = x \oplus \mathrm{brgc\_inverse}(n, x / 2)$; since $x < 2^{n+1}$ and the recursive term is bounded by $2^n \le 2^{n+1}$ by the induction hypothesis, their bitwise XOR remains strictly less than $2^{n+1}$.
In the base case $n = 0$, the inequality $\mathrm{brgc\_inverse}(0, x) < 2^0$ holds.
We proceed by induction on $n$, keeping $x$ arbitrary. For $n = 0$, $\mathrm{brgc\_inverse}(0, x) = 0$ by definition, and $2^0 = 1$, so the claim reduces to $0 < 1$, which is verified immediately by simplification.
uses
brgc_inverseinduction n generalizing x with | zero => simp [brgc_inverse]
For the inductive step, the shifted argument satisfies $x / 2 < 2^n$.
Given $x < 2^{n+1}$, rewriting the right-hand side using `pow_succ` gives $x < 2^n \cdot 2$. Linear integer arithmetic (`omega`) then deduces that $x / 2 < 2^n$.
uses
pow_succ| succ n ih => have hhalf : x / 2 < 2 ^ n := by rw [pow_succ] at hx omegaIt suffices to show that $\mathrm{brgc\_inverse}(n, x / 2) < 2^{n+1}$.
By definition, $\mathrm{brgc\_inverse}(n + 1, x) = x \oplus \mathrm{brgc\_inverse}(n, x / 2)$. Applying `Nat.xor_lt_two_pow` with the hypothesis $x < 2^{n+1}$ reduces the goal to proving that the second XOR operand is also strictly less than $2^{n+1}$.
uses
Nat.xor_lt_two_powapply Nat.xor_lt_two_pow hxThe inductive step holds: $\mathrm{brgc\_inverse}(n + 1, x) < 2^{n+1}$.
The induction hypothesis applied to $x / 2$ with the bound $x / 2 < 2^n$ gives $\mathrm{brgc\_inverse}(n, x / 2) < 2^n$. Since $2 > 0$ and $n \le n + 1$, `Nat.pow_le_pow_right` establishes $2^n \le 2^{n+1}$. Combining these two inequalities via transitivity (`lt_of_lt_of_le`) yields $\mathrm{brgc\_inverse}(n, x / 2) < 2^{n+1}$.
uses
lt_of_lt_of_le,Nat.pow_le_pow_rightexact lt_of_lt_of_le (ih hhalf) (Nat.pow_le_pow_right (by decide) (by omega))
brgc_inverse- The inverse prefix-parity transform on natural numbers, satisfying $\mathrm{brgc\_inverse}(0, x) = 0$ and $\mathrm{brgc\_inverse}(n + 1, x) = x \oplus \mathrm{brgc\_inverse}(n, x / 2)$.
pow_succ- For any base $a$ and exponent $n$, $a^{n+1} = a^n \cdot a$.
Nat.xor_lt_two_pow- If $x < 2^n$ and $y < 2^n$, then the bitwise XOR $x \oplus y < 2^n$.
lt_of_lt_of_le- In a preorder, if $a < b$ and $b \le c$, then $a < c$.
Nat.pow_le_pow_right- For $n > 0$, if $i \le j$ then $n^i \le n^j$.
- Lean implicitly unfolds the definition of `brgc_inverse (n + 1) x` as `x ^^^ brgc_inverse n (x / 2)` when matching the goal against `Nat.xor_lt_two_pow`.
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 brgc_inverse_lt_two_pow {n x : ℕ} (hx : x < 2 ^ n) : brgc_inverse n x < 2 ^ n := by induction n generalizing x with | zero => simp [brgc_inverse] | succ n ih => have hhalf : x / 2 < 2 ^ n := by rw [pow_succ] at hx omega apply Nat.xor_lt_two_pow hx exact lt_of_lt_of_le (ih hhalf) (Nat.pow_le_pow_right (by decide) (by omega))