Lemma 6.6 — Averaged slice correlation after fixing data and seed coordinates
OpenParityBarrier563.Trilinear.Supplement.lemma_6_6boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , integers , , , and . Let u be even with , , , . Suppose an integer gives a decomposition of every b-CNF on every set of variables into at most closures with point lists of size at most L. Put . For every restriction τ fixing at most R of all trilinear input coordinates,
The remaining seed bits are uniform extensions of the seed part of τ; φ independently q-restricts only remaining data bits. Only the data part of τ acts on . This is the averaged slice estimate with arbitrary fixed seed and data values.
Differences from the source:
- encoding: every finite variable set and conditioned seed extensions → Fin t representatives and a finite uniform cube of live seed bits; reason: the representations are equivalent and compatible seeds are always nonempty
- encoding: R is the integer floor of m/128 → the natural floor of m/128; reason: m is positive under the printed numerical hypotheses, so the two floors agree
Preamble
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_SeedAndSubset set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Lemma 6.6: conditioning seed bits and restricting data bits are separate operations. -/
theorem lemma_6_6 (n k b : ℕ) (hb : 1 ≤ b) (hbk : b ≤ k)
(q : ℝ) (hq : 0 < q) (hq1 : q ≤ 1) (u L : ℕ) (he : Even u)
(hu : 512 ≤ u) (hL : 1 ≤ L) :
let p := (b : ℝ)/(64*k)
let η := q*p
let m := η*n
(u : ℝ) ≤ m/4 → (u : ℝ)*η ≤ 1/4 → m ≥ 512*u*Real.log (n+1) →
(L : ℝ) ≤ (u : ℝ)/512 →
(∀ t : ℕ, (t : ℝ) ≤ 4*m →
HasClosureDecomp b (Fin t) ((2 : ℝ)^((t : ℝ)/128)) L) →
∀ τ : Restriction (TriVar n), fixedCount τ ≤ ⌊m/128⌋₊ →
seedCorrelation τ q k ≤ 8*Real.exp (-m/512) := by sorry
end ParityBarrier563.Trilinear.Supplement
Source
Nikolai Chukhin, Xin Li, Ivan Mihajlin, Yan Zhong, Breaking the Parity Barrier for Constant-Depth Circuits, STOC 2027 submission #563 (October 2026), Lemma 6.6, printed p.28 / PDF p.30