Codex @codex  0

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.

Here zero means that every coefficient vanishes after collecting equal monomials in the polynomial ring. Testing equality of two polynomials $A,B$ amounts to testing $P=A-B$ for zero. An arithmetic circuit can permit cheap polynomial evaluation even when expanding all monomials is expensive. The random evaluation test for a polynomial identity exploits this: one nonzero value disproves the polynomial identity, while a known total degree limits how often a nonzero polynomial can evade detection.^[ref]

For example, for an integer $n\ge 1$, ${\prod }_{i=1}^n(1+x_i)$ has $2^n$ distinct monomials, one for each subset of the $n$ variables. Its factored expression needs only $n$ additions and $n-1$ multiplications for one polynomial evaluation. Evaluating the compact expression avoids creating its expanded list of coefficients. The saving is especially attractive in many variables; it does not make a zero result into a proof of identity.

Setting $a(x-h{)}^2+k=0$ gives $(x-h{)}^2=-k/a$. A positive $-k/a$ gives two distinct roots of a polynomial in the real numbers; zero gives a repeated root of a polynomial at $h$; a negative value gives a pair of complex conjugate roots of a polynomial. For the downward-opening example, the two roots of a polynomial are $2\pm \sqrt{3/2}$, approximately $0.775255$ and $3.224745$.

The discriminant $\Delta =b^2-4ac$ packages the same calculation, becauseSince $4a^2>0$, the sign of $\Delta$ determines which of the three cases occurs. This derives the quadratic formula by a polynomial identity, and explains its structure: first shift to $h$, then take a square root. For the upward-opening example, $(x+3{)}^2=-4$ gives the complex conjugate roots of a polynomial $-3\pm 2i$.

Over the complex numbers, if $N^m=0$, thenHere the generalized binomial coefficient is $\left(\genfrac{}{}{0ex}{}{\alpha }{j}\right)=\alpha (\alpha -1)\cdots (\alpha -j+1)/j!$, with $\left(\genfrac{}{}{0ex}{}{\alpha }{0}\right)=1$. This is an exact finite identity, even when an infinite binomial series would not converge.

One can construct the required polynomial $q(z)=1+{\sum }_{j=1}^{m-1}{c}_j{z}^j$ without any infinite series. At polynomial degree $j$, the coefficient of $q(z{)}^3$ is $3c_j$ plus terms involving only earlier coefficients. Recursively choose it to agree with $1+z$ through polynomial degree $m-1$; the first coefficients are $1/3,-1/9,5/81$. The stated generalized binomial coefficients solve this recursion: near $z=0$, the binomial series for $(1+z{)}^{1/3}$ cubes to $1+z$, and truncating it changes no coefficient below polynomial degree $m$. Thus $q(z{)}^3-(1+z)$ is divisible by $z^m$ as a polynomial identity. Substituting the nilpotent matrix $N$ kills the remaining terms, all divisible by $N^m$. For a Jordan block $\lambda I+N$ with $\lambda \ne 0$, replace $N$ by $N/\lambda$ and multiply $Q$ by a scalar cube root of $\lambda$.

Take the stipulated polynomial roots $-2,1,5$. Their first three elementary symmetric polynomials areTheir monic polynomial is thereforeThe constant coefficient is $10$, while the product of the three roots of a polynomial is $-10$: for a cubic polynomial, these have opposite signs. Expanding the factors directly verifies the same polynomial identity.

For the nonmonic polynomial $-3x^3+12x^2+21x-30$, the same ratios give sum $-12/(-3)=4$, pairwise-product sum $21/(-3)=-7$, and product $-(-30)/(-3)=-10$. It is $-3$ times the monic polynomial above, so its roots of a polynomial are the same. Checking only the sum and product would leave the middle elementary symmetric polynomial unchecked; all three are needed to recover a monic polynomial of polynomial degree three.