`Pattern`

definition

show as: view math explainer →

module: IndisputableMonolith.Streams.Blocks
domain: Streams
line: 19 · github
papers citing: none yet

open explainer

Generate a durable explainer page for this declaration.

open lean source

IndisputableMonolith.Streams.Blocks on GitHub at line 19.

browse module

All declarations in this module, on Recognition.

explainer page

Tracked in the explainer inventory; generation is lazy so crawlers do not trigger LLM jobs.

open explainer

depends on

used by

formal source

  16def Stream := Nat → Bool
  17
  18/-- A finite window/pattern of length `n`. -/
  19def Pattern (n : Nat) := Fin n → Bool
  20
  21/-- Integer functional `Z` counting ones in a finite window. -/
  22def Z_of_window {n : Nat} (w : Pattern n) : Nat :=
  23  ∑ i : Fin n, (if w i then 1 else 0)
  24
  25/-- The cylinder set of streams whose first `n` bits coincide with the window `w`. -/
  26def Cylinder {n : Nat} (w : Pattern n) : Set Stream :=
  27  { s | ∀ i : Fin n, s i.val = w i }
  28
  29/-- Periodic extension of an 8‑bit window. -/
  30def extendPeriodic8 (w : Pattern 8) : Stream := fun t =>
  31  let i : Fin 8 := ⟨t % 8, Nat.mod_lt _ (by decide)⟩
  32  w i
  33
  34/-- Sum of the first `m` bits of a stream. -/
  35def sumFirst (m : Nat) (s : Stream) : Nat :=
  36  ∑ i : Fin m, (if s i.val then 1 else 0)
  37
  38/-- If a stream agrees with a window on its first `n` bits, then the first‑`n` sum equals `Z`. -/
  39lemma sumFirst_eq_Z_on_cylinder {n : Nat} (w : Pattern n)
  40  {s : Stream} (hs : s ∈ Cylinder w) :
  41  sumFirst n s = Z_of_window w := by
  42  classical
  43  unfold sumFirst Z_of_window Cylinder at *
  44  have : (fun i : Fin n => (if s i.val then 1 else 0)) =
  45         (fun i : Fin n => (if w i then 1 else 0)) := by
  46    funext i; simpa [hs i]
  47  simpa [this]
  48
  49/-- For an 8‑bit window extended periodically, the first‑8 sum equals `Z`. -/

papers checked against this theorem

No papers in the current corpus map onto this theorem yet.