A new approach to an old problem of Erdős and Moser

DOI10.1016/J.JCTA.2012.01.003zbMATH Open1268.11019arXiv1112.0755OpenAlexW2079194144MaRDI QIDQ412182FDOQ412182

Hoi Nguyen

Publication date: 4 May 2012

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let $et{a}_i,i=1,\mathrm{...},n$ be iid Bernoulli random variables, taking values $pm1$ with probability 1/2. Given a multiset $V$ of $n$ elements $v_1,\mathrm{...},v_n$ of an additive group $G$, we define the emph{concentration probability} of $V$ as ${\displaystyle }$ ho(V) := sup_{vin G} P(eta_1 v_1 + ... eta_n v_n =v). ${\displaystyle }$ An old result of Erdos and Moser asserts that if $v_i$ are distinct real numbers then $ho(V)$ is $O(n^{-3/2}logn)$. This bound was then refined by Sarkozy and Szemeredi to $O(n^{-3/2})$, which is sharp up to a constant factor. The ultimate result dues to Stanley who used tools from algebraic geometry to give a complete description for sets having optimal concentration probability; the result now becomes classic in algebraic combinatorics. In this paper, we will prove that the optimal sets from Stanley's work are stable. More importantly, our result gives an almost complete description for sets having large concentration probability.

Full work available at URL: https://arxiv.org/abs/1112.0755

Recommendations

• A sharp inverse Littlewood-Offord theorem
• Optimal inverse Littlewood-Offord theorems
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• On the Littlewood‐Offord problem for arbitrary distributions
• scientific article; zbMATH DE number 813707

zbMATH Keywords

concentration probabilitysharp concentrationErdős-Moser problem

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Sums of independent random variables; random walks (60G50) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Arithmetic combinatorics; higher degree uniformity (11B30)

Cites Work

• Additive combinatorics
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Optimal inverse Littlewood-Offord theorems
• SETS WITH SMALL SUMSET AND RECTIFICATION
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Title not available (Why is that?)
• On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors
• On the singularity probability of random Bernoulli matrices
• Über ein Problem von Erdös und Moser
• On a lemma of Littlewood and Offord
• Solution of Two Difficult Combinatorial Problems with Linear Algebra
• Long arithmetic progressions in sumsets: Thresholds and bounds
• Freiman's theorem for solvable groups

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Majorization and Rényi entropy inequalities via Sperner theory

This page was built for publication: A new approach to an old problem of Erdős and Moser

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412182)