brgc_arbitrary_symmetric_intervals_obstruction
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.
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.
decide
- The `decide` tactic proves the theorem purely by computational evaluation of decidable propositions, calculating the explicit bitwise operations and exhausting the finite search space `Fin 4`.
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_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