AFTD Auto-Formalizing Theoretical Domains

tarski_query_tree_slice_lift_spec

theoremverified

Run/cost law for the slice lift: in dimension k+1, the lifted tree computes insertNth i c of the slice algorithm's output (run against the sliced map y ↦ f (insertNth i c y) ∘ succAbove i), and it costs exactly what the slice algorithm costs.

Statement

theorem tarski_query_tree_slice_lift_spec {n k : ℕ} (i : Fin (k+1)) (c : Fin n)
    (f : (Fin (k+1) → Fin n) → Fin (k+1) → Fin n) (t : TarskiQueryTree n k) :
    TarskiQueryTree.run f (tarski_query_tree_slice_lift i c t) =
      Fin.insertNth i c (TarskiQueryTree.run (fun y j => f (Fin.insertNth i c y) (i.succAbove j)) t) ∧
    TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c t) =
      TarskiQueryTree.cost (fun y j => f (Fin.insertNth i c y) (i.succAbove j)) t
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
propext
Built on 4
  • tarski_query_tree_slice_liftSlice lifting of a query tree one dimension up: replace every query y in dimension k by the query (insertNth i c y) in dimension k+1, and…
  • 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…
  • TarskiQueryTree.runThe point a query tree outputs when the black box is f.
Used by 1
  • 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…

The proof, explained

The proof proceeds by structural induction on the query tree $t$. For an output leaf, both the lifted tree and the sliced execution immediately return the corresponding vector with query cost $0$. For a query node, performing the initial query evaluates the oracle at the lifted point, which matches the sliced oracle query on the original point; specializing the induction hypothesis to the oracle's response then equates both the resulting outputs and the incremented query costs.

  1. The specification holds for leaf nodes $\operatorname{output}(x)$.

    We proceed by structural induction on the tree $t$. When $t = \operatorname{output}(x)$, no queries are made and the tree immediately returns $x$. Lifting it produces $\operatorname{output}(\operatorname{insertNth}(i, c, x))$, which returns $\operatorname{insertNth}(i, c, x)$ with cost $0$. Similarly, running the sliced oracle on the original leaf returns $x$ with cost $0$, and inserting $c$ at index $i$ gives $\operatorname{insertNth}(i, c, x)$ with cost $0$. Simplifying with the definitions of `tarski_query_tree_slice_lift`, `TarskiQueryTree.run`, and `TarskiQueryTree.cost` verifies both equalities directly.

    lines 8–10

    uses tarski_query_tree_slice_lift, TarskiQueryTree.run, TarskiQueryTree.cost

      induction t with
      | output x =>
        simp [tarski_query_tree_slice_lift, TarskiQueryTree.run, TarskiQueryTree.cost]
  2. For a query node $\operatorname{query}(x, \operatorname{next})$, executing the initial query reduces the run and cost equalities to those of the continuation sub-tree, with each cost incremented by $1$.

    Unfolding the definitions of `tarski_query_tree_slice_lift`, `TarskiQueryTree.run`, and `TarskiQueryTree.cost` evaluates the leading query. The lifted tree queries $f$ at $\operatorname{insertNth}(i, c, x)$, strips coordinate $i$ from the answer, and passes the remaining vector to the continuation. This matches querying the sliced oracle at $x$, advancing both sides to the continuation $\operatorname{next}(j \mapsto f(\operatorname{insertNth}(i, c, x))(i.\operatorname{succAbove}(j)))$ and adding $1$ to each cost.

    lines 11–12

    uses tarski_query_tree_slice_lift, TarskiQueryTree.run, TarskiQueryTree.cost

      | query x next ih =>
        simp only [tarski_query_tree_slice_lift, TarskiQueryTree.run, TarskiQueryTree.cost]
  3. The induction hypothesis on the continuation sub-tree completes the query case, establishing the specification for all trees.

    We instantiate the induction hypothesis `ih` at the response vector $a = j \mapsto f(\operatorname{insertNth}(i, c, x))(i.\operatorname{succAbove}(j))$. This yields both the equality of output vectors (`this.1`) and the equality of query costs (`this.2`) for the continuation. Applying `congrArg (· + 1)` to the cost equality matches the incremented query counts, completing the inductive step.

    lines 13–14

    uses congrArg

        have := ih (fun j => f (i.insertNth c x) (i.succAbove j))
        exact ⟨this.1, congrArg (· + 1) this.2⟩
congrArg
Applying a function to equal arguments yields equal results ($a_1 = a_2 \implies f(a_1) = f(a_2)$).
TarskiQueryTree.cost
Counts the total number of oracle queries made when executing a query tree against an oracle function.
TarskiQueryTree.run
Executes a query tree against an oracle function, returning the tree's final output vector.
tarski_query_tree_slice_lift
Lifts a $k$-dimensional query tree to dimension $k+1$ by inserting a fixed coordinate value $c$ at index $i$ into all queried points and output vectors.

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

/-- Run and cost of a slice lift. -/theorem tarski_query_tree_slice_lift_spec {n k : ℕ} (i : Fin (k+1)) (c : Fin n)    (f : (Fin (k+1) → Fin n) → Fin (k+1) → Fin n) (t : TarskiQueryTree n k) :    TarskiQueryTree.run f (tarski_query_tree_slice_lift i c t) =      Fin.insertNth i c (TarskiQueryTree.run (fun y j => f (Fin.insertNth i c y) (i.succAbove j)) t) ∧    TarskiQueryTree.cost f (tarski_query_tree_slice_lift i c t) =      TarskiQueryTree.cost (fun y j => f (Fin.insertNth i c y) (i.succAbove j)) t := by  induction t with  | output x =>    simp [tarski_query_tree_slice_lift, TarskiQueryTree.run, TarskiQueryTree.cost]  | query x next ih =>    simp only [tarski_query_tree_slice_lift, TarskiQueryTree.run, TarskiQueryTree.cost]    have := ih (fun j => f (i.insertNth c x) (i.succAbove j))    exact ⟨this.1, congrArg (· + 1) this.2⟩
See it in the graphDiscuss this resultChallenge it