GrayCycle

formal source

  50
  51/-! ## The GrayCycle structure (adjacency + wrap-around) -/
  52
  53structure GrayCycle (d : Nat) where
  54  /-- Phase-indexed path through patterns (period is fixed to `2^d`). -/
  55  path : Fin (2 ^ d) → Pattern d
  56  /-- No repeats (Hamiltonian cycle candidate). -/
  57  inj : Function.Injective path
  58  /-- Consecutive phases differ in exactly one bit (with wrap-around). -/
  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