tarski_box_query_le
def
Box-local Tarski query invariant: for every sub-box [a,b] (a ≤ b) of [n]^k there is a single deterministic query tree — depending only on the box, not on the unknown f — that, against every monotone f with a ≤ f a and f b ≤ b, outputs a fixed point of f lying inside [a,b] using at most q queries.
Statement
def tarski_box_query_le (n k q : ℕ) : Prop
- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 5
- TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
- TarskiQueryTreeA deterministic adaptive query algorithm for an unknown map f : [n]^k → [n]^k, as a decision tree: a leaf outputs a point; an internal…
- TarskiQueryTree.runThe point a query tree outputs when the black box is f.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 9
- tarski_box_query_le_imp_query_complexityThe box-local invariant implies the ambient query complexity notion, by taking the full box [0, n−1]^k (needs n ≥ 1 since Fin n has no…
- tarski_box_query_le_zero_dimDimension zero is free: in dimension 0 (the one-point box) one query suffices, for every n and every box.
- tarski_box_query_le_two_fiveSmall instance at the exact target parameters: in dimension 5 over the two-element grid, every box is solvable with at most 2^5 = 32…
- tarski_box_query_le_polylogBox-form state of the art: for every dimension k there is a constant C such that every sub-box of [n]^k admits a box algorithm with at…
- tarski_box_query_le_mono_budgetThe box-local query invariant is monotone in the query budget: a box algorithm using at most q queries also satisfies the invariant for…
- tarski_box_query_le_succ_halvingOne dimension costs a factor log₂ n: from a box-search algorithm in dimension k with q queries one gets one in dimension k+1 with at most…
- tarski_query_complexity_le_polylogMultidimensional Tarski search is polylogarithmic: for every fixed k there is a constant C with Tarski(n,k) ≤ C·(log₂ n + 2)^k for all n ≥…
- tarski_box_query_le_smallBrute force on small boxes: if every box in dimension k has at most M points, then every box query is answerable within M queries — and in…
- tarski_box_query_le_log_sq_of_nat_budgetAssembly step: if some natural constant C gives, for every n ≥ 2, a five-dimensional box algorithm with at most C·(log₂ n + 2)² queries,…
Lean source view module on GitHub
/-- Box-local Tarski query invariant: one tree, uniform in the oracle f, finds a fixed point inside any sub-box [a,b]. -/ def tarski_box_query_le (n k q : ℕ) : Prop := ∀ a b : Fin k → Fin n, a ≤ b → ∃ t : TarskiQueryTree n k, ∀ f : (Fin k → Fin n) → Fin k → Fin n, Monotone f → a ≤ f a → f b ≤ b → a ≤ TarskiQueryTree.run f t ∧ TarskiQueryTree.run f t ≤ b ∧ f (TarskiQueryTree.run f t) = TarskiQueryTree.run f t ∧ TarskiQueryTree.cost f t ≤ q