AFTD Auto-Formalizing Theoretical Domains

bitword_necklace_adjacent_three_one_three

theoremverified

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`).

  1. $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`).

    line 2

        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⟩⟩

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 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⟩⟩
See it in the graphDiscuss this resultChallenge it