Search

Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed k⩾1$k\geqslant 1$ and n$n$ large with respect to k$k$, what is the minimum possible degree of a polynomial P∈R[x1,⋯,xn]$P\in \mathbb {R}[x_1,\dots ,x_n]$ with P(0,⋯,0)≠0$P(0,\dots ,0)\ne 0$ such that P$P$ has zeroes of multiplicity at least k$k$ at all points in {0,1}n∖{(0,⋯,0)}$\lbrace 0,1\rbrace ^n\setminus \lbrace (0,\dots ,0)\rbrace$? For k=1$k=1$, a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals n$n$. In this paper, we solve the problem for all k⩾2$k\geqslant 2$, proving that the answer is n+2k−3$n+2k-3$. As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in Rn$\mathbb {R}^n$ such that each point in {0,1}n∖{(0,⋯,0)}$\lbrace 0,1\rbrace ^n\setminus \lbrace (0,\dots ,0)\rbrace$ is covered by at least k$k$ hyperplanes, but the point (0,⋯,0)$(0,\dots ,0)$ is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics. [ABSTRACT FROM AUTHOR]