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



Smallest $S\subset \mathbb C$ on which no degree $k$ polynomial always vanishes?
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.


