Lemma 5.7 — Hash injectivity and polynomial-evaluation tail bound
OpenParityBarrier563.Trilinear.Supplement.lemma_5_7boolean-circuitscomplexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , t the largest even integer with , and fix any irreducible monic degree-r polynomial P over . Let σ restrict the n data coordinates, and . A uniformly random Hankel hash U fails to be injective on the points extending σ with probability at most . For every injective such U, choose independent uniform . For g the sign of the acceptance predicate ,
Both the hash failure estimate and the tail estimate for every injective hash are included. These give the hard slices for hashed evaluation.
Differences from the source:
- encoding: field quotient and uniform ring elements → monic coefficient bits, polynomial remainders, and uniform coefficient cubes; reason: irreducibility is assumed only in this support lemma; coefficient encoding is a bijection
Preamble
import Definitions.Def_ParityBarrier563_Trilinear_Supplement_HashedEvaluation set_option autoImplicit false open scoped Classical
Formal statement
namespace ParityBarrier563.Trilinear.Supplement
/-- Lemma 5.7: both the hash failure bound and the tail bound for every injective hash. -/
theorem lemma_5_7 (n : ℕ) (hn : 64 ≤ n) (Pbits : Fin (hashR n) → Bool)
(hP : Irreducible (hashModulus Pbits)) (σ : Restriction (Fin n))
(J : RealFn (Live σ)) (hJ : BoundedTest J) :
probability (fun U : Fin (n+hashR n-1) → Bool =>
¬ Function.Injective (fun z : Live σ → Bool => hankelHash U (fill σ z))) ≤
(2 : ℝ)^((Fintype.card (Live σ) : ℝ)-hashR n) ∧
∀ U : Fin (n+hashR n-1) → Bool,
Function.Injective (fun z : Live σ → Bool => hankelHash U (fill σ z)) →
probability (fun β : Fin (hashT n) × Fin (hashR n) → Bool =>
|avg (fun z => restrict σ (sgn (hashAccept U (hashModulus Pbits) β)) z * J z)| >
(2 : ℝ)^(-(Fintype.card (Live σ) : ℝ)/4)) ≤
(hashT n : ℝ)^(hashT n/2) *
(2 : ℝ)^(-((hashT n : ℝ)*Fintype.card (Live σ))/4) := 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.7, printed p.20 / PDF p.22