Covering Hypercube $m{B}^n$

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 $\mathbf{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 $m{B}^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 $m{B}^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 $m{B}^n$. We determine a tight lower bound for the degree of polynomials that vanish with multiplicity at least $k$ at all points of $m{B}^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.