Theorem 7.1 — enhanced depth hierarchy theorem: agreement on critical assignments
OpenAvgPHETH.Supplement.theorem_7_1circuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every there exist and a family of AND-rooted layered alternating formulas of depth on input bits such that the following holds for every :
- all internal fan-ins of are at most ;
- for every , no OR-rooted alternating circuit with depth , bottom width at most , and at most gates above the bottom layer agrees with on all critical assignments. That is, some critical assignment of has .
The lower bound holds against circuits that are only required to agree with the hard formula on its critical assignments. This is what lets the formulas be embedded into the selector trees of the oracle construction in Section 8.
Differences from the source:
- reading: for every → for every ; reason: an AND-rooted formula has a root gate, so its depth is at least ; the paper's starts at (Section 8 restates "for all " as "for all "), and the proof's induction starts at
- encoding: on input bits → has variables for one polynomial and every ; the circuit is over the same variables; reason: the usual meaning of
- encoding: a gate's inputs, with repeated use allowed → a nonempty set of vertices of the previous layer; reason: a repeated wire changes neither an AND nor an OR gate, and removing it increases no fan-in or count; fan-in starts at one on p.16
- reading: → natural with ; reason: bounds a bottom width (a fan-in) and is an integer throughout §7 (the induction applies the projection switching lemma with width ); for natural the two conditions coincide
- reading: layered alternating formula (leaves labelled by literals or constants) → every gate of has at least one child (Formula.IsLayeredAlt); reason: leaves are the literal/constant nodes, so a childless gate would end a root-to-leaf path at a gate; the condition only restricts the family the theorem asserts to exist, so the Lean statement is at least as strong
Preamble
import Mathlib import Definitions.Def_AvgPHETH_Supplement_Formula_IsLayeredAlt import Definitions.Def_AvgPHETH_Supplement_Formula_FanInLe import Definitions.Def_AvgPHETH_Supplement_Formula_IsCritical import Definitions.Def_AvgPHETH_Supplement_AltCircuit_eval
Formal statement
namespace AvgPHETH.Supplement
/-- **Theorem 7.1** (enhanced depth hierarchy theorem, 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.30 (PDF 32)): for every `k ≥ 1`
there exist `C_k, w₀ ∈ ℕ` and a family of AND-rooted alternating formulas `F_{k,w}` of depth `k` on
`poly(w)` input bits such that, for every `w ≥ w₀`, all internal fan-ins of `F_{k,w}` are at most
`w^{C_k}`, and, for every `t ≤ w/4`, no OR-rooted alternating circuit with depth `k + 1`, bottom width
at most `t`, and at most `2^t` gates above the bottom layer agrees with `F_{k,w}` on all critical
assignments.
**Formalization Note** `F_{k,w}` has `N w ≤ p(w)` variables for one polynomial `p`; the circuit is
over the same variables. Bottom width is the largest fan-in in gate layer `1`; the gates above the
bottom layer are those in layers `2, …, k+1`. "Does not agree on all critical assignments" is: some
critical assignment of `F_{k,w}` gets different values. `k ∈ ℕ` is read as `k ≥ 1` (an AND-rooted
formula has depth at least `1`). -/
theorem theorem_7_1 (k : ℕ) (hk : 1 ≤ k) :
∃ (Ck w₀ : ℕ) (p : Polynomial ℕ) (N : ℕ → ℕ) (F : (w : ℕ) → Formula (Fin (N w))),
(∀ w, N w ≤ p.eval w) ∧ (∀ w, (F w).IsLayeredAlt true k) ∧
∀ w, w₀ ≤ w →
(F w).FanInLe (w ^ Ck) ∧
∀ t : ℕ, 4 * t ≤ w → ∀ C : AltCircuit (Fin (N w)),
C.depth = k + 1 → C.outAnd = false →
(∀ g : Fin (C.size 1), (C.wires 0 g).card ≤ t) →
∑ j ∈ Finset.Icc 2 C.depth, C.size j ≤ 2 ^ t →
∃ α : Fin (N w) → Bool, (F w).IsCritical α ∧ C.eval α ≠ (F w).eval α := 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 7.1, p.30 (PDF 32); definitions of §4.3, pp.16–17 (PDF 18–19)