Martin Kreuzer ; Florian Walsh - Efficient Algorithms for Finite $\mathbb{Z}$-Algebras

gcc:12496 - journal of Groups, complexity, cryptology, April 24, 2024, Volume 15, Issue 2 - https://doi.org/10.46298/jgcc.2024.15.2.12496
Efficient Algorithms for Finite $\mathbb{Z}$-AlgebrasArticle

Authors: Martin Kreuzer ; Florian Walsh

    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$.


    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)

    Consultation statistics

    This page has been seen 832 times.
    This article's PDF has been downloaded 688 times.