tarski_box_query_le_imp_query_complexity
The 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 Bot/Top for general n).
Statement
theorem tarski_box_query_le_imp_query_complexity (n k q : ℕ) (hn : 1 ≤ n)
(h : tarski_box_query_le n k q) : tarski_query_complexity_le n k q- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Quot.soundpropext- 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.runThe point a query tree outputs when the black box is f.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - tarski_query_complexity_leTarski(n, k) ≤ q: some deterministic query algorithm finds a fixed point of every monotone map f : [n]^k → [n]^k (componentwise order)…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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…
- Used by 1
- 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 ≥…
The proof, explained
The proof reduces ambient query complexity to box-local query complexity by instantiating the box-local hypothesis with the full grid [a, b], where a = (0, ..., 0) and b = (n - 1, ..., n - 1). Because a is the global minimum and b is the global maximum of the grid, any monotone function f automatically satisfies the box-invariance boundary conditions a ≤ f a and f b ≤ b. The query tree guaranteed by the box-local hypothesis for this choice of box therefore finds a fixed point of any monotone function within cost q.
Establish that n ≠ 0 and unfold the definitions of box-local and ambient query complexity.
Since 1 ≤ n, linear arithmetic (omega) gives n ≠ 0, yielding the NeZero n instance needed to treat 0 as an element of Fin n. We then unfold the definitions of tarski_box_query_le in the hypothesis and tarski_query_complexity_le in the goal to reveal their logical structure.
haveI : NeZero n := ⟨by omega⟩ unfold tarski_box_query_le at h unfold tarski_query_complexity_le
Define the global minimum a and maximum b of the grid (Fin k → Fin n) and prove that a ≤ b.
We define a as the constantly 0 function and b as the constantly n - 1 function, which are well-defined since 0 < n and n - 1 < n when 1 ≤ n. The inequality a ≤ b holds coordinatewise because a i = 0 ≤ b i by Fin.zero_le.
uses
Fin.zero_lelet a : Fin k → Fin n := fun _ => ⟨0, by omega⟩ let b : Fin k → Fin n := fun _ => ⟨n - 1, by omega⟩ have hab : a ≤ b := by intro i exact Fin.zero_le _
Obtain the query tree t from the box-local hypothesis on [a, b] and propose it as the witness for ambient query complexity.
Specializing the hypothesis h to the endpoints a and b with the proof that a ≤ b yields a query tree t. We supply t as the candidate tree for the existential goal in tarski_query_complexity_le.
obtain ⟨t, ht⟩ := h a b hab refine ⟨t, ?_⟩
For any monotone function f, the lower boundary condition a ≤ f a holds.
Let f be an arbitrary monotone function. Since a is constantly 0, each coordinate satisfies a i = 0 ≤ (f a) i by Fin.zero_le, so a ≤ f a.
uses
Fin.zero_leintro f hf have hfa : a ≤ f a := fun _ => Fin.zero_le _
For any monotone function f, the upper boundary condition f b ≤ b holds.
For each coordinate i, Fin.le_def translates the inequality in Fin n to the underlying natural numbers. By Fin.isLt, the natural number representing (f b) i is strictly less than n, which by linear arithmetic (omega) implies (f b) i ≤ n - 1 = b i.
uses
Fin.le_def,Fin.isLthave hfb : f b ≤ b := by intro i rw [Fin.le_def] have := (f b i).isLt show (f b i : ℕ) ≤ n - 1 omega
The query tree t outputs a fixed point of f within query budget q.
Feeding f, its monotonicity, and the boundary conditions a ≤ f a and f b ≤ b into the guarantee for t produces the result that running t on f yields a fixed point of f with query cost at most q, closing the goal.
obtain ⟨-, -, hfix, hcost⟩ := ht f hf hfa hfb exact ⟨hfix, hcost⟩
Fin.zero_le- Every element of Fin n is greater than or equal to zero.
Fin.le_def- The order on Fin n is defined by the inequality on the underlying natural numbers.
Fin.isLt- The underlying natural number of an element of Fin n is strictly less than n.
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-local invariant on the full grid gives the ambient query-complexity bound. -/theorem tarski_box_query_le_imp_query_complexity (n k q : ℕ) (hn : 1 ≤ n) (h : tarski_box_query_le n k q) : tarski_query_complexity_le n k q := by haveI : NeZero n := ⟨by omega⟩ unfold tarski_box_query_le at h unfold tarski_query_complexity_le let a : Fin k → Fin n := fun _ => ⟨0, by omega⟩ let b : Fin k → Fin n := fun _ => ⟨n - 1, by omega⟩ have hab : a ≤ b := by intro i exact Fin.zero_le _ obtain ⟨t, ht⟩ := h a b hab refine ⟨t, ?_⟩ intro f hf have hfa : a ≤ f a := fun _ => Fin.zero_le _ have hfb : f b ≤ b := by intro i rw [Fin.le_def] have := (f b i).isLt show (f b i : ℕ) ≤ n - 1 omega obtain ⟨-, -, hfix, hcost⟩ := ht f hf hfa hfb exact ⟨hfix, hcost⟩