AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_polylog

theoremverified

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

  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.

    line 8

      induction' k with k ih
  2. The 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.

    lines 9–11

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

    lines 12–16

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

    lines 17–24

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

    lines 25–32

    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']
  6. 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.

    lines 33–37

    uses Nat.add_le_add, tarski_box_query_le_polylog_C

          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
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

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