Lemma 4.3 — Validity of the hidden-sign instances
OpenTarskiBootstrap.Dimensional.Supplement.lemma_4_3adversary-methodp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytarski-fixed-points
Let be a family of monotone self-maps of , each with a unique fixed point , whose possible fixed points lie on an antichain , and let be the downward closure of . Then for every :
- is injective on ;
- for every , the sign function is monotone;
- for every , is the unique solution of the Tarski instance : for all ,
Here equals at , at the other points of and off . The lemma shows that consists of valid instances of the hidden-sign problem whatever sign is hidden.
Differences from the source:
- encoding: a hard instance family for Tarski(n, k) in which every function has a unique fixed point → F : Set (Grid n k → Grid n k) with every member monotone and having a unique fixed point; reason: Definition 2.1: instances are monotone self-maps of [n]^k; "hard" adds no assumption beyond the stated witness
- encoding: all possible fixed points lie on an antichain A → A antichain with possibleAnswers F ⊆ A; reason: literal transcription; the set of possible fixed points is the published possibleAnswers F
- encoding: s ∈ {−1, 0, 1} → s : SignType; reason: the same three ordered values
- encoding: f* is the unique solution → for all x, x is a solution ↔ x = fixedPoint f; reason: states both that f* solves the instance and that nothing else does; fixedPoint f is f* under uniqueness
Preamble
import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_HiddenSign import Definitions.Def_TarskiBootstrap_Dimensional_Supplement_TarskiStar
Formal statement
namespace TarskiBootstrap.Dimensional.Supplement
/-- Lemma 4.3, PDF/printed pp. 17–18: for every hidden sign `s ∈ {-1, 0, 1}`, the
hidden-sign constructor `H_s(f) = (f, σ_s^f)` is injective on `F`, each `σ_s^f` is
monotone, and `f*` is the unique solution of the `Tarski*` instance `(f, σ_s^f)`. -/
theorem lemma_4_3 {n k : ℕ+} (F : Set (Grid n k → Grid n k)) (A : Set (Grid n k))
(hF : ∀ f : F, Monotone f.val ∧ ∃! x, f.val x = x)
(hA : IsAntichain (· ≤ ·) A) (hcontains : possibleAnswers F ⊆ A)
(s : SignType) :
Function.Injective (fun f : F => (f.val, hiddenSign A s f.val)) ∧
(∀ f : F, Monotone (hiddenSign A s f.val)) ∧
(∀ f : F, ∀ x : Grid n k,
IsTarskiStarSolution f.val (hiddenSign A s f.val) x ↔ x = fixedPoint f.val) := by sorry
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, Lemma 4.3, PDF/printed pp. 17–18, SHA-256 320afa8333f95589a388b30ffbfd6d7b7e5d93cdf07fa8630825fbf7d0107d59; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/6.pdf. Printed page = PDF page. No arXiv identifier/version supplied.