Polynomials that vanish to high order on most of the hypercube

Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed and large with respect to , what is the minimum possible degree of a polynomial with such that has zeroes of multiplicity at least at all points in ? For , a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals . In this paper, we solve the problem for all , proving that the answer is . As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in such that each point in is covered by at least hyperplanes, but the point is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.