Resilience for the Littlewood-Offord Problem

Consider the sum X(ξ)=∑_i=1ⁿa_iξ_i, where a=(a_i)_i=1ⁿ is a sequence of non-zero reals and ξ=(ξ_i)_i=1ⁿ is a sequence of i.i.d. Rademacher random variables (that is, Pr[ξ_i=1]=Pr[ξ_i=−1]=1/2). The classical Littlewood-Offord problem asks for the best possible upper bound on the concentration probabilities Pr[X=x]. We study a resilience version of the Littlewood-Offord problem: how many of the ξ_i is an adversary typically allowed to change without being able to force concentration on a particular value? We solve this problem asymptotically, demonstrating an interesting connection to the notion of an additive basis from additive combinatorics. We also present several interesting open problems.