AFTD Auto-Formalizing Theoretical Domains

is_single_track_gray_code

deforiginal

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