A polynomial $p$ can be specified by its coefficient function, a finitely supported function $c:\mathbb N^d_0\to\mathbb R.$ Here $\mathbb N_0=\{0,1,2,\dots\}$ and $d\in\mathbb N_0.$ The value of $p$ at a point $x\in\mathbb R^d$ is $p(x)=\sum_{\alpha\in\mathbb N^d_0}c(\alpha)x_1^{\alpha_1}\dots x_d^{\alpha_d}$ (the sum makes sense by the assumption that $c$ has finite support). We call $p$ non-zero if $c(\alpha)\neq 0$ for some $\alpha.$

For all non-zero $p$ does there exist $\alpha$ such that $c(\alpha)\neq 0$ and $p(\alpha)\neq 0$?

Equivalently: for all finite $A\subset\mathbb N_0^d,$ is the $|A|\times |A|$ matrix defined by $M_{\alpha,\beta}=(\alpha_1^{\beta_1}\dots\alpha_d^{\beta_d})$ non-singular? (In one direction. take $A$ to be the support of a counterexample $c,$ which is then in the kernel of $M.$ In the other direction, take $c$ to be a vector in the kernel of a counterexample $M.$) Call $A$ "good" if this holds. I have checked some randomly generated sets $A$ are good. Also:

  • If $A\subset \mathbb N_0^d$ and $B\subset \mathbb N_0^e$ are both non-empty and good then the Cartesian product $A\times B\subset\mathbb N_0^{d+e}$ is good. In terms of matrices this is because the Kronecker product of two positive-dimensional square matrices is non-singular iff the two matrices are non-singular.

  • Let $A\subset \mathbb N_0^{d+1}.$ If the sets defined by $A_0=\{\alpha\in A\mid \alpha_{d+1}=0\}$ and $A_+=\{\alpha\in A\mid \alpha_{d+1}>0\}$ are good then $A$ is good. Proof: assume $A_0$ and $A_+$ are good and consider a polynomial $p$ with coefficients $c$ zero outside $A.$ If $p(\alpha)=0$ for $\alpha\in A_0$ then $c(\alpha)=0$ for all $\alpha\in A_0,$ because $A_0$ is good and the $A_+$ coefficients don't contribute to $p(x)$ when $x_{d+1}=0.$ So $c$ is zero outside $A_+,$ and hence $p$ must also be zero on $A_+$ because $A_+$ is good.

  • If $A\subset \mathbb N_0^1$ then $A$ is good. Proof: by the last point we can assume $0\not\in A.$ By Descartes' rule of signs a univariate polynomial with at most $|A|$ non-zero coefficients has at most $|A|-1$ positive zeroes.

  • $A\subset \mathbb N_0^d$ is good if it is downwards-closed, i.e. for all $\beta\in A$ and all $\alpha$ such that $\alpha_i\leq\beta_i$ for all $1\leq i\leq d$ we have $\alpha\in A.$ Proof: apply the forward difference operator $(\Delta p)(x)=p(x_1,\dots,x_{d-1},x_d+1)-p(x).$ By induction $A'=\{\alpha \in A\mid (\alpha_1,\dots,\alpha_d+1)\in A\}$ is good. If $p$ had zero coefficients outside $A$ and also vanished on $A,$ then $\Delta p$ would have zero coefficients outside $A'$ and vanish on $A',$ which forces $\Delta p$ to be the zero polynomial. This means $p$ has zero coefficients outside $A_0$ (as defined in the last point) and we can apply induction on dimension.

  • A small variation: if $A\subset \mathbb N_0^d$ is downwards closed and $\alpha\in\mathbb N_0^d$ then the shifted set $\alpha+A=\{\alpha+\beta\mid \beta\in A\}$ is good. This follows from the same argument but using the modified forwards difference operator defined by $\Delta' p=x^\alpha \Delta x^{-\alpha} p.$

R. Zippel's "Interpolating polynomials from their values" calls similar questions "zero avoidance problems", but I couldn't find anything answering this question.

  • $\begingroup$ I think I can show this is indeed true for the univariate case. But I think you have this already in your third item $\endgroup$
    – quantum
    Jan 22, 2019 at 13:30


You must log in to answer this question.