Efficient Polynomial Identity Testing over Nonassociative Algebras

Mukhopadhyay, Partha; C. Ramya; Shastri, Pratik

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.56

Efficient Polynomial Identity Testing over Nonassociative Algebras

Partha Mukhopadhyay Chennai Mathematical Institute, India C. Ramya

The Institute of Mathematical Sciences (a CI of Homi Bhabha National Institute), Chennai, India Pratik Shastri

The Institute of Mathematical Sciences (a CI of Homi Bhabha National Institute), Chennai, India

Abstract

We design the first efficient polynomial identity testing algorithms over the nonassociative polynomial algebra. In particular, multiplication among the formal variables is commutative but it is not associative. This complements the strong lower bound results obtained over this algebra by Hrubeš, Yehudayoff, and Wigderson [12] and Fijalkow, Lagarde, Ohlmann, and Serre [9] from the identity testing perspective. Our main results are the following:

$\blacksquare$

We construct nonassociative algebras (both commutative and noncommutative) which have no low degree identities. As a result, we obtain the first Amitsur-Levitzki type theorems [2] over nonassociative polynomial algebras. As a direct consequence, we obtain randomized polynomial-time black-box PIT algorithms for nonassociative polynomials which allow evaluation over such algebras.
$\blacksquare$

On the derandomization side, we give a deterministic polynomial-time identity testing algorithm for nonassociative polynomials given by arithmetic circuits in the white-box setting. Previously, such an algorithm was known with the additional restriction of noncommutativity [4].
$\blacksquare$

In the black-box setting, we construct a hitting set of quasipolynomial-size for nonassociative polynomials computed by arithmetic circuits of small depth. Understanding the black-box complexity of identity testing, even in the randomized setting, was open prior to our work.

Keywords and phrases:

Polynomial identity testing, nonassociative algebra, arithmetic circuits, black-box algorithms, white-box algorithms

Category:

RANDOM

Funding:

C. Ramya: Research supported by INSPIRE Faculty Fellowship of DST.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algebraic complexity theory

DOI:

10.4230/LIPIcs.APPROX/RANDOM.2025.56

Event:

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The goal of algebraic complexity is to study the complexity of computing multivariate polynomials using basic arithmetic operations, such as addition and multiplication. Arithmetic circuits and formulas are among the well-studied models in this area. In particular, arithmetic circuits are directed acyclic graphs whose leaves are labeled by variables or constants, and whose internal nodes (called gates) are labeled with either $+$ or $\times$ . Formulas are circuits whose underlying graph is a tree. Each gate in a circuit computes a polynomial in the natural way and the output of a circuit is said to be the polynomial computed at a distinguished output gate.

There are two central problems studied in algebraic complexity: one is the question of proving size lower bounds for circuits computing explicit polynomials, and the other is the question of derandomizing polynomial identity testing (PIT for short). The PIT problem comes in two variants. First is the black-box setting, where we are given evaluation access to a circuit (given as a black box), and we must decide whether the polynomial it computes is identically zero. The second, seemingly easier is the white-box setting, where we are explicitly given the circuit as a graph to determine whether it computes the zero polynomial.

Baur and Strassen [5] proved that any circuit computing $\sum_{i=0}^{n}x_{i}^{n}$ requires size $\Omega(n\log n)$ . This is the strongest known lower bound for arithmetic circuits. On the other hand, the PIT problem admits a randomized polynomial-time black-box algorithm over the usual polynomial ring $\mathbb{F}[x_{1},\ldots,x_{n}]$ , thanks to the Polynomial Identity Lemma [30, 25, 8] (see Lemma 6 for the exact statement). Here, $\mathbb{F}$ can be any field of sufficient size, and the variables $x_{1},\ldots,x_{n}$ commute under multiplication. For the black-box case, the derandomization problem is essentially equivalent to the efficient construction of small hitting sets. Despite intense efforts over many years, proving strong lower bounds for circuits and derandomizing PIT for circuits have both remained elusive goals. For more on these problems, the reader is referred to the excellent surveys by Shpilka and Yehudayoff [26] and Saxena [24]. In general, the problems of proving lower bounds and derandomizing PIT are closely related and, in fact, nearly equivalent due to an influential result of Impagliazzo and Kabanets [14]. For example, very recently, a subexponential-size hitting set for PIT of low-depth arithmetic circuits was obtained via a breakthrough lower bound result by Limaye, Srinivasan, and Tavenas [18].

The limitation in our understanding of PIT and lower bounds stems from the difficulty of analyzing how a monomial gets canceled at an intermediate step in an arithmetic circuit computation. In the setting of the usual polynomial ring $\mathbb{F}[x_{1},\ldots,x_{n}]$ , multiplication is commutative and associative. In other words, for all $x_{i},x_{j},x_{k}$ we have $x_{i}x_{j}=x_{j}x_{i}$ and $(x_{i}(x_{j}x_{k}))=((x_{i}x_{j})x_{k})$ . A central line of investigation studies arithmetic circuits by restricting the relations satisfied by the multiplication rule. The hope is that, in the absence of such relations, we can better understand cancellations of monomials and gain insight into general circuits. For example, we can drop commutativity while preserving associativity.

If we drop commutativity, we obtain the noncommutative polynomial ring $\mathbb{F}\langle x_{1},\ldots,x_{n}\rangle$ (which remains associative), and noncommutative circuits compute polynomials in the ring $\mathbb{F}\langle x_{1},\ldots,x_{n}\rangle$ . In his pioneering work [20], Nisan proved that the noncommutative Permanent and Determinant polynomials require exponential-size noncommutative algebraic branching programs (ABPs for short). ABPs are a subclass of circuits. Up to polynomial blowup, they simulate formulas and are simulated by circuits. In the noncommutative setting, exponential separations are known between ABPs and circuits [20]. On the PIT side, Raz and Shpilka [22] developed a white-box deterministic polynomial-time algorithm for polynomials computed by noncommutative ABPs. In fact, a quasipolynomial time black-box PIT algorithm has also been designed for the same problem by Forbes and Shpilka [10].

However, if we look at general noncommutative circuits (instead of ABPs), again we see that progress on the questions of lower bounds and derandomizing PIT has remained elusive. In fact, for general circuits, the best lower bound and PIT results over $\mathbb{F}\langle x_{1},\ldots,x_{n}\rangle$ match those over $\mathbb{F}[x_{1}\ldots,x_{n}]$ .

Henceforth, we use $X$ to denote the set $\{x_{1},\ldots,x_{n}\}$ . $\mathbb{F}_{A,C}[X]$ and $\mathbb{F}_{A,\bar{C}}[X]$ stand for the rings $\mathbb{F}[X]$ and $\mathbb{F}\langle{X}\rangle$ , respectively. Instead of dropping commutativity, we may choose to drop associativity. This leads us to the algebra $\mathbb{F}_{\bar{A},C}[X]$ , the polynomial algebra where multiplication is commutative but nonassociative¹¹1Formally, an algebra $\mathbb{A}$ over a field $\mathbb{F}$ is a vector space equipped with a bilinear product.²²2In ${\mathbb{F}_{\bar{A},C}[X]}$ , $(x_{i}(x_{j}x_{k}))\neq((x_{i}x_{j})x_{k})$ even in the case when $x_{i}=x_{j}=x_{k}$ .. If we drop both commutativity and associativity, we obtain the polynomial algebra ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ . On the lower bounds side, very impressive progress has been made in the algebra $\mathbb{F}_{\bar{A},C}[X]$ . Hrubeš, Yehudayoff, and Wigderson [12] proved the first exponential-size lower bounds for circuits computing explicit polynomials in ${\mathbb{F}_{\bar{A},C}[X]}$ . Subsequently, Fijalkow, Lagarde, Ohlmann, and Serre [9] strengthened this result by providing an exact characterization of the size of a minimal circuit computing a polynomial $f\in{\mathbb{F}_{\bar{A},C}[X]}$ in terms of the rank of a certain matrix of coefficients.

On the other hand, in the context of PIT, it is imperative to note that no efficient algorithm is known over the algebra ${\mathbb{F}_{\bar{A},C}[X]}$ , not even a randomized white-box algorithm. This is surprising given the intimate connections between lower bounds and PIT in various settings. Over the algebra ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ , Arvind et al. designed a deterministic white-box polynomial-time algorithm for PIT of arithmetic circuits [4]. Furthermore, as mentioned by the authors in [4], a black-box algorithm is not known even over ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ . Notably, over the algebra $\mathbb{F}\langle{X}\rangle$ , such a randomized PIT algorithm is known due to the Amitsur-Levitzki Theorem [2, 29] (see Theorem 7 for a formal statement).

We note that nonassociative computations are fundamental even beyond algebraic complexity. For example, the composition of operations in computer programs is typically nonassociative. As a concrete algorithmic example, in a seminal work, Valiant designed a sub-cubic algorithm for recognizing Context Free Languages (CFL) [28]. In particular, Valiant developed an algorithm to compute the transitive closure of upper triangular matrices whose entries are elements of a nonassociative monoid [28]. In algebraic complexity, lower bounds for nonassociative circuits have been used prove lower bounds for related associative models of computation [9].

The main technical contributions of this paper are as follows. Over the polynomial algebra ${\mathbb{F}_{\bar{A},C}[X]}$ , we design a white-box deterministic polynomial-time algorithm for the PIT of arithmetic circuits. In the black-box setting, we develop the first randomized polynomial-time PIT algorithm for nonassociative arithmetic circuits (over both ${\mathbb{F}_{\bar{A},C}[X]}$ and ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ ). This is achieved by proving analogues of the Amitsur-Levitzki theorem over the nonassociative polynomial algebras ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ and ${\mathbb{F}_{\bar{A},C}[X]}$ . Moreover, for the classes of circuits over the algebras ${\mathbb{F}_{\bar{A},C}[X]}$ and ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ with polylogarithmic depth, we construct quasipolynomial-size hitting sets over nonassociative algebras of small dimension. To the best of our knowledge, this is the first black-box derandomization result for a well-studied circuit class over a nonassociative polynomial algebra. We elaborate on our results and techniques in the next section.

1.1 Our Results

In this paper, we complement the strong lower bounds results obtained over the algebra ${\mathbb{F}_{\bar{A},C}[X]}$ ([12, 9]) by designing efficient PIT algorithms. Our results work over all fields of sufficiently large size.

1.1.1 Black-box randomized nonassociative PIT (Section 3)

Our first result is a black-box randomized polynomial-time identity testing algorithm for polynomials in ${\mathbb{F}_{\bar{A},C}[X]}$ . Of course, to capture nonassociativity, the natural idea is to evaluate the given polynomial over nonassociative algebras.

In mathematics, nonassociative algebras are very well-studied. For example, one can see the classic work of Albert [13]. In particular, there are various specific algebras of interest which are nonassociative but commutative. The most important such algebras are, perhaps, the Jordan Algebras. Unfortunately, every Jordan Algebra $\mathbb{J}$ satisfies the Jordan Identity: $\forall a,b\in\mathbb{J}$ , we have $(ab)(aa)-(a(b(aa)))=0$ . This means that performing PIT using Jordan Algebras is not possible. To see why, suppose we are given a circuit computing a non-zero polynomial in the ideal of ${\mathbb{F}_{\bar{A},C}[X]}$ generated by $\{(x_{i}x_{j})(x_{i}x_{i})-(x_{i}(x_{j}(x_{i}x_{i})))\mid x_{i},x_{j}\in X\}$ . On any input from $\mathbb{J}$ , the circuit will evaluate to $0$ , whereas the circuit computes a non-zero polynomial. Even over ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ , we have a similar difficulty. For example, Matrix Lie algebras are well studied algebras that are nonassociative and noncommutative, but they satisfy the Jacobi Identity [6].

Thus, in order to obtain a fast black-box algorithm, we need to construct a suitable nonassociative algebra that does not satisfy low (in terms of its dimension) degree identities. We should remark that over the noncommutative polynomial ring $\mathbb{F}\langle X\rangle$ (equivalently, $\mathbb{F}_{A,\bar{C}}[X]$ ), the Amitsur-Levitzki theorem allows us to do black-box randomized PIT for polynomials of degree $\leqslant d$ , using random matrices of dimension $(\lceil d/2\rceil+1)\times(\lceil d/2+1\rceil)$ [2, 29]. In our setting of polynomials in ${\mathbb{F}_{\bar{A},C}[X]}$ , we construct a unital nonassociative, commutative algebra $\mathbb{C}_{d}$ of dimension $d(d+1)^{2}+1$ which does not satisfies any identity of degree $\leqslant d$ .

Lemma 1.

Let $f\in{\mathbb{F}_{\bar{A},C}[X]}$ be a non-zero polynomial of total degree $\leqslant d$ . Then $f$ is not a polynomial identity (PI) for $\mathbb{C}_{d}$ .

To the best of our knowledge, this is the first Amitsur-Levitzki type theorem in the nonassociative setting. As an immediate consequence, we obtain a nonassociative analogue of the Polynomial Identity Lemma.

Theorem 2.

Let $\mathbb{F}$ be a field with $|\mathbb{F}|>d$ , and $S\subset\mathbb{F}$ . Let $f\in{\mathbb{F}_{\bar{A},C}[X]}$ be a non-zero polynomial of degree $\leqslant d$ given as a black-box with query access to evaluations of $f$ on elements of $\mathbb{C}_{d}$ . Let $S\subseteq\mathbb{F}$ with $|S|>d$ . Sample $b_{1},\ldots,b_{n}\in\mathbb{C}_{d}$ as follows: Pick each of the $d(d+1)^{2}+1$ entries of each of the $b_{i}$ ’s uniformly and independently from $S$ . Then

\Pr_{b_{1},\ldots,b_{n}\in\mathbb{C}_{d}}[f(b_{1},\ldots,b_{n})=0]\leqslant d/% |S|.

We construct $\mathbb{C}_{d}$ in two stages. First, we construct a noncommutative, nonassociative algebra $\mathbb{A}_{d}$ (see Section 3.1 for the precise definition) and show that $\mathbb{A}_{d}$ does not satisfy identities of degree $\leqslant d$ . Note that this also gives us a noncommutative, nonassociative analogue of Theorem 2 (see Theorem 12 for exact statement). We prove this by showing that monomials in ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ can be isolated using substitutions from $(\mathbb{A}_{d})^{n}$ . Each monomial $m\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ can be viewed as a rooted, ordered binary tree whose leaves are labeled by variables (see Figure 2 for examples). To each occurrence of a variable $x$ in $m$ , we may associate a level which indicates the depth at which it appears in the monomial $m$ (when viewed as a tree). Noncommutativity of ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ also induces a left to right order in which the variables appear in $m$ . We show that given the left to right order and the corresponding sequence of levels, we can fully reconstruct $m$ (Lemma 8). Using this lemma and a three dimensional version of the set-multilinearization procedure introduced by Forbes and Shpilka [10] in the context of PIT for noncommutative ABPs, we show that $\mathbb{A}_{d}$ does not satisfy identities of degree $\leqslant d$ . The third dimension “keeps track” of the level at which each leaf appears in a monomial. After this, we define the commutative algebra $\mathbb{C}_{d}$ as follows: the $\mathbb{C}_{d}$ product of $x, y$ is the anticommutator³³3The anticommutator of $x, y$ with respect to a product operation $\cdot$ is defined as $x\cdot y+y\cdot x$ . of $x, y$ with respect to the $\mathbb{A}_{d}$ product. In $\mathbb{C}_{d}$ , there is no unique left to right order of the variables that we can associate with a monomial. But there is a set of orders that we can associate with each monomial. This set, together with the corresponding sequence of levels, determines the monomial uniquely. Using this, we show that $\mathbb{C}_{d}$ also does not satisfy identities of degree $\leqslant d$ .

1.1.2 White-box deterministic PIT over ${\mathbb{F}_{\bar{A},C}[X]}$ (Section 4.1)

Next, we consider the white-box identity testing problem over ${\mathbb{F}_{\bar{A},C}[X]}$ . Raz and Shpilka [22] give a white-box linear algebraic algorithm for identity testing of noncommutative algebraic branching programs. Subsequently, their algorithm has been adapted to obtain PIT algorithms in various settings, for example, for Read-Once Algebraic Branching Programs (ROABPs) [10], noncommutative Unique Parse Tree Circuits [16] and circuits over ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ [4]. In this work, we show that an adaption of the Raz-Shpilka algorithm can be used to do PIT for circuits over ${\mathbb{F}_{\bar{A},C}[X]}$ :

Theorem 3.

Let $\Psi$ be a nonassociative arithmetic circuit of size $s$ computing an $n$ variate, degree $\leqslant d$ polynomial $f\in{\mathbb{F}_{\bar{A},C}[X]}$ . Given $\Psi$ as input, we can check whether $f\equiv 0$ deterministically in time ${\mathsf{poly}}(s,n,d)$ .

The main difference in the application of the Raz-Shpilka algorithm in our setting is that in all previous works (that we are aware of), if a monomial $m$ is generated at a product gate $g=g_{1}\times g_{2}$ in the circuit, then there is a unique way it could have been generated: there exist monomials $m_{1}$ , $m_{2}$ such that ${\sf coeff}_{m}(g)={\sf coeff}_{m_{1}}(g_{1})\times{\sf coeff}_{m_{2}}(g_{2})$ . On the other hand since we are working in the commutative setting of ${\mathbb{F}_{\bar{A},C}[X]}$ , there are two ways of generating $m$ at $g$ . Either $m_{1}$ could be contributed by $g_{1}$ and $m_{2}$ by $g_{2}$ , or $m_{2}$ could be contributed by $g_{1}$ and $m_{1}$ by $g_{2}$ . We show (somewhat surprisingly) that the Raz-Shpilka algorithm, suitably modified, works even in this setting.

1.1.3 Black-box deterministic nonassociative PIT (Section 4.2)

We consider next the question of derandomizing black-box PIT for circuits over ${\mathbb{F}_{\bar{A},C}[X]}$ . Towards this, we provide a hitting set (consisting of elements of $(\mathbb{C}_{d})^{n}$ ) for such circuits. A hitting set $H$ for a class $\mathcal{C}$ of circuits is a set of points such that for any non-zero circuit $\Psi\in\mathcal{C}$ , there exists an $a\in H$ such that $\Psi$ evaluated at $a$ is not $0$ .

Theorem 4.

There exists a set $H_{n,s,d,\Delta}\subseteq(\mathbb{C}_{d})^{n}$ of size $(nsd)^{O(\Delta)}$ of points in $(\mathbb{C}_{d})^{n}$ such that for every nonassociative, commutative circuit $\Psi$ of size $\leqslant s$ and product depth $\leqslant\Delta$ computing a non-zero polynomial $f\in{\mathbb{F}_{\bar{A},C}[X]}$ of degree $\leqslant d$ , there is a point in $H_{n,s,d,\Delta}$ at which $f$ is non-zero. Furthermore, we can compute $H_{n,s,d,\Delta}$ deterministically in time $(nsd)^{O(\Delta)}$ .

Recall that the product depth of a circuit is the maximum number of product gates encountered on any leaf to root path in the circuit. Theorem 4 gives a non-trivial hitting set when the product depth $\Delta=o(d)$ . In particular, when $\Delta$ is polylogarithmic, we obtain a quasipolynomial size hitting set.

The result of Kabanets and Impagliazzo [14] shows that explicit lower bound results can give subexponential-time black-box PIT algorithms over the usual commutative polynomial ring $\mathbb{F}[X]$ . The main ingredients in their proof are the combinatorial design of Nisan and Wigderson [21] and the factorization algorithm of Kaltofen [15]. Although we have strong and explicit lower bounds over the algebra ${\mathbb{F}_{\bar{A},C}[X]}$ , it is unclear how to use them for PIT algorithms. Note that such a connection is not known even over $\mathbb{F}\langle{X}\rangle$ .

We prove Theorem 4 in two stages. In the first stage, we reduce PIT for circuits over ${\mathbb{F}_{\bar{A},C}[X]}$ to PIT for unambiguous circuits over $\mathbb{F}[Z]$ (where $Z$ is a fresh set of variables and $\mathbb{F}[Z]$ is the usual polynomial ring) via a set-multilinearization argument. We say that a circuit $\Psi$ over is $\mathbb{F}[Z]$ is unambiguous if for any monomial $m\in\mathbb{F}[Z]$ , there exists a reduced parse tree⁴⁴4See 5 for a definition.⁵⁵5The term unambiguous circuit has been used in different contexts in earlier works [3, 17]. $T_{m}$ such that any reduced parse tree computing $m$ at any gate of $\Psi$ is isomorphic to $T_{m}$ as a labeled, rooted binary tree. These are the natural associative analogues of nonassociative circuits. We also observe that a similar reduction works over ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ , which gives us an analogue of Theorem 4 over the algebra $\mathbb{A}_{d}$ .

In the second stage, we suitably adapt the machinery of basis isolating weight assignments developed by Agrawal et al. [1] to construct hitting sets for unambiguous circuits.

Theorem 5.

There exists a set $H_{s,n,d,\Delta}\subseteq\mathbb{F}^{n}$ such that for any unambiguous circuit $\Psi$ of size $s$ and product depth $\Delta$ computing a non-zero polynomial $f\in\mathbb{F}[z_{1},\ldots,z_{n}]$ of degree $\leqslant d$ , $f$ is non-zero on some point of $H_{s,n,d,\Delta}$ . Furthermore, $|H_{s,n,d,\Delta}|=(nds)^{O(\Delta)}$ and $H_{s,n,d,\Delta}$ can be constructed in time $(nds)^{O(\Delta)}$ .

Informally, given a polynomial $f$ with coefficients coming from a vector space, a basis isolating weight assignment for $f$ is a function from the underlying set of variables to $\mathbb{N}$ that isolates a minimum weight basis (among the coefficients) for the space spanned by the coefficients of $f$ . Basis isolating weight assignments were used in [1] to construct quasipolynomial size hitting-sets for ROABPs (these are commutative analogues of noncommutative ABPs). Subsequently, they were also used to construct hitting sets for set-multilinear Unique Parse Tree circuits (UPT circuits for short) [23]. UPT set-multilinear circuits generalize ROABPs. In a UPT set-multilinear circuit, every parse tree (see 4 for the definition) at the output has exactly the same shape as a rooted, ordered binary tree. In particular this implies that there is a universal parse tree shape at the root that induces a unique parse tree for each monomial. In unambiguous circuits, this is no longer true. In particular, there is a unique reduced parse tree for each monomial, but two different monomials could have different parse tree shapes. Also, note that unambiguous circuits need not be set-multilinear. On the other hand, we require that for any monomial $m$ , there is a unique parse tree computing it independent of the gate at which $m$ is being computed.

Suppose we have an unambiguous circuit of product depth $\Delta$ . We construct a basis isolating weight assignment $w$ for it in multiple stages (as in [1]). At each stage we handle monomials of increasing depths. The proof that $w$ is a basis isolating weight assignment involves isolation of a set $M_{i}$ of monomials for each depth $i\in[\Delta]$ such that the coefficient of every other monomial of depth $i$ is spanned by coefficients of $M_{i}$ . The construction of $M_{i}$ and the proof that its coefficients indeed span coefficients of other monomials is the main technical content of the proof and uses the fact that the circuit is unambiguous. Combining these $M_{i}$ ’s we get the isolated set $M$ of monomials. Identity testing follows from the construction of a basis isolating weight assignment.

The result of Valiant, Skyum, Berkowitz and Rackoff [27] shows that arithmetic circuits can be depth reduced to depth polylogarithmic in the size and degree of the original circuit while incurring only a polynomial blowup in size. Unfortunately, we do not know if such a depth reduction is possible while preserving unambiguousness.

Organization

The paper is organized as follows. In Section 2, we provide the necessary background. Section 3 contains the randomized polynomial-time PIT algorithms over nonassociative algebras. The deterministic PIT algorithms (white-box and black-box) are presented in Section 4. We state a few questions for further research in Section 5.

2 Preliminaries

Definition 1 (Algebra over a field).

Let $\mathbb{F}$ be a field. An algebra $\mathbb{A}$ over $\mathbb{F}$ is an $\mathbb{F}$ -vector space together with a product operation on the elements of the vector space that is bilinear. The dimension of $\mathbb{A}$ is defined to be the dimension of the underlying vector space. In particular, if the underlying vector space is finite (say $n$ ) dimensional and identified with $\mathbb{F}^{n}$ after choice of a basis, an algebra $\mathbb{A}$ is uniquely defined by $n$ matrices $L_{1},\ldots,L_{n}\in\mathbb{F}^{n\times n}$ as follows: for $\mathbf{x},\mathbf{y}\in\mathbb{F}^{n}$ , their $\mathbb{A}$ -product is precisely

\mathbf{x}\cdot\mathbf{y}=(x_{1},\ldots,x_{n})\cdot(y_{1},\ldots,y_{n})=\left(% \mathbf{x}^{T}L_{1}\mathbf{y},\ldots,\mathbf{x}^{T}L_{n}\mathbf{y}\right).

An algebra $\mathbb{A}$ is called unital if it contains a multiplicative identity $i$ such that $\forall x\in\mathbb{A},x\cdot i=i\cdot x=x$ . We define the following four different polynomial algebras, depending on the relations the variables satisfy:

(1)

$\mathbb{F}_{A,C}[X]$ : This is the polynomial ring $\mathbb{F}[X]$ . The product operation is both commutative and associative.
(2)

$\mathbb{F}_{A,\widebar{C}}[X]$ is the noncommutative polynomial ring $\mathbb{F}\langle X\rangle$ . The product operation is noncommutative but associative.
(3)

$\mathbb{F}_{\bar{A},C}[X]$ is the $\mathbb{F}$ -vector space generated by commutative, nonassociative monomials in the variables $X$ . This vector space becomes an $\mathbb{F}$ -algebra with the commutative, nonassociative product of monomials extended to all of ${\mathbb{F}_{\bar{A},C}[X]}$ by bilinearity.
(4)

$\mathbb{F}_{\bar{A},\bar{C}}[X]$ is the $\mathbb{F}$ -vector space generated by noncommutative, nonassociative monomials in the variables $X$ . This vector space becomes an $\mathbb{F}$ -algebra with the noncommutative, nonassociative product of monomials extended to all elements of $\mathbb{F}_{\bar{A},\bar{C}}[X]$ by bilinearity.

Definition 2 (Polynomial Identities).

A Polynomial Identity (PI for short) for an algebra $\mathbb{A}$ is a polynomial $f(x_{1},\ldots,x_{n})$ in a set of variables $\{x_{1},\ldots,x_{n}\}$ such that for all $A_{1},\ldots,A_{n}\in\mathbb{A}$ , $f(A_{1},\ldots,A_{n})=0$ where the multiplication is according to the product operation in $\mathbb{A}$ . An algebra that satisfies nontrivial identities is called a PI-algebra.

The study of polynomial identities is a classical and very rich subject in mathematics. For a comprehensive details, see [11].

Definition 3 (Arithmetic Circuit).

An Arithmetic Circuit $\Psi$ over a field $\mathbb{F}$ is a directed acyclic graph whose leaves (called input gates) are labeled by either variables (say $X=\{x_{1},\ldots,x_{n}\}$ ) or field elements and whose internal vertices (called gates) are labeled by either a sum ( $+$ ) or a product $(\times)$ . In our case the product operation will often be nonassociative, and we will assume that the fan-in of each product gate is $2$ . If in addition we are working in $\mathbb{F}_{\bar{A},\bar{C}}[X]$ , the product will also be noncommutative: each product gate will have designated left and and right child. Each gate in a circuit naturally computes a polynomial. The circuit $\Psi$ has a designated output gate and $\Psi$ is said to compute the polynomial computed at the output gate. The size of a circuit is the number of gates in it and the depth of a circuit is the length of the longest leaf-to-root path.

Next we define the concept of a parse tree, that depicts the generation of a particular monomial in the circuit.

Definition 4 (Parse trees).

Let $X=\{x_{1},\ldots,x_{n}\}$ be a set of variables, $\mathbb{F}$ be a field and $\Psi$ be an arithmetic circuit computing a polynomial $f\in\mathbb{F}[X]$ . The set of parse trees for $\Psi$ will be defined by induction on the size of $\Psi$ as follows:

$\blacksquare$

If $\Psi$ is just a leaf labeled by either a variable or a constant, then it has only one parse tree, itself.
$\blacksquare$

If the root $g$ of $\Psi$ is a sum gate with subcircuits $\Psi_{1}$ and $\Psi_{2}$ as children, the set of parse trees for $\Psi$ is the set of all trees obtained by taking the root $g$ , and attaching to it a parse tree of either $\Psi_{1}$ or $\Psi_{2}$ .
$\blacksquare$

If the root $g$ of $\Psi$ is a product gate with subcircuits $\Psi_{1}$ and $\Psi_{2}$ , we define the set of parse trees for $\Psi$ to be the set of all trees $T$ obtained by taking a parse tree $T_{1}$ for $\Psi_{1}$ , a parse tree $T_{2}$ for a disjoint copy of $\Psi_{2}$ and making $T_{1},T_{2}$ the children of $g$ .

Note that each parse tree $T$ for $\Psi$ computes a monomial (with coefficient).

Definition 5 (Reduced Parse Trees).

From each parse tree $T$ of a circuit $\Psi$ , we may obtain a reduced parse tree $T^{\prime}$ by short-circuiting the sum gates, removing leaves labeled by constants and restructuring the tree in the natural way. $T^{\prime}$ is a full binary tree all of whose leaves are labeled by a variable and all of whose gates are product gates. $T^{\prime}$ captures the multiplicative structure of $T$ . The set of reduced parse trees for $\Psi$ is defined as $\{T^{\prime}\mid T\text{ is a parse tree for }\Psi\}$ . See Figure 1(c) for an illustrative example.

(a) A circuit

\Psi

.

(b) A parse tree

T

for

\Psi

.

(c) Reduced parse tree

T^{\prime}

.

We also recall the following standard result over $\mathbb{F}_{A,C}[X]$ :

Lemma 6 (Polynomial Identity Lemma [30, 25, 8]).

Suppose $f(x)\in\mathbb{F}[X]$ is an $n$ -variate polynomial of degree $d$ , and let $S\subseteq F$ be a finite set of size strictly larger than $d$ . Then $f(\bar{a})\neq 0$ for at least $\left(1-\frac{d}{|S|}\right)$ fraction of $\bar{a}$ ’s in $S^{n}$ .

Over the algebra $\mathbb{F}_{A,\bar{C}}[X]$ , the following is a well-known result of Amitsur and Levitzki [2].

Theorem 7 (Amitsur-Levitzki Theorem [2]).

Over any field $\mathbb{F}$ , the matrix algebra $\mathbb{F}^{k\times k}$ satisfies no PI of (total) degree less than $2k$ , and satisfies exactly one (up to constant factor) PI of degree $2k$ .

2.1 A structural lemma about nonassociative monomials

2.1.1 Over the algebra $\mathbb{F}_{\bar{A},\bar{C}}[X]$

Let $\mathbb{F}$ be a field and $X=\{x_{1},\ldots,x_{n}\}$ be a set of variables. There is a natural correspondence between rooted binary trees with leaves labeled by elements of $X$ and monomials in ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ . The nonassociativity introduces a unique product structure which may be interpreted as a binary tree: Let $m\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ be a monomial. Then there is a unique rooted binary tree $T_{m}$ whose the leaves (labeled by elements of $X$ ) represent the variables, and whose internal nodes compute the product their two children. The root computes the monomial $m$ . For instance, the binary trees in Figure 2(a) and 2(b) compute monomials $m=((x_{i_{1}}x_{i_{2}})x_{i_{3}})$ and $m^{\prime}=(x_{i_{1}}(x_{i_{2}}x_{i_{3}}))$ respectively. Noncommutativity implies that each internal node has designated left and right children, and swapping this order changes the monomial.

Suppose $m$ has degree $d$ . Noncommutativity gives us a unique string $\sigma_{m}=(i_{1},\ldots,i_{d})\in[n]^{d}$ which is the unique left to right order $x_{i_{1}},x_{i_{2}}\ldots x_{i_{d}}$ in which the variables appear in $m$ . We will think of $\sigma_{m}:[d]\rightarrow[n]$ as a function defined as $\sigma_{m}(j)=i_{j}$ for all $j\in[d]$ . Note that $\sigma_{m}$ does not uniquely define a monomial. For instance, for the monomials $m,m^{\prime}\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ shown in Figure 2, $\sigma_{m}=\sigma_{m^{\prime}}$ but $m\neq m^{\prime}$ . Given a monomial $m\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ as a binary tree $T_{m}$ , we assign level numbers to the nodes of $T_{m}$ . Define the level of a node $v$ in $T_{m}$ to be $1+d(\text{root},v)$ , where $d(\cdot,\cdot)$ is the distance function. That is, the root is at level $1$ , the children of the root are at level $2$ and so on. For each $j\in[d]$ , let $l^{m}_{j}$ denote the level at which the $j^{th}$ variable (in the left to right order) appears in $m$ .

For monomials $m=((x_{i_{1}}x_{i_{2}})x_{i_{3}})$ and $m^{\prime}=(x_{i_{1}}(x_{i_{2}}x_{i_{3}}))$ shown in Figure 2, $l_{1}^{m}=3,l_{2}^{m}=3,l_{3}^{m}=2$ and $l_{1}^{m^{\prime}}=2,l_{2}^{m^{\prime}}=3,l_{3}^{m^{\prime}}=3$ . In general, the variable order $\sigma_{m}$ and the level numbers $(l_{1}^{m},\ldots,l_{d}^{m})$ together uniquely determine the monomial $m$ .

(a)

m=((x_{i_{1}}x_{i_{2}})x_{i_{3}})

.

(b)

m^{\prime}=(x_{i_{1}}(x_{i_{2}}x_{i_{3}}))

.

(c)

m^{\prime\prime}=((x_{i_{2}}x_{i_{1}})x_{i_{3}})

.

Figure 2: Examples of nonassociative, noncommutative monomials.

We state this formally in the following lemma:

Lemma 8.

Let $m,m^{\prime}$ be distinct monomials in ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ . Let ${\sf deg}(m)=d$ and ${\sf deg}(m^{\prime})=d^{\prime}$ . Then the tuples $(\sigma_{m},l^{m}_{1},\ldots,l^{m}_{d})$ and $(\sigma_{m^{\prime}},l^{m^{\prime}}_{1},\ldots,l^{m^{\prime}}_{d^{\prime}})$ are distinct.

Proof.

We assume that $\sigma_{m}=\sigma_{m^{\prime}}$ , for otherwise the statement is evidently true. In particular, assume that the degrees of $m$ and $m^{\prime}$ are both equal to $d$ . Next, we simply observe that it is possible to iteratively reconstruct $m$ uniquely, given the sequence $l^{m}_{1},\ldots,l^{m}_{d}$ of levels. Start with just the root. To it, add a path of length $l_{1}^{m}-1$ consisting entirely of left edges (every node is a left child of it’s parent). Label the ultimate node (leaf) on the path by $x_{\sigma_{m}(1)}$ . Now suppose we already have a leaf for the $i$ -th variable, $x_{\sigma_{m}(i)}$ . To generate the leaf labeled by $x_{\sigma_{m}(i+1)}$ , find the ancestor $v$ of $x_{\sigma_{m}(i)}$ closest to $x_{\sigma_{m}(i)}$ that only has a left child. Let the level of $v$ be $l$ . Add a right $v^{\prime}$ to child to $v$ . If $v^{\prime}$ is at level $l_{\sigma_{m}(i+1)}$ , label it by $x_{\sigma_{m}(i+1)}$ . Otherwise, add to it a path of length $l_{\sigma_{m}(i+1)}-l-1$ consisting only of left edges and label the ultimate node on this path by $x_{\sigma_{m}(i)}$ . This process recovers $m$ . The key property of trees representing nonassociative monomials that is used in the procedure above is that they are full binary trees, that is, each node either has exactly two children or none at all. This justifies our choice of going back to the the closest ancestor $v$ of $x_{\sigma_{m}(i)}$ that only has a left child and no right child. $\hfill\blacktriangleleft$

2.1.2 Over the algebra $\mathbb{F}_{\bar{A},{C}}[X]$

Next, we consider the case of monomials in ${\mathbb{F}_{\bar{A},C}[X]}$ . One may partition the set of all monomials in ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ into equivalence classes under commutativity: For all monomials $m,m^{\prime}\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ , $m\sim m^{\prime}$ if and only if $m$ and $m^{\prime}$ are equal up commutativity. For example the monomials shown in Figure 2(a) and Figure 2(b) belong to different equivalence classes. On the other hand, monomials in Figure 2(a) and Figure 2(c) belong to the same equivalence class.

Each equivalence class may be identified with a monomial in ${\mathbb{F}_{\bar{A},C}[X]}$ . Looking at it from the other direction, suppose $m,m^{\prime}$ are monomials in ${\mathbb{F}_{\bar{A},C}[X]}$ and suppose $M_{m}$ , $M_{m^{\prime}}$ are the equivalence classes of monomials in ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ they represent. Since $\sim$ as defined above is an equivalence relation, we have the following simple observation:

Observation 9.

For any two distinct monomials $m,m^{\prime}\in{\mathbb{F}_{\bar{A},C}[X]}$ we have $M_{m}\cap M_{m^{\prime}}=\emptyset$ .

3 Randomized Black-box PIT for Nonassociative circuits

Let $\mathbb{F}$ be a field and let $X=\{x_{1},\ldots,x_{n}\}$ . In this section, we work with both the nonassociative, noncommutative polynomial algebra ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ as well as the commutative ${\mathbb{F}_{\bar{A},C}[X]}$ . In subsection 3.1, we give a randomized, polynomial time black-box algorithms to test whether a nonassociative, noncommutative circuit $\Phi$ over $\mathbb{F}$ computes the identically zero polynomial. The algorithm assumes that we have access to evaluations of $\Phi$ on a suitable $k$ dimensional $\mathbb{F}$ -algebra $A$ , and that the cost of one $A$ -query is ${\mathsf{poly}}({\sf size}(\Phi),k)$ . That is, the cost is polynomial in the size of the circuit and the dimension of the algebra. To the best of our knowledge, this gives the first Amitsur-Levitzki type theorem [2] over nonassociative polynomial algebras.

3.1 Nonassociative, Noncommutative Randomized Black-box PIT

The key idea is to construct a noncommutative, nonassociative $\mathbb{F}$ -algebra and show that it does not satisfy low degree polynomial identities. This will imply that a random non-zero substitution from this algebra will make a non-zero circuit $\Phi$ evaluate to something non-zero, with high probability.

We will query noncommutative, nonassociative circuits computing a polynomial $f\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ of degree $\leqslant d$ on a particular $d(d+1)^{2}+1$ dimensional algebra $\mathbb{A}_{d}$ that we now describe. First, we construct an algebra $\mathbb{A^{\prime}}_{d}$ of dimension $d(d+1)^{2}$ and then construct the desired algebra $\mathbb{A}_{d}$ by adjoining an identity element to $\mathbb{A^{\prime}}_{d}$ . Additively, $\mathbb{A^{\prime}}_{d}$ is an $\mathbb{F}$ -vector space of dimension $d(d+1)^{2}$ . We will think of an element of $\mathbb{A^{\prime}}_{d}$ as a set of $d$ matrices each of dimension $(d+1)\times(d+1)$ :

Figure 3:

3

-dimensional view of an element of

\mathbb{A}^{\prime}_{d}

.

Let $x,y\in\mathbb{F}^{d(d+1)^{2}}$ . We index $x, y$ as $x[i,j,k]$ and $y[i,j,k]$ for $1\leqslant i,j\leqslant d+1$ and $1\leqslant k\leqslant d$ . Here, $k$ can be thought of as indexing the set of $d$ matrices and for a fixed $k$ , $i$ and $j$ index respectively the rows and columns of the $k$ -th matrix. Next, we define the bilinear $\mathbb{A}_{d}^{\prime}$ -product of $x, y$ as follows: $z\triangleq x\circ y$ such that

z[i,j,k]=\begin{cases}0&k=d\\ \displaystyle\sum_{l=1}^{d+1}x[i,l,k+1]y[l,j,k+1]&1\leqslant k\leqslant d-1\\ \end{cases}

Clearly, $\mathbb{A^{\prime}}_{d}$ is an $\mathbb{F}$ -algebra. From the proof of Lemma 10, it will be evident that $\mathbb{A^{\prime}}_{d}$ is a nonassociative algebra.

We require the algebra $\mathbb{A^{\prime}}_{d}$ to be unital to make sense of $\mathbb{A^{\prime}}_{d}$ -evaluations of polynomials with a non-zero constant term: For any $f\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ , $f(0,\ldots,0)=c\cdot\mathbf{1}$ where $f$ has constant term $c\in\mathbb{F}$ and $\mathbf{1}$ is the identity element of $\mathbb{A^{\prime}}_{d}$ . However, $\mathbb{A^{\prime}}_{d}$ is non-unital. To construct the unital algebra $\mathbb{A}_{d}$ (from $\mathbb{A^{\prime}}_{d}$ ), we use a standard procedure of adjoining an identity to an algebra:

The Algebra $\mathbf{\mathbb{A}_{d}}$

Define the algebra $\mathbb{A}_{d}$ to be the vector space $\mathbb{F}^{d(d+1)^{2}+1}=\{(a,\alpha)\mid a\in\mathbb{A^{\prime}}_{d},\alpha% \in\mathbb{F}\}$ together with the bilinear product $\cdot$ defined as follows:

(a_{1},\alpha_{1})\cdot(a_{2},\alpha_{2})=(a_{1}\circ a_{2}+\alpha_{1}a_{2}+% \alpha_{2}a_{1},\alpha_{1}\alpha_{2})

We will refer to this newly added index as the last index. It is easy to verify that $\mathbb{A}_{d}$ is indeed a nonassociative algebra with $(\mathbf{0},1)$ being the multiplicative identity, and that $\mathbb{A^{\prime}}_{d}$ is isomorphic to the sub-algebra $\{(a,0)\mid a\in\mathbb{A^{\prime}}_{d}\}$ of $\mathbb{A}_{d}$ .

Now, we show that $\mathbb{A}_{d}$ cannot have polynomial identities of degree $\leqslant d$ .

Lemma 10.

Let $f\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ be a non-zero polynomial of total degree $\leqslant d$ . Then $f$ is not a PI for $\mathbb{A}_{d}$ .

Proof.

It suffices to consider polynomials that do not have a constant term, since a polynomial with a non zero constant term evaluates to a non-zero value at the all zeroes input. Also, it suffices to prove Lemma 10 for the algebra $\mathbb{A^{\prime}}_{d}$ instead of $\mathbb{A}_{d}$ , since $\mathbb{A^{\prime}}_{d}$ is a subalgebra of $A_{d}$ . In order to prove the lemma, we reduce the problem to the associative, commutative setting.

For each $x_{i}$ , we introduce an associative, commutative set of variables $\{z_{i,j,k}\mid 1\leqslant j,k\leqslant d\}$ . For convenience, denote the vector $(z_{i,j,k})_{j,k\in[d]}$ by $\mathbf{z_{i}}$ . Extend the ground field $\mathbb{F}$ to the function field $\mathbb{F}^{\prime}=\mathbb{F}(\mathbf{z}_{1},\ldots,\mathbf{z}_{n})$ . We define the algebra $\mathbb{A^{\prime}}_{d}$ over the field $\mathbb{F}^{\prime}$ as described earlier. Eventually, the $\mathbf{z}$ variables will be fixed suitably from the base field $\mathbb{F}$ .

Next, consider the evaluation map $\Phi:{\mathbb{F}_{\bar{A},\bar{C}}[X]}\rightarrow\mathbb{A^{\prime}}_{d}$ that sends $x_{i}$ to $Z_{i}$ where for each $1\leqslant j,k\leqslant d$ , the $(j,j+1,k)$ -th entry of $Z_{i}$ is $z_{i,j,k}$ and the rest of the entries are zero. For an illustration, we describe $Z_{1}$ explicitly in Figure 4.

Figure 4:

Z_{1}=\Phi(x_{1})

visualized as an element of

\mathbb{A}^{\prime}_{d}

.

Let us look at the image of a monomial $m\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ (of degree at most $d$ ) under $\Phi$ . Let $d^{\prime}\leqslant d$ be the degree of $m$ . We interpret $m$ as a binary tree with leaves labeled by variables. Since we are in the noncommutative setting, there is a unique function $\sigma_{m}:[d^{\prime}]\rightarrow[n]$ that describes the left-to-right order in which the variables appear in $m$ . We will level the nodes (including leaves) of $m$ as described in Section 2.1. Let $l^{m}_{t}$ denote the level at which the $t$ -th variable in $\sigma_{m}$ (i.e., variable $x_{\sigma_{m}(t)}$ ) appears in $m$ . Let the depth of $m$ (i.e., ${\sf max}_{i}\{l_{i}\}$ ) be $l$ .

Claim 11.

Let $m$ be as above. For each $k_{1}\in[d-d^{\prime}+1]$ and each $k_{2}\in[d-l+1]$ , the $(k_{1},k_{1}+d^{\prime},k_{2})$ -th entry of $\Phi(m)$ is the monomial $\prod_{t=1}^{d^{\prime}}z_{\sigma_{m}(t),t+k_{1}-1,l^{m}_{t}+k_{2}-1}$ , and every other entry is zero.

Proof.

We prove this by induction on the degree $d^{\prime}$ of $m$ . For ${\sf deg}(m)=1$ , the claim follows from the definition of $Z_{i}$ ’s. Now suppose $d^{\prime}>1$ and $m$ is uniquely written as $m_{1}m_{2}$ such that ${\sf deg}(m_{1})=d_{1}$ , ${\sf deg}(m_{2})=d_{2}$ and $d_{1}+d_{2}=d^{\prime}$ . Then,

\displaystyle\Phi(m)[k_{1},k_{1}+d^{\prime},k_{2}]=\sum_{i=1}^{d+1}\Phi(m_{1})% [k_{1},i,k_{2}+1]\Phi(m_{2})[i,k_{1}+d^{\prime},k_{2}+1]

By induction, we see that exactly one term in this sum is non zero, the one corresponding to $i=k_{1}+d_{1}$ and the sum is therefore equal to

\left(\prod_{t=1}^{d_{1}}z_{\sigma_{m_{1}}(t),t+k_{1}-1,l^{m_{1}}_{t}+k_{2}}% \right)\left(\prod_{t=1}^{d_{2}}z_{\sigma_{m_{2}}(t),t+d_{1}+k_{1}-1,l^{m_{2}}% _{t}+k_{2}}\right)

(1)

Notice that

\sigma_{m}(t)=\begin{cases}\sigma_{m_{1}}(t)\quad 1\leqslant t\leqslant d_{1}% \\ \sigma_{m_{2}}(t-d_{1})\quad d_{1}+1\leqslant t\leqslant d^{\prime}\end{cases}

and that

l^{m}_{t}=\begin{cases}l^{m_{1}}_{t}+1\quad 1\leqslant t\leqslant d_{1}\\ l^{m_{2}}_{t-d_{1}}+1\quad d_{1}+1\leqslant t\leqslant d^{\prime}\end{cases}

Using these observations, we find that (1) is exactly equal to $\prod_{t=1}^{d^{\prime}}z_{\sigma_{m}(t),t+k_{1}-1,l^{m}_{\sigma_{m}(t)}+k_{2}% -1}$ .

Now let us look at $\Phi(m)[i_{1},i_{2},i_{3}]$ such that $i_{2}\neq i_{1}+d^{\prime}$ and $i_{3}\in[d-1]$ (if $i_{3}=d$ , $\Phi(m)[i_{1},i_{2},i_{3}]=0$ by definition of the $\mathbb{A}_{d}$ product).

\Phi(m)[i_{1},i_{2},i_{3}]=\sum_{i=1}^{d+1}\Phi(m_{1})[i_{1},i,i_{3}+1]\Phi(m_% {2})[i,i_{2},i_{3}+1]

Using the induction hypothesis, we see that each summand in the sum above is actually zero, and therefore so is $\Phi(m)[i_{1},i_{2},i_{3}]$ .

Let us also look at $\Phi(m)[i_{1},i_{2},i_{3}]$ with $i_{3}>d-l+1$ . If $d^{\prime}=2$ then all such entries of $\Phi(m)$ are easily seen to be zero. Now suppose $d^{\prime}>2$ and assume, without loss of generality, that the depth of $m_{1}$ is $l-1$ . Then by induction, all entries $\Phi(m_{1})[i_{1},i_{2},i_{3}]$ of $\Phi(m_{1})$ with $i_{3}>d-l$ are zero and therefore so are all the entries $\Phi(m)[i_{1},i_{2},i_{3}]$ of $\Phi(m)$ with $i_{3}>d-l+1$ .

This concludes the proof of Claim 11. $\hfill\vartriangleleft$ Now, by setting $k_{1},k_{2}=1$ in the statement of Claim 11 we see that for a monomial $m$ of degree $d^{\prime}$ , the $(1,d^{\prime}+1,1)$ -th entry of $\Phi(m)$ is $\prod_{t=1}^{d^{\prime}}z_{\sigma_{m}(t),t,l_{t}}$ . For any monomial of degree $\neq d^{\prime}$ , this entry is zero. This observation combined with Lemma 8 gives us Lemma 10. $\hfill\blacktriangleleft$

Using Lemma 10, we exhibit a randomized black-box identity testing algorithm for nonassociative, noncommutative circuits.

Theorem 12.

Let $\mathbb{F}$ be a field with $|\mathbb{F}|>d$ , and $S\subset\mathbb{F}$ . Let $f\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ be a non-zero polynomial of degree $\leqslant d$ given as a black-box with query access to evaluations of $f$ on elements of $\mathbb{A}_{d}$ . Let $S\subseteq\mathbb{F}$ with $|S|>d$ . Sample $b_{1},\ldots,b_{n}\in\mathbb{A}_{d}$ as follows: Pick each of the $d(d+1)^{2}+1$ entries of each of the $b_{i}$ ’s uniformly and independently from $S$ . Then

\Pr_{b_{1},\ldots,b_{n}\in\mathbb{A}_{d}}[f(b_{1},\ldots,b_{n})=0]\leqslant d/% |S|.

Proof.

From Lemma 10, it follows that $f$ is not a PI for $\mathbb{A}_{d}$ . By slight abuse of notation, define $\mathbb{A}_{d}$ over the field $\mathbb{F}(Y)$ where $Y$ is a commutative, associative set of variables and $|Y|=nd(d+1)^{2}+1$ . Replace each $x_{i}$ by $Y_{i}\in\mathbb{A}_{d}$ defined as follows: $Y_{i}$ has dimension $d(d+1)^{2}+1$ and each entry of each $Y_{i}$ is a fresh variable from $Y$ . Since $f$ is not a PI for $\mathbb{A}_{d}$ , $f(Y_{1},\ldots,Y_{n})\nequiv 0$ and so at least one entry of $f(Y_{1},\ldots,Y_{n})$ is a non-zero polynomial in $\mathbb{F}[Y]$ . By the Polynomial Identity Lemma (Lemma 6), under a random $S$ -substitution, the probability that that entry of $f(Y_{1},\ldots,Y_{n})$ evaluates to zero is $\leqslant d/|S|$ . $\hfill\blacktriangleleft$

Theorem 12 can be thought of as a version of Theorem 7 over $\mathbb{F}_{\bar{A},\bar{C}}$ . It immediately gives us the desired black-box PIT algorithm.

3.2 Nonassociative, Commutative Randomized Black-box PIT

Next, we construct a nonassociative, commutative algebra $\mathbb{C}_{d}$ that does not satisfy low degree identities in ${\mathbb{F}_{\bar{A},C}[X]}$ . $\mathbb{C}_{d}$ is constructed using the algebra $\mathbb{A}_{d}$ from the previous section (Section 3.1). Recall that $\cdot$ denotes the $\mathbb{A}_{d}$ -product.

The Algebra $\mathbb{C}_{d}$

$\mathbb{C}_{d}$ is isomorphic to $\mathbb{A}_{d}$ as a vector space, and the $\mathbb{C}_{d}$ product of $a, b$ (denoted by $\odot$ ) is simply the anticommutator of $a, b$ with respect to the $\mathbb{A}_{d}$ product “ $\cdot$ ”. That is, $a\odot b=a\cdot b+b\cdot a$ . Let $\mathbb{C^{\prime}}_{d}$ denote the sub-algebra of $\mathbb{C}_{d}$ obtained by setting the last index to $0$ . It is easily verified that $\mathbb{C}^{\prime}_{d}$ is isomorphic to the algebra whose product is the anticommutator with respect to the $\mathbb{A}^{\prime}_{d}$ product $\circ$ . For convenience, in the sequel, we will drop the last index of elements of $\mathbb{C}^{\prime}_{d}$ .

Lemma 1. [Restated, see original statement.]

Let $f\in{\mathbb{F}_{\bar{A},C}[X]}$ be a non-zero polynomial of total degree $\leqslant d$ . Then $f$ is not a polynomial identity (PI) for $\mathbb{C}_{d}$ .

Proof.

The proof of Lemma 1 is similar to the proof of Lemma 10. As before, we note that it suffices to prove the lemma for constant free polynomials and that it suffices to prove the claim for $\mathbb{C^{\prime}}_{d}$ instead of $\mathbb{C}_{d}$ , because any identity of $\mathbb{C}_{d}$ is also an identity of $\mathbb{C^{\prime}}_{d}$ .

For each $x_{i}$ , we introduce the same associative, commutative set of variables $\{z_{i,j,k}\mid 1\leqslant j,k\leqslant d\}$ as before. Denote the vector $(z_{i,j,k})_{j,k\in[d]}$ by $\mathbf{z_{i}}$ . As in the proof of Lemma 10, we consider the extended field $\mathbb{F}^{\prime}=\mathbb{F}(\mathbf{z}_{1},\ldots,\mathbf{z}_{n})$ and define $\mathbb{C^{\prime}}_{d}$ over $\mathbb{F}^{\prime}$ . We consider the evaluation map $\Phi:{\mathbb{F}_{\bar{A},C}[X]}\rightarrow\mathbb{C^{\prime}}_{d}$ that sends $x_{i}$ to $Z_{i}$ where for each $1\leqslant j,k\leqslant d$ , the $(j,j+1,k)$ -th entry of $Z_{i}$ is $z_{i,j,k}$ and the rest of the entries are zero. Again, we would like to inspect the image of a monomial $m\in{\mathbb{F}_{\bar{A},C}[X]}$ of degree $d^{\prime}\leqslant d$ under $\Phi$ . As before, we interpret $m$ as a binary tree. Without loss of generality, let the variables appearing in $m$ be $x_{1},\ldots,x_{d^{\prime}}$ . Unlike in the noncommutative case, there is no unique left to right order of variables that one can associate with the monomial $m$ .

There is, however, a set of orders that one can associate with $m$ : For each internal node in the tree representing $m$ , arbitrarily designate one of the children to be the left child and the other to be the right child. This procedure induces an order $\sigma$ on the variables of $m$ . Furthermore, every distinct way of designating left and right children at the internal nodes of $m$ induces a unique order. Consider the union of all these orders and denote this set by $\Sigma_{m}$ . Each $\sigma\in\Sigma_{m}$ corresponds to a unique monomial from ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ in the equivalence class $M_{m}$ corresponding to the monomial $m$ (see Section 2.1, the commutative case). Also, for a fixed $\sigma\in\Sigma_{m}$ , let $l^{m,\sigma}_{t}$ denote the level at which the $t$ -th variable in the order $\sigma$ (i.e., variable $x_{\sigma(t)}$ ) appears in $m$ . Let the depth of $m$ (i.e., ${\sf max}_{i}\{l_{i}\}$ ) be $l$ .

Claim 13.

Let $m$ be as above. For each $k_{1}\in[d-d^{\prime}+1]$ and each $k_{2}\in[d-l+1]$ , the $(k_{1},k_{1}+d^{\prime},k_{2})$ -th entry of $\Phi(m)$ is the polynomial $\displaystyle\sum_{\sigma\in\Sigma_{m}}\prod_{t=1}^{d^{\prime}}z_{\sigma(t),t+% k_{1}-1,l^{m,\sigma}_{t}+k_{2}-1}$ , and every other entry is zero.

Proof.

We prove this by induction on the degree $d^{\prime}$ of $m$ . For ${\sf deg}(m)=1$ , $|\Sigma_{m}|=1$ and the claim follows from the definition of $Z_{i}$ ’s. Now suppose $d^{\prime}>1$ and $m$ is uniquely written as $m_{1}m_{2}$ such that ${\sf deg}(m_{1})=d_{1}$ , ${\sf deg}(m_{2})=d_{2}$ and $d_{1}+d_{2}=d^{\prime}$ . Then,

	$\displaystyle\Phi(m)[k_{1},k_{1}+d^{\prime},k_{2}]=$	$\displaystyle\sum_{i=1}^{d+1}\Phi(m_{1})[k_{1},i,k_{2}+1]\Phi(m_{2})[i,k_{1}+d% ^{\prime},k_{2}+1]$
	$\displaystyle+$	$\displaystyle\sum_{i=1}^{d+1}\Phi(m_{2})[k_{1},i,k_{2}+1]\Phi(m_{1})[i,k_{1}+d% ^{\prime},k_{2}+1]$

By induction, we see that the first sum $\displaystyle\sum_{i=1}^{d+1}\Phi(m_{1})[k_{1},i,k_{2}+1]\Phi(m_{2})[i,k_{1}+d% ^{\prime},k_{2}+1]$ is equal to

\left(\sum_{\pi\in\Sigma_{m_{1}}}\prod_{t=1}^{d_{1}}z_{\pi(t),t+k_{1}-1,l^{m_{% 1},\pi}_{t}+k_{2}}\right)\left(\sum_{\tau\in\Sigma_{m_{2}}}\prod_{t=1}^{d_{2}}% z_{\tau(t),t+d_{1}+k_{1}-1,l^{m_{2},\tau}_{t}+k_{2}}\right)

while the second sum $\sum_{i=1}^{d+1}\Phi(m_{2})[k_{1},i,k_{2}+1]\Phi(m_{1})[i,k_{1}+d^{\prime},k_{% 2}+1]$ is equal to

\left(\sum_{\tau\in\Sigma_{m_{2}}}\prod_{t=1}^{d_{2}}z_{\tau(t),t+k_{1}-1,l^{m% _{2},\tau}_{t}+k_{2}}\right)\left(\sum_{\pi\in\Sigma_{m_{1}}}\prod_{t=1}^{d_{1% }}z_{\pi(t),t+d_{2}+k_{1}-1,l_{t}^{m_{1},\pi}+k_{2}}\right)

Expanding the products, we see that the first sum generates the monomials in the polynomial $\displaystyle\sum_{\sigma\in\Sigma_{m}}\prod_{t=1}^{d^{\prime}}z_{\sigma(t),t+% k_{1}-1,l^{m,\sigma}_{t}+k_{2}-1}$ corresponding to the $\sigma\in\Sigma_{m}$ that make $m_{1}$ the left child of the root of $m$ and $m_{2}$ the right, and the second term generates the rest of the monomials.

Also, note that the same argument as in the proof of Lemma 10 tells us that if we have $i_{1},i_{2},i_{3}$ such that $i_{2}\neq i_{1}+d^{\prime}$ and $i_{3}\in[d]$ then $\Phi(m)[i_{1},i_{2},i_{3}]=0$ and that if $i_{3}>d-l+1$ then again $\Phi(m)[i_{1},i_{2},i_{3}]=0$ . $\hfill\vartriangleleft$

In particular, by setting $k_{1},k_{2}=1$ in the statement of Claim 13 we see that for a monomial $m$ of degree $d^{\prime}$ , the $(1,d^{\prime}+1,1)$ -th entry of $\Phi(m)$ is $\displaystyle\sum_{\sigma\in\Sigma_{m}}\prod_{t=1}^{d^{\prime}}z_{\sigma(t),t,% l^{m,\sigma}_{t}}$ . For a monomial of degree $\neq d^{\prime}$ , this entry is zero.

Therefore, Combining Claim 13, Lemma 8 and Observation 9, we see that $f$ cannot be an a PI for $\mathbb{C^{\prime}}_{d}$ (and therefore for $\mathbb{C}_{d}$ ). $\hfill\blacktriangleleft$

The proof of Theorem 2 follows from Lemma 1, in a way similar to the proof of Theorem 12. We record the statement here for completeness

Theorem 2. [Restated, see original statement.]

Let $\mathbb{F}$ be a field with $|\mathbb{F}|>d$ , and $S\subset\mathbb{F}$ . Let $f\in{\mathbb{F}_{\bar{A},C}[X]}$ be a non-zero polynomial of degree $\leqslant d$ given as a black-box with query access to evaluations of $f$ on elements of $\mathbb{C}_{d}$ . Let $S\subseteq\mathbb{F}$ with $|S|>d$ . Sample $b_{1},\ldots,b_{n}\in\mathbb{C}_{d}$ as follows: Pick each of the $d(d+1)^{2}+1$ entries of each of the $b_{i}$ ’s uniformly and independently from $S$ . Then

\Pr_{b_{1},\ldots,b_{n}\in\mathbb{C}_{d}}[f(b_{1},\ldots,b_{n})=0]\leqslant d/% |S|.

4 Deterministic PIT Algorithms Over ${\mathbb{F}_{\bar{A},C}[X]}$

In this section, we develop efficient deterministic PIT algorithms over the algebra ${\mathbb{F}_{\bar{A},C}[X]}$ . First, we present the white-box algorithm and then the black-box algorithm.

4.1 White-box Deterministic PIT over ${\mathbb{F}_{\bar{A},C}[X]}$

We give a polynomial time white-box PIT algorithm for commutative, nonassociative circuits. We use linear algebraic ideas from the PIT algorithm by Raz and Shpilka [22] for noncommutative algebraic branching programs. These ideas have later been used to give polynomial time white-box PIT algorithms for various models, such as nonassociative, noncommutative circuits [4] and noncommutative unique parse tree circuits [16].

Theorem 3. [Restated, see original statement.]

Let $\Psi$ be a nonassociative arithmetic circuit of size $s$ computing an $n$ variate, degree $\leqslant d$ polynomial $f\in{\mathbb{F}_{\bar{A},C}[X]}$ . Given $\Psi$ as input, we can check whether $f\equiv 0$ deterministically in time ${\mathsf{poly}}(s,n,d)$ .

Proof.

For each monomial $m$ of degree $\leqslant d$ , we may associate a vector $v_{m}\in\mathbb{F}^{s}$ where $s$ is the number of gates in $\Psi$ . The vector $v_{m}$ is indexed by the gates of $\Psi$ such that $v_{m}(g)={\sf coeff}_{m}(g)$ . For each $i\in\{0\}\cup[d]$ , we wish to maintain a polynomially bounded set $M_{i}$ of monomials of degree $i$ and a corresponding set $B_{i}=\{v_{m}\mid m\in M_{i}\}$ of vectors such that ${\sf span}\{B_{i}\}={\sf span}\{v_{m}\mid{\sf deg}(m)=i\}$ , and we build these sets inductively, starting from $i=0,1$ . For $i=0,1$ , we set $M_{i}$ to be the set of all monomials of degree $i$ and populate the vectors in $B_{i}$ in a brute force manner.

Next, suppose we have the sets $M_{i},B_{i}$ for $0\leqslant i<j$ and we want to construct $M_{j}$ and $B_{j}$ ( $j\geqslant 2$ ). We set

M^{\prime}_{j}=\bigcup_{\begin{subarray}{c}i+k=j\\ i,k\geqslant 1\end{subarray}}\{m\times m^{\prime}\mid m\in M_{i}\text{ and }m^% {\prime}\in M_{k}\}

For all $m=m_{1}m_{2}\in M^{\prime}_{j}$ we do the following: we sort the gates of $\Psi$ in topological order and fill the entries of $v_{m}$ in that order as follows:

$\blacksquare$

If $g$ is a leaf, we set $v_{m}(g)=0$ (since $j={\sf deg}(m)\geqslant 2$ ).
$\blacksquare$

If $g=g_{1}\times g_{2}$ is a product gate, set $v_{m}(g)=v_{m_{1}}(g_{1})v_{m_{2}}(g_{2})+v_{m_{2}}(g_{1})v_{m_{1}}(g_{2})+v_{% m}(g_{1})v_{1}(g_{2})+v_{1}(g_{1})v_{m}(g_{2})$ . We can do this since we know the vectors $v_{m_{1}},v_{m_{2}}$ by induction on the degree, and we know $v_{m}(g_{1}),v_{m}(g_{2})$ as $g_{1},g_{2}$ appear before $g$ in the topological order.
$\blacksquare$

If $g=g_{1}+g_{2}$ is a sum gate, set $v_{m}(g)=v_{m}(g_{1})+v_{m}(g_{2})$ . Again, we know $v_{m}(g_{1}),v_{m}(g_{2})$ as $g_{1},g_{2}$ appear before $g$ .

Finally, we select a maximal linearly independent subset $B_{j}$ (using Gaussian elimination) from the set of vectors $\{v_{m}\mid m\in M^{\prime}_{j}\}$ and call the corresponding set of monomials $M_{j}$ . Clearly, $|M_{j}|\leqslant s$ .

Claim 14.

For any monomial $m$ such that ${\sf deg}(m)=j$ , $v_{m}\in{\sf span}\{B_{j}\}$ .

Proof.

The proof is by induction on the degree $j$ . For $j=0,1$ , the claim is trivially true, so assume $j\geqslant 2$ . Now suppose $m$ is uniquely decomposed (up to commutativity) as $m=m_{1}m_{2}$ such that ${\sf deg}(m_{1})=i$ and ${\sf deg}(m_{2})=k$ (with $i,k\geqslant 1$ ). By induction on degree, we assume that

v_{m_{1}}=\sum_{m^{\prime}\in M_{i}}\alpha_{m^{\prime}}v_{m^{\prime}}\text{ % and }v_{m_{2}}=\sum_{m^{\prime\prime}\in M_{k}}\beta_{m^{\prime\prime}}v_{m^{% \prime\prime}}

(2)

for constants $\{\alpha_{m^{\prime}}\mid m^{\prime}\in M_{i}\}$ and $\{\beta_{m^{\prime\prime}}\mid m^{\prime\prime}\in M_{k}\}$ . We will prove that for each gate $g$ of $\Psi$

v_{m}(g)=\sum_{\begin{subarray}{c}m^{\prime}\in M_{i}\\ m^{\prime\prime}\in M_{k}\end{subarray}}\alpha_{m^{\prime}}\beta_{m^{\prime% \prime}}v_{m^{\prime}m^{\prime\prime}}(g)

(3)

This puts $v_{m}$ in ${\sf span}\{B_{j}\}$ by construction. We prove (3) gate by gate, by induction on the depth of the gate.

$\blacksquare$

For a leaf $g$ , $g$ is labeled by a variable or a constant, so $v_{m}(g)=0$ (recall that $j\geqslant 2$ ) and $v_{m^{\prime}m^{\prime\prime}}(g)$ for each $m^{\prime}\in B_{i},m^{\prime\prime}\in B_{k}$ is also all zero by construction, so (3) is true in this case.
$\blacksquare$

For a product gate $g=g_{1}\times g_{2}$ ,

$\displaystyle v_{m}(g)$ $\displaystyle=v_{m_{1}}(g_{1})v_{m_{2}}(g_{2})+v_{m_{2}}(g_{1})v_{m_{1}}(g_{2}% )+v_{m}(g_{1})v_{1}(g_{2})+v_{1}(g_{1})v_{m}(g_{2}).$

After substituting (2) for $v_{m_{1}}$ and $v_{m_{2}}$ using the (degree) induction hypothesis, substituting (3) for $v_{m}(g_{1}),v_{m}(g_{2})$ using induction on the depth of $g_{1},g_{2}$ and simplifying, we get that

$v_{m}(g)=\displaystyle\sum_{\begin{subarray}{c}m^{\prime}\in M_{i}\\ m^{\prime\prime}\in M_{k}\end{subarray}}\alpha_{m^{\prime}}\beta_{m^{\prime% \prime}}\left(\sum_{(r,t)\in\{(1,2),(2,1)\}}v_{m^{\prime}}(g_{r})v_{m^{\prime% \prime}}(g_{t})+v_{m^{\prime}m^{\prime\prime}}(g_{r})v_{1}(g_{t})\right)$

Note that the inner expression is nothing but $v_{m^{\prime}m^{\prime\prime}}(g)$ (by construction), and therefore (3) is true when $g$ is a product gate.

\blacksquare

For a sum gate $g=g_{1}+g_{2}$ , we have

	$\displaystyle v_{m}(g)$	$\displaystyle=v_{m}(g_{1})+v_{m}(g_{2})$
		$\displaystyle=\sum_{\begin{subarray}{c}m^{\prime}\in M_{i}\\ m^{\prime\prime}\in M_{k}\end{subarray}}\alpha_{m^{\prime}}\beta_{m^{\prime% \prime}}v_{m^{\prime}m^{\prime\prime}}(g_{1})+\sum_{\begin{subarray}{c}m^{% \prime}\in M_{i}\\ m^{\prime\prime}\in M_{k}\end{subarray}}\alpha_{m^{\prime}}\beta_{m^{\prime% \prime}}v_{m^{\prime}m^{\prime\prime}}(g_{2})$
		$\displaystyle=\sum_{\begin{subarray}{c}m^{\prime}\in M_{i}\\ m^{\prime\prime}\in M_{k}\end{subarray}}\alpha_{m^{\prime}}\beta_{m^{\prime% \prime}}(v_{m^{\prime}m^{\prime\prime}}(g_{1})+v_{m^{\prime}m^{\prime\prime}}(% g_{2}))$
		$\displaystyle=\sum_{\begin{subarray}{c}m^{\prime}\in M_{i}\\ m^{\prime\prime}\in M_{k}\end{subarray}}\alpha_{m^{\prime}}\beta_{m^{\prime% \prime}}v_{m^{\prime}m^{\prime\prime}}(g)$

where the second step follows by induction on depth and the fourth by construction of $v_{m^{\prime}m^{\prime\prime}}$ . This verifies (3) when $g$ is a sum gate.

These three cases together prove the claim. $\hfill\vartriangleleft$

Clearly, this procedure of constructing $B_{j}$ ’s and $M_{j}$ ’s takes polynomial time since $|B_{j}|\leqslant{\max\{s,n,1\}}$ for each $0\leqslant j\leqslant d$ . To check whether $\Psi\equiv 0$ , we simply check whether there exists an $i\in\{0,\ldots,d\}$ such that there exists a monomial $m\in M_{i}$ such that $v_{m}(g_{s})\neq 0$ , where $g_{s}$ is the output gate of $\Psi$ . If yes, we say $\Psi\not\equiv 0$ , otherwise we say $\Psi\equiv 0$ . $\hfill\blacktriangleleft$

4.2 Deterministic Nonassociative Black-box PIT

Due to space constraints, many of the proofs in this section are omitted, and can be found in the full version of this paper [19]. In this section, we design black-box PIT algorithms for polynomials in ${\mathbb{F}_{\bar{A},C}[X]}$ and ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ computed by low depth circuits. Our algorithms run in quasipolynomial time as long as the input circuit $\Psi$ has depth polylogarithmic in the size of $\Psi$ and the degree of the polynomial computed by it. The algorithms query $\Psi$ on elements of the algebra $\mathbb{A}_{d}$ in the non-commutative case and on elements of $\mathbb{C}_{d}$ in the commutative case, defined in sections 3.1 and 3.2 respectively. In particular, we construct hitting sets of quasipolynomial size in both the commutative and noncommutative setting, for circuits that have depth polylogarithmic in its size and degree.

Theorem 4. [Restated, see original statement.]

There exists a set $H_{n,s,d,\Delta}\subseteq(\mathbb{C}_{d})^{n}$ of size $(nsd)^{O(\Delta)}$ of points in $(\mathbb{C}_{d})^{n}$ such that for every nonassociative, commutative circuit $\Psi$ of size $\leqslant s$ and product depth $\leqslant\Delta$ computing a non-zero polynomial $f\in{\mathbb{F}_{\bar{A},C}[X]}$ of degree $\leqslant d$ , there is a point in $H_{n,s,d,\Delta}$ at which $f$ is non-zero. Furthermore, we can compute $H_{n,s,d,\Delta}$ deterministically in time $(nsd)^{O(\Delta)}$ .

Over the algebra ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ , we have the following analogous result.

Theorem 15.

There exists a set $H_{n,s,d,\Delta}\subseteq(\mathbb{A}_{d})^{n}$ of size $(nsd)^{O(\Delta)}$ of points in $(\mathbb{A}_{d})^{n}$ such that for every nonassociative, noncommutative circuit $\Psi$ of size $\leqslant s$ and product depth $\leqslant\Delta$ computing a non-zero polynomial $f\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ of degree $\leqslant d$ , there is a point in $H_{n,s,d,\Delta}$ at which $f$ is non-zero. Furthermore, we can compute $H_{n,s,d,\Delta}$ in time $(nsd)^{O(\Delta)}$ .

The proofs of Theorems 4 and 15 involve reducing PIT for nonassociative circuits to PIT for associative, unambiguous circuits (see below for a formal definition) and then giving hitting sets for unambiguous circuits.

Definition 6 (Unambiguous Circuits).

Let $Z=\{z_{1}.\ldots,z_{n}\}$ be a commutative, associative set of variables and let $\text{mons}(Z)$ denote the set of monomials in the variables in $Z$ . We say that a circuit $\Psi$ computing a polynomial $f\in\mathbb{F}[Z]$ is unambiguous if for each monomial $m$ in $f$ there is a unique reduced parse tree $T_{m}$ in $\Psi$ generating $m$ . That is, if another reduced parse tree $T$ generates $m$ at any gate in $\Psi$ , then the trees $T$ and $T_{m}$ are identical as labeled rooted binary trees.

4.2.1 Reduction from non-associative to associative, unambiguous circuits

The first, fairly straightforward step is to reduce PIT for nonassociative circuits to PIT for associative, unambiguous circuits. We do this via a set-multilinearization argument. This type of reduction is commonplace in noncommutative PIT literature (see for example [10, 23]).

We first describe the reduction in the nonassociative, commutative setting. The proof is along exactly the same lines in the noncommutative setting as well (in fact it is simpler).

Let $\{x_{1},\ldots,x_{n}\}$ be a set of variables. Let $\Psi$ be a circuit computing a polynomial $f\in{\mathbb{F}_{\bar{A},C}[X]}$ of degree $d^{\prime}\leqslant d$ . For each variable $x_{i},i\in[n]$ , we introduce a set $\{z_{i,j,k}\mid 1\leqslant j,k\leqslant d\}$ . Let $Z=\bigcup_{i=1}^{n}\{z_{i,j,k}\mid 1\leqslant j,k\leqslant d\}$ and define the algebras $\mathbb{C}_{d}$ and $\mathbb{C^{\prime}}_{d}$ over the field $\mathbb{F}(Z)$ . We consider the evaluation map $\Phi:{\mathbb{F}_{\bar{A},C}[X]}\rightarrow\mathbb{C^{\prime}}_{d}$ defined in Section 3.2. Let us recall the definition of $\Phi$ : $\Phi$ maps $x_{i}$ to $Z_{i}$ where for each $1\leqslant j,k\leqslant d$ , the entry $(j,j+1,k)$ of $Z_{i}$ is $z_{i,j,k}$ and the rest of the entries are zero.

We will examine the image of the circuit $\Psi$ under $\Phi$ . To this end, we define another map $\phi:{\mathbb{F}_{\bar{A},C}[X]}\rightarrow\mathbb{F}[Z]$ . Let $m$ be a monomial in $\{x_{1},\ldots,x_{n}\}$ of degree $d^{\prime}$ . Recall that in Section 3.2, we associated to $m$ a set $\Sigma_{m}$ of “orders” and for each $\sigma\in\Sigma_{m}$ , we had $l^{m,\sigma}_{t}$ (for each $1\leqslant t\leqslant d^{\prime}$ ), the level at which the $t$ -th variable in the order $\sigma$ appears in $m$ . For a monomial $m$ in ${\mathbb{F}_{\bar{A},C}[X]}$ define

\phi(m)\triangleq\displaystyle\sum_{\sigma\in\Sigma_{m}}\prod_{t=1}^{d^{\prime% }}z_{\sigma(t),t,l^{m,\sigma}_{t}}

and extend $\phi$ linearly to all of ${\mathbb{F}_{\bar{A},C}[X]}$ .

Lemma 16.

Let $f\in{\mathbb{F}_{\bar{A},C}[X]}$ be a homogeneous polynomial of degree $d^{\prime}\leqslant d$ . The $(1,d^{\prime}+1,1)$ -th entry of $\Phi(f)$ is equal to $\phi(f_{d^{\prime}})$ where $f_{d^{\prime}}$ is the homogeneous degree $d^{\prime}$ component of $f$ .

Proof.

This is a simple corollary of Claim 13. Setting $k_{1},k_{2}=1$ in the statement of Claim 13, we see that for a monomial $m$ of degree $d^{\prime}$ , the $(1,d^{\prime}+1,1)$ -th entry of $\Phi(m)$ is $\phi(m)$ . On the other hand, for a monomial $m$ of degree $\neq d^{\prime}$ , we get that the $(1,d^{\prime}+1,1)$ -th entry of $\Phi(m)$ is $0$ . Therefore, Lemma 16 follows by summing over monomials of $f$ . $\hfill\blacktriangleleft$

Lemma 17.

Let $\Psi$ be a nonassociative, commutative arithmetic circuit of size $s$ and product depth $\Delta$ computing a polynomial $f\in{\mathbb{F}_{\bar{A},C}[X]}$ of degree $d^{\prime}\leqslant d$ . Then, there exists an unambiguous circuit $\Psi^{\prime}$ computing $\phi(f_{d^{\prime}})$ where $f_{d^{\prime}}$ is the homogeneous degree $d^{\prime}$ component of $f$ . Furthermore, the size of $\Psi^{\prime}$ is at most $3d^{4}s$ and product depth at most $\Delta$ .

In the non-commutative setting, let $\{x_{1},\ldots,x_{n}\}$ be a set of variables and let the set $Z$ of variables be as before. We consider the map $\Phi:{\mathbb{F}_{\bar{A},\bar{C}}[X]}\rightarrow\mathbb{A^{\prime}}_{d}$ from Section 3.1 (where $\mathbb{A^{\prime}}_{d}$ is an algebra over the field $\mathbb{F}(Z)$ ). In this case, $\Phi$ sends $x_{i}$ to $Z_{i}\in\mathbb{A^{\prime}}_{d}$ where for each $1\leqslant j,k\leqslant d$ the $(j,j+1,k)$ -th entry of $Z_{i}$ is $z_{i,j,k}$ and every other entry is zero.

Recall that for any monomial $m\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ of degree $d^{\prime}$ there is a unique left to right order $\sigma_{m}:[d^{\prime}]\rightarrow[n]$ of variables associated to $m$ . To study the image of a polynomial under $\Phi$ , we need the auxiliary map $\phi:{\mathbb{F}_{\bar{A},\bar{C}}[X]}\rightarrow\mathbb{F}[Z]$ defined as follows: for a monomial $m$ as above,

\phi(m)=\prod_{t=1}^{d^{\prime}}z_{\sigma_{m}(t),t,l^{m}_{t}}

Using these definitions of $\Phi$ and $\phi$ , and along the same lines as the proofs of Lemmas 16 and 17, we obtain the following:

Lemma 18.

Let $f\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ be a homogeneous polynomial of degree $d^{\prime}\leqslant d$ . The $(1,d^{\prime}+1,1)$ -th entry of $\Phi(f)$ is equal to $\phi(f_{d^{\prime}})$ where $f_{d^{\prime}}$ is the homogeneous degree $d^{\prime}$ component of $f$ .

Lemma 19.

Let $\Psi$ be a nonassociative, noncommutative arithmetic circuit computing a polynomial $f\in{\mathbb{F}_{\bar{A},\bar{C}}[X]}$ of degree $d^{\prime}\leqslant d$ . Then, there exists an unambiguous circuit $\Psi^{\prime}$ computing $\phi(f_{d^{\prime}})$ (where $f_{d^{\prime}}$ is the homogeneous degree $d^{\prime}$ component of $f$ ). Furthermore, the size of $\Psi^{\prime}$ is at most $3d^{4}s$ and product depth at most $\Delta$ .

4.2.2 Hitting sets for low-depth associative, unambiguous circuits

In this section, we construct hitting sets for low-depth unambiguous circuits in the commutative, associative setting. We first define the most important tool in the design of hitting sets for unambiguous circuits: basis isolating weight assignments. Agrawal et al. [1] defined basis isolating weight assignments and used them to construct hitting sets for Read-Once oblivious ABPs. These weight assignements were subsequently also used in a work of Saptharishi and Tengse [23] for PIT of noncommutative unique parse tree circuits.

Let $Z=\{z_{1},\ldots,z_{n}\}$ and let $\Psi$ an unambiguous circuit with $s$ gates computing a polynomial $f\in\mathbb{F}[Z]$ of degree $d$ . Define $f_{\Psi}\in\mathbb{F}^{s}[Z]$ to be the polynomial $\sum\limits_{m\in\text{mons}(Z)}v_{m}m$ where for each monomial $m$ , $v_{m}$ , the coefficient of $m$ in $f_{\Psi}$ , is (as before) an $s$ dimensional vector whose entries are indexed by gates of $\Psi$ and for each gate $g$ in $\Psi$ , $v_{m}(g)\triangleq\text{coeff}_{m}(g)$ . Let $w:Z\rightarrow\mathbb{N}$ be a weight function that assigns weights to variables in $Z$ . $w$ extends to ${\text{mons}(Z)}$ naturally as follows: $w(z_{1}^{i_{1}}z_{2}^{i_{2}}\ldots z_{n}^{i_{n}})=\sum_{j=1}^{n}i_{j}w(z_{j})$ .

Definition 7 (Basis Isolating Weight Assignment).

A weight function $w:Z\rightarrow\mathbb{N}$ is said to be a basis isolating weight assignment for $f_{\Psi}\in\mathbb{F}^{s}[Z]$ if there exists a set $M$ of isolated monomials in $\text{mons}(Z)$ such that the following conditions hold:

1.

$B=\{v_{m}\mid m\in M\}$ forms a basis for $\text{span}\{v_{m}\mid m\in\text{mons}(Z)\}$
2.

For $m,m^{\prime}\in M$ such that $m\neq m^{\prime}$ , we have that $w(m)\neq w(m^{\prime})$
3.

For each $m\not\in M$ , $v_{m}\in\text{span}\{v_{m^{\prime}}\mid m^{\prime}\in M,w(m^{\prime})<w(m)\}$ .

We construct such weight assignments for unambiguous circuits.

Theorem 20.

Let $\Psi$ be an unambiguous circuit with $s$ gates and product depth $\Delta$ computing $f\in\mathbb{F}[Z]$ of degree $d$ . Let $f_{\Psi}=\sum_{m\in\text{mons}(Z)}v_{m}m$ be as above. Then, we can construct a basis isolating weight assignment $w:Z\rightarrow\mathbb{N}$ for $f_{\Psi}$ such that $w(z_{i})=(nds)^{O(\Delta)}$ , for each $i\in[n]$ . Furthermore, we can construct $w$ in time $(nds)^{O(\Delta)}$ .

Next, we show that a basis isolating weight assignment is useful for PIT.

Lemma 21.

Let $\Psi$ be a circuit computing $f(z_{1},\ldots,z_{n})\in\mathbb{F}[Z]$ and $f_{\Psi}=\displaystyle\sum_{m\in\text{mons}(Z)}v_{m}m$ be as defined earlier. Suppose $w$ is a basis isolating weight assignment for $f_{\Psi}$ . Let $\phi$ be the polynomial map that sends $z_{i}$ to $t^{w(z_{i})}$ where $t$ is a new variable. Then $\phi(f)\not\equiv 0\iff f\not\equiv 0$ .

PIT for unambiguous circuits of low depth follows easily from Lemmas 20 and 21, just by noting that the degree of the univariate polynomial $\phi(f)$ (as above) is ${\mathsf{poly}}(n,d,s)^{\Delta}$ . To check if a univariate is identically zero, we can query it on ${\sf degree}+1$ points in $\mathbb{F}$ (recall that a non-zero univariate has at most degree many roots). If $\Delta$ is polylogarithmic in $n, d, s$ , we get the quasipolyomial running time bound. We record this as our next theorem.

Theorem 5. [Restated, see original statement.]

There exists a set $H_{s,n,d,\Delta}\subseteq\mathbb{F}^{n}$ such that for any unambiguous circuit $\Psi$ of size $s$ and product depth $\Delta$ computing a non-zero polynomial $f\in\mathbb{F}[z_{1},\ldots,z_{n}]$ of degree $\leqslant d$ , $f$ is non-zero on some point of $H_{s,n,d,\Delta}$ . Furthermore, $|H_{s,n,d,\Delta}|=(nds)^{O(\Delta)}$ and $H_{s,n,d,\Delta}$ can be constructed in time $(nds)^{O(\Delta)}$ .

Theorems 4 and 15 are a direct consequence of combining the reduction from nonassociative circuits to commutative, associative, unambiguous circuits and the hitting set for unambiguous circuits.

5 Discussion

Two interesting question that stem from our work are the following:

1.

Depth reduction for unambiguous circuits: As briefly mentioned in the introduction, we leave open the question of whether unambiguous circuits can be depth reduced without too much blowup in size. More precisely, suppose we have an unambiguous circuit $\Psi$ of size $s$ , computing a polynomial $f\in\mathbb{F}[z_{1},\ldots,z_{n}]$ of degree $d$ . Does there exist another unambiguous circuit $\Psi^{\prime}$ computing $f$ , with size quasipolynomial in $n, s, d$ and depth polylogarithmic in $n, s, d$ ? A positive answer to this question would imply that the size of the hitting sets from Theorem 4 and Theorem 15 can be improved to quasipolynomial, irrespective of the depth of the circuit. As far as we know, standard depth reduction techniques due to Valiant et al. [27] and Brent [7] do not preserve unambiguity of circuits, even if we allow quasipolynomial blowup in size.
2.

Tightness of the dimension of $\mathbb{C}_{d}$ and $\mathbb{A}_{d}$ : Consider the following, purely mathematical question: What is the smallest possible dimension $k(d)$ of a unital algebra that does not satisfy any identity $f\in{\mathbb{F}_{\bar{A},C}[X]}$ of degree $\leqslant d$ ? We show $k(d)\leqslant d(d+1)^{2}+1$ . One could also ask the analogous question over the algebra ${\mathbb{F}_{\bar{A},\bar{C}}[X]}$ . The Amitsur-Levitzki Theorem (Theorem 7) gives such a tight characterization over $\mathbb{F}\langle X\rangle$ , for matrix algebras.

References

[1] Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for roabp and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669–697, 2015. doi:10.1137/140975103.
[2] A. S. Amitsur and J. Levitzki. Minimal identities for algebras. Proceedings of the American Mathematical Society, 1(4):449–463, 1950. URL: http://www.jstor.org/stable/2032312.
[3] V. Arvind and S. Raja. Some lower bound results for set-multilinear arithmetic computations. Chicago Journal of Theoretical Computer Science, 2016, April 2016.
[4] Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja. Efficient identity testing and polynomial factorization in nonassociative free rings. In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, volume 83 of LIPIcs, pages 38:1–38:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPICS.MFCS.2017.38.
[5] Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22(3):317–330, 1983. doi:10.1016/0304-3975(83)90110-X.
[6] Nicolas Bourbaki. Lie Groups and Lie Algebras. Springer Science, 1989.
[7] Richard P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201–206, April 1974. doi:10.1145/321812.321815.
[8] Richard A. DeMillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Inf. Process. Lett., 7(4):193–195, 1978. doi:10.1016/0020-0190(78)90067-4.
[9] Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, and Olivier Serre. Lower bounds for arithmetic circuits via the hankel matrix. computational complexity, 30(2):14, October 2021. doi:10.1007/s00037-021-00214-1.
[10] Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 243–252, 2013. doi:10.1109/FOCS.2013.34.
[11] A. Giambruno and Mikhail Zaicev. Polynomial Identities and Asymptotic Methods, volume 122 of Mathematical surveys and monographs. American Mathematical Soc., 2005.
[12] Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff. Relationless completeness and separations. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 280–290. IEEE Computer Society, 2010. doi:10.1109/CCC.2010.34.
[13] Nathan Jacobson, Daniel Zelinsky, Richard E. Block, David J. Saltman, and J. Marshall Osborn. A. Adrian Albert Collected Mathematical Papers, volume 3. American Mathematical Society, 1993.
[14] Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex., 13(1-2):1–46, 2004. doi:10.1007/s00037-004-0182-6.
[15] K. A. Kalorkoti. A lower bound for the formula size of rational functions. SIAM Journal on Computing, 14(3):678–687, 1985. doi:10.1137/0214050.
[16] Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and pit for non-commutative arithmetic circuits with restricted parse trees. computational complexity, 28(3):471–542, September 2019. doi:10.1007/s00037-018-0171-9.
[17] Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Chicago Journal of Theoretical Computer Science, 2019(2), September 2019. URL: http://cjtcs.cs.uchicago.edu/articles/2019/2/contents.html.
[18] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 804–814. IEEE, 2021. doi:10.1109/FOCS52979.2021.00083.
[19] Partha Mukhopadhyay, C. Ramya, and Pratik Shastri. Efficient polynomial identity testing over nonassociative algebras. Electron. Colloquium Comput. Complex., TR25-061, 2025. URL: https://eccc.weizmann.ac.il/report/2025/061.
[20] Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410–418. ACM, 1991. doi:10.1145/103418.103462.
[21] Avi Wigderson Noam Nisan. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149–167, 1994. doi:10.1016/S0022-0000(05)80043-1.
[22] R. Raz and A. Shpilka. Deterministic polynomial identity testing in non commutative models. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 215–222, 2004. doi:10.1109/CCC.2004.1313845.
[23] Ramprasad Saptharishi and Anamay Tengse. Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees. In Sumit Ganguly and Paritosh Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), volume 122 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:19, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2018.6.
[24] Nitin Saxena. Progress on polynomial identity testing – II. CoRR, abs/1401.0976, 2014. arXiv:1401.0976.
[25] Jacob T. Schwartz. Fast probabilistic algorithm for verification of polynomial identities. J. ACM., 27(4):701–717, 1980. doi:10.1145/322217.322225.
[26] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3-4):207–388, 2010. doi:10.1561/0400000039.
[27] L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing, 12(4):641–644, 1983. doi:10.1137/0212043.
[28] Leslie G. Valiant. On non-linear lower bounds in computational complexity. In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, STOC ’75, pages 45–53, New York, NY, USA, 1975. Association for Computing Machinery. doi:10.1145/800116.803752.
[29] H. Wee and A. Bogdanov. More on noncommutative polynomial identity testing. In Proceedings. Twentieth Annual IEEE Conference on Computational Complexity, pages 92–99, Los Alamitos, CA, USA, June 2005. IEEE Computer Society. doi:10.1109/CCC.2005.13.
[30] R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. of the Int. Sym. on Symbolic and Algebraic Computation, pages 216–226, 1979.

[bib.bib1] [1] Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for roabp and sum of set-multilinear circuits. SIAM Journal on Computing, 44(3):669–697, 2015. doi:10.1137/140975103.

[bib.bib2] [2] A. S. Amitsur and J. Levitzki. Minimal identities for algebras. Proceedings of the American Mathematical Society, 1(4):449–463, 1950. URL: http://www.jstor.org/stable/2032312.

[bib.bib3] [3] V. Arvind and S. Raja. Some lower bound results for set-multilinear arithmetic computations. Chicago Journal of Theoretical Computer Science, 2016, April 2016.

[bib.bib4] [4] Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, and S. Raja. Efficient identity testing and polynomial factorization in nonassociative free rings. In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, volume 83 of LIPIcs, pages 38:1–38:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPICS.MFCS.2017.38.

[bib.bib5] [5] Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22(3):317–330, 1983. doi:10.1016/0304-3975(83)90110-X.

[bib.bib6] [6] Nicolas Bourbaki. Lie Groups and Lie Algebras. Springer Science, 1989.

[bib.bib7] [7] Richard P. Brent. The parallel evaluation of general arithmetic expressions. J. ACM, 21(2):201–206, April 1974. doi:10.1145/321812.321815.

[bib.bib8] [8] Richard A. DeMillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Inf. Process. Lett., 7(4):193–195, 1978. doi:10.1016/0020-0190(78)90067-4.

[bib.bib9] [9] Nathanaël Fijalkow, Guillaume Lagarde, Pierre Ohlmann, and Olivier Serre. Lower bounds for arithmetic circuits via the hankel matrix. computational complexity, 30(2):14, October 2021. doi:10.1007/s00037-021-00214-1.

[bib.bib10] [10] Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 243–252, 2013. doi:10.1109/FOCS.2013.34.

[bib.bib11] [11] A. Giambruno and Mikhail Zaicev. Polynomial Identities and Asymptotic Methods, volume 122 of Mathematical surveys and monographs. American Mathematical Soc., 2005.

[bib.bib12] [12] Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff. Relationless completeness and separations. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 280–290. IEEE Computer Society, 2010. doi:10.1109/CCC.2010.34.

[bib.bib13] [13] Nathan Jacobson, Daniel Zelinsky, Richard E. Block, David J. Saltman, and J. Marshall Osborn. A. Adrian Albert Collected Mathematical Papers, volume 3. American Mathematical Society, 1993.

[bib.bib14] [14] Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex., 13(1-2):1–46, 2004. doi:10.1007/s00037-004-0182-6.

[bib.bib15] [15] K. A. Kalorkoti. A lower bound for the formula size of rational functions. SIAM Journal on Computing, 14(3):678–687, 1985. doi:10.1137/0214050.

[bib.bib16] [16] Guillaume Lagarde, Nutan Limaye, and Srikanth Srinivasan. Lower bounds and pit for non-commutative arithmetic circuits with restricted parse trees. computational complexity, 28(3):471–542, September 2019. doi:10.1007/s00037-018-0171-9.

[bib.bib17] [17] Guillaume Lagarde, Guillaume Malod, and Sylvain Perifel. Non-commutative computations: lower bounds and polynomial identity testing. Chicago Journal of Theoretical Computer Science, 2019(2), September 2019. URL: http://cjtcs.cs.uchicago.edu/articles/2019/2/contents.html.

[bib.bib18] [18] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 804–814. IEEE, 2021. doi:10.1109/FOCS52979.2021.00083.

[bib.bib19] [19] Partha Mukhopadhyay, C. Ramya, and Pratik Shastri. Efficient polynomial identity testing over nonassociative algebras. Electron. Colloquium Comput. Complex., TR25-061, 2025. URL: https://eccc.weizmann.ac.il/report/2025/061.

[bib.bib20] [20] Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Cris Koutsougeras and Jeffrey Scott Vitter, editors, Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410–418. ACM, 1991. doi:10.1145/103418.103462.

[bib.bib21] [21] Avi Wigderson Noam Nisan. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149–167, 1994. doi:10.1016/S0022-0000(05)80043-1.

[bib.bib22] [22] R. Raz and A. Shpilka. Deterministic polynomial identity testing in non commutative models. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004., pages 215–222, 2004. doi:10.1109/CCC.2004.1313845.

[bib.bib23] [23] Ramprasad Saptharishi and Anamay Tengse. Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees. In Sumit Ganguly and Paritosh Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), volume 122 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:19, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2018.6.

[bib.bib24] [24] Nitin Saxena. Progress on polynomial identity testing – II. CoRR, abs/1401.0976, 2014. arXiv:1401.0976.

[bib.bib25] [25] Jacob T. Schwartz. Fast probabilistic algorithm for verification of polynomial identities. J. ACM., 27(4):701–717, 1980. doi:10.1145/322217.322225.

[bib.bib26] [26] Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3-4):207–388, 2010. doi:10.1561/0400000039.

[bib.bib27] [27] L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM Journal on Computing, 12(4):641–644, 1983. doi:10.1137/0212043.

[bib.bib28] [28] Leslie G. Valiant. On non-linear lower bounds in computational complexity. In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, STOC ’75, pages 45–53, New York, NY, USA, 1975. Association for Computing Machinery. doi:10.1145/800116.803752.

[bib.bib29] [29] H. Wee and A. Bogdanov. More on noncommutative polynomial identity testing. In Proceedings. Twentieth Annual IEEE Conference on Computational Complexity, pages 92–99, Los Alamitos, CA, USA, June 2005. IEEE Computer Society. doi:10.1109/CCC.2005.13.

[bib.bib30] [30] R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. of the Int. Sym. on Symbolic and Algebraic Computation, pages 216–226, 1979.

Efficient Polynomial Identity Testing over Nonassociative Algebras

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our Results

1.1.1 Black-box randomized nonassociative PIT (Section 3)

Lemma 1.

Theorem 2.

1.1.2 White-box deterministic PIT over 𝔽𝑨¯,𝑪⁢[𝑿] (Section 4.1)

Theorem 3.

1.1.3 Black-box deterministic nonassociative PIT (Section 4.2)

Theorem 4.

Theorem 5.

Organization

2 Preliminaries

Definition 1 (Algebra over a field).

Definition 2 (Polynomial Identities).

Definition 3 (Arithmetic Circuit).

Definition 4 (Parse trees).

Definition 5 (Reduced Parse Trees).

Lemma 6 (Polynomial Identity Lemma [30, 25, 8]).

Theorem 7 (Amitsur-Levitzki Theorem [2]).

2.1 A structural lemma about nonassociative monomials

2.1.1 Over the algebra 𝔽𝑨¯,𝑪¯⁢[𝑿]

Lemma 8.

Proof.

2.1.2 Over the algebra 𝔽𝑨¯,𝑪⁢[𝑿]

Observation 9.

3 Randomized Black-box PIT for Nonassociative circuits

3.1 Nonassociative, Noncommutative Randomized Black-box PIT

The Algebra 𝔸𝐝

Lemma 10.

Proof.

Claim 11.

Proof.

Theorem 12.

Proof.

3.2 Nonassociative, Commutative Randomized Black-box PIT

The Algebra ℂ𝒅

Lemma 1. [Restated, see original statement.]

Proof.

Claim 13.

Proof.

Theorem 2. [Restated, see original statement.]

4 Deterministic PIT Algorithms Over 𝔽𝑨¯,𝑪⁢[𝑿]

4.1 White-box Deterministic PIT over 𝔽𝑨¯,𝑪⁢[𝑿]

Theorem 3. [Restated, see original statement.]

Proof.

Claim 14.

Proof.

4.2 Deterministic Nonassociative Black-box PIT

Theorem 4. [Restated, see original statement.]

Theorem 15.

Definition 6 (Unambiguous Circuits).

4.2.1 Reduction from non-associative to associative, unambiguous circuits

Lemma 16.

Proof.

Lemma 17.

Lemma 18.

Lemma 19.

4.2.2 Hitting sets for low-depth associative, unambiguous circuits

Definition 7 (Basis Isolating Weight Assignment).

Theorem 20.

Lemma 21.

Theorem 5. [Restated, see original statement.]

5 Discussion

References

1.1.2 White-box deterministic PIT over ${\mathbb{F}_{\bar{A},C}[X]}$ (Section 4.1)

2.1.1 Over the algebra $\mathbb{F}_{\bar{A},\bar{C}}[X]$

2.1.2 Over the algebra $\mathbb{F}_{\bar{A},{C}}[X]$

The Algebra $\mathbf{\mathbb{A}_{d}}$

The Algebra $\mathbb{C}_{d}$

4 Deterministic PIT Algorithms Over ${\mathbb{F}_{\bar{A},C}[X]}$

4.1 White-box Deterministic PIT over ${\mathbb{F}_{\bar{A},C}[X]}$