A complete subtree with arity and all selectors unset
DefinitionAvgPHETH_Supplement_HasUnsetSubtreeaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For a partial assignment and a selector tree , , a complete subtree with arity is a subtree rooted at the root of with arity at each level. This definition says that below a given node there is such a subtree, of a given number of levels, all of whose selectors are unset: the selector of the node is unset and of its children satisfy the condition again.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_CVar
import Definitions.Def_AvgPHETH_Supplement_aPar
namespace AvgPHETH.Supplement
/-- Below the node `path` of the selector tree `T^k_x` there is a complete subtree with arity
`2^{a_k(|x|)}` at each of its `r` levels, all of whose selectors are unset in `ρ`
(Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §8.1, p.40 (PDF 42): "`T^k_x` has a complete subtree with arity `2^{a_k(n)}`
which has all selectors unset. Here, by a 'complete subtree with arity `2^{a_k(n)}`' we mean a subtree
rooted at the root of `T^k_x` with arity `2^{a_k(n)}` at each level").
**Formalization Note** `r` is the number of levels below `path`; with `r = k` and `path = []` this is the
page's condition on `T^k_x`. The selector of `path` is unset and `2^{a_k(|x|)}` of its children (strings
of `Y_{j+1}(|x|)`, `j` the depth of `path`) again satisfy the condition; leaves carry no selector. -/
def HasUnsetSubtree (ε : ℕ → ℝ) (ρ : CVar → Option (List Bool)) (k : ℕ) (x : List Bool) :
ℕ → List (List Bool) → Prop
| 0, _ => True
| r + 1, path =>
ρ ⟨k, x, false, path⟩ = none ∧
∃ C : Finset (List Bool), C.card = 2 ^ aPar ε k x.length ∧
∀ y ∈ C, y.length = aPar ε (path.length + 1) x.length ∧
HasUnsetSubtree ε ρ k x r (path ++ [y])
end AvgPHETH.Supplement
Source
Hirahara–Juvekar–Nanashima, Average-Case Hardness of PH from ETH-Type Hypotheses, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), §8.1, "The construction", p.40 (PDF 42)