5
$\begingroup$

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.

$\endgroup$
6
  • 4
    $\begingroup$ This is reminiscent of the Littlewood-Offord problem (en.wikipedia.org/wiki/Littlewood%E2%80%93Offord_problem). $\endgroup$
    – GH from MO
    Jun 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 Kyncl
    Jun 16, 2014 at 8:07
  • 1
    $\begingroup$ See corollary 7.8 of additive combinatorics by tao and vu $\endgroup$ Jun 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 MO
    Jun 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 Kyncl
    Jun 17, 2014 at 5:40

2 Answers 2

7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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