Covering the hypercube, the uncertainty principle, and an interpolation formula
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909821706436608 |
|---|---|
| author | Ivanisvili, Paata Klein, Ohad Vershynin, Roman |
| author_facet | Ivanisvili, Paata Klein, Ohad Vershynin, Roman |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_13277 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Covering the hypercube, the uncertainty principle, and an interpolation formula Ivanisvili, Paata Klein, Ohad Vershynin, Roman Combinatorics Probability 06E30, 42C10 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$. |
| title | Covering the hypercube, the uncertainty principle, and an interpolation formula |
| topic | Combinatorics Probability 06E30, 42C10 |
| url | https://arxiv.org/abs/2310.13277 |