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