is_single_track_gray_code
A sequence w of n-bit words is a single-track Gray code of length n and period P if it is periodic with period P, all words within a period are distinct, consecutive words differ in exactly one bit, and every column is a cyclic shift of the first column.
Statement
def is_single_track_gray_code (n P : ℕ) (w : ℕ → ℕ) : Prop
- Related work
- arXiv:2610.24758: Optimal single-track Gray codes from Gray-ordered necklaces
- Verified
- 20 Oct 2026
- Axioms
- none listed
Read back from the Lean
The definition is_single_track_gray_code n P w asserts that a sequence w : ℕ → ℕ is an n-bit single-track Gray code of period P, meaning that all of the following conditions hold:
1. Periodicity: For all t : ℕ, w (t + P) = w t.
2. Range: For all t : ℕ, w t < 2 ^ n.
3. Injectivity on the period: For all t₁ t₂ : ℕ, if t₁ < P, t₂ < P, and w t₁ = w t₂, then t₁ = t₂.
4. Gray code property: For all t : ℕ, there exists some bit position i < n such that w (t + 1) ^^^ w t = 2 ^ i (i.e., consecutive terms differ by exactly one bit, and that bit index is less than n).
5. Single-track property: There exists a shift function h : ℕ → ℕ such that h 0 = 0, and for all t : ℕ and all bit indices j < n, the j-th bit of w t (Nat.testBit (w t) j) is equal to the 0-th bit of w (t + h j) (Nat.testBit (w (t + h j)) 0).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Predicate asserting that w is a single-track Gray code of length n and period P. -/ def is_single_track_gray_code (n P : ℕ) (w : ℕ → ℕ) : Prop := (∀ t, w (t + P) = w t) ∧ (∀ t, w t < 2 ^ n) ∧ (∀ t₁ t₂, t₁ < P → t₂ < P → w t₁ = w t₂ → t₁ = t₂) ∧ (∀ t, ∃ i < n, w (t + 1) ^^^ w t = 2 ^ i) ∧ ∃ h : ℕ → ℕ, h 0 = 0 ∧ ∀ t, ∀ j < n, Nat.testBit (w t) j = Nat.testBit (w (t + h j)) 0