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

Paata Ivanisvili¹ ; Ohad Klein² ; Roman Vershynin³

¹Kent State University
²Hebrew University of Jerusalem
³University of California, Irvine

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

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 the 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$.

Détail

DOI : 10.37236/12756

Classification : 06E30, 42C10