# Smallest $S\subset \mathbb C$ on which no degree $k$ polynomial always vanishes?

Say $$p$$ is a polynomial of degree $$k$$ in $$\mathbb C[x]$$. Then $$p$$ can have at most $$k$$ distinct roots. A somewhat obtuse way to state that is to say that among any set of $$k+1$$ distinct complex numbers, there must exist a value $$a$$ for which $$p(a)\neq 0$$.

The question here has to do with generalizing the above fact to multivariate polynomials.

Given some $$p \in \mathbb C[x_1,\ldots,x_n]$$, it turns out that whenever we have enough different values to choose from, we can always pick from these some $$a_1,\ldots,a_n$$ so as to give $$p(a_1,\ldots,a_n)\neq 0$$. Moreover, how many is "enough" is a function just of $$n$$ and the degree of $$p$$.

I want to emphasize that, in the above and in what follows, the $$a_1,\ldots,a_n$$ so chosen are distinct.

To make things more precise and specific, we have the following.

Theorem.  Let $$p \in \mathbb C[x_1,\ldots,x_n]$$ be a polynomial of total degree $$k$$. Then any set of $$n+k$$ distinct complex numbers contains a subset of $$n$$ that can be assigned to the variables $$x_1,\ldots,x_n$$ so as to give a nonzero value for $$p$$. (Again, we are talking about choosing from the set $$n$$ distinct values that we assign to $$x_1,\ldots,x_n$$.)

The proof of the above is a not-too-difficult exercise.

But the question is:

Question.  In the above theorem, can the $$n+k$$ be replaced with some other function of $$n$$ and $$k$$ so as to give a better upper bound?

In fact, let's define $$M(n,k)$$ to be the smallest positive integer such that for every $$p\in \mathbb C[x_1,\ldots,x_n]$$ of total degree $$k$$, every set $$S$$ of at least $$M(n,k)$$ distinct complex numbers contains some subset $$\{a_1,\ldots,a_n\}$$ (of cardinality $$n$$, so that these are distinct values) such that $$p(a_1,\ldots,a_n)\neq 0$$.

The theorem above states that $$M(n,k) \le n+k$$, but I don't even see how to meet that bound for $$n=k=2$$.

This is probably just another way to present Fedor Petrov's solution: Expand $$\frac{(1-t \alpha_1) (1-t \alpha_2) \cdots (1-t \alpha_{n+k-1})}{(1-t \beta_1)(1 - t \beta_2) \cdots (1-t \beta_n)}$$ as a formal power series in $$t$$. The coefficient of $$t^k$$ is a degree $$k$$ polynomial in the $$\beta$$'s, which vanishes whenever $$\{ \beta_1, \beta_2, \ldots, \beta_n \}$$ is a $$n$$-element subset of the $$\alpha$$'s.

Three does not suffice for $$n=k=2.$$ Consider $$x^2+xy+y^2-1$$ with the set $$\{-1,0,1\}.$$

• Oh, nice. Now I'm not sure whether I suspect the bound can be met in general. Commented Feb 22, 2020 at 11:56
• moreover, $n+1$ do not suffice for $k=2$ and any set $A$ of size $n+1$. Consider the polynomial $x_1^2+\ldots+x_n^2+(x_1+\ldots+x_n-s)^2-t$, where $s=\sum_{a\in A} s$, $t=\sum_{a\in A} a^2$. Commented Feb 27, 2020 at 7:00
• ... and the same trick works for any $k$ Commented Feb 27, 2020 at 7:12

No. Moreover, for any set $$A\subset \mathbb{C}$$, $$|A|=n+k-1$$, you may find a not identically zero polynomial $$p_A$$ of degree at most $$k$$ such that $$p_A(x_1,\ldots,x_n)=0$$ for all distinct $$x_i\in A$$. For $$n=1$$ this is already mentioned in OP, so further I suppose that $$n>1$$.

For $$k-1$$ variables $$t_1,\ldots,t_{k-1}$$ denote $$p_i=\sum_{j=1}^{k-1} t_j^i$$. We may express $$p_k$$ as a polynomial in $$p_1,\ldots,p_{k-1}$$. This gives us a polynomial $$h$$ such that $$h(p_k,p_{k-1},\ldots,p_1)\equiv 0$$, and $$h(z_k,\ldots,z_1)$$ is weighted homogeneous with weighted degree $$k$$: for any monomial $$\prod z_i^{c_i}$$ in $$h$$ we have $$\sum ic_i=k$$. Next, consider $$k$$-th variable $$t_k$$ and the polynomial $$F(t_1,\ldots,t_k):=h\left(\sum_{j=1}^{k} t_j^k,\sum_{j=1}^{k} t_j^{k-1},\ldots,\sum_{j=1}^{k} t_j\right).$$ $$F$$ is symmetric, not identically zero (since $$h$$ is not identically zero and the guys $$\sum_{j=1}^{k} t_j^i$$ which we substitute to $$h$$ may take any complex values), is homogeneous of degree $$k$$. Also $$F$$ takes zero value when one of $$t_i$$'s is zero. Therefore $$F$$ is divisible by $$t_1\ldots t_k$$, and since $$\deg F=k$$ we get $$F=c\,t_1\ldots t_k$$ for certain non-zero constant $$c$$.

Now denote $$\alpha_i=\sum_{a\in A} a^i$$ and take the polynomial $$p_A(x_1,\ldots,x_n)=h\left(\alpha_k-\sum x_i^k,\alpha_{k-1}-\sum x_i^{k-1},\ldots,\alpha_1-\sum x_i\right).$$ From the above properties of $$h$$ we get $$\deg p_A\leqslant k$$ and $$p_A(x_1,\ldots,x_n)=0$$ whenever $$x_1,\ldots,x_n$$ are distinct elements of $$A$$. It remains to show that $$p_A$$ is not identically zero. For this aim we choose $$k$$ non-zero elements $$a_1,\ldots,a_k\in A$$, denote other elements of $$A$$ by $$a_{k+1},\ldots,a_{k+n-1}$$ and substitute $$x_i=a_{k+i}$$ for $$i=1,\ldots,n$$ and $$x_n=0$$ to $$p_A$$. This value of $$p_A$$ is nothing but $$F(a_1,\ldots,a_k)\ne 0$$.

• Why is the total degree of $p_A$ $k$? Commented Feb 27, 2020 at 7:25
• Because $h(p_k,p_{k-1},\ldots,p_1)$ is homogeneous of degree $k$ (where $p_i=\sum_{i=1}^{k-1} t_i^k$), thus degree of $p_A$ is at most $k$. If it is less than $k$, multiply it by something. If it is identical 0, well, we need some additional argument. But at least it is not identical zero for some some sets $A$, that is ok for OP. Commented Feb 27, 2020 at 7:37
• I see. Would you care to explain why $h$ with such degree bounds exists? I understand that $p_1,\dots,p_k$ are algebraically dependent, but this seems to be a much stronger property. Commented Feb 27, 2020 at 8:34
• @EmilJeřábek3.0 it is some basics of symmetric polynomials: any symmetric polynomial may be expressed as a polynomial in $p_1,\ldots,p_{k-1}$, in particular $p_k$. Commented Feb 27, 2020 at 9:04
• Yes. But why it can be done with such tight constraints on the monomials? Commented Feb 27, 2020 at 9:33