# Does every nonzero polynomial take a nonzero value at one of its multi-indices?

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.

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