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

DOI10.1007/S00493-012-2716-XMaRDI QIDQ2392038zbMATH OpenOpenAlexWikidataFDO

Publication date 6 August 2013

Published in Combinatorica (Search for Journal in Brave)

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

Bernoulli random variables concentration inequality Fubini's theorem Littlewood-Offord problem orthonormal basis small ball probability

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Abstract: We give a new bound on the probability that the random sum

x i_{1} v_{1} + ... + x i_{n} v_{n}

belongs to a ball of fixed radius, where the

x i_{i}

are iid Bernoulli random variables and the

v_{i}

are vectors in

R^{d}

. As an application, we prove a conjecture of Frankl and F"uredi (raised in 1988), which can be seen as the high dimensional version of the classical Littlewood-Offord-ErdH os theorem.

Review text

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\).

Recommendations

Cites work

Cited in

(16)

This page was built for publication: The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi

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