Geometric Littlewood–Offord problems via lattice point counting
Alexandr Grebennikov, Matthew Kwan · 2025
Read Geometric Littlewood–Offord problems via lattice point counting by Alexandr Grebennikov, Matthew Kwan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-24699.txt.
Introduction
Alexandr Grebennikov and Matthew Kwan bound the chance that a random signed sum of vectors lands inside a given set, in a paper published in two thousand twenty-five. Each vector is added or subtracted at random, and the question is how concentrated the total can be. Questions of this shape are called Littlewood-Offord problems.
Their idea is to turn probability into counting: the chance is controlled by how many lattice points the target set contains. With that bridge, they import tools from Diophantine geometry to handle concrete shapes. They prove bounds when the set is points in convex position, an algebraic variety, or a semialgebraic set. Along the way they settle conjectures posed by other researchers. Corollaries cover polynomial versions of the problem for polynomials built from few linear forms. The framework gives a geometric handle on a classic anti-concentration question.
Catalog record
| CREATOR | Alexandr Grebennikov, Matthew Kwan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-24699
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Geometric Littlewood–Offord problems via lattice point counting Alexandr Grebennikov, Matthew Kwan Abstract Consider nonzero vectors a 1 , … , a n ∈ ℂ k a_{1},\dots,a_{n}\in\mathbb{C}^{k} , independent Rademacher random variables ξ 1 , … , ξ n \xi_{1},\dots,\xi_{n} , and a set S ⊆ ℂ k S\subseteq\mathbb{C}^{k} . What upper bounds can we prove on the probability that the random sum ξ 1 a 1 + ⋯ + ξ n a n \xi_{1}a_{1}+\dots+\xi_{n}a_{n} lies in S S ? We develop a general framework that allows us to reduce problems of this type to counting lattice points in S S . We apply this framework with known results from diophantine geometry to prove various bounds when S S is a set of points in convex position, an algebraic variety, or a semialgebraic set. In particular, this resolves conjectures of Fox–Kwan–Spink and Kwan–Sauermann. We also obtain some corollaries for the polynomial Littlewood–Offord problem , for polynomials that have bounded Chow rank (i.e., can be written as a polynomial of a bounded number of linear forms). For example, one of our results confirms a conjecture of Nguyen and Vu in the special case of polynomials with bounded Chow rank: if a bounded-degree polynomial F ∈ ℂ [ x 1 , … , x n ] F\in\mathbb{C}[x_{1},\dots,x_{n}] has bounded Chow rank and “robustly depends on at least b b of its variables”, then ℙ [ F ( ξ 1 , … , ξ n ) = 0 ] ⩽ O ( 1 / b ) \mathbb{P}[F(\xi_{1},\dots,\xi_{n})=0]\leqslant O(1/\sqrt{b}) . We also prove significantly stronger bounds when F F is “robustly irreducible”, towards a conjecture of Costello. † † Both authors are supported by ERC Starting Grant “RANDSTRUCT” No. 101076777. 1 Introduction Throughout this paper \xi_{1},\ldots,\xi_{n} will always denote a sequence of independent Rademacher random variables (that is, taking values 1 or -1 with probability 1/2 ). In 1943, motivated by their study of random algebraic equations, Littlewood and Offord [ 26 ] considered the following question: given a sequence of n nonzero real numbers c_{1},\ldots,c_{n} , what is the maximum probability that the random variable \xi_{1}c_{1}+\ldots+\xi_{n}c_{n} equals a given value 1 1 1 Here and for the rest of this introduction, we specialise to the “discrete” form of the Littlewood–Offord problem. (There is also a “small-ball” form, where one assumes that the c_{i} have absolute value at least 1, and studies the likelihood that \xi_{1}c_{1}+\ldots+\xi_{n}c_{n} falls in a given interval of radius 1.) ? They proved an upper bound of the form O(\log n/\sqrt{n}) , which was sharpened by an elegant argument of Erdős [ 14 ] to the following precise result (now called the Erdős–Littlewood–Offord theorem): (1) \sup_{z\in\mathbb{R}}\mathbb{P}\mathopen{}\mathclose{{\left[\xi_{1}c_{1}+\ldots+\xi_{n}c_{n}=z}}\right]\leqslant 2^{-n}\binom{n}{\lfloor n/2\rfloor}=\mathopen{}\mathclose{{\left(\sqrt{2/\pi}+o(1)}}\right)\frac{1}{\sqrt{n}}=O\mathopen{}\mathclose{{\left(\frac{1}{\sqrt{n}}}}\right). Since then, the Erdős–Littlewood–Offord theorem has been generalised in many different directions, and these results have found applications in a wide variety of different fields (e.g., random matrix theory, the theory of Boolean functions, extremal combinatorics; see [ 29 ] for a survey). In this paper we introduce a general approach to attack several different questions in Littlewood–Offord theory of a “geometric” flavour. 1.1 Polynomial Littlewood–Offord problem First, a natural direction of generalisation is to replace the linear form \xi_{1}c_{1}+\ldots+\xi_{n}c_{n} by a polynomial F(\xi_{1},\ldots,\xi_{n}) of higher degree. This direction was first considered by Rosiński and Samorodnitsky [ 33 ] , Costello, Tao and Vu [ 11 ] , and Razborov and Viola [ 32 ] in the contexts of Lévy chaos, discrete random matrices and Boolean functions, respectively. It is widely believed that if F is an n -variable degree- d polynomial that is “robustly nonzero” then a bound analogous to Equation 1 should hold. For example, it was conjectured by Nguyen and Vu (see [ 27 , 32 ] ) that if F has at least bn^{d-1} nonzero coefficients, then 2 2 2 Subscripts on asymptotic notation indicate quantities that should be treated as constants. (2) \mathbb{P}\mathopen{}\mathclose{{\left[F(\xi_{1},\ldots,\xi_{n})=0}}\right]\leqslant O_{d}\mathopen{}\mathclose{{\left(\frac{1}{\sqrt{b}}}}\right). This is known to hold for d=1 (thanks to the Erdős–Littlewood–Offord theorem) and for d=2 (thanks to recent work of Kwan and Sauermann [ 25 ] ). For general d , the best available bound (due to Meka, Nguyen and Vu [ 27 ] , via a result of Kane [ 24 ] ) falls short of Equation 2 by a factor of (\log b)^{O_{d}(1)} . If true, the bound in Equation 2 is best-possible: for example, one can see this by considering the polynomial (x_{1}+\dots+x_{n})^{d} . However, it is natural to wonder whether one can prove much stronger bounds if one makes assumptions to rule out this kind of example. Indeed, it was conjectured by Costello [ 10 ] that Equation 2 can be significantly improved when the polynomial F is “robustly irreducible”. Though his original conjecture was recently disproved by Kwan, Sah and Sawhney (see [ 23 , Appendix B] ), it is plausible that the following “repaired” version of his conjecture still holds: consider any polynomial F\in\mathbb{C}[t_{1},\ldots,t_{n}] of degree d\geqslant 2 , and suppose that for any reducible 3 3 3 In this paper, we use the convention that the zero polynomial is reducible. polynomial G of degree at least d , the difference F-G has at least bn^{d-1} nonzero coefficients. Then, \mathbb{P}\mathopen{}\mathclose{{\left[F(\xi_{1},\dots,\xi_{n})=0}}\right]\leqslant O_{d,\varepsilon}(b^{-1+\varepsilon}). We remark that a slight variation on this “repaired” conjecture was also suggested by Jin, Kwan, Sauermann and Wang [ 23 ] ; they observed that this bound, if true, would be best possible. As our first results in this paper, we essentially resolve the above conjectures, under an assumption that F has “bounded complexity”. Formally, for a polynomial F\in\mathbb{F}[t_{1},\ldots,t_{n}] of degree d (over some field \mathbb{F}\subseteq\mathbb{C} ), define its Chow rank (over \mathbb{F} ) to be the minimal number c such that F can be represented as \sum_{i=1}^{c}P_{i} , where each P_{i} is a product of d (not necessarily homogeneous) linear forms with coefficients in \mathbb{F} . One can check that the Chow rank of any homogeneous polynomial of a fixed degree d is “equivalent” to the tensor rank of its coefficient tensor (in the sense that each of them is bounded by some function of the other). Theorem 1.1 . Let 1\leqslant b\leqslant n and d,c\geqslant 1 be integers. Let F\in\mathbb{C}[t_{1},\ldots,t_{n}] be a polynomial of degree d and Chow rank at most c . (1) Suppose that F “robustly depends on at least b of its variables”, in the sense that it is not possible to make F(\xi_{1},\dots,\xi_{n}) identically zero by fixing fewer than b of the \xi_{i} to \pm 1 values. (In particular, this holds whenever F has at least bn^{d-1} nonzero degree- d coefficients 4 4 4 Note that the total number of terms in F with degree less than d is at most dn^{d-1} , so these terms can be essentially ignored. .) Then \mathbb{P}\mathopen{}\mathclose{{\left[F(\xi_{1},\ldots,\xi_{n})=0}}\right]\leqslant O_{d,c}(b^{-1/2}). (2) Suppose that d\geqslant 2 and d\neq 3 . Also, suppose that for any reducible polynomial G\in\mathbb{C}[x_{1},\ldots,x_{n}] of degree at most d , the difference F-G has at least bn^{d-1} nonzero coefficients. Then for any \varepsilon>0 , \mathbb{P}\mathopen{}\mathclose{{\left[F(\xi_{1},\ldots,\xi_{n})=0}}\right]=O_{d,c,\varepsilon}(b^{-1+\varepsilon}). We will discuss our proof approach properly later in this introduction, but very briefly: we prove Theorem 1.1 via a connection to diophantine geometry. Specifically, we leverage various known estimates for the number of lattice