AFTD Auto-Formalizing Theoretical Domains

tarski_box_query_le_small

theoremverified

Brute 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 particular tarski_box_query_le n k M holds, so the new definition is inhabited (non-vacuous).

Statement

theorem tarski_box_query_le_small (n k M : ℕ) [NeZero n]
    (hM : ∀ a b : Fin k → Fin n, a ≤ b → (∏ j : Fin k, ((b j : ℕ) - (a j : ℕ) + 1)) ≤ M) :
    tarski_box_query_le n k M
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.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…
  • tarski_subinterval_fixed_pointSubinterval fixed point theorem: if a monotone map f satisfies a ≤ f(a) and f(b) ≤ b, then f has a fixed point in the sub-box [a, b].
  • 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.
  • TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
  • 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…
Used by 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_two_fiveSmall instance at the exact target parameters: in dimension 5 over the two-element grid, every box is solvable with at most 2^5 = 32…
  • 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_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 theorem proves that when every box [a, b] in (Fin n)^k has size at most M, a fixed point of any monotone map f on [a, b] can be found within at most M queries by brute-force search. A query tree is constructed that tests every element of the box in order, halting as soon as it encounters a fixed point. Tarski's fixed point theorem on subintervals guarantees that the box contains at least one fixed point, ensuring the search succeeds. Finally, the query cost is bounded by the number of points in the box, which is the product of coordinate interval lengths and is at most M by assumption.

  1. The query tree for a candidate list L uses at most |L| queries.

    We proceed by induction on the candidate list L. For the empty list, the tree outputs the default point with zero queries. For a non-empty list x :: xs, the tree queries x; if f(x) = x, it halts immediately with cost 1 ≤ |x :: xs|; otherwise, it queries xs, incurring 1 + cost(xs) queries, which is at most 1 + |xs| = |x :: xs| by the induction hypothesis.

    lines 9–16

    uses List.length_cons

      induction L with
      | nil =>
        simp [tarski_box_query_le_small_tree, TarskiQueryTree.cost]
      | cons x xs ih =>
        simp only [tarski_box_query_le_small_tree, TarskiQueryTree.cost, List.length_cons]
        split_ifs with h
        · simp [TarskiQueryTree.cost]
        · omega
  2. An empty candidate list cannot contain a fixed point.

    For the base case of search correctness, assuming there exists a fixed point in L = [] is impossible because the empty list has no elements.

    lines 23–26

      induction L with
      | nil =>
        rcases h with ⟨z, hz, -⟩
        cases hz
  3. If x :: xs contains a fixed point, the search tree terminates at a fixed point in x :: xs.

    If f(x) = x, the tree returns x, which is a fixed point in x :: xs. If f(x) ≠ x, the fixed point guaranteed to exist in x :: xs cannot be x, so it must lie in xs. By the induction hypothesis, running the search on xs finds a fixed point in xs, which also belongs to x :: xs via List.mem_cons_of_mem.

    lines 27–36

    uses List.mem_cons, False.elim, List.mem_cons_of_mem

      | cons x xs ih =>
        simp only [tarski_box_query_le_small_tree, TarskiQueryTree.run]
        split_ifs with hfx
        · simp [TarskiQueryTree.run, hfx]
        · rcases h with ⟨z, hz, hfz⟩
          simp only [List.mem_cons] at hz
          rcases hz with rfl | hz
          · exact False.elim (hfx hfz)
          · have ⟨h1, h2⟩ := ih ⟨z, hz, hfz⟩
            exact ⟨List.mem_cons_of_mem x h1, h2⟩
  4. For any box [a, b], the search strategy is defined by querying all its points in list order.

    Given subinterval endpoints a ≤ b, we instantiate the existential query tree with the linear search tree over the list of points in [a, b] ((Finset.Icc a b).toList), with fallback point a. We then take any monotone map f satisfying a ≤ f(a) and f(b) ≤ b.

    lines 42–44

      intro a b hab
      use tarski_box_query_le_small_tree a (Finset.Icc a b).toList
      intro f hf ha hb
  5. The box [a, b] contains at least one fixed point of f.

    By Tarski's fixed point theorem on subintervals (tarski_subinterval_fixed_point), there is a point x such that a ≤ x ≤ b and f(x) = x. Therefore x belongs to the closed interval Finset.Icc a b and thus to its list representation.

    lines 45–49

    uses tarski_subinterval_fixed_point, Finset.mem_toList, Finset.mem_Icc

      have h_fp := tarski_subinterval_fixed_point n k f hf a b hab ha hb
      rcases h_fp with ⟨x, hax, hxb, hfx⟩
      have hx_mem : x ∈ (Finset.Icc a b).toList := by
        rw [Finset.mem_toList, Finset.mem_Icc]
        exact ⟨hax, hxb⟩
  6. The query tree outputs a fixed point of f lying in the box [a, b].

    Applying the correctness lemma tarski_box_query_le_small_run_mem_and_fixed with witness x shows that the output of the query tree is in (Finset.Icc a b).toList and is a fixed point of f. Hence the output lies in Finset.Icc a b, satisfying a ≤ output ≤ b.

    lines 50–55

    uses tarski_box_query_le_small_run_mem_and_fixed, Finset.mem_toList, Finset.mem_Icc

      have h_run := tarski_box_query_le_small_run_mem_and_fixed a (Finset.Icc a b).toList f ⟨x, hx_mem, hfx⟩
      have h_mem_box : TarskiQueryTree.run f (tarski_box_query_le_small_tree a (Finset.Icc a b).toList) ∈ Finset.Icc a b := by
        rw [← Finset.mem_toList]
        exact h_run.1
      rw [Finset.mem_Icc] at h_mem_box
      refine ⟨h_mem_box.1, h_mem_box.2, h_run.2, ?_⟩
  7. The query cost of the tree is at most M, completing the proof.

    By tarski_box_query_le_small_cost_le, the query cost is bounded by the length of the list, which equals the cardinality of [a, b] (Finset.length_toList). By Pi.card_Icc, the size of [a, b] in the product order is the product over coordinates of the 1D interval sizes, each of which is (b j - a j + 1) by Fin.card_Icc. By assumption hM, this product is at most M, so transitivity (le_trans) ensures the query cost is at most M.

    lines 56–67

    uses tarski_box_query_le_small_cost_le, Finset.length_toList, Pi.card_Icc, Fin.card_Icc, le_trans

      have h_cost := tarski_box_query_le_small_cost_le a (Finset.Icc a b).toList f
      rw [Finset.length_toList] at h_cost
      have h_card_le : (Finset.Icc a b).card ≤ M := by
        rw [Pi.card_Icc]
        have h1 : ∀ j, (Finset.Icc (a j) (b j)).card = (b j : ℕ) - (a j : ℕ) + 1 := by
          intro j
          rw [Fin.card_Icc]
          have : a j ≤ b j := hab j
          omega
        simp_rw [h1]
        exact hM a b hab
      exact le_trans h_cost h_card_le
List.length_cons
Prepending an element to a list increases its length by one: `(a :: as).length = as.length + 1`.
List.mem_cons
An element belongs to `b :: l` if and only if it equals `b` or belongs to `l`.
False.elim
From a contradiction (`False`), any statement follows (ex falso quodlibet).
List.mem_cons_of_mem
If an element belongs to `l`, it also belongs to `y :: l`.
tarski_subinterval_fixed_point
Any monotone function on a subinterval `[a, b]` that maps `a ≤ f(a)` and `f(b) ≤ b` has a fixed point in `[a, b]`.
Finset.mem_toList
An element is in `s.toList` if and only if it belongs to the finite set `s`.
Finset.mem_Icc
An element `x` belongs to the closed interval `Finset.Icc a b` if and only if `a ≤ x ≤ b`.
tarski_box_query_le_small_run_mem_and_fixed
If a candidate list `L` contains a fixed point of `f`, the linear-search query tree on `L` terminates at a fixed point in `L`.
tarski_box_query_le_small_cost_le
The query cost of the linear-search tree on candidate list `L` is at most the length of `L`.
Finset.length_toList
The length of the list of elements of a finite set equals the set's cardinality.
Pi.card_Icc
The cardinality of a box (product interval) in a product order is the product of the cardinalities of its coordinate intervals.
Fin.card_Icc
The cardinality of a closed interval `[a, b]` in `Fin n` is `b + 1 - a`.
le_trans
The inequality relation `≤` is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`.

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

def tarski_box_query_le_small_tree {n k : ℕ} (x₀ : Fin k → Fin n) :    List (Fin k → Fin n) → TarskiQueryTree n k  | [] => .output x₀  | x :: xs => .query x (fun fx => if fx = x then .output x else tarski_box_query_le_small_tree x₀ xs)theorem tarski_box_query_le_small_cost_le {n k : ℕ} (x₀ : Fin k → Fin n) (L : List (Fin k → Fin n))    (f : (Fin k → Fin n) → Fin k → Fin n) :    TarskiQueryTree.cost f (tarski_box_query_le_small_tree x₀ L) ≤ L.length := by  induction L with  | nil =>    simp [tarski_box_query_le_small_tree, TarskiQueryTree.cost]  | cons x xs ih =>    simp only [tarski_box_query_le_small_tree, TarskiQueryTree.cost, List.length_cons]    split_ifs with h    · simp [TarskiQueryTree.cost]    · omegatheorem tarski_box_query_le_small_run_mem_and_fixed {n k : ℕ} (x₀ : Fin k → Fin n) (L : List (Fin k → Fin n))    (f : (Fin k → Fin n) → Fin k → Fin n) (h : ∃ z ∈ L, f z = z) :    TarskiQueryTree.run f (tarski_box_query_le_small_tree x₀ L) ∈ L ∧    f (TarskiQueryTree.run f (tarski_box_query_le_small_tree x₀ L)) =      TarskiQueryTree.run f (tarski_box_query_le_small_tree x₀ L) := by  induction L with  | nil =>    rcases h with ⟨z, hz, -⟩    cases hz  | cons x xs ih =>    simp only [tarski_box_query_le_small_tree, TarskiQueryTree.run]    split_ifs with hfx    · simp [TarskiQueryTree.run, hfx]    · rcases h with ⟨z, hz, hfz⟩      simp only [List.mem_cons] at hz      rcases hz with rfl | hz      · exact False.elim (hfx hfz)      · have ⟨h1, h2⟩ := ih ⟨z, hz, hfz⟩        exact ⟨List.mem_cons_of_mem x h1, h2⟩/-- Boxes small enough to enumerate are solved by querying all their points. -/theorem tarski_box_query_le_small (n k M : ℕ) [NeZero n]    (hM : ∀ a b : Fin k → Fin n, a ≤ b → (∏ j : Fin k, ((b j : ℕ) - (a j : ℕ) + 1)) ≤ M) :    tarski_box_query_le n k M := by  intro a b hab  use tarski_box_query_le_small_tree a (Finset.Icc a b).toList  intro f hf ha hb  have h_fp := tarski_subinterval_fixed_point n k f hf a b hab ha hb  rcases h_fp with ⟨x, hax, hxb, hfx⟩  have hx_mem : x ∈ (Finset.Icc a b).toList := by    rw [Finset.mem_toList, Finset.mem_Icc]    exact ⟨hax, hxb⟩  have h_run := tarski_box_query_le_small_run_mem_and_fixed a (Finset.Icc a b).toList f ⟨x, hx_mem, hfx⟩  have h_mem_box : TarskiQueryTree.run f (tarski_box_query_le_small_tree a (Finset.Icc a b).toList) ∈ Finset.Icc a b := by    rw [← Finset.mem_toList]    exact h_run.1  rw [Finset.mem_Icc] at h_mem_box  refine ⟨h_mem_box.1, h_mem_box.2, h_run.2, ?_⟩  have h_cost := tarski_box_query_le_small_cost_le a (Finset.Icc a b).toList f  rw [Finset.length_toList] at h_cost  have h_card_le : (Finset.Icc a b).card ≤ M := by    rw [Pi.card_Icc]    have h1 : ∀ j, (Finset.Icc (a j) (b j)).card = (b j : ℕ) - (a j : ℕ) + 1 := by      intro j      rw [Fin.card_Icc]      have : a j ≤ b j := hab j      omega    simp_rw [h1]    exact hM a b hab  exact le_trans h_cost h_card_le
See it in the graphDiscuss this resultChallenge it