Fetching the paper…

Reading the bibliography…

2020

Polynomials that vanish to high order on most of the hypercube

Sauermann, Lisa, Wigderson, Yuval

Original
PDF
Post on X

Understand

Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed $k\geq 1$ and $n$ large with respect to $k$, what is the minimum possible degree of a polynomial $P\in \mathbb{R}[x_1,\dots,x_n]$ with $P(0,\dots,0)\neq 0$ such that $P$ has zeroes of multiplicity at least $k$ at all points in $\{0,1\}^n\setminus \{(0,\dots,0)\}$? For $k=1$, a classical theorem of Alon and F\"uredi states that the minimum possible degree of such a polynomial equals $n$.

In this paper, we solve the problem for all $k\geq 2$, proving that the answer is $n+2k-3$.
As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in $\mathbb{R}^n$ such that each point in $\{0,1\}^n\setminus \{(0,\dots,0)\}$ is covered by at least $k$ hyperplanes, but the point $(0,\dots,0)$ is uncovered.
Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.

Polynomials that vanish to high order on most of the hypercube · Around

Built on

N. Alon and Z. Füredi, Covering the cube by affine hyperplanes
1993
Earlier work this paper cites.
P. Komjáth, Partitions of vector spaces
1994
Earlier work this paper cites.
N. Alon, Combinatorial Nullstellensatz
1999
Earlier work this paper cites.
S. Ball and O. Serra, Punctured combinatorial Nullstellensätze
2009
Earlier work this paper cites.
T. Koshy, Catalan numbers with applications
2009
Earlier work this paper cites.
J. Riordan, A note on Catalan parentheses
Original
2010
Earlier work this paper cites.

Similar

S. B. Ekhad and D. Zeilberger, Two quick proofs of a Catalan lemma needed by Lisa Sauermann and Yuval Wigderson
Original
2011
Cited alongside, same era.
G. Kós, T. Mészáros, and L. Rónyai, Some extensions of Alon’s Nullstellensatz
2011
Cited alongside, same era.
G. Kós and L. Rónyai, Alon’s Nullstellensatz for multisets
2012
Cited alongside, same era.
Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan, Extensions to the method of multiplicities, with applications to Kakeya sets and mergers
2013
Cited alongside, same era.
A. Bishnoi, P. L. Clark, A. Potukuchi, and J. Schmitt, On zeros of a polynomial in a finite grid
2018
Cited alongside, same era.

Then

G. Batzaya and G. Bayarmagnai, A generalized combinatorial Nullstellensatz for multisets
2020
Closest in time.
A. Clifton and H. Huang, On almost k k -covers of hypercubes
2020
Closest in time.
B. Bukh and T.-W. Chao, Sharp density bounds on the finite field Kakeya problem
2021
Closest in time.
K. Carde, The q q -golden ratio, Catalan numbers, and an identity of Sauermann–Wigderson
Original
2021
Closest in time.
B. Hanson and G, Petridis, Refined Estimates Concerning Sumsets Contained in the Roots of Unity
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…