AFTD Auto-Formalizing Theoretical Domains

brgc_word_lt_two_pow

theoremverified

An n-bit rank encodes an n-bit word.

Statement

theorem brgc_word_lt_two_pow {n t : ℕ} (ht : t < 2 ^ n) :
    brgc_word t < 2 ^ n
Source
Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
Verified
25 Oct 2026
Axioms
Quot.soundpropext
Built on 1
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
Used by 4

The proof, explained

The binary reflected Gray code word at rank t is defined as t ^^^ (t / 2). Since integer division satisfies t / 2 ≤ t < 2^n, both t and t / 2 are strictly bounded by 2^n. The claim then follows because the bitwise XOR of two numbers strictly less than 2^n is itself strictly less than 2^n.

  1. brgc_word t < 2 ^ n

    By definition, brgc_word t is the bitwise XOR t ^^^ (t / 2). Since integer division satisfies t / 2 ≤ t by Nat.div_le_self, chaining this with the hypothesis t < 2^n (ht) using lt_of_le_of_lt gives t / 2 < 2^n. Finally, Nat.xor_lt_two_pow applies to both t < 2^n and t / 2 < 2^n to conclude that t ^^^ (t / 2) < 2^n.

    line 3

    uses Nat.xor_lt_two_pow, lt_of_le_of_lt, Nat.div_le_self

      exact Nat.xor_lt_two_pow ht (lt_of_le_of_lt (Nat.div_le_self _ _) ht)
Nat.xor_lt_two_pow
the bitwise XOR of two natural numbers strictly bounded by 2^n is also strictly less than 2^n
lt_of_le_of_lt
if a ≤ b and b < c, then a < c
Nat.div_le_self
natural number division satisfies n / k ≤ n for all n and k

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_word_lt_two_pow {n t : ℕ} (ht : t < 2 ^ n) :    brgc_word t < 2 ^ n := by  exact Nat.xor_lt_two_pow ht (lt_of_le_of_lt (Nat.div_le_self _ _) ht)
See it in the graphDiscuss this resultChallenge it