AFTD Auto-Formalizing Theoretical Domains

SubmodQueryTree

inductive

An adaptive deterministic query decision tree of depth at most d for testing functions on the Boolean hypercube into {0, ..., k}.

Statement

inductive SubmodQueryTree (n k : ℕ) : ℕ → Type
Defined in
arXiv:2611.02374, Def. 2.5
Verified
06 Nov 2026
Axioms
none listed
Used by 2
  • RandomizedSubmodTesterA randomized tester making at most q queries, modeled as a finite probability distribution over deterministic decision trees of depth at…
  • submod_query_tree_evalEvaluates a query decision tree on a function f by querying coordinates along the tree path until reaching a leaf.

Read back from the Lean

An inductive type family SubmodQueryTree (n k : ℕ) : ℕ → Type representing a decision/query tree with depth bound d : ℕ, queries in Fin n → Bool, and $(k + 1)$-ary branching: - leaf: takes a boolean accept : Bool and an implicit d : ℕ, returning a SubmodQueryTree n k d. Because d is arbitrary, a leaf can be formed at any depth level. - query: takes an implicit d : ℕ, a query point x : Fin n → Bool, and a child-tree assignment next : Fin (k + 1) → SubmodQueryTree n k d, returning a SubmodQueryTree n k (d + 1).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A deterministic query decision tree of depth at most d for testing functions on the Boolean hypercube. -/
inductive SubmodQueryTree (n k : ℕ) : ℕ → Type where
  | leaf (accept : Bool) {d : ℕ} : SubmodQueryTree n k d
  | query {d : ℕ} (x : Fin n → Bool) (next : Fin (k + 1) → SubmodQueryTree n k d) :
      SubmodQueryTree n k (d + 1)
See it in the graphDiscuss this resultChallenge it