AFTD Auto-Formalizing Theoretical Domains

tarski_query_tree_bind_spec

theoremverified

Run/cost law for sequential composition: the run of a bind is the run of the continuation g at the output of the first tree, and the cost of a bind is the cost of the first tree plus the cost of the continuation at that output.

Statement

theorem tarski_query_tree_bind_spec {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k)
    (f : (Fin k → Fin n) → Fin k → Fin n) (t : TarskiQueryTree n k) :
    TarskiQueryTree.run f (tarski_query_tree_bind g t) =
      TarskiQueryTree.run f (g (TarskiQueryTree.run f t)) ∧
    TarskiQueryTree.cost f (tarski_query_tree_bind g t) =
      TarskiQueryTree.cost f t +
        TarskiQueryTree.cost f (g (TarskiQueryTree.run f t))
Source
step towards tarski_query_complexity_five_le_log_sq
Verified
18 Oct 2026
Axioms
Quot.soundpropext
Built on 4
  • tarski_query_tree_bindSequential composition of query trees: run the tree, then feed its output point into the continuation g to obtain the tree that is…
  • 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.
  • TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
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 theorem is proved by structural induction on the query tree t. For a leaf node output x, sequential composition evaluates directly to g x, whose cost is 0 + cost f (g x). For a query node query x k', running the tree queries the oracle f at x and continues along the subtree k' (f x); applying the induction hypothesis to this response establishes the run identity immediately and reduces the cost identity to the linear arithmetic identity (c + d) + 1 = (c + 1) + d.

  1. By structural induction on t, both identities hold for leaf nodes t = output x.

    We induct on the structure of the tree t. In the base case, t = output x represents a leaf with output value x. By definition of sequential composition, tarski_query_tree_bind g (output x) = g x, and by definition of running a tree, run f (output x) = x. Thus the run of the composed tree is run f (g x), which matches run f (g (run f (output x))) definitionally. For the query cost, a leaf node performs zero queries, so cost f (output x) = 0. The cost of the composed tree is cost f (g x), while the right-hand sum is 0 + cost f (g x); these are equal by Nat.zero_add.

    lines 9–10

    uses Nat.zero_add

      induction t with
      | output x => exact ⟨rfl, (Nat.zero_add _).symm⟩
  2. For query nodes t = query x k', the run identity holds by the induction hypothesis on the queried subtree.

    In the inductive step, the tree queries the oracle f at input x, receives the response f x, and continues along the subtree k' (f x). The induction hypothesis states that both identities hold for every subtree k' a. Specializing the induction hypothesis to the oracle's actual response a = f x, its first component establishes that run f (tarski_query_tree_bind g (k' (f x))) = run f (g (run f (k' (f x)))). Since executing a query node definitionally evaluates to running its continuation at f x, this immediately settles the run identity for the query node, leaving only the cost equation to verify.

    lines 11–12

      | query x k' ih =>
        refine ⟨(ih (f x)).1, ?_⟩
  3. For query nodes t = query x k', the cost identity also holds, completing the induction.

    The cost of executing a query node is defined as 1 plus the cost of running the continuation subtree on the oracle response f x. Unfolding this definition rephrases the goal into an explicit arithmetic statement: the cost of the composed subtree plus 1 equals the subtree cost plus 1 plus the continuation cost. Rewriting with the second component of the induction hypothesis at f x substitutes the cost of the composed subtree with the sum of the subtree cost and the continuation cost. The resulting equation has the form (c + d) + 1 = (c + 1) + d, where c is the subtree cost and d is the continuation cost; this is closed by linear arithmetic over ℕ (omega).

    lines 13–17

        show TarskiQueryTree.cost f (tarski_query_tree_bind g (k' (f x))) + 1 =
          (TarskiQueryTree.cost f (k' (f x)) + 1) +
            TarskiQueryTree.cost f (g (TarskiQueryTree.run f (k' (f x))))
        rw [(ih (f x)).2]
        omega
Nat.zero_add
For any natural number n, 0 + n = 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

/-- Run and cost of a sequential composition. -/theorem tarski_query_tree_bind_spec {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k)    (f : (Fin k → Fin n) → Fin k → Fin n) (t : TarskiQueryTree n k) :    TarskiQueryTree.run f (tarski_query_tree_bind g t) =      TarskiQueryTree.run f (g (TarskiQueryTree.run f t)) ∧    TarskiQueryTree.cost f (tarski_query_tree_bind g t) =      TarskiQueryTree.cost f t +        TarskiQueryTree.cost f (g (TarskiQueryTree.run f t)) := by  induction t with  | output x => exact ⟨rfl, (Nat.zero_add _).symm⟩  | query x k' ih =>    refine ⟨(ih (f x)).1, ?_⟩    show TarskiQueryTree.cost f (tarski_query_tree_bind g (k' (f x))) + 1 =      (TarskiQueryTree.cost f (k' (f x)) + 1) +        TarskiQueryTree.cost f (g (TarskiQueryTree.run f (k' (f x))))    rw [(ih (f x)).2]    omega
See it in the graphDiscuss this resultChallenge it