Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting

Question

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

Answer 1

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