Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Run of a deterministic table on a word

Definition
StreamRot_Supplement_detRun

by iris · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationspace-complexitystreaming-algorithms

Let S0,…,SNS_0,\dots,S_NS0​,…,SN​ be finite label sets. A deterministic table consists of an initial label s0∈S0s_0\in S_0s0​∈S0​ and, for every time 0≤t<N0\le t<N0≤t<N, every letter aaa and every label s∈Sts\in S_ts∈St​, one next label nextt(a,s)∈St+1\mathrm{next}_t(a,s)\in S_{t+1}nextt​(a,s)∈St+1​. Its run on a word w=a1⋯aNw=a_1\cdots a_Nw=a1​⋯aN​ is the sequence of labels

s0,st+1=nextt(at+1,st)(0≤t<N).s_0,\qquad s_{t+1}=\mathrm{next}_t(a_{t+1},s_t)\quad(0\le t<N).s0​,st+1​=nextt​(at+1​,st​)(0≤t<N).

This is the object produced by the same-width deterministic selection of Theorem B.4: the table lives on the same label sets as the stochastic controller, and the time ttt is an argument of the table.

Formalization Note Label sets are Fin(width t)\mathrm{Fin}(\mathrm{width}\,t)Fin(widtht), as in the published controller StreamRot.Controller, and the table entry at time ttt (0-based) reads the letter wtw_twt​, the page's at+1a_{t+1}at+1​.

Definition code
import Mathlib

namespace StreamRot

namespace Supplement

/-- The run of a deterministic table on a word: the label at cut `t ≤ N` when the initial label is `s₀` and the
label after reading the letter `a_{t+1}` at cut `t` is `next t a_{t+1} s`. Qi, Constant-Failure Width Bounds for Streaming Rotations, STOC 2027 submission (manuscript sha256 3ffd9cd7…), Theorem B.4, p.22.

**Formalization Note** Label sets are `Fin (width t)`, as in `StreamRot.Controller`, and rows are 0-based: the
table entry `next t` (`t < N`) reads the letter `w t`, the page's `a_{t+1}`. The time coordinate `t` is an
argument of the table. -/
def detRun {A : Type} {width : ℕ → ℕ} {N : ℕ} (s₀ : Fin (width 0))
    (next : (t : Fin N) → A → Fin (width t) → Fin (width (t + 1))) (w : Fin N → A) :
    (t : ℕ) → t ≤ N → Fin (width t)
  | 0, _ => s₀
  | t + 1, h => next ⟨t, h⟩ (w ⟨t, h⟩) (detRun s₀ next w t (Nat.le_of_succ_le h))

end Supplement

end StreamRot
Source
Qi, Constant-Failure Width Bounds for Streaming Rotations, STOC 2027 submission (manuscript sha256 3ffd9cd7…), Theorem B.4, p.22 (PDF 24)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me