AFTD Auto-Formalizing Theoretical Domains

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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
See it in the graphDiscuss this resultChallenge it