Theorem 8.5 — with probability one, for the random oracle of §8.1
OpenAvgPHETH.Supplement.theorem_8_5Let be an efficiently computable function with and , and let be the random oracle built from by the staged construction of Section 8.1: in each stage, random restrictions of the construction variables (root bits and selectors of the selector trees), then the assignment of the help oracle on the queries of that stage, then the completion of the groups that are due, with a diagonalization step on the reserved groups. Then, with probability one,
The help oracle answers a query about an alternating computation only once the answer no longer depends on the undetermined part of ; the theorem says that this is enough to solve every distributional problem of the polynomial hierarchy in average polynomial time relative to . Together with Theorem 8.7 it yields the relativization barrier of Theorem 1.5.
Formalization Note The oracle is a function of the construction data (the function , a numbering of machines, the enumeration of triples, a selection rule, the reserved lengths) and of independent uniform seeds; the statement is for all admissible data and seeds, and "with probability one" is "for almost every ".
Differences from the source:
- reading: the oracle of the construction of §8.1, whose enumeration , reserved lengths and lexicographic order are left to be chosen → for every choice: every enumeration of all triples with each appearing infinitely often, every sequence satisfying (a)–(d), every rule selecting one of the disagreeing pairs in step 3(b)iii; reason: the page fixes none of them; the statement is asserted for each admissible choice, which includes the page's
- reading: "an enumeration of all triples " and codes of machines → a numbering of oracle machines in which every machine occurs up to its acceptance behaviour (same accepting runs for every oracle, clock and input); and ; the statement holds for every such numbering; reason: the published machine model has arbitrary alphabet and state types, so its machines form a proper class and have no enumeration; the construction and both proofs use a machine only through its accepting runs
- reading: "efficiently computable", , " without loss of generality" (§8.1, p.38) → for all ; ; computable from in time ; for every , for all large ; reason: §8.1 fixes with these properties for the whole section; positivity is presupposed by ; the construction uses only through
- encoding: "with probability one" over the random restrictions of the construction → for almost every , for any family of independent seeds uniform on , one per stage, variable and channel, on any probability space; a restriction round is a deterministic function of its seeds and the current assignment (priorities choose the surviving subset, the other seeds the values); reason: conditionally on the earlier rounds this is the -random restriction of Definition 4.4, independently for each family, group and stage
- encoding: "an appropriate encoding" of -queries, an unspecified encoding of -queries and of the answer , and → -query ↦ binary tuple code of ; -query ↦ tuple code of , with iff and iff ; is the published join; reason: linear-time decodable encodings with valid -queries of length , as the page requires; they change no class
- encoding: oracle bits not yet fixed when (step 2(a)) and (step 3(b)) are formed → unassigned -queries are answered , unassigned variables of other groups get the empty string; reason: Proposition 8.3 shows these bits are never read within the clock, so the default changes nothing
- encoding: "lexicographically first possible value" / "lexicographically first valid assignment" → every unset variable of the group gets the all-zeros string of its alphabet; reason: the first element of in lexicographic order
- encoding: → , DistSubAvgP O d (published); reason: (§4.1)
import Mathlib import Definitions.Def_AvgPHETH_Supplement_OracleData_oracle import Definitions.Def_AvgPHETH_Supplement_OracleData_Admissible import Definitions.Def_AvgPHETH_DistSubAvgP
namespace AvgPHETH.Supplement
open AvgPHETH MeasureTheory
/-- **Theorem 8.5** (Hirahara–Juvekar–Nanashima, *Average-Case Hardness of PH from ETH-Type Hypotheses*, manuscript of November 3, 2026 (STOC 2027 submission; held version sha256 ea5fd472…), p.44 (PDF 46)): "With probability one, `DistPH^O ⊆ AvgP^O`",
where `O = A + V` is the random oracle of the construction of §8.1 (pp.38–41, PDF 40–43).
**Formalization Note** The oracle is `D.oracle`, a function of the data `D` of the construction and of
the seeds of its restriction rounds; the statement is for all data and seeds satisfying
`OracleData.Admissible` (the function `ε` of Section 8, a numbering of all machines, an enumeration of
all triples, a selection rule, independent uniform seeds, reserved lengths `n_s` with (a)–(d)). "With
probability one" is `∀ᵐ ω ∂μ`. `DistPH^O ⊆ AvgP^O` is `DistΣ_d^{p,O} ⊆ AvgP^O` for every `d` (the
published `AvgPHETH.DistSubAvgP`). -/
theorem theorem_8_5 (D : OracleData) {Ω : Type} [MeasurableSpace Ω] (μ : MeasureTheory.Measure Ω)
[MeasureTheory.IsProbabilityMeasure μ] (U : ℕ × CVar × ℕ → Ω → ℝ) (hD : D.Admissible μ U) :
∀ᵐ ω ∂μ, ∀ d : ℕ, DistSubAvgP (D.oracle (fun i v c => U (i, v, c) ω)) d := by sorry
end AvgPHETH.Supplement