SubmodQueryTree
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)