21
$\begingroup$

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

$\endgroup$
0

3 Answers 3

11
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Oh, nice. Now I'm not sure whether I suspect the bound can be met in general. $\endgroup$ Commented Feb 22, 2020 at 11:56
  • 5
    $\begingroup$ 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$. $\endgroup$ Commented Feb 27, 2020 at 7:00
  • $\begingroup$ ... and the same trick works for any $k$ $\endgroup$ Commented Feb 27, 2020 at 7:12
10
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Why is the total degree of $p_A$ $k$? $\endgroup$ Commented Feb 27, 2020 at 7:25
  • $\begingroup$ 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. $\endgroup$ Commented Feb 27, 2020 at 7:37
  • $\begingroup$ 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. $\endgroup$ Commented Feb 27, 2020 at 8:34
  • $\begingroup$ @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$. $\endgroup$ Commented Feb 27, 2020 at 9:04
  • 1
    $\begingroup$ Yes. But why it can be done with such tight constraints on the monomials? $\endgroup$ Commented Feb 27, 2020 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.