Which names are construction variables
DefinitionAvgPHETH_Supplement_CVar_IsValidaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
A name is a construction variable of the oracle construction if is active and it is either the root bit , or the selector of an internal node with and for every (for this is the root selector ).
The variables with a given and form the group .
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_CVar
import Definitions.Def_AvgPHETH_Supplement_IsActive
import Definitions.Def_AvgPHETH_Supplement_aPar
namespace AvgPHETH.Supplement
/-- The name `v` is a construction variable: `(k, |x|)` is active and `v` is either the root bit
`B^k_x`, or the selector of an internal node `(y₁, …, y_j)`, `0 ≤ j < k`, `y_i ∈ Y_i(|x|) = {0,1}^{a_i(|x|)}`
(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, "Construction variables", p.39 (PDF 41)). -/
def CVar.IsValid (ε : ℕ → ℝ) (v : CVar) : Prop :=
IsActive ε v.k v.x.length ∧
if v.isBit = true then v.path = []
else v.path.length < v.k ∧
∀ (i : ℕ) (h : i < v.path.length), (v.path[i]).length = aPar ε (i + 1) v.x.length
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, "Construction variables", p.39 (PDF 41)