Geometric and o-minimal Littlewood-Offord problems

Abstract

The classical Erdős-Littlewood-Offord theorem says that for nonzero vectors $a_1,\dots ,a_n\in {\mathbb{R}}^d$, any $x\in {\mathbb{R}}^d$, and uniformly random $({\xi }_1,\dots ,{\xi }_n)\in \{-1,1{\}}^n$, we have $\mathrm{Pr}(a_1{\xi }_1+\cdots +a_n{\xi }_n=x)=O(n^{-1/2})$. In this paper we show that $\mathrm{Pr}(a_1{\xi }_1+\cdots +a_n{\xi }_n\in S)\le n^{-1/2+o(1)}$ whenever $S$ is definable with respect to an o-minimal structure (for example, this holds when $S$ is any algebraic hypersurface), under the necessary condition that it does not contain a line segment. We also obtain an inverse theorem in this setting.

arXiv comment22 pages, minor edits. To appear in the Annals of Probability