2025/05/30 by Alexandr Grebennikov, Matthew Kwan, Grebennikov, Alexandr +1
Computer Science · #Topological and Geometric Data Analysis #Data Management and Algorithms #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.2505.24699
Consider nonzero vectors a1,…,an∈ℂk, independent Rademacher random variables ξ1,…,ξn, and a set S⊆ℂk. What upper bounds can we prove on the probability that the random sum ξ1a1+…+ξnan lies in S? We develop a general framework that allows us to reduce problems of this type to counting lattice points in S. We apply this framework with known results from diophantine geometry to prove various bounds when 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∈ℂ[x1,…,xn] has bounded Chow rank and ''robustly depends on at least b of its variables'', then ℙ[F(ξ1,…,ξn)=0]≤ O(1/√(b)). We also prove significantly stronger bounds when F is ''robustly irreducible'', towards a conjecture of Costello.