Summary: In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring \(\mathbb{F}\{x_1,x_2,\ldots,x_n\}\). Prior to this work, nonassociative arithmetic computation was considered by P. Hrubes et al. [“Relationless completeness and separations”, Techn. Rep., Weizmann Institute of Science, Electronic Colloquium on Computational Complexity, TR-10-040 (2010)], and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing (PIT) and polynomial factorization over \(\mathbb{F}\{x_1,x_2,\ldots,x_n\}\) and show the following results.

●

Given an arithmetic circuit \(C\) of size \(s\) computing a polynomial \(f\in\mathbb{F}\{x_1,x_2,\ldots,x_n\}\) of degree \(d\), we give a deterministic \(\operatorname{poly}(n,s,d)\) algorithm to decide if \(f\) is identically zero polynomial or not. Our result is obtained by a suitable adaptation of the PIT algorithm of R. Raz and A. Shpilka [Comput. Complexity 14, No. 1, 1–19 (2005; Zbl 1096.68070)] for noncommutative ABPs.

●

Given an arithmetic circuit \(C\) or size \(s\) computing a polynomial \(f\in\mathbb{F}\{x_1,x_2,\ldots,x_n\}\) of degree \(d\), we give an efficient deterministic algorithm to compute circuits for the irreducible factors of \(f\) in time \(\operatorname{poly}(n,s,d)\) when \(\mathbb{F}=\mathbb{Q}\). Over finite fields of characteristic \(p\), our algorithm runs in time \(\operatorname{poly}(n,s,d,p)\).

For the entire collection see [Zbl 1376.68011].