bitword_necklace_adjacent_three_one_three
Sanity check: 100 is a rotation of 001, and the necklaces of 001 and 011 are adjacent in Q_3.
Statement
theorem bitword_necklace_adjacent_three_one_three :
bitword_is_rotation 3 1 4 ∧ bitword_necklace_adjacent 3 1 3- Source
- sanity check for bitword_is_rotation and bitword_necklace_adjacent (OP-392)
- Verified
- 20 Oct 2026
- Axioms
propext- Built on 2
- bitword_is_rotationThe n-bit word y is a cyclic rotation of the n-bit word x, i.e. x and y lie in the same binary necklace.
- bitword_necklace_adjacentThe necklaces of the n-bit words x and y are adjacent in the necklace graph Q_n: some rotation of x differs from y in exactly one bit.
The proof, explained
The theorem is proven by providing explicit witnesses for both conjuncts and verifying all conditions by direct computation. To show that $4$ ($100_2$) is a rotation of $1$ ($001_2$) in 3-bit space, the rotation count is chosen as $r = 2$. To show that the necklaces of $1$ and $3$ ($011_2$) are adjacent in the hypercube $Q_3$, the witnesses $r = 0$ and bit index $i = 1$ are provided, since $1 \oplus 3 = 2 = 2^1$. In each case, the bounds and equalities are discharged by Lean's computational decision procedure (`decide`).
$4$ is a rotation of $1$ as a 3-bit word, and the necklaces of $1$ and $3$ are adjacent in the 3-cube. automation
For the first conjunct, we provide the witness $r = 2$ rotations. Lean confirms $2 < 3$ and verifies that rotating the 3-bit word $1$ ($001_2$) by $2$ positions yields $4$ ($100_2$). For the second conjunct, we provide rotation count $r = 0$ and bit index $i = 1$. Lean verifies that $0 < 3$, $1 < 3$, and that the bitwise XOR of the unrotated word $1$ ($001_2$) with $3$ ($011_2$) is $1 \oplus 3 = 2 = 2^1$, indicating they differ in exactly bit position $1$. All numerical bounds and bitwise arithmetic equalities are verified by direct computation (`decide`).
bitword_is_rotation 3 1 4 ∧ bitword_necklace_adjacent 3 1 3 := ⟨⟨2, by decide, by decide⟩, ⟨0, by decide, 1, by decide, by decide⟩⟩
- The proof relies entirely on Lean's computational evaluator (`decide`) to check arithmetic inequalities and evaluate the bit-manipulation operations on numbers.
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 bitword_necklace_adjacent_three_one_three : bitword_is_rotation 3 1 4 ∧ bitword_necklace_adjacent 3 1 3 := ⟨⟨2, by decide, by decide⟩, ⟨0, by decide, 1, by decide, by decide⟩⟩