1
$\begingroup$

Let me define the problems first

Polynomial Identity Testing $(\mathsf{PIT\text{}})$

Given : A polynomial $p$ over some field $\mathbb{F}$.

Decide : Are all coefficients of the monomials of $p$ are equal to zero ?

Polynomial Identity Testing $(\mathsf{PIT1\text{}})$

Polynomial identity testing defined in non commutative setting i.e. $x.y \neq y.x $

Given : A polynomial $p$ over some field $\mathbb{F}$.

Decide : Are all coefficients of the monomials of $p$ are equal to zero?

Evaluates to Zero Everywhere $(\mathsf{EZE\text{}})$

Given : A polynomial $p$ over some field $\mathbb{F}$.

Decide : Is it true that for every choice of numbers $a \in \mathbb{F}$, the value of $p(a)$ is the number $0$.

My question : Are $\mathsf{PIT\text{}}$ and $\mathsf{PIT1\text{}}$ equivalent?

Reference : http://www.cs.ubc.ca/~nickhar/W12/Lecture9Notes.pdf

$\endgroup$
  • 1
    $\begingroup$ You are asking two questions. The usual rule is one question per post. $\endgroup$ – Yuval Filmus Mar 6 '17 at 11:06
  • $\begingroup$ I've edited the question to remove the second question, so that this fits our rules of one question per post. You can post the second question separately (use 'Ask Question' in the upper-right). You can gain access to the older versions of the question by clicking on the revision history ('click on 'edited...' under the question). $\endgroup$ – D.W. Mar 6 '17 at 17:45
2
$\begingroup$

PIT and PIT1 are not equivalent. For example, $xy-yx$ is the zero polynomial in the commutative setting but not in the non-commutative setting. You can get a non-commutative analog of EZE by considering large enough matrices, where large enough depends on the formal degree of the polynomial involved.

Suppose that $P$ is a multivariate polynomial in $x_1,\ldots,x_n$ which is not identically zero. We want to find a point where it is non-zero. The proof is by induction on $n$. If $n=0$ then $P$ is some non-zero constant, and there is nothing to prove. If $n>0$, write $$ P = \sum_{i=0}^d Q_i x_n^i, $$ where the $Q_i$ are polynomials in $x_1,\ldots,x_{n-1}$, and $Q_d$ is not identically zero. The induction hypothesis shows that $Q_d(\alpha_1,\ldots,\alpha_{n-1}) \neq 0$ for some real $\alpha_1,\ldots,\alpha_{n-1}$. Making this substitution, we obtain a univariate polynomial $P'$ in $x_n$ which is not identically zero. If $|\alpha_n|$ is large enough, simple estimates show that $P'(\alpha_n) \neq 0$, and so $P(\alpha_1,\ldots,\alpha_n) \neq 0$.

Here are the simple estimates: if $P' = \sum_{i=0}^d c_i x^i$ and $|\alpha| \geq 1$ then $$ |P'(\alpha)| \geq |c_d| |\alpha|^d - \sum_{i=0}^{d-1} |c_i| |\alpha|^i \geq |\alpha|^{d-1} |c_d| \left(|\alpha| - \frac{\sum_{i=0}^{d-1} |c_i|}{|c_d|}\right). $$ This is non-zero if $|\alpha| > 1+\sum_{i=0}^{d-1} |c_i|/|c_d|$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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