For a finite $\mathbb{Z}$-algebra $R$, i.e., for a $\mathbb{Z}$-algebra which is a finitely generated $\mathbb{Z}$-module, we assume that $R$ is explicitly given by a system of $\mathbb{Z}$-module generators $G$, its relation module ${\rm Syz}(G)$, and the structure constants of the multiplication in $R$. In this setting we develop and analyze efficient algorithms for computing essential information about $R$. First we provide polynomial time algorithms for solving linear systems of equations over $R$ and for basic ideal-theoretic operations in $R$. Then we develop ZPP (zero-error probabilitic polynomial time) algorithms to compute the nilradical and the maximal ideals of 0-dimensional affine algebras $K[x_1,\dots,x_n]/I$ with $K=\mathbb{Q}$ or $K=\mathbb{F}_p$. The task of finding the associated primes of a finite $\mathbb{Z}$-algebra $R$ is reduced to these cases and solved in ZPPIF (ZPP plus one integer factorization). With the same complexity, we calculate the connected components of the set of minimal associated primes ${\rm minPrimes}(R)$ and then the primitive idempotents of $R$. Finally, we prove that knowing an explicit representation of $R$ is polynomial time equivalent to knowing a strong GrÃ¶bner basis of an ideal $I$ such that $R = \mathbb{Z}[x_1,\dots,x_n]/I$.

Source: arXiv.org:2308.02610

Volume: Volume 15, Issue 2

Published on: April 24, 2024

Submitted on: November 1, 2023

Keywords: Mathematics - Commutative Algebra,Mathematics - Rings and Algebras,13P99 (Primary) 68W39, 13P10, 68Q15 (Secondary)

This page has been seen 832 times.

This article's PDF has been downloaded 688 times.