Conjugation and the antichain constructor
DefinitionTarskiBootstrap_Dimensional_Supplement_AntichainConstructoradversary-methodp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-query-complexitytarski-fixed-points
For its conjugate is . For a self-map of , the antichain constructor produces the self-map of
For a family , .
The constructor doubles the dimension and places the fixed points on the antichain of points with coordinate sum , which the logarithmic and dimensional bootstrapping theorems require.
Formalization Note is represented as the product Grid n k × Grid n k with the componentwise order, which is the coordinatewise order on the coordinates (an explicit order isomorphism is flattenBlocks n k 2 of the published grid definition).
Definition code
import Definitions.Def_TarskiBootstrap_Dimensional_FixedPoint
namespace TarskiBootstrap.Dimensional.Supplement
/-- The conjugate `x̄ = (n-1)𝟏 - x` of a grid point, §3.3, PDF/printed p. 16. -/
def gridConj {n k : ℕ+} (x : Grid n k) : Grid n k := fun i => Fin.rev (x i)
/-- Definition 3.8, PDF/printed p. 16: `B(f)(x, y) = (f(x), conj(f(conj y)))`.
The grid `[n]^{2k}` is the pair `Grid n k × Grid n k` with the product order, which is
the coordinatewise order on the `2k` coordinates. -/
def antichainConstructor {n k : ℕ+} (f : Grid n k → Grid n k) :
Grid n k × Grid n k → Grid n k × Grid n k :=
fun p => (f p.1, gridConj (f (gridConj p.2)))
/-- The image family `B(F) = {B(f) : f ∈ F}`. -/
def antichainFamily {n k : ℕ+} (F : Set (Grid n k → Grid n k)) :
Set (Grid n k × Grid n k → Grid n k × Grid n k) :=
Set.range (fun f : F => antichainConstructor f.val)
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 3.8 and equation (3.21), PDF/printed p. 16, SHA-256 320afa8333f95589a388b30ffbfd6d7b7e5d93cdf07fa8630825fbf7d0107d59; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/6.pdf. Printed page = PDF page. No arXiv identifier/version supplied.