# Computing the Unit Group of a Commutative Finite $\mathbb{Z}$-Algebra

Martin Kreuzer  Fakultät für Informatik und Mathematik
Universität Passau, D-94032 Passau, Germany<EMAIL_ADDRESS>and
Florian Walsh  Fakultät für Informatik und Mathematik
Universität Passau, D-94032 Passau, Germany<EMAIL_ADDRESS>
###### Abstract.

For a commutative finite $\mathbb{Z}$-algebra, i.e., for a commutative ring
$R$ whose additive group is finitely generated, it is known that the group of
units of $R$ is finitely generated, as well. Our main results are algorithms
to compute generators and the structure of this group. This is achieved by
reducing the task first to the case of reduced rings, then to torsion-free
reduced rings, and finally to an order in a reduced ring. The simplified cases
are treated via a calculation of exponent lattices and various algorithms to
compute the minimal primes, primitive idempotents, and other basic objects.
All algorithms have been implemented and are available as a SageMath package.
Whenever possible, the time complexity of the described methods is tracked
carefully.

###### Key words and phrases:

finite Z-algebra, unit group, exponent lattice, explicitly given algebra

###### 1991 Mathematics Subject Classification:

Primary 13P99; Secondary 20-08, 11R27

##  1\. Introduction

In the study of the structure of a commutative ring, one important aspect is
its group of units. A famous result in this direction dating back to 1846 is
L.G. Dirichlet’s unit theorem (see [7]) which says that the group of units of
the ring of integers of a number field is a finitely generated abelian group.
Much later, in 1972, this was generalized to orders in such rings by H.
Zassenhaus (see [30]). With the advance of computer algebra, the computation
of an actual system of generators of such a unit group and its set of
relations have become feasible, and algorithms achieving these tasks have been
developed (see, for example, [6, 3]). Also for other types of rings, for which
the group of units is known to be finitely generated, explicit algorithms for
computing their generators or their presentations have been described,
including for orders in (not necessarily commutative) finite dimensional
$\mathbb{Q}$-algebras (see [4]), for integral group rings over finite abelian
groups (see [10]), and for the affine coordinate rings of rational normal
curves and elliptic curves (see [5]).

In this paper we improve on many of these results and consider the general
case of a commutative finite $\mathbb{Z}$-algebra, i.e., a commutative ring
which is a finitely generated $\mathbb{Z}$-module. In [24], P. Samuel proved
that the unit groups of such rings are finitely generated. The main results of
this paper are algorithms for computing a system of generators of these unit
groups, as well as for calculating their structure.

Let us describe the path we follow to reach these goals. After recalling some
basic results about finite $\mathbb{Z}$-algebras in Section 2, we devise
algorithms for computing exponent lattices in such a ring $R$, i.e., lattices
of the type $\Lambda=\\{(a_{1},\dots,a_{k})\in\mathbb{Z}^{k}\mid
f_{1}^{a_{1}}\cdots f_{k}^{a_{k}}=1\\}$ where $f_{1},\dots,f_{k}\in R$. Using
several techniques from our previous paper [19], we reduce the calculation of
exponent lattices to the cases of 0-dimensional algebras over the fields
$\mathbb{Q}$ and $\mathbb{F}_{p}$ with a prime $p$. For this characteristic
$p$ part, we solve the problem first modulo $p$ and then refine the answer
modulo higher powers of $p$ with a method resembling the well-known technique
of Hensel lifting (see Proposition 8). Altogether, we obtain Algorithm 3 and
discuss several methods to improve its implementation (see Remark 9).

The next step is taken in Section 4 where we consider the case of a reduced
finite $\mathbb{Z}$-algebra. If the algebra is even integral, algorithms for
computing its unit group are known (see Remark 10). The general case is
treated by calculating the primitive idempotents and computing the unit group
of an order via reduction to the case of orders in number fields (see Lemma 11
and Algorithm 4). This solves the torsion-free reduced case (see Corollary 13)
and allows us to deal with the general reduced case using a version of the
Chinese Remainder Theorem (see Lemma 14 and Algorithm 4).

Finally, in Section 5, we attack the general case of a finite
$\mathbb{Z}$-algebra. The main additional task is to find generators of
$1+\operatorname{Rad}(0)$ (see Lemma 15). We provide two different solutions
(Algorithm 5 and Lemma 17). All in all, we are able to compute a system of
generators of the unit group of a finite $\mathbb{Z}$-algebra (see Algorithm
5) and also its structure in terms of its rank and invariant factors (see
Corollary 18).

Throughout the paper we tried to keep track of the complexity of the presented
algorithms. First of all, this depends on the way the algebra $R$ is given:
either explicitly (via generators and relations of $R^{+}$ plus the structure
constants) or through a presentation $R=\mathbb{Z}[x_{1},\dots,x_{n}]/I$ with
an ideal $I$ given by explicit generators. In the first case, many steps of
the algorithms can be performed in probabilistic polynomial time plus
(possibly) one integer factorization. In the second case, we may have to first
compute a strong Gröbner basis to get going. After we reduce everything to the
case of an order in a number field, we have to rely on previous work whose
precise complexity estimates are apparently not known.

All algorithms in this paper are illustrated by explicit examples. They were
computed using an implementation by the second author in the software system
SageMath [27]. The complete package is available freely from his GitHub page
[28]. As for the basic definitions and notation, we adhere to the terminology
given in the books [17] and [18].

##  2\. Preliminaries on Finite $\mathbb{Z}$-Algebras

In this section we collect basic properties of finite $\mathbb{Z}$-algebras,
i.e., $\mathbb{Z}$-algebras which are finitely generated as a
$\mathbb{Z}$-module. Given such an algebra $R$, we denote its underlying
$\mathbb{Z}$-module by $R^{+}$. Subsequently, we assume that a
$\mathbb{Z}$-algebra $R$ is either given by an ideal $I$ in
$P=\mathbb{Z}[x_{1},\dots,x_{n}]$ such that $R=P/I$ or that it is given as
follows.

######  Remark 1.

A $\mathbb{Z}$-algebra $R$ is said to be explicitly given if it is given by
the following information.

  1. (a)

A set of generators $\mathcal{G}=\\{g_{0},\dots,g_{n}\\}$ of the
$\mathbb{Z}$-module $R^{+}$, together with a matrix $A=(a_{\ell
k})\in\operatorname{Mat}_{m,n+1}(\mathbb{Z})$ whose rows generate the syzygy
module $\operatorname{Syz}_{\mathbb{Z}}(\mathcal{G})$ of $\mathcal{G}$.

  2. (b)

Structure constants $c_{ijk}\in\mathbb{Z}$ such that
$g_{i}g_{j}=\sum_{k=0}^{n}c_{ijk}g_{k}$ for $i,j=0,\dots,n$.

Notice that we may assume $g_{0}=1$ and encode this information as an ideal

$I=\left\langle
x_{i}x_{j}-\textstyle\sum\limits_{k=0}^{n}c_{ijk}x_{k},\;\textstyle\sum\limits_{k=0}^{n}a_{\ell
k}g_{k}\mid i,j=1,\dots,n,\;\ell=1,\dots,m\right\rangle$

in $P=\mathbb{Z}[x_{1},\dots,x_{n}]$ such that $R\cong P/I$.

If $R=P/I$ is not explicitly given, then we can obtain an explicit
representation from a strong Gröbner basis of $I$.

Given an ideal $I\subseteq P$ and a term ordering $\sigma$, a set of
polynomials $G=\\{g_{1},\dots,g_{r}\\}$ in $I$ is called a strong
$\sigma$-Gröbner basis of $I$ if, for every non-zero polynomial $f\in I$,
there exists an index $i\in\\{1,\dots,r\\}$ such that
$\operatorname{LM}_{\sigma}(f)$ is a multiple of
$\operatorname{LM}_{\sigma}(g_{i})$.

Strong Gröbner bases can be computed using a generalization of Buchberger’s
algorithm (see for example [1, Ch. 4] or [9]). For some ideal-theoretic
operations which can be performed effectively using strong Gröbner bases, we
refer to [1, Ch. 4] and [17, Ch. 3]. Generators of the $\mathbb{Z}$-module
$R^{+}$ can be deduced from a strong Gröbner basis as follows.

######  Proposition 2.

(Macaulay’s Basis Theorem for Finite $\mathbb{Z}$-Algebras)
Let $I\subseteq P$ be an ideal such that $P/I$ is a finite
$\mathbb{Z}$-algebra, let $\sigma$ be a term ordering on $\mathbb{T}^{n}$, and
let
$L=\\{m\in\operatorname{LM}_{\sigma}(I)\mid\operatorname{LC}_{\sigma}(m)=1\\}$
be the set of all monic leading monomials of $I$. Then the residue classes of
the terms in $\mathcal{O}_{\sigma}=\mathbb{T}^{n}\setminus L$ form a
generating set of the $\mathbb{Z}$-module $P/I$.

######  Proof 2.1.

See Proposition 6.6 in [20].

Given generators of $R^{+}$ as in the preceding lemma, it is also possible to
determine an explicit presentation of $R$ (see Algorithm 6.7 and Corollary 6.8
in [20]). From such a presentation we can then determine the structure of
$R^{+}$.

######  Remark 3.

By the structure theorem for finitely generated modules over a principal ideal
domain there exist $r$ and $k_{1},\dots,k_{u}$ in $\mathbb{N}$ such that
$k_{i}$ divides $k_{j}$ for $i<j$ and such that

$R^{+}\cong\mathbb{Z}^{r}\oplus\mathbb{Z}/k_{1}\mathbb{Z}\oplus\cdots\oplus\mathbb{Z}/k_{u}\mathbb{Z}.$

The numbers $r$ and $k_{1},\dots,k_{u}$ are uniquely determined by $R^{+}$. We
call $r$ the rank and $k_{1},\dots,k_{u}$ the invariant factors of $R^{+}$.
The largest invariant factor $k_{u}$ is the exponent of the torsion subgroup
of $R^{+}$. We call it the torsion exponent $\tau$ of $R^{+}$.

The rank, the invariant factors, and the torsion exponent can be determined
using a Smith normal form computation (for details we refer to Section 2 in
[20]). Algorithms which compute the Smith normal form of an integer matrix can
for example be found in [13] or [26]. If an explicit presentation is given or
has been determined from a strong Gröbner basis, many computations that we
need in the following sections can be performed efficiently, i.e., in
(probabilistic) polynomial time in the bit complexity of the input. More
precisely, we have the following complexity results.

######  Remark 4.

Assume that $R$ is an explicitly given finite $\mathbb{Z}$-algebra.

  1. (a)

The minimal prime ideals of $R$ can be computed in zero-error probabilistic
polynomial time except for the factorization of one integer (see Algorithm 4.2
in [20]).

  2. (b)

The primitive idempotents of $R$ can be obtained from its minimal prime ideals
in polynomial time using Algorithm 5.8 in [20].

  3. (c)

The intersection of ideals in $R$ can be determined in polynomial time using
Proposition 2.9 in [20].

##  3\. Exponent Lattices in Finitely Generated $\mathbb{Z}$-Algebras

Let $R=P/I$ be a finitely generated $\mathbb{Z}$-algebra. In the following we
present an algorithm which computes the multiplicative relations between units
in $R$. We emphasize that in this section we do not require that $R$ is a
finite $\mathbb{Z}$-algebra.

Let $R$ be a ring and let $f_{1},\dots,f_{k}\in R^{\times}$. Then the lattice

$\Lambda=\\{(a_{1},\dots,a_{k})\in\mathbb{Z}^{k}\mid f_{1}^{a_{1}}\cdots
f_{k}^{a_{k}}=1\\}$

is called the exponent lattice of $(f_{1},\dots,f_{k})$ in $R$.

The goal of this section is to provide an algorithm which computes a basis of
the exponent lattice of the tuple $(f_{1},\dots,f_{k})$ in a finitely
generated $\mathbb{Z}$-algebra. In the following we refer to this task simply
as computing an exponent lattice. Let us recall how this task is solved in
affine $K$-algebras, i.e., in finitely generated algebras over a field $K$.

######  Remark 5.

(Computing Exponent Lattices in Affine $K$-Algebras)
The problem of computing the exponent lattices has been considered by many
authors. For units in a number field algorithms can be found in [11], in
Section 7.3 of [14], in Section 3 of [15], or in [31]. Based on these
algorithms, a method for computing the exponent lattice in zero-dimensional
$\mathbb{Q}$-algebras is presented in [21]. Recently, we generalized these
results and presented a method (see Algorithm 5.3 in [19]) for computing
exponent lattices in arbitrary affine $K$-algebras where $K$ is a field such
that exponent lattices in finite extensions of $K$ can be effectively
computed. Note, that this includes the cases $K=\mathbb{Q}$ and
$K=\mathbb{F}_{p}$.

Now the main idea is to reduce the problem of computing an exponent lattice in
$R$ to computing exponent lattices in affine $\mathbb{Q}$\- and
$\mathbb{F}_{p}$-algebras.

######  Lemma 6.

Let $R$ be a ring and $I$ an ideal in $R$. If $I:f^{\infty}=I:f^{m}$ some
$f\in R$ and $m\in\mathbb{N}$. Then we have

$I=(I:f^{m})\cap\langle I,f^{m}\rangle.$

######  Proof 3.1.

See [12], Lemma 3.3.6.

Together with the following proposition this lemma is the main tool for
reducing the exponent lattice computation to $\mathbb{Q}$\- and
$\mathbb{F}_{p}$-algebras.

######  Proposition 7.

Let $I$ be an ideal in $P$, let $G=\\{g_{1},\dots,g_{s}\\}$ be a minimal
strong Gröbner basis of $I$, and let $N\in\mathbb{Z}$ be the least common
multiple of the leading coefficients of the elements of $G$. Then the
following holds.

  1. (a)

$I=(I:\langle N\rangle)\cap(I+\langle N\rangle)$

  2. (b)

If $I\cap\mathbb{Z}=\langle 0\rangle$, then
$I\mathbb{Q}[x_{1},\dots,x_{n}]\cap P=I:\langle N\rangle$.

######  Proof 3.2.

See [16], Proposition 4.3.

The following example given in Section 4 of [16] illustrates the fact that the
least common multiple $N$ of the leading coefficients of a strong Gröbner
basis as in the proposition is in general not the smallest number satisfying
$I:\langle N\rangle=I:\langle N\rangle^{\infty}$.

Consider the ideal $I=\langle
x^{2},y^{2},z^{2},xz+yz,xy,2x-y,3z\rangle\subseteq\mathbb{Z}[x,y,z]$. The
generators form a strong Gröbner basis of $I$ and the least common multiple of
the leading coefficients is 6. But we have $I:\langle 3\rangle=I:\langle
6\rangle=I:\langle 6\rangle^{\infty}$.

Let $\\{g_{1},\dots,g_{k}\\}$ be a strong Gröbner basis of $I$ and let $N$ be
the least common multiple of the leading coefficients of the $g_{i}$. Then we
have $I=I:\langle N\rangle\cap\langle I,N\rangle$. The property $I:\langle
N\rangle=I\mathbb{Q}[x_{1},\dots,x_{n}]\cap P$ then allows us to compute the
exponent lattice modulo $I:\langle N\rangle$. This can be done using Remark 5.
The ideal $\langle I,N\rangle$ can be further split into $\langle
I,N\rangle=\bigcap_{i=1}^{r}\langle I,p_{i}^{e_{i}}\rangle$ where
$N=p_{1}^{e_{1}}\cdots p_{r}^{e_{r}}$ is the prime factorization of $N$. Let
$p\in\mathbb{N}$ be a prime number. The exponent lattice modulo an ideal of
the form $\langle I,p\rangle$ can be computed using the fact that the
polynomial $f_{1}^{c_{1}}\cdots f_{k}^{c_{k}}-1$ is in $I$ if and only if its
canonical residue class is in $I\mathbb{F}_{p}[x_{1},\dots,x_{n}]$. We can
therefore again apply Remark 5. It remains to handle ideals of the form
$\langle I,p^{e}\rangle$ with $e>1$.

######  Proposition 8.

Let $I$ be an ideal such that $I\cap\mathbb{Z}=\\{0\\}$. Consider the finitely
generated $\mathbb{Z}$-algebra $R=P/I$, and let $f_{1},\dots,f_{k}\in
R^{\times}$. Let $p$ be a prime number, let $e$ be a positive integer, and let
$b_{1},\dots,b_{m}\in\mathbb{Z}^{k}$ be a basis of the exponent lattice
$\Lambda$ of $\left(\bar{f}_{1},\dots,\bar{f}_{k}\right)$ in $P/\langle
I,p^{e}\rangle$. Then the following conditions are equivalent.

  1. (a)

The $\mathbb{Z}$-linear combination $c=a_{1}b_{1}+\cdots+a_{m}b_{m}\in\Lambda$
with $a_{1},\dots,a_{m}\in\mathbb{Z}$ is in the exponent lattice of
$\left(\bar{f}_{1},\dots,\bar{f}_{k}\right)$ in $P/\langle I,p^{e+1}\rangle$.

  2. (b)

The tuple $(a_{1},\dots,a_{m})$ is a solution of the linear equation over
$\mathbb{Z}$ in the indeterminates $y_{1},\dots,y_{m}$ given by

$\bar{h}_{1}y_{1}+\cdots+\bar{h}_{m}y_{m}=0\quad\text{ in }P/\langle
I,p\rangle,$ (i)

where $h_{i}=(f_{1}^{b_{i1}}\cdots f_{k}^{b_{ik}}-1)/p^{e}\in R$ and
$\bar{h}_{i}$ is its residue class modulo $\langle I,p\rangle$.

######  Proof 3.3.

Since all tuples $b_{i}$ are in $\Lambda$ we have $f_{1}^{b_{i1}}\cdots
f_{k}^{b_{ik}}=1$ modulo $\langle I,p^{e}\rangle$. Therefore there exists
$g_{i}\in P$ such that $f_{1}^{b_{i1}}\cdots f_{k}^{b_{ik}}=1+p^{e}g_{i}$ in
$R$ for $i=1,\dots,m$. This shows $h_{i}=g_{i}$. Now the tuple $c$ is in the
exponent lattice of $\left(\bar{f}_{1},\dots,\bar{f}_{k}\right)$ in $P/\langle
I,p^{e+1}\rangle$ if and only if

$f^{c}=f^{a_{1}b_{1}}\cdots
f^{a_{m}b_{m}}=(1+p^{e}g_{1})^{a_{1}}\cdots(1+p^{e}g_{m})^{a_{m}}=1+a_{1}p^{e}g_{1}+\cdots+a_{m}p^{e}g_{m}=1$

in $P/\langle I,p^{e+1}\rangle$. This is equivalent to
$a_{1}\bar{h}_{1}+\cdots+a_{m}\bar{h}_{m}=0$ in $P/\langle I,p\rangle$, which
is satisfied if and only if $(a_{1},\dots,a_{m})$ is a solution of the linear
equation (i).

At this point we are ready to compute the exponent lattice of
$(f_{1},\dots,f_{k})$ modulo an ideal of the form $\langle I,p^{e}\rangle$.
This is achieved by first computing the exponent lattice of
$(f_{1},\dots,f_{k})$ modulo $I\mathbb{F}_{p}[x_{1},\dots,x_{n}]$ and then
iteratively applying Proposition 8 to obtain the exponent lattice modulo
$\langle I,p^{i}\rangle$ for $i=2,\dots,e$.

Let $I=\left\langle x^{2}+x+1,y^{2}+y+1,8\right\rangle$, and consider the
finite $\mathbb{Z}$-algebra $R=\mathbb{Z}[x,y]/I$. For $f_{1}=2x+1$,
$f_{2}=4y+1$ and $f_{3}=-2y-1$ let us compute the exponent lattice of
$\left(\bar{f}_{1},\bar{f}_{2},\bar{f_{3}}\right)$ in $R$. To compute the
exponent lattice modulo $\langle I,2\rangle$ we form the zero-dimensional
$\mathbb{F}_{2}$-algebra $\mathbb{F}_{2}[x,y]/I\mathbb{F}_{2}[x,y]$, and
obtain the exponent lattice $\Lambda_{1}=\mathbb{Z}^{3}$. We then solve the
linear equation in the indeterminates $z_{1},z_{2},z_{3}$ given by
$xz_{1}+2yz_{2}-(y+1)z_{3}=0$ modulo $\langle I,2\rangle$, and obtain the
solution space $M_{1}=\langle(0,1,0),(2,0,0),(0,0,2)\rangle$. Since
$\Lambda_{1}=\mathbb{Z}^{3}$, this yields $\Lambda_{2}=M_{1}$. Then we solve
the linear equation in the indeterminates $z_{1},z_{2},z_{3}$ given by
$yz_{1}-z_{2}-z_{3}=0$ modulo $\langle I,2\rangle$ and obtain the solution
space $M_{2}=\langle b_{1},b_{2},b_{3}\rangle$ with $b_{1}=(0,1,1)$,
$b_{2}=(0,-1,1)$ and $b_{3}=(2,0,0)$. Finally, we compute the exponent lattice

$\Lambda_{3}=\\{c_{1}b_{1}+c_{2}b_{2}+c_{3}b_{3}\mid c\in
M_{2}\\}=\langle(0,2,0),(2,0,2),(-2,0,2)\rangle.$

Combining the previous results we now obtain the following algorithm.

(Computing Exponent Lattices in Finitely Generated $\mathbb{Z}$-Algebras)
Let $R=P/I$ be a $\mathbb{Z}$-algebra, and let $f_{1},\dots,f_{k}\in
R^{\times}$. The following sequence of instructions forms an algorithm which
computes the exponent lattice of $(f_{1},\dots,f_{k})$ in $R$.

1: Compute $I\cap\mathbb{Z}=\langle q\rangle$.

2: if $q=0$ then

3: Using Remark 5, compute the exponent lattice
$\Lambda\subseteq\mathbb{Z}^{k}$ of $(f_{1},\dots,f_{k})$ in the
$\mathbb{Q}$-algebra $\mathbb{Q}\otimes_{\mathbb{Z}}R$.

4: Compute a strong Gröbner basis $\\{g_{1},\dots,g_{\ell}\\}$ of $I$.

5: Let
$N=\operatorname{lcm}(\operatorname{LC}(g_{1}),\dots,\operatorname{LC}(g_{\ell}))$.

6: if $N=1$ then

7: return $\Lambda$

8: else

9: Recursively apply the algorithm to compute the exponent lattice
$M\subseteq\mathbb{Z}^{k}$ of $(f_{1},\dots,f_{k})$ in $P/(I+\langle
N\rangle)$.

10: return $\Lambda\cap M$

11: end if

12: else

13: Compute the prime factorization $q=p_{1}^{e_{1}}\cdots p_{r}^{e_{r}}$.

14: for $i=1,\dots,r$ do

15: Using Remark 5, compute the exponent lattice
$M_{i}\subseteq\mathbb{Z}^{k}$ of $(f_{1},\dots,f_{k})$ in the
$\mathbb{F}_{p}$-algebra $\mathbb{F}_{p}\otimes_{\mathbb{Z}}R$.

16: for $j=1,\dots,e_{i}-1$ do

17: Assume that $M_{i}$ is generated by
$\\{b_{1},\dots,b_{m}\\}\subseteq\mathbb{Z}^{k}$.

18: For $s=1,\dots,m$ form the elements $h_{r}=(f_{1}^{b_{s1}}\cdots
f_{k}^{b_{sk}}-1)/p_{i}^{j}\in R$.

19: Compute the solution space $M^{\prime}\subseteq\mathbb{Z}^{m}$ of the
linear equation over $\mathbb{Z}$ in the indeterminates $y_{1},\dots,y_{m}$
given by  $\bar{h}_{1}y_{1}+\cdots+\bar{h}_{m}y_{m}=0\quad\text{ in }P/\langle
I,p_{i}\rangle.$

20: Replace $M_{i}$ by the lattice
$\\{c_{1}b_{1}+\cdots+c_{m}b_{m}\mid(c_{1},\dots,c_{m})\in
M^{\prime}\\}\subseteq\mathbb{Z}^{k}$.

21: end for

22: end for

23: return the lattice $M_{1}\cap\cdots\cap M_{r}$

24: end if

######  Proof 3.4.

A tuple $a=(a_{1},\dots,a_{k})\in\mathbb{Z}^{k}$ is in the exponent lattice of
$(f_{1},\dots,f_{k})$ if and only if $f_{1}^{a_{1}}\cdots f_{k}^{a_{k}}-1\in
I$. By Proposition 7 we have $I=(I:\langle N\rangle)\cap\langle I,N\rangle$.
In the case $I\cap\mathbb{Z}=\langle 0\rangle$, we have $I:\langle
N\rangle=I\mathbb{Q}[x_{1},\dots,x_{n}]\cap P$ by the same proposition. Line 3
therefore yields the exponent lattice of $(f_{1},\dots,f_{k})$ in
$P/(I:\langle N\rangle)$. It remains to prove that lines 12–24 determine the
exponent lattice of $(f_{1},\dots,f_{k})$ in $P/\langle I,N\rangle$. Since we
have $\langle I,N\rangle=\bigcap_{i=1}^{r}\langle I,p_{i}^{e_{i}}\rangle$, it
is enough to show that lines 15–21 compute the exponent lattice of
$(f_{1},\dots,f_{k})$ in $P/\langle I,p_{i}^{e_{i}}\rangle$. Line 15 yields
the exponent lattice of $(f_{1},\dots,f_{k})$ in $P/\langle I,p_{i}\rangle$.
It then follows from Proposition 8 that the j-th iteration of the for loop in
lines 16–21 correctly computes the exponent lattice of $(f_{1},\dots,f_{k})$
in $P/\langle I,p_{i}^{j+1}\rangle$.

Let us collect some remarks about the implementation of this algorithm.

######  Remark 9.

Suppose we are in the setting of Algorithm 3.

  1. (a)

A non-zero generator $q$ of the ideal $I\cap\mathbb{Z}$ in line 1 is given by
the unique integer contained in a reduced strong Gröbner basis of $I$. If $R$
is a finite $\mathbb{Z}$-algebra, then $q$ is zero if and only if the rank of
$R^{+}$ is non-zero. The rank of an explicitly given finite
$\mathbb{Z}$-algebra can be determined in polynomial time using a Smith normal
form computation.

  2. (b)

As illustrated in Example 3 there can be a proper divisor $M$ of $N$
satisfying $I:\langle M\rangle=I:\langle M\rangle\cap\langle I,M\rangle$. By
determining the smallest number with this property, unnecessary iterations in
the else-branch of this algorithm can be avoided. If $R$ is a finite
$\mathbb{Z}$-algebra, then the smallest number with this property is given by
the torsion exponent of $R$. It can be determined in polynomial time using a
Smith normal form computation if $R$ is explicitly given.

  3. (c)

If $R$ is a finite $\mathbb{Z}$-algebra, then the $\mathbb{Q}$-algebra in line
3 and the $\mathbb{F}_{p}$-algebra in line 15 are zero-dimensional. Exponent
lattices in an explicitly given zero-dimensional $\mathbb{Q}$-algebra can be
computed in polynomial time (see Algorithm 8.3 in [21]). For zero-dimensional
$\mathbb{F}_{p}$-algebras, the problem can be reduced to the discrete
logarithm problem in finite fields (see Algorithm 3.20 in [19]).

  4. (d)

In line 19 we need to compute the solution space of the linear equation over
$\mathbb{Z}$ in the indeterminates $y_{1},\dots,y_{m}$ given by

$g_{1}y_{1}+\cdots+g_{m}y_{m}=0$

in $P/\langle I,p_{i}\rangle$. This can be achieved by checking for all
$(a_{1},\dots,a_{m})\in\mathbb{Z}^{m}$ with $0\leq a_{\ell}\leq p_{i}$ for
$\ell=1,\dots,m$ whether $a_{1}g_{1}+\cdots+a_{m}g_{m}\in\langle
I,p_{i}\rangle$. Alternatively, one can perform a syzygy calculation using
Gröbner basis techniques. In particular, for large $p_{i}$, this might be more
efficient. If $R$ is an explicitly given finite $\mathbb{Z}$-algebra, we can
use [20, Prop. 2.6] to solve this linear equation efficiently.

The following example illustrates how Algorithm 3 can be applied to compute
exponent lattices in finite $\mathbb{Z}$-algebras.

Let $I=\left\langle x^{2}+x+1,\,y^{2}+y+1,\,6z^{2},\,z^{3}\right\rangle$, and
consider the finite $\mathbb{Z}$-algebra $R=\mathbb{Z}[x,y,z]/I$. Let
$f_{1}=-xyz-xz+1$, $f_{2}=y+1$ and $f_{3}=xy+x+y+1$. We apply Algorithm 3 to
compute the exponent lattice of
$\left(\bar{f}_{1},\bar{f}_{2},\bar{f}_{3}\right)$ in $R$.

  1. 1:

Since $R$ is a finite $\mathbb{Z}$-algebra, we compute its rank given by 8.

  2. 2:

The rank of $R$ is non-zero, which implies $I\cap\mathbb{Z}=\langle 0\rangle$.

  3. 3:

Using Remark 5, we compute the exponent lattice
$\Lambda=\langle(0,6,0),(0,0,3)\rangle$ in the zero-dimensional
$\mathbb{Q}$-algebra $\mathbb{Q}\otimes_{\mathbb{Z}}R$.

  4. 4,5:

Since $R$ is a finite $\mathbb{Z}$-algebra, we compute its torsion exponent
given by 6.

  5. 9:

We recursively apply the Algorithm to compute the exponent lattice of
$\left(\bar{f}_{1},\bar{f}_{2},\bar{f}_{3}\right)$ in $P/\langle I,6\rangle$.

  6. 1:

We have $q=6$.

  7. 13:

We determine the factorization $6=2\cdot 3$.

  8. 15:

Using Remark 5, we compute generators $(4,0,0)$, $(0,3,0)$ and $(0,0,3)$ of
the exponent lattice $M_{1}$ of
$\left(\bar{f}_{1},\bar{f}_{2},\bar{f}_{3}\right)$ modulo
$I\mathbb{F}_{2}[x,y,z]$ and generators $(3,0,0)$, $(0,6,0)$, and $(0,0,3)$ of
the exponent lattice $M_{2}$ modulo $I\mathbb{F}_{3}[x,y,z]$.

  9. 20:

The exponent lattice of $\left(\bar{f}_{1},\bar{f}_{2},\bar{f}_{3}\right)$ in
$R$ is given by $\Lambda\cap M_{1}\cap M_{2}=\langle(0,6,0),(0,0,3)\rangle$.

It is an open question to what extent Algorithm 3 can be generalized to the
non-commutative case. A straightforward generalization does not seem to be
possible, since in the non-commutative case exponent lattices are in general
not computable. This follows from the fact that the subgroup membership
problem is undecidable for $4\times 4$ integral matrices (see [23]).

##  4\. The Unit Group of Reduced Finite $\mathbb{Z}$-Algebras

Let us begin by considering the case of integral finite $\mathbb{Z}$-algebras,
i.e, algebras of the form $P/\mathfrak{p}$ where $\mathfrak{p}$ is a prime
ideal in $P$.

######  Remark 10.

(Computing the Unit Group of Integral Finite $\mathbb{Z}$-Algebras)
Let $\mathfrak{p}$ be a prime ideal in $P$ such that $R=P/\mathfrak{p}$ is a
finite $\mathbb{Z}$-algebra.

  1. (a)

If $\mathfrak{p}\cap\mathbb{Z}=\langle 0\rangle$, then
$K=\mathbb{Q}\otimes_{\mathbb{Z}}R$ is a number field. Since $P/\mathfrak{p}$
is integral over $\mathbb{Z}$ and its rank equals $\dim_{\mathbb{Q}}(K)$, the
ring $R$ is an order in $K$. Generators of the unit group of $R$ can therefore
be computed using for example the algorithms given in [6] or [3]. These
algorithms require that the field $K$ is given by a primitive element. Such an
element can be determined using one of the methods described in [29] or
Algorithm 6.3 in [21].

  2. (b)

If $\mathfrak{p}\cap\mathbb{Z}=\langle p\rangle$ for a prime number $p$, then
$P/\mathfrak{p}$ is isomorphic to the finite field
$K=\mathbb{F}_{p}\otimes_{\mathbb{Z}}R$. The problem therefore reduces to
computing a primitive root of $K$. Algorithms for this task can be found in
[25] or in [8].

Let us now consider the case of a reduced finite $\mathbb{Z}$-algebra $R=P/I$.
If $I\cap\mathbb{Z}=\langle n\rangle$ for some
$n\in\mathbb{Z}\setminus\\{0\\}$, then the minimal prime ideals of $R$ are
maximal ideals and therefore pairwise coprime. By the Chinese Remainder
Theorem computing the unit group then reduces to the case discussed above. If
$I\cap\mathbb{Z}=\langle 0\rangle$, then the minimal prime ideals of $R$ need
not be pairwise coprime.

Consider the ideal $I=\langle x^{2}+x+1,y^{2}+y+1\rangle$. Its minimal prime
ideals are given by $\mathfrak{p}_{1}=\langle x-y,y^{2}+y+1\rangle$ and
$\mathfrak{p}_{2}=\langle x+y+1,y^{2}+y+1\rangle$ and we have
$\mathfrak{p}_{1}+\mathfrak{p}_{2}=\langle x+2,y+2,3\rangle$.

This example demonstrates that we cannot directly reduce to the integral case.
Instead we notice that if $R$ is torsion-free then $R$ is an order in the
reduced zero-dimensional $\mathbb{Q}$-algebra
$\mathbb{Q}\otimes_{\mathbb{Z}}R$.

Let $A$ be a zero-dimensional reduced $\mathbb{Q}$-algebra. A subring
$\mathcal{O}$ of $A$ is called an order if there is a basis
$a_{1},\dots,a_{m}$ of $A$ such that
$\mathcal{O}=\mathbb{Z}a_{1}+\cdots+\mathbb{Z}a_{m}$.

The unit group of an order in a zero-dimensional reduced $\mathbb{Q}$-algebra
can be computed using the algorithm presented in Section 3 of [10]. In the
following we present a modified version of this algorithm.

######  Lemma 11.

Let $A$ be a reduced zero-dimensional $\mathbb{Q}$-algebra, and let
$e_{1},e_{2}$ be orthogonal idempotents with $e_{1}+e_{2}=1$. Let
$\mathcal{O}$ be an order in $A$. Consider the ideal
$J=(e_{1}\mathcal{O}\cap\mathcal{O})+(e_{2}\mathcal{O}\cap\mathcal{O})$ and
form the ring $S=\mathcal{O}/J$. Consider the ring homomorphisms
$\varphi_{i}:e_{i}\mathcal{O}\rightarrow S$ given by $\varphi_{i}(e_{i}a)=a+J$
for $a\in\mathcal{O}$. Then we have

$\mathcal{O}=\\{a_{1}+a_{2}\mid a_{i}\in e_{i}\mathcal{O}\text{ and
}\varphi_{1}(a_{1})=\varphi_{2}(a_{2})\\}$

######  Proof 4.1.

See [10], Lemma 3.1.

Given an order $\mathcal{O}$ in a reduced zero-dimensional
$\mathbb{Q}$-algebra $A$ and primitive idempotents $e_{1},\dots,e_{k}$ of $A$,
we can compute generators of $(e_{i}\mathcal{O})^{\times}$ since
$e_{i}\mathcal{O}$ is an order in the number field $e_{i}A$. We can then
iteratively apply Lemma 11 to determine $\mathcal{O}^{\times}$.

(Computing the Unit Group of an Order)
Let $A$ be a reduced zero-dimensional $\mathbb{Q}$-algebra, and let
$\mathcal{O}$ be an order in $A$. The following instructions form an algorithm
which computes a set of generators of $\mathcal{O}^{\times}$.

1: Compute the primitive idempotents $e_{1},\dots,e_{m}$ of $A$.

2: Compute $U=(e_{1}\mathcal{O})^{\times}$.

3: for $j=2,\dots,m$ do

4: Set $f=e_{1}+\cdots+e_{j-1}$.

5: Compute generators of $f\mathcal{O}\cap\mathcal{O}$ and
$e_{j}\mathcal{O}\cap\mathcal{O}$ and form the ideal
$J=(f\mathcal{O}\cap\mathcal{O})+(e_{j}\mathcal{O}\cap\mathcal{O})$ in
$\mathcal{O}$.

6: Compute generators $e_{j}h_{1},\dots,e_{j}h_{\ell}$ of
$(e_{j}\mathcal{O})^{\times}$.

7: Assume that $U=\\{fg_{1},\dots,fg_{k}\\}$.

8: Compute a set of generators $B\subseteq\mathbb{Z}^{k+\ell}$ of the exponent
lattice $\Lambda$ of the tuple
$\left(g_{1},\dots,g_{k},h_{1}^{-1},\dots,h_{\ell}^{-1}\right)$ in
$\mathcal{O}/J$.

9: Set $U=\left\\{fg_{1}^{b_{1}}\cdots
g_{k}^{b_{k}}+e_{j}h_{1}^{b_{k+1}}\cdots h_{\ell}^{b_{k+\ell}}\mid b\in
B\right\\}$.

10: end for

11: return $U$.

######  Proof 4.2.

It suffices to show that after the $j$-th iteration $U$ generates the unit
group of the order $(e_{1}+\cdots+e_{j})\mathcal{O}$ in
$(e_{1}+\cdots+e_{j})A$. Let $r\in\mathcal{O}$ and consider the group
homomorphisms $\varphi_{f}:f\mathcal{O}\rightarrow\mathcal{O}/J$ given by
$\varphi_{f}(fr)=r+J$ and
$\varphi_{e_{j}}:e_{j}\mathcal{O}\rightarrow\mathcal{O}/J$ given by
$\varphi_{e_{j}}(e_{j}r)\mapsto r+J$. Let $g=fg_{1}^{c_{1}}\cdots
g_{k}^{c_{k}}$ in $U$ and $h=e_{j}h_{1}^{c_{k+1}}\cdots h_{\ell}^{c_{k+\ell}}$
in $(e_{j}\mathcal{O})^{\times}$. Then by Lemma 11 the element $g-h$ is in the
unit group of $(e_{1}+\cdots+e_{j})\mathcal{O}$ if and only if

$\varphi_{f}(g)=g_{1}^{c_{1}}\cdots g_{k}^{c_{k}}+J=h_{1}^{c_{k+1}}\cdots
h_{\ell}^{c_{k+\ell}}+J=\varphi_{e_{j}}(e_{j}h).$

This is equivalent to $(c_{1},\dots,c_{k+\ell})\in\Lambda$.

Let $R=P/I$ be a finite $\mathbb{Z}$-algebra. If $R$ is torsion-free and
reduced, then it is an order in the zero-dimensional $\mathbb{Q}$-algebra
$A=\mathbb{Q}\otimes_{\mathbb{Z}}R$. Consequently, Algorithm 4 can be applied
to compute the unit group of the order $R$ in $A$. In this case the steps of
this algorithm can be performed as follows.

######  Lemma 12.

Let $R=P/I$ be a reduced torsion-free finite $\mathbb{Z}$-algebra, and let
$\mathfrak{p}_{1},\dots,\mathfrak{p}_{m}$ be the minimal prime ideals of $I$.

  1. (a)

The $\mathbb{Q}$-algebra $A=\mathbb{Q}\otimes_{\mathbb{Z}}R$ is zero-
dimensional and its maximal ideals are given by
$\mathfrak{m}_{i}=\mathfrak{p}_{i}\mathbb{Q}[x_{1},\dots,x_{n}]$ for
$i=1,\dots,m$. We can therefore compute elements $q_{i}\in\bigcap_{i\neq
j}\mathfrak{m}_{j}$ and $p_{i}\in\mathfrak{m}_{i}$ such that $q_{i}+p_{i}=1$.
Then the residue classes $\bar{q}_{1},\dots,\bar{q}_{m}$ in $A$ are the
primitive idempotents of $A$.

  2. (b)

The ideal $\bar{q}_{i}R$ in $A$ is isomorphic to
$\bar{q}_{i}(P/\mathfrak{p}_{i})$.

  3. (c)

We have $\bar{q}_{i}R\cap R=\bigcap_{j\neq i}\mathfrak{p}_{i}/I$.

  4. (d)

For $f=\sum_{i\neq j}q_{i}$ we have $\bar{f}R\cap R=\mathfrak{p}_{j}/I$.

######  Proof 4.3.

Part (a) is a direct consequence of the Chinese Remainder Theorem (see Lemma
3.7.4 in [17]), and (b) follows from the fact that $\bar{q}_{i}A$ is
isomorphic to $A/\mathfrak{m}_{i}$.

To prove (c), we notice that the ideal $\bar{q}_{i}R\cap R$ is contained in
the right-hand side, since $q_{i}\in\bigcap_{i\neq j}\mathfrak{m}_{j}$. To
show the opposite inclusion, let $f\in P$ such that $\bar{f}\in\bigcap_{i\neq
j}\mathfrak{p}_{j}/I$. Then we have $f=q_{i}f+p_{i}f$. Since
$p_{i}\in\mathfrak{m}_{i}$, this implies
$p_{i}f\in\bigcap_{i=1,\dots,m}\mathfrak{p}_{i}=I$. Hence we get
$\bar{f}=\bar{q}_{i}\bar{f}\in\bar{q}_{i}R\cap R$. Part (d) follows
analogously.

Using these observations, we can adapt Algorithm 4 as follows.

######  Corollary 13.

(Computing the Unit Group of a Reduced Torsion-Free Finite
$\mathbb{Z}$-Algebra)
Let $R=P/I$ be a reduced torsion-free finite $\mathbb{Z}$-algebra. The
following instructions form an algorithm which computes a set of polynomials
such that their residue classes generate $R^{\times}$.

1: Compute the minimal prime ideals $\mathfrak{p}_{1},\dots,\mathfrak{p}_{m}$
of $I$.

2: for $i=1,\dots,m$ do

3: Compute elements $q_{i}\in\bigcap_{i\neq
j}\mathfrak{p}_{j}\mathbb{Q}[x_{1},\dots,x_{n}]$ and
$p_{i}\in\mathfrak{p}_{i}\mathbb{Q}[x_{1},\dots,x_{n}]$ such that
$q_{i}+p_{i}=1$.

4: end for

5: Using Remark 10, compute a set of polynomials $U$ such that their residue
classes generate $(P/\mathfrak{p}_{1})^{\times}$.

6: for $j=2,\dots,m$ do

7: Form the ideal $J=\bigcap_{1\leq i\leq
j-1}\mathfrak{p}_{i}+\mathfrak{p}_{j}$.

8: Using Remark 10, compute polynomials $h_{1},\dots,h_{\ell}$ such that their
residue classes generate $(P/\mathfrak{p}_{j})^{\times}$.

9: Assuming $U=\\{g_{1},\dots,g_{k}\\}$, compute a set of generators
$B\subseteq\mathbb{Z}^{k+\ell}$ of the exponent lattice of
$\left(\bar{g}_{1},\dots,\bar{g}_{k},\bar{h}_{1}^{-1},\dots,\bar{h}_{\ell}^{-1}\right)$
in $P/J$.

10: Set $U=\left\\{fg_{1}^{b_{1}}\cdots
g_{k}^{b_{k}}+q_{j}h_{1}^{b_{k+1}}\cdots h_{\ell}^{b_{k+\ell}}\mid b\in
B\right\\}$ where $f=q_{1}+\cdots+q_{j-1}$.

11: end for

12: return $U$.

######  Proof 4.4.

Since $R$ is torsion-free and reduced, it is an order in the zero-dimensional
$\mathbb{Q}$-algebra $\mathbb{Q}\otimes_{\mathbb{Z}}R$. Now we show that the
steps of this algorithm correspond to the steps of Algorithm 4.

Assume that at the start of the $j$-th iteration of the for-loop in lines 6–11
the residue classes of the elements in $U$ generate the unit group of
$R_{j-1}=P/(\mathfrak{p}_{1}\cap\cdots\cap\mathfrak{p}_{j-1})$. Consider the
finite $\mathbb{Z}$-algebra
$R_{j}=P/(\mathfrak{p}_{1}\cap\cdots\cap\mathfrak{p}_{j})$. The residue
classes of the elements $f=q_{1}+\cdots+q_{j-1}$ and $q_{j}$ form orthogonal
idempotents in $\mathbb{Q}\otimes_{\mathbb{Z}}R_{j}$ with
$\bar{f}+\bar{q}_{j}=1$. By Lemma 12.b we then have
$\bar{q}_{j}R_{j}\cong\bar{q}_{j}(P/\mathfrak{p}_{j})$ and
$\bar{f}R_{j}\cong\bar{f}R_{j-1}$. Furthermore Lemma 12.c yields
$\bar{q}_{j}R_{j}\cap
R_{j}=(\mathfrak{p}_{1}\cap\cdots\cap\mathfrak{p}_{j-1})/I$ and
$\bar{f}R_{j}\cap R_{j}=\mathfrak{p}_{j}/I$. This shows that the ideal $J$ in
line 7 corresponds to the ideal $J$ in line 5 of Algorithm 4.

Let us apply this algorithm to a concrete example.

Let $I=\left\langle x^{2}+x+1,y^{2}+y+1,z^{2}+z+1\right\rangle$, and consider
the finite $\mathbb{Z}$-algebra $R=\mathbb{Z}[x,y,z]/I$. We follow the steps
of Corollary 13 to compute generators of $R^{\times}$.

  1. 1:

We compute the minimal prime ideals of $I$ and obtain

$\displaystyle\mathfrak{p}_{1}$ $\displaystyle=\left\langle
y-z,x+z+1,z^{2}+z+1\right\rangle$ $\displaystyle\mathfrak{p}_{2}$
$\displaystyle=\left\langle y-z,x-z,z^{2}+z+1\right\rangle$
$\displaystyle\mathfrak{p}_{3}$ $\displaystyle=\left\langle
y+z+1,x+z+1,z^{2}+z+1\right\rangle$ $\displaystyle\mathfrak{p}_{4}$
$\displaystyle=\left\langle y+z+1,x-z,z^{2}+z+1\right\rangle$

  2. 2–4:

We compute the primitive idempotents

$\displaystyle e_{1}$
$\displaystyle=1/3\bar{x}\bar{y}+1/3\bar{x}\bar{z}-1/3\bar{y}\bar{z}+1/3\bar{x}+1/3$
$\displaystyle e_{2}$
$\displaystyle=-1/3\bar{x}\bar{y}-1/3\bar{x}\bar{z}-1/3\bar{y}\bar{z}-1/3\bar{x}-1/3\bar{y}-1/3\bar{z}$
$\displaystyle e_{3}$
$\displaystyle=-1/3\bar{x}\bar{y}+1/3\bar{x}\bar{z}+1/3\bar{y}\bar{z}+1/3\bar{z}+1/3$
$\displaystyle e_{4}$
$\displaystyle=1/3\bar{x}\bar{y}-1/3\bar{x}\bar{z}+1/3\bar{y}\bar{z}+1/3\bar{y}+1/3$

of the zero-dimensional $\mathbb{Q}$-algebra
$\mathbb{Q}\otimes_{\mathbb{Z}}R$.

  3. 5:

Using Remark 10, we determine a set of generators $U=\\{\bar{z}+1\\}$ of
$(R/\mathfrak{p}_{1})^{\times}$.

  4. 7:

Form the ideal $J=\mathfrak{p}_{1}+\mathfrak{p}_{2}=\langle
x+1,y+2,z+2,3\rangle$.

  5. 8:

Using Remark 10, we compute
$(R/\mathfrak{p}_{2})^{\times}=\langle\bar{z}+1\rangle$.

  6. 9:

Using Remark 5, we compute generators $(1,1)$ and $(0,2)$ of the exponent
lattice of $(\bar{z}+1,(\bar{z}+1)^{-1})$ in the finite field $R/J$.

  7. 10:

Compute $e_{1}(\bar{z}+1)+e_{2}(\bar{z}+1)=\bar{z}+1$ and
$e_{1}+e_{2}(\bar{y}+1)^{2}=-\bar{y}\bar{z}-\bar{y}$ and set
$U=\\{\bar{z}+1,-\bar{y}\bar{z}-\bar{y}\\}$.

  8. 7:

Form the ideal
$J=(\mathfrak{p}_{1}\cap\mathfrak{p}_{2})+\mathfrak{p}_{3}=\langle
x+2,y+2,z+2,3\rangle$.

  9. 8:

Using Remark 10, we compute
$(R/\mathfrak{p}_{2})^{\times}=\langle\bar{z}+1\rangle$.

  10. 9:

Using Remark 5, we compute generators $(1,0,1)$, $(0,1,0)$ and $(0,0,2)$ of
the exponent lattice of $(\bar{z}+1,-\bar{y}\bar{z}-\bar{y},(\bar{z}+1)^{-1})$
in $R/J$.

  11. 10:

Set
$U=\\{\bar{z}+1,-\bar{y}\bar{z}-\bar{y},\bar{x}\bar{z}+\bar{x}+\bar{z}+1\\}$.

  12. 7:

Form the ideal
$J=(\mathfrak{p}_{1}\cap\mathfrak{p}_{2}\cap\mathfrak{p}_{3})+\mathfrak{p}_{4}=\langle
z^{2}+z+1,x+2z,y+z+1,3\rangle$.

  13. 8:

Using Remark 10, we compute
$(R/\mathfrak{p}_{2})^{\times}=\langle\bar{z}+1\rangle$.

  14. 9:

Using Remark 5, we compute generators $(1,0,0,1)$, $(0,1,0,2)$, $(0,0,1,2)$
and $(0,0,0,6)$ of the exponent lattice in $R/J$ of

$\left(\bar{z}+1,-\bar{y}\bar{z}-\bar{y},\bar{x}\bar{z}+\bar{x}+\bar{z}+1,(\bar{z}+1)^{-1}\right).$

  15. 10:

Set
$U=\\{\bar{z}+1,-\bar{y}\bar{z}-\bar{y},\bar{x}\bar{z}+\bar{x}+\bar{z}+1,1\\}$.

  16. 12:

The algorithm returns the generators
$\bar{z}+1,-\bar{y}\bar{z}-\bar{y},\bar{x}\bar{z}+\bar{x}+\bar{z}+1$ of
$R^{\times}$.

A reduced finite $\mathbb{Z}$-algebra need not be torsion-free, but we can
decompose it into a direct product of finitely many finite fields and a
torsion-free algebra.

######  Lemma 14.

Let $R$ be a reduced finite $\mathbb{Z}$-algebra. Let
$\mathfrak{p}_{1},\dots,\mathfrak{p}_{r}$ be the minimal prime ideals of $R$
of height $n$, let $\mathfrak{m}_{1},\dots,\mathfrak{m}_{s}$ be the maximal
ideals of $R$, and let $J=\mathfrak{p}_{1}\cap\cdots\cap\mathfrak{p}_{r}$.
Then $R/J$ is torsion-free and we have $R\cong R/J\times
R/\mathfrak{m}_{1}\times\cdots\times R/\mathfrak{m}_{s}$.

######  Proof 4.5.

As a reduced ring, $R$ does not have embedded prime ideals. Therefore $J$ is
not contained in any $\mathfrak{m}_{i}$. Since
$\mathfrak{m}_{1},\dots,\mathfrak{m}_{s}$ are maximal ideals the isomorphism
follows directly by the Chinese Remainder Theorem. To prove that $R/J$ is
torsion-free, we note that the prime ideals $\mathfrak{p}_{i}$ satisfy
$\mathfrak{p}_{i}\mathbb{Q}[x_{1},\dots,x_{n}]\cap P$. Now let $f\in P$ and
assume there exists $k\in\mathbb{Z}\setminus\\{0\\}$ with $kf\in J$. Then we
have $kf\in\mathfrak{p}_{i}$ and by the above observation
$f\in\mathfrak{p}_{i}$ for all $i=1,\dots,k$. This shows $f\in J$.

Thus we can now combine our results and obtain the following algorithm.

(Computing the Unit Group of a Reduced Finite $\mathbb{Z}$-Algebra) Let
$R=P/I$ be a reduced finite $\mathbb{Z}$-algebra. The following instructions
form an algorithm which computes generators of the unit group $R^{\times}$.

1: Let $G=[\;]$.

2: Compute the prime decomposition
$I=\mathfrak{p}_{1}\cap\cdots\cap\mathfrak{p}_{r}\cap\mathfrak{m}_{1}\cap\cdots\cap\mathfrak{m}_{s}$
where $\mathfrak{p}_{1},\dots,\mathfrak{p}_{r}$ are prime ideals of height $n$
and $\mathfrak{m}_{1},\dots,\mathfrak{m}_{s}$ are maximal ideals.

3: Compute $J=\mathfrak{p}_{1}\cap\cdots\cap\mathfrak{p}_{r}$.

4: Apply Algorithm 4 to compute a set of polynomials $H$ such that their
residue classes generate the unit group of the order $P/J$ in
$\mathbb{Q}[x_{1},\dots,x_{n}]/J\mathbb{Q}[x_{1},\dots,x_{n}]$.

5: Using the Chinese Remainder Theorem, compute $e_{1},\dots,e_{s+1}\in P$
such that their residue classes form orthogonal idempotents of $R$ with
$R\cong\bar{e}_{1}R\times\cdots\times\bar{e}_{s+1}R$ and $\bar{e}_{i}R\cong
P/\mathfrak{m}_{i}$ for $i=1,\dots,s$ and $\bar{e}_{s+1}R\cong P/J$.

6: for all $h\in H$ do

7: Add $\bar{e}_{s+1}\bar{h}+\sum_{i=1}^{s}\bar{e}_{i}$ to $G$.

8: end for

9: for $i=1,\dots,s$ do

10: Using Remark 10, compute $g_{i}\in P$ such that $\bar{g}_{i}$ generates
$(P/\mathfrak{m}_{i})^{\times}$.

11: Add $\bar{e}_{i}\bar{g}_{i}+\sum_{j\neq i}\bar{e}_{j}$ to $G$.

12: end for

13: return $G$.

######  Proof 4.6.

By Lemma 14, we have
$R^{\times}\cong(P/J)^{\times}\times(P/\mathfrak{m}_{1})^{\times}\times\cdots\times(P/\mathfrak{m}_{s})^{\times}$,
and $P/J$ is torsion-free. This shows that the units in $R$ are given by the
residue classes of elements of the form
$e_{1}f_{1}+\cdots+e_{s}f_{s}+e_{s+1}g$ where $\bar{f}_{i}$ is a unit in
$(P/\mathfrak{m}_{i})$ and $\bar{h}$ is a unit in $(P/J)$. We therefore
conclude that the elements computed in line 7 and in line 11 generate
$R^{\times}$.

As noted in Remark 4, the computations in lines 2, 3 and 5 can be performed
efficiently if $R$ is explicitly given.

Consider the reduced finite $\mathbb{Z}$-algebra $R=\mathbb{Z}[x,y,z]/I$ where

$I=\left\langle 3x,\,xz-x,\,y^{2}+z,\,x^{2}+xy,\,z^{3}-1\right\rangle.$

Let us apply Algorithm 4 to compute generators of $R^{\times}$.

  1. 1:

Set $G=[\;]$.

  2. 2:

We compute the minimal prime ideals of $I$ and obtain
$\mathfrak{p}_{1}=\langle z-1,x,y^{2}+1\rangle$, $\mathfrak{p}_{2}=\langle
x,z^{2}+z+1,y^{2}+z\rangle$ and $\mathfrak{m}=\langle
3,z-1,x+y,y^{2}+1\rangle$.

  3. 3:

Compute $J=\mathfrak{p}_{1}\cap\mathfrak{p}_{2}$.

  4. 4:

Using Algorithm 4, we obtain the following generators of $(P/J)^{\times}$.

$\displaystyle h_{1}$
$\displaystyle=9\bar{y}\bar{z}^{2}-17\bar{y}\bar{z}-15\bar{z}^{2}+9\bar{y}+15\bar{z}$
$\displaystyle h_{2}$
$\displaystyle=15\bar{y}\bar{z}+9\bar{z}^{2}-15\bar{y}-17\bar{z}+9$
$\displaystyle h_{3}$
$\displaystyle=-56\bar{y}\bar{z}-32\bar{z}^{2}+56\bar{y}+65\bar{z}-32$

  5. 5:

Determine orthogonal idempotents $e_{1}=\bar{x}\bar{y}+\bar{y}^{2}+\bar{z}$
and $e_{2}=-\bar{x}\bar{y}+1$ of $R$ such that $e_{1}+e_{2}=1$, $e_{1}R\cong
P/\mathfrak{m}$ and $e_{2}R\cong P/J$.

  6. 7:

Add $e_{1}+e_{2}h_{1}$, $e_{1}+e_{2}h_{2}$ and $e_{1}+e_{2}h_{3}$ to $G$.

  7. 10:

Using Remark 10, we compute a generator $g=\bar{y}+1$ of
$(P/\mathfrak{m})^{\times}$.

  8. 11:

Add $e_{1}g+e_{2}$ to $G$.

  9. 13:

The generators of $R^{\times}$ are given by

$\displaystyle e_{1}+e_{2}h_{1}$
$\displaystyle=9\bar{y}\bar{z}^{2}+\bar{x}\bar{y}-17\bar{y}\bar{z}-15\bar{z}^{2}+\bar{x}+9\bar{y}+15\bar{z}$
$\displaystyle e_{1}+e_{2}h_{2}$
$\displaystyle=15\bar{y}\bar{z}+9\bar{z}^{2}-15\bar{y}-17\bar{z}+9$
$\displaystyle e_{1}+e_{2}h_{3}$
$\displaystyle=-56\bar{y}\bar{z}-32\bar{z}^{2}+56\bar{y}+65\bar{z}-32$
$\displaystyle e_{1}g+e_{2}$ $\displaystyle=-\bar{x}+1.$

##  5\. The Unit Group of Non-Reduced Finite $\mathbb{Z}$-Algebras

Using the results of the previous section, in particular Algorithm 4, we can
now compute generators of the unit group of $R/\operatorname{Rad}(0)$. The
next task is to lift these generators to a generating set of $R^{\times}$.

######  Lemma 15.

Let $R$ be a finite $\mathbb{Z}$-algebra.

  1. (a)

The canonical homomorphism $\varphi\colon R\rightarrow
R/\operatorname{Rad}(0)$ induces a surjective group homomorphism
$\varphi^{\times}\colon
R^{\times}\rightarrow(R/\operatorname{Rad}(0))^{\times}$.

  2. (b)

The kernel of $\varphi^{\times}$ is given by $1+\operatorname{Rad}(0)$.

######  Proof 5.1.

See [22], Lemma 1.1.5.

This lemma shows
$R^{\times}/(1+\operatorname{Rad}(0))\cong(R/\operatorname{Rad}(0))^{\times}$.
Therefore, if we have generators of $(R/\operatorname{Rad}(0))^{\times}$ and
generators of $1+\operatorname{Rad}(0)$, we obtain generators of $R^{\times}$
using the following well-known result.

######  Remark 16.

Let $M$ be a $\mathbb{Z}$-module and $N\subseteq M$ a submodule. Assume that
the residue classes of $m_{1},\dots,m_{k}\in M$ generate $M/N$, and let $N$ be
generated by $n_{1},\dots,n_{\ell}$. Then
$m_{1},\dots,m_{k},n_{1},\dots,n_{\ell}$ generate $M$.

Since we already saw how to determine generators of
$R/\operatorname{Rad}(0)^{\times}$, it remains to compute generators of
$1+\operatorname{Rad}(0)$. If $\operatorname{Rad}(0)^{2}=0$, then elements
$1+f,1+g$ of $1+\operatorname{Rad}(0)$ satisfy $(1+f)(1+g)\equiv 1+f+g$. In
this case generators of the additive group of $\operatorname{Rad}(0)$
immediately yield generators of $1+\operatorname{Rad}(0)$. If the nilpotency
index of $\operatorname{Rad}(0)$ is greater than 2, we can inductively compute
generators of $1+\operatorname{Rad}(0)^{i-1}$ in
$R/\operatorname{Rad}(0)^{i}$.

(Computing Generators of the Unit Group)
Let $R=P/I$ be a finite $\mathbb{Z}$-algebra. The following instructions form
an algorithm which computes generators of the unit group $R^{\times}$.

1: Let $G=[\;]$.

2: Compute the nilradical $\operatorname{Rad}(0)$ of $R$.

3: Apply Algorithm 4 to compute elements in $R$ such that their residue
classes generate the unit group of $R/\operatorname{Rad}(0)$. Add these
elements to $G$.

4: Compute the nilpotency index $s$ of $\operatorname{Rad}(0)$ in $R$.

5: for $i=2,\dots,s$ do

6: Compute $f_{1},\dots,f_{\ell}\in R$ such that the residue classes
$\bar{f}_{1},\dots,\bar{f}_{\ell}$ in $R/\operatorname{Rad}(0)^{i}$ generate
$1+\operatorname{Rad}(0)^{i-1}$.

7: Add $f_{1},\dots,f_{\ell}$ to $G$.

8: end for

9: return $G$.

######  Proof 5.2.

After line 3 has been executed, the list $G$ contains generators of the unit
group of $R/\operatorname{Rad}(0)$. Now assume that the elements in $G$
generate $R/\operatorname{Rad}(0)^{i-1}$ after iteration number $i-1$ of lines
5–8. By Lemma 15, the group homomorphism

$\varphi_{i}^{\times}\colon\left(R/\operatorname{Rad}(0)^{i-1}\right)^{\times}\rightarrow\left(R/\operatorname{Rad}(0)^{i}\right)^{\times}$

is surjective and its kernel is given by $1+\operatorname{Rad}(0)^{i-1}$. This
implies

$\left(R/\operatorname{Rad}(0)^{i-1}\right)^{\times}/\left(1+\operatorname{Rad}(0)^{i-1}\right)\cong\left(R/\operatorname{Rad}(0)^{i}\right)^{\times}.$

The generators of $R/\operatorname{Rad}(0)^{i-1}$ together with the generators
of $1+\operatorname{Rad}(0)^{i-1}$ therefore generate
$\left(R/\operatorname{Rad}(0)^{i}\right)^{\times}$. Hence, after iteration
number $s$, the list $G$ contains generators of
$\left(R/\operatorname{Rad}(0)^{s}\right)^{\times}=R^{\times}$.

The loop in lines 5–8 can be avoided as follows.

######  Lemma 17.

Let $R=P/I$ be a finite $\mathbb{Z}$-algebra, and let
$\mathcal{G}=\mathbb{T}^{n}\setminus L$ be a set of terms as in Lemma 2 such
that the residue classes of the elements in $\mathcal{G}$ generate $R^{+}$.
Let $f_{1},\dots,f_{k}\in P$ such that their residue classes generate
$\operatorname{Rad}(0)$. Then $\mathcal{H}=\left\\{1+\bar{t}\bar{f}_{i}\mid
i=1,\dots,k,\;t\in\mathcal{G}\right\\}$ generates $1+\operatorname{Rad}(0)$.

######  Proof 5.3.

Clearly, $\mathcal{H}$ is contained in $1+\operatorname{Rad}(0)$. By the proof
of Algorithm 5, it is then enough to show that there are $g_{1},\dots,g_{s}\in
H$ such that the4 residue classes $\bar{g}_{1},\dots,\bar{g}_{s}$ in
$R/\operatorname{Rad}(0)^{i}$ generate $1+\operatorname{Rad}(0)^{i-1}$. Every
element in $\operatorname{Rad}(0)^{i-2}$ can be written as a
$\mathbb{Z}$-linear combination of the residue classes of the terms in
$\mathcal{G}$. Thus, every element in $\operatorname{Rad}(0)^{i-1}$ can be
written as a $\mathbb{Z}$-linear combination of the terms in
$\left\\{\bar{t}\bar{f}_{i}\mid i=1,\dots,k,\;t\in\mathcal{G}\right\\}$. The
claim now follows from the fact that
$(1+\bar{f})(1+\bar{g})=1+\bar{f}+\bar{g}$ for
$f,g\in\operatorname{Rad}(0)^{i-1}$, since $fg\in\operatorname{Rad}(0)^{i}$.

Let us apply Algorithm 5, together with this simplification, to a concrete
example.

Consider the finite $\mathbb{Z}$-algebra $R=\mathbb{Z}[x,y]/I$, where
$I=\left\langle x^{3},6x^{2},y^{2}+y+1\right\rangle$.

  1. 1:

Let $G=[\;]$.

  2. 2:

Compute
$\operatorname{Rad}(0)=\left\langle\bar{x},\bar{y}^{2}+\bar{y}+1\right\rangle$.

  3. 3:

Using Algorithm 4, we compute
$(R/\operatorname{Rad}(0))^{\times}=\langle\bar{y}+1\rangle$ and add
$\bar{y}+1$ to $G$.

  4. 4-8:

Using Lemma 2, we determine $\mathbb{Z}$-module generators
$\mathcal{G}=\left\\{\bar{x}^{2}\bar{y},\bar{x}\bar{y},\bar{y},\bar{x}^{2},\bar{x},1\right\\}$
of $R$. Then for every generator $g$ of $\operatorname{Rad}(0)$ and for every
term $t\in\mathcal{G}$ we calculate $1+\operatorname{NF}_{\sigma,I}(tg)$ and
obtain generators
$1+\bar{x},1+\bar{x}^{2},1+\bar{x}\bar{y},1+\bar{x}^{2}\bar{y}$ of
$1+\operatorname{Rad}(0)$.

  5. 9:

We obtain

$R^{\times}=\left\langle
1+\bar{y},1+\bar{x},1+\bar{x}^{2},1+\bar{x}\bar{y},1+\bar{x}^{2}\bar{y}\right\rangle.$

The generating set produced by Algorithm 5 is in general not minimal. But we
can compute the exponent lattice of these generators to identify redundant
ones. Furthermore, the isomorphism type of the unit group can be determined by
computing the Smith normal form of the exponent lattice.

######  Corollary 18.

(Computing the Isomorphism Type of the Unit Group)
Let $R=P/I$ be a finite $\mathbb{Z}$-algebra. The following instructions form
an algorithm which computes the rank and the invariant factors of the group
$R^{\times}$.

1: Using Algorithm 5, compute generators $g_{1},\dots,g_{k}$ of $R^{\times}$.

2: Using Algorithm 3, compute generators $v_{1},\dots,v_{m}\in\mathbb{Z}^{k}$
which generate the exponent lattice of $(g_{1},\dots,g_{k})$ in $R$.

3: Form the matrix whose rows are given by $v_{1},\dots,v_{m}$, and compute
its Smith normal form $S$.

4: Let $r$ be the number of main diagonal entries of $S$ equal to zero, and
let $k_{1},\dots,k_{u}$ be the non-zero main diagonal entries of $S$.

5: return $r$ and $k_{1},\dots,k_{u}$.

Algorithm 5 for computing generators of the unit group of a finite
$\mathbb{Z}$-algebra raises the natural question whether it can be extended to
finitely generated $\mathbb{Z}$-algebras which are not necessarily finite
$\mathbb{Z}$-modules. The unit group of such rings is finitely generated if
and only if the Jacobson radical is finitely generated as an additive group
(see [2, Thm. 1]). In particular, the unit group of a finitely generated,
reduced $\mathbb{Z}$-algebra is a finitely generated group. However, the
previous results cannot be directly applied to compute a set of generators.
For example, in the integral case, the algebra no longer needs to be a finite
field or an order in a number field. To the best of our knowledge, there exist
no algorithms which compute generators of the unit group in this case. We
leave this problem for future research.

## References

  * [1] W.W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics 3, Amer. Math. Soc., Providence, 1994.
  * [2] H. Bass, Introduction to Some Methods of Algebraic $K$-Theory, Amer. Math. Soc., Providence, 1974.
  * [3] J.-F. Biasse and C. Fieker, Subexponential class group and unit group computation in large degree number fields, LMS J. Comput. Math. 17A (2014), 385–403.
  * [4] O. Braun, R. Coulangeon, G. Nebe, and S. Schönnenbeck, Computing in arithmetic groups with Voronoi’s algorithm, J. Algebra 435 (2015), 263–285.
  * [5] J. Chen, S. Vemulapalli, and L. Zhang, Computing unit groups of curves, J. Symbolic Comput. 104 (2021), 236–255.
  * [6] H. Cohen, F. Diaz, and M. Olivier, Subexponential algorithms for class group and unit computations, J. Symbolic Comput. 24 (1997), 433–441.
  * [7] L.G. Dirichlet, Zur Theorie der komplexen Einheiten (1846) (in German), Werke, Vol. I, Dietrich Reimer Verlag, Berlin, 1889, pp. 639–644.
  * [8] J. Dubrois and J.-G. Dumas, Efficient polynomial time algorithms computing industrial-strength primitive roots, Inform. Process. Lett. 97(2) (2006), 41–45.
  * [9] C. Eder, G. Pfister, and A. Popescu, Standard bases over Euclidean domains, J. Symbolic Comput. 102 (2021), 21–36.
  * [10] P. Faccin, W.A. de Graaf, and W. Plesken, Computing generators of the unit group of an integral abelian group ring, J. Algebra 373 (2013), 441–452.
  * [11] G. Ge, Algorithms related to multiplicative representations of algebraic numbers, PhD thesis, University of California, Berkeley, 1993.
  * [12] G.-M. Greuel and G. Pfister, A Singular Introduction to Commutative Algebra, Springer-Verlag, Berlin, Heidelberg, 2008.
  * [13] R. Kannan and A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8(4) (1979), 499–507.
  * [14] M. Kauers, Algorithms for nonlinear higher order difference equations, PhD Thesis, RISC Institute, Linz, 2005.
  * [15] M. Kauers, P. Nuspl, and V. Pillwein, Order bounds for $C^{2}$-finite sequences, in: ISSAC’23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery, New York, 2023, pp. 389–397.
  * [16] M. Kreuzer, A. Miasnikov, and F. Walsh, Decomposing finite $\mathbb{Z}$-algebras, preprint 2023, available at arXiv:2308.01735.
  * [17] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1, Springer-Verlag, Berlin, Heidelberg, 2000.
  * [18] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2, Springer-Verlag, Berlin, Heidelberg, 2005.
  * [19] M. Kreuzer and F. Walsh, Computing the binomial part of a polynomial ideal, J. Symbolic Comput. 124 (2024), paper 102298.
  * [20] M. Kreuzer and F. Walsh, Efficient algorithms for finite $\mathbb{Z}$-algebras, journal of Groups, Complexity, Cryptology 15(2) (2024).
  * [21] H.W. Lenstra and A. Silverberg, Algorithms for commutative algebras over the rational numbers, Found. Comput. Math. 18(1) (2018), 159–180.
  * [22] E. Malek, On the group of units of a finite R-algebra, J. Algebra 23(3) (1972), 538–552.
  * [23] K.A. Mihailova, The occurrence problem for free products of groups, Math. USSR Sb. 4(2) (1968), 181–190.
  * [24] P. Samuel, Algebraic Theory of Numbers: Translated from the French by Allan J. Silberger, Hermann, Paris, 1970.
  * [25] V. Shoup, Searching for primitive roots in finite fields, Math. Comp. 58(197) (1992), 369–380.
  * [26] A. Storjohann, Near optimal algorithms for computing smith normal forms of integer matrices, in: Algorithms and Computation, Proc. ISAAC’96 (Osaka 1996), LNCS 1178, Springer-Verlag, Berlin, Heidelberg, 1996, pp. 267–274.
  * [27] The Sage Developers, Sagemath, the Sage Mathematics Software System, 2023.
  * [28] F. Walsh, Binomial part, a Sagemath package, Version 1.1, April 2024, available at
https://github.com/abacus42/binomial-part.

  * [29] K. Yokoyama, M. Noro, and T. Takeshima, Computing primitive elements of extension fields, J. Symbolic Comput. 8(6) (1989), 553–580.
  * [30] H. Zassenhaus, On the units of orders, J. Algebra 20 (1972), 368–395.
  * [31] T. Zheng and B. Xia, An effective framework for constructing exponent lattice basis of nonzero algebraic numbers, in: ISSAC ’19: Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery, New York, 2019, pp. 371–378.