tarski_box_query_le_small
Brute 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 particular tarski_box_query_le n k M holds, so the new definition is inhabited (non-vacuous).
Statement
theorem tarski_box_query_le_small (n k M : ℕ) [NeZero n]
(hM : ∀ a b : Fin k → Fin n, a ≤ b → (∏ j : Fin k, ((b j : ℕ) - (a j : ℕ) + 1)) ≤ M) :
tarski_box_query_le n k M- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.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…
- tarski_subinterval_fixed_pointSubinterval fixed point theorem: if a monotone map f satisfies a ≤ f(a) and f(b) ≤ b, then f has a fixed point in the sub-box [a, b].
- 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…
- 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).
- 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…
- Used by 4
- 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_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 ≥…
The proof, explained
The theorem proves that when every box [a, b] in (Fin n)^k has size at most M, a fixed point of any monotone map f on [a, b] can be found within at most M queries by brute-force search. A query tree is constructed that tests every element of the box in order, halting as soon as it encounters a fixed point. Tarski's fixed point theorem on subintervals guarantees that the box contains at least one fixed point, ensuring the search succeeds. Finally, the query cost is bounded by the number of points in the box, which is the product of coordinate interval lengths and is at most M by assumption.
The query tree for a candidate list L uses at most |L| queries.
We proceed by induction on the candidate list L. For the empty list, the tree outputs the default point with zero queries. For a non-empty list x :: xs, the tree queries x; if f(x) = x, it halts immediately with cost 1 ≤ |x :: xs|; otherwise, it queries xs, incurring 1 + cost(xs) queries, which is at most 1 + |xs| = |x :: xs| by the induction hypothesis.
uses
List.length_consinduction L with | nil => simp [tarski_box_query_le_small_tree, TarskiQueryTree.cost] | cons x xs ih => simp only [tarski_box_query_le_small_tree, TarskiQueryTree.cost, List.length_cons] split_ifs with h · simp [TarskiQueryTree.cost] · omega
An empty candidate list cannot contain a fixed point.
For the base case of search correctness, assuming there exists a fixed point in L = [] is impossible because the empty list has no elements.
induction L with | nil => rcases h with ⟨z, hz, -⟩ cases hz
If x :: xs contains a fixed point, the search tree terminates at a fixed point in x :: xs.
If f(x) = x, the tree returns x, which is a fixed point in x :: xs. If f(x) ≠ x, the fixed point guaranteed to exist in x :: xs cannot be x, so it must lie in xs. By the induction hypothesis, running the search on xs finds a fixed point in xs, which also belongs to x :: xs via List.mem_cons_of_mem.
uses
List.mem_cons,False.elim,List.mem_cons_of_mem| cons x xs ih => simp only [tarski_box_query_le_small_tree, TarskiQueryTree.run] split_ifs with hfx · simp [TarskiQueryTree.run, hfx] · rcases h with ⟨z, hz, hfz⟩ simp only [List.mem_cons] at hz rcases hz with rfl | hz · exact False.elim (hfx hfz) · have ⟨h1, h2⟩ := ih ⟨z, hz, hfz⟩ exact ⟨List.mem_cons_of_mem x h1, h2⟩For any box [a, b], the search strategy is defined by querying all its points in list order.
Given subinterval endpoints a ≤ b, we instantiate the existential query tree with the linear search tree over the list of points in [a, b] ((Finset.Icc a b).toList), with fallback point a. We then take any monotone map f satisfying a ≤ f(a) and f(b) ≤ b.
intro a b hab use tarski_box_query_le_small_tree a (Finset.Icc a b).toList intro f hf ha hb
The box [a, b] contains at least one fixed point of f.
By Tarski's fixed point theorem on subintervals (tarski_subinterval_fixed_point), there is a point x such that a ≤ x ≤ b and f(x) = x. Therefore x belongs to the closed interval Finset.Icc a b and thus to its list representation.
uses
tarski_subinterval_fixed_point,Finset.mem_toList,Finset.mem_Icchave h_fp := tarski_subinterval_fixed_point n k f hf a b hab ha hb rcases h_fp with ⟨x, hax, hxb, hfx⟩ have hx_mem : x ∈ (Finset.Icc a b).toList := by rw [Finset.mem_toList, Finset.mem_Icc] exact ⟨hax, hxb⟩
The query tree outputs a fixed point of f lying in the box [a, b].
Applying the correctness lemma tarski_box_query_le_small_run_mem_and_fixed with witness x shows that the output of the query tree is in (Finset.Icc a b).toList and is a fixed point of f. Hence the output lies in Finset.Icc a b, satisfying a ≤ output ≤ b.
uses
tarski_box_query_le_small_run_mem_and_fixed,Finset.mem_toList,Finset.mem_Icchave h_run := tarski_box_query_le_small_run_mem_and_fixed a (Finset.Icc a b).toList f ⟨x, hx_mem, hfx⟩ have h_mem_box : TarskiQueryTree.run f (tarski_box_query_le_small_tree a (Finset.Icc a b).toList) ∈ Finset.Icc a b := by rw [← Finset.mem_toList] exact h_run.1 rw [Finset.mem_Icc] at h_mem_box refine ⟨h_mem_box.1, h_mem_box.2, h_run.2, ?_⟩
The query cost of the tree is at most M, completing the proof.
By tarski_box_query_le_small_cost_le, the query cost is bounded by the length of the list, which equals the cardinality of [a, b] (Finset.length_toList). By Pi.card_Icc, the size of [a, b] in the product order is the product over coordinates of the 1D interval sizes, each of which is (b j - a j + 1) by Fin.card_Icc. By assumption hM, this product is at most M, so transitivity (le_trans) ensures the query cost is at most M.
uses
tarski_box_query_le_small_cost_le,Finset.length_toList,Pi.card_Icc,Fin.card_Icc,le_transhave h_cost := tarski_box_query_le_small_cost_le a (Finset.Icc a b).toList f rw [Finset.length_toList] at h_cost have h_card_le : (Finset.Icc a b).card ≤ M := by rw [Pi.card_Icc] have h1 : ∀ j, (Finset.Icc (a j) (b j)).card = (b j : ℕ) - (a j : ℕ) + 1 := by intro j rw [Fin.card_Icc] have : a j ≤ b j := hab j omega simp_rw [h1] exact hM a b hab exact le_trans h_cost h_card_le
List.length_cons- Prepending an element to a list increases its length by one: `(a :: as).length = as.length + 1`.
List.mem_cons- An element belongs to `b :: l` if and only if it equals `b` or belongs to `l`.
False.elim- From a contradiction (`False`), any statement follows (ex falso quodlibet).
List.mem_cons_of_mem- If an element belongs to `l`, it also belongs to `y :: l`.
tarski_subinterval_fixed_point- Any monotone function on a subinterval `[a, b]` that maps `a ≤ f(a)` and `f(b) ≤ b` has a fixed point in `[a, b]`.
Finset.mem_toList- An element is in `s.toList` if and only if it belongs to the finite set `s`.
Finset.mem_Icc- An element `x` belongs to the closed interval `Finset.Icc a b` if and only if `a ≤ x ≤ b`.
tarski_box_query_le_small_run_mem_and_fixed- If a candidate list `L` contains a fixed point of `f`, the linear-search query tree on `L` terminates at a fixed point in `L`.
tarski_box_query_le_small_cost_le- The query cost of the linear-search tree on candidate list `L` is at most the length of `L`.
Finset.length_toList- The length of the list of elements of a finite set equals the set's cardinality.
Pi.card_Icc- The cardinality of a box (product interval) in a product order is the product of the cardinalities of its coordinate intervals.
Fin.card_Icc- The cardinality of a closed interval `[a, b]` in `Fin n` is `b + 1 - a`.
le_trans- The inequality relation `≤` is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`.
- The linear arithmetic tactic `omega` is used to justify the interval length arithmetic in `Fin n` and inductive step bounds.
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.
def tarski_box_query_le_small_tree {n k : ℕ} (x₀ : Fin k → Fin n) : List (Fin k → Fin n) → TarskiQueryTree n k | [] => .output x₀ | x :: xs => .query x (fun fx => if fx = x then .output x else tarski_box_query_le_small_tree x₀ xs)theorem tarski_box_query_le_small_cost_le {n k : ℕ} (x₀ : Fin k → Fin n) (L : List (Fin k → Fin n)) (f : (Fin k → Fin n) → Fin k → Fin n) : TarskiQueryTree.cost f (tarski_box_query_le_small_tree x₀ L) ≤ L.length := by induction L with | nil => simp [tarski_box_query_le_small_tree, TarskiQueryTree.cost] | cons x xs ih => simp only [tarski_box_query_le_small_tree, TarskiQueryTree.cost, List.length_cons] split_ifs with h · simp [TarskiQueryTree.cost] · omegatheorem tarski_box_query_le_small_run_mem_and_fixed {n k : ℕ} (x₀ : Fin k → Fin n) (L : List (Fin k → Fin n)) (f : (Fin k → Fin n) → Fin k → Fin n) (h : ∃ z ∈ L, f z = z) : TarskiQueryTree.run f (tarski_box_query_le_small_tree x₀ L) ∈ L ∧ f (TarskiQueryTree.run f (tarski_box_query_le_small_tree x₀ L)) = TarskiQueryTree.run f (tarski_box_query_le_small_tree x₀ L) := by induction L with | nil => rcases h with ⟨z, hz, -⟩ cases hz | cons x xs ih => simp only [tarski_box_query_le_small_tree, TarskiQueryTree.run] split_ifs with hfx · simp [TarskiQueryTree.run, hfx] · rcases h with ⟨z, hz, hfz⟩ simp only [List.mem_cons] at hz rcases hz with rfl | hz · exact False.elim (hfx hfz) · have ⟨h1, h2⟩ := ih ⟨z, hz, hfz⟩ exact ⟨List.mem_cons_of_mem x h1, h2⟩/-- Boxes small enough to enumerate are solved by querying all their points. -/theorem tarski_box_query_le_small (n k M : ℕ) [NeZero n] (hM : ∀ a b : Fin k → Fin n, a ≤ b → (∏ j : Fin k, ((b j : ℕ) - (a j : ℕ) + 1)) ≤ M) : tarski_box_query_le n k M := by intro a b hab use tarski_box_query_le_small_tree a (Finset.Icc a b).toList intro f hf ha hb have h_fp := tarski_subinterval_fixed_point n k f hf a b hab ha hb rcases h_fp with ⟨x, hax, hxb, hfx⟩ have hx_mem : x ∈ (Finset.Icc a b).toList := by rw [Finset.mem_toList, Finset.mem_Icc] exact ⟨hax, hxb⟩ have h_run := tarski_box_query_le_small_run_mem_and_fixed a (Finset.Icc a b).toList f ⟨x, hx_mem, hfx⟩ have h_mem_box : TarskiQueryTree.run f (tarski_box_query_le_small_tree a (Finset.Icc a b).toList) ∈ Finset.Icc a b := by rw [← Finset.mem_toList] exact h_run.1 rw [Finset.mem_Icc] at h_mem_box refine ⟨h_mem_box.1, h_mem_box.2, h_run.2, ?_⟩ have h_cost := tarski_box_query_le_small_cost_le a (Finset.Icc a b).toList f rw [Finset.length_toList] at h_cost have h_card_le : (Finset.Icc a b).card ≤ M := by rw [Pi.card_Icc] have h1 : ∀ j, (Finset.Icc (a j) (b j)).card = (b j : ℕ) - (a j : ℕ) + 1 := by intro j rw [Fin.card_Icc] have : a j ≤ b j := hab j omega simp_rw [h1] exact hM a b hab exact le_trans h_cost h_card_le