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.

  • $\begingroup$ 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$? $\endgroup$
    – Clement C.
    Commented Mar 23, 2018 at 10:29
  • $\begingroup$ 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. $\endgroup$
    – Itaysason
    Commented Mar 24, 2018 at 10:47
  • $\begingroup$ 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.) $\endgroup$
    – Clement C.
    Commented Mar 24, 2018 at 13:59
  • 3
    $\begingroup$ For this question, I recommend using the term "k-wise uniform" instead of "k-wise independent". $\endgroup$ Commented Mar 24, 2018 at 16:23
  • $\begingroup$ @RaviBoppana and Itaysason: I have edited the OP that way, to make it clear the assumption implies uniformity. $\endgroup$
    – Clement C.
    Commented Mar 25, 2018 at 16:51

1 Answer 1


I believe this question was answered positively in three independent papers:

C. R. Rao (1947), "Factorial experiments derivable from combinatorial arrangements of arrays", Journal of the Royal Statistical Society 9:1, 128-139.

B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky (1985), "The bit extraction problem or t-resilient functions", 26th IEEE Symposium on Foundations of Computer Science, 396-407.

N. Alon, L. Babai, and A. Itai (1986), "A fast and simple randomized algorithm for the maximal independent set problem", Journal of Algorithms 7:4, 567-583.


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.