AFTD Auto-Formalizing Theoretical Domains

brgc_arbitrary_symmetric_intervals_obstruction

theoremverified

Two separate rank reflections need not compose to a one-bit Gray-word difference.

Statement

theorem brgc_arbitrary_symmetric_intervals_obstruction :
    brgc_word 1 ^^^ brgc_word 6 = 4 ∧
    brgc_word 5 ^^^ brgc_word 10 = 8 ∧
    brgc_word 1 ^^^ brgc_word 10 = 14 ∧
    ¬ ∃ i : Fin 4, brgc_word 1 ^^^ brgc_word 10 = 2 ^ i.val
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
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).

The proof, explained

The theorem exhibits an explicit counterexample demonstrating that two rank reflections in the Binary Reflected Gray Code need not compose to a one-bit Gray-word difference. At ranks 1 and 6, and ranks 5 and 10, the respective bitwise XOR differences are powers of two (4 and 8), but the composite difference between ranks 1 and 10 is 14. Because 14 is not a power of two for any index in `Fin 4`, and all values are fully concrete, the entire goal is a decidable proposition proved by direct arithmetic computation.

  1. The four arithmetic claims hold: the two interval reflections have XOR differences 4 and 8, their composite difference is 14, and 14 is not of the form 2^i for any 4-bit index i. automation

    The binary reflected Gray code function `brgc_word t = t ^^^ (t / 2)` can be evaluated directly on the given inputs: `brgc_word 1 = 1`, `brgc_word 6 = 5`, `brgc_word 5 = 7`, and `brgc_word 10 = 15`. Taking bitwise XORs gives `1 ^^^ 5 = 4`, `7 ^^^ 15 = 8`, and `1 ^^^ 15 = 14`. Finally, checking the four possible values of `i : Fin 4` (namely 0, 1, 2, 3 with powers 1, 2, 4, 8) confirms that none equals 14. Because every statement is a decidable equality or bounded search over a finite type, `decide` verifies the conjunction by direct computation.

    line 6

      decide

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_arbitrary_symmetric_intervals_obstruction :    brgc_word 1 ^^^ brgc_word 6 = 4 ∧    brgc_word 5 ^^^ brgc_word 10 = 8 ∧    brgc_word 1 ^^^ brgc_word 10 = 14 ∧    ¬ ∃ i : Fin 4, brgc_word 1 ^^^ brgc_word 10 = 2 ^ i.val := by  decide
See it in the graphDiscuss this resultChallenge it