tarski_box_query_le_polylog
Box-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 most C·(log₂ n + 2)^k queries, for all n ≥ 1. In particular k = 5 gives log⁵ n, whereas the open target asks for log² n at k = 5 — this node fixes the baseline the target must beat, in box-local (uniform-in-box) form rather than the ambient form of tarski_query_complexity_le_polylog.
Statement
theorem tarski_box_query_le_polylog (k : ℕ) :
∃ C : ℕ, ∀ n : ℕ, 1 ≤ n → tarski_box_query_le n k (C * (Nat.log 2 n + 2) ^ k)- Source
- step towards tarski_box_query_le_five_log_sq
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 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_mono_budgetThe box-local query invariant is monotone in the query budget: a box algorithm using at most q queries also satisfies the invariant for…
- 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_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…
The proof, explained
The theorem bounds the query complexity of finding a Tarski fixed point in any sub-box of [n]^k by C(k)·(log₂ n + 2)^k. The proof proceeds by induction on the dimension k, using the halving and slicing recurrence tarski_box_query_le_succ_halving to reduce dimension k+1 to dimension k. An explicit arithmetic calculation shows that the query budget generated by the halving step is bounded by the recursive definition of C(k+1)·(log₂ n + 2)^(k+1).
The bound holds for all n ≥ 1 in all dimensions k, proved by induction on k.
We proceed by mathematical induction on the dimension k.
induction' k with k ihThe bound holds in dimension 0.
For k = 0, C(0) = 1 and (log₂ n + 2)⁰ = 1, so the required query bound simplifies to 1. In dimension 0, the domain has a unique trivial point, which requires at most 1 query by tarski_box_query_le_zero_dim.
uses
tarski_box_query_le_polylog_C,pow_zero,mul_one,tarski_box_query_le_zero_dim· intro n hn simp only [tarski_box_query_le_polylog_C, pow_zero, mul_one] exact tarski_box_query_le_zero_dim n
In dimension k + 1, it suffices to show that the halving query budget does not exceed C(k + 1) · (log₂ n + 2)^(k + 1).
Assuming the induction hypothesis for dimension k and taking n ≥ 1 (which ensures n ≠ 0), we apply tarski_box_query_le_succ_halving to obtain a valid algorithm in dimension k + 1 with query budget 3(k+1)(log₂ n + 2)(C(k)(log₂ n + 2)^k + 1) + 2^(k+1). By budget monotonicity (tarski_box_query_le_mono_budget), it suffices to prove that this budget is bounded above by C(k+1) · (log₂ n + 2)^(k+1).
uses
tarski_box_query_le_succ_halving,tarski_box_query_le_mono_budget· intro n hn have : NeZero n := ⟨by omega⟩ have h_rec := tarski_box_query_le_succ_halving n k (tarski_box_query_le_polylog_C k * (Nat.log 2 n + 2) ^ k) (ih n hn) apply tarski_box_query_le_mono_budget (q := 3 * (k + 1) * (Nat.log 2 n + 2) * (tarski_box_query_le_polylog_C k * (Nat.log 2 n + 2) ^ k + 1) + 2 ^ (k + 1)) · exact h_rec
The term C(k) · p^k + 1 is at most (C(k) + 1) · p^k, where p = log₂ n + 2.
Abbreviating p = log₂ n + 2, we have p ≥ 2 and therefore p^k ≥ 1. Replacing 1 with p^k gives C(k) · p^k + 1 ≤ C(k) · p^k + p^k = (C(k) + 1) · p^k.
uses
Nat.pow_le_pow_left,Nat.one_le_pow,Nat.add_le_add_left· set p := Nat.log 2 n + 2 have hp : 2 ≤ p := by dsimp [p]; omega have h1 : 2 ^ (k + 1) ≤ p ^ (k + 1) := Nat.pow_le_pow_left hp (k + 1) have hpk : 1 ≤ p ^ k := Nat.one_le_pow k p (by omega) have h2 : tarski_box_query_le_polylog_C k * p ^ k + 1 ≤ (tarski_box_query_le_polylog_C k + 1) * p ^ k := by calc tarski_box_query_le_polylog_C k * p ^ k + 1 ≤ tarski_box_query_le_polylog_C k * p ^ k + p ^ k := Nat.add_le_add_left hpk _ _ = (tarski_box_query_le_polylog_C k + 1) * p ^ k := by ring
The first term 3(k + 1)p(C(k)p^k + 1) is at most 3(k + 1)(C(k) + 1)p^(k + 1).
Multiplying the previous inequality by 3(k + 1)p and regrouping terms gives 3(k+1)p(C(k)p^k + 1) ≤ 3(k+1)p((C(k)+1)p^k) = 3(k+1)(C(k)+1)(p · p^k) = 3(k+1)(C(k)+1)p^(k+1).
uses
Nat.mul_le_mul_left,pow_succ'have h3 : 3 * (k + 1) * p * (tarski_box_query_le_polylog_C k * p ^ k + 1) ≤ 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * p ^ (k + 1) := by calc 3 * (k + 1) * p * (tarski_box_query_le_polylog_C k * p ^ k + 1) ≤ 3 * (k + 1) * p * ((tarski_box_query_le_polylog_C k + 1) * p ^ k) := by apply Nat.mul_le_mul_left exact h2 _ = 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * (p * p ^ k) := by ring _ = 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * p ^ (k + 1) := by rw [← pow_succ']
The total halving budget is bounded by C(k + 1) · p^(k + 1).
Since 2 ≤ p, we have 2^(k+1) ≤ p^(k+1). Adding this to the bound on the first term yields 3(k+1)(C(k)+1)p^(k+1) + p^(k+1) = (3(k+1)(C(k)+1) + 1)p^(k+1), which matches the definition of C(k+1) · p^(k+1) by definition.
uses
Nat.add_le_add,tarski_box_query_le_polylog_Ccalc 3 * (k + 1) * p * (tarski_box_query_le_polylog_C k * p ^ k + 1) + 2 ^ (k + 1) ≤ 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * p ^ (k + 1) + p ^ (k + 1) := Nat.add_le_add h3 h1 _ = (3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) + 1) * p ^ (k + 1) := by ring _ = tarski_box_query_le_polylog_C (k + 1) * p ^ (k + 1) := by rfl
pow_zero- Any number to the zeroth power is 1.
mul_one- Multiplying any element by 1 leaves it unchanged.
tarski_box_query_le_zero_dim- In dimension zero, any sub-box Tarski instance can be solved with at most 1 query.
tarski_box_query_le_succ_halving- Given a query bound q in dimension k, binary halving along coordinate slices solves the problem in dimension k+1 with query complexity at most 3(k+1)(log₂ n + 2)(q + 1) + 2^(k+1).
tarski_box_query_le_mono_budget- Query complexity is monotone in the query budget: an algorithm with budget q also respects any larger budget q'.
Nat.pow_le_pow_left- Taking powers preserves inequality between positive bases: if n ≤ m, then n^i ≤ m^i.
Nat.one_le_pow- Any positive number raised to a natural power is at least 1.
Nat.add_le_add_left- Adding a common term to the left preserves an inequality.
Nat.mul_le_mul_left- Multiplying on the left by a natural number preserves an inequality.
pow_succ'- For powers of an element, a^(n+1) = a * a^n.
Nat.add_le_add- Adding two inequalities preserves the order.
tarski_box_query_le_polylog_bound- The inductive query complexity bound in dimension k with constant tarski_box_query_le_polylog_C k.
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.
/-- Recurrence constant bounding the query complexity in dimension `k`. -/def tarski_box_query_le_polylog_C : ℕ → ℕ | 0 => 1 | k + 1 => 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) + 1theorem tarski_box_query_le_polylog_bound (k : ℕ) : ∀ n : ℕ, 1 ≤ n → tarski_box_query_le n k (tarski_box_query_le_polylog_C k * (Nat.log 2 n + 2) ^ k) := by induction' k with k ih · intro n hn simp only [tarski_box_query_le_polylog_C, pow_zero, mul_one] exact tarski_box_query_le_zero_dim n · intro n hn have : NeZero n := ⟨by omega⟩ have h_rec := tarski_box_query_le_succ_halving n k (tarski_box_query_le_polylog_C k * (Nat.log 2 n + 2) ^ k) (ih n hn) apply tarski_box_query_le_mono_budget (q := 3 * (k + 1) * (Nat.log 2 n + 2) * (tarski_box_query_le_polylog_C k * (Nat.log 2 n + 2) ^ k + 1) + 2 ^ (k + 1)) · exact h_rec · set p := Nat.log 2 n + 2 have hp : 2 ≤ p := by dsimp [p]; omega have h1 : 2 ^ (k + 1) ≤ p ^ (k + 1) := Nat.pow_le_pow_left hp (k + 1) have hpk : 1 ≤ p ^ k := Nat.one_le_pow k p (by omega) have h2 : tarski_box_query_le_polylog_C k * p ^ k + 1 ≤ (tarski_box_query_le_polylog_C k + 1) * p ^ k := by calc tarski_box_query_le_polylog_C k * p ^ k + 1 ≤ tarski_box_query_le_polylog_C k * p ^ k + p ^ k := Nat.add_le_add_left hpk _ _ = (tarski_box_query_le_polylog_C k + 1) * p ^ k := by ring have h3 : 3 * (k + 1) * p * (tarski_box_query_le_polylog_C k * p ^ k + 1) ≤ 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * p ^ (k + 1) := by calc 3 * (k + 1) * p * (tarski_box_query_le_polylog_C k * p ^ k + 1) ≤ 3 * (k + 1) * p * ((tarski_box_query_le_polylog_C k + 1) * p ^ k) := by apply Nat.mul_le_mul_left exact h2 _ = 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * (p * p ^ k) := by ring _ = 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * p ^ (k + 1) := by rw [← pow_succ'] calc 3 * (k + 1) * p * (tarski_box_query_le_polylog_C k * p ^ k + 1) + 2 ^ (k + 1) ≤ 3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) * p ^ (k + 1) + p ^ (k + 1) := Nat.add_le_add h3 h1 _ = (3 * (k + 1) * (tarski_box_query_le_polylog_C k + 1) + 1) * p ^ (k + 1) := by ring _ = tarski_box_query_le_polylog_C (k + 1) * p ^ (k + 1) := by rfl/-- The best bound the KB's slice/halving recursion gives, in the box form the open target is stated in: Tarski(n,k) ≤ C·(log₂ n + 2)^k uniformly over sub-boxes. -/theorem tarski_box_query_le_polylog (k : ℕ) : ∃ C : ℕ, ∀ n : ℕ, 1 ≤ n → tarski_box_query_le n k (C * (Nat.log 2 n + 2) ^ k) := ⟨tarski_box_query_le_polylog_C k, tarski_box_query_le_polylog_bound k⟩