Optimal probability bound for polynomial outcomes with random inputs
Optimal bound for the polynomial Littlewood-Offord problem
Computational Complexity
Summary
This paper improves our understanding of how likely it is for a certain type of polynomial expression, made from random plus-or-minus inputs, to equal zero. The authors provide a sharper, optimal estimate for this probability when the polynomial has a specific number of top-degree terms involving distinct variables. Their approach solves an earlier problem and confirms a recent conjecture about related mathematical functions. This work refines a previous more complicated estimate, giving a cleaner and tighter result.
What this means in practice
- •For cryptography engineers: Design cryptographic protocols that rely on polynomial randomness properties with improved guarantees on zero-probability outcomes.
- •For signal processing developers: Enhance random signal models by using precise probability bounds for polynomial expressions with independent random inputs.
A theory result. No direct application yet.
Authors
Alexandr Grebennikov
Abstract
We present an exposition of an argument, discovered by GPT-6 Pro, that gives an optimal bound for the polynomial Littlewood-Offord problem. Namely, let $F$ be a degree-$d$ multilinear polynomial that contains $r$ degree-$d$ monomials involving disjoint sets of variables. Then, for i.i.d. Rademacher random variables $ξ_1, \ldots, ξ_n$, we have $\mathbb{P}[F(ξ_1, \ldots, ξ_n) = 0] = O_d(r^{-1/2})$. This improves upon the previous bound of $(\log r)^{O_d(1)} r^{-1/2}$ due to Meka, O. Nguyen, and Vu, and resolves a conjecture attributed to H. Nguyen and Vu. The key part of the proof is an estimate for the total influence of bounded-degree rational functions, which resolves a recent conjecture of Kothari, Kovacs-Deak, Wang, and Yang.