A New Bound in the Littlewood–Offord Problem

Abstract

The paper deals with studying a connection of the Littlewood–Offord problem with estimating the concentration functions of some symmetric infinitely divisible distributions. It is shown that the concentration function of a weighted sum of independent identically distributed random variables is estimated in terms of the concentration function of a symmetric infinitely divisible distribution whose spectral measure is concentrated on the set of plus-minus weights.

The aim of the present work is to provide a supplement to the paper of Eliseeva and Zaitsev [1]. We studied a connection of the Littlewood–Offord problem with estimating the concentration functions of some symmetric infinitely divisible distributions. In the study, we repeat the arguments of [1], adding, at the last step, an application of Jensen’s inequality.

Let $X,X_1,\dots ,X_n$ be independent identically distributed (i.i.d.) random variables. The concentration function of a ${\mathbf{R}}^d$-dimensional random vector Y with distribution $F=\mathcal{L}\left(Y\right)$ is defined by the equality

$$Q(F,\lambda )=\underset{x\in {\mathbf{R}}^d}{sup}\mathbf{P}(Y\in x+\lambda B),0\le \lambda \le \infty ,$$

where $B=\{x\in {\mathbf{R}}^d:\parallel x\parallel \le 1/2\}$. Of course, $Q(F,\infty )=1$. Let $a=(a_1,\dots ,a_n)$, where $a_k=(a_{k1},\dots ,a_{kd})\in {\mathbf{R}}^d$, $k=1,\dots ,n$. In this paper, we studied the behavior of the concentration functions of the weighted sums $S_a={\displaystyle \sum _{k=1}^n}{X}_k{a}_k$ with respect to the properties of vectors $a_k$. Interest in this subject has increased considerably in connection with the study of eigenvalues of random matrices (see, for instance, Friedland and Sodin [2], Rudelson and Vershynin [3,4], Tao and Vu [5,6], Nguyen and Vu [7], Vershynin [8], Tikhomirov [9], Livshyts, Tikhomirov and Vershynin [10], Campos et al. [11]). For a detailed history of the problem, we refer to a review of Nguyen and Vu [12]. The authors of the above articles (see also Halász [13]) called this question the Littlewood–Offord problem, since, for the first time, this problem was considered in 1943 by Littlewood and Offord [14] in connection with the study of random polynomials. They considered a special case, where the coefficients $a_k\in \mathbf{R}$ are one-dimensional, and X takes values $\pm 1$ with probabilities $1/2$.

The recent achivements in estimating the probabilities of singularity of random matrices [9,10,11] were based on the Rudelson and Vershynin [3,4,8] method of least common denominator. Note that the results of [2,4,8] (concerning the Littlewood–Offord problem) were improved and refined in [15,16,17].

Now, we introduce some notation. In the sequel, let $F_a$ denote the distribution of the sum $S_a$, let $E_y$ be the probability measure concentrated at a point y, and let G be the distribution of the symmetrized random variable $\tilde{X}=X_1-X_2$. For $\delta \ge 0$, we denote

$$p\left(\delta \right)=G\left\{\{z:|z|>\delta \}\right\}.$$

(1)

The symbol c will be used for absolute positive constants which may be different, even in the same formulas.

Writing $A\ll B$ means that $\left|A\right|\le cB$. Furthermore, we will write $A\asymp B$, if $A\ll B$ and $B\ll A$. We will write $A{\ll }_{d}B$, if $\left|A\right|\le c\left(d\right)B$, where $c\left(d\right)>0$ depends on d only. Similarly, $A{\asymp }_{d}B$, if $A{\ll }_{d}B$ and $B{\ll }_{d}A$. The scalar product in ${\mathbf{R}}^d$ will be denoted $〈·,·〉$. Later, $\lfloor x\rfloor$ is the largest integer k, such that $k<x$. For $x=(x_1,\cdots ,x_n)\in {\mathbf{R}}^n$, we will use the norms ${\parallel x\parallel }^2=x_1^2+\cdots +x_n^2$ and $\left|x\right|={max}_j\left|x_j\right|$. We denote by $\widehat{F}\left(t\right)$, $t\in {\mathbf{R}}^d$, the characteristic function of d-dimensional distributions F.

Products and powers of measures will be understood in the convolution sense. For infinitely divisible distribution F and $\lambda \ge 0$, we denote by $F^{\lambda }$ the infinitely divisible distribution with characteristic function ${\widehat{F}}^{\lambda }\left(t\right)$.

The elementary properties of concentration functions are well studied (see, for instance, refs [18,19,20]). It is known that

$$Q(F,\mu ){\ll }_d{(1+\lfloor \mu /\lambda \rfloor )}^{d}Q(F,\lambda )$$

(2)

for any $\mu ,\lambda >0$. Hence,

$$Q(F,c\lambda ){\asymp }_{d}Q(F,\lambda ).$$

(3)

Let us formulate a generalization of the classical Esséen inequality [21] to the multivariate case ([22], see also [19]):

Lemma 1.

Let $\tau >0$ and let F be a d-dimensional probability distribution. Then,

$$Q(F,\tau ){\ll }_d{\tau }^d{\int }_{\left|t\right|\le 1/\tau }\left|\widehat{F}\left(t\right)\right|dt.$$

(4)

In the general case, $Q(F,\tau )$ cannot be estimated from below by the right hand side of inequality (4). However, if we assume additionally that the distribution F is symmetric and its characteristic function is non-negative for all $t\in \mathbf{R}$, then we have the lower bound:

$$Q(F,\tau ){\gg }_d{\tau }^d\underset{\left|t\right|\le 1/\tau }{\int }\widehat{F}\left(t\right)dt,$$

(5)

and, therefore,

$$Q(F,\tau ){\asymp }_d{\tau }^d\underset{\left|t\right|\le 1/\tau }{\int }\widehat{F}\left(t\right)dt,$$

(6)

(see [23] or [18], Lemma 1.5 of Chapter II for $d=1$). In the multivariate case, relations (5) and (6) may be found in Zaitsev [24]. The use of relation (6) allows us to simplify the arguments of Friedland and Sodin [2], Rudelson and Vershynin [4] and Vershynin [8] which were applied to Littlewood–Offord problem (see [15,16,17]).

The main result of this paper is a general inequality which reduces the estimation of concentration functions in the Littlewood–Offord problem to the estimation of concentration functions of some infinitely divisible distributions. This result is formulated in Theorem 1.

For $z\in \mathbf{R}$, introduce the distribution $H_z$ with the characteristic function

$${\widehat{H}}_z\left(t\right)=exp\left(-\frac{1}{2}\sum _{k=1}^n\left(1-cos\left(〈t,a_k〉z\right)\right)\right).$$

(7)

It depends on the vector a. It is clear that $H_z$ is a symmetric infinitely divisible distribution. Therefore, its characteristic function is positive for all $t\in {\mathbf{R}}^d$.

Recall that $G=\mathcal{L}(X_1-X_2)$ and $F_a=\mathcal{L}\left(S_a\right)$, where $S_a={\displaystyle \sum _{k=1}^n}{X}_k{a}_k$.

Theorem 1.

Let V be an arbitrary one-dimensional Borel measure, such that $\lambda =V\left\{\mathbf{R}\right\}>0$, and $V\le G$, that is, $V\left\{B\right\}\le G\left\{B\right\}$, for any Borel set B. Then, for any $\tau >0$, we have

$$Q(F_a,\tau ){\ll }_d{\int }_{z\in \mathbf{R}}Q(H_1^{\lambda }{,\tau \left|z\right|}^{-1})W\left\{dz\right\},$$

(8)

where $W={\lambda }^{-1}V$.

Corollary 1.

For any $\epsilon ,\tau >0$, we have

$$Q(F_a,\tau ){\ll }_{d}Q(H_1^{p(\tau /\epsilon )},\epsilon ),$$

(9)

where $p(·)$ is defined in (1).

In order to verify Corollary 1, we note that the distribution $G=\mathcal{L}(\tilde{X})$ may be represented as the mixture

$$G=p_0{G}_0+p_1{G}_1,\mathrm{where}{p}_j=\mathbf{P}\left\{\tilde{X}\in A_j\right\},j=0,1,$$

$A_0=\{x:|x|\le \tau /\epsilon \}$, $A_1=\{x:|x|>\tau /\epsilon \}$, $G_j$ are probability measures defined for $p_j>0$ by the formula $G_j\left\{B\right\}=G\{B\cap A_j\}/p_j$, for any Borel set B. In fact, $G_j$ is the conditional distribution of $\tilde{X}$, given that $\tilde{X}\in A_j$. If $p_j=0$, then we can take $G_j$ as an arbitrary measure.

The conditions of Theorem 1 are satisfied for $V=p_1{G}_1$. $\lambda =p_1=p(\tau /\epsilon )$, $W=G_1$.

Inequalities (2) and (6) imply that

$$\begin{array}{ccc}\hfill Q(F_a,\tau )& {\ll }_d& {\int }_{z\in A_1}Q(H_1^{\lambda }{,\tau \left|z\right|}^{-1})W\left\{dz\right\}\hfill \\ & \le & \underset{z\ge \tau /\epsilon }{sup}Q\left(H_1^{p(\tau /\epsilon )},\tau /z\right)=Q\left(H_1^{p(\tau /\epsilon )},\epsilon \right),\hfill \end{array}$$

(10)

proving (9).

Applying Theorem 1 with V of the form

$$V\left\{dz\right\}={\left(1+{\lfloor \tau \left(\epsilon \right|z\left|\right)}^{-1}\rfloor \right)}^{-d}G\left\{dz\right\},$$

(11)

and using inequality (2), we obtain.

Corollary 2.

For any $\epsilon ,\tau >0$, we have

$$Q(F_a,\tau ){\ll }_d{\lambda }^{-1}Q(H_1^{\lambda },\epsilon ),$$

(12)

where

$$\lambda =\lambda (G,\tau /\epsilon )=V\left\{\mathbf{R}\right\}=\underset{z\in \mathbf{R}}{\int }{\left(1+{\lfloor \tau \left(\epsilon \right|z\left|\right)}^{-1}\rfloor \right)}^{-d}G\left\{dz\right\}.$$

(13)

It is clear that ${\lfloor \tau \left(\epsilon \right|z\left|\right)}^{-1}\rfloor =0$ if $\left|z\right|>\tau /\epsilon$. Therefore, $\lambda =\lambda (G,\tau /\epsilon )\ge p(\tau /\epsilon )$, hence, $Q(H_1^{\lambda },\epsilon )\le Q(H_1^{p(\tau /\epsilon )},\epsilon )$. Thus, if $\lambda {\gg }_{d}1$, then inequality (12) of Corollary 2 is stronger than inequality (9) of Corollary 1.

The proof of Theorem 1 is based on elementary properties of concentration functions. We repeat the arguments of [1], adding, at the last step, an application of Jensen’s inequality. In [1], inequality (2) was used instead. The main result of [1] does not imply Corollary 2. Note that $H_1^{\lambda }$ is an infinitely divisible distribution with the Lévy spectral measure $M_{\lambda }=\frac{\lambda }{4}{M}^{*}$, where $M^{*}={\displaystyle \sum _{k=1}^n}\left(E_{a_k}+E_{-a_k}\right)$. It is clear that the assertions of Theorem 1 and Corollaries 1 and 2 may be treated as statements about the measure $M^{*}$.

Corollary 1 was already proved earlier in [1,25], see also [26] for the case $\tau =0$. It was used essentially in [25,27] to show that Arak’s inequalities for concentration functions may be used for investigations of the Littlewood–Offord problem. Arak has shown that if the concentration function of infinitely divisible distribution is relatively large, then the spectral measure of this distribution is concentrated in a neighborhood of a set with simple arithmetical structure. Together with Corollary 1, this means that a large value of $Q(F_a,\tau )$ implies a simple arithmetical structure of the set ${\{\pm a_k\}}_{k=1}^n$. This statement is similar to the so-called “inverse principle” in the Littlewood–Offord problem (see [5,7,12]).

Note that using the results of Arak [23,28] (see also [18]) one could derive from Corollary 1 inequalities similar to boumds for concentration functions in the Littlewood–Offord problem, which were obtained in a paper of Nguyen and Vu [7] (see also [12]). A detailed discussion of this fact is presented in [25,27]. We noticed that Corollary 2 may be stronger than Corollary 1. Therefore, the results of [25,27] could be improved (in the sense of dependence of constants on the distribution of $X_1$) replacing an application of Corollary 1 by an application of Corollary 2. The authors are going to devote a separate publication to this topic.

Proof of Theorem 1.

Let us show that, for arbitrary probability distribution, W and $\lambda ,T>0$,

$$\begin{array}{c}log{\int }_{\left|t\right|\le T}exp\left(-\frac{1}{2}\sum _{k=1}^n{\int }_{z\in \mathbf{R}}\left(1-cos\left(〈t,a_k〉z\right)\right)\lambda W\left\{dz\right\}\right)dt\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\le {\int }_{z\in \mathbf{R}}\left(log{\int }_{\left|t\right|\le T}exp\left(-\frac{\lambda }{2}\sum _{k=1}^n\left(1-cos\left(〈t,a_k〉z\right)\right)\right)dt\right)W\left\{dz\right\}\\ \hfill ={\int }_{z\in \mathbf{R}}\left(log{\int }_{\left|t\right|\le T}{\widehat{H}}_z^{\lambda }\left(t\right)dt\right)W\left\{dz\right\}.\end{array}$$

(14)

It is suffice to prove (14) for discrete distributions $W={\sum }_{j=1}^{\infty }{p}_j{E}_{z_j}$, where $0\le p_j\le 1$, $z_j\in \mathbf{R}$, ${\sum }_{j=1}^{\infty }{p}_j=1$. Applying in this case the generalized Hölder inequality, we have

$$\begin{array}{c}\underset{\left|t\right|\le T}{\int }exp\left(-\frac{1}{2}\sum _{k=1}^n\underset{z\in \mathbf{R}}{\int }\left(1-cos\left(〈t,a_k〉z\right)\right)\lambda W\left\{dz\right\}\right)dt\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\underset{\left|t\right|\le T}{\int }exp\left(-\frac{\lambda }{2}\sum _{j=1}^{\infty }{p}_j\sum _{k=1}^n\left(1-cos\left(〈t,a_k〉z_j\right)\right)\right)dt\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\le \prod _{j=1}^{\infty }{\left(\underset{\left|t\right|\le T}{\int }exp\left(-\frac{\lambda }{2}\sum _{k=1}^n\left(1-cos\left(〈t,a_k〉z_j\right)\right)\right)dt\right)}^{p_j}.\hfill \end{array}$$

(15)

Taking logarithms of the left- and right-hand sides of (15), we get (14). In general cases, we can approximate W by discrete distributions in the sense of weak convergence and pass to the limit. Note also that the integrals ${\int }_{\left|t\right|\le T}dt$ may be replaced in (14) by the integrals $\int \mu \left\{dt\right\}$ with an arbitrary Borel measure $\mu$.

Since for characteristic function $\widehat{U}\left(t\right)$ of a random vector Y, we have

$$|\widehat{U}{\left(t\right)|}^2=\mathbf{E}exp(i\langle t,\tilde{Y}\rangle )=\mathbf{E}cos(\langle t,\tilde{Y}\rangle ),$$

where $\tilde{Y}$ is the corresponding symmetrized random vector, then

$$|\widehat{U}\left(t\right)|\le exp\left(-\frac{1}{2}\left(1-|\widehat{U}{\left(t\right)|}^2\right)\right)=exp\left(-\frac{1}{2}\mathbf{E}\left(1-cos(\langle t,\tilde{Y}\rangle )\right)\right).$$

(16)

According to Theorem 1 and relations $V=\lambda W\le G$, (14) and (16), applying Jensen’s inequality of the form $exp\left(\mathbf{E}f\right(\xi \left)\right)\le \mathbf{E}exp\left(f\right(\xi \left)\right)$ for any measurable function f and any random varialble $\xi$, we have

$$\begin{array}{ccc}\hfill Q(F_a,\tau )& {\ll }_d& {\tau }^d{\int }_{\tau \left|t\right|\le 1}\left|\widehat{F_a}\left(t\right)\right|dt\hfill \\ & {\ll }_d& {\tau }^d{\int }_{\tau \left|t\right|\le 1}exp\left(-\frac{1}{2}\sum _{k=1}^n\mathbf{E}\left(1-cos\left(〈t,a_k〉\tilde{X}\right)\right)\right)dt\hfill \\ & =& {\tau }^d{\int }_{\tau \left|t\right|\le 1}exp\left(-\frac{1}{2}\sum _{k=1}^n{\int }_{z\in \mathbf{R}}\left(1-cos\left(〈t,a_k〉z\right)\right)G\left\{dz\right\}\right)dt\hfill \\ & \le & {\tau }^d{\int }_{\tau \left|t\right|\le 1}exp\left(-\frac{1}{2}\sum _{k=1}^n{\int }_{z\in \mathbf{R}}\left(1-cos\left(〈t,a_k〉z\right)\right)\lambda W\left\{dz\right\}\right)dt\hfill \\ & \le & exp\left({\int }_{z\in \mathbf{R}}log\left({\tau }^d{\int }_{\tau \left|t\right|\le 1}{\widehat{H}}_z^{\lambda }\left(t\right)dt\right)W\left\{dz\right\}\right)\hfill \\ & \le & {\int }_{z\in \mathbf{R}}\left({\tau }^d{\int }_{\tau \left|t\right|\le 1}{\widehat{H}}_z^{\lambda }\left(t\right)dt\right)W\left\{dz\right\}.\hfill \end{array}$$

(17)

Using (6), we have

$$\begin{array}{ccc}\hfill {\tau }^d{\int }_{\tau \left|t\right|\le 1}{\widehat{H}}_z^{\lambda }\left(t\right)dt& {\asymp }_d& Q(H_z^{\lambda },\tau )=Q\left(H_1^{\lambda },\tau {\left|z\right|}^{-1}\right).\hfill \end{array}$$

(18)

Substituting this formula into (17), we obtain (8). In (18), we have used that $H_z^{\lambda }=\mathcal{L}\left(z\eta \right)$, where $\eta$ is a random vector with $\mathcal{L}\left(\eta \right)=H_1^{\lambda }$. □