Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The staircase SSS and the staircase constructor E^\hat{\mathcal E}E^

Definition
TarskiBootstrap_Dimensional_Supplement_Staircase

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

adversary-methodp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytarski-fixed-points

Let Q={1,…,m}×[n]kQ=\{1,\dots,m\}\times[n]^kQ={1,…,m}×[n]k with the lexicographic order: (i,x)⪯(j,y)(i,x)\preceq(j,y)(i,x)⪯(j,y) iff i<ji<ji<j, or i=ji=ji=j and x⪯yx\preceq yx⪯y. Give Q2Q^2Q2 the product order and let

S=⋃i=1mDi ∪ ⋃i=1m−1Bi,Di=Pi×Pi,Bi=Pi×Pi+1,Pi={(i,x)},S=\bigcup_{i=1}^m D_i\ \cup\ \bigcup_{i=1}^{m-1}B_i,\qquad D_i=P_i\times P_i,\quad B_i=P_i\times P_{i+1},\quad P_i=\{(i,x)\},S=i=1⋃m​Di​ ∪ i=1⋃m−1​Bi​,Di​=Pi​×Pi​,Bi​=Pi​×Pi+1​,Pi​={(i,x)},

with the induced order. With σi=σsifi\sigma_i=\sigma^{f_i}_{s_i}σi​=σsi​fi​​, the transition directions are

φi(x,y)={+1,σi(x)=+1,−1,σi(x)<+1∧σi(y)=−1,0,otherwise,ψi(x,y)={−1,σi(x)<+1,0,σi(x)=+1∧σi+1(y)=−1,+1,σi(x)=+1∧σi+1(y)>−1.\varphi_i(x,y)=\begin{cases}+1,&\sigma_i(x)=+1,\\-1,&\sigma_i(x)<+1\wedge\sigma_i(y)=-1,\\0,&\text{otherwise,}\end{cases}\qquad \psi_i(x,y)=\begin{cases}-1,&\sigma_i(x)<+1,\\0,&\sigma_i(x)=+1\wedge\sigma_{i+1}(y)=-1,\\+1,&\sigma_i(x)=+1\wedge\sigma_{i+1}(y)>-1.\end{cases}φi​(x,y)=⎩⎨⎧​+1,−1,0,​σi​(x)=+1,σi​(x)<+1∧σi​(y)=−1,otherwise,​ψi​(x,y)=⎩⎨⎧​−1,0,+1,​σi​(x)<+1,σi​(x)=+1∧σi+1​(y)=−1,σi​(x)=+1∧σi+1​(y)>−1.​

The staircase constructor F=E^(s,f):S→SF=\hat{\mathcal E}(s,f):S\to SF=E^(s,f):S→S is, on DiD_iDi​ with d=φi(x,y)d=\varphi_i(x,y)d=φi​(x,y),

F((i,x),(i,y))={((i−1,⊤),(i,fi(y))),d=−1∧i>1,((i,fi(x)),(i+1,⊥)),d=+1∧i<m,((i,fi(x)),(i,fi(y))),otherwise,F((i,x),(i,y))=\begin{cases}((i-1,\top),(i,f_i(y))),& d=-1\wedge i>1,\\((i,f_i(x)),(i+1,\bot)),& d=+1\wedge i<m,\\((i,f_i(x)),(i,f_i(y))),&\text{otherwise,}\end{cases}F((i,x),(i,y))=⎩⎨⎧​((i−1,⊤),(i,fi​(y))),((i,fi​(x)),(i+1,⊥)),((i,fi​(x)),(i,fi​(y))),​d=−1∧i>1,d=+1∧i<m,otherwise,​

and on BiB_iBi​ with d=ψi(x,y)d=\psi_i(x,y)d=ψi​(x,y),

F((i,x),(i+1,y))={((i,fi(x)),(i,⊤)),d=−1,((i,fi(x)),(i+1,fi+1(y))),d=0,((i+1,⊥),(i+1,fi+1(y))),d=+1,F((i,x),(i+1,y))=\begin{cases}((i,f_i(x)),(i,\top)),& d=-1,\\((i,f_i(x)),(i+1,f_{i+1}(y))),& d=0,\\((i+1,\bot),(i+1,f_{i+1}(y))),& d=+1,\end{cases}F((i,x),(i+1,y))=⎩⎨⎧​((i,fi​(x)),(i,⊤)),((i,fi​(x)),(i+1,fi+1​(y))),((i+1,⊥),(i+1,fi+1​(y))),​d=−1,d=0,d=+1,​

where ⊤=(n−1)1\top=(n-1)\mathbf 1⊤=(n−1)1 and ⊥=0\bot=0⊥=0.

Formalization Note QQQ is Mathlib's lexicographic product Fin m ×ₗ Grid n k; SSS is a subtype of Q×QQ\times QQ×Q with the induced product order; block indices 1,…,m1,\dots,m1,…,m are Fin m, so i>1i>1i>1 reads 0 < i.val and i<mi<mi<m reads i.val + 1 < m.

Definition code
import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_HiddenSign

namespace TarskiBootstrap.Dimensional.Supplement

/-- `Q = {1, …, m} × [n]^k` of (4.8), PDF/printed p. 19, with the lexicographic order:
`(i, x) ⪯ (j, y)` iff `i < j`, or `i = j` and `x ⪯ y` (block indices encoded by
`Fin m`). -/
abbrev StairQ (n k m : ℕ+) := Fin (m : ℕ) ×ₗ Grid n k

/-- Membership in the staircase `S = ⋃ D_i ∪ ⋃ B_i ⊆ Q²` of (4.10), p. 20: a main block
point `((i, x), (i, y)) ∈ D_i` or a bridge point `((i, x), (i + 1, y)) ∈ B_i`. -/
def IsStaircase {n k m : ℕ+} (u : StairQ n k m × StairQ n k m) : Prop :=
  (ofLex u.2).1 = (ofLex u.1).1 ∨ (ofLex u.2).1.val = (ofLex u.1).1.val + 1

/-- The staircase `S` with the order induced from the product order on `Q²`. -/
abbrev Staircase (n k m : ℕ+) := {u : StairQ n k m × StairQ n k m // IsStaircase u}

/-- The transition direction `φ_i` on the main block `D_i`, (4.13), p. 21, for the sign
function `σ = σ_{s_i}^{f_i}`. -/
def stairPhi {n k : ℕ+} (σ : Grid n k → SignType) (x y : Grid n k) : SignType :=
  if σ x = 1 then 1 else if σ x < 1 ∧ σ y = -1 then -1 else 0

/-- The transition direction `ψ_i` on the bridge `B_i`, (4.14), p. 21, for
`σ = σ_{s_i}^{f_i}` and `σ' = σ_{s_{i+1}}^{f_{i+1}}`. -/
def stairPsi {n k : ℕ+} (σ σ' : Grid n k → SignType) (x y : Grid n k) : SignType :=
  if σ x < 1 then -1 else if σ x = 1 ∧ σ' y = -1 then 0 else 1

/-- The staircase constructor `Ê(s, f) : S → S` of Definition 4.8, (4.15)–(4.16),
PDF/printed p. 21, with `σ_r = σ_{s_r}^{f_r}` the hidden sign functions of (4.2) for the
antichain `A`, `⊤ = (n-1)𝟏` and `⊥ = 0`. On `D_i` with `d = φ_i(x, y)`:
`((i-1, ⊤), (i, f_i(y)))` if `d = -1 ∧ i > 1`; `((i, f_i(x)), (i+1, ⊥))` if
`d = +1 ∧ i < m`; otherwise `((i, f_i(x)), (i, f_i(y)))`. On `B_i` with `d = ψ_i(x, y)`:
`((i, f_i(x)), (i, ⊤))` if `d = -1`; `((i, f_i(x)), (i+1, f_{i+1}(y)))` if `d = 0`;
`((i+1, ⊥), (i+1, f_{i+1}(y)))` if `d = +1`. -/
noncomputable def staircase {n k m : ℕ+} (A : Set (Grid n k))
    (s : Fin (m : ℕ) → SignType) (f : Fin (m : ℕ) → Grid n k → Grid n k)
    (u : Staircase n k m) : Staircase n k m :=
  let i := (ofLex u.val.1).1
  let x := (ofLex u.val.1).2
  let j := (ofLex u.val.2).1
  let y := (ofLex u.val.2).2
  let σ : Fin (m : ℕ) → Grid n k → SignType := fun r => hiddenSign A (s r) (f r)
  if j = i then
    if h1 : stairPhi (σ i) x y = -1 ∧ 0 < i.val then
      ⟨(toLex (⟨i.val - 1, by omega⟩, ⊤), toLex (i, f i y)),
        Or.inr (by show i.val = (i.val - 1) + 1; omega)⟩
    else if h2 : stairPhi (σ i) x y = 1 ∧ i.val + 1 < (m : ℕ) then
      ⟨(toLex (i, f i x), toLex (⟨i.val + 1, h2.2⟩, ⊥)), Or.inr rfl⟩
    else
      ⟨(toLex (i, f i x), toLex (i, f i y)), Or.inl rfl⟩
  else
    if stairPsi (σ i) (σ j) x y = -1 then
      ⟨(toLex (i, f i x), toLex (i, ⊤)), Or.inl rfl⟩
    else if stairPsi (σ i) (σ j) x y = 0 then
      ⟨(toLex (i, f i x), toLex (j, f j y)), u.property⟩
    else
      ⟨(toLex (j, ⊥), toLex (j, f j y)), Or.inl rfl⟩

end TarskiBootstrap.Dimensional.Supplement
Source
Li, Ma, Yang and Zhao, Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points, STOC 2027 submission #6 (2026), frozen preprint, equations (4.8), (4.10), (4.13)–(4.16) and Definition 4.8, PDF/printed pp. 19–21, SHA-256 320afa8333f95589a388b30ffbfd6d7b7e5d93cdf07fa8630825fbf7d0107d59; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/6.pdf. Printed page = PDF page. No arXiv identifier/version supplied.

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