AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_lt_two_pow

theoremverified

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

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}$.

  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.

    lines 2–3

    uses brgc_inverse

      induction n generalizing x with
      | zero => simp [brgc_inverse]
  2. 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$.

    lines 4–7

    uses pow_succ

      | succ n ih =>
        have hhalf : x / 2 < 2 ^ n := by
          rw [pow_succ] at hx
          omega
  3. It 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}$.

    line 8

    uses Nat.xor_lt_two_pow

        apply Nat.xor_lt_two_pow hx
  4. The 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}$.

    line 9

    uses lt_of_lt_of_le, Nat.pow_le_pow_right

        exact 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$.

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