OpenAlex ·
Optimal bound for the polynomial Littlewood-Offord problem
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.08708
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Combinatorics
Perfect state transfer on mixed graphs: complete classes and transfer times
A deterministic algorithm for signing bipartite graphs at the Ramanujan bound
On the complexity of the single-move labeled token routing problem
Moment Methods for Uniform Average Mixing on Strongly Regular Graphs
Stability of plethysm coefficients and modified polynomial induction
Get the few papers worth your time in Combinatorics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.