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

AbstractLet ηi, i=1,…,n be independent identically distributed Bernoulli random variables, taking values ±1 with probability 12. Given a multiset V of n elements v1,…,vn of an additive group G, we define ρ(V) asρ(V):=supv∈GP(η1v1+⋯+ηnvn=v). An old result of Erdős and Moser asserts that if G=R and the vi are distinct then ρ(V) is O(n−32logn). This bound was then refined by Sárközy and Szemerédi to O(n−32), which is sharp up to a constant factor. The ultimate result is due to Stanley who used tools from algebraic geometry to give a complete description for sets having optimal ρ(V); the result has become 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