The index length
DefinitionAvgPHETH_Supplement_aParaverage-case-complexitycomplexity-theoryoracle-constructionp2o-gran-per-chapterp2o-plan-paperp2o-v1
For ,
A node at depth of a selector tree for an input of length has its children indexed by , so the tree has arity at level .
Formalization Note The paper defines for active and ; the same formula is used here for all . For one has , so the division is not degenerate where the construction uses it.
Definition code
import Mathlib
import Definitions.Def_AvgPHETH_Supplement_RPar
namespace AvgPHETH.Supplement
/-- The length parameter `a_j(n) = ⌊n / R(n)^j⌋`; `Y_j(n) = {0,1}^{a_j(n)}` is the set of child
indices of a node at depth `j − 1` of a selector tree
(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, "Parameters", items 1–2, p.39 (PDF 41)).
**Formalization Note** The page defines `a_j(n)` for active `(k, n)` and `1 ≤ j ≤ k`; this is the same
formula for all `j, n` (Theorem 8.7 uses `a_k(n)` as a function of `n`, and only large `n` matter).
For `n ≥ 16`, `R(n) ≥ 64 > 0`, so the division is not degenerate where the construction uses it. -/
noncomputable def aPar (ε : ℕ → ℝ) (j n : ℕ) : ℕ := ⌊(n : ℝ) / RPar ε n ^ j⌋₊
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, "Parameters", p.39 (PDF 41), items 1–2