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

Question

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$.

Answer 1

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.

Answer 2

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

Answer 3

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$.