# Polynomials that vanish to high order on most of the hypercube

Lisa Sauermann Department of Mathematics, Massachusetts Institute of
Technology, Cambridge, MA. Email<EMAIL_ADDRESS>This research was
supported by the National Science Foundation under Grant CCF-1900460 and under
Award DMS-1953772. Yuval Wigderson Department of Mathematics, Stanford
University, Stanford, CA. Email<EMAIL_ADDRESS>Research supported by
NSF GRFP Grant DGE-1656518.

###### Abstract

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üredi 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.

##  1 Introduction

Alon’s Combinatorial Nullstellensatz [1], which gives a non-vanishing
criterion for a polynomial on some grid of points under certain conditions,
has had applications to many problems in combinatorics. The following
statement due to Alon and Füredi [2] is a now classical example of an
application of the Combinatorial Nullstellensatz (even though it historically
predated it).

######  Theorem 1.1 (see [2]).

Let $n\geq 1$. Then any polynomial $P\in\mathbb{R}[x_{1},\dots,x_{n}]$ with
$P(0,\dots,0)\neq 0$ and such that $P$ has zeroes at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ has degree $\deg P\geq n$.

The example $P=(x_{1}-1)\dotsm(x_{n}-1)$ shows that the bound $\deg P\geq n$
is tight. Alon and Füredi [2] proved this theorem in order to solve a problem
of Komjáth [12] asking about the minimum possible number $m$ such that there
are $m$ hyperplanes in $\mathbb{R}^{n}$ covering all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, but not covering $(0,\dots,0)$. By
considering the product of the linear polynomials defining these hyperplanes,
Theorem 1.1 easily implies that at least $n$ hyperplanes are needed. As $n$
hyperplanes are also sufficient, the answer to Komjáth’s hyperplane problem is
$m=n$.

There has been a lot of work on finding generalizations of both the
Combinatorial Nullstellensatz [1] and of Alon and Füredi’s result [2] on
Komjáth’s hyperplane problem to higher vanishing or covering multiplicities
[3, 4, 8, 13, 14]. More generally, there is now a rich collection of higher-
multiplicity generalizations of related algebraic results. There are also
various combinatorial applications of such higher-multiplicity results, like
Stepanov’s method (see e.g. [11]) and the multiplicity Schwartz–Zippel lemma
(see e.g. [5, 6, 9]). In this spirit, it is natural to also ask for
generalizations of Theorem 1.1 to higher vanishing orders for the polynomial
$P$. This leads to the following problem.

######  Problem 1.2.

Let $k\geq 2$ and let $n$ be sufficiently large with respect to $k$. What is
the minimum degree that a polynomial $P\in\mathbb{R}[x_{1},\dots,x_{n}]$ can
have, if $P(0,\dots,0)\neq 0$ and if $P$ has zeroes of multiplicity at least
$k$ at all points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$?

As usual, we say that a polynomial $P\in\mathbb{R}[x_{1},\dots,x_{n}]$ has a
zero of multiplicity at least $k$ at a point $a\in\mathbb{R}^{n}$ if all
derivatives of $P$ up to order $k-1$ vanish at $a$. Note that $P(a)=0$ is
equivalent to $P$ having a zero of multiplicity at least $1$ at $a$.

Ball and Serra [3, Theorem 4.1] proved a lower bound of $\deg P\geq n+k-1$ for
Problem 1.2 (in fact, they proved a similar bound for more general grids
instead of just $\\{0,1\\}^{n}\subseteq\mathbb{R}^{n}$). This in particular
implies that the answer to Problem 1.2 is $n+1$ if $k=2$. Clifton and Huang
[8] proved that the answer to Problem 1.2 is $n+3$ if $k=3$, and they improved
the lower bound to $\deg P\geq n+k+1$ for $k\geq 4$. Clifton and Huang were
actually studying the generalization of Komjáth’s hyperplane problem [12]
mentioned above to higher covering multiplicities (where every point in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ needs to be covered by at least $k$
hyperplanes, while $(0,\ldots,0)$ must remain uncovered). Their approach was
to consider the product of the polynomials for all of the hyperplanes and to
prove a lower bound for the degree of this product. This naturally leads to
Problem 1.2, even though their lower bound results are not explicitly stated
in the setting of Problem 1.2.

In this paper, we resolve Problem 1.2, showing that the answer is $n+2k-3$.
This is the content of the following theorem.

######  Theorem 1.3.

Let $k\geq 2$ and $n\geq 2k-3$. Then any polynomial
$P\in\mathbb{R}[x_{1},\dots,x_{n}]$ with $P(0,\dots,0)\neq 0$ having zeroes of
multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ has degree $\deg P\geq n+2k-3$.
Furthermore, there exists such a polynomial $P$ with degree $\deg P=n+2k-3$.

Instead of demanding $P(0,\dots,0)\neq 0$, one can also ask a more general
version of Problem 1.2 where $P$ is required to have a zero of multiplicity
exactly $\ell$ at $(0,\dots,0)$ for some $\ell\in\\{0,\dots,k-1\\}$ (note that
for $\ell\geq k$, we cannot expect any interesting lower bounds on the degree
of $P$ for large $n$, as the example $P=x_{1}^{\ell}(x_{1}-1)^{k}$ with $\deg
P=\ell+k$ shows). Also note that the case $\ell=0$ corresponds to Problem 1.2
above. Our next theorem resolves this more general problem for $0\leq\ell\leq
k-2$.

######  Theorem 1.4.

Let $k\geq 2$ and $n\geq 2k-3$. Let $P\in\mathbb{R}[x_{1},\dots,x_{n}]$ be a
polynomial having zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and such that $P$ does not have a
zero of multiplicity at least $k-1$ at $(0,\dots,0)$. Then $P$ must have
degree $\deg P\geq n+2k-3$. Furthermore, for every $\ell=0,\dots,k-2$, there
exists a polynomial $P$ with degree $\deg P=n+2k-3$ having zeroes of
multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and such that $P$ has a zero of
multiplicity exactly $\ell$ at $(0,\dots,0)$.

Note that Theorem 1.4 implies Theorem 1.3. Indeed, it is clear that the first
part of Theorem 1.4 (giving the degree bound $\deg P\geq n+2k-3$) implies the
first part of Theorem 1.3. Furthermore, the second part of Theorem 1.3 is
equivalent to the second part of Theorem 1.4 for $\ell=0$.

Theorem 1.4 does not address the case where $P$ has a zero of multiplicity
exactly $k-1$ at $(0,\dots,0)$. This case turns out to have a slightly
different answer, as shown in the following theorem.

######  Theorem 1.5.

Let $k\geq 2$ and $n\geq 1$. Let $P\in\mathbb{R}[x_{1},\dots,x_{n}]$ be a
polynomial having zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and a zero of multiplicity exactly
$k-1$ at $(0,\dots,0)$. Then $P$ must have degree $\deg P\geq n+2k-2$.
Furthermore, there exists such a polynomial $P$ with degree $\deg P=n+2k-2$.

Note that Theorem 1.5 is also true for $k=1$, and is identical to Alon and
Füredi’s result in Theorem 1.1. Theorem 1.5 is actually significantly easier
to prove than Theorems 1.3 and 1.4.

As an application of Theorem 1.3, we can improve a result of Clifton and Huang
[8] concerning collections of hyperplanes in $\mathbb{R}^{n}$ such that every
point in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ is covered by at least $k$
of these hyperplanes, but no hyperplane contains $(0,\dots,0)$. Generalizing
Komjáth’s hyperplane problem [12], Clifton and Huang studied the minimum
possible size of such a collection of hyperplanes, where $k$ is fixed and $n$
is assumed to be sufficiently large with respect to $k$. They proved that the
minimum size of such a collection of hyperplanes is $n+1$ if $k=2$ and $n+3$
if $k=3$. Furthermore, for $k\geq 4$ they proved a lower bound of $n+k+1$ for
the size of any such collection of hyperplanes. As an immediate corollary of
Theorem 1.3, we can recover their lower bound for $k\in\\{2,3,4\\}$ and
improve it for $k\geq 5$.

######  Corollary 1.6.

Fix $k\geq 2$ and let $n\geq 2k-3$. Consider a collection of hyperplanes in
$\mathbb{R}^{n}$ such that every point in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ is covered by at least $k$ of these
hyperplanes, but no hyperplane contains $(0,\dots,0)$. Then this collection
must consist of at least $n+2k-3$ hyperplanes.

Indeed, Corollary 1.6 follows from Theorem 1.3 by taking the linear
polynomials corresponding to all of the hyperplanes, and observing that their
product $P$ satisfies the assumptions in Theorem 1.3. This was also the
approach taken by Clifton and Huang [8] to prove their lower bounds for the
size of any such collection of hyperplanes. Clifton and Huang obtained lower
bounds on the degree of the resulting product polynomial $P$ by using a
punctured higher-multiplicity version of the Combinatorial Nullstellensatz due
to Ball and Serra [3] and a relatively involved analysis of the conditions on
the coefficients of the polynomial $P$ imposed by its vanishing properties. As
mentioned above, their arguments also apply in the setting of Problem 1.2, but
their bounds on the degree of $P$ are weaker than the lower bound we obtain in
Theorem 1.3.

It is still an interesting open problem to determine the minimum possible size
of a collection of hyperplanes as in Corollary 1.6 for $k\geq 4$ (and $n$
sufficiently large with respect to $k$). While Corollary 1.6 gives the best
currently known lower bound, the best known upper bound is $n+\binom{k}{2}$,
obtained by a construction due to Clifton and Huang [8]. They conjectured that
this upper bound is tight if $n$ is sufficiently large with respect to $k$;
see also the discussion in Subsection 4.1 in the concluding remarks.

While Theorem 1.5 is relatively easy to prove, the proof of Theorem 1.4 takes
up most of this paper. Indeed, the proof of Theorem 1.5 uses only fairly
standard techniques related to the Combinatorial Nullstellensatz and its
generalizations (like iteratively subtracting appropriate monomials in order
to put a given polynomial in some “canonical form”). Proving Theorem 1.4 is,
however, significantly harder. With various linear algebra arguments, one can
reduce the desired statement to showing that a certain linear map is an
isomorphism (see Corollary 2.11 below). In order to show surjectivity of this
linear map, we analyze the representations of certain symmetric polynomials in
terms of power sum symmetric polynomials. We then need to show that a certain
coefficient of such a representation is non-zero. Surprisingly, it turns out
that this coefficient is actually equal (up to sign) to a Catalan number. The
fact that enumerative combinatorics arguments appear in our proof is maybe
somewhat unexpected, given that Problem 1.2 is a problem in extremal
combinatorics.

Notation. Throughout this paper, we work with the usual convention that the
binomial coefficients $\binom{n}{m}$ are defined for all integers $m$ and
$n\geq 0$, but we have $\binom{n}{m}=0$ unless $0\leq m\leq n$. The variables
$i,j,k,\ell,m,n,r,s,t$ always refer to integers.

##  2 Proof of Theorems 1.4 and 1.5

In this section we prove Theorem 1.5, and we also prove Theorem 1.4 apart from
the proof of Proposition 2.9 below, which we postpone to Section 3. Recall
that Theorem 1.4 implies Theorem 1.3.

For $k\geq 2$, let us say that a polynomial
$P\in\mathbb{R}[x_{1},\dots,x_{n}]$ is _$k$ -reduced_, if $\deg P\leq n+2k-3$
and if $P$ does not contain any monomials divisible by $x_{i_{1}}^{2}\dotsm
x_{i_{k}}^{2}$ for some (not necessarily distinct) indices
$i_{1},\dots,i_{k}\in\\{1,\dots,n\\}$ (in other words, no monomial of $P$ is
divisible by a product of $k$ squares of variables). Let
$U_{k}\subseteq\mathbb{R}[x_{1},\dots,x_{n}]$ be the vector space of all
$k$-reduced polynomials.

Before starting the proofs of Theorems 1.4 and 1.5, we will show a sequence of
claims. The first claim shows that in order to prove the first part of
Theorems 1.4 and 1.5, we can restrict ourselves to considering $k$-reduced
polynomials $P$. Furthermore, it will be easy to derive the second part of
Theorem 1.4 from this claim.

######  Claim 2.1.

Let $k\geq 2$ and $n\geq 1$. For every polynomial
$Q\in\mathbb{R}[x_{1},\dots,x_{n}]$, we can find a polynomial $P\in U_{k}$
with $\deg P\leq\deg Q$ such that the difference $Q-P$ has zeroes of
multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at least
$k-1$ at $(0,\dots,0)$. Furthermore, if $\deg Q\leq n+2k-3$, then we can even
choose $P\in U_{k}$ with $\deg P\leq\deg Q$ such that the difference $Q-P$ has
zeroes of multiplicity at least $k$ at all points in $\\{0,1\\}^{n}$.

###### Proof.

Fix $k\geq 2$ and $n\geq 1$. Note that for any polynomial
$Q\in\mathbb{R}[x_{1},\dots,x_{n}]$, when defining a polynomial
$Q^{*}\in\mathbb{R}[x_{1},\dots,x_{n}]$ by either

  * (a)

$Q^{*}=Q-a\cdot x_{i_{1}}(x_{i_{1}}-1)\dotsm x_{i_{k}}(x_{i_{k}}-1)\cdot
x_{1}^{m_{1}}\dotsm x_{n}^{m_{n}}$ with $a\in\mathbb{R}$, with non-negative
integers $m_{1},\dots,m_{n}$ and with (not necessarily distinct) indices
$i_{1},\dots,i_{k}\in\\{1,\dots,n\\}$, or

  * (b)

$Q^{*}=Q-a\cdot x_{i_{1}}(x_{i_{1}}-1)\dotsm
x_{i_{k-1}}(x_{i_{k-1}}-1)\cdot(x_{1}-1)\dotsm(x_{n}-1)$ with $a\in\mathbb{R}$
and with (not necessarily distinct) indices
$i_{1},\dots,i_{k-1}\in\\{1,\dots,n\\}$,

the difference $Q-Q^{*}$ has zeroes of multiplicity at least $k$ at all points
in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at
least $k-1$ at $(0,\dots,0)$. Furthermore, if we define $Q^{*}$ as in (a),
then $Q-Q^{*}$ even has zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}$.

Let us say that a monomial in $\mathbb{R}[x_{1},\dots,x_{n}]$ is _bad_ if it
is of the form $x_{i_{1}}^{2}\dotsm x_{i_{k}}^{2}\cdot x_{1}^{m_{1}}\dotsm
x_{n}^{m_{n}}$ with non-negative integers $m_{1},\dots,m_{n}$ and with (not
necessarily distinct) indices $i_{1},\dots,i_{k}\in\\{1,\dots,n\\}$, or of the
form $x_{i_{1}}^{2}\dotsm x_{i_{k-1}}^{2}\cdot x_{1}\dotsm x_{n}$ with (not
necessarily distinct) indices $i_{1},\dots,i_{k-1}\in\\{1,\dots,n\\}$.

Whenever $Q\in\mathbb{R}[x_{1},\dots,x_{n}]$ contains a bad monomial, we can
apply one of the steps (a) or (b) above, replacing the bad monomial with
monomials of lower degree. We can repeatedly perform these steps, always
replacing a bad monomial of maximum degree by lower-degree monomials, until we
arrive at a polynomial $P\in\mathbb{R}[x_{1},\dots,x_{n}]$ which does not
contain any bad monomials. Indeed, note that when repeatedly applying these
steps, the process must terminate at some point (since at every step either
the maximum degree of the occurring bad monomials decreases or the maximum
degree of the occurring bad monomials remains unchanged but the number of
different bad monomials of this maximum degree decreases).

By construction of $P$, we have $\deg P\leq\deg Q$ and the difference $Q-P$
has zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at least
$k-1$ at $(0,\dots,0)$. Let us now check that $P\in U_{k}$, i.e. that $P$ is
$k$-reduced and has degree $\deg P\leq n+2k-3$.

Recall that $P$ does not contain any bad monomials. This means in particular
that $P$ does not have any monomials which are divisible by
$x_{i_{1}}^{2}\dotsm x_{i_{k}}^{2}$ for some (not necessarily distinct)
indices $i_{1},\dots,i_{k}\in\\{1,\dots,n\\}$. Note that this already implies
that $\deg P\leq n+2k-2$. Furthermore, if $P$ had a monomial of degree
$n+2k-2$, then this monomial would need to be of the form $x_{i_{1}}^{2}\dotsm
x_{i_{k-1}}^{2}\cdot x_{1}\dotsm x_{n}$ with (not necessarily distinct)
indices $i_{1},\dots,i_{k-1}\in\\{1,\dots,n\\}$. But such a monomial is also
bad, and therefore we must have $\deg P\leq n+2k-3$. This proves that $P\in
U_{k}$.

Finally, for the second part of the claim, note that if we have $\deg Q\leq
n+2k-3$, then throughout the process of obtaining $P$ from $Q$ all polynomials
have degree at most $n+2k-3$ and we therefore never apply step (b). This means
that we will only perform step (a), and hence $Q-P$ has zeroes of multiplicity
at least $k$ at all points in $\\{0,1\\}^{n}$. ∎

For $n\geq 1$ and $t\geq 1$, let us define $M_{t}(n)$ to be the number of
$n$-tuples $(m_{1},\dots,m_{n})$ of non-negative integers with
$m_{1}+\dots+m_{n}<t$. We remark that $M_{t}(n)=\binom{n+t-1}{n}$, but we will
not use this formula. Note that for a polynomial
$P\in\mathbb{R}[x_{1},\dots,x_{n}]$ there are precisely $M_{t}(n)$ different
ways to form a derivative of $P$ of order less than $t$.

We will be using various dimension-counting arguments. The following claim
expresses the dimension of the vector space $U_{k}$ in terms of the numbers
$M_{t}(n)$ we just defined.

######  Claim 2.2.

Let $k\geq 2$ and $n\geq 1$. Then the vector space
$U_{k}\subseteq\mathbb{R}[x_{1},\dots,x_{n}]$ has dimension $\dim
U_{k}=(2^{n}-1)\cdot M_{k}(n)+M_{k-1}(n)$.

###### Proof.

The dimension of the vector space $U_{k}$ equals the number of monomials in
$\mathbb{R}[x_{1},\dots,x_{n}]$ of degree at most $n+2k-3$ which are not
divisible by $x_{i_{1}}^{2}\dotsm x_{i_{k}}^{2}$ for any (not necessarily
distinct) indices $i_{1},\dots,i_{k}\in\\{1,\dots,n\\}$. In other words, $\dim
U_{k}$ is the number of monomials of the form $x_{1}^{2m_{1}+r_{1}}\dotsm
x_{n}^{2m_{n}+r_{n}}$ with non-negative integers $(m_{1},\dots,m_{n})$ with
$m_{1}+\dots+m_{n}<k$ and $r_{1},\dots,r_{n}\in\\{0,1\\}$ such that
$(2m_{1}+r_{1})+\dots+(2m_{n}+r_{n})\leq n+2k-3$. If $r_{1}+\dots+r_{n}\leq
n-1$, then there are precisely $M_{k}(n)$ choices for $(m_{1},\dots,m_{n})$.
But if $r_{1}=\dots=r_{n}=1$, then we must have $2m_{1}+\dots+2m_{n}\leq
2k-3$, which (for non-negative integers $m_{1},\dots,m_{n}$) is equivalent to
$m_{1}+\dots+m_{n}<k-1$. Hence, in this case, there are only $M_{k-1}(n)$
choices for $(m_{1},\dots,m_{n})$. All in all we obtain $\dim
U_{k}=(2^{n}-1)\cdot M_{k}(n)+M_{k-1}(n)$, as desired. ∎

######  Claim 2.3.

Let $k\geq 2$ and $n\geq 1$, and let $N=(2^{n}-1)\cdot M_{k}(n)+M_{k-1}(n)$.
Consider the linear map $\psi_{k}:U_{k}\to\mathbb{R}^{N}$ sending each
polynomial $P\in U_{k}$ to the $N$-tuple consisting of the derivatives of $P$
of order less than $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and all the derivatives of $P$ of
order less than $k-1$ at $(0,\dots,0)$. Then $\psi_{k}:U_{k}\to\mathbb{R}^{N}$
is an isomorphism.

###### Proof.

By Claim 2.2 we have $\dim U_{k}=(2^{n}-1)\cdot M_{k}(n)+M_{k-1}(n)=N$, so it
suffices to prove that the linear map $\psi_{k}:U_{k}\to\mathbb{R}^{N}$ is
surjective. The surjectivity of $\psi_{k}$ follows from Claim 2.1: indeed, for
any $N$-tuple $\alpha\in\mathbb{R}^{N}$, we can easily construct a (high-
degree) polynomial $Q\in\mathbb{R}[x_{1},\dots,x_{n}]$ such that the
derivatives of $Q$ of order less than $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and the derivatives of $Q$ of order
less than $k-1$ at $(0,\dots,0)$ form precisely the $N$-tuple $\alpha$. For
example, one can take

$Q=\sum\frac{\alpha_{(a_{1},\dots,a_{n}),(m_{1},\dots,m_{n})}}{m_{1}!\dotsm
m_{n}!}\cdot(x_{1}-a_{1})^{m_{1}}\dotsm(x_{n}-a_{n})^{m_{n}}\cdot((x_{1}-a_{1})^{2k}-1)^{2k}\dotsm((x_{n}-a_{n})^{2k}-1)^{2k},$

where the sum is over all entries
$\alpha_{(a_{1},\dots,a_{n}),(m_{1},\dots,m_{n})}$ of $\alpha$ (which
correspond to conditions of the form
$(\partial_{x_{1}})^{m_{1}}\dots(\partial_{x_{n}})^{m_{n}}Q(a_{1},\dots,a_{n})=\alpha_{(a_{1},\dots,a_{n}),(m_{1},\dots,m_{n})}$
with $(a_{1},\dots,a_{n})\in\\{0,1\\}^{n}$). Now, by Claim 2.1 there exists a
polynomial $P\in U_{k}$ where this $N$-tuple of derivatives agrees with the
$N$-tuple for $Q$. Hence $\psi_{k}(P)=\alpha$. ∎

######  Corollary 2.4.

Let $k\geq 2$ and $n\geq 1$. For every polynomial
$Q\in\mathbb{R}[x_{1},\dots,x_{n}]$ there is at most one polynomial $P\in
U_{k}$ such that $Q-P$ has zeroes of multiplicity at least $k$ at all points
in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at
least $k-1$ at $(0,\dots,0)$. In particular, the polynomial $P$ in Claim 2.1
is unique.

###### Proof.

Suppose that for some polynomial $Q\in\mathbb{R}[x_{1},\dots,x_{n}]$ there
were two different polynomials $P,P^{*}\in U_{k}$ with the desired properties.
Then the non-zero polynomial $P-P^{*}\in U_{k}$ would have zeroes of
multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at least
$k-1$ at $(0,\dots,0)$, and would therefore be mapped to
$(0,0,\dots,0)\in\mathbb{R}^{N}$ under the isomorphism
$\psi_{k}:U_{k}\to\mathbb{R}^{N}$ in Claim 2.3. This is a contradiction. ∎

With these preparations, we are now ready to prove Theorem 1.5.

###### Proof of Theorem 1.5.

Suppose for contradiction that there is a polynomial
$Q\in\mathbb{R}[x_{1},\dots,x_{n}]$ of degree $\deg Q\leq n+2k-3$ having
zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and a zero of multiplicity exactly
$k-1$ at $(0,\dots,0)$. By the second part of Claim 2.1, there is a polynomial
$P\in U_{k}$ also having zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and a zero of multiplicity exactly
$k-1$ at $(0,\dots,0)$. In particular, $P$ is not the zero polynomial.
However, under the isomorphism $\psi_{k}:U_{k}\to\mathbb{R}^{N}$ in Claim 2.3,
the polynomial $P$ is mapped to $(0,0,\dots,0)\in\mathbb{R}^{N}$ (recall that
the derivatives of order $k-1$ at $(0,\dots,0)$ are not recorded by
$\psi_{k}$). This is a contradiction.

For the second part of the theorem, note that the polynomial

$P(x_{1},\dots,x_{n})=x_{1}^{k-1}(x_{1}-1)^{k-1}\cdot(x_{1}-1)\dotsm(x_{n}-1)$

has degree $\deg P=n+2k-2$ and satisfies the desired conditions. ∎

It remains to prove Theorem 1.4. The second part of Theorem 1.4 (concerning
the existence of $P$ with $\deg P=n+2k-3$ with the desired conditions) is a
direct consequence of Claim 2.1, as we will see below. However, the first part
of Theorem 1.4 is much more challenging.

For $k\geq 2$, let $V_{k}\subseteq
U_{k}\subseteq\mathbb{R}[x_{1},\dots,x_{n}]$ be the vector space of all
$k$-reduced polynomials which have zeroes of multiplicity at least $k$ at all
points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$. In order to prove the
first part of Theorem 1.4, our goal will be to show that all non-zero
polynomials $P\in V_{k}$ have degree $n+2k-3$. We continue with our sequence
of claims.

######  Claim 2.5.

Let $k\geq 2$ and $n\geq 1$. Then the vector space
$V_{k}\subseteq\mathbb{R}[x_{1},\dots,x_{n}]$ has dimension $M_{k-1}(n)$.

###### Proof.

Note that $V_{k}$ consists precisely of those polynomials in $U_{k}$ which are
mapped to $N$-tuples under the isomorphism $\psi_{k}:U_{k}\to\mathbb{R}^{N}$
in Claim 2.3 where the first $(2^{n}-1)\cdot M_{k}(n)$ entries are zero. Since
the subspace of such $N$-tuples has dimension $N-(2^{n}-1)\cdot
M_{k}(n)=M_{k-1}(n)$, the subspace $V_{k}\subseteq U_{k}$ also has dimension
$M_{k-1}(n)$. ∎

######  Claim 2.6.

Let $k\geq 3$ and $n\geq 1$. Then for each $j\in\\{1,\dots,n\\}$ and each
polynomial $P\in V_{k-1}$, we have $x_{j}(x_{j}-1)\cdot P\in V_{k}$.

###### Proof.

Recall that $P\in V_{k-1}\subseteq U_{k-1}$ is $(k-1)$-reduced, meaning that
$\deg P\leq n+2k-5$ and no monomial of $P$ is divisible by
$x_{i_{1}}^{2}\dotsm x_{i_{k-1}}^{2}$ for any (not necessarily distinct)
indices $i_{1},\dots,i_{k-1}\in\\{1,\dots,n\\}$. Then clearly the polynomial
$x_{j}(x_{j}-1)\cdot P$ has degree at most $n+2k-3$, and it is also not hard
to see that no monomial of $x_{j}(x_{j}-1)\cdot P$ is divisible by
$x_{i_{1}}^{2}\dotsm x_{i_{k}}^{2}$ for any (not necessarily distinct) indices
$i_{1},\dots,i_{k}\in\\{1,\dots,n\\}$. Hence $x_{j}(x_{j}-1)\cdot P\in U_{k}$.

Since $P\in V_{k-1}$, the polynomial $P$ has zeroes of multiplicity at least
$k-1$ at all points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$. Hence
$x_{j}(x_{j}-1)\cdot P$ has zeroes of multiplicity at least $k$ at all these
points, and we can conclude that $x_{j}(x_{j}-1)\cdot P\in V_{k}$. ∎

Now, in order to show that all non-zero polynomials $P\in V_{k}$ have degree
$n+2k-3$, let us consider the linear map
$\varphi_{k}:V_{k}\to\mathbb{R}[x_{1},\dots,x_{n}]$ sending each polynomial in
$V_{k}$ to its homogeneous degree $n+2k-3$ part. Our goal is to show that this
map is injective. To show this, it is sufficient to prove that the image
$\varphi_{k}(V_{k})$ has dimension $\dim V_{k}=M_{k-1}(n)$.

Let $W_{k}\subseteq\mathbb{R}[x_{1},\dots,x_{n}]$ be the subspace spanned by
all polynomials of the form

$x_{1}\dotsm x_{n}\cdot(x_{1}^{m}+\dots+x_{n}^{m})\cdot x_{1}^{2d_{1}}\dotsm
x_{n}^{2d_{n}}$ (2.1)

for non-negative integers $(m,d_{1},\dots,d_{n})$ with
$m+2(d_{1}+\dots+d_{n})=2k-3$. Note that all polynomials in $W_{k}$ are
homogeneous of degree $n+2k-3$. We will later show that
$\varphi_{k}(V_{k})=W_{k}$.

######  Claim 2.7.

Let $k\geq 2$ and $n\geq k-1$. Then the polynomials in (2.1) form a basis of
$W_{k}$.

###### Proof.

By definition of $W_{k}$, the polynomials in (2.1) span $W_{k}$. It remains to
show that these polynomials are linearly independent. Since we can divide all
the polynomials by $x_{1}\dotsm x_{n}$, it suffices to show that the
polynomials of the form

$Q_{m,d_{1},\dots,d_{n}}=(x_{1}^{m}+\dots+x_{n}^{m})\cdot x_{1}^{2d_{1}}\dotsm
x_{n}^{2d_{n}}$

for non-negative integers $(m,d_{1},\dots,d_{n})$ with
$m+2(d_{1}+\dots+d_{n})=2k-3$ are linearly independent.

Note that for each such polynomial $Q_{m,d_{1},\dots,d_{n}}$ we have that $m$
is odd and that $d_{1}+\dots+d_{n}\leq k-2<n$. Hence all monomials of
$Q_{m,d_{1},\dots,d_{n}}$ have exactly one variable with an odd exponent, this
odd exponent is always at least $m$, and there exists some monomial where the
odd exponent is equal to $m$ (namely each of the monomials $x_{i}^{m}\cdot
x_{1}^{2d_{1}}\dotsm x_{n}^{2d_{n}}$ for those $i\in\\{1,\dots,n\\}$ with
$d_{i}=0$, which must exist since $d_{1}+\dots+d_{n}<n$).

Now suppose we had a linear dependence relationship

$\sum_{(m,d_{1},\dots,d_{n})}\lambda_{m,d_{1},\dots,d_{n}}Q_{m,d_{1},\dots,d_{n}}=0$

for some coefficients $\lambda_{m,d_{1},\dots,d_{n}}\in\mathbb{R}$ not all of
which are zero. Then let $m^{*}$ be the minimum value of $m$ for which some
coefficient $\lambda_{m,d_{1},\dots,d_{n}}$ is non-zero (and note that $m^{*}$
is odd, since $m$ is always odd). Furthermore, fix $i\in\\{1,\dots,n\\}$ such
that we have $\lambda_{m,d_{1},\dots,d_{n}}\neq 0$ for some
$(m,d_{1},\dots,d_{n})$ with $m=m^{*}$ and $d_{i}=0$.

Now, in the polynomials $Q_{m,d_{1},\dots,d_{n}}$ with
$\lambda_{m,d_{1},\dots,d_{n}}\neq 0$, all monomials have exactly one variable
with an odd exponent, and this odd exponent is always at least $m^{*}$. Let us
consider all the monomials where $x_{i}$ has exponent $m^{*}$. These monomials
can only appear in polynomials $Q_{m,d_{1},\dots,d_{n}}$ with
$\lambda_{m,d_{1},\dots,d_{n}}\neq 0$ where $m=m^{*}$ and $d_{i}=0$. But note
that each such polynomial contains precisely one monomial where $x_{i}$ has
exponent $m=m^{*}$, namely the monomial $x_{i}^{m^{*}}\cdot
x_{1}^{2d_{1}}\dotsm x_{n}^{2d_{n}}$. Hence these monomials cannot cancel out
between different polynomials $Q_{m,d_{1},\dots,d_{n}}$ with
$\lambda_{m,d_{1},\dots,d_{n}}\neq 0$. Thus, a linear dependence relationship
between the polynomials $Q_{m,d_{1},\dots,d_{n}}$ is not possible. ∎

######  Corollary 2.8.

Let $k\geq 2$ and $n\geq k-1$. Then the vector space
$W_{k}\subseteq\mathbb{R}[x_{1},\dots,x_{n}]$ has dimension $M_{k-1}(n)$.

###### Proof.

By Claim 2.7, the dimension of $W_{k}$ equals the number of polynomials of the
form as in (2.1), i.e. the number of choices of non-negative integers
$(m,d_{1},\dots,d_{n})$ with $m+2(d_{1}+\dots+d_{n})=2k-3$. We must have
$d_{1}+\dots+d_{n}<k-1$. So there are $M_{k-1}(n)$ possibilities to choose
$(d_{1},\dots,d_{n})$, and for each of them $m=2k-3-2(d_{1}+\dots+d_{n})$ is
uniquely determined. ∎

A key step in the proof of Theorem 1.4 is to prove the following proposition,
from which we will deduce that the map
$\varphi_{k}:V_{k}\to\mathbb{R}[x_{1},\dots,x_{n}]$ is injective.

######  Proposition 2.9.

Let $k\geq 2$ and $n\geq 2k-3$. Then there exists a polynomial $P\in V_{k}$
such that the homogeneous degree $n+2k-3$ part $\varphi_{k}(P)$ of $P$
satisfies $\varphi_{k}(P)\in W_{k}$ as well as the following condition: if we
write $\varphi_{k}(P)\in W_{k}$ in terms of the basis in (2.1), then the
coefficient of the basis element $x_{1}\dotsm
x_{n}\cdot(x_{1}^{2k-3}+\dots+x_{n}^{2k-3})$ is non-zero.

We postpone the proof of Proposition 2.9 to Section 3. The proposition implies
the following corollaries.

######  Corollary 2.10.

Let $k\geq 2$ and $n\geq 2k-3$. Then we have
$W_{k}\subseteq\varphi_{k}(V_{k})$.

###### Proof.

We prove the corollary by induction on $k$. For the base case $k=2$ note that
the space $W_{2}$ is the one-dimensional space spanned by the polynomial
$x_{1}\dotsm x_{n}\cdot(x_{1}+\dots+x_{n})$. By Proposition 2.9 for $k=2$,
there exists a polynomial $P\in V_{2}$ such that $\varphi_{2}(P)\in W_{2}$ is
a non-zero scalar multiple of $x_{1}\dotsm x_{n}\cdot(x_{1}+\dots+x_{n})$.
This shows that $W_{2}\subseteq\varphi_{2}(V_{2})$.

Now let $k\geq 3$ and assume that we have already shown that
$W_{k-1}\subseteq\varphi_{k-1}(V_{k-1})$. Let $W_{k}^{\prime}\subseteq W_{k}$
be the subspace spanned by all polynomials of the form (2.1) with
$d_{1}+\dots+d_{n}\geq 1$. In other words, $W_{k}^{\prime}\subseteq W_{k}$ is
spanned by all of the form (2.1) except the polynomial $x_{1}\dotsm
x_{n}\cdot(x_{1}^{2k-3}+\dots+x_{n}^{2k-3})$. Note that $\dim
W_{k}^{\prime}=\dim W_{k}-1$.

Let us first show that $W_{k}^{\prime}\subseteq\varphi_{k}(V_{k})$. So fix a
polynomial $x_{1}\dotsm x_{n}\cdot(x_{1}^{m}+\dots+x_{n}^{m})\cdot
x_{1}^{2d_{1}}\dotsm x_{n}^{2d_{n}}$ of the form (2.1) where
$d_{1}+\dots+d_{n}\geq 1$. Now, let $j\in\\{1,\dots,n\\}$ be chosen such that
$d_{j}\geq 1$. Note that then (using the induction hypothesis
$W_{k-1}\subseteq\varphi_{k-1}(V_{k-1})$) we have

$x_{1}\dotsm x_{n}\cdot(x_{1}^{m}+\dots+x_{n}^{m})\cdot x_{1}^{2d_{1}}\dotsm
x_{j-1}^{2d_{j-1}}x_{j}^{2d_{j}-2}x_{j+1}^{2d_{j+1}}\dotsm x_{n}^{2d_{n}}\in
W_{k-1}\subseteq\varphi_{k-1}(V_{k-1}).$

Hence there exists a polynomial $P^{*}\in V_{k-1}$ of degree $n+2k-5$ whose
homogeneous degree $n+2k-5$ part is $\varphi_{k-1}(P^{*})=x_{1}\dotsm
x_{n}\cdot(x_{1}^{m}+\dots+x_{n}^{m})\cdot x_{1}^{2d_{1}}\dotsm
x_{j-1}^{2d_{j-1}}x_{j}^{2d_{j}-2}x_{j+1}^{2d_{j+1}}\dotsm x_{n}^{2d_{n}}$. By
Claim 2.6 we have $x_{j}(x_{j}-1)\cdot P^{*}\in V_{k}$, and note that the
homogeneous degree $n+2k-3$ part of $x_{j}(x_{j}-1)\cdot P^{*}$ is precisely
$x_{j}^{2}\cdot\varphi_{k-1}(P^{*})=x_{1}\dotsm
x_{n}\cdot(x_{1}^{m}+\dots+x_{n}^{m})\cdot x_{1}^{2d_{1}}\dotsm
x_{n}^{2d_{n}}$. Hence $\varphi_{k}$ maps the polynomial $x_{j}(x_{j}-1)\cdot
P^{*}\in V_{k}$ to $x_{1}\dotsm x_{n}\cdot(x_{1}^{m}+\dots+x_{n}^{m})\cdot
x_{1}^{2d_{1}}\dotsm x_{n}^{2d_{n}}$. This establishes that
$W_{k}^{\prime}\subseteq\varphi_{k}(V_{k})$.

Thus, $\varphi_{k}(V_{k})\cap W_{k}$ is a subspace of $W_{k}$ with
$W_{k}^{\prime}\subseteq\varphi_{k}(V_{k})\cap W_{k}\subseteq W_{k}$. Now,
Proposition 2.9 states that there exists a polynomial $P\in V_{k}$ with
$\varphi_{k}(P)\in W_{k}$ and $\varphi_{k}(P)\not\in W_{k}^{\prime}$. Hence
$\varphi_{k}(V_{k})\cap W_{k}\neq W_{k}^{\prime}$. Since $\dim
W_{k}^{\prime}=\dim W_{k}-1$, this implies that $\varphi_{k}(V_{k})\cap
W_{k}=W_{k}$ and consequently $W_{k}\subseteq\varphi_{k}(V_{k})$. ∎

######  Corollary 2.11.

Let $k\geq 2$ and $n\geq 2k-3$. Then $\varphi_{k}(V_{k})=W_{k}$, and the
linear map $\varphi_{k}:V_{k}\to W_{k}$ is an isomorphism.

###### Proof.

Recall that $\dim V_{k}=M_{k-1}(n)=\dim W_{k}$ by Claim 2.5 and Corollary 2.8.
Furthermore recall that by Corollary 2.10 we have
$W_{k}\subseteq\varphi_{k}(V_{k})$. Since $\dim\varphi_{k}(V_{k})\leq\dim
V_{k}=\dim W_{k}$, we must have $\varphi_{k}(V_{k})=W_{k}$ and the linear map
$\varphi_{k}:V_{k}\to W_{k}$ must be an isomorphism. ∎

Using Corollary 2.11, we are now ready to prove Theorem 1.4.

###### Proof of Theorem 1.4.

Fix $k\geq 2$ and $n\geq 2k-3$, and let $Q\in\mathbb{R}[x_{1},\dots,x_{n}]$ be
a polynomial having zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and such that $Q$ does not have a
zero of multiplicity at least $k-1$ at $(0,\dots,0)$. We need to show that
$\deg Q\geq n+2k-3$. Let $P$ be a polynomial as in Claim 2.1. Then we have
$P\in U_{k}$ and $\deg P\leq\deg Q$. Furthermore, $P$ also has zeroes of
multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, which implies that $P\in V_{k}$.
Finally, $P$ does not have a zero of multiplicity at least $k-1$ at
$(0,\dots,0)$, which in particular means that $P$ is not the zero polynomial.
Recall that by Corollary 2.11 the map $\varphi_{k}:V_{k}\to W_{k}$ is an
isomorphism (and in particular injective). Thus, we have $\varphi_{k}(P)\neq
0$, which means that the homogeneous degree $n+2k-3$ part of $P$ is non-zero.
So we can conclude that $\deg Q\geq\deg P\geq n+2k-3$.

It remains to prove the second part of Theorem 1.4. Fix $0\leq\ell\leq k-2$.
It is not hard to construct a (high-degree) polynomial $Q$ having zeroes of
multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and such that $Q$ has a zero of
multiplicity exactly $\ell$ at $(0,\dots,0)$, for example the polynomial
$Q=x_{1}^{\ell}\cdot(x_{1}-1)^{k}\dotsm(x_{n}-1)^{k}$. By Claim 2.1, there
exists a polynomial $P\in U_{k}$ which also has zeroes of multiplicity at
least $k$ at all points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and a
zero of multiplicity exactly $\ell$ at $(0,\dots,0)$ (recall that $\ell\leq
k-2$). It remains to check that $\deg P=n+2k-3$. Since $P\in U_{k}$, we must
have $\deg P\leq n+2k-3$. Furthermore, the first part of Theorem 1.4 proved
above implies that $\deg P\geq n+2k-3$. Hence $\deg P=n+2k-3$, and the
polynomial $P$ has all of the desired properties. ∎

##  3 Proof of Proposition 2.9

In this section, we will prove Proposition 2.9 by constructing a polynomial
$P\in V_{k}$ satisfying the desired conditions. Our polynomial $P$ will be a
symmetric polynomial.

Recall that we can write any symmetric polynomial
$R\in\mathbb{R}[x_{1},\dots,x_{n}]$ in terms of the power sum symmetric
polynomials $x_{1}^{m}+\dots+x_{n}^{m}$ for $1\leq m\leq n$. More precisely,
we can write $R$ as a linear combination of products of power sum symmetric
polynomials, i.e. as a linear combination of terms of the form
$(x_{1}^{m_{1}}+\dots+x_{n}^{m_{1}})\dotsm(x_{1}^{m_{\ell}}+\dots+x_{n}^{m_{\ell}})$
for positive integers $m_{1},\dots,m_{\ell}\leq n$. Furthermore, for every
symmetric polynomial $R\in\mathbb{R}[x_{1},\dots,x_{n}]$, such a
representation is unique (up to reordering $m_{1},\dots,m_{\ell}$ in the terms
of this linear combination), and we can therefore refer to it as “the
representation of $R$ in terms of power sum symmetric polynomials”.

######  Claim 3.1.

Let $n\geq 1$. Suppose that $d_{1},\dots,d_{t}$ are positive integers with
$d_{1}+\dots+d_{t}\leq n$, such that exactly one of $d_{1},\dots,d_{t}$ is
odd. Then the symmetric polynomial

$\sum_{\begin{subarray}{c}i_{1},\dots,i_{t}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm x_{i_{t}}^{d_{t}}$

is a linear combination of terms of the form
$(x_{1}^{m_{1}}+\dots+x_{n}^{m_{1}})\dotsm(x_{1}^{m_{\ell}}+\dots+x_{n}^{m_{\ell}})$
for $m_{1},\dots,m_{\ell}\in\\{1,\dots,n\\}$ with
$m_{1}+\dots+m_{\ell}=d_{1}+\dots+d_{t}$ and such that exactly one of
$m_{1},\dots,m_{\ell}$ is odd.

###### Proof.

Let us prove the claim by induction on $t$. If $t=1$, then $d_{1}$ is odd and
the symmetric polynomial $x_{1}^{d_{1}}+\dots+x_{n}^{d_{1}}$ is already of the
desired form. So let us now assume that $t\geq 2$ and that the claim holds for
$t-1$. As only one of $d_{1},\dots,d_{t}$ is odd, we may assume without loss
of generality that $d_{t}$ is even. Note that

$\sum_{\begin{subarray}{c}i_{1},\dots,i_{t}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{t}}^{d_{t}}=(x_{1}^{d_{t}}+\dots+x_{n}^{d_{t}})\cdot\sum_{\begin{subarray}{c}i_{1},\dots,i_{t-1}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{t-1}}^{d_{t-1}}\\\
-\sum_{s=1}^{t-1}\,\sum_{\begin{subarray}{c}i_{1},\dots,i_{t-1}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{s-1}}^{d_{s-1}}x_{i_{s}}^{d_{s}+d_{t}}x_{i_{s+1}}^{d_{s+1}}\dotsm
x_{i_{t-1}}^{d_{t-1}}.$

As exactly one of $d_{1},\dots,d_{t-1}$ is odd, we can apply the induction
hypothesis to the sum $\sum x_{i_{1}}^{d_{1}}\dotsm x_{i_{t-1}}^{d_{t-1}}$. We
can then conclude that $(x_{1}^{d_{t}}+\dots+x_{n}^{d_{t}})\cdot\sum
x_{i_{1}}^{d_{1}}\dotsm x_{i_{t-1}}^{d_{t-1}}$ is a linear combination of
terms of the form
$(x_{1}^{d_{t}}+\dots+x_{n}^{d_{t}})\cdot(x_{1}^{m_{1}}+\dots+x_{n}^{m_{1}})\dotsm(x_{1}^{m_{\ell}}+\dots+x_{n}^{m_{\ell}})$
for positive integers $m_{1},\dots,m_{\ell}$ with
$d_{t}+m_{1}+\dots+m_{\ell}=d_{1}+\dots+d_{t}$ and such that exactly one of
$d_{t},m_{1},\dots,m_{\ell}$ is odd. Furthermore, for each $s=1,\dots,t-1$ we
can also apply the induction hypothesis to the sum $\sum
x_{i_{1}}^{d_{1}}\dotsm
x_{i_{s-1}}^{d_{s-1}}x_{i_{s}}^{d_{s}+d_{t}}x_{i_{s+1}}^{d_{s+1}}\dotsm
x_{i_{t-1}}^{d_{t-1}}$ and we find that each of these sums is a linear
combination of terms of the desired form as well. ∎

######  Claim 3.2.

Let $k\geq 2$ and let $n\geq 2k-3$. Let $P\in U_{k}$ be a symmetric polynomial
and let $\overline{P}$ be the homogeneous degree $n+2k-3$ part of $P$. Suppose
that the polynomial $\overline{P}$ is divisible by $x_{1}\dotsm x_{n}$. Then
we have $\overline{P}\in W_{k}$. Furthermore, when we write $\overline{P}$ in
terms of the basis of $W_{k}$ in (2.1), then the coefficient of $x_{1}\dotsm
x_{n}\cdot(x_{1}^{2k-3}+\dots+x_{n}^{2k-3})$ is the same as the coefficient of
$x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ when writing the symmetric polynomial
$\overline{P}/(x_{1}\dotsm x_{n})$ in terms of power sum symmetric
polynomials.

###### Proof.

Recall that $P\in U_{k}$ does not contain any monomials which are divisible by
$x_{i_{1}}^{2}\dotsm x_{i_{k}}^{2}$ for some (not necessarily distinct)
indices $i_{1},\dots,i_{k}\in\\{1,\dots,n\\}$. Therefore any monomial of $P$
must be of the form $x_{1}^{2m_{1}+r_{1}}\dotsm x_{n}^{2m_{n}+r_{n}}$ with
non-negative integers $(m_{1},\dots,m_{n})$ with $m_{1}+\dots+m_{n}\leq k-1$
and $r_{1},\dots,r_{n}\in\\{0,1\\}$. If
$(2m_{1}+r_{1})+\dots+(2m_{n}+r_{n})=n+2k-3$, then this is only possible if
$m_{1}+\dots+m_{n}=k-1$ and $r_{1}+\dots+r_{n}=n-1$. This means that any
monomial of $P$ of degree $n+2k-3$ must have an odd exponent for exactly $n-1$
of the $n$ variables $x_{1},\dots,x_{n}$.

Now let $R=\overline{P}/(x_{1}\dotsm x_{n})$, and note that
$R\in\mathbb{R}[x_{1},\dots,x_{n}]$ is homogeneous of degree $2k-3$.
Furthermore, since $P$ is symmetric, the polynomials $\overline{P}$ and $R$
are also symmetric. We saw above that every monomial in $\overline{P}$ has odd
exponents for exactly $n-1$ of the variables $x_{1},\dots,x_{n}$ (and an even
exponent for the remaining variable). Hence every monomial in $R$ has an odd
exponent for exactly one variable. Thus, we can apply Claim 3.1 to all
different types of monomials appearing in $R$ (recalling that $n\geq 2k-3$).
We obtain that $R$ is a linear combination of terms of the form
$(x_{1}^{m_{1}}+\dots+x_{n}^{m_{1}})\dotsm(x_{1}^{m_{\ell}}+\dots+x_{n}^{m_{\ell}})$
for $m_{1},\dots,m_{\ell}\in\\{1,\dots,n\\}$ with $m_{1}+\dots+m_{\ell}=2k-3$
and such that exactly one of $m_{1},\dots,m_{\ell}$ is odd. By renaming
$m_{1},\dots,m_{\ell}$, we can always assume that $m_{1}$ is odd and
$m_{2},\dots,m_{\ell}$ are even.

Note that this representation of $R$ as a linear combination of such terms is
the representation of $R$ in terms of power sum symmetric polynomials. Hence
the coefficient $\lambda$ of $x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ when expressing
$\overline{P}/(x_{1}\dotsm x_{n})=R$ in terms of power sum symmetric
polynomials is precisely the coefficient of $x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$
when expressing $R$ as a linear combination as above.

By multiplying with $x_{1}\dotsm x_{n}$, we can now express
$\overline{P}=x_{1}\dotsm x_{n}\cdot R$ as a linear combination of terms of
the form $x_{1}\dotsm
x_{n}\cdot(x_{1}^{m_{1}}+\dots+x_{n}^{m_{1}})\dotsm(x_{1}^{m_{\ell}}+\dots+x_{n}^{m_{\ell}})$
for $m_{1},\dots,m_{\ell}\in\\{1,\dots,n\\}$ with $m_{1}+\dots+m_{\ell}=2k-3$
such that $m_{1}$ is odd and $m_{2},\dots,m_{\ell}$ are even. Note that the
only such term with $m_{1}=2k-3$ is the term $x_{1}\dotsm
x_{n}\cdot(x_{1}^{2k-3}+\dots+x_{n}^{2k-3})$, and the coefficient of this term
equals $\lambda$.

Note that each of these terms $x_{1}\dotsm
x_{n}\cdot(x_{1}^{m_{1}}+\dots+x_{n}^{m_{1}})\dotsm(x_{1}^{m_{\ell}}+\dots+x_{n}^{m_{\ell}})$
(with $m_{1}+\dots+m_{\ell}=2k-3$ and such that $m_{1}$ is odd and
$m_{2},\dots,m_{\ell}$ are even) can be written as a linear combination of
terms of the form (2.1) with $m=m_{1}$ (indeed, when multiplying out
$(x_{1}^{m_{2}}+\dots+x_{n}^{m_{2}})\dotsm(x_{1}^{m_{\ell}}+\dots+x_{n}^{m_{\ell}})$
all variables always appear with even exponents). All in all, this shows that
$\overline{P}$ can be written as a linear combination of terms of the form
(2.1), so $\overline{P}\in W_{k}$. Furthermore, when writing $\overline{P}$ in
terms of the basis of $W_{k}$ in (2.1), the coefficient of $x_{1}\dotsm
x_{n}\cdot(x_{1}^{2k-3}+\dots+x_{n}^{2k-3})$ equals $\lambda$, which we
defined as the coefficient of $x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ when
expressing $\overline{P}/(x_{1}\dotsm x_{n})$ in terms of power sum symmetric
polynomials. ∎

Let us now prove Proposition 2.9. The proof of the proposition depends on
three lemmas, whose proofs we will postpone to the next two subsections.

###### Proof of Proposition 2.9.

Fix $k\geq 2$ and $n\geq 2k-3$. In order to construct the desired polynomial
$P\in V_{k}$, let us first define the symmetric polynomial

$Q(x_{1},\dots,x_{n})=(-1)^{(k-1)n}\cdot(x_{1}-1)^{k}\dotsm(x_{n}-1)^{k}.$
(3.1)

Note that $Q$ has zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$.

Let us now define $P\in U_{k}$ to be the unique polynomial in $U_{k}$ such
that $Q-P$ has zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at least
$k-1$ at $(0,\dots,0)$ (such a polynomial $P$ exists by Claim 2.1 and it is
unique by Corollary 2.4). Then $P$ has zeroes of multiplicity at least $k$ at
all points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$, and hence $P\in
V_{k}$. Furthermore, since $Q$ is symmetric and $P$ is unique, $P$ must also
be a symmetric polynomial (otherwise we could permute the variables in $P$ and
obtain another polynomial with the desired properties, contradicting
uniqueness).

Recall that $\varphi_{k}(P)$ is the homogeneous degree $n+2k-3$ part of $P$.
We need to show that $\varphi_{k}(P)\in W_{k}$ and that when writing
$\varphi_{k}(P)\in W_{k}$ in terms of the basis in (2.1), then the coefficient
of the basis element $x_{1}\dotsm x_{n}\cdot(x_{1}^{2k-3}+\dots+x_{n}^{2k-3})$
is non-zero.

We wish to apply Claim 3.2 to $P$, but this requires the homogeneous degree
$n+2k-3$ part $\varphi_{k}(P)$ of $P$ to be divisible by $x_{1}\dotsm x_{n}$.

######  Lemma 3.3.

The polynomial $\varphi_{k}(P)$ is divisible by $x_{1}\dotsm x_{n}$.

We postpone the proof of Lemma 3.3 to Subsection 3.1. Assuming Lemma 3.3, by
Claim 3.2 we obtain $\varphi_{k}(P)\in W_{k}$, which establishes the first of
our two required properties for $P$. Furthermore, we also obtain from Claim
3.2 that the desired coefficient of $\varphi_{k}(P)$ (when writing it in terms
of the basis elements of $W_{k}$) is equal to the coefficient of
$x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ when writing $\varphi_{k}(P)/(x_{1}\dotsm
x_{n})$ in terms of power sum symmetric polynomials. So it remains to prove
that this coefficient of $x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ is non-zero. The
following lemma determines this coefficient.

######  Lemma 3.4.

When writing $\varphi_{k}(P)/(x_{1}\dotsm x_{n})$ in terms of power sum
symmetric polynomials, the coefficient of $x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ is
equal to

$\sum_{(m_{1},\dots,m_{t})}(-1)^{t}\cdot\binom{k-1-m_{1}}{m_{1}-1}\binom{k-1-m_{2}}{m_{2}}\dots\binom{k-1-m_{t}}{m_{t}},$

where the sum is over all sequences $(m_{1},\dots,m_{t})$ of positive integers
with $m_{1}+\dots+m_{t}=k-1$.

We also postpone the proof of Lemma 3.4 to Subsection 3.1. Surprisingly, the
value of the sum in Lemma 3.4 is (up to its sign) equal to the Catalan number
$C_{k-2}$; see the following lemma. Recall that the Catalan numbers
$C_{0},C_{1},\dots$ are given by the explicit formula
$C_{n}=\binom{2n}{n}/(n+1)$ for all $n\geq 0$.

######  Lemma 3.5.

For any $\ell\geq 1$, we have

$\sum_{(m_{1},\dots,m_{t})}(-1)^{t}\cdot\binom{\ell-
m_{1}}{m_{1}-1}\binom{\ell-m_{2}}{m_{2}}\dots\binom{\ell-
m_{t}}{m_{t}}=(-1)^{\ell}C_{\ell-1},$

where the sum is over all sequences $(m_{1},\dots,m_{t})$ of positive integers
with $m_{1}+\dots+m_{t}=\ell$.

We postpone the proof of Lemma 3.5 to Subsection 3.2. Applying the lemma with
$\ell=k-1$, we see that the sum in Lemma 3.4 equals
$(-1)^{k-1}C_{k-2}=(-1)^{k-1}\binom{2k-4}{k-2}/(k-1)\neq 0$. Thus, the
coefficient of $x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ when writing
$\varphi_{k}(P)/(x_{1}\dotsm x_{n})$ in terms of power sum symmetric
polynomials is indeed non-zero, finishing the proof of the Proposition 2.9. ∎

###  3.1 Proof of Lemmas 3.3 and 3.4

In this subsection, we prove Lemmas 3.3 and 3.4 by analyzing the polynomial
$P$ and its homogeneous degree $n+2k-3$ part $\varphi_{k}(P)$. As before, let
$k\geq 2$ and $n\geq 2k-3$ be fixed.

In order to calculate $\varphi_{k}(P)$, let us first rewrite the definition of
the polynomial $Q$ in (3.1) as

$Q(x_{1},\dots,x_{n})=\prod_{i=1}^{n}\left((-1)^{k-1}\cdot(x_{i}-1)^{k}\right).$

For $i=1,\dots,n$, let us now write $(-1)^{k-1}\cdot(x_{i}-1)^{k}$ as a linear
combination of $\allowbreak(x_{i}-1),\allowbreak x_{i}(x_{i}-1),\allowbreak
x_{i}(x_{i}-1)^{2},\allowbreak x_{i}^{2}(x_{i}-1)^{2},\allowbreak
x_{i}^{2}(x_{i}-1)^{3},\dots$, as in the following claim.

######  Claim 3.6.

For any $\ell\geq 1$ and $i\in\\{1,\dots,n\\}$, we have

$(-1)^{\ell-1}\cdot(x_{i}-1)^{\ell}=\sum_{m=0}^{\lfloor(\ell-1)/2\rfloor}\binom{\ell-1-m}{m}x_{i}^{m}(x_{i}-1)^{m+1}-\sum_{m=1}^{\lfloor\ell/2\rfloor}\binom{\ell-1-m}{m-1}x_{i}^{m}(x_{i}-1)^{m}.$

###### Proof.

First, note that we may equivalently write the desired equation as

$(-1)^{\ell-1}\cdot(x_{i}-1)^{\ell}=\sum_{m=0}^{\infty}\binom{\ell-1-m}{m}x_{i}^{m}(x_{i}-1)^{m+1}-\sum_{m=1}^{\infty}\binom{\ell-1-m}{m-1}x_{i}^{m}(x_{i}-1)^{m},$

since for all terms appearing in the infinite sums that did not appear in the
original equation, the respective binomial coefficients are zero.

Let us now prove this equation by induction on $\ell$. For $\ell=1$, the
equation is easy to check. Let us now assume it is true for some $\ell\geq 1$,
and let us check it for $\ell+1$. We have

$\displaystyle(-1)^{\ell}(x_{i}-1)^{\ell+1}$
$\displaystyle=-(x_{i}-1)\sum_{m=0}^{\infty}\binom{\ell-1-m}{m}x_{i}^{m}(x_{i}-1)^{m+1}+(x_{i}-1)\sum_{m=1}^{\infty}\binom{\ell-1-m}{m-1}x_{i}^{m}(x_{i}-1)^{m}$
$\displaystyle=-\sum_{m=0}^{\infty}\binom{\ell-1-m}{m}x_{i}^{m+1}(x_{i}-1)^{m+1}+\sum_{m=0}^{\infty}\binom{\ell-1-m}{m}x_{i}^{m}(x_{i}-1)^{m+1}$
$\displaystyle+\sum_{m=1}^{\infty}\binom{\ell-1-m}{m-1}x_{i}^{m}(x_{i}-1)^{m+1}$
$\displaystyle=-\sum_{m=1}^{\infty}\binom{\ell-m}{m-1}x_{i}^{m}(x_{i}-1)^{m}+\sum_{m=0}^{\infty}\binom{\ell-m}{m}x_{i}^{m}(x_{i}-1)^{m+1},$

as desired. This proves the claim. ∎

From Claim 3.6, we now obtain that $Q(x_{1},\dots,x_{n})$ equals

$\prod_{i=1}^{n}\left(\sum_{m=0}^{\lfloor(k-1)/2\rfloor}\binom{k-1-m}{m}x_{i}^{m}(x_{i}-1)^{m+1}-\sum_{m=1}^{\lfloor
k/2\rfloor}\binom{k-1-m}{m-1}x_{i}^{m}(x_{i}-1)^{m}\right).$ (3.2)

Using this equation, we can calculate the polynomial $P$. Recall that $P$ is
the unique polynomial in $U_{k}$ such that $Q-P$ has zeroes of multiplicity at
least $k$ at all points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a
zero of multiplicity at least $k-1$ at $(0,\dots,0)$.

When expanding the product over all $i$ in (3.2), each of the terms that we
obtain is a product of factors of the form $x_{i}^{m_{i}}(x_{i}-1)^{m_{i}+1}$
or $x_{i}^{m_{i}}(x_{i}-1)^{m_{i}}$ for each $i=1,\dots,n$ (with some
coefficient given as the product of certain binomial coefficients). Note that
each such term is divisible by the product
$x_{1}^{m_{1}}(x_{1}-1)^{m_{1}}\dotsm x_{n}^{m_{n}}(x_{n}-1)^{m_{n}}$, and if
$m_{1}+\dots+m_{n}\geq k$ this means that the term has zeroes of multiplicity
at least $k$ at all points in $\\{0,1\\}^{n}$. We can omit all such terms from
$Q$ without violating the defining property of $P\in U_{k}$ (i.e. the property
that $Q-P$ has zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at least
$k-1$ at $(0,\dots,0)$).

So let us now imagine that we expand the product over $i$ in (3.2), but we
only keep the terms which are products of factors of the form
$x_{i}^{m_{i}}(x_{i}-1)^{m_{i}+1}$ or $x_{i}^{m_{i}}(x_{i}-1)^{m_{i}}$ for
each $i=1,\dots,n$ such that $m_{1}+\dots+m_{n}\leq k-1$. Note that all of
these terms have degree at most $n+2k-2$. Furthermore, any such term of degree
$n+2k-2$ must be of the form $x_{1}^{m_{1}}(x_{1}-1)^{m_{1}+1}\dotsm
x_{n}^{m_{n}}(x_{n}-1)^{m_{n}+1}=(x_{1}-1)\dotsm(x_{n}-1)\cdot
x_{1}^{m_{1}}(x_{1}-1)^{m_{1}}\dotsm x_{n}^{m_{n}}(x_{n}-1)^{m_{n}}$ with
$m_{1}+\dots+m_{n}=k-1$. Hence any such term of degree $n+2k-2$ has zeroes of
multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at least
$k-1$ at $(0,\dots,0)$. We can also omit all of these terms from $Q$ without
violating the defining property of $P\in U_{k}$.

Now, let $Q^{*}$ be the polynomial consisting only of the remaining terms in
the expansion of the product over $i$ in (3.2), i.e. of the terms which are
products of factors of the form $x_{i}^{m_{i}}(x_{i}-1)^{m_{i}+1}$ or
$x_{i}^{m_{i}}(x_{i}-1)^{m_{i}}$ for each $i=1,\dots,n$ such that
$m_{1}+\dots+m_{n}\leq k-1$ and which have degree at most $n+2k-3$. Then
$Q^{*}-P$ has zeroes of multiplicity at least $k$ at all points in
$\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ and a zero of multiplicity at least
$k-1$ at $(0,\dots,0)$. However, the polynomial $Q^{*}$ is also $k$-reduced,
so we have $Q^{*}\in U_{k}$. By applying Corollary 2.4 to the polynomial
$Q^{*}$, we can therefore conclude that $Q^{*}=P$ (since $P,Q^{*}\in U_{k}$
both satisfy the conditions in Corollary 2.4).

In other words, we just showed that $P$ can be obtained by expanding the
product over $i$ in (3.2), but only keeping the terms which are products of
factors of the form $x_{i}^{m_{i}}(x_{i}-1)^{m_{i}+1}$ or
$x_{i}^{m_{i}}(x_{i}-1)^{m_{i}}$ for each $i=1,\dots,n$ such that
$m_{1}+\dots+m_{n}\leq k-1$ and which have degree at most $n+2k-3$. Now, the
homogeneous degree $n+2k-3$ part $\varphi_{k}(P)$ of $P$ can be calculated by
only considering the products of degree exactly $n+2k-3$ (and by only taking
the homogeneous degree $n+2k-3$ part of these products). In other words,
$\varphi_{k}(P)$ is obtained by expanding

$\prod_{i=1}^{n}\left(\sum_{m=0}^{\lfloor(k-1)/2\rfloor}\binom{k-1-m}{m}x_{i}^{2m+1}-\sum_{m=1}^{\lfloor
k/2\rfloor}\binom{k-1-m}{m-1}x_{i}^{2m}\right),$ (3.3)

but only keeping the terms which are products of factors of the form
$x_{i}^{2m_{i}+1}$ or $x_{i}^{2m_{i}}$ for each $i=1,\dots,n$ such that
$m_{1}+\dots+m_{n}\leq k-1$ and which have degree exactly $n+2k-3$. Note that
such a term can only have degree $n+2k-3$ if it consists of $n-1$ factors of
the form $x_{i}^{2m_{i}+1}$ and one factor of the form $x_{i}^{2m_{i}}$ (with
$m_{1}+\dots+m_{n}=k-1$). Hence $\varphi_{k}(P)$ can be obtained by expanding
(3.3), but only keeping the monomials of degree exactly $n+2k-3$ in which
exactly one variable has an even exponent.

To simplify notation, let us define $a_{0},\dots,a_{k-1}$ to be the
coefficients such that (3.3) can be written as
$\prod_{i=1}^{n}(a_{k-1}x_{i}^{k}+a_{k-2}x_{i}^{k-1}+\dots+a_{0}x_{i})$.
Furthermore, for $d\geq k$, let us define $a_{d}=0$. Note that then for all
$m\geq 0$ we have $a_{2m}=\binom{k-1-m}{m}$, and for all $m\geq 1$ we have
$a_{2m-1}=-\binom{k-1-m}{m-1}$. Also note that $a_{0}=1$. Using this notation,
we now obtain that

$\varphi_{k}(P)=\sum_{(d_{1},\dots,d_{n})}a_{d_{1}}\dotsm a_{d_{n}}\cdot
x_{1}^{d_{1}+1}\dotsm x_{n}^{d_{n}+1},$ (3.4)

where the sum is over all sequences $(d_{1},\dots,d_{n})$ of non-negative
integers with $(d_{1}+1)+\dots+(d_{n}+1)=n+2k-3$ such that exactly one of
$d_{1}+1,\dots,d_{n}+1$ is even. These conditions are equivalent to demanding
that $d_{1}+\dots+d_{n}=2k-3$ and exactly one of $d_{1},\dots,d_{n}$ is odd.
Now, Lemma 3.3 follows easily.

###### Proof of Lemma 3.3.

All monomials appearing in (3.4) are divisible by $x_{1}\dotsm x_{n}$, and
hence $\varphi_{k}(P)$ is divisible by $x_{1}\dotsm x_{n}$, as desired. ∎

From (3.4), we now obtain that

$\varphi_{k}(P)/(x_{1}\dotsm x_{n})=\sum_{(d_{1},\dots,d_{n})}a_{d_{1}}\dotsm
a_{d_{n}}\cdot x_{1}^{d_{1}}\dotsm x_{n}^{d_{n}},$

where the sum is over all sequences $(d_{1},\dots,d_{n})$ of non-negative
integers with $d_{1}+\dots+d_{n}=2k-3$ such that exactly one of
$d_{1},\dots,d_{n}$ is odd. Recalling that $a_{0}=1$, we can rewrite this
equation as

$\varphi_{k}(P)/(x_{1}\dotsm
x_{n})=\sum_{(d_{1},\dots,d_{t})}\left(a_{d_{1}}\dotsm a_{d_{t}}\sum_{1\leq
i_{1}<\dots<i_{t}\leq n}x_{i_{1}}^{d_{1}}\dotsm x_{i_{t}}^{d_{t}}\right),$
(3.5)

where the sum is over all sequences $(d_{1},\dots,d_{t})$ of positive integers
with $d_{1}+\dots+d_{t}=2k-3$ such that exactly one of $d_{1},\dots,d_{t}$ is
odd. Note that when we consider all $t!$ permutations of one fixed such
sequence $(d_{1},\dots,d_{t})$ (some of which may be equal to the original
sequence), then the resulting part of the sum in (3.5) is the symmetric
polynomial $a_{d_{1}}\dotsm
a_{d_{t}}\sum_{\begin{subarray}{c}i_{1},\dots,i_{t}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{t}}^{d_{t}}$. By averaging over all permutations of
$(d_{1},\dots,d_{t})$, we can therefore rewrite (3.5) as

$\varphi_{k}(P)/(x_{1}\dotsm
x_{n})=\sum_{(d_{1},\dots,d_{t})}\left(\frac{a_{d_{1}}\dotsm
a_{d_{t}}}{t!}\sum_{\begin{subarray}{c}i_{1},\dots,i_{t}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{t}}^{d_{t}}\right),$ (3.6)

where the sum is again over all sequences $(d_{1},\dots,d_{t})$ of positive
integers with $d_{1}+\dots+d_{t}=2k-3$ such that exactly one of
$d_{1},\dots,d_{t}$ is odd.

In order to prove Lemma 3.4, we need to find the coefficient of
$x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ when expressing $\varphi_{k}(P)/(x_{1}\dotsm
x_{n})$ in terms of power sum symmetric polynomials. We will use the following
claim, which can be derived from more general statements in the theory of
symmetric polynomials. For the reader’s convenience we provide a simple self-
contained proof.

######  Claim 3.7.

For any sequence $(d_{1},\dots,d_{t})$ of positive integers with
$d_{1}+\dots+d_{t}\leq n$, when expressing

$\sum_{\begin{subarray}{c}i_{1},\dots,i_{t}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm x_{i_{t}}^{d_{t}}$

in terms of power sum symmetric polynomials, the coefficient of
$x_{1}^{d_{1}+\dots+d_{t}}+\dots+x_{n}^{d_{1}+\dots+d_{t}}$ equals
$t!\cdot(-1)^{t-1}/t$.

###### Proof.

For $t=1$, the claim is trivially true. Let us now assume that $t\geq 2$, and
that we already proved the claim for $t-1$. Note that

$\sum_{\begin{subarray}{c}i_{1},\dots,i_{t}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{t}}^{d_{t}}=(x_{1}^{d_{t}}+\dots+x_{n}^{d_{t}})\cdot\sum_{\begin{subarray}{c}i_{1},\dots,i_{t-1}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{t-1}}^{d_{t-1}}\\\
-\sum_{s=1}^{t-1}\,\sum_{\begin{subarray}{c}i_{1},\dots,i_{t-1}\in\\{1,\dots,n\\}\\\
\textnormal{distinct}\end{subarray}}x_{i_{1}}^{d_{1}}\dotsm
x_{i_{s-1}}^{d_{s-1}}x_{i_{s}}^{d_{s}+d_{t}}x_{i_{s+1}}^{d_{s+1}}\dotsm
x_{i_{t-1}}^{d_{t-1}}.$

Let us now imagine that we express the sums on the left-hand side in terms of
power sum symmetric polynomials. The terms contributed from the first part
(before the minus sign), all contain a factor
$x_{1}^{d_{t}}+\dots+x_{n}^{d_{t}}$, and in particular this first part does
not contribute any $x_{1}^{d_{1}+\dots+d_{t}}+\dots+x_{n}^{d_{1}+\dots+d_{t}}$
terms. For the second part (after the minus sign), the coefficient of
$x_{1}^{d_{1}+\dots+d_{t}}+\dots+x_{n}^{d_{1}+\dots+d_{t}}$ is by the
induction hypothesis equal to
$-\sum_{s=1}^{t-1}(t-1)!\cdot(-1)^{t-2}/(t-1)=(t-1)!\cdot(-1)^{t-1}=t!\cdot(-1)^{t-1}/t$.
This finishes the proof of the claim. ∎

###### Proof of Lemma 3.4.

Let $Y$ denote the coefficient of $x_{1}^{2k-3}+\dots+x_{n}^{2k-3}$ when
writing $\varphi_{k}(P)/(x_{1}\dotsm x_{n})$ in terms of power sum symmetric
polynomials. We need to prove that $Y$ equals the sum in the statement of
Lemma 3.4.

Recalling that we assumed $n\geq 2k-3$, we can apply Claim 3.7 to the terms on
the right-hand side of (3.6), and obtain

$Y=\sum_{(d_{1},\dots,d_{t})}\frac{a_{d_{1}}\dotsm
a_{d_{t}}}{t!}\cdot\frac{t!\cdot(-1)^{t-1}}{t}=\sum_{(d_{1},\dots,d_{t})}a_{d_{1}}\dotsm
a_{d_{t}}\cdot\frac{(-1)^{t-1}}{t},$

where the sums are over all sequences $(d_{1},\dots,d_{t})$ of positive
integers with $d_{1}+\dots+d_{t}=2k-3$ such that exactly one of
$d_{1},\dots,d_{t}$ is odd. Note that all $t$ cyclic permutations of one fixed
such sequence $(d_{1},\dots,d_{t})$ contribute the same amount to the sum
above, and for exactly one of these permutations $d_{1}$ is odd. Hence we can
conclude that

$Y=\sum_{(d_{1},\dots,d_{t})}t\cdot a_{d_{1}}\dotsm
a_{d_{t}}\cdot\frac{(-1)^{t-1}}{t}=\sum_{(d_{1},\dots,d_{t})}(-1)^{t-1}a_{d_{1}}\dotsm
a_{d_{t}},$

where this time the sums are over all sequences $(d_{1},\dots,d_{t})$ of
positive integers with $d_{1}+\dots+d_{t}=2k-3$ such that $d_{1}$ is odd and
$d_{2},\dots,d_{t}$ are even.

Let us now change variables, writing $d_{1}=2m_{1}-1$ and $d_{j}=2m_{j}$ for
$j=2,\dots,t$. Then we obtain

$Y=\sum_{(m_{1},\dots,m_{t})}(-1)^{t-1}a_{2m_{1}-1}a_{2m_{2}}\dotsm
a_{2m_{t}}=\sum_{(m_{1},\dots,m_{t})}(-1)^{t}\cdot(-a_{2m_{1}-1})\cdot
a_{2m_{2}}\dotsm a_{2m_{t}}\\\
=\sum_{(m_{1},\dots,m_{t})}(-1)^{t}\cdot\binom{k-1-m_{1}}{m_{1}-1}\binom{k-1-m_{2}}{m_{2}}\dots\binom{k-1-m_{t}}{m_{t}},$

where the sums are over all sequences $(m_{1},\dots,m_{t})$ of positive
integers with $m_{1}+\dots+m_{t}=k-1$. This proves Lemma 3.4. ∎

###  3.2 Proof of Lemma 3.5

In this subsection, we prove Lemma 3.5. We remark that after an earlier
version of this paper was posted, alternative proofs were found, by Ekhad and
Zeilberger [10] and by Carde [7].

We will use the formula for Catalan numbers stated in the following claim.
This formula follows from work of Riordan [16] and is also stated as Theorem
12.1 in a book on Catalan numbers by Koshy [15]. It can also be proved from a
simple bijection argument, as shown in [10]. For the reader’s convenience we
give a self-contained proof here.

######  Claim 3.8.

For all $s\geq 1$, we have

$\sum_{i=0}^{s}(-1)^{i}C_{i}\cdot\binom{i+1}{s-i}=0.$ (3.7)

###### Proof.

We prove the desired formula by induction on $s$. For $s=1$ and $s=2$, the
formula is easy to check. So let us now assume that $s\geq 3$ and that the
formula is true for $s-1$ and $s-2$.

Recall that for $i\geq 0$ we have $C_{i}=\binom{2i}{i}/(i+1)$, which implies
that $C_{i}=C_{i-1}\cdot 2(2i-1)/(i+1)$ for $i\geq 1$. Consequently, for all
$i\geq 1$ we have

$\displaystyle C_{i}\cdot\binom{i+1}{s-i}$
$\displaystyle=2C_{i-1}\cdot(2i-1)\cdot\frac{1}{i+1}\binom{i+1}{s-i}$
$\displaystyle=2C_{i-1}\cdot\left(\frac{2s-4}{s+1}(s-i)+\frac{2s-1}{s+1}(2i+1-s)\right)\cdot\frac{1}{i+1}\binom{i+1}{s-i}$
$\displaystyle=\frac{4s-8}{s+1}\cdot
C_{i-1}\cdot\frac{s-i}{i+1}\binom{i+1}{s-i}+\frac{4s-2}{s+1}\cdot
C_{i-1}\cdot\frac{2i+1-s}{i+1}\binom{i+1}{s-i}$
$\displaystyle=\frac{4s-8}{s+1}\cdot
C_{i-1}\cdot\binom{i}{s-i-1}+\frac{4s-2}{s+1}\cdot
C_{i-1}\cdot\binom{i}{s-i}.$

Now, recalling that $s\geq 3$, we obtain that

$\displaystyle\sum_{i=0}^{s}(-1)^{i}C_{i}\cdot\binom{i+1}{s-i}$
$\displaystyle=\sum_{i=1}^{\infty}(-1)^{i}C_{i}\cdot\binom{i+1}{s-i}$
$\displaystyle=-\frac{4s-8}{s+1}\sum_{i=1}^{\infty}(-1)^{i-1}C_{i-1}\cdot\binom{i}{s-1-i}-\frac{4s-2}{s+1}\sum_{i=1}^{\infty}(-1)^{i-1}C_{i-1}\cdot\binom{i}{s-i}$
$\displaystyle=-\frac{4s-8}{s+1}\sum_{i=0}^{\infty}(-1)^{i}C_{i}\cdot\binom{i+1}{s-2-i}-\frac{4s-2}{s+1}\sum_{i=0}^{\infty}(-1)^{i}C_{i}\cdot\binom{i+1}{s-1-i}$
$\displaystyle=-\frac{4s-8}{s+1}\sum_{i=0}^{s-2}(-1)^{i}C_{i}\cdot\binom{i+1}{s-2-i}-\frac{4s-2}{s+1}\sum_{i=0}^{s-1}(-1)^{i}C_{i}\cdot\binom{i+1}{s-1-i}=0,$

using the induction hypothesis for $s-2$ and $s-1$ in the last step. ∎

We will also use the following well-known formula for binomial coefficients
(which is easy to prove, for example by double-counting): for all non-negative
integers $m$, $n$ and $s$, we have

$\binom{n+s+1}{m-s}=\sum_{j=s}^{\infty}\binom{s+1}{j-s}\binom{n}{m-j}.$ (3.8)

From (3.7) and (3.8) we can derive the following statement, which will be used
in the proof of Lemma 3.5.

######  Claim 3.9.

For any non-negative integers $m$, $n$ and $s$, we have

$\binom{n}{m}=\sum_{j=0}^{s}(-1)^{j}C_{j}\cdot\binom{n+j+1}{m-j}-\sum_{j=s+1}^{2s+1}\left(\sum_{i=0}^{s}(-1)^{i}C_{i}\cdot\binom{i+1}{j-i}\right)\binom{n}{m-j}.$

###### Proof.

First, note that for any $j>2s+1$, we have $\binom{i+1}{j-i}=0$ for all
$i=0,\dots,s$. We can therefore equivalently write the desired equation as

$\binom{n}{m}=\sum_{j=0}^{s}(-1)^{j}C_{j}\cdot\binom{n+j+1}{m-j}-\sum_{j=s+1}^{\infty}\left(\sum_{i=0}^{s}(-1)^{i}C_{i}\cdot\binom{i+1}{j-i}\right)\binom{n}{m-j}.$

We prove this equation by induction on $s$. Note that for $s=0$, it simply
states that (recall that $C_{0}=1$)

$\binom{n}{m}=\binom{n+1}{m}-\binom{n}{m-1},$

which is true. Now let us assume that $s\geq 1$ and that the desired equation
is true for $s-1$. Then

$\displaystyle\binom{n}{m}$
$\displaystyle=\sum_{j=0}^{s-1}(-1)^{j}C_{j}\cdot\binom{n+j+1}{m-j}-\sum_{j=s}^{\infty}\left(\sum_{i=0}^{s-1}(-1)^{i}C_{i}\cdot\binom{i+1}{j-i}\right)\binom{n}{m-j}$
$\displaystyle=\sum_{j=0}^{s}(-1)^{j}C_{j}\cdot\binom{n+j+1}{m-j}-(-1)^{s}C_{s}\cdot\binom{n+s+1}{m-s}-\sum_{j=s}^{\infty}\left(\sum_{i=0}^{s-1}(-1)^{i}C_{i}\cdot\binom{i+1}{j-i}\right)\binom{n}{m-j}$
$\displaystyle=\sum_{j=0}^{s}(-1)^{j}C_{j}\cdot\binom{n+j+1}{m-j}-\sum_{j=s}^{\infty}\left((-1)^{s}C_{s}\cdot\binom{s+1}{j-s}+\sum_{i=0}^{s-1}(-1)^{i}C_{i}\cdot\binom{i+1}{j-i}\right)\binom{n}{m-j}$
$\displaystyle=\sum_{j=0}^{s}(-1)^{j}C_{j}\cdot\binom{n+j+1}{m-j}-\sum_{j=s}^{\infty}\left(\sum_{i=0}^{s}(-1)^{i}C_{i}\cdot\binom{i+1}{j-i}\right)\binom{n}{m-j}$
$\displaystyle=\sum_{j=0}^{s}(-1)^{j}C_{j}\cdot\binom{n+j+1}{m-j}-\sum_{j=s+1}^{\infty}\left(\sum_{i=0}^{s}(-1)^{i}C_{i}\cdot\binom{i+1}{j-i}\right)\binom{n}{m-j},$

where for the third equation we used (3.8), and in the last equation we used
(3.7). This finishes the proof of the claim. ∎

Using Claim 3.9, we now prove Lemma 3.5.

###### Proof of Lemma 3.5.

Fix $\ell\geq 1$. For convenience, let us denote the left-hand side of the
equation in Lemma 3.5 by $Z$. We then need to show that
$Z=(-1)^{\ell}C_{\ell-1}$.

We have

$Z=\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\ m_{1},\dots,m_{t}>0\\\
m_{1}+\dots+m_{t}=\ell\end{subarray}}(-1)^{t}\cdot\binom{\ell-
m_{1}}{m_{1}-1}\binom{\ell-m_{2}}{m_{2}}\dots\binom{\ell-m_{t}}{m_{t}}.$

Applying Claim 3.9 to the first binomial coefficient in the product (with
$n=\ell-m_{1}$ and $m=m_{1}-1$ and $s=\ell-1$), we obtain

$Z=\sum_{j=0}^{\ell-1}\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\
m_{1},\dots,m_{t}>0\\\
m_{1}+\dots+m_{t}=\ell\end{subarray}}(-1)^{t}\cdot(-1)^{j}C_{j}\binom{\ell-
m_{1}+j+1}{m_{1}-1-j}\binom{\ell-m_{2}}{m_{2}}\dots\binom{\ell-
m_{t}}{m_{t}}\\\
-\sum_{j=\ell}^{2\ell-1}\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\
m_{1},\dots,m_{t}>0\\\
m_{1}+\dots+m_{t}=\ell\end{subarray}}(-1)^{t}\cdot\left(\sum_{i=0}^{\ell-1}(-1)^{i}C_{i}\binom{i+1}{j-i}\right)\binom{\ell-
m_{1}}{m_{1}-1-j}\binom{\ell-m_{2}}{m_{2}}\dots\binom{\ell-m_{t}}{m_{t}}.$

Note that the sum after the minus sign in the above equation is zero. Indeed,
for all terms appearing in this sum we have $m_{1}\leq\ell\leq j$, so the
binomial coefficient $\binom{\ell-m_{1}}{m_{1}-1-j}$ is zero. Hence

$Z=\sum_{j=0}^{\ell-1}\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\
m_{1},\dots,m_{t}>0\\\ m_{1}+\dots+m_{t}=\ell\\\ t\geq
1\end{subarray}}(-1)^{j+t}C_{j}\binom{\ell-m_{1}+j+1}{m_{1}-j-1}\binom{\ell-
m_{2}}{m_{2}}\dots\binom{\ell-m_{t}}{m_{t}}.$

With a change of variables, replacing $m_{1}-j-1$ by $m_{1}$, we can rewrite
this as

$Z=\sum_{j=0}^{\ell-1}\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\
m_{1}\geq 0,\,m_{2},\dots,m_{t}>0\\\ m_{1}+\dots+m_{t}=\ell-j-1\\\ t\geq
1\end{subarray}}(-1)^{j+t}C_{j}\binom{\ell-m_{1}}{m_{1}}\binom{\ell-
m_{2}}{m_{2}}\dots\binom{\ell-m_{t}}{m_{t}}$

(here, a priori the condition on $m_{1}$ would be $m_{1}>-j-1$, but since the
binomial coefficient $\binom{\ell-m_{1}}{m_{1}}$ vanishes for negative
$m_{1}$, we can instead take the condition $m_{1}\geq 0$). Note that in the
above equation, the contribution for $j=\ell-1$ is just
$(-1)^{\ell-1+1}C_{\ell-1}\binom{\ell-0}{0}=(-1)^{\ell}C_{\ell-1}$. Thus,

$Z=(-1)^{\ell}C_{\ell-1}+\sum_{j=0}^{\ell-2}\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\
m_{1}\geq 0,\,m_{2},\dots,m_{t}>0\\\
m_{1}+\dots+m_{t}=\ell-j-1\end{subarray}}(-1)^{j+t}C_{j}\binom{\ell-
m_{1}}{m_{1}}\binom{\ell-m_{2}}{m_{2}}\dots\binom{\ell-m_{t}}{m_{t}}.$

Now, in order to prove the lemma, it suffices to show that for any fixed
$j\in\\{0,\dots,\ell-2\\}$ we have

$\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\ m_{1}\geq
0,\,m_{2},\dots,m_{t}>0\\\
m_{1}+\dots+m_{t}=\ell-j-1\end{subarray}}(-1)^{t}\cdot\binom{\ell-
m_{1}}{m_{1}}\binom{\ell-m_{2}}{m_{2}}\dots\binom{\ell-m_{t}}{m_{t}}=0.$ (3.9)

Indeed, by distinguishing whether $m_{1}$ is positive or zero (and noting that
for $m_{1}=0$ we have $\binom{\ell-m_{1}}{m_{1}}=\binom{\ell-0}{0}=1$), we can
rewrite the left-hand size of (3.9) as

$\sum_{\begin{subarray}{c}(m_{1},\dots,m_{t})\\\ m_{1},m_{2},\dots,m_{t}>0\\\
m_{1}+\dots+m_{t}=\ell-j-1\end{subarray}}(-1)^{t}\cdot\binom{\ell-
m_{1}}{m_{1}}\dots\binom{\ell-
m_{t}}{m_{t}}+\sum_{\begin{subarray}{c}(m_{2},\dots,m_{t})\\\
m_{2},\dots,m_{t}>0\\\
m_{2}+\dots+m_{t}=\ell-j-1\end{subarray}}(-1)^{t}\cdot\binom{\ell-
m_{2}}{m_{2}}\dots\binom{\ell-m_{t}}{m_{t}}=0,$

where the equality follows because the exact same summands appear in both
sums, but with opposite signs. This proves (3.9), finishing the proof of Lemma
3.5. ∎

##  4 Concluding remarks

###  4.1 Clifton and Huang’s hyperplane problem

As mentioned in the introduction, Clifton and Huang [8] studied the minimum
size of a collection of hyperplanes in $\mathbb{R}^{n}$ such that every point
in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ is covered by at least $k$ of
these hyperplanes, but no hyperplane contains $(0,\dots,0)$, where $k\geq 2$
is fixed and $n$ is large with respect to $k$. While Theorem 1.3 improves
their lower bound for this problem to $n+2k-3$, the best known upper bound is
still $n+\binom{k}{2}$. It would be very interesting to close this gap.

Clifton and Huang [8] conjectured that their upper bound $n+\binom{k}{2}$ for
this hyperplane problem is tight if $n$ is sufficiently large with respect to
$k$. Theorem 1.3 shows that this conjecture cannot be proved by following the
approach of Clifton and Huang and only being more careful with the of the
analysis of the coefficients of the polynomials appearing in their argument.
In their approach, they consider a polynomial $f$ defined as the product of
the linear hyperplane polynomials corresponding to a collection of hyperplanes
satisfying the conditions. By applying the punctured higher-multiplicity
version of the Combinatorial Nullstellensatz due to Ball and Serra [3] to $f$,
they obtain another polynomial $u$. This polynomial $u$ (and some of its
derivatives) need to vanish at certain points, due to the higher-order
vanishing properties of the polynomial $f$. Clifton and Huang show that these
vanishing conditions for $u$ imply that $u$ must have sufficiently large
degree (specifically, degree at least $3$ for $k=3$ and degree at least $5$
for $k=4$), and this gives their lower bound for the number of hyperplanes. In
principle, one could hope to get better lower bounds from performing the
analysis of the vanishing conditions for $u$ more carefully or for larger
values of $k$. However, the second part of Theorem 1.3 implies that there
exist polynomials of degree at most $2k-3$ satisfying the vanishing properties
of the polynomial $u$ in the approach of Clifton and Huang. Hence one cannot
prove a lower bound of $\binom{k}{2}$ on the degree of $u$ just by using the
relevant vanishing conditions. Instead, when hoping to prove the conjecture
that $n+\binom{k}{2}$ hyperplanes are necessary (if $n$ is sufficiently large
with respect to $k$) with an argument along the lines of Clifton and Huang’s
approach, one would need to incorporate additional information about the
polynomial $f$ from which $u$ is obtained. This polynomial $f$ is a product of
linear polynomials, but this is not necessarily true for the polynomial $u$
obtained by applying the punctured higher-multiplicity version of the
Combinatorial Nullstellensatz. Unfortunately, it is unclear how the fact that
$f$ is a product of linear polynomials can be used when analyzing the
polynomial $u$.

Note that Clifton and Huang’s hyperplane problem is actually equivalent to 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)\\}$ and such that $P$ can be written as
a product of linear polynomials? Without this last condition, this is
precisely Problem 1.2. By the results of Alon and Füredi [2], the answers for
both problems agree if $k=1$. The answers also agree for $k=2$ and $k=3$,
since then $n+2k-3=n+\binom{k}{2}$. However, if Clifton and Huang’s conjecture
is true, then by Theorem 1.3 the answers must be different for $k\geq 4$. It
would be interesting to prove (or disprove) that the two problems have
different answers for sufficiently large $k$.

One can also study a variant of Clifton and Huang’s hyperplane problem, where
one replaces the condition that no hyperplane contains $(0,\dots,0)$ by the
condition that $(0,\dots,0)$ is covered by exactly $\ell$ hyperplanes for some
given $0\leq\ell\leq k-1$. The case of $\ell=0$ corresponds to Clifton and
Huang’s original hyperplane problem. As before, we can equivalently rephrase
the problem in terms of polynomials, asking for the minimum possible degree of
a polynomial $P\in\mathbb{R}[x_{1},\dots,x_{n}]$ with a zero of multiplicity
exactly $\ell$ at $(0,\dots,0)$ and zeroes of multiplicity at least $k$ at all
points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$ such that $P$ can be
written as a product of linear polynomials. Again, one may ask whether the
answer to this problem changes by omitting the last condition that $P$ is a
product of linear polynomials. Theorems 1.4 and 1.5 determine the answer of
the problem where the last condition is omitted (the answer is $n+2k-3$ for
$0\leq\ell\leq k-2$ and $n+2k-2$ for $\ell=k-1$). By finding examples for the
polynomial $P$ with the desired properties and of the appropriate degree such
that $P$ is a product of linear polynomials, one can show that the answers for
both problems agree for $k-3\leq\ell\leq k-1$. However, it is not clear what
happens for smaller $\ell$.

Clifton and Huang also studied their hyperplane problem in the opposite
parameter range, where the dimension $n$ is fixed and $k$ is large. They
proved that for any fixed dimension $n$, the answer is of the form
$(1+\frac{1}{2}+\dots+\frac{1}{n}+o(1))\cdot k$ as $k$ goes to infinity. It
might also be interesting to study Problem 1.2 for fixed dimension $n$ and
large $k$.

###  4.2 Problem 1.2 over other fields

One can also consider Problem 1.2 over other fields than $\mathbb{R}$. For an
arbitrary field $\mathbb{F}$, let us say that a polynomial
$P\in\mathbb{F}[x_{1},\dots,x_{n}]$ has a zero of multiplicity at least $k$ at
a point $(a_{1},\dots,a_{n})\in\mathbb{F}^{n}$ if the following holds: when
expanding the polynomial
$P(x_{1}+a_{1},\dots,x_{n}+a_{n})\in\mathbb{F}[x_{1},\dots,x_{n}]$, all
monomials occurring in $P(x_{1}+a_{1},\dots,x_{n}+a_{n})$ have degree at least
$k$. Note that for $\mathbb{F}=\mathbb{R}$ this agrees with our definition in
terms of the derivatives of $P$ at $(a_{1},\dots,a_{n})$.

Our proof of Theorems 1.3 to 1.5 works for every field of characteristic $0$,
but it is also interesting to consider Problem 1.2 over fields of positive
characteristic. Since Alon and Füredi’s result [2] stated in Theorem 1.1 is
valid over any field, one might also expect the answer for Problem 1.2 to be
independent of the characteristic of the field.

Interestingly, this is not the case, and the answer for Problem 1.2 does
depend on the characteristic of the field. Specifically, for a field
$\mathbb{F}$ of characteristic $p>3$ and $k=(p+5)/2$, there exists a
polynomial $P\in\mathbb{F}[x_{1},\dots,x_{n}]$ of degree $\deg P\leq n+2k-4$
with $P(0,\dots,0)\neq 0$ and such that $P$ has zeroes of multiplicity at
least $k$ at all points in $\\{0,1\\}^{n}\setminus\\{(0,\dots,0)\\}$. In
particular, the statement in Theorem 1.3 fails to hold in this case. Theorem
1.3 similarly fails for a field of characteristic $2$ and $k=4$ and for a
field of characteristic $3$ and $k=7$.

For example, for $k=4$ and the field $\mathbb{F}=\mathbb{F}_{2}$, one can
check that the following polynomial of degree $n+2k-4=n+4$ has zeroes of
multiplicity at least $4$ at all points in
$\mathbb{F}_{2}^{n}\setminus\\{(0,\ldots,0)\\}$, but does not vanish at
$(0,\ldots,0)$:

$\left(\prod_{\ell=1}^{n}(x_{\ell}+1)\right)\cdot\left(1+\sum_{i=1}^{n}(x_{i}^{3}+x_{i}^{2}+x_{i})+\sum_{1\leq
i\neq j\leq n}(x_{i}^{3}+x_{i}^{2})x_{j}+\sum_{1\leq i<j\leq
n}x_{i}x_{j}+\sum_{1\leq i<j<k\leq n}x_{i}x_{j}x_{k}\right).$

The relevance of the values $k=(p+5)/2$ in characteristic $p>3$, as well as
$k=4$ in characteristic $p=2$, and $k=7$ in characteristic $p=3$ is as
follows: in each of these cases, $k$ is the smallest number such that the
Catalan number $C_{k-2}$ is divisible by $p$. By using the arguments from our
proof (together with some additional analysis of our map $\varphi_{k}$), one
can show that there is a counterexample to Theorem 1.3 for this value of $k$
in each of these cases (but the theorem holds for all smaller values). In
fact, the proof of Theorem 1.3 essentially gives an algorithm for producing
such counterexamples. It is worth pointing out that the only point in our
proof which is dependent on the characteristic of the field $\mathbb{F}$ is
the assertion that the Catalan numbers are non-zero in $\mathbb{F}$.

Since the first part of Theorem 1.3 fails to hold over fields of positive
characteristic, the first part of Theorem 1.4 (which is a more general
statement) also fails for over fields of positive characteristic. Theorem 1.5,
however, holds over any field.

Acknowledgments. We thank the anonymous referees for their careful reading of
this paper, and for many helpful comments. This work began while the first
author was at Stanford University and was completed while the first author was
at the Institute for Advanced Study.

## References

  * [1] N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 7–29.
  * [2] N. Alon and Z. Füredi, Covering the cube by affine hyperplanes, European J. Combin. 14 (1993), 79–83.
  * [3] S. Ball and O. Serra, Punctured combinatorial Nullstellensätze, Combinatorica 29 (2009), 511–522.
  * [4] G. Batzaya and G. Bayarmagnai, A generalized combinatorial Nullstellensatz for multisets, European J. Combin. 83 (2020), 5 pp.
  * [5] A. Bishnoi, P. L. Clark, A. Potukuchi, and J. Schmitt, On zeros of a polynomial in a finite grid, Combin. Probab. Comput. 27 (2018), 310–333.
  * [6] B. Bukh and T.-W. Chao, Sharp density bounds on the finite field Kakeya problem, Discrete Anal. 2021, Paper No. 26, 9 pp.
  * [7] K. Carde, The $q$-golden ratio, Catalan numbers, and an identity of Sauermann–Wigderson, 2021. Preprint available at arXiv:2108.04963.
  * [8] A. Clifton and H. Huang, On almost $k$-covers of hypercubes, Combinatorica 40 (2020), 511–526.
  * [9] Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan, Extensions to the method of multiplicities, with applications to Kakeya sets and mergers, SIAM J. Comput. 42 (2013), 2305–2328.
  * [10] S. B. Ekhad and D. Zeilberger, Two quick proofs of a Catalan lemma needed by Lisa Sauermann and Yuval Wigderson, 2020. Preprint available at arXiv:2011.07625.
  * [11] B. Hanson and G, Petridis, Refined Estimates Concerning Sumsets Contained in the Roots of Unity, Proc. Lond. Math. Soc. (3) 122 (2021), 353–-358.
  * [12] P. Komjáth, Partitions of vector spaces, Period. Math. Hungar. 28 (1994), 187–193.
  * [13] G. Kós and L. Rónyai, Alon’s Nullstellensatz for multisets, Combinatorica 32 (2012), 589–605.
  * [14] G. Kós, T. Mészáros, and L. Rónyai, Some extensions of Alon’s Nullstellensatz, Publ. Math. Debrecen 79 (2011), 507–519.
  * [15] T. Koshy, Catalan numbers with applications, Oxford University Press, Oxford, 2009.
  * [16] J. Riordan, A note on Catalan parentheses, Amer. Math. Monthly 80 (1973), 904–906.