tarski_box_query_le_mono_budget
The box-local query invariant is monotone in the query budget: a box algorithm using at most q queries also satisfies the invariant for every larger budget q'.
Statement
theorem tarski_box_query_le_mono_budget (n k q q' : ℕ)
(h : tarski_box_query_le n k q) (hle : q ≤ q') : tarski_box_query_le n k q'- Source
- step towards tarski_box_query_le_five_log_sq
- Verified
- 22 Oct 2026
- Axioms
propext- Built on 7
- tarski_box_query_leBox-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…
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TarskiQueryTree.runThe point a query tree outputs when the black box is f.
- tarski_query_complexity_mono_budgetQuery complexity is monotone in the query budget: any algorithm using at most q queries also satisfies the bound for any q' ≥ q.
- Used by 1
- 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…
The proof, explained
To show that the box-local query invariant is monotone in the query budget, we take the exact same query tree that witnesses the invariant for budget q and use it as the witness for the larger budget q'. The execution of the tree on any valid function produces the same fixed point within the given box, and its query cost is at most q. By transitivity of inequality, this cost is also bounded by q'.
Given a sub-box [a, b], the query tree t that witnesses budget q serves as the candidate tree for budget q'.
Fix arbitrary box endpoints a ≤ b. By the hypothesis that the box invariant holds for budget q, there exists a query tree t that finds a fixed point within [a, b] using at most q queries. We use this same tree t as the witness for budget q', reducing the goal to showing that for any monotone function f satisfying the boundary conditions a ≤ f(a) and f(b) ≤ b, running t on f meets all required conditions under budget q'.
intro a b hab obtain ⟨t, ht⟩ := h a b hab refine ⟨t, fun f hf ha hb => ?_⟩
Running t on f produces a fixed point in [a, b] using at most q' queries.
From the guarantee for t under budget q, running t on f produces a point in [a, b] that is a fixed point of f and incurs a query cost of at most q. Because q ≤ q' by assumption, transitivity of inequality (le_trans) establishes that the query cost is also at most q'.
uses
le_transobtain ⟨h1, h2, h3, h4⟩ := ht f hf ha hb exact ⟨h1, h2, h3, le_trans h4 hle⟩
le_trans- If a ≤ b and b ≤ c, then a ≤ c.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Box-form analogue of tarski_query_complexity_mono_budget: the same tree witnesses the invariant for any larger budget. -/theorem tarski_box_query_le_mono_budget (n k q q' : ℕ) (h : tarski_box_query_le n k q) (hle : q ≤ q') : tarski_box_query_le n k q' := by intro a b hab obtain ⟨t, ht⟩ := h a b hab refine ⟨t, fun f hf ha hb => ?_⟩ obtain ⟨h1, h2, h3, h4⟩ := ht f hf ha hb exact ⟨h1, h2, h3, le_trans h4 hle⟩