Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated just now
PreprintCC BY 4.0arXiv

Optimal bound for the polynomial Littlewood-Offord problem

  • Alexandr Grebennikov
Open at sourcePDFDOICite

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, …, ξn, we have ℙ[F(ξ1, …, ξn) = 0] = Od(r−1/2). This improves upon the previous bound of (log r)Od(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.

Related

  1. Pseudo-solutions of polynomial systems and the lower bound problem for AC0[p]-Frege systems
    Jan Krajicek
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  2. A Uniform Bound on Optimal Strategy Length in Water Transport Problem
    Tianyi Tao, Bohan Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Erdős's Robust Polynomial Interpolation Problem: the Optimal Exponential Scale
    Jia-Qi Yang
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. The weak-type (1,1) bound for the Hardy--Littlewood maximal function is O(√n log n)
    Daniel Spector, Cody B. Stockdale
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  5. Polynomial Bohnenblust--Hille Bounds and Hardy--Littlewood Inequalities for Finite Local Systems
    Anderson Barbosa, Daniel Núñez-Alarcón, Daniel Pellegrino +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{grebennikov2026optimal,
  title = {{Optimal bound for the polynomial Littlewood-Offord problem}},
  author = {Alexandr Grebennikov},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.08708},
  eprint = {2610.08708},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.08708},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Optimal bound for the polynomial Littlewood-Offord problem
AU  - Alexandr Grebennikov
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.08708
UR  - https://arxiv.org/abs/2610.08708
AB  - 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, …, ξ_n, we have ℙ[F(ξ_1, …, ξ_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.
ER  -