Patterns Gray Code Axioms Gray To Nat Inverts Nat To Gray

The inverse Gray code

The binary-reflected Gray code is a way of listing the integers from 0 upward so that consecutive numbers differ in exactly one binary digit. Frank Gray patented the construction in 1953, and the standard recipe is gray(n) = n XOR (n shifted right by 1). The code is useful in rotary encoders, error correction, and computer graphics because a single-bit change in position cannot be misread as a distant jump.

The inverse operation, turning a Gray code value back into an ordinary natural number, is the cumulative XOR of the code with itself shifted right by 1, then by 2, then by 4, and so on. For example, the Gray code for 6 is 5 (binary 101), and applying the inverse gives back 6. The framework's machine-checked library of formal theorems states this round trip as a theorem: for any natural number n below 2^64, applying the inverse to the Gray code of n returns n. The statement is tagged THEOREM because it is a declared axiom in the library, but the proof is not yet formalized; the library declares the classical result as an axiom pending full bitwise formalization.

In Recognition Science, the Gray code appears as a candidate for how a discrete recognition ledger might order its ticks. The framework models a ledger as a record of events, and the Gray code offers a way to step through states with minimal change. The declaration grayToNat_inverts_natToGray is one of several classical Gray code properties the library states as axioms, including the one-bit difference property and bound preservation.

The theorem does not claim that the inverse works for all natural numbers; it is restricted to n below 2^64, the bit width of the implementation. It also does not claim that the inverse is computed efficiently, only that the result is correct. The declaration is an axiom, not a proved theorem, so the library does not yet contain a formal proof of the round trip; that remains a target for future bitwise formalization.

/-- **Classical Result**: Gray code inverse is a left inverse.

The inverse Gray code operation (cumulative XOR) correctly inverts the forward
Gray code transformation.

**Proof**: Induction on bit positions with XOR algebra

**References**:
- Knuth (2011), Exercise 7.2.1.1.4
- Savage (1997), Section 2.1

**Formalization Blocker**: Requires bitwise induction infrastructure for Nat

**Status**: Standard result in discrete mathematics
-/
theorem grayToNat_inverts_natToGray :
  ∀ n : ℕ, n < 2^64 → grayInverse (n ^^^ (n >>> 1)) = n :=
  GrayCodeFacts.grayToNat_inverts_natToGray

/-- **Classical Result**: Gray code inverse is a left inverse.

The inverse Gray code operation (cumulative XOR) correctly inverts the forward
Gray code transformation.

**Proof**: Induction on bit positions with XOR algebra

**References**:
- Knuth (2011), Exercise 7.2.1.1.4
- Savage (1997), Section 2.1

**Formalization Blocker**: Requires bitwise induction infrastructure for Nat

**Status**: Standard result in discrete mathematics
-/
theorem grayToNat_inverts_natToGray :
  ∀ n : ℕ, n < 2^64 → grayInverse (n ^^^ (n >>> 1)) = n :=
  GrayCodeFacts.grayToNat_inverts_natToGray

What this page does not claim

The inverse works for all natural numbers beyond 2^64. The theorem provides an efficient algorithm, only a correctness statement. The library contains a formal proof of the round trip; it is declared as an axiom.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Patterns/GrayCodeAxioms.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: