Randomized Black-Box PIT for Small Depth +-Regular Non-Commutative Circuits

Let $𝐌=f({𝐌}_{{𝐱}_{\mathrm{𝟏}}},{𝐌}_{{𝐱}_{\mathrm{𝟐}}},\mathrm{\dots },{𝐌}_{{𝐱}_{𝐧}})$. Then we consider the output of the automaton as:

which is a polynomial in the variables $\xi \bigsqcup Y\bigsqcup Z$.

Suppose a monomial $m$ is computed by a $+$-regular circuit $C$. The monomial $m$ has non-zero coefficient in ${\prod }_{j\in [D_2]}{Q}_{ij}$ for some $i\in [s]$. This monomial can be written as $m=m_1\cdot m_2\mathrm{\cdots }{m}_{D_2}$, where each sub-monomial $m_j\in X^{D_1}$ has non-zero coefficient in $Q_{ij}$.

Next, we consider the output of the substitution automaton $𝒜$ on $m$. The automaton knows how to replace/substitute any variable $x_j$ at any state $q$. Suppose $m=x_{i_1}.x_{i_2}.x_{i_3}\mathrm{\dots }{x}_{i_D}$, the output of the substitution automaton $𝒜$ on the monomial $m$ is given by

where ${𝐌}_{𝐦}={𝐌}_{{𝐱}_{{𝐢}_{\mathrm{𝟏}}}}\cdot {𝐌}_{{𝐱}_{{𝐢}_{\mathrm{𝟐}}}}\mathrm{\cdots }{𝐌}_{{𝐱}_{{𝐢}_{𝐃}}}$. Each variable $x_i,i\in [n]$, is substituted by a degree two monomial over $\xi \bigsqcup Y\bigsqcup Z$ (one n.c. variable and one commutative variable). Consequently, the automaton transforms the monomial $m$ into a degree $2D$ polynomial over $\xi \bigsqcup Y\bigsqcup Z$. Importantly, the new n.c. degree (i.e., sum of exponents of $\xi$ variables) equals to the original degree $D$.

The automaton has exponentially many paths (with states allowed to repeat) from $q_0$ to $q_{s-1}$, all labeled by the same monomial $m$. Each computation path transforms the monomial $m$, originally over the variables $X$, into a new monomial over $\xi \bigsqcup Y\bigsqcup Z$.

For any path $\rho$ from $q_0$ to $q_{s-1}$, we denote the transformed monomial as $m_{\rho }$. The polynomial computed by ${𝐌}_{𝐦}[q_0,q_{s-1}]$ is given by

which is a polynomial in $𝔽[Y\bigsqcup Z]⟨\xi ⟩$. Recall that n.c. polynomials are $𝔽$-linear combinations of words/strings (called monomials). For a n.c. monomial $m$, we can identify the variable at position $e$ in $m$, where $1\le e\le |m|$.

Recall that $m$ can be written as $m=m_1\cdot m_2\mathrm{\cdots }{m}_{D_2}$. Each computation path $\rho$ substitutes each n.c. variable in $m$ according to the automaton’s transition rules, resulting in a monomial $m_{\rho }$ over new variables $\xi \bigsqcup Y\bigsqcup Z$. We group all commutative variables appearing in $m_{\rho }$ and denote it by $c_m$, which is a commutative monomial over $Y\bigsqcup Z$. The resulting monomial $m_{\rho }$ has the following form.

For $i\ne j$, the exponents of the $\xi$ variables in the sub-monomials $m_i^{\prime }$ and $m_j^{\prime }$ can vary. In particular, it is generally possible that $(i_1,i_2,\mathrm{\dots },i_s)\ne (j_1,j_2,\mathrm{\dots },j_s)$.

It is important to note that the number of new sub-monomials $m_i^{\prime }$, denoted as $N$, may not be equal to $D_2$. This is because $N$ depends on how many times the path $\rho$ returns to the initial state $q_0$. Also, the sum of exponents of $\xi$ variables in each sub-monomial $m_i^{\prime }$ in $m_{\rho }$ can vary. This leads us to consider two possible cases for each computation path $\rho$ that starts at $q_0$ and ends at $q_{s-1}$: (recall $m=m_1\cdot m_2\mathrm{\cdots }{m}_{D_2}$).

• $\mathrm{■}$

  Case 1: For each , the boundary between $m_j$ and $m_{j+1}$ in $m$ is respected by the path $\rho$. In this computation path $\rho$, the state of $𝒜$ is at $q_0$ precisely when it begins processing each sub-monomial $m_j\in X^{D_1}$ for $j\in [D_2]$. This means that when $𝒜$ reads the last variable of the sub-monomial $m_{j-1}$ (for $j>1$), it transitions back to state $q_0$. As a result, $𝒜$ is in state $q_0$ exactly when it reads the first variable of the sub-monomial $m_j$. This holds true for all sub-monomials $m_j$ where $j\in [N]$. By Proposition 8, the transformed monomial can be expressed as: $m_{\rho }=c_m\cdot m_1^{\prime }\cdot m_2^{\prime }\mathrm{\cdots }{m}_N^{\prime }$ where $c_m$ is a monomial over $Y\bigsqcup Z$ and each $m_{\mathrm{\ell }}^{\prime }$ is of form $m_{\mathrm{\ell }}^{\prime }={\xi }_1^{{\mathrm{\ell }}_1}\mathrm{\cdots }{\xi }_s^{{\mathrm{\ell }}_s}$. In this case, we observe that $N=D_2$ since there are exactly $D_2$ sub-monomials in $m$. or

• $\mathrm{■}$

  Case 2: For some , the boundary between $m_j$ and $m_{j+1}$ in $m$ is not respected by the path $\rho$. In this case, there exists a sub-monomial $m_j$, where $j\in [D_2]$, such that either (1) the computation path $\rho$ visits the state $q_0$ while processing the variable located at position $c$, where . This means $\rho$ returns to $q_0$ in the middle of processing $m_j$. or (2) the path $\rho$ is in a state $q_j,j\ne 0$ (i.e., other than the initial state $q_0$) while processing the variable that appears at the first position of the sub-monomial $m_j$. By Proposition 8, the transformed monomial can be expressed as: $m_{\rho }=c_m\cdot m_1^{\prime }\cdot m_2^{\prime }\mathrm{\cdots }{m}_N^{\prime }$ where $c_m$ is a monomial over $Y\bigsqcup Z$ and each $m_{\mathrm{\ell }}^{\prime }$ is of form $m_{\mathrm{\ell }}^{\prime }={\xi }_1^{{\mathrm{\ell }}_1}\mathrm{\cdots }{\xi }_s^{{\mathrm{\ell }}_s}$. In this case, we cannot definitively say whether $N$ is equal to $D_2$ or not.

In Case 1, we can make the following important observation about the obtained monomial $m_{\rho }$. Recall that $D_1$ is the degree of $Q_{ij}$ polynomial for all $i\in [s]$ and $j\in [D_2]$.

For all paths $\rho$ that satisfy Case 2, this is not true. We note this down as the following claim.

We crucially utilize Claims 10 and 11 later to ensure the non-zeroness of the transformed commutative polynomial.

For a monomial $m=m_1\cdot m_2\mathrm{\cdots }{m}_{D_2}$, we define the polynomial ${\widehat{f}}_m$ as the sum of all monomials that are obtained from computation paths $\rho$ labeled by $m$ from Case 1 above. Similarly, the polynomial $F_m$ is defined as the sum of all monomials obtained from computation paths $\rho$ labeled by $m$ from Case 2 above. We consider the output of the substitution automaton $𝒜$ on the given n.c. polynomial $f\in 𝔽⟨X⟩$. The output of the automaton is the sum of all monomials produced by computation paths $\rho$ starting from $q_0$ and leading to $q_{s-1}$, with these paths labeled by monomials generated by a depth-5 $+$-regular circuit.

Let $Mon(f)$ be the set of all monomials computed/generated by the given depth-5 $+$-regular circuit computing $f$. That is, suppose $m$ is computed by ${\prod }_{j\in [D_2]}{Q}_{i,j}$ for some $i\in [s]$, with coefficient ${\alpha }_{m,i}$ then ${\alpha }_{m,i}\cdot m\in Mon(f)$. Let

We refer to $F$ as the sum of spurious monomials obtained from the automaton, which can be viewed as noise resulting from our method.

We assume that the linear forms in the $Q_{i,j}$ polynomials are numbered from 1 to $D_1$. For $I\subseteq [D_1]$ with size at most $s-1$, define $Q_{i,j,I}$ as the polynomial obtained from $Q_{i,j}$ by treating linear forms indexed by $I$ as non-commuting and the rest of the linear forms as commuting. We also substitute the n.c. variables that appear in linear forms indexed by $I$ with double-indexed commutative variables $Y$, as shown in the substitution automaton.

We have the following claim regarding the polynomial $\widehat{f}$.

Let

Then we can express $\widehat{f}$ as:

The output of the substitution automaton $𝒜$ on the polynomial $f$ is given by:

This is stated in the following claim.

We establish that $f^{\prime }$ is non-zero by first proving that $\widehat{f}$ is not zero. This is shown in Lemma 15, which builds on the result of PIT for $\mathrm{\Sigma }{\mathrm{\Pi }}^{\ast }\mathrm{\Sigma }$ circuits (see Section 6.2 in [4]). We briefly discuss this result.

Let $Z=\{z_1,\mathrm{\dots },z_n\}$ be the set of new commuting variables. Let $g\in 𝔽⟨X⟩$ be a polynomial of degree $D$ computed by a $\mathrm{\Sigma }{\mathrm{\Pi }}^{\ast }\mathrm{\Sigma }$ circuit of size $s$. Then $g$ can be expressed as $g={\sum }_{i\in [s]}{\prod }_{j\in [D]}{L}_{ij}$, where $L_{ij}$ are homogeneous linear forms. Let $P_i={\prod }_{j\in [D]}{L}_{ij}$, $i\in [s]$. We have $g={\sum }_{i\in [s]}{P}_i$. For $I\subseteq [D]$ with size at most $s-1$, define $P_{i,I}$ as the polynomial obtained from $P_i$ by treating linear forms indexed by $I$ as non-commuting and the rest of the linear forms as commuting. We replace each n.c. variable $x_i$ appearing in $[D]\setminus I$ by a new commuting variable $z_i$.

The number of n.c. linear forms appearing in $P_{i,I}\in 𝔽[Z]⟨X⟩$ is bounded by . This is because the linear forms that appear with indices other than those in $I$ are treated as commutative. Consequently, the number of non-commutative linear forms in $P_{i,I}\in 𝔽[Z]⟨X⟩$ is bounded by . We refer to this as the n.c. degree of the polynomial $P_{i,I}$. Since this degree is small, $P_{i,I}$ can be converted into a commutative polynomial while preserving its non-zeroness. Let $P_{i,I}^{(c)}$ denote the commutative polynomial obtained from $P_{i,I}$ and define $g_I={\sum }_{i\in [s]}{P}_{i,I}^{(c)}$. To keep all guesses of the set $I$ distinct, additional commutative variables $\xi =\{{\xi }_1,{\xi }_2,\mathrm{\cdots },{\xi }_{k+1}\}$ are introduced in [4]. The transformed commutative polynomial obtained in [4] is given by:

where ${\xi }_I^{\prime }={\xi }_1^{{\mathrm{\ell }}_1-1}.{\xi }_2^{{\mathrm{\ell }}_2-{\mathrm{\ell }}_1-1}\mathrm{\cdots }{\xi }_{k+1}^{D-{\mathrm{\ell }}_k}$ with $I=\{{\mathrm{\ell }}_1,{\mathrm{\ell }}_2,\mathrm{\cdots },{\mathrm{\ell }}_k\}$. The degree of the monomial ${\xi }_I^{\prime }$ is $D-|I|$.

By Lemma 6.2 in [4], there exists a set of indices $I\subseteq [D]$, , such that $g_I\ne 0$ implying $g^{\star }\ne 0$. Replacing ${\xi }_I^{\prime }$ with ${\xi }_I={\xi }_1^{{\mathrm{\ell }}_1}.{\xi }_2^{{\mathrm{\ell }}_2-{\mathrm{\ell }}_1}\mathrm{\cdots }{\xi }_{k+1}^{D-{\mathrm{\ell }}_k}$ in $g^{\star }$ retains the non-zeroness of $g^{\star }$ while the degree of ${\xi }_I$ becomes $D$.

We have the following lemma that shows $\widehat{f}\ne 0$.

We will need a generalization of Lemma 15 for polynomials computed by larger depth +-regular circuits.

The resulting n.c. polynomial $\widehat{f}$ (from Lemma 15) still has an exponential degree in $\xi$ variables, but each ${\widehat{Q}}_{ij}$ is structured as $s$-ordered polynomials. Importantly, $\widehat{f}$ does not contain any monomials from the spurious polynomial $F={\sum }_{\begin{array}{c}m\in Mon(f)\end{array}}{F}_m$.

We now show that each $Q_{ij}$ polynomial can be converted into a structured polynomial ${\widehat{Q}}_{ij}$. The key property of this transformation is that there is a bijection between the monomials of $Q_{ij}$ and those of ${\widehat{Q}}_{ij}$, which ensures that ${\widehat{Q}}_{ij}\equiv 0$ if and only if $Q_{ij}\equiv 0$.

It is easy to observe the following because the first index of each variable $z_{\mathrm{\ell }k}$ indicates the position of the variable $x_k$ within each $Q_{ij}$.

This guarantees that for the small degree case, we can transform the polynomial $f$ similarly to Lemma 15, ensuring that each $Q_{ij}$ is transformed into ${\widehat{Q}}_{ij}$ which can be regarded as a commutative polynomial without making it zero. While ${\widehat{Q}}_{ij}$ remains a n.c. polynomial over $Z$, we acknowledge that our model is black-box and we do not know the value of $D_1$. However, for the purpose of analyzing the existence of matrices of small dimensions for identity testing, we can assume $D_1$ is known.

Thus, we can successfully transform the given polynomial in both scenarios – whether $D_1\ge s-1$ or – ensuring that the resulting ${\widehat{Q}}_{ij}$ can be considered as a commutative polynomial without making it a zero polynomial.

However, it is important to note that this transformation alone will not provide a black-box PIT, as we cannot guarantee the non-zeroness of the sum of products of these ${\widehat{Q}}_{ij}$ polynomials. This is because if we simply treat all ${\widehat{Q}}_{ij}$ as commutative, the variables across different ${\widehat{Q}}_{ij}$ polynomials could mix, which may lead to cancellations. At this stage, the variables in $Z$ are still considered n.c. in the polynomial $\widehat{f}$.

By Lemma 15, we established that $\widehat{f}\not\equiv 0$. Next, we show that the polynomial $f^{\prime }=\widehat{f}+F\not\equiv 0$. In $\widehat{f}$, for every monomial $m=m_1{m}_2\mathrm{\cdots }{m}_{D_2}$, and for all $\mathrm{\ell }\in [D_2]$ each $m_{\mathrm{\ell }}$ takes the form ${\xi }_1^{{\mathrm{\ell }}_1}.{\xi }_2^{{\mathrm{\ell }}_2}\mathrm{\cdots }{\xi }_s^{{\mathrm{\ell }}_s}$ where ${\sum }_{k\in [s]}{\mathrm{\ell }}_k=D_1$ (see Claim 10). However, this property does not hold for monomials appearing in $F$ (see Claim 11). Specifically, for any monomial $m^{\prime }=m_1^{\prime }{m}_2^{\prime }\mathrm{\cdots }{m}_N^{\prime }$ in $F$, there exists a sub-monomial $m_a^{\prime }={\xi }_1^{a_1}.{\xi }_2^{a_2}\mathrm{\cdots }{\xi }_s^{a_s}$ such that ${\sum }_{h\in [s]}{a}_h\ne D_1$. This distinction ensures that the monomials of $\widehat{f}$ do not cancel with those of $F$. Thus, we conclude that $f^{\prime }=\widehat{f}+F\not\equiv 0$. It’s important to note that if $f\equiv 0$ then clearly $f^{\prime }\equiv 0$ as well (converse statement). We note these observations in the following claim.

Next, we can simplify the polynomial $f^{\prime }$ using the Polynomial Identity Lemma for commutative polynomials. We replace the commuting variables $Y\bigsqcup Z$ with scalar substitutions from $𝔽$ or an extension field, yielding a non-zero polynomial. Let us denote this resulting non-zero polynomial as $\tilde{f}$. After this substitution, the only remaining variables in $\tilde{f}$ will be n.c. variables $\xi$.

Let us denote new polynomials obtained after replacing the commuting variables by scalars in $\widehat{f}$ and $F$ by ${\widehat{f}}_1$ and $F_1$ respectively. That is, $\tilde{f}={\widehat{f}}_1+F_1$.

One of the goals of this transformation is to ensure that if ${\xi }_s$ is followed by ${\xi }_1$ in the transformed monomials (for all such occurrences of ${\xi }_s$ followed by ${\xi }_1$), there must be a transition from $Q_{i,j}$ to $Q_{i,j+1}$ for some $j\in [D_2]$. As noted, we cannot be sure of this. However, all those monomials where this transition occurs are captured in the structured part ${\widehat{f}}_1$. Since there is no such structure in $F_1$, we cannot conclude anything about the monomials appearing in the spurious part $F_1$.

We can envision a substitution automaton $𝒜$ for Theorem 28 as follows. By applying the matrix composition Lemma, we can combine the substitution matrices obtained from Steps (1) through (3), along with the modifications to coefficients, into a single substitution matrix $𝐌=({𝐌}_{{𝐱}_{\mathrm{𝟏}}},{𝐌}_{{𝐱}_{\mathrm{𝟐}}},\mathrm{\dots },{𝐌}_{{𝐱}_{𝐧}})$ of dimension $O(s^6)$. We then evaluate the polynomial as $𝐎=f({𝐌}_{{𝐱}_{\mathrm{𝟏}}},{𝐌}_{{𝐱}_{\mathrm{𝟐}}},\mathrm{\dots },{𝐌}_{{𝐱}_{𝐧}})$.

The output of the substitution automaton is defined as the sum of several entries of the matrix $𝐎$ (refer to the polynomial $f^{(c)}$ defined in the proof of Theorem 26).

It is crucial to note that each entry of the matrices in $𝐌=({𝐌}_{{𝐱}_{\mathrm{𝟏}}},{𝐌}_{{𝐱}_{\mathrm{𝟐}}},\mathrm{\dots },{𝐌}_{{𝐱}_{𝐧}})$ is a monomial over $Y\bigsqcup Z\bigsqcup \zeta \bigsqcup \chi \bigsqcup W$, where $Y\bigsqcup Z$ are commutative variables from Step (1), and $\zeta \bigsqcup \chi$ are commutative variables from Step (2), while $W$ contains commutative variables from Step (3).

As noted in Steps (1) and (2), we can replace the commutative variables in $Y\bigsqcup Z\bigsqcup \zeta \bigsqcup \chi$ with scalars without losing the non-zeroness of the output polynomial. Since these commutative variables are disjoint, for simplicity in the analysis, we substitute them with scalars. That is, there exist scalar substitutions for the variables in $Y\bigsqcup Z\bigsqcup \zeta \bigsqcup \chi$ such that non-zeroness is preserved. To avoid carrying these variables throughout all derivations, we replace them with scalars, and by the DeMillo–Lipton–Schwartz–Zippel lemma, such substitutions are guaranteed to exist. After these replacements, each entry of the matrices in $𝐌=({𝐌}_{{𝐱}_{\mathrm{𝟏}}},{𝐌}_{{𝐱}_{\mathrm{𝟐}}},\mathrm{\dots },{𝐌}_{{𝐱}_{𝐧}})$ transforms into scalar multiples of variables over $W$. We denote the resulting matrices as ${𝐌}^{\prime }=({𝐌}_{{𝐱}_{\mathrm{𝟏}}}^{\prime },{𝐌}_{{𝐱}_{\mathrm{𝟐}}}^{\prime },\mathrm{\dots },{𝐌}_{{𝐱}_{𝐧}}^{\prime })$.

We can construct a substitution automaton $𝒜$ such that the substitution matrix for the variable $x_i$ is given by the matrix ${𝐌}_{{𝐱}_{𝐢}}^{\prime }$, where the entries are scalar multiples of variables in $W$. These entries correspond to transitions that substitute a n.c. variable with a scalar multiple of a variable in $W$. This automaton $𝒜$ effectively transforms $f$ into an $s^2$-ordered polynomial $f^{(c)}$ while preserving its non-zeroness.

We can view the resulting $s^2$-ordered polynomial $f^{(c)}$ as a n.c. polynomial over $W$. This idea is crucial for developing black-box randomized polynomial identity testing (PIT) for circuits of larger depths using induction.

It is important to note that the monomials of $f^{(c)}$ do not correspond to a single entry of the output matrix $𝐎=f({𝐌}_{{𝐱}_{\mathrm{𝟏}}}^{\prime },{𝐌}_{{𝐱}_{\mathrm{𝟐}}}^{\prime },\mathrm{\dots },{𝐌}_{{𝐱}_{𝐧}}^{\prime })$. Instead, they represent the sum of several entries, as indicated in the polynomial $f^{(c)}$ defined in the proof of Theorem 26. Effectively, the column numbers of these entries form the set of accepting states for the new automaton $𝒜$, with row 1 serving as the starting state of this automaton.