AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_mono_budget

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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'.

  1. 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'.

    lines 4–6

      intro a b hab
      obtain ⟨t, ht⟩ := h a b hab
      refine ⟨t, fun f hf ha hb => ?_⟩
  2. 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'.

    lines 7–8

    uses le_trans

      obtain ⟨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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it