Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
4  
This is reminiscent of the Littlewood-Offord problem (en.wikipedia.org/wiki/Littlewood%E2%80%93Offord_problem). –  GH from MO Jun 16 at 7:18
2  
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 at 8:07
1  
See corollary 7.8 of additive combinatorics by tao and vu –  George Shakan Jun 16 at 9:55
3  
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 at 10:09
1  
@Joybangla As GH from MO correctly noticed, I misread the question and assumed that $\alpha_i \in \{-1,1\}$. –  Jan Kyncl Jun 17 at 5:40

2 Answers 2

up vote 6 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|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|improve this answer

Your Answer

 
discard

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.