# A bound on a set

Let $x_1,\cdots , x_n$ be a sequence of real number such that $x_i\geq 1$ for all $1\leq i\leq n$, $S=\{\alpha_1x_1+\cdots +\alpha_nx_n | \alpha_i\in\{0,+1,-1\}\}$ and $I=[a,b)$ be a Interval with length $2$. So I was wondering if there was any subsequent upper bound on $|I \cap S|$. Is there a general bound when $2$ is replaced by a positive real $\alpha$? Thanks in advance for your answers and comments. I haven't been able to guess anything, but this bound on size of a set reminded me of Sperner's Theorem but not sure about it.

-
This is reminiscent of the Littlewood-Offord problem (en.wikipedia.org/wiki/Littlewood%E2%80%93Offord_problem). –  GH from MO Jun 16 '14 at 7:18
Yes, Sperner Theorem gives the upper bound ${n \choose \lfloor n/2\rfloor}$. For $\alpha>2$, one can use the generalization to families of subsets with no chains of length $r$, where $r=\lceil\alpha/2\rceil+1$. See en.wikipedia.org/wiki/Sperner%27s_theorem#No_long_chains –  Jan Kyncl Jun 16 '14 at 8:07
See corollary 7.8 of additive combinatorics by tao and vu –  George Shakan Jun 16 '14 at 9:55
Note that the Sperner bound is not quite the answer here as the coefficients are from $\{-1,0,+1\}$ rather than from $\{-1,+1\}$. See my response for the full story (for the case when $I$ has length $2$). –  GH from MO Jun 16 '14 at 10:09
@Joybangla As GH from MO correctly noticed, I misread the question and assumed that $\alpha_i \in \{-1,1\}$. –  Jan Kyncl Jun 17 '14 at 5:40

For a given $A\subset\{1,\dots,n\}$, let $S_A$ denote the multiset of $\alpha_1 x_1+\cdots+\alpha_n x_n$ with $\alpha_i=\pm 1$ for $i\in A$ and $\alpha_i=0$ for $i\not\in A$. Note that, as multisets, $$S=\bigcup_{A\subset\{1,\dots,n\}} S_A,$$ so that $$I\cap S=\bigcup_{A\subset\{1,\dots,n\}} (I\cap S_A).$$ By the Sperner bound, realized in this problem by Erdős (1945), we have $$|I\cap S_A|\leq {|A| \choose \lfloor |A|/2\rfloor},$$ with equality for $I=[-1,1)$ and $x_i=1$ for $i\in A$. Hence, $$|I\cap S|\leq \sum_{A\subset\{1,\dots,n\}}{|A| \choose \lfloor |A|/2\rfloor}=\sum_{m=0}^n {n\choose m}{m \choose \lfloor m/2\rfloor},$$ with equality for $I=[-1,1)$ and $x_1=\dots =x_n=1$.
For $\alpha >2$, let $r:=\lceil\alpha/2\rceil+1$. Since a half-open interval $I$ of length $\alpha$ cannot contain $r$ numbers whose pairwise distance is at least $2$, for any fixed $A \subseteq \{1, \dots, n\}$, the set $A_+:=\{i \in A; \alpha_i = +1\}$ cannot contain an inclusion chain of length $r$.
$$\lvert I\cap S_A \rvert \le \sum_{k=\lfloor |A|/2\rfloor-\lfloor (r-1)/2\rfloor}^{\lfloor |A|/2\rfloor+\lfloor r/2\rfloor} {\lvert A \rvert \choose k},$$ with equality for $I=[-r+1, -r+1+\alpha)$ and $x_i=1$ for $i\in A$. Hence, $$|I\cap S|\leq \sum_{A\subset\{1,\dots,n\}}\sum_{k=\lfloor |A|/2\rfloor-\lfloor (r-1)/2\rfloor}^{\lfloor |A|/2\rfloor+\lfloor r/2\rfloor} {\lvert A \rvert \choose k} = \sum_{m=0}^n {n\choose m}\sum_{k=\lfloor m/2\rfloor-\lfloor (r-1)/2\rfloor}^{\lfloor m/2\rfloor+\lfloor r/2\rfloor} {m \choose k},$$ with equality for $I=[-r+1, -r+1+\alpha)$ and $x_i=1$ for all $1\le i\le n$.