Theorem 1.5 — an oracle with and
OpenAvgPHETH.Supplement.theorem_1_5average-case-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an efficiently computable function with and . Then there exists an oracle such that and, for all ,
So the bounds of Theorem 1.2 are optimal among relativizing techniques at every level of the polynomial hierarchy. Relative to the polynomial hierarchy does not collapse while . Hence relativizing techniques cannot derive from the non-collapse of PH.
Differences from the source:
- reading: "efficiently computable" (not defined) → IsEfficientlyComputable: is computable from in time ; reason: the construction of §8.1 uses only through ; every standard reading implies this one, so the theorem is at least as strong
- reading: with used in §8.1 → for every ; reason: the parameter on p.39 takes , which presupposes
- encoding: → Tendsto ε atTop (𝓝 0); reason: definition of
- reading: for a bound that need not be time-constructible → SigmaKTime: for all , for some and machine ; reason: this is the characterisation of Definition 4.3 (p.15), which contains the page's class for time-constructible ; a larger class makes the non-inclusion at least as strong
- encoding: and → , DistSubAvgP O d (published) and PiPO O k (complements of the published SigmaPO O k); reason: (§4.1)
- encoding: → ; at the bound is (Lean's ); reason: two input lengths, absorbed by the threshold
Preamble
import Mathlib import Definitions.Def_AvgPHETH_DistSubAvgP import Definitions.Def_AvgPHETH_Supplement_PiPO import Definitions.Def_AvgPHETH_Supplement_SigmaKTime import Definitions.Def_AvgPHETH_Supplement_IsEfficientlyComputable
Formal statement
namespace AvgPHETH.Supplement
open AvgPHETH Filter Topology
/-- **Theorem 1.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.4 (PDF 6)): for every efficiently computable function `ε(n) = o(1)`,
there exists an oracle `O` such that `DistPH^O ⊆ AvgP^O` and, for all `k ≥ 1`,
`Π_k^{p,O} ⊄ Σ_kTIME^O[2^{ε(n)·(n/log^k n)}]`.
**Formalization Note** `DistPH^O ⊆ AvgP^O` is `DistΣ_d^{p,O} ⊆ AvgP^O` for every `d` (published
`AvgPHETH.DistSubAvgP`). `ε(n) > 0` is presupposed by `log(1/ε(n))` in §8.1; "efficiently computable"
is `IsEfficientlyComputable`. `log` is `log₂`; at `n ≤ 1`, `log₂ n = 0` and Lean's `x/0 = 0` makes the
bound `1` at those two lengths, which `SigmaKTime`'s threshold `⌈c·t⌉₊ + c` absorbs. The one oracle
`O` works for every `k`. -/
theorem theorem_1_5 (ε : ℕ → ℝ) (hpos : ∀ n, 0 < ε n) (hlim : Tendsto ε atTop (𝓝 0))
(hε : IsEfficientlyComputable ε) :
∃ O : Set (List Bool), (∀ d, DistSubAvgP O d) ∧
∀ k, 1 ≤ k → ∃ L ∈ PiPO O k,
L ∉ SigmaKTime O k (fun n => (2 : ℝ) ^ (ε n * ((n : ℝ) / Real.logb 2 n ^ k))) := by sorry
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…), Theorem 1.5, p.4 (PDF 6); §8, pp.38–39 (PDF 40–41)