# Support size lower bound for $k$-wise uniform distribution

So I have this question which I can't seem to find a solution to:

Prove that if $X = (X_1, ... X_n)$ is $k$-wise uniform* and each $X_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \mathbf B(\frac{k}{2}, n)$, where $\mathbf B(r, n)$ is the number of words of weight at most $r$.

$*$ Where $k$-wise uniform means that, for each subset $S=\{i_1,\dots, i_s\}\subseteq [n]$ of size $s\leq k$, the distribution of $(X_{i_1},\dots,X_{i_s})$ is uniform.

• Isn't the constant distribution $\delta_{1^n}$ (i.e., $X_i = 1$ a.s. for every $i\in[n]$) $k$-wise independent for every $1\leq k\leq n$? – Clement C. Mar 23 '18 at 10:29
• no, it is not even 1-wise independent, k-wise independent means that if we look at a subset (every subset) of length k it will look uniform. – Itaysason Mar 24 '18 at 10:47
• That's only one of the possible definitions. One of the standard ones defines it as "every subset of at most k of the variables is mutually independent". (With yours, pairwise and 2-wise do not coincide.) – Clement C. Mar 24 '18 at 13:59
• For this question, I recommend using the term "k-wise uniform" instead of "k-wise independent". – Ravi Boppana Mar 24 '18 at 16:23
• @RaviBoppana and Itaysason: I have edited the OP that way, to make it clear the assumption implies uniformity. – Clement C. Mar 25 '18 at 16:51