Covering the hypercube, the uncertainty principle, and an interpolation formula

Abstract

We show that the minimal number of skewed hyperplanes that cover the hypercube $\{0,1{\}}^n$ is at least $\frac{n}{2}+1$, and there are infinitely many $n$'s when the hypercube can be covered with $n-{\log }_2(n)+1$ skewed hyperplanes. The minimal covering problems are closely related to uncertainty principle on the hypercube, where we also obtain an interpolation formula for multilinear polynomials on ${\mathbb{R}}^n$ of degree less than $\lfloor n/m\rfloor$ by showing that its coefficients corresponding to the largest monomials can be represented as a linear combination of values of the polynomial over the points $\{0,1{\}}^n$ whose hamming weights are divisible by $m$.

Incorporates referee comments