MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
This is reminiscent of the Littlewood-Offord 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 – 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
up vote 7 down vote accepted

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$.

share|cite|improve this answer

Expanding on my comment and continuing GH from MO's answer:

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$.

By Erdos's generalization of the Sperner Theorem, we have

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.