Polynomials that vanish to high order on most of the hypercube

article Polynomials that vanish to high order on most of the hypercube published yes Lisa Sauermann author Yuval Wigderson author 2d0023a0-1567-11f0-833d-d5c1e476d4b5 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. Wiley2022 eng Journal of the London Mathematical Society 0024-6107 1469-7750 2010.0007710.1112/jlms.12637 10632379-2402 yes L. Sauermann, Y. Wigderson, Journal of the London Mathematical Society 106 (2022) 2379–2402. Sauermann, Lisa, and Yuval Wigderson. “Polynomials That Vanish to High Order on Most of the Hypercube.” Journal of the London Mathematical Society. Wiley, 2022. <a href="https://doi.org/10.1112/jlms.12637">https://doi.org/10.1112/jlms.12637</a>. L. Sauermann and Y. Wigderson, “Polynomials that vanish to high order on most of the hypercube,” Journal of the London Mathematical Society, vol. 106, no. 3. Wiley, pp. 2379–2402, 2022. Sauermann, Lisa, and Yuval Wigderson. “Polynomials That Vanish to High Order on Most of the Hypercube.” Journal of the London Mathematical Society, vol. 106, no. 3, Wiley, 2022, pp. 2379–402, doi:<a href="https://doi.org/10.1112/jlms.12637">10.1112/jlms.12637</a>. Sauermann L, Wigderson Y. Polynomials that vanish to high order on most of the hypercube. Journal of the London Mathematical Society. 2022;106(3):2379-2402. doi:<a href="https://doi.org/10.1112/jlms.12637">10.1112/jlms.12637</a> Sauermann, L., & Wigderson, Y. (2022). Polynomials that vanish to high order on most of the hypercube. Journal of the London Mathematical Society. Wiley. <a href="https://doi.org/10.1112/jlms.12637">https://doi.org/10.1112/jlms.12637</a> Sauermann L, Wigderson Y. 2022. Polynomials that vanish to high order on most of the hypercube. Journal of the London Mathematical Society. 106(3), 2379–2402. 221602026-06-29T10:51:52Z2026-07-08T10:37:38Z