4
$\begingroup$

I'm self-studying Bollobás' Combinatorics textbook and am stuck on a question regarding a reformulation of Littlewood-Offord. We are given a vector $x\in {\bf R}^d$ and $n$ other vectors $x_1,\ldots,x_n$. All of these vectors have length at least $1$. Now we consider all $2^n$ sums of the form $$\sum_{i=1}^n \epsilon_ix_i$$ where $\epsilon_i\in\{-1,1\}$ and the goal is to show that at most ${n\choose \lfloor n/2\rfloor}$ of these sums can be at a distance $\leq 1$ from $x$.

For $d=1$, we can assume that all the $x_i$ are positive by multiplying by $-1$ if necessary. For $A\subseteq [n]$, we let $$x_A = \sum_{i\in A} x_i - \sum_{i\notin A} x_i.$$ Let ${\cal F}$ be the set of all $A\subseteq [n]$ such that $|x_A - x| < 1$. Let $A$ be a proper subset of $B\subseteq [n]$ and consider $|x_A - x| + |x_B-x|$. By the triangle inequality, we have $$\eqalign{ |x_A - x| + |x_B - x|&\geq |x_B - x_A| \cr &= \Big| \sum_{i\in B} x_i -\sum_{i\in A}x_i + \sum_{i\notin A}x_i - \sum_{i\notin B} x_i\Big| \cr &= 2\Big|\sum_{i\in B\setminus A} x_i\Big|\cr &\geq 2 \Big(\sum_{i\in B\setminus A}x_i - \sum_{i\in B\setminus A} x_i \Big)\cr &= 2x_{B\setminus A}\cr &\geq 2. }$$ So one of $x_A$ and $x_B$ is not in ${\cal F}$, meaning we can apply Sperner's theorem. But in arbitrary dimension, the last bit does not work, because introducing the part of the sum that is subtracted, we could actually make the vector longer. There doesn't seem to be an analogue of assuming all the vectors are "positive", like we did at the beginning.

Instead, I'm guessing that the author intended us to use the Littlewood-Offord theorem statement found in the chapter. I'll rephrase it here:

Theorem 2. Let $B$ be a normed space and let $x_1, \ldots, x_n\in B$ be vectors of norm $\geq 1$. Consider all $2^n$ possible sums (where the null sum has value $0$). If we pick a subset $A$ of these sums such that every pair $x,y\in A$ is such that $|\!|x - y|\!| < 1$, then the subset must have size $\leq{n\choose \lfloor n/2\rfloor}$.

In fact, the author says that these two statements are equivalent, and indeed they seem like they should be, but I'm stuck on the details.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

After a rumble and a tumble, I think I got it figured out. (I followed a construction I found on Wikipedia, but the details still took a bit of work and I'm spelling them out here for completeness.) Fix some vectors $x_i$ as well as $x$, all of norm $\geq 1$, let $x_A$ be as above and let ${\cal F}$ be the family of $A\subseteq S = [n]$ such that $\lVert x_A -x\rVert < 1$. Let $f : {\bf R}^d\to {\bf R}^d$ be the affine transformation given by $$f(x) = {1\over 2}\Big(x+\sum_{i\in S} x_i\Big).$$ Note that for any $A\subseteq S$, $$\eqalign{ f(x_A) &= {1\over 2} \Big( \sum_{i\in A} x_i - \sum_{i\notin A} x_i + \sum_{i\in S} x_i\Big)\cr &= \sum_{i\in A} x_i;\cr }$$ these vectors are exactly of the form prescribed by Theorem 2. Let $x_A$ and $x_B$ be vectors such that $A,B\in \cal F$. By the triangle inequality applied with $x$ as the intermediate point, we have $\lVert x_A - x_B\rVert <2$. Now we can compute $$\eqalign{ \big\lVert f(x_A) - f(x_B)\big\rVert &= \bigg\lVert {1\over 2} \Big( \sum_{i\in A} x_i - \sum_{i\notin A} x_i + \sum_{i\in S} x_i\Big) - {1\over 2} \Big( \sum_{i\in B} x_i - \sum_{i\notin B} x_i + \sum_{i\in S} x_i\Big) \bigg\lVert \cr &= {1\over 2}\lVert x_A - x_B\rVert \cr &<1, }$$ so the set $\{ f(x_A) : A\in {\cal F}\}$ consists of vectors that are at distance $<1$ of each other. But this is a set of sums of $x_i$, and since $f$ is injective, it has exactly the same size as ${\cal F}$, so by Theorem 2, ${\cal F}$ must have had size $\leq {n \choose \lfloor n/2\rfloor}$. (In fact, $f$ is a bijection, so the argument can be reversed to show that the proposition is equivalent to Theorem 2.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .