AFTD Auto-Formalizing Theoretical Domains

RandomizedSubmodTester

structure

A randomized tester making at most q queries, modeled as a finite probability distribution over deterministic decision trees of depth at most q.

Statement

structure RandomizedSubmodTester (n k q : ℕ)
Defined in
arXiv:2611.02374, Def. 2.5
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • SubmodQueryTreeAn adaptive deterministic query decision tree of depth at most d for testing functions on the Boolean hypercube into {0, ..., k}.
Used by 1

Read back from the Lean

RandomizedSubmodTester n k q is a structure parameterized by natural numbers n, k, and q. An instance consists of: 1. m : ℕ, a natural number specifying the size of the support; 2. prob : Fin m → ℝ, a probability assigned to each index in Fin m; 3. prob_nonneg : ∀ i : Fin m, 0 ≤ prob i, asserting that every probability is non-negative; 4. prob_sum : ∑ i : Fin m, prob i = 1, asserting that the sum of the probabilities over Fin m equals 1; 5. tree : Fin m → SubmodQueryTree n k q, associating to each index in Fin m a query tree of depth parameter q.

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 randomized tester of query complexity q, given by a probability distribution over decision trees of depth q. -/
structure RandomizedSubmodTester (n k q : ℕ) where
  m : ℕ
  prob : Fin m → ℝ
  prob_nonneg : ∀ i, 0 ≤ prob i
  prob_sum : ∑ i, prob i = 1
  tree : Fin m → SubmodQueryTree n k q
See it in the graphDiscuss this resultChallenge it