tarski_query_tree_slice_lift_spec
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.
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.
uses
tarski_query_tree_slice_lift,TarskiQueryTree.run,TarskiQueryTree.costinduction t with | output x => simp [tarski_query_tree_slice_lift, TarskiQueryTree.run, TarskiQueryTree.cost]
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.
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]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.
uses
congrArghave := 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.
- The simplification in line 12 relies on the fact that removing the $i$-th coordinate via `Fin.removeNth i (f (Fin.insertNth i c x))` is definitionally equal to composing with `succAbove i`, namely `fun j => f (Fin.insertNth i c x) (i.succAbove j)`, allowing the instantiated induction hypothesis to match the continuation directly.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩