Efficient algorithms for finite \(\mathbb{Z}\)-algebras (Q6601470)

A finite \(\mathbb{Z}\)-algebra is a \(\mathbb{Z}\)-algebra which is finitely generated as a \(\mathbb{Z}\)-module. For example, if \(I \subset \mathbb{Z}[x_1,\ldots,x_n]\) is a zero-dimensional ideal, then \(R := \mathbb{Z}[x_1,\ldots,x_n]/I\) is a finite \(\mathbb{Z}\)-algebra. Assume that \(R\) is a finite \(\mathbb{Z}\)-algebra generated by a set \(G = \{g_1,\ldots,g_k\}\). Moreover, assume that we have a generating set for the first syzygy module of the elements of \(G\). Finally, assume that the multiplication table of \(G\) is given; that is, for each \(i,j\), we are provided with the coefficients \(c_{i,j,\ell}\) such that\N\[\Ng_i \cdot g_j = \sum_{\ell=1}^k c_{i,j,\ell} \cdot g_\ell.\N\]\NWe refer to the set of all this information as an explicit representation of \(R\).\N\NThe aim of this paper is, given an explicit representation of \(R\), to present efficient algorithms for computing essential properties of \(R\), focusing on polynomial-time complexity for solving linear systems of equations over \(R\), as well as for basic ideal-theoretic operations in \(R\). Moreover, in this setting, the authors describe algorithms for computing the nilradical, associated primes and maximal ideals, primitive idempotents, and connected components of \(\text{Spec}(R)\) with the lowest possible worst-case complexity. Finally, it is proven that knowing an explicit representation of \(R\) in the case of the aforementioned example is polynomial-time equivalent to knowing a strong Gröbner basis for the ideal \(I\).