Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The composite problem OSm∘(TarskiH∣F′,… )\mathrm{OS}_m\circ(\mathrm{Tarski}^H|_{\mathcal F'},\dots)OSm​∘(TarskiH∣F′​,…)

Definition
TarskiBootstrap_Dimensional_Supplement_Composite

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

Fix AAA, F\mathcal FF and mmm. The composite problem has index set {1,…,m}×[n]k\{1,\dots,m\}\times[n]^k{1,…,m}×[n]k. Its domain D\mathcal DD (equation (2.13)) consists of the strings xxx on this index set such that, for every rrr, the block z↦x(r,z)z\mapsto x(r,z)z↦x(r,z) is an input of TarskiH∣F′\mathrm{Tarski}^H|_{\mathcal F'}TarskiH∣F′​, and the vector of inner answers (TarskiH(x(r,⋅)))r\bigl(\mathrm{Tarski}^H(x(r,\cdot))\bigr)_{r}(TarskiH(x(r,⋅)))r​ is an OSm\mathrm{OS}_mOSm​ instance. The composite function (2.12) applies OSm\mathrm{OS}_mOSm​ to that vector. For signs s=(s1,…,sm)s=(s_1,\dots,s_m)s=(s1​,…,sm​) and maps f=(f1,…,fm)f=(f_1,\dots,f_m)f=(f1​,…,fm​), the oracle of the input (s,f)(s,f)(s,f) is

h(r,z)=Hsr(fr)(z)=(fr(z), σsrfr(z)).h(r,z)=H_{s_r}(f_r)(z)=\bigl(f_r(z),\ \sigma^{f_r}_{s_r}(z)\bigr).h(r,z)=Hsr​​(fr​)(z)=(fr​(z), σsr​fr​​(z)).

This is the abstract problem that the staircase construction embeds into a grid.

Formalization Note Positions 1,…,m1,\dots,m1,…,m are encoded by Fin m.

Definition code
import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_HiddenSign
import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_OrderedSearch

namespace TarskiBootstrap.Dimensional.Supplement

/-- The oracle `h(r, z) = H_{s_r}(f_r)(z) = (f_r(z), σ_{s_r}^{f_r}(z))` of the composite
input `(s, f)`, on the index set `{1, …, m} × [n]^k` of (2.11) (positions encoded by
`Fin m`), PDF/printed pp. 19, 21. -/
noncomputable def compositeOracle {n k : ℕ+} {m : ℕ+} (A : Set (Grid n k))
    (s : Fin (m : ℕ) → SignType) (f : Fin (m : ℕ) → Grid n k → Grid n k) :
    Fin (m : ℕ) × Grid n k → Grid n k × SignType :=
  fun p => hiddenSignOracle A (s p.1) (f p.1) p.2

/-- The domain (2.13), p. 8, of `OS_m ∘ (Tarski^H(n,k)|F′, …, Tarski^H(n,k)|F′)`:
strings on `{1, …, m} × [n]^k` whose `r`-th block is an input of `Tarski^H|F′` for
every `r`, and whose vector of inner answers is an `OS_m` instance. -/
noncomputable def compositeDomain {n k : ℕ+} (A : Set (Grid n k))
    (F : Set (Grid n k → Grid n k)) (m : ℕ+) :
    Set (Fin (m : ℕ) × Grid n k → Grid n k × SignType) :=
  {x | (∀ r, (fun z => x (r, z)) ∈ hiddenSignFamily A F) ∧
    ∃ i, (fun r => tarskiHAnswer (fun z => x (r, z))) = osInstance m i}

/-- The composite function (2.12), p. 8: `OS_m` applied to the vector of inner
`Tarski^H` answers. -/
noncomputable def compositeAnswer {n k : ℕ+} (m : ℕ+)
    (x : Fin (m : ℕ) × Grid n k → Grid n k × SignType) : Fin (m : ℕ) :=
  osOutput m (fun r => tarskiHAnswer (fun z => x (r, z)))

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, Definition 2.9, equations (2.11)–(2.13), PDF/printed p. 8; §4.2–4.3, 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