A factorization algorithm for \(G\)-algebras and its applications (Q2409016)

The authors consider the problem of factoring polynomials in \(G\)-algebras, which have rewrite rules \(x_jx_i=c_{ij}x_ix_j+d_{ij}\) where the \(c_{ij}\) are units of a field and the \(d_{ij}\) are polynomials over the same field which, when nonzero, have leading monomial smaller than \(x_ix_j\). (Of note is the discussion on p. 3 of the different meanings of factorization.) The main result leads to Algorithm 1, which produces all finite factorizations of a polynomial over a \(G\)-algebra, which is a finite factorization domain. It sets up an ansatz \(a\cdot b=g\), then computes a Gröbner basis of the ideal generated by the coefficients of \(a\cdot b-g\). (An ``ansatz'' is an educated guess.) When the basis indicates a solution, the algorithm saves it and later factors the factors recursively to find irreducible factorizations. The authors prove the algorithm's asymptotic complexity. A library that implements the algorithm for Singular (Plural) is provided online. This algorithm allows them to develop a second algorithm to compute factorized Gröbner bases for \(G\)-algebras, also implemented as a library for Singular (Plural). While complexity is not proved in this case, the authors point out that the algorithm must compute a (left) Gröbner basis, and this is already known to be double exponential in the number of variables. Throughout the article, the authors refer to applications and work through numerous examples.