Covering Hypercube $mB^n$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913046864068608 |
|---|---|
| author | Huang, Zihao Wang, Miao Wang, Suijie |
| author_facet | Huang, Zihao Wang, Miao Wang, Suijie |
| contents | A celebrated result of Alon and Füredi gives a tight lower bound on the number of hyperplanes required to cover all points of the Boolean cube $B^n$ except the origin $\bm{0}$. Recent breakthroughs by Sauermann and Wigderson generalized this to the case where all points of $B^n \setminus \{\mathbf{0}\}$ are covered with multiplicities at least $k$. In this paper, we further extend their result by replacing the Boolean cube with the general hypercube $mB^n = \{0, 1, \dots, m\}^n$. \vspace{2mm}
Let $f_m(n, k)$ denote the minimum number of hyperplanes required to cover every point of $mB^n \setminus \{\mathbf{0}\}$ at least $k$ times while leaving the origin uncovered. Our primary contribution is a sharp extension of the Sauermann--Wigderson Combinatorial Nullstellensatz to the setting of $mB^n$. We determine a tight lower bound for the degree of polynomials that vanish with multiplicity at least $k$ at all points of $mB^n \setminus \{\mathbf{0}\}$ and have multiplicity less than $k$ at the origin. As an application, we establish the exact values $f_m(n, k)$ for $k=1,2$ and provide upper and lower bounds for $f_m(n, k)$ when $k \ge 3$ and $n\ge k-1$. The proofs involve a new construction of hyperplanes and a surprisingly elegant application of the Lagrange inversion formula in enumerative combinatorics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_14262 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Covering Hypercube $mB^n$ Huang, Zihao Wang, Miao Wang, Suijie Combinatorics 05D40, 05A19, 12D10, 52C17 A celebrated result of Alon and Füredi gives a tight lower bound on the number of hyperplanes required to cover all points of the Boolean cube $B^n$ except the origin $\bm{0}$. Recent breakthroughs by Sauermann and Wigderson generalized this to the case where all points of $B^n \setminus \{\mathbf{0}\}$ are covered with multiplicities at least $k$. In this paper, we further extend their result by replacing the Boolean cube with the general hypercube $mB^n = \{0, 1, \dots, m\}^n$. \vspace{2mm} Let $f_m(n, k)$ denote the minimum number of hyperplanes required to cover every point of $mB^n \setminus \{\mathbf{0}\}$ at least $k$ times while leaving the origin uncovered. Our primary contribution is a sharp extension of the Sauermann--Wigderson Combinatorial Nullstellensatz to the setting of $mB^n$. We determine a tight lower bound for the degree of polynomials that vanish with multiplicity at least $k$ at all points of $mB^n \setminus \{\mathbf{0}\}$ and have multiplicity less than $k$ at the origin. As an application, we establish the exact values $f_m(n, k)$ for $k=1,2$ and provide upper and lower bounds for $f_m(n, k)$ when $k \ge 3$ and $n\ge k-1$. The proofs involve a new construction of hyperplanes and a surprisingly elegant application of the Lagrange inversion formula in enumerative combinatorics. |
| title | Covering Hypercube $mB^n$ |
| topic | Combinatorics 05D40, 05A19, 12D10, 52C17 |
| url | https://arxiv.org/abs/2603.14262 |