AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_imp_query_complexity

theoremverified

The 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 Bot/Top for general n).

Statement

theorem tarski_box_query_le_imp_query_complexity (n k q : ℕ) (hn : 1 ≤ n)
    (h : tarski_box_query_le n k q) : tarski_query_complexity_le n k q
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
Quot.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…
  • 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 than LinearOrder — it does NOT require antisymmetry or…
  • 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)…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
  • 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…
Used by 1
  • 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 proof reduces ambient query complexity to box-local query complexity by instantiating the box-local hypothesis with the full grid [a, b], where a = (0, ..., 0) and b = (n - 1, ..., n - 1). Because a is the global minimum and b is the global maximum of the grid, any monotone function f automatically satisfies the box-invariance boundary conditions a ≤ f a and f b ≤ b. The query tree guaranteed by the box-local hypothesis for this choice of box therefore finds a fixed point of any monotone function within cost q.

  1. Establish that n ≠ 0 and unfold the definitions of box-local and ambient query complexity.

    Since 1 ≤ n, linear arithmetic (omega) gives n ≠ 0, yielding the NeZero n instance needed to treat 0 as an element of Fin n. We then unfold the definitions of tarski_box_query_le in the hypothesis and tarski_query_complexity_le in the goal to reveal their logical structure.

    lines 4–6

      haveI : NeZero n := ⟨by omega⟩
      unfold tarski_box_query_le at h
      unfold tarski_query_complexity_le
  2. Define the global minimum a and maximum b of the grid (Fin k → Fin n) and prove that a ≤ b.

    We define a as the constantly 0 function and b as the constantly n - 1 function, which are well-defined since 0 < n and n - 1 < n when 1 ≤ n. The inequality a ≤ b holds coordinatewise because a i = 0 ≤ b i by Fin.zero_le.

    lines 7–11

    uses Fin.zero_le

      let a : Fin k → Fin n := fun _ => ⟨0, by omega⟩
      let b : Fin k → Fin n := fun _ => ⟨n - 1, by omega⟩
      have hab : a ≤ b := by
        intro i
        exact Fin.zero_le _
  3. Obtain the query tree t from the box-local hypothesis on [a, b] and propose it as the witness for ambient query complexity.

    Specializing the hypothesis h to the endpoints a and b with the proof that a ≤ b yields a query tree t. We supply t as the candidate tree for the existential goal in tarski_query_complexity_le.

    lines 12–13

      obtain ⟨t, ht⟩ := h a b hab
      refine ⟨t, ?_⟩
  4. For any monotone function f, the lower boundary condition a ≤ f a holds.

    Let f be an arbitrary monotone function. Since a is constantly 0, each coordinate satisfies a i = 0 ≤ (f a) i by Fin.zero_le, so a ≤ f a.

    lines 14–15

    uses Fin.zero_le

      intro f hf
      have hfa : a ≤ f a := fun _ => Fin.zero_le _
  5. For any monotone function f, the upper boundary condition f b ≤ b holds.

    For each coordinate i, Fin.le_def translates the inequality in Fin n to the underlying natural numbers. By Fin.isLt, the natural number representing (f b) i is strictly less than n, which by linear arithmetic (omega) implies (f b) i ≤ n - 1 = b i.

    lines 16–21

    uses Fin.le_def, Fin.isLt

      have hfb : f b ≤ b := by
        intro i
        rw [Fin.le_def]
        have := (f b i).isLt
        show (f b i : ℕ) ≤ n - 1
        omega
  6. The query tree t outputs a fixed point of f within query budget q.

    Feeding f, its monotonicity, and the boundary conditions a ≤ f a and f b ≤ b into the guarantee for t produces the result that running t on f yields a fixed point of f with query cost at most q, closing the goal.

    lines 22–23

      obtain ⟨-, -, hfix, hcost⟩ := ht f hf hfa hfb
      exact ⟨hfix, hcost⟩
Fin.zero_le
Every element of Fin n is greater than or equal to zero.
Fin.le_def
The order on Fin n is defined by the inequality on the underlying natural numbers.
Fin.isLt
The underlying natural number of an element of Fin n is strictly less than n.

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

/-- Box-local invariant on the full grid gives the ambient query-complexity bound. -/theorem tarski_box_query_le_imp_query_complexity (n k q : ℕ) (hn : 1 ≤ n)    (h : tarski_box_query_le n k q) : tarski_query_complexity_le n k q := by  haveI : NeZero n := ⟨by omega⟩  unfold tarski_box_query_le at h  unfold tarski_query_complexity_le  let a : Fin k → Fin n := fun _ => ⟨0, by omega⟩  let b : Fin k → Fin n := fun _ => ⟨n - 1, by omega⟩  have hab : a ≤ b := by    intro i    exact Fin.zero_le _  obtain ⟨t, ht⟩ := h a b hab  refine ⟨t, ?_⟩  intro f hf  have hfa : a ≤ f a := fun _ => Fin.zero_le _  have hfb : f b ≤ b := by    intro i    rw [Fin.le_def]    have := (f b i).isLt    show (f b i : ℕ) ≤ n - 1    omega  obtain ⟨-, -, hfix, hcost⟩ := ht f hf hfa hfb  exact ⟨hfix, hcost⟩
See it in the graphDiscuss this resultChallenge it