4
$\begingroup$

I found two different looking things being called the Littlewood-Offord theorem,

  1. If $\vec{a} \in \mathbb{R}^k \setminus 0$ and $t \in \mathbb{R}$ then there are $O(\frac{2^k}{\sqrt{k}})$ points $x \in \{1,-1\}^k$ such that $\vec{a}.\vec{x}=t$

  2. If $\vec{a} \in \mathbb{R}^k$ is such that at least $n$ of the $a_i$ have $\vert a_i \vert \geq 1$ then for $x \sim \{1,-1\}^k$ uniformly at random and $I$ an interval of length $2$ we have $Pr_x[ \vec{a}.\vec{x} \in I] \leq O(\frac{1}{\sqrt{n}})$

    • Can someone kindly explain if these two are related to each other or not? Is one derivable from the other?

    • Can someone give an expository (lecture notes) reference of the proof of the later version?

$\endgroup$
11
  • $\begingroup$ Do you mean to divide by the square root of the number of nonzero entries of $a$ in 1? Else I can take $a = (1,0,0,...)$ and $t = 1$ and then the $2^{k-1}$ solutions $x = (1,\star,\star,...)$ to $a\cdot x = t$ would contradict the claim for $k$ large. $\endgroup$
    – alpoge
    Jan 27, 2017 at 2:06
  • $\begingroup$ (Or did you mean $(\mathbb{R} - \{0\})^k$?) $\endgroup$
    – alpoge
    Jan 27, 2017 at 2:07
  • 1
    $\begingroup$ Anywho I think this works. Wlog since all the $a_i$ are nonzero they're all positive (absorb the sign into the $x_i$). Let $T:=\{S_x : a\cdot x = t\}$, where I've written S_x for the subset of $\{1,...,n\}$ where $x_i=1$. Claim: for every pair of distinct $S, S'\in T$ we do not have that $S\subseteq S'$. Proof: otherwise the respective $x,x'$ would have $a\cdot x' > a\cdot x$. OK, so we've found an antichain in the power set of $\{1,...,n\}$ (ordered with respect to inclusion) of the same size as the set of $x$'s we wanted to estimate. $\endgroup$
    – alpoge
    Jan 27, 2017 at 2:36
  • 1
    $\begingroup$ Sperner's theorem says that therefore $|T|\leq {n\choose \lfloor n/2\rfloor)}$. By Stirling this gives what you wanted. To prove Sperner, consider the set of permutations that send some prefix $\{1,...,k\}$ to a set inside our $T$. Claim: given such a permutation, you can recover the corresponding subset of $T$. (Note that I only said some prefix.) Proof: otherwise $\{1,...,k\}\subseteq \{1,...,k'\}$ would both be sent to subsets of $T$, with $k<k'$, contradiction. Thus the count of this subset of $S_n$ is $\sum_{S\in T} |S|! (n - |S|)!$, which is $\leq n!$ since it's in $S_n$. $\endgroup$
    – alpoge
    Jan 27, 2017 at 2:43
  • 2
    $\begingroup$ For the second claim you asked about, just fix the values of the $x_i$ outside the set where $a_i\geq 1$ (again you can assume all of the $a_i$ are positive) and run the above argument except now you've reduced to the case where all $a_i\geq 1$. Then instead of the $a\cdot x' > a\cdot x$ you get $a\cdot x' > a\cdot x + 2$, so both of them can't be in the same interval of length $2$. Otherwise the argument is the same. $\endgroup$
    – alpoge
    Jan 27, 2017 at 2:56

0

Your Answer

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