Lemma 5.8 — Products of inverse-trace shifts on every coordinate subcube
OpenParityBarrier563.Trilinear.Supplement.lemma_5_8boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , choose any -basis of , and let τ fix any subset of its n coordinates. For every nonempty finite set B⊆K, with y uniform among the extensions of τ,
Here χ is the absolute-trace character and inverse at zero is zero. This controls products of shifted inverse traces on every coordinate subcube.
Differences from the source:
- encoding: coordinate subcube and finite field → Fin n coordinates with a binary basis and a Finset B; reason: the basis identifies every field element with exactly one Boolean assignment
- encoding: the field of order 2^n in every binary basis → an arbitrary field K with an F₂-algebra structure and an n-vector basis; reason: the basis bijects K with F₂^n and enforces order 2^n without any additional restriction
Preamble
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_InverseTrace set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Lemma 5.8, printed p.22 / PDF 24, including every coordinate subcube. -/
theorem lemma_5_8 (n : ℕ) (hn : 1 ≤ n)
(K : Type) [Field K] [Algebra (ZMod 2) K]
(e : Module.Basis (Fin n) (ZMod 2) K)
(τ : Restriction (Fin n)) (B : Finset K) (hB : B.Nonempty) :
|avg (fun z => ∏ v ∈ B, character n ((fieldPoint e (fill τ z) + v)⁻¹))| ≤
3 * B.card * (2 : ℝ) ^ ((n : ℝ)/2 - Fintype.card (Live τ)) := 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 5.8, printed p.22 / PDF p.24