GrayCover

formal source

  59  oneBit_step : ∀ i : Fin (2 ^ d), OneBitDiff (path i) (path (i + 1))
  60
  61/-- A Gray *cover* with an arbitrary period `T`: adjacency (one-bit steps) plus coverage (surjection). -/
  62structure GrayCover (d T : Nat) [NeZero T] where
  63  path : Fin T → Pattern d
  64  complete : Function.Surjective path
  65  oneBit_step : ∀ i : Fin T, OneBitDiff (path i) (path (i + 1))
  66
  67/-! Minimality: any cover of all `d`-bit patterns needs at least `2^d` ticks. -/
  68theorem grayCover_min_ticks {d T : Nat} [NeZero T] (w : GrayCover d T) : 2 ^ d ≤ T :=
  69  Patterns.min_ticks_cover (d := d) (T := T) w.path w.complete
  70
  71theorem grayCover_eight_tick_min {T : Nat} [NeZero T] (w : GrayCover 3 T) : 8 ≤ T := by
  72  simpa using (Patterns.eight_tick_min (T := T) w.path w.complete)
  73
  74/-!
  75### A fully explicit, fully decidable 3-bit witness (the actual “octave”)
  76
  77This gives a *rigorous* Gray cycle for `d=3` (period 8) without any axioms.
  78We deliberately start here because it is the “octave” case used throughout RS.
  79-/
  80
  81/-- Convert a `Fin 8` codeword into a 3-bit pattern via `testBit`. -/
  82def pattern3 : Fin 8 → Pattern 3
  83| ⟨0, _⟩ => fun _ => false
  84| ⟨1, _⟩ => fun j => decide (j.val = 0)
  85| ⟨2, _⟩ => fun j => decide (j.val = 1)
  86| ⟨3, _⟩ => fun j => decide (j.val = 0 ∨ j.val = 1)
  87| ⟨4, _⟩ => fun j => decide (j.val = 2)
  88| ⟨5, _⟩ => fun j => decide (j.val = 0 ∨ j.val = 2)
  89| ⟨6, _⟩ => fun j => decide (j.val = 1 ∨ j.val = 2)
  90| ⟨7, _⟩ => fun _ => true
  91
  92/-- Canonical 3-bit Gray order as a function `Fin 8 → Fin 8`.