AFTD Auto-Formalizing Theoretical Domains

tarski_query_complexity_le_polylog

theoremverified

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 than LinearOrder — 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 LinearOrder is a TotalPreorder.

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.

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

    lines 1–6

    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'⟩⟩
  2. 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).

    lines 8–22

    uses Nat.one_le_pow, Nat.pow_le_pow_left, Nat.pow_succ, Nat.mul_le_mul_left, Nat.add_le_add

    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 hD
  3. 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.

    lines 24–33

    uses tarski_box_query_le_small

    lemma 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
  4. 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.

    lines 34–42

    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)
    
  5. 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.

    lines 44–49

    uses tarski_query_complexity_le_polylog_box, tarski_box_query_le_imp_query_complexity

    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)⟩
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'.

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

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