The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi (Q2392038)

Let \(V =\{v_1,\dots,v_n\}\) be a (multi-)set of \(n\) vectors in \(\mathbb R^d\). Consider the random sum \(X_{V }= \xi_1v_1 + \ldots+ \xi_nv_n\) where \(\xi _i\) are i.i.d.\ Bernoulli random variables (each \(\xi_i\) takes values \(1\) and \(-1\) with probability 1/2 each). The famous Littlewood-Offord problem (posed in [\textit{J. E.~Littlewood} and \textit{A. C.~Offord}, Mat. Sb., N. Ser. 12(54), 277--286 (1943; Zbl 0061.01801)]) is to estimate the small ball probability \(p_d(n,\Delta) = \sup_{V,B} P(X_{V} \in B)\), where the supremum is taken over all multi-sets \(V =\{v_1,\dots,v_n\}\) of \(n\) vectors of length at least one and all closed balls \(B\) of radius \(\Delta\). The main result of this paper is the following: Let \(V =\{v_1, \ldots ,v_n\}\) be a multi-set of vectors in \(\mathbb R^d\) with the property that for any hyperplane \(H\), one has \(\text{dist}(v_i,H) \geq 1\) for at least \(k\) values of \( i=1, \ldots, n\). Then for any unit ball \(B\), one has \(P(X_V\in B) = O(k^{-d/2})\). The hidden constant in the \(O(\;)\) notation here depends on \(d\), but not on \(k\) and \(n\). As an application, the following conjecture of \textit{P.~Frankl} and \textit{Z.~Füredi} [Ann. Math. (2) 128, No. 2, 259--270 (1988; Zbl 0667.05017)] is proved: Let \(\Delta\), \(d\) be fixed. If \(s-1 \leq \Delta<\sqrt{(s-1)^{2}+1}\) and \(n\) is sufficiently large, then \(p_{d}(n,\Delta) = 2^{-n}S(n, s)\), where \(S(n,s)\) denotes the sum of the largest \(s\) binomial coefficients \({{n}\choose {i}}\), \(0\leq i\leq n\).