AFTD Auto-Formalizing Theoretical Domains

tarski_query_tree_slice_lift

def

Slice 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 every returned answer v by its restriction (removeNth i v) to the other coordinates.

Statement

def tarski_query_tree_slice_lift {n k : ℕ} (i : Fin (k+1)) (c : Fin n) :
    TarskiQueryTree n k → TarskiQueryTree n (k+1)
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
none listed
Built on 1
  • 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 2
  • 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_tree_slice_lift_specRun/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…

Lean source view module on GitHub

/-- Lift a dimension-k query tree to dimension k+1 by holding coordinate i at c. -/
def tarski_query_tree_slice_lift {n k : ℕ} (i : Fin (k+1)) (c : Fin n) :
    TarskiQueryTree n k → TarskiQueryTree n (k+1) := fun _t => match _t with
  | .output x => .output (Fin.insertNth i c x)
  | .query x k' => .query (Fin.insertNth i c x)
      (fun v => tarski_query_tree_slice_lift i c (k' (Fin.removeNth i v)))
See it in the graphDiscuss this resultChallenge it