Reverse Littlewood--Offord problems with parity conditions

Abstract

We consider the probability that the random signed sum $\hat{I}{¾}_1{v}_1+\cdots +\hat{I}{¾}_n{v}_n$ lies within a given distance $r$ of the origin, where $v_1,\dots ,v_n\in {\mathbb{R}}^d$ are fixed unit vectors and $\hat{I}{¾}_1,\dots ,\hat{I}{¾}_n$ are independently and uniformly distributed on $\{-1,+1\}$. In particular, our results demonstrate that, for certain values of $r$, the infimum of this probability is very sensitive to the parity of $n$. We prove that, for any $d\ge 3$, there is some $\epsilon =\epsilon (d)>0$ such that for any $n\not\equiv d\mathrm{mod}2$ and unit vectors $v_1,\dots ,v_n\in {\mathbb{R}}^d$, there are signs $\hat{I}{\cdot }_1,\dots ,\hat{I}{\cdot }_n\in \{-1,+1\}$ such that $\Vert {\sum }_{i=1}^n\hat{I}{\cdot }_i{v}_i\Vert \le \sqrt{d-\epsilon }$, and so $\mathbb{P}(\Vert \hat{I}{¾}_1{v}_1+\cdots +\hat{I}{¾}_n{v}_n\Vert \le \sqrt{d-\epsilon })>0$. This is in contrast to the case of $n\equiv d\mathrm{mod}2$, wherein the above probability can be zero. More is known if $d=2$ and $n$ is odd, and in this case we present a construction demonstrating that $\mathbb{P}(\Vert \hat{I}{¾}_1{v}_1+\cdots +\hat{I}{¾}_n{v}_n\Vert \le 1)$ can decay exponentially as $n$ increases.

13 pages