tarski_query_complexity_le_polylog
Multidimensional 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 ≥ 1. In particular Tarski(n,5) = O(log⁵ n).
Statement
theorem tarski_query_complexity_le_polylog (k : ℕ) :
∃ C : ℕ, ∀ n : ℕ, 1 ≤ n →
tarski_query_complexity_le n k (C * (Nat.log 2 n + 2) ^ k)- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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_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_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_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)…
- 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.
- TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - 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.
The proof, explained
The theorem is proved by induction on the dimension k, establishing that fixed-point search in any sub-box of [n]^k takes at most C·(log₂ n + 2)^k queries. In the base case k = 0, the domain is a singleton, so 1 query suffices. For the induction step, dimension halving reduces search in dimension k + 1 to dimension k at cost 3(k+1)p(q + 1) + 2^(k+1) with p = log₂ n + 2, which an algebraic lemma bounds by C'·p^(k+1). Finally, global Tarski search is a special case of sub-box search on the full domain, yielding the polylogarithmic query bound.
Sub-box query complexity is monotone in the query bound: if tarski_box_query_le n k q holds and q ≤ q', then tarski_box_query_le n k q' holds.
Given any sub-box [a, b], the hypothesis provides a query tree t that finds a fixed point in at most q queries. By transitivity of ≤, its cost is also bounded by q'.
lemma tarski_query_complexity_le_polylog_mono (n k q q' : ℕ) (h : tarski_box_query_le n k q) (hqq' : q ≤ q') : tarski_box_query_le n k q' := by intro a b hab obtain ⟨t, ht⟩ := h a b hab exact ⟨t, fun f hf ha hb => ⟨(ht f hf ha hb).1, (ht f hf ha hb).2.1, (ht f hf ha hb).2.2.1, (ht f hf ha hb).2.2.2.trans hqq'⟩⟩
For any k, C and p ≥ 2, 3(k+1)p(C p^k + 1) + 2^(k+1) ≤ (3(k+1)(C+1) + 1)p^(k+1).
Since p ≥ 2, we have p^k ≥ 1 and 2^(k+1) ≤ p^(k+1). From p^k ≥ 1, it follows that C p^k + 1 ≤ (C + 1)p^k. Multiplying both sides by 3(k+1)p and rewriting p^k * p as p^(k+1) yields 3(k+1)p(C p^k + 1) ≤ 3(k+1)(C+1)p^(k+1). Adding 2^(k+1) ≤ p^(k+1) to both sides gives the desired upper bound (3(k+1)(C+1) + 1)p^(k+1).
uses
Nat.one_le_pow,Nat.pow_le_pow_left,Nat.pow_succ,Nat.mul_le_mul_left,Nat.add_le_addlemma tarski_query_complexity_le_polylog_arith (k C p : ℕ) (hp : 2 ≤ p) : 3 * (k + 1) * p * (C * p^k + 1) + 2^(k+1) ≤ (3 * (k + 1) * (C + 1) + 1) * p^(k+1) := by have h1 : 1 ≤ p^k := Nat.one_le_pow k p (by omega) have h2 : 2^(k+1) ≤ p^(k+1) := Nat.pow_le_pow_left hp (k+1) have h3 : p^(k+1) = p^k * p := Nat.pow_succ p k have h4 : C * p^k + 1 ≤ (C + 1) * p^k := by nlinarith have hA : 3 * (k + 1) * p * (C * p^k + 1) ≤ 3 * (k + 1) * p * ((C + 1) * p^k) := Nat.mul_le_mul_left (3 * (k + 1) * p) h4 have hB : 3 * (k + 1) * p * ((C + 1) * p^k) = (3 * (k + 1) * (C + 1)) * p^(k+1) := by rw [h3]; ring have hA' : 3 * (k + 1) * p * (C * p^k + 1) ≤ (3 * (k + 1) * (C + 1)) * p^(k+1) := by rw [← hB]; exact hA have hC := Nat.add_le_add hA' h2 have hD : (3 * (k + 1) * (C + 1)) * p^(k+1) + p^(k+1) = (3 * (k + 1) * (C + 1) + 1) * p^(k+1) := by ring exact hC.trans_eq hD
Base case k = 0: for any n ≥ 1, sub-box search in dimension 0 requires at most 1 · (log₂ n + 2)⁰ = 1 query.
We proceed by induction on k. In dimension 0, any sub-box has volume equal to the empty product ∏_{j ∈ Fin 0} (b_j - a_j + 1) = 1. By tarski_box_query_le_small, at most 1 query is required, matching C · (log₂ n + 2)⁰ with C = 1.
uses
tarski_box_query_le_smalllemma tarski_query_complexity_le_polylog_box (k : ℕ) : ∃ C : ℕ, ∀ n : ℕ, 1 ≤ n → tarski_box_query_le n k (C * (Nat.log 2 n + 2)^k) := by induction k with | zero => refine ⟨1, fun n hn => ?_⟩ haveI : NeZero n := ⟨by omega⟩ have h : tarski_box_query_le n 0 1 := tarski_box_query_le_small n 0 1 (fun a b hab => by simp) simpa using h
Inductive step: if dimension k has sub-box query bound C(log₂ n + 2)^k, then dimension k + 1 has bound C'(log₂ n + 2)^(k+1) with C' = 3(k+1)(C+1) + 1.
Given the bound q = C(log₂ n + 2)^k in dimension k, domain halving (tarski_box_query_le_succ_halving) bounds the search cost in dimension k + 1 by 3(k+1)p(q + 1) + 2^(k+1), where p = log₂ n + 2. Since n ≥ 1, p ≥ 2, so the arithmetic lemma tarski_query_complexity_le_polylog_arith bounds this by C' p^(k+1). Monotonicity (tarski_query_complexity_le_polylog_mono) completes the step.
uses
tarski_box_query_le_succ_halving,tarski_query_complexity_le_polylog_mono,tarski_query_complexity_le_polylog_arith| succ k ih => obtain ⟨C, hC⟩ := ih refine ⟨3 * (k + 1) * (C + 1) + 1, fun n hn => ?_⟩ haveI : NeZero n := ⟨by omega⟩ have hb := hC n hn have hs := tarski_box_query_le_succ_halving n k (C * (Nat.log 2 n + 2)^k) hb refine tarski_query_complexity_le_polylog_mono n (k+1) _ _ hs ?_ exact tarski_query_complexity_le_polylog_arith k C (Nat.log 2 n + 2) (by omega)Multidimensional Tarski search on [n]^k has query complexity bounded by C(log₂ n + 2)^k for all n ≥ 1.
We obtain the constant C from the sub-box query bound tarski_query_complexity_le_polylog_box. Finding a fixed point on the entire domain [n]^k is the special case of sub-box search on [(0,…,0), (n-1,…,n-1)], so tarski_box_query_le_imp_query_complexity implies the global query complexity bound.
uses
tarski_query_complexity_le_polylog_box,tarski_box_query_le_imp_query_complexitytheorem tarski_query_complexity_le_polylog (k : ℕ) : ∃ C : ℕ, ∀ n : ℕ, 1 ≤ n → tarski_query_complexity_le n k (C * (Nat.log 2 n + 2) ^ k) := by obtain ⟨C, hC⟩ := tarski_query_complexity_le_polylog_box k exact ⟨C, fun n hn => tarski_box_query_le_imp_query_complexity n k (C * (Nat.log 2 n + 2)^k) hn (hC n hn)⟩
Nat.add_le_add- If a + c ≤ b + d whenever a ≤ b and c ≤ d.
Nat.mul_le_mul_left- Multiplication on the left preserves order: if n ≤ m, then k * n ≤ k * m.
Nat.one_le_pow- A positive natural number raised to any power is at least 1.
Nat.pow_le_pow_left- Exponentiation preserves order in the base: if n ≤ m, then n^i ≤ m^i.
Nat.pow_succ- Power recurrence for natural numbers: n^(m+1) = n^m * n.
tarski_box_query_le_imp_query_complexity- A query bound for sub-box fixed-point search implies the same query bound for global fixed-point search on [n]^k.
tarski_box_query_le_small- If every sub-box in [n]^k has volume at most M, then fixed-point search in any sub-box requires at most M queries.
tarski_box_query_le_succ_halving- Domain halving reduces fixed-point search in dimension k + 1 to dimension k, with query bound 3(k+1)(log₂ n + 2)(q + 1) + 2^(k+1) given a bound of q in dimension k.
tarski_query_complexity_le_polylog_arith- For any k, C and any p ≥ 2, the inequality 3(k+1)p(C p^k + 1) + 2^(k+1) ≤ (3(k+1)(C+1) + 1)p^(k+1) holds.
tarski_query_complexity_le_polylog_box- For every dimension k, there exists a constant C such that sub-box fixed-point search on [n]^k requires at most C(log₂ n + 2)^k queries for all n ≥ 1.
tarski_query_complexity_le_polylog_mono- Sub-box query complexity is monotone in the query bound: if q ≤ q', any search tree with cost at most q also has cost at most q'.
- The inductive step uses an offset p = log₂ n + 2 so that p ≥ 2 holds unconditionally for all n ≥ 1 (even when log₂ 1 = 0), ensuring the arithmetic inequality applies.
- The base case instantiates the typeclass NeZero n via omega from 1 ≤ n, which is required by tarski_box_query_le_small.
- The arithmetic step relies on nlinarith and ring for intermediate polynomial simplifications.
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.
lemma tarski_query_complexity_le_polylog_mono (n k q q' : ℕ) (h : tarski_box_query_le n k q) (hqq' : q ≤ q') : tarski_box_query_le n k q' := by intro a b hab obtain ⟨t, ht⟩ := h a b hab exact ⟨t, fun f hf ha hb => ⟨(ht f hf ha hb).1, (ht f hf ha hb).2.1, (ht f hf ha hb).2.2.1, (ht f hf ha hb).2.2.2.trans hqq'⟩⟩lemma tarski_query_complexity_le_polylog_arith (k C p : ℕ) (hp : 2 ≤ p) : 3 * (k + 1) * p * (C * p^k + 1) + 2^(k+1) ≤ (3 * (k + 1) * (C + 1) + 1) * p^(k+1) := by have h1 : 1 ≤ p^k := Nat.one_le_pow k p (by omega) have h2 : 2^(k+1) ≤ p^(k+1) := Nat.pow_le_pow_left hp (k+1) have h3 : p^(k+1) = p^k * p := Nat.pow_succ p k have h4 : C * p^k + 1 ≤ (C + 1) * p^k := by nlinarith have hA : 3 * (k + 1) * p * (C * p^k + 1) ≤ 3 * (k + 1) * p * ((C + 1) * p^k) := Nat.mul_le_mul_left (3 * (k + 1) * p) h4 have hB : 3 * (k + 1) * p * ((C + 1) * p^k) = (3 * (k + 1) * (C + 1)) * p^(k+1) := by rw [h3]; ring have hA' : 3 * (k + 1) * p * (C * p^k + 1) ≤ (3 * (k + 1) * (C + 1)) * p^(k+1) := by rw [← hB]; exact hA have hC := Nat.add_le_add hA' h2 have hD : (3 * (k + 1) * (C + 1)) * p^(k+1) + p^(k+1) = (3 * (k + 1) * (C + 1) + 1) * p^(k+1) := by ring exact hC.trans_eq hDlemma tarski_query_complexity_le_polylog_box (k : ℕ) : ∃ C : ℕ, ∀ n : ℕ, 1 ≤ n → tarski_box_query_le n k (C * (Nat.log 2 n + 2)^k) := by induction k with | zero => refine ⟨1, fun n hn => ?_⟩ haveI : NeZero n := ⟨by omega⟩ have h : tarski_box_query_le n 0 1 := tarski_box_query_le_small n 0 1 (fun a b hab => by simp) simpa using h | succ k ih => obtain ⟨C, hC⟩ := ih refine ⟨3 * (k + 1) * (C + 1) + 1, fun n hn => ?_⟩ haveI : NeZero n := ⟨by omega⟩ have hb := hC n hn have hs := tarski_box_query_le_succ_halving n k (C * (Nat.log 2 n + 2)^k) hb refine tarski_query_complexity_le_polylog_mono n (k+1) _ _ hs ?_ exact tarski_query_complexity_le_polylog_arith k C (Nat.log 2 n + 2) (by omega)/-- Multidimensional Tarski search is polylogarithmic with exponent k; in particular Tarski(n,5) = O(log⁵ n). -/theorem tarski_query_complexity_le_polylog (k : ℕ) : ∃ C : ℕ, ∀ n : ℕ, 1 ≤ n → tarski_query_complexity_le n k (C * (Nat.log 2 n + 2) ^ k) := by obtain ⟨C, hC⟩ := tarski_query_complexity_le_polylog_box k exact ⟨C, fun n hn => tarski_box_query_le_imp_query_complexity n k (C * (Nat.log 2 n + 2)^k) hn (hC n hn)⟩