Proefschrift ter Verkrijging Van

C J J M Stolker

ALGORITHMS FOR FINITE RINGS

Keywords: algorithmes déterministes, anneaux finis, modules finis, isomorphisme, radical de Jacobson, semi-simplicité, séparabilité deterministic algorithms, finite rings, finite modules, isomorphism, Jacobson radical, semisimplicity, separability

Titre: Algorithmes pour les anneaux finis Résumé: Cette thèse s'attache à décrire des algorithmes qui répondent à des questions provenant de la théorie des anneaux et des modules. Nous restreindrons essentiellement notre étude à des algorithmes déterministes, en temps polynomial, ainsi qu'aux anneaux et modules finis.

Le premier des principaux résultats de cette thèse concerne le problème de l'isomorphisme entre modules : nous décrivons deux algorithmes distincts qui, étant donné un anneau fini R et deux R-modules M et N finis, déterminent si M et N sont isomorphes. S'ils le sont, les deux algorithmes exhibent un tel isomorphisme.

De plus, nous montrons comment calculer un ensemble de générateurs de taille minimale pour un module donné, et comment construire des couvertures projectives et des enveloppes injectives. Nous décrivons ensuite des tests mettant en évidence le caractère simple, projectif ou injectif d'un module, ainsi qu'un test constructif de l'existence d'un homomorphisme de modules surjectif entre deux modules finis, l'un d'entre eux étant projectif. Par contraste, nous montrons le résultat négatif suivant : le problème consistant à tester l'existence d'un homomorphisme de modules injectif entre deux modules, l'un des deux étant projectif, est NP-complet.

La dernière partie de cette thèse concerne le problème de l'approximation du radical de Jacobson d'un anneau fini. Il s'agit de déterminer un idéal bilatère nilpotent tel que l'anneau quotient correspondant soit "presque" semi-simple. La notion de "semi-simplicité approchée" que nous utilisons est la séparabilité.

"Once [the reader] explicitly gives up all practical claims, he will realize that he can occupy himself with algorithms without having to fear the bad dreams caused by the messy details and dirty tricks that stand between an elegant algorithmic idea and its practical implementation. He will find himself in the platonic paradise of pure mathematics, where a conceptual and concise version of an algorithm is valued more highly than an ad hoc device that speeds it up by a factor of ten and where words have precise meanings that do not change with the changing world. (...) And in his innermost self he will know that in the end his own work will turn out to have the widest application range, exactly because it was not done with any specific application in mind."

H.W. Lenstra. Algorithms in Algebraic Number Theory (1992). BAMS, 26: 211-244

"If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in creative leaps, no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss (...)."

Contents

Introduction

Throughout this text, rings are assumed to contain a unit element, but are not necessarily commutative. Modules are always left-unital, unless otherwise specified.

The main goal of this PhD thesis is to develop a toolbox for working with finite rings and finite modules within algorithms. The motivation to study problems concerning finite rings and finite modules is twofold. The first reason is a theoretical one and stems from the fundamental nature of the problems that arise. Since we are mostly interested in viewing algorithms as mathematical objects in their own right, the focus will be on deterministic polynomial-time algorithms. The second reason to study these problems refers to the necessity of having as many algorithms as possible available in computer algebra systems to deal with finite rings.

The first chapter of this thesis contains the necessary background theory on algorithms, complexity, rings and modules. Chapters 2 and 3 contain a series of basic algorithms for finitely generated abelian groups and finite rings. These will be used implicitly and extensively in the rest of the algorithms described.

The first algorithmic problem we tackle is the module isomorphism problem. The module isomorphism problem can be formulated as follows: design a deterministic algorithm that, given a ring R and two left R-modules M and N , decides in polynomial time whether they are isomorphic, and if yes, exhibits an isomorphism.

Isomorphism problems are some of the most natural algorithmic questions. Given two objects of the same nature, we would like to be able to tell if they are isomorphic, and if so, we would ideally also want to produce an isomorphism. Objects for which isomorphism problems have been extensively studied include graphs, groups and rings. The easy formulation of these problems and their fundamental nature does not however entail that they have a trivial solution. In fact, for many problems of this type, no deterministic polynomial-time algorithms are known ( [START_REF] Brooksbank | The module isomorphism problem reconsidered[END_REF][START_REF] Kayal | On the ring isomorphism and automorphism problems[END_REF][START_REF] Kayal | Complexity of ring morphism problems[END_REF]).

Two intermediate results, valuable in themselves, are proved in Chapter 4:

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M and N , computes a maximum length R-module C that is isomorphic to a direct summand both of M and of N . Moreover, the algorithm computes direct complements of C both in M and in N , together with the corresponding isomorphisms.

i

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , computes a set of generators for M of minimum cardinality.

Both of these theorems can be used to provide a solution for the module isomorphism problem.

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M and N , decides whether M and N are isomorphic, and if they are, exhibits an isomorphism.

Chapter 5 contains a collection of deterministic polynomial-time algorithms for testing properties of rings and modules.

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , tests whether M is (i) projective, (ii) injective, (iii) simple.

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R, tests whether R is (i) simple, (ii) quasi-Frobenius.

Moreover,

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , constructs a projective cover and an injective hull of M .

We also discuss the algorithmic problem of constructively testing for existence of injective and surjective homomorphisms between two finite length modules over a ring R, i.e. the problem of testing for existence and finding such homomorphisms when they do exist. If R is a finite-dimensional algebra over a field, this problem can be cast in the context of matrix completion, and has been shown to be NP-hard. We consider the case where R is a finite ring and one of the modules is either projective or injective over R.

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M and N , one of which is R-projective, constructively tests for existence of a surjective R-module homomorphism M N .

Dually:

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M and N , one of which is R-injective, constructively tests for existence of an injective R-module homomorphism M → N .

For the remaining cases we obtain negative results:

Theorem. The problem of deciding existence of an injective module homomorphism between two modules over a finite ring, one of which is projective over that ring, is NP-complete.

A very important class of rings is that of semisimple rings. Let R be a ring and M an R-module. Then M is said to be semisimple if every R-submodule of M has a direct complement in M . A ring R is said to be semisimple if the left-regular (or equivalently right-regular) module is semisimple. Semisimple rings have a lot of structure: everything breaks down in an orderly fashion. Moreover, the Wedderburn theorem gives a complete classification of such rings as finite products of matrix rings over division rings.

The notion of semisimplicity is inextricably linked to that of the Jacobson radical of a ring, defined as the intersection of all maximal left ideals. The Jacobson radical of a ring R is a two-sided ideal, and we denote it by J(R). The rings R and R/ J(R) have the same simple left modules, which suggests that a study of R/ J(R) will reveal much of the structure of R. Moreover, if R is left-artinian, then J(R) is a nilpotent ideal of R and R is semisimple if and only if J(R) = 0.

When trying to answer questions about left-artinian rings and modules over them, it is often convenient to reduce the problem at hand to the semisimple case, where structures are much more manageable, and then "lift". This places the computation of the Jacobson radical at the heart of many problems. While it can be done deterministically in polynomial time for matrix algebras over a field [START_REF] Chistov | Polynomial time algorithms for modules over finite dimensional algebras[END_REF][START_REF] Cohen | Finding the radical of an algebra of linear transformations[END_REF][START_REF] Friedl | Polynomial time solutions of some problems of computational algebra[END_REF][START_REF] Rónyai | Computing the structure of finite algebras[END_REF], we cannot expect to have a deterministic polynomial-time algorithm for the general case, since the problem ultimately reduces to finding the squarefree part of an integer (consider the ring Z/nZ, for some n ∈ Z >0 ). In Chapter 6, we attempt to deterministically construct approximations of the Jacobson radical of a finite ring that are "satisfactory" for many practical purposes, that is, two-sided nilpotent ideals such that when we quotient the ring by them, we are left with something that is "almost" semisimple.

The notion used to approximate semisimplicity is that of separability. Given a commutative ring R, an R-algebra S is said to be separable over R if S is projective as an S ⊗ R S o -module, where S o denotes the opposite ring of S. A ring is said to be separable if it is separable as a Z-algebra.

Definition. Let A be a finite ring and j A ⊂ A an ideal. We say j A is an approximation of the Jacobson radical of A if (A1) j A is a two-sided nilpotent ideal of A, (A2) A/j A is finite separable, (A3) A/j A is projective as a module over its prime subring.

The resulting ring, A/j A , has many good properties, e.g. it has "many" projective modules (via projectivity lift), it is quasi-Frobenius, it is isomorphic to its opposite as rings. Moreover, finite separable rings can be classified as finite products of matrix rings over certain commutative rings. We show that approximations of Jacobson radicals can be efficiently computed.

Theorem. There exists a deterministic polynomial-time algorithm that, given a finite ring A, computes an approximation of the Jacobson radical of A.

We are interested in deterministic polynomial-time algorithms that produce approximations of the Jacobson radical of a finite ring and have the additional property that, when run on two isomorphic rings, they output isomorphic approximations of their Jacobson radicals, even when the ring isomorphism is unknown.

In fact, we exhibit not one, but two algorithms as described by the above theorem. If we denote by F the class of finite rings, then the two families of ideals (j A ) A∈F and (j A ) A∈F , produced by the two algorithms are functorial under isomorphisms, i.e. if φ : A → B is an isomorphism of finite rings, then φ(j A ) = j B and φ(j A ) = j B .

List of symbols

Background

This chapter introduces the terminology that will be used throughout the rest of the text. The first section contains a brief discussion about algorithms and complexity, followed by a list of examples of basic algorithmic questions (primality testing, integer factorisation, coprime factorisation). The remaining sections review basic facts of ring and module theory. We will focus on those results that are specific to noncommutative ring theory.

The main references for this chapter are: [START_REF] Lenstra | Algorithms in algebraic number theory[END_REF][START_REF] Papadimitriou | Computational Complexity. Theoretical computer science[END_REF], for the section concerning algorithms, and [START_REF] Lam | Lectures on Modules and Rings[END_REF][START_REF] Lam | A First Course in Noncommutative Rings[END_REF][START_REF] Lam | Serre's Problem on Projective Modules[END_REF][START_REF] Lang | Algebra. Graduate Texts in Mathematics[END_REF], for the rest.

Algorithms and complexity

For an entirely formal discussion of algorithms and complexity, one needs to enter the realm of theoretical computer science jargon. Fortunately, however, this can be avoided, since it so happens that the intuitive notions we have of algorithms, "hardness" of a computational problem, "efficiency" etc., are enough for a meaningful discussion, and complexity theory appears to be "robust" enough to allow us to work with them.

Formally, an algorithm is a Turing machine. Intuitively, an algorithm is a sequence of steps that takes as input a finite sequence of nonnegative integers and produces an output in the form of another finite sequence of nonnegative integers. An integer is represented inside an algorithm by a string of bits, and a step in the algorithm is then a bit operation. It is also useful to have a notion of the "size" of an input. If n ∈ Z ≥0 , then the length of n is taken to be length(n) := log 2 (n + 2), reflecting the number of bits required to write n down in binary. The length of a negative integer m is 1 + length(|m|) and the length of an input is the sum of the lengths of the integers that compose it.

We would like to study the number of steps needed for an algorithm to perform a certain task. The running time represents the number of steps required to produce 1 an output. An algorithm is said to be polynomial-time if its running time is bounded above by a polynomial expression in the length of the input. The running time of an algorithm is often referred to as the complexity of the algorithm. In our case, this is the bit-complexity, as opposed to e.g. the arithmetic complexity, where a step is taken to be an arithmetic operation.

Naturally, we are interested in more than just performing arithmetic in Z. However, virtually any mathematical object of interest can be encoded as a sequence of nonnegative integers. For the objects we are interested in, we will see exactly how to do this in the following two chapters.

Throughout this text, we will be exclusively interested in deterministic polynomialtime algorithms, i.e. algorithms in the running of which no random bit is generated. While allowing for probabilistic algorithms (e.g. Las Vegas or Monte Carlo algorithms) leads in practice to increased efficiency, these algorithms reveal less about the intrinsic difficulty of the problem at hand and are thus of less theoretical interest. We shall not think about them.

Furthermore, we will be content with being able to declare a certain algorithm as running in polynomial time, without computing exact exponents. The main reason for this is that we have not conceived the algorithms presented in this thesis with the intention of also implementing them. Therefore, there are countless improvements and randomised variations possible, which we have chosen not to explore in detail. Computing running times of an algorithm that is deliberately non-optimal seems futile.

Algorithms are often thought of as auxiliary objects, whose main reason for existence is to facilitate experimentation within computer algebra systems, with the purpose of confirming or invalidating hypotheses formulated in a more theoretical setting, providing examples or guiding the mathematician's intuition. In these cases, one is rarely interested in the "intrinsic" difficulty of a problem. Instead, one usually focuses one's attention to a very particular instance of a problem and only desires that the algorithm used to solve it output a result in a "reasonable" amount of time.

Under this paradigm, our preference for deterministic polynomial-time algorithms seems at least odd and perhaps even outdated. However, the viewpoint that we adopt in this thesis is that algorithms are mathematical objects per se, worthy of independent study. The fact that a problem can be solved deterministically in polynomial time says that the problem is not intrinsically difficult or mysterious.

Complexity classes

After fixing the model of computation, we may wish to classify problems based on the rate at which they use up a certain resource, e.g. time. This gives rise to complexity classes.

Within complexity classes, we can order the problems according to their difficulty by using reductions. A reduction from a problem Q to a problem P is an intermediate algorithm that, given a solution to a problem P , produces a solution to another problem Q. We say Q reduces to P . This formulation suggests that problem P is "at least as hard" as Q. Intuitively, a reduction has to be an "easy" computation. We will mainly be interested in reductions that are deterministic polynomial-time algorithms.

The problems that are maximal elements with respect to the partial ordering induced by reductions are said to be complete for that complexity class. These problems capture the difficulty of the entire class. Moreover, the existence of a "natural" complete problem in a complexity class guarantees that the class is not "artificial".

The most important complexity classes are listed below, together with informal descriptions:

1. P: consists of problems that can be solved by a deterministic polynomial-time algorithm;

2. NP: consists of problems whose solutions can be verified deterministically in polynomial time;

3. NP-hard: a problem A is NP-hard if every problem B in NP can be reduced to A;

4. NP-complete: consists of problems that are both in NP and NP-hard.

Clearly P ⊆ NP. The question whether the reverse inclusion holds is at this time one of the most important open problems in theoretical computer science. If P = NP, then there exist problems that are in NP, but are neither NP-complete, nor in P (see [START_REF] Papadimitriou | Computational Complexity. Theoretical computer science[END_REF], Theorem 14.1). These are called NP-intermediate problems. However, no "natural" NP-intermediate problems are known.

Integer factorisation, coprime factorisation and primality testing

Perhaps the simplest question one might ask oneself is, if given a positive integer, whether one can find a factorisation into primes. Despite its fundamental nature, the problem of integer factorisation is notoriously difficult, which has made it the heart of many algorithms used in cryptography. It is easy to see that integer factorisation lies in the complexity class NP. However, no deterministic polynomial-time algorithm for it is known. It is also not thought to be NP-complete, and is hence considered to be a candidate for the NP-intermediate class. There is an extensive literature devoted to a large variety of algorithms for integer factorisation (see e.g. [START_REF] Buhler | Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography[END_REF][START_REF] Lenstra | Integer factoring. Designs[END_REF]). A similar and related problem is that of finding square divisors of a given integer, for which there is also no known deterministic polynomial-time algorithm (see [START_REF] Landau | Some remarks on computing the square parts of integers[END_REF] or [START_REF] Buchmann | Approximating rings of integers in number fields[END_REF], Section 7.1).

Factoring into primes is out of our reach. However, given a set of integers, we can simultaneously factor them into "coprime" factors. Furthermore, primality testing has been shown to be in P.

Theorem 1.1.3 ([1]

). There exists a deterministic polynomial-time algorithm that, given n ∈ Z >1 , determines if n is prime.

Basic ring theory

Definition 1.2.1. A ring is a triple (R, +, •), where R is a set and +, • : R × R → R are binary operations such that:

(R1) (R, +) is an abelian group, (R2) (R, •) is a monoid, i.e
. the operation • is associative and has an identity element, (R3) for all x, y, z ∈ R, we have x

• (y + z) = x • y + x • z and (x + y) • z = x • z + y • z.
We say (R, +, •) is a commutative ring if, in addition (R, +, •) satisfies (R4) for all x, y ∈ R, we have x • y = y • x.

We denote the identity element of (R, +) by 0 R , and the identity element of (R,

•) by 1 R . A subring of (R, +, •) is a subset S ⊂ R such that (S, +, •) is itself a ring and 1 R ∈ S. Definition 1.2.2. Let R be a ring. (i) We define the centre of R to be Z(R) := {r ∈ R | ∀s ∈ R : rs = sr}. (ii) We define the characteristic of R to be the integer n ∈ Z ≥0 such that ker(Z → R + , 1 → 1 R ) = nZ.
Note 1.2.3. Let R be a finite ring and let R + denote the underlying abelian group of R. Then char(R) = exp(R + ),

where exp(R + ) is the exponent of the abelian group R + , i.e. the smallest positive integer m such that for all r ∈ R + , the composition of r with itself m times equals the identity element.

Definition 1.2.4. Let (R, +, •) be a ring. A left ideal of R is subset I ⊂ R such that (I1) (I, +
) is an abelian subgroup of (R, +), (I2) for all r ∈ R and i ∈ I, we have ri ∈ I.

Analogously, we can define right ideals. An ideal is said to be two-sided, if it is both right and left.

Definition 1.2.5. Let R be a ring and I ⊆ R a one-sided (or two-sided) ideal of R. Then (i) I is said to be nil if every element of I is nilpotent.

(ii) I is said to be nilpotent if there exists n ∈ Z >0 such that I n = 0.

F (r 1 • R r 2 ) = F (r 1 ) • S F (r 2 ).
A bijective ring homomorphism is called a ring isomorphism.

Definition 1.2.8. Let R be a ring. We define the prime subring of R to be the image of the ring homomorphism Z → R, given by 1 → 1 R .

Definition 1.2.9. An algebra is a pair of rings, k and R, with k commutative, together with a ring homomorphism ϕ : k → R such that im(ϕ) ⊆ Z(R). We then say that R is an algebra over k.

Theorem 1.2.10 ([27], Theorem 1.1). Let R be a finite-dimensional algebra over a field F and let n := dim F (R). Then R is isomorphic to a subalgebra of M n (F).

Theorem 1.2.11 ([57], Theorem 3.1). Let R be a ring, n ∈ Z >0 and S = M n (R).

Then (i) If I is a two-sided ideal of R, then M n (I) is a two-sided ideal of S.
(ii) Every two-sided ideal of S is of the form M n (I), for some two-sided ideal I of R.

Basic module theory

Definition 1.3.1. Let R be a ring. A left R-module is an abelian group (M, +), together with an action R × M → M such that:

(M1) for all r, s ∈ R and x ∈ M , we have r(sx) = (rs)x, (M2) for all r, s ∈ R and x ∈ M , we have (r + s)x = rx + sx, (M3) for all r ∈ R and x, y ∈ M , we have r(x + y) = rx + ry, (M4) for all x ∈ M , we have 1 R x = x.

Analogously, we can define right R-modules. A submodule of a left R-module M is an abelian subgroup N ⊂ M such that RN ⊆ N .

Note 1.3.2. By a module, we will always mean a left module.

Definition 1.3.3. Let R, S be two rings. An R-S-bimodule is an abelian group (M, +) such that

(B1) M is a left R-module, (B2) M is a right S-module, ( B3
) for all x ∈ M , r ∈ R and s ∈ S, we have (rm)s = r(ms).

We often write R M S for an R-S-bimodule M .

Definition 1.3.4. Let R be a ring. Then the left-regular R-module, R R, is the abelian group (R, +), together with an action R × R → R given by left-multiplication. We can similarly define the right-regular R-module, R R .

Definition 1.3.5. Let R be a ring. We say an R-module M is free if M ∼ = i∈I R i =: R (I) as R-modules, where I is an arbitrary indexing set and R i ∼ = R for all i ∈ I.

Definition 1.3.6. Let R be a ring. We say that R has left (vi) M is finitely generated over R if there exists a finite set X ⊂ M such that M = x∈X Rx. (vii) M has finite length if M has a finite composition series, i.e. there exists t ∈ Z ≥0 and a sequence Theorem 19.16). (Fitting's Lemma) Let R be a ring, M a finite-length R-module and f ∈ End R (M ). Then there exists n ∈ Z >0 such that

IBN (Invariant Basis Number) if for all n, m ∈ Z >0 , whenever R R n ∼ = R R m , we have that n = m. Note 1.3.7 ([56], Corollary 1.2). Let R be a ring. If R R (I) ∼ = R R (J) ,
(N i ) t i=0 of submodules of M such that M = N t > N t-1 > . . . > N 1 > N 0 = 0 and for all 0 ≤ i ≤ t -1, we have that N i+1 /N i is simple. Proposition 1.3.12 ([57],
M = ker(f n ) ⊕ im(f n ).
Theorem 1. 3.13 ([57], Corollary 19.22). (Krull-Remak-Schmidt Theorem) Let R be a ring and M an R-module of finite length. Then there exist n ∈ Z >0 and indecomposable submodules

M i ≤ M such that M = n i=1 M i .
Moreover, n is uniquely determined, and the sequence (M i ) n i=1 is uniquely determined up to isomorphism, and up to a permutation. Proposition 1.3.14. Let R be a ring and I ⊂ R a two-sided ideal. Let M be an abelian group. Then M is an R/I-module if and only if M is an R-module that is annihilated by I.

Proof. Suppose M is an R-module that is annihilated by I. Then we can define an R/I-module structure on M , given by R Theorem 3.3). Let D be a division ring and let R = M n (D), for some n ∈ Z >0 . Then, up to isomorphism, R has a unique simple left module V , and V ∼ = D n as R-modules.

/I × M → M , (r + I)m → rm. Conversely, if M is an R/I-module, then M is an R-module via R × M → M , rm → rm
(i) R is a division ring if R = 0 and for all 0 = r ∈ R, there exists s ∈ R such that rs = sr = 1 R . (ii) R is Dedekind-finite if every element of R that is left-invertible is also right- invertible. (iii) R is left-artinian (resp. right-artinian) if R R (resp. R R ) is artinian. (iv) R is left-noetherian (resp. right-noetherian) if R R (resp. R R ) is noetherian. Proposition 1.4.2 ([57],

Semisimple rings

One of the most important class of rings is that of semisimple rings.

R ∼ = t i=1 M ni (D i ),
where t ∈ Z ≥0 , n i ∈ Z >0 and the D i are division rings. Note 1.4.6. Let R be a semisimple ring. Then the isomorphism classes of simple R-modules form a finite set. Moreover, the proof of Theorem 1.4.5 shows that

R ∼ = S simple End End R (S) (S),
where the product ranges over the isomorphism classes of simple R-modules.

The Jacobson radical

The notion of semisimplicity is inextricably linked to that of the Jacobson radical. Definition 1.4.7. Let R be a ring. The Jacobson radical is defined as

J(R) := I⊂R I max left ideal I. Theorem 1.4.8 ([57], Corollary 4.2). Let R be a ring. Then J(R) = M M simple R-module ann R (M )
Theorem 1.4.9 ([57], Lemma 4.11, Theorems 4.12,4.14). Let R be a ring and J(R) its Jacobson radical. Then

(i) J(R) is a two-sided ideal of R. (ii) If I ⊂ R is a nil one-sided ideal, then I ⊆ J(R). (iii) If R is left-artinian, then J(R) is the largest nilpotent left (resp. right) ideal of R. (iv) R is semisimple if and only if R is left-artinian and J(R) = 0.
Theorem 1. 4.10 ([18], Section 2). Let R be a finite-dimensional algebra of matrices over a field F, where char(F) = 0. Then J(R) = {r ∈ R | Tr(rs) = 0 for all s ∈ R}.

(1.

∈ Z >0 . Then J(M n (R)) = M n (J(R)).
Proposition 1.4.13. Let R be a ring, I ⊆ R a two-sided nilpotent ideal and M an R-module. Then M is an R/I-modules, and M is simple over R/I if and only if it is simple over R.

Proof. This is an easy corollary of Proposition 1.3.14.

Menagerie of rings II

Definition 1.4.14. Let R be a ring. Then

(i) R is semilocal if R/ J(R) is semisimple. (ii) R is semiprimary if J(R) is nilpotent and R/ J(R) is semisimple. (iii) R is local if R/ J(R

Idempotents

Definition 1.5.1. Let R be a ring. An element e ∈ R is an idempotent if e 2 = e.

Two idempotents e 1 and e 2 are said to be orthogonal if e 1 e 2 = e 2 e 1 = 0.

Definition 1.5.2. Let R be a ring and e ∈ R an idempotent. Then

(i) e is central if e ∈ Z(R).
(ii) e is primitive if e = 0 and it cannot be written as the sum of two nonzero orthogonal idempotents. (iii) e is centrally primitive if e ∈ Z(R), e = 0 and e cannot be written as the sum of two nonzero orthogonal central idempotents.

Definition 1.5.3. A ring R is said to be connected if R = 0 and the only central idempotents in R are 0 and 1.

Theorem 1.5.4. Let R be a ring, and M an R-module.

(i) Let N, P be R-modules. Then M = N ⊕ P if and only if there exists an idempotent e ∈ End R (M ) such that N = e(M ) and P = (1 -e)(M ).

(ii) Let A, B be R-modules. Then R = A⊕B if and only if there exists an idempotent e ∈ R such that A = Re and

B = R(1 -e). (iii) ([77], Proposition 1.1.14) Let R 1 , R 2 be two-sided ideals of R. Then R = R 1 ×R 2
if and only if there exist central orthogonal idempotents e 1 , e 2 such that e 1 +e 2 = 1, with R i = Re i , for i = 1, 2.

Let R be a ring and suppose that 1 ∈ R can be written as a finite sum of orthogonal centrally primitive idempotents. Then such a decomposition 1 = e 1 +. . .+e n is unique up to permutation of the summands, and R can be written as a finite product of connected rings. Moreover, we have

R = Re 1 ⊕ . . . ⊕ Re n .
We call this a block decomposition of R. Proof. Let E ∈ R be an idempotent. Then certainly p(E) is an idempotent in R/ J(R). Suppose e ∈ R/ J(R) is an idempotent, i.e. e 2 -e ∈ J(R). What we want to find is an element satisfying x 2 -x = 0 in R, which is mapped to e. Consider the polynomial F (x) = 3x 2 -2x 3 . Let e 1 := F (e). Then

e 2 1 -e 1 = (3e 2 -2e 3 ) 2 -(3e 2 -2e 3 ) = (4e 2 -4e -3)(e 2 -e) 2 ∈ J(R) 2 , so e 2 1 -e 1 ∈ J(R) 2 .
Moreover, e 1 = e -(2e -1)(e 2 -e), so e 1 ≡ e mod J(R).

We define e i := F (e i-1 ). By induction, we have e 2 i -e i ∈ J(R) 2 i and e i ≡ e mod J(R). Since R is left-artinian, J(R) is nilpotent, so there exists n ∈ Z ≥0 such that e 2 n -e n ∈ J(R) n = 0. Then E = e n is the element we were after.

Remark 1.5.9. The key to the above proof is that e 2 -e is nilpotent. Hence we can use the same lifting technique against any nil ideal of R. (i) J ⊆ J(R).

R = F F 0 F and the R-module M = R 0 0 0 1 = 0 F 0 F . Then End R (M ) ∼ = F ,
(ii) For any finitely generated left R-module M ,

J • M = M ⇒ M = 0.
(iii) For any left R-modules N ≤ M such that M/N is finitely generated, , for some subset J ⊆ I. But this happens if and only if Z/mZ = j∈J Z/p aj j Z, which is a direct summand of Z/nZ. Proposition 1.6.9 ([20], Proposition 1.4). Let k be a commutative ring and let R be a k-algebra such that R is projective as a k-module. Let M be a projective R-module. Then M is projective over k. Definition 1.6.10. Let R be a ring and I an R-module. Then I is said to be injective if for any injective R-module homomorphism g : A → B and any R-module homomorphism f : A → I, there exists an R-module homomorphism h : B → I such that f = hg: I

N + J • M = M ⇒ N = M.
0 A B.

Rank of a projective module

In this section, suppose R is a commutative ring. Denote by Spec(R) the set of prime ideals of R and by Max(R) the set of maximal ideals of R. Let M be an R-module and p ∈ Spec(R). Then we denote by M p the localisation of M at R\p. Proposition 1.6.17 ([58], Corollary 3.4). Let M be a finitely presented R-module. Then the following are equivalent:

(i) M is projective over R, (ii) for all m ∈ Max(R), we have that M m is projective over R m , (iii) for all p ∈ Spec(R), we have that M p is free over R p .

Let P be a projective R-module. Consider the function rk R (P ) : Spec(R) → Z, p → rk Rp (P p ). Definition 1.6.18. Let P be a projective R-module. If rk R (P ) is a constant function, then we say P has constant rank.

i) Hom R ( R M S , R N T ) is an S-T -bimodule, where for all s ∈ S, t ∈ T , m ∈ M and f ∈ Hom R (M, N ), we have s • f (m) = f (ms) and (f • t)(m) = f (m)t. (ii) Hom T ( R N T , S P T ) is an S-R-bimodule
, where for all s ∈ S, r ∈ R, n ∈ N and g ∈ Hom T (N, P ), we have that s

• g(n) = sg(n) and (g • r)(n) = g(rn). (iii) R M S ⊗ S S P T is an R-T -bimodule, where for all r ∈ R, t ∈ T , m ∈ M and n ∈ N , we have r • (m ⊗ n) = rm ⊗ n and (m ⊗ n) • t = m ⊗ nt.
Proposition 1.6.20. Let R, S be two rings, let α : R → S be a ring homomorphism and M an S-R-bimodule. Then

Hom S ( S S R , S M R ) ∼ = R M R ,
as R-R-bimodules.

(P, Q) ⊗ R R ∼ = Hom R (P ⊗ R R , Q ⊗ R R ), (P ⊗ R Q) ⊗ R R ∼ = (P ⊗ R R ) ⊗ R (Q ⊗ R R ),
as R -modules. If S is a superfluous submodule of M , we write S ⊆ s M .

Projective covers and injective hulls

Definition 1.6.24. Let M be an R-module. A projective cover of M is a pair (P, φ), where P is a projective R-module, φ : P M is an epimorphism, and ker(φ) ⊆ s P . (i) If R is left-artinian, then any R-module has a projective cover.

(ii) Let M be an R-module. Suppose (P, φ) and (P , φ ) are two projective covers of M . Then there exists an isomorphism α : P → P such that φ = φα. (iii) Let M 1 , . . . , M n be R-modules. Suppose (P i , φ i ) is a projective cover of M i , for all 1 ≤ i ≤ n. Then (

n i=1 P i , n i=1 φ i ) is a projective cover of n i=1 M i . Definition 1.6.26. Let M be an R-module. An essential extension of M is an R- module E ⊇ M such that ∀F ≤ E : (F ∩ M = 0 ⇒ F = 0)
If E is an essential extension of M , we write M ⊆ e E.

Frobenius algebras and symmetric algebras

Let k be a commutative ring and A a k-algebra that is finitely generated projective as a module over k. The k-dual, Hom k (A, k), is an A-A-bimodule. The left module structure is given by a

• f = (x → f (xa)),
and the right module structure is given by

f • a = (x → f (ax)),
where a ∈ A and f ∈ Hom k (A, k). These two actions are compatible: for any a, a , x ∈ A, we have ((a

• f ) • a )(x) = f (a xa) = (a • (f • a ))(x).
Comparing the A-A-bimodule structures of A and Hom k (A, k) leads to the following two notions. Definition 1.8.1. Let k be a commutative ring and A a k-algebra that is finitely generated projective as a module over k. If A ∼ = Hom k (A, k) as left A-modules, then we say A is a Frobenius algebra. If A ∼ = Hom k (A, k) as A-A-bimodules, then we say A is a symmetric algebra.

Theorem 1.8.2 ([56], Theorems 16.54). Let k be a commutative ring and A a kalgebra that is finitely generated projective as a module over k. Then A is a symmetric algebra over k if and only if there exists a k-bilinear map B : A × A → k such that (i) B is symmetric, i.e. for all x, y ∈ A, we have B(x, y) = B(y, x), (ii) B is nonsingular, i.e. the map A → Hom k (A, k), given by x → (y → B(x, y)) is a k-module isomorphism, (iii) B is associative, i.e. for all x, y, z ∈ A, we have B(xy, z) = B(x, yz), Example 1.8.3 ([56], 16.56-59). (Symmetric algebras) 1. Let k be a field and G a finite group. Then the group ring A = k[G] is a symmetric k-algebra. To see this, consider the map B :

A × A → k given by B( g∈G a g g, h∈G b h h) = g∈G a g b g -1
, where for all g ∈ G, we have a g , b g ∈ k. 2. Let k be a field and A = M n (k), for some n ∈ Z >0 . Then A is a symmetric k-algebra. To see this, consider the map B : A × A → k, given by B(X, Y ) = tr(XY ), where tr denotes the usual trace map. 3. Let k be a field. Then any finite-dimensional semisimple k-algebra is symmetric.

Generators and progenerators

Definition 1.8.4. Let R be a ring and M and R-module. The trace ideal of M over R is defined to be T R (M ) :=

f ∈Hom R (M,R) im(f ). Note 1.8.5. It is easy to check that T R (M ) is a two-sided ideal of R. Definition 1.8.6. Let R be a ring. An R-module M is an R-generator if T R (M ) = R.
If, in addition, M is finitely generated and projective, then it is said to be an Rprogenerator.

Note 1.8.7. Over a commutative ring R, any faithful finitely generated projective module is a progenerator. The converse also holds.

Duality

Let R be a finite ring. Denote by fg R M and M fg R the categories of finitely generated left, respectively right, R-modules. Definition 1.9.1. Let R be a finite ring and denote by fg R M and M fg R the categories of finitely generated left and right R-modules, respectively. We define the character functors

: fg R M M fg R , M → M := Hom Z (M, Q/Z).
The module M is called the character module of M .

Theorem 1.9.2 ([56], §19C,D). Let R be a finite ring. Consider the contravariant functors

F : fg R M -→ M fg R and G : M fg R -→ fg R M, (1.2)
defined by taking character modules. Then G • F and F • G are naturally equivalent to the identity functors, i.e. F and G define a duality between fg R M and M fg R .

Chapter 2

Linear algebra over Z: basic algorithms for finite abelian groups

When working algorithmically with finite-dimensional algebras over a field, we rely on the vector space structure for our computations (most importantly for solving systems of linear equations). However, when presented with an arbitrary finite ring, we would like to be able to handle the situation regardless of whether it contains a field or not. In the absence of an underlying field, it is the additive group structure of the ring in question that we wish to exploit.

This chapter lays the foundation of everything that succeeds it. At the end of it, we will have built a toolbox for working with finite abelian groups within algorithms. This will allow our later algorithms to have a natural proof-like flow. We will not have to think about the bit operations that go on behind the scenes, and we will talk of algebraic structures, rather than of the strings of integers representing them.

Our algorithms are purposely conceptual. In this way, we aim to concentrate on the structural properties of our objects, rather than rely on seemingly random matrix manipulations that end up giving the "right" result.

We will represent finitely generated abelian groups via generators and relations. Correspondingly, we show how to represent group homomorphisms, subgroups and quotients of groups. Building on this, we describe deterministic polynomial-time algorithms that accomplish the following tasks in the abelian case: The last of these is particularly important, as it will allow us to assume in later chapters that a finite abelian group is given by specifying the sizes of its cyclic direct summands.

Working with finitely generated abelian groups in the representation we have chosen ultimately reduces to carrying out integer matrix computations. The way to keep the entries of these matrices under control is either to employ modular techniques, or to give the group a lattice structure and use basis reduction algorithms.

Lattices

The main references for this section are [START_REF] Lenstra | Flags and lattice basis reduction[END_REF][START_REF] Lenstra | Lattices. In Algorithmic number theory: lattices, number fields, curves and cryptography[END_REF]. Definition 2.1.1. A lattice is an additive subgroup L ⊆ R n , where n ∈ Z ≥0 , for which there exists ∈ R >0 such that for all x ∈ L, x = 0, we have x, x ≥ , where A set B as in Proposition 2.1.2 is said to be a basis of L, and the cardinality of B is the rank of L. Suppose B = {b 1 , . . . , b m }, for some m ∈ Z >0 and let A be the matrix whose i th column is given by b

i . The determinant of L is det(L) := det( b i , b j ) 1/2 1≤i,j≤m = | det(A)|.
It can be shown that the rank and determinant of a lattice are well-defined. Definition 2.1.3. Two lattices L and L are said to be isomorphic if there exists a bijective Z-linear transformation τ : L → L such that for all x, y ∈ L, we have x, y = τ (x), τ (y) . If such a transformation exists, we write L ∼ = L .

Since most real numbers cannot be represented inside algorithms using a finite number of bits, we will only consider lattices whose vectors are rational numbers. In this case, we represent a lattice by giving a matrix A ∈ M n×m (Q) of rank m. Then L is taken to be the lattice with basis given by the m columns of A, and we write L = L(A).

An important notion in the theory of lattices is that of a reduced basis. A precise definition can be found in [START_REF] Lenstra | Lattices. In Algorithmic number theory: lattices, number fields, curves and cryptography[END_REF], Section 10. Intuitively, reduced bases can be thought of as consisting of "short" vectors that are "nearly orthogonal". To the notion of a reduced basis we associate a parameter c > 4/3. Roughly speaking, c is a qualitative measure of the reduction -the smaller the value of c, the better the reduction. When no such parameter is specified, it is typically taken to be 2.

An algorithm that, given a lattice, produces a reduced basis thereof is called a lattice basis reduction algorithm. An example of such an algorithm, that is deterministic and runs in polynomial time, is the LLL algorithm ( [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]).

Definition 2.1.4. Let L be a lattice of rank n in R n . The dual lattice of L is given by L = {x ∈ R n | x, L ⊂ Z},
where •, • is the standard inner product. (iv) If L has basis given by the columns of a matrix A, then L has basis given by the columns of the inverse of the transpose of A.

Kernels, images and systems of linear equations over Z

One of the basic tools that we will use is the efficient computability of kernels and images. This algorithm can then be used to solve systems of linear equations over Z.

Theorem 2.1.7 ([68], Section 14). There exists a deterministic polynomial-time algorithm that, given a triple (m, n, f ), with n, m ∈ Z ≥0 and f ∈ M n×m (Z), together with a vector b ∈ Z n , computes the set of solutions of the equation f x = b, or determines that there is no solution.

Intersection, sum, inclusion and equality of lattices

A subgroup H ⊆ Z n is given to an algorithm by specifying a sequence of elements of

Z n that
H 1 = H 1 ∩(H 1 +H 2 ), which gives a basis for H 1 in terms of the basis of H 1 + H 2 .
As a consequence of this, we are able to determine inclusion and equality of two subgroups of Z n . Corollary 2.1.9. There exists a deterministic polynomial-time algorithm such that, given n ∈ Z >0 and two subgroups H 1 , H 2 ⊆ Z n , determines whether

H 1 ⊆ H 2 . Proof. Note that H 1 ⊆ H 2 if and only if H 1 ∩ H 2 = H 1 . Since H 1 ∩ H 2 ⊆ H 1 ,
testing equality is equivalent to testing whether the determinants of the two lattices, H 1 ∩ H 2 and H 1 , are equal. Computing determinants of lattices reduces to computing determinants of integer matrices, which can be done in polynomial time.

Corollary 2.1.10. There exists a deterministic polynomial-time algorithm such that, given n ∈ Z >0 and two subgroups H 1 , H 2 ⊆ Z n , determines whether

H 1 = H 2 .

Hermite and Smith normal forms

This section draws on Section 2.4 of [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF].

There are two canonical forms of a matrix A that are of interest: the Hermite normal form and the Smith normal form. These can be obtained by applying row and column operations to A. Definition 2.2.1. Let m, n ∈ Z >0 and A ∈ M n×m (Z). A column operation on A is one of the following:

(i) interchanging two columns of A, (ii) multiplying one column of A by -1, (iii) adding a nonzero multiple of a column of A to another column.

Note 2.2.2. (i) Each column operation corresponds to postmultiplying A with an

appropriate invertible matrix over Z. (ii) If A is a matrix obtained from A via a sequence of column operations, then there exists an invertible matrix V such that A = AV . Conversely, if two matrices differ by a postmultiplied invertible matrix, then one can be obtained from the other by a series of column operations. (iii) Applying column operations to a square matrix does not change the absolute value of its determinant.

Note 2.2.3. We can similarly define row operations. These correspond to premultiplying by a certain invertible matrix over Z.

It is easy to see that performing column operations on a matrix does not change the lattice the columns generate. Proposition 2.2.4. Let A, B ∈ M n×m (Z). Then the lattice generated by the columns of A is equal to the lattice generated by the columns of B if and only if there exists

V ∈ GL m (Z) such that AV = B.
Note 2.2.5. Let F be a free Z-module of finite rank. In choosing to represent a subgroup H → F via a matrix A ∈ M n×m (Z), we are making a choice of basis of H and of F . Applying column operations to A corresponds to a change of basis of H, while keeping the basis for F fixed. Applying row operations corresponds to a change of basis of F , while keeping the basis for H fixed.

We are now ready to introduce the Hermite normal form, which is useful for representing subgroups of Z n in a canonical way. Definition 2.2.6. Let A = (a i,j ) ∈ M n×m (Z), for some m, n ∈ Z >0 . Then A is said to be in Hermite normal form (HNF) if there exists 0 ≤ k ≤ m such that the last mk columns are zero and for each 1 ≤ j ≤ k, there exists an entry a ij ,j > 0 such that (i) For all i < i j , we have a i ,j = 0. (ii) For all j < j, we have a ij ,j > a ij ,j ≥ 0. (iii) For all j < j, we have i j < i j .

Note 2.2.7. The nonzero entry a ij ,j is called the leading coefficient of the j th column. Informally, a matrix is in Hermite normal form if all its zero columns lie on the right, the leading coefficients of all nonzero columns are strictly positive and have nonnegative and strictly smaller entries to their left, and occur strictly below the position of the leading coefficient of the previous column, if this exists. Note 2.2.8. We have seen that applying column operations to a matrix does not change the lattice it generates. Thus, finding the Hermite normal form of a matrix corresponds to finding a basis of the associated lattice, such that the basis vectors can be ordered in such a way that they have an increasing number of leading zero entries. Proposition 2.2.9. (i) Each integer matrix can transformed into a matrix in Hermite normal form by a sequence of column operations. (ii) ( [START_REF] Buchmann | Approximating rings of integers in number fields[END_REF], Section 5.3) Each integer matrix has a unique Hermite normal form, i.e. if A = (a i,j ) ∈ M n×m (Z), then there exists a matrix

V ∈ GL m (Z) such that AV is in Hermite normal form. If there is another V ∈ GL m (Z) such that AV is in Hermite normal form, then AV = AV . Sketch of proof of (i). Let A = (a i,j ) ∈ M n×m (Z). Suppose that A has block form A = A 0 0 ,
where A 0 is an n × m matrix, for some m ≤ m, with no nonzero columns. Otherwise interchange columns to arrive at this form. Let a 01 , . . . , a 0m be the entries in the first nonzero row of A 0 . Then at least one a 0i must be nonzero and we can ensure that they are all nonnegative (by applying suitable column operations), so using the extended Euclid algorithm (see [START_REF] Havas | Extended GCD and Hermite normal form algorithms via lattice basis reduction[END_REF]), we can compute g := gcd({a 0i } i ). This reduces to applying a sequence of column operations at the end of which the first nonzero row of A will be [g 0 0 . . . 0]. The matrix now has form

  0 0 0 g 0 0 A 1 0   .
We proceed by computing the greatest common divisor of the entries in the first nonzero row of A 1 . We perform a couple of extra column operations to ensure that the entry to the left of the leading entry of the second column is strictly smaller than the leading entry. We continue in this way until we attain the Hermite normal form.

Note 2.2.10. The matrix V in Proposition 2.2.9, part (ii), need not be unique.

Note 2.2.11. Since the Hermite normal form is unique, we see that the leading entry of the first column is the greatest common divisor of the entries in the first nonzero row of the original matrix.

There are many algorithms available in the literature that compute the Hermite normal form of a given integer matrix. The main difficulty in achieving polynomial time is to keep the entries of the intermediate matrices small. The straightforward column-operation-algorithm presented in Proposition 2.2.9 suffers from coefficient blow-up. This can be avoided by using modular techniques, for example by working modulo an integer d, where d is chosen to be the determinant of a full rank submatrix of A. Another way to circumvent coefficient blow-up is to employ lattice basis reduction techniques.

For detailed accounts of deterministic polynomial-time algorithms for computing the Hermite normal form of an integer matrix, together with a transformation matrix V , see [START_REF] Chou | Algorithms for the solution of systems of linear diophantine equations[END_REF][START_REF] Hafner | Asymptotically fast triangulation of matrices over rings[END_REF][START_REF] Havas | Extended GCD and Hermite normal form algorithms via lattice basis reduction[END_REF][START_REF] Storjohann | Near optimal algorithms for computing smith normal forms of integer matrices[END_REF]. We will only record their existence. Theorem 2.2.12 ([12], Proposition 5.4). There exists a deterministic polynomialtime algorithm that, given a matrix A = (a i,j ) ∈ M n×m (Z), computes a matrix V ∈ GL m (Z) such that AV is in Hermite normal form. Note 2.2.13. Theorem 2.2.12 can also be obtained from Theorem 2.1.6 if we equip L(A) with a suitable "length function" q : L → R (see [START_REF] Lenstra | Lattices. In Algorithmic number theory: lattices, number fields, curves and cryptography[END_REF], Section 14).

The second canonical form we wish to examine is the Smith normal form. Definition 2.2.14. Let A = (a i,j ) ∈ M n×m (Z), for some m, n ∈ Z ≥0 . Then A is said to be in Smith normal form (SNF) if there exists 0 ≤ k ≤ min{n, m} such that the last nk rows and the last mk columns are zero and the matrix (a i,j ) k,k i=1,j=1 is diagonal, with a i,i > 0 for all 1 ≤ i ≤ k, and a i,i | a i+1,i+1 for all 1 ≤ i < k. Note 2.2.15. The nonzero entries are called elementary divisors of A.

The following is a standard result. Proposition 2.2.16. Every integer matrix has a unique Smith normal form, i.e. if A = (a i,j ) ∈ M n×m (Z), then there exist matrices

U ∈ GL n (Z) and V ∈ GL m (Z) such that U AV is in Smith normal form. If there exist other U ∈ GL n (Z) and V ∈ GL m (Z) such that U AV is in Smith normal form, then U AV = U AV .
Theorem 2.2.17 ([86], Section 8.2). There exists a deterministic polynomial-time algorithm that, given a matrix A = (a i,j ) ∈ M n×m (Z), computes the Smith normal form of A, together with transformation matrices U ∈ GL n (Z) and V ∈ GL m (Z).

The relevance of the Hermite and Smith normal forms to the study of finitely generated abelian groups lies in the following theorem.

Theorem 2.2.18. Let n ∈ Z >0 . Suppose H ⊆ Z n is a subgroup.
(i) There exists a unique full column rank matrix A in Hermite normal form such that H is generated over Z by the columns of A. (ii) If H has rank n, then there exists a unique square matrix A in Smith normal form such that

Z n /H ∼ = n i=1 Z/d i Z, (2.1)
as Z-modules, where d 1 , . . . , d n are the elementary divisors of A.

Proof. Part (i) is a consequence of Propositions 2.2.4 and 2.2.9. For a proof of part (ii), see Theorem 2.4.13 of [START_REF] Cohen | A Course in Computational Algebraic Number Theory[END_REF].

Representing objects and basic constructions

Given that we wish to bound the running time of an algorithm in terms of the length of the input, it is of crucial importance to make clear how we represent objects inside algorithms. Different representations may lead to essentially different computational tasks, with different complexities.

There are several ways to represent groups inside an algorithm. These include giving a finite presentation, giving the group as a permutation group of a finite set or a matrix group over a ring, black-box representations, or giving the group as automorphisms of certain objects (e.g. graphs, field extensions). For more details on group representations and the algorithmic problems they give rise to, see [START_REF] Hitz | Computer Algebra Handbook: Foundations • Applications • Systems[END_REF]38].

For finitely generated abelian groups, matters simplify greatly, since these are nothing else than Z-modules and thus can be represented by matrices.

Representing finite and finitely generated abelian groups

The proof of the following result can be found in any introductory algebra textbook.

Theorem 2.3.1. Let G be a finitely generated abelian group. Then:

(i) There exists k ∈ Z ≥0 such that G ∼ = Z k ⊕ H, where H is a finite abelian group. (ii) If G is finite, then there exist n ∈ Z >0 and a subgroup L ⊆ Z n of rank n, such that G ∼ = Z n /L. (iii) (Fundamental Theorem of Finite Abelian Groups) If G is finite,
G ∼ = t i=1 Z/d i Z.
To represent a group G, we give the algorithm a set of generators and relations. More precisely, suppose G has generators x 1 , . . . , x n and relations in G are of the form n i=1 a ij x i for 1 ≤ j ≤ m, where a ij ∈ Z for all i, j. Then the matrix f = (a ij ) ∈ M n×m (Z) is said to be a presentation matrix of G. Consider the exact sequence

Z m f -→ Z n → coker(f ) → 0,
Then coker(f ) ∼ = G and an element g ∈ coker(f ) corresponds, in a non-unique way, to a vector in Z n mapping to g, i.e. it is specified as a Z-linear combination of generators. Proof. This follows from Theorem 2.2.18, Theorem 2.3.1.

From now on, given a presentation matrix f for a finitely generated abelian group G, we will identify G with coker(f ).

Group homomorphisms

Let G 1 , G 2 be two finitely generated abelian groups. Suppose G 1 and G 2 are represented by triples (m 1 , n 1 , f 1 ) and (m 2 , n 2 , f 2 ) respectively. Then we have two exact sequences:

Z m1 Z n1 G 1 0 Z m2 Z n2 G 2 0. f1 π1 f2 π2 Any group homomorphism G 1 → G 2 is induced by a map Z n1 → Z n2
. This is the same as saying that a group homomorphism is determined by the images of the generators. However, not all assignments of generators correspond to well-defined group homomorphisms. That is to say, not every map g : Z n1 → Z n2 gives rise to a group homomorphism g :

G 1 → G 2 .
Proposition 2.3.4. There exists a deterministic polynomial-time algorithm that, given two finitely generated abelian groups G 1 and G 2 , represented by triples (m 1 , n 1 , f 1 ) and (m 2 , n 2 , f 2 ) respectively, and a map g : Z n1 → Z n2 , decides whether or not g induces a group homomorphism g :

G 1 → G 2 .
Proof. The map induced by g takes an element of G 1 , lifts it to Z n1 and then maps it to G 2 under π 2 • g. For this to be a well-defined group homomorphism, we must ensure that it is independent of the lift to Z n1 we choose. For this, we require that im(f 1 ) ⊆ ker(π 2 • g), or equivalently, im(g

• f 1 ) ⊆ im(f 2 )
. By Theorem 2.1.6 and Corollary 2.1.9, we can compute kernels and images, and test for inclusion, so, given a map g :

Z n1 → Z n2 , we can test if g induces a group homomorphism G 1 → G 2 by checking whether im(g • f 1 ) ⊆ im(f 2 ). Note 2.3.5. The condition im(g • f 1 ) ⊆ im(f 2 ) is equivalent to the existence of a map h : Z m1 → Z m2 such that g • f 1 = f 2 • h.
Once we have ensured that we have a well-defined group homomorphism, we may test whether it is injective or surjective. Proposition 2.3.6. There exists a deterministic polynomial-time algorithm that, given two finitely generated abelian groups G 1 and G 2 , represented by triples (m 1 , n 1 , f 1 ) and (m 2 , n 2 , f 2 ) respectively, and a map g : Z n1 → Z n2 inducing a group homomorphism g : G 1 → G 2 , decides whether g is injective.

Proof. For g to be injective, we require that for all x ∈ Z n1 , if g(x) ∈ im(f 2 ), then x ∈ im(f 1 ), or equivalently, that im(f 1 ) ⊇ g -1 (im(f 2 )).

To express this condition in terms of the maps that are part of the input, i.e. in terms of f 1 , f 2 and g, consider the map

-f 2 + g : Z m2 ⊕ Z n1 → Z n2 , (x, y) → -f 2 (x) + g(y).
(2.2)

Let p 2 : Z m2 ⊕ Z n1 → Z n1 be the projection map to the second component. It is easy to see that

g -1 (im(f 2 )) = p 2 (ker(-f 2 + g)).
Thus, the condition for injectivity becomes

p 2 (ker(-f 2 + g)) ⊆ im f 1 ,
which can be tested deterministically in polynomial time using Theorem 2.1.6 and Corollary 2.1.9.

Proposition 2.3.7. There exists a deterministic polynomial-time algorithm that, given two finitely generated abelian groups G 1 and G 2 , represented by triples (m 1 , n 1 , f 1 ) and (m 2 , n 2 , f 2 ) respectively, and a map g : Z n1 → Z n2 inducing a group homomorphism g : G 1 → G 2 , decides whether g is surjective.

Proof. For g : G 1 → G 2 to be surjective, we require that for all x ∈ G 2 = Z n2 / im(f 2 ), there exist y ∈ Z n1 such that π 2 • g(y) = x. This is equivalent to requiring that

∀x ∈ Z n2 , ∃y ∈ Z n1 such that g(y) -x ∈ im(f 2 ),
which is further equivalent to the map -f 2 + g defined in (2.2), being surjective. We can check this using Theorem 2.1.6.

Proposition 2.3.8. There exists a deterministic polynomial-time algorithm that, given two finitely generated abelian groups G 1 and G 2 , represented by triples (m 1 , n 1 , f 1 ) and (m 2 , n 2 , f 2 ) respectively, and two maps g, h :

Z n1 → Z n2 inducing group homo- morphisms g, h : G 1 → G 2 , decides whether g = h.
Proof. The problem of deciding if two group homomorphisms are equal is equivalent to deciding if a given group homomorphism is the zero homomorphism. Let g : G 1 → G 2 be a group homomorphism induced by the map g : Z n1 → Z n2 . Then g ≡ 0 if and only if im(g) ⊆ im(f 2 ).

Subgroups and quotients

Representing subgroups

Let G be a finitely generated abelian group. Let S = {s 1 , . . . , s t } ⊂ Z n be a set of representatives of the elements of S in G. Consider the map g : Z t → Z n given by e i → s i , where for 1 ≤ i ≤ t, the vector e i is the i th canonical basis element of Z t :

Z t Z m Z n G 0. g f π f (2.3) Consider the map (-f + g) : Z m ⊕ Z t → Z n , given by (x, y) → -f (x) + g(y). Compute ker(-f + g) = {(x, y) ∈ Z m ⊕ Z t | f (x) = g(y)
} and project it to Z t via a map p. Put r := rank(ker(-f + g)) and let φ be the matrix whose columns are the basis vectors of ker(-f + g). The following diagram illustrates what was described above:

Z r ker(-f + g) Z t H 0 Z m ⊕ Z t Z m Z n G 0. φ ∼ h p g π h i -f +g f π f Put h := p • φ.
Then (r, t, h) represents H. Note that t is not necessarily the minimum number of generators of H. The map g induces a map i : H → G in the following way: an element of H = Z t / im(h) is lifted to Z t and then is mapped to G. We claim that i : H → G is an injective group homomorphism.

First we show that i is independent of the chosen lift to Z t . Let x ∈ H and lift it to x + k ∈ Z t , for some k ∈ im(h). Then g(x + k) = g(x) + g(k). But, since k ∈ im(h), it follows that k is the image under p of some (y, k) ∈ ker(-f + g), with y ∈ Z m . Then g(k) = f (y). Hence π f g(k) = 0 and so g does not depend on the lift.

For injectivity, suppose i(y) = 0 G , for some y ∈ H, where 0 G denotes the zero element in G. Let y be a lift of y to Z t . Then π f (g(y)) = 0 G , so g(y) = f (x), for some x ∈ Z t . But then (x, y) ∈ ker(-f + g) and so y ∈ im(p), i.e. y = 0 H . Moreover, by construction, im(i) = {s i } = H, where s i := π f (s i ).

Example 2.3.11. Let G be any group. If S = ∅, then t = 0, and H = 0, as expected.

Example 2.3.12. Let G = Z/2Z ⊕ Z/4Z ⊕ Z/4Z. (i) Let S = {(1, 1, 2)}. Then H := S ∼ = Z/4Z. The map g -f : Z 3 ⊕ Z → Z 3 is given by (x 1 , x 2 , x 3 , y) → (y -2x 1 , y -4x 2 , 2y -4x 3 ), so ker(g -f ) = (2, 1, 2, 4)Z.
Hence im(π) = 4Z and the subgroup H is given by (1, 1, 4

• id). (ii) Let S = {(1, 1, 2), (0, 2, 0)}. Again, H := S ∼ = Z/4Z. The map g-f : Z 3 ⊕Z 2 → Z 3 is given by (x 1 , x 2 , x 3 , y 1 , y 2 ) → (2y 1 -4x 1 , y 1 + 2y 2 -4x 2 , 2y 1 -4x 3 ), so ker(g -f ) = (1, 0, 1, 2, 1)Z ⊕ (0, 1, 0, 0, 2)Z. Hence im(π) = (2, 1)Z ⊕ (0, 2)Z and
the subgroup H is given by (2, 2, h), where h is the map represented by the matrix 2 1 0 2 .

It can be checked that the Smith normal form of this matrix has diagonal (4, 1), so (2, 2, h) indeed represents the cyclic group of order 4.

Representing quotients

Let G be a finitely generated abelian group and let H ≤ G be a subgroup. To represent the quotient G/H, we need to represent it as a group, which we denote by Q, and additionally, to produce a surjection j : G

Q. Then Q ∼ = G/H.
Z r Z m Z s ⊕ Z m Z s Z n Z n 0 H G Q 0 0 0 0 . h f g+f g id π g+f i j
Then G/H is represented by triple (s + m, n, g + f ). The map g + f induces a map j : G → Q in the following way: an element of G = Z n / im(f ) is lifted to Z n and then mapped to Q via π g+f • id. We claim that this map is a surjective group homomorphism.

To see that it is well-defined, let x ∈ G and a consider a lift of x to Z n given by x + f (y), for some y ∈ Z m . Since f (y) ∈ im(g + f ) by construction, it is sent to zero under π g+f . Hence j is independent of the choice of lift. Surjectivity follows by construction.

Example 2.3.14. Let G = Z/2Z ⊕ Z/4Z. Let H 1 = Z/2Z ⊕ Z/2Z. Then the quotient G/H 1 is given by data Z ⊕ Z Z ⊕ Z (Z ⊕ Z) ⊕ (Z ⊕ Z) 0 Z ⊕ Z Z ⊕ Z Z ⊕ Z 0 0 H 1 G Z/2Z 0 0 0 0 .   2 0 0 2     2 0 0 4     1 0 0 2  
The presentation matrix for G/H 1 is

f G/H1 = 1 0 2 0 0 2 0 4 ,
whose Smith normal form has nonzero entries (2 1), and so G/H 1 ∼ = Z/2Z.

If we let H 2 = Z/4Z, the quotient G/H 2 is given by data where g : G 1 → G 2 is the group homomorphism induced by g.

Z Z ⊕ Z Z ⊕ (Z ⊕ Z) 0 Z Z ⊕ Z Z ⊕ Z 0 0 H 2 G Z/2Z 0 0 0 0 . (4)   2 0 0 4     0 1   Then the presentation matrix for G/H 2 is f G/H2 = 0
Proof. Kernels can be computed as:

ker(G 1 → G 2 ) = ker (Z n1 / im(f 1 ) -→ Z n2 / im(f 2 )) = {x ∈ Z n1 | π 2 • g(x) = 0}/ im(f 1 ) = ker(π 2 • g)/ im(f 1 ) = p 2 (ker(-f 2 + g))/ im(f 1 ).
Images can be computed as:

im(G 1 → G 2 ) = im(π 2 • g) = im(g)/(im(g) ∩ im(f 2 )) = im(-f 2 + g)/ im(f 2 ).
Cokernels can be computed as:

coker(G 1 → G 2 ) = G 2 / im(G 1 → G 2 ) = (Z n2 / im(f 2 )) / (im(-f 2 + g)/ im(f 2 )) = coker(-f 2 + g).
All these computations can be carried out in polynomial time by Theorem

F = f 1 0 0 f 2 .

Homomorphism groups and tensor products

In the case of free abelian groups of finite rank, the tensor product is easy to construct: if {x i } n i=1 is a basis for Z n and {y i } m i=1 is a basis for Z m , then the set {x i ⊗ y j | 1 ≤ i, j ≤ n} is a basis for Z n ⊗ Z m . Constructing homomorphism groups of free abelian groups of finite rank is also easy, since Hom(Z m , Z n ) = M n×m (Z).

Suppose now that G 1 , G 2 are two finitely generated abelian groups with presentations

Z m1 Z n1 G 1 0 f1 (2.4)
and

Z m2 Z n2 G 2 0 f2 (2.5)
respectively.

Proposition 2.4.1. There exists a deterministic polynomial-time algorithm that, given two finitely generated abelian groups G 1 , G 2 , computes

(i) the tensor product, G 1 ⊗ G 2 , together with the corresponding bilinear map G 1 × G 2 → G 1 ⊗ G 2 , (ii) the homomorphism group, Hom(G 1 , G 2 ), together with the corresponding bilin- ear map Hom(G 1 , G 2 ) × G 1 → G 2 .
Proof. Suppose G 1 , G 2 have presentations (2.4) and (2.5), respectively. Recall that tensoring is right-exact, so tensoring (2.4) with G 2 and tensoring (2.5) with Z m1 and Z n1 gives

Z m1 ⊗ Z m2 Z n1 ⊗ Z m2 Z m1 ⊗ Z n2 Z n1 ⊗ Z n2 Z m1 ⊗ G 2 Z n1 ⊗ G 2 G 1 ⊗ G 2 0. 0 0
By construction of quotient groups (Theorem 2.3.13), it follows that G 1 ⊗ G 2 has presentation given by

(Z m1 ⊗ Z n2 ) ⊕ (Z n1 ⊗ Z m2 ) Z n1 ⊗ Z n2 G 1 ⊗ G 2 0,
where the first map is given by (f

1 ⊗ id) + (id ⊗f 2 ). Applying Hom(-, G 2 ) to (2.4) gives 0 Hom(G 1 , G 2 ) Hom(Z n1 , G 2 ) Hom(Z m1 , G 2 ). Hence Hom(G 1 , G 2 ) = ker Hom(Z n1 , G 2 ) •f1 --→ Hom(Z m1 , G 2 ), h → h • f 1 ,
which can be computed using Proposition 2.3.15. Now, for k ∈ Z ≥0 , we have that Hom(Z k , -) is an exact functor, so

Hom(Z k , G 2 ) = coker Hom(Z k , Z m2 ) f2• --→ Hom(Z k , Z n2 ), h → f 2 • h ,
which we compute for k equal to n 1 and m 1 .

The bilinear maps

G 1 ×G 2 → G 1 ⊗G 2 and Hom(G 1 , G 2 )×G 1 → G 2 are
represented by listing the images of all pairs of generators, and can be readily obtained from the above construction.

Splitting exact sequences

Consider an exact sequence of finitely generated abelian groups

0 H G K 0. i p (2.6)
Proposition 2.5.1. There exists a deterministic polynomial-time algorithm that, given an exact sequence as in (2.6), decides if it is split, and if it is split, produces a right-inverse of p and a left-inverse of i.

Proof. We consider the map

ψ : Hom(K, G) → Hom(K, K), k → p • k.
Deciding if the sequence is split reduces to deciding if id K is in the image of ψ. This can be done by solving a system of linear equations over Z (Theorem 2.1.7). If the system has a solution, solving it will also produces a right inverse of p, i.e. an element s ∈ Hom(K, G) such that ψ(s) = id K . Similarly, we construct a left-inverse of i.

Note 2.5.2. Suppose that the exact sequence (2.6) is right-split, i.e. there exists a group homomorphism s : K → G such that p • s = id K . Moreover, suppose that we have found such an s. Then we know that G = i(H) ⊕ s(K), and we can construct images of group homomorphism and direct sums of groups. The isomorphism

H ⊕ K ∼ -→ G is given by (h, k) → i(h) + s(k), with inverse G ∼ -→ H ⊕ K given by g → (t(h), p(k)),

Computing the torsion subgroup of a finitely generated abelian group

Suppose we are given a finitely generated abelian group G. We have seen that we can determine if G is finite or not. If we find that it is not finite, we would like to find its torsion subgroup. To do this, we introduce a construction described in [START_REF] Lenstra | Lattices. In Algorithmic number theory: lattices, number fields, curves and cryptography[END_REF], at the end of Section 14.

Theorem 2.6.2. There exists a deterministic polynomial-time algorithm that, given a finitely generated abelian group G, determines its torsion subgroup T , and produces an isomorphism

G ∼ = T ⊕ G/T .
Proof. Suppose G is represented by triple (m, n, f ). Let L := Z n and H = im(f ) ⊆ Z n . Suppose H ∼ = Z k and let F ∈ M n×k (Z) be a matrix whose columns are a Z-basis of H. Consider the map

φ : L → Hom(H, Z), φ(x)(y) = x, y ,
for x ∈ L, y ∈ H and •, • the standard inner product. Then φ is represented by the matrix F t ∈ M k×n (Z). This is because x, y = y t F t x, for any x ∈ L, y ∈ H. We denote the kernel of this map by

H ⊥ := {x ∈ L | x, H = 0}.
Since H ⊥ is the kernel of a map between two free Z-modules, Theorem 2.1.6 produces for us a basis b

1 . . . , b n of L, where b 1 , . . . , b n-k is a Z-basis of H ⊥ .
We repeat the process above by considering the map

φ : L → Hom(H ⊥ , Z),
where the matrix representing φ is given by the transpose of the matrix whose columns are b 1 , . . . , b n-k . We denote the kernel of this map by

H ⊥⊥ := {a ∈ L | a, H ⊥ = 0} = (Q • H) ∩ L. (2.7) Thus, L/H ⊥⊥ ∼ = (L/H) (L/H) tor ,
where (L/H) tor denotes the torsion subgroup of L/H. Our goal becomes to split the exact sequence 0

H ⊥⊥ /H L/H L/H ⊥⊥ 0, (2.8)
which we do using Proposition 2.5.1.

Computing the order of a group element

Theorem 2.6.3. There exists a deterministic polynomial-time algorithm that, given a finitely generated abelian group G and an element g ∈ G, determines the order of g.

Proof. Consider the map ψ : Z → G, given by 1 → g. If ψ is injective, which we can test, then g has infinite order. Otherwise, ker(ψ) is of the form lZ, giving the order of g in G as equal to l.

Note 2.6.4. This result depends heavily on the way we are representing G. Suppose G = (Z/nZ) × , for some n ∈ Z >2 . Suppose we choose to represent G by only giving the integer n. Then we can certainly carry out computations in G, but given the element 2 ∈ G, we cannot in general efficiently compute its order without knowing the factorisation of n, and even then it is hard.

We can use this tool to decide if two elements are equal, by simply determining if their difference is equal to the zero element, i.e. if it has order 1.

Corollary 2.6.5. There exists a deterministic polynomial-time algorithm that, given a finitely generated abelian group G and an element g ∈ G, determines if g = 0 G . Corollary 2.6.6. There exists a deterministic polynomial-time algorithm that, given a finitely generated abelian group G and two elements g, h ∈ G, determines if g = h.

Computing the exponent of a group

The exponent of a group G is computable as the generator over Z of

ker (Z → Hom(G, G), n → (x → nx)) .
However, it is also useful to be able to exhibit an element of G of order equal to the exponent of G. To do this, we begin with a couple of preliminary results. Lemma 2.6.7. There exists a deterministic polynomial-time algorithm that, given a finite abelian group G and two elements x, y ∈ G of orders n and m respectively, outputs an element z, expressed in terms of x and y, of order equal to lcm(n, m).

Proof. Using Theorem 2.6.3, compute n and m, the orders of x and y, respectively. Apply the Coprime Base Algorithm (Theorem 1. Proof. Let e 1 , . . . , e n be the respective orders of b 1 + H, . . . , b n + H in L/H. Let l = lcm i ({e i }). By Lemma 2.6.7, there exists an element of L/H of order equal to l, so exp(L/H) ≥ l. Moreover, since B is a basis of L, every x ∈ L/H is of the form i α i b i + H, for some α i ∈ Z. Then lx ∈ H, so x has order dividing l. Hence exp(L/H) = l.

This now enables us to compute the exponent of any given finite abelian group.

Theorem 2.6.9. There exists a deterministic polynomial-time algorithm such that, given a finite abelian group G, computes the exponent of G and produces an element g ∈ G of order equal to the exponent.

Proof. We begin by determining the order of all basis vectors of L in L/H using Theorem 2.6.3. This gives a sequence of integers whose lowest common multiple is the exponent of L/H. Applying Proposition 2.6.7 repeatedly, we produce an element with the required property.

Writing a finitely generated abelian group as a direct sum of cyclic groups

Let G be a finite abelian group of exponent n. Then we have seen that there exists g ∈ G such that the order of g is n. Moreover, for any such g, the cyclic subgroup generated by it is a direct summand of G. This suggests a method of decomposing a finite abelian group into a direct sum of cyclic subgroups by computing the exponent of the group, producing an element of that order, quotienting out by the subgroup it generates and repeating the process for the remaining part.

Theorem 2.6.10. There exists a deterministic polynomial-time algorithm that, given a finite abelian group G, produces a direct-sum-decomposition of G into cyclic subgroups.

Proof. Suppose G is represented by triple (m, n, f ), and put L := Z n and H := im(f ).

Then G = L/H. By Theorem 2.6.9, we can compute e 1 , the exponent of G, and produce an element x 1 ∈ G of order e 1 . The subgroup generated by x 1 is now a direct summand of G. We would now like to determine a subgroup

G 2 ≤ G such that G ∼ = G 2 ⊕ Z/e 1 Z.
To do this, apply Proposition 2.5.1 to the exact sequence

0 → Z/e 1 Z → G → G/Zx 1 → 0.
Now replace G by G 2 and repeat. In the end we will have produced a positive integer t ∈ Z >0 , a sequence of integers e 1 , . . . , e t ∈ Z >0 , a sequence of subgroups G 1 , . . . , G t ≤ G such that the exponent of G i is e i , and a sequence of elements x 1 , . . . , x t such that x i ∈ G i and the order of x i is equal to e i . Moreover, we have an isomorphism

G ψ ← - ∼ t i=1 Z/e i Z,
where ψ : 1 Z/eiZ → x i . The algorithm requires t ≤ log 2 |G| iterations.

Note 2.6.11. Another way to obtain a decomposition of G into cyclic subgroups is to apply Theorem 2.2.17 to the presentation matrix of G.

Homomorphism groups and tensor products reconsidered

We have already seen how to compute tensor products and homomorphism groups, without knowing a cyclic direct sum decomposition of the groups involved. The disadvantage of that approach is that the number of generators produced by the algorithm can get unnecessarily large. In this section we construct tensor products and homomorphism groups of finite abelian groups by making use of the fact that we can compute a cyclic direct sum decomposition.

Suppose

G 1 ∼ = t1 i=1 Z/c i Z and G 2 ∼ = t2 j=1 Z/d i Z, (2.9)
for some t 1 , t 2 ∈ Z >0 and c i , d j ∈ Z >0 , for all 1 ≤ i ≤ t 1 and 1 ≤ j ≤ t 2 .

Let n, m ∈ Z >0 and d := gcd(n, m). Then we have an isomorphism

Z/nZ ⊗ Z/mZ ∼ -→ Z/dZ, x ⊗ y → xy.
Similarly, every group homomorphism φ : Z/nZ → Z/mZ is determined by the image of 1 in Z/mZ, which must be a multiple of m d . This is because

nφ(1) = φ(n) ≡ 0 mod m,
and so n d φ(1) ≡ 0 mod m d .

Since n/d and m/d are coprime, it must be the case that φ(1) ≡ 0 mod m d . Hence we have an isomorphism

Hom(Z/nZ, Z/mZ) ∼ -→ Z/ gcd(n, m)Z, φ → m d -1
φ(1).

Proposition 2.7.1. There exists a deterministic polynomial-time algorithm that, given two finite abelian groups G 1 , G 2 via direct-sum representations as in (2.9), computes

(i) the tensor product, G 1 ⊗ G 2 , together with the corresponding bilinear map G 1 × G 2 → G 1 ⊗ G 2 , (ii) the homomorphism group, Hom(G 1 , G 2 ), together with the corresponding bilin- ear map Hom(G 1 , G 2 ) × G 1 → G 2 .
Proof. Note that one can always obtain a direct-sum representation using Theorem 2.2.17. We then have that

G 1 ⊗ G 2 ∼ = t1 i=1 Z/c i Z ⊗   t2 j=1 Z/d i Z   ∼ = t1,t2 i,j=1 (Z/c i Z ⊗ Z/d j Z) ∼ = t1,t2 i,j=1 Z/gcd(c i , d j )Z,
and all isomorphisms occurring are known and computable. Similarly,

Hom(G 1 , G 2 ) ∼ = Hom   t1 i=1 Z/c i Z, t2 j=1 Z/d i Z   ∼ = t1,t2 i,j=1 Hom(Z/c i Z, Z/d j Z) ∼ = t1,t2 i,j=1 Z/ gcd(c i , d j )Z,
and all isomorphisms occurring are known and computable.

Projective Z/mZ-modules

We have seen in Proposition 1.6.8, what the projective modules over Z/mZ are, for m ∈ Z >0 . Suppose now we are given a finite abelian group A 1 and we would like to find the largest integer m | exp(A 1 ) such that A 1 /mA 1 is projective as a module over Z/mZ. Proposition 2.8.1. There exists a deterministic polynomial-time algorithm that, given a finite abelian group A 1 computes the largest integer m ∈ Z >0 such that m | exp(A 1 ) and A 1 /mA 1 is projective as a Z/mZ-module.

Proof. Suppose

A 1 ∼ = p∈P a∈Z>0

(Z/p a Z) na,p , where P is a set of pairwise coprime integers greater than 1 and n a,p ∈ Z ≥0 . Note that this is a situation we can reduce to if we first compute a decomposition of A 1 as a direct sum of cyclic subgroups using Theorem 2.6.10 and then apply the Coprime Base Algorithm (Theorem 1.1.2) to the set of sizes of these cyclic components. For each p ∈ P, set

α p = min{a | n a,p = 0}, if ∃a s. t. n a,p = 0 0, otherwise . Let m = p∈P p αp .
Then

A 1 /mA 1 ∼ = p∈P (Z/p αp Z) a na,p ,
so is projective as a Z/mZ-module. This value of m is the largest possible. To see this, it is enough to consider the case when P = {p} for some p ∈ Z >1 . Suppose m = p βp , where β p is a positive integer larger than α p . Then A 1 /mA 1 will have Z/p αp Z as a direct summand and thus cannot be projective as a Z/mZ-module.

To see maximality of m graphically, let p be a prime and consider the p-group A 1 = t i=1 Z/p ei Z, where e i ≤ e i+1 and e 1 > 0. We represent A 1 by the following diagram:

p e1 p et . (2.10)
The number of vertical boxes is equal to the number of cyclic direct summands of A 1 and the height of each such box proportional to the length of the cyclic group it represents.

To make this into a free module, we need to "cut out a rectangle", so we need to cut along the smallest invariant, p e1 , or along any other p e , for e ≤ e 1 :

p et p e1 .
The remaining part is isomorphic to (Z/p e1 Z) t as an abelian group.

Suppose A 2 is a finite abelian group and we want to find the least integer m | exp(A 2 ) such that

A 2 /A 2 [m ] is projective over Z/ exp(A2) m Z, where A 2 [m ] = ker(A 2 → A 2 , x → m x).
Proposition 2.8.2. There exists a deterministic polynomial-time algorithm that, given a finite abelian group A 2 of exponent m, for some

m ∈ Z >0 , computes the smallest m | m such that A 2 /A 2 [m ] is projective over Z/ m m Z. Proof. Suppose A 2 ∼ = q∈Q b∈Z>0 Z/q b Z n b,q , (2.11)
where Q is a set of coprime integers greater than 1 and n b,q ∈ Z ≥0 . For each q ∈ Q, let µ(q) = max{b | n b,q = 0}, if ∃b s.t. n b,q = 0 0, otherwise, and α(q) = max{{b | n b,q = 0}\µ(q)}, if ∃b s.t. n b,q = 0 and b = µ(q) 0, otherwise.

Then µ(q) is the largest power of q occurring as the exponent of one of the cyclic groups in the direct sum (2.11), and α(q) is the second largest power of q occurring. Set m = q∈Q q α(q) .

Then A 2 /A 2 [m ] = q∈Q Z/q α(q) Z n µ(q),q
, where n 0,q := 0. This value of m is the smallest possible. To see this, it is enough to consider the case when Q = {p}, for some p ∈ Z >1 . Suppose m = β(p), where β(q) is a positive integer smaller than α(q). Then A 2 /A 2 [m] will have Z/p α(q)-β(q) Z as a direct summand, and thus cannot be projective as a Z/ m m Z-module. To see minimality of m graphically, reduce again to the p-group case. Suppose A 2 = t i=1 Z/p ei Z, where e i ≤ e i+1 and e 1 > 0, and suppose that there are k copies of Z/p et Z in this sum. Then A 2 is represented by a diagram like in (2.10). This time however, to get a rectangle, we do not cut along the smallest invariant, but along the second largest one:

p et p et p α(p) p et-α(p)
.

The remaining part is represented by the upper-left rectangle left unhatched, and is isomorphic to (Z/p et-α(p) Z) k .

Chapter 3

Linear algebra over Z: basic algorithms for finite rings

We have seen in the previous chapter how to represent and carry out basic computations with finite abelian groups. This enables us to deal with the underlying additive group of a finite ring, which is crucial for all our algorithms. This chapter is a compendium of basic algorithms to do with finite rings.

We will represent finite rings using "basis representations" and describe algorithms that accomplish the following tasks:

1. compute homomorphism groups between two finite modules over a finite ring, 2. compute the ideal generated by a given set of elements, 3. compute sums, products and intersections of ideals, 4. compute the quotient of a finite ring by a two-sided ideal, 5. compute the characteristic, centre and prime subring of a finite ring.

We will also look at the problem of computing the Jacobson radical of a ring. In the case where the given ring is a finite-dimensional algebra over a field, this can be accomplished deterministically in polynomial time ( [START_REF] Friedl | Polynomial time solutions of some problems of computational algebra[END_REF][START_REF] Rónyai | Computing the structure of finite algebras[END_REF]). However, in general, such a result cannot be expected, in view of our inability to compute the largest square divisor of an integer.

Finally, we will briefly look at some other known algorithms for finite rings, and some open algorithmic questions.

Representing objects and basic constructions 3.1.1 Representing rings and modules

To represent finite rings inside algorithms, we will use basis representations. These are considered to be the "right" representations for complexity considerations, since they are neither too verbose (so as to make all problems quasipolynomial), nor too compact (so as to make all problems NP-hard). For more on the different representations and the complexity of problems on different representations, see [START_REF] Agrawal | Automorphisms of finite rings and applications to complexity of problems[END_REF][START_REF] Arvind | The complexity of black-box ring problems[END_REF][START_REF] Kayal | On the ring isomorphism and automorphism problems[END_REF][START_REF] Kayal | Complexity of ring morphism problems[END_REF].

Definition 3.1.1. Let R be a finite ring. A basis representation of R consists of a sequence of integers d 1 , . . . , d t ∈ Z >1 , for some t ∈ Z ≥0 such that R + ∼ = t i=1 (Z/d i Z), (3.1)
together with a bilinear map

σ : R + × R + → R + (3.2)
(e i , e j ) → e i e j ,

where e i is a generator of the cyclic subgroup Z/d i Z, for 1 ≤ i ≤ t, and we express e i e j linearly in terms of {e i }, i.e. for each 1 ≤ i, j ≤ t we give a sequence a ijk ∈ Z/d k Z, for 1 ≤ k ≤ t, such that e i e j = t k=1 a ijk e k .

Note 3.1.2. We have established in Definition 2.3.2 that the default representation of a finite abelian group is the exact-sequence representation. However, by the results of Section 2.6.5, we may assume that R + is in fact given by a direct-sum decomposition into cyclic groups.

Note 3.1.3. The map σ in (3.2) will be referred to as the multiplication map of R. Specifying σ amounts to giving t 3 integers a ijk , which are called structure constants.

Note 3.1.4. Given d 1 , . . . , d t and a sequence of t 3 integers, a ijk , we can check in polynomial time whether they define a ring. This amounts to checking a series of equalities and solving systems of linear equations over Z.

Note 3.1.5. The size of a basis representation is equal to

t i=1 log 2 (d i ) • t 2 = log 2 (|R|) • t 2 ≤ log 3 2 (|R|), (3.4)
since t ≤ log 2 (|R|). Thus, when we say an algorithm with input R runs in polynomial time, we mean that the number of bit operations is bounded above by (log

2 (2 + |R|)) C ,
for some constant C. The 2 is added in order to accommodate the zero ring.

To input a finite module, we give a finite abelian group (M, +) and a bilinear map

α : R + × M → M, (3.5)
which describes the action of R on M . For every additive generator of R and M , we express the image in terms of the additive generators of M .

Representing ring and module homomorphisms

Let R 1 and R 2 be two finite rings. A ring homomorphism ρ : R 1 → R 2 is a homomorphism of the underlying abelian groups that sends the unit element of R 1 to the unit element of R 2 and respects the multiplicative structure of the rings, i.e. for all r, s ∈ R 1 , we have that ρ(rs) = ρ(r)ρ(s).

(3.6) Proposition 3.1.6. There exists a deterministic polynomial-time algorithm that, given two finite rings R 1 and R 2 , and a group homomorphism ρ : R + 1 → R + 2 , decides whether ρ is a ring homomorphism, and if it is, decides whether it is injective or surjective.

Proof. As in Section 2.3.2, the map φ is given by a matrix which specifies the image of each additive generator of R 1 as a linear combination of additive generators of R 2 . Given such a matrix, we can easily check if it induces a homomorphism of rings, by verifying that the induced map preserves multiplication and sends the unit element of one ring to the unit element of the other. This amounts to checking equalities over Z. By Propositions 2.3.6 and 2.3.7, we can also check for injectivity or surjectivity.

Let R be a ring and M, N two R-modules. A module homomorphism φ : M → N is a homomorphism of abelian groups which is R-linear, i.e. for all r ∈ R, m ∈ M , we have that φ(rm) = rφ(m).

(3.7)

Proposition 3.1.7. There exists a deterministic polynomial-time algorithm that, given a finite ring R, two R-modules M and N , and a group homomorphism φ : M → N , decides whether φ is an R-module homomorphism, and if it is, decides whether it is injective or surjective.

Proof. As in Chapter 2, Section 2.3.2, the map φ is given by a matrix which specifies the image of each additive generator of M as a linear combination of additive generators of N . Given such a matrix, we can easily check if it induces a module homomorphism by verifying that the induced map preserves scalar multiplication. This amounts to checking equalities over Z. By Propositions 2.3.6 and 2.3.7, we can also check for injectivity or surjectivity.

Homomorphism group

Proposition 3.1.8. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M 1 and M 2 , computes the homomorphism group Hom R (M 1 , M 2 ).

Proof. We can certainly compute Hom Z (M 1 , M 2 ). Then

Hom R (M 1 , M 2 ) = {f ∈ Hom Z (M 1 , M 2 ) | f (rx) = rf (x), ∀r ∈ R, ∀x ∈ M 1 }. (3.8)
It is enough to ensure that the relation f (rx) = rf (x) holds for the additive generators of R and M 1 . Consider the map

Hom Z (M 1 , M 2 ) → r additive generator of R x additive generator of M1 M 2 f → (f (rx) -rf (x)) r,x .
Then Hom R (M 1 , M 2 ) is the kernel of this map, which we can compute.

Computations with ideals

Let R be a ring. A left ideal I is, in particular, a left R-module, so it is given to the algorithm as an additive subgroup of R, together with a map R × I → I, as in (3.5).

Right ideals and two-sided ideals are given in a similar way.

Computing the ideal generated by a given set of elements

Proposition 3.2.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a set S ⊂ R, computes the ideal generated by S in R.

Proof. Suppose S = {s 1 , . . . , s u }. The left ideal I, generated by S in R has underlying additive group generated by the set {e i s j | 1 ≤ i ≤ t, 1 ≤ j ≤ k}, which can be computed using Proposition 2.3.10. This will also produce an injective group homomorphism I → R specifying I + as a subgroup of R + . To determine the R-action, we look at the map σ : R + × R + → R + as in (3.2), giving the multiplicative structure of R. Suppose e i s j = Now we express this sum as a linear combination of the e i s j .

The right and two-sided ideals are dealt with in a similar manner.

Sum, product and intersection of ideals

Proposition 3.2.2. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two ideals I, J ⊂ R, computes the ideals I + J, I ∩ J and IJ.

Proof. Note that (I + J) + = I + + J + and (I ∩ J) + = I + ∩ J + , and the action of R is induced by the ring multiplication map σ (as in (3.2)). Suppose x 1 , . . . , x n is a set of additive generators of I and y 1 , . . . , y m is a set of additive generators of J. Recall that IJ ⊆ J. We have that

(IJ) + = {x i • y j } i,j Z , (3.10)
where the product x i • y j is computed by writing each x i and y j in terms of additive generators of R and then using the multiplication map σ to write each x i • y j as a linear combination of additive generators of R. The action of R on (IJ) + is again induced by σ.

The right and two-sided ideals are dealt with in a similar manner.

Quotient of ring and two-sided ideal

Proposition 3.2.3. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a two-sided ideal I, computes the quotient ring R/I.

Proof. Let I be a two-sided ideal of R. Then (R/I)

+ = R + /I + , (3.11)
which can be computed using Proposition 2.3.13. This will also produce a surjective group homomorphism R + (R/I) + . The multiplication map for R/I is induced by the multiplication map for R.

Computing the centre and the prime subring of a finite ring

Given a finite ring, we will often want to view it as an algebra over its centre or its prime subring. We show how to compute these.

Theorem 3.3.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R, computes its centre, prime subring and characteristic.

Proof. To compute the centre of a finite ring R, we consider the map

ψ : R + -→ r additive generator of R R + s -→ (rs -sr) r .
The centre of R is the kernel of ψ, which we can compute. Its ring structure is induced by σ, the map defining multiplication in R.

To compute the prime subring of a finite ring R, we consider the map

α : Z → R + , 1 → 1 R .
The prime subring of R is the image of α, which we can compute. The multiplication map is induced by σ.

The cardinality of the prime subring is the characteristic of R, which we can also compute by taking the lowest common multiple of the sizes of the cyclic direct summands of R + .

Computing the Jacobson radical

When dealing with problems concerning rings, it is often convenient to reduce to the semisimple case. When the ring at hand is left-artinian, this reduces to computing the Jacobson radical (see Theorem 1.4.9, part (iv)). Thus, the natural question to ask is if Jacobson radicals can be efficiently computed. For our purposes, the appropriate version of this question is whether the Jacobson radical of a finite ring can be computed deterministically in polynomial time.

If the given ring R is a finite-dimensional algebra over a "nice" field F, there do exist deterministic polynomial-time algorithms that compute the Jacobson radical of R (see [START_REF] Cohen | Finding the radical of an algebra of linear transformations[END_REF][START_REF] Friedl | Polynomial time solutions of some problems of computational algebra[END_REF][START_REF] Rónyai | Computing the structure of finite algebras[END_REF]). For F a field of characteristic 0, this reduces to solving a system of linear equations over F by Dickson's theorem (see Theorem 1.4.10). If F is a finite field, then Friedl and Rónyai showed how to recursively construct a sequence of ideals of R, whose last element is equal to J(R). Using a very similar technique, Cohen, Ivanyos and Wales generalised these results, showing how to compute the Jacobson radical in the case that F is any field in which one can perform arithmetic and over which one can solve semilinear equations of the form k i=1 a i x p i = 0, where p = char(F), k ∈ Z >0 and a i ∈ F for all 1 ≤ i ≤ k. Finite fields are examples of such fields.

Theorem 3.4.1 ([18]

). There exists a deterministic polynomial-time algorithm that, given a finite-dimensional algebra R over a field F, where F is a field over which we can perform arithmetic and solve semilinear equations, computes the Jacobson radical of R. Note 3.4.2. We cannot in general expect to be able to compute the Jacobson radical for rings not containing a field. To see this, consider rings of the form Z/nZ, with n ∈ Z >0 , for which the task ultimately reduces to finding square divisors of n. This is not something we know how to do deterministically in polynomial time.

Other known algorithms and open questions

Rings are ubiquitous. It is thus important to have a wide range of algorithms to deal with finite rings. This list of deterministic polynomial-time algorithms for finite rings however, is not as long as would be expected for such basic objects. One of the reasons for this is that many problems for finite rings reduce to rings of the type Z/nZ, and at this stage the fact that we cannot factor n efficiently becomes a serious issue.

The study of algorithmic problems involving automorphisms and isomorphisms of finite rings intensified after the first deterministic polynomial-time primality test was formulated by Agrawal, Saxena and Kayal in terms of automorphisms of a certain finite ring (see [START_REF] Agrawal | Primes is in P[END_REF]). Subsequently, the same authors studied how some of the most important open algorithmic questions, like integer factorisation, polynomial factorisation over finite fields and graph isomorphism can be reduced to ring automorphism questions. The questions for which deterministic polynomial-time algorithms are sought are the following: As far as deterministic polynomial-time algorithms are concerned, all of the above problems are open, with the exception of the decision version of the ring automorphism problem, which was shown to be in P in [START_REF] Kayal | Complexity of ring morphism problems[END_REF]. The algorithm given there relies on the classification of rigid rings (i.e. rings with no nontrivial automorphisms).

Theorem 3.5.1 ([53], Theorem 7.1).

There exists a deterministic polynomial-time algorithm that, given a finite ring R, determines whether R has a nontrivial automorphism.

It is shown in [START_REF] Kayal | Complexity of ring morphism problems[END_REF] that both integer factorisation and the graph isomorphism problem reduce to the counting version of the ring automorphism problem, which is unlikely to be NP-complete. The decision version of the ring isomorphism problem is shown to be at least as hard as the graph isomorphism problem. Moreover, integer factorisation reduces to the search version of the ring isomorphism problem.

For finite fields, the isomorphism problem can be handled deterministically in polynomial time.

Theorem 3.5.2 ([65], Theorem 1.2).

There exists a deterministic polynomial-time algorithm that, given two finite fields of the same cardinality, exhibits an isomorphism between them.

Apart from these problems, to which systematic study has been devoted, the list of algorithms for finite rings remains quite a short one. It is one of the goals of this thesis to expand on this list, thus supplementing the toolbox for algorithmically dealing with finite rings.

Chapter 4

The module isomorphism problem

Let R be a finite ring and let M 1 , M 2 be two finite left R-modules. We present two distinct deterministic algorithms that decide in polynomial time whether or not M 1 and M 2 are isomorphic, and if they are, exhibit an isomorphism. As by-products, we are able to determine the largest isomorphic common direct summand between two modules and the minimum number of generators of a module. By not requiring R to contain a field, avoiding computation of the Jacobson radical and not distinguishing between large and small characteristic, both algorithms constitute improvements to known results. We have not attempted to implement either of the two algorithms, but we have no reason to believe that they would not perform well in practice.

Introduction

The module isomorphism problem (MIP) can be formulated as follows: design a deterministic algorithm that, given a ring R and two left R-modules M 1 and M 2 , decides in polynomial time whether they are isomorphic, and if yes, exhibits an isomorphism.

This problem is as fundamental as it is easily stated and has been studied extensively, due both to its intrinsic theoretical value and to its broad range of applications. As a theoretical question it is one in a long series of isomorphism problems. These are some of the most natural questions that occur in algorithmic contexts: given two objects "of the same nature", one wishes to determine if they are equal, or isomorphic. Examples of these problems include the group isomorphism problem, the graph isomorphism problem and the ring isomorphism (see [START_REF] Kayal | On the ring isomorphism and automorphism problems[END_REF][START_REF] Kayal | Complexity of ring morphism problems[END_REF]). From a complexity point of view, these problems have a special status, namely, they are thought to be NP-intermediate, i.e. pertaining to the class consisting of problems that are known This chapter is an extended version of the paper The module isomorphism problem for finite rings and related results, arXiv:1512.08365v1 ( [START_REF] Ciocȃnea-Teodorescu | The module isomorphism for finite rings and related results[END_REF]) to be in NP, but are not known to be in P, or to be NP-complete. The class of NPintermediate problems is nonempty if and only if P = NP (see [START_REF] Papadimitriou | Computational Complexity. Theoretical computer science[END_REF], Theorem 14.1). However, even under the hypothesis that P = NP, no "natural" NP-intermediate problems are known.

The practical value of the module isomorphism problem comes from viewing it in the larger context of algorithms for finite rings. Finite rings are fundamental objects and one wishes to have as many algorithms as possible for handling them at one's disposal, that is to say, in one's computer algebra system toolbox.

A brief overview of the results related to the module isomorphism problem is included in Section 4.2. In particular, polynomial-time algorithms for the module isomorphism problem were given in [START_REF] Brooksbank | Testing isomorphism of modules[END_REF][START_REF] Chistov | Polynomial time algorithms for modules over finite dimensional algebras[END_REF] for the case where R is a finite-dimensional algebra over a field and M 1 , M 2 are finite-dimensional modules over that field. For our purposes, R will be a finite ring (not necessarily containing a field) and M 1 , M 2 will be finite R-modules. We give an algorithm as described by the following theorem: Theorem 4.1.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M 1 and M 2 , computes a maximum length R-module C that is isomorphic to a direct summand both of M 1 and of M 2 . Moreover, the algorithm computes direct complements of C both in M 1 and in M 2 , together with the corresponding isomorphisms.

We establish the result in Theorem 4.1.1 by a direct generalisation of the methods given in [START_REF] Brooksbank | Testing isomorphism of modules[END_REF], where the rings considered were finitely generated algebras over a field and the modules were finite-dimensional over that field. This approach relies on the ability of finding non-nilpotent elements in non-nilpotent ideals of the endomorphism ring End R (M 1 ) (cf. Proposition 4.3.3). As a direct consequence of Theorem 4.1.1 we have that: Theorem 4.1.2. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M 1 and M 2 , decides whether M 1 and M 2 are isomorphic, and if they are, exhibits an isomorphism.

In Section 3, we show how the module isomorphism problem reduces to determining freeness of rank one of a module. We then give an algorithm that computes the minimum number of generators of a given finite module.

Theorem 4.1.3. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , computes a set for generators of M of minimum cardinality.

In particular, we can determine if a module is cyclic or free (by comparing cardinalities), which gives a second deterministic polynomial-time algorithm for the module isomorphism problem.

It is important to note that the algorithms given here work for any finite ring, do not distinguish between large and small characteristic and avoid computation of the Jacobson radical, thus constituting an improvement to known results. Moreover, the algorithm in Theorem 4.1.3 is an interesting object per se, due to its structure and the techniques it employs. A common approach to this type of problems is to reduce to the semisimple case and then "lift" (e.g. [START_REF] Chistov | Polynomial time algorithms for modules over finite dimensional algebras[END_REF][START_REF] Ivanyos | Deterministic polynomial time algorithms for matrix completion problems[END_REF]). In our algorithm, we work as if the ring were semisimple and we have a list, S 1 , . . . , S t , of candidates for the isomorphism classes of simple modules composing it. During the running of the algorithm, we allow ourselves to be contradicted in our assumption about the simplicity of the S i , in which case we update our list, quotient the ring by an appropriate two-sided nilpotent ideal and start again. If we are not contradicted, we may still draw conclusions. In this way, there is always a side-exit available and what forces an output in polynomial time is that we cannot take the side-exit too many times.

Context

All of the results referred to in this section deal with the case where the given ring R is a finite-dimensional algebra over a field F and the two modules are finite-dimensional over that field.

One of the first attempts at tackling the module isomorphism problem made use of the MeatAxe algorithm due to Parker (see [START_REF] Parker | The computer calculation of modular characters (the meat-axe)[END_REF]). Holt and Rees produce an efficient randomized algorithm in [START_REF] Holt | Testing modules for irreducibility[END_REF], that in the case where F is finite, tests whether a module is simple, and if it is not, produces a proper submodule. This algorithm is then used to test for isomorphism between two modules of which one is known to be simple. However, their method fails in the cases where the given module has a very special structure.

The first deterministic polynomial-time algorithm for the module isomorphism problem was presented by Chistov, Ivanyos and Karpinski in [START_REF] Chistov | Polynomial time algorithms for modules over finite dimensional algebras[END_REF]. For the purpose of their paper, F is a finite field or an algebraic number field. Their method reduces the problem to the semisimple case by computing the Jacobson radical of R and then further reduces the problem to testing cyclicity of modules. Because this method requires the computation of the Jacobson radical, it does not lend itself to generalisation in the case of general finite rings (cf. Chapter 3, Section 3.4).

The next solution to the module isomorphism problem was given by Brooksbank and Luks in [START_REF] Brooksbank | Testing isomorphism of modules[END_REF]. Their algorithm is based on finding nilpotent endomorphisms of one of the modules and in fact does more than test for module isomorphism -it produces the largest isomorphic common direct summand between two modules, i.e. the maximal length direct summand of one of the modules, which has an isomorphic copy as a direct summand of the other. In principle, this method works for any underlying field, as long as we can perform arithmetic in it.

Another related result was presented by Ivanyos, Karpinski and Saxena in [START_REF] Ivanyos | Deterministic polynomial time algorithms for matrix completion problems[END_REF]. Their algorithm computes the minimum number of generators of a given module and is in particular useful for testing module cyclicity. The drawback of this method is that it distinguishes between small and large characteristic of the underlying field.

Our goal is to obtain corresponding algorithms for the case that R is a finite ring (not necessarily containing a field) and the given modules are also finite.

MIP via non-nilpotent endomorphisms

In this section, the algorithm of Brooksbank and Luks [START_REF] Brooksbank | Testing isomorphism of modules[END_REF] is generalised to solve the module isomorphism problem for finite rings and finite modules over that ring.

Finding non-nilpotent elements in non-nilpotent ideals

An ideal I of a ring R is said to be nil if all its elements are nilpotent. The following is a well known fact. Proof. Clearly if a left (or right) ideal is nilpotent, then it is nil. For the other direction, note that any nil left (or right) ideal of R is contained in the Jacobson radical J(R) (see [START_REF] Lam | A First Course in Noncommutative Rings[END_REF], Lemma 4.11). So it is enough to show that J := J(R) is nilpotent.

Suppose J is not nilpotent. Since R is left-artinian, the sequence of consecutive powers of J must stabilize, i.e. ∃n ∈ Z >0 such that J n = J 2n = 0. Then there exists a left ideal L s.t. J n L = 0. Suppose L is minimal with this property. Since J n L = 0, there exists a ∈ L such that J n a = 0. Now Ra ⊆ L and J n a ⊆ L. Moreover, 0 = J n a = J n J n a and 0 = J n a ⊆ J n Ra, so by minimality of L, we have that L = Ra = J n a. Hence a = xa, for some x ∈ J n . It follows that a = 0 (otherwise, 1 -x would be both a unit and a left zero-divisor, which is not possible). This gives the desired contradiction. Note 4.3.2. The "only if" direction in the statement of the previous proposition is not true if we remove the artinianity condition. Consider the commutative ring R = Z[x 1 , x 2 , . . .]/(x 2 1 , x 2 2 , . . .). Then the ideal I = (x 1 , x 2 , . . .) is nil, but I is not nilpotent.

If R is finite, the proof of Proposition 4.3.1 can be translated into an algorithm for finding a non-nilpotent element in a non-nilpotent left ideal of R. Proposition 4.3.3. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a left ideal I, determines whether or not I is nilpotent and if it is not, produces a non-nilpotent element lying inside it.

Proof. Suppose R is a k-algebra, where k is a commutative ring (R will certainly be an algebra over its centre or its prime subring) and let I be a non-nilpotent left ideal of R. Since R is finite, we can find n ∈ Z >0 such that I n = I 2n = 0. Suppose I n is generated over k by a set A and over R by a set B, i.e. Consider the ideals I n a ⊆ Ra, where I n a = 0 since it contains ba. If this inclusion is in fact an equality, then we can write a = xa, for some x ∈ I n and since a = 0, it must be the case that x is non-nilpotent, as required (otherwise 1 -x would be a unit and a left zero divisor at the same time, which is impossible). Suppose now that the inclusion is strict. Then there exists c ∈ I n a such that I n c = 0 (otherwise I n I n a = I n a = 0, which is a contradiction, since 0 = ba ∈ I n a). Moreover, we will be able to find such a c among k-generators of I n a, otherwise, for all α ∈ A, we would have that I n αa = 0, and so 0 = α∈A kI n αa = I 2n a = I n a = 0, which is a contradiction.

We have now produced a smaller ideal Ra I n a ⊃ Rc such that I n c = 0. We replace a by c and keep going. This process must terminate in polynomial time, since length(Ra) ≤ length( R R) ≤ log 2 (|R|), and so the length of the descending chain of ideals obtained, and hence the number of steps performed by the algorithm, is bounded above by log 2 (|R|). We also note that I is nilpotent if and only if I length( R R) = 0, so it is possible to test if I is nilpotent in polynomial time.

Splitters

Let R be an algebra over a commutative artinian ring k such that R is finitely generated as a k-module. Let M 1 and M 2 be two R-modules of finite length over k. Note that Hom R (M 1 , M 2 ) is a left k-module via the action

k × Hom R (M 1 , M 2 ) → Hom R (M 1 , M 2 ) (r, f ) → (m → f (mr)),
and a right End R (M 1 )-module via the action

Hom R (M 1 , M 2 ) × End R (M 1 ) → Hom R (M 1 , M 2 ) (f, g) → f • g.
Moreover, End R (M 1 ) is left (and right) artinian. In particular, all its nil ideals are nilpotent and vice versa.

Following [START_REF] Brooksbank | Testing isomorphism of modules[END_REF], we make the following definition:

Definition 4.3.4. Let f ∈ Hom R (M 1 , M 2 ). A decomposition M 1 = N 1 ⊕ K 1 , for N 1 , K 1 ≤ M 1 , is called an f -decomposition if N 1 = 0, ker(f ) ≤ K 1 and the image of N 1 under f , which we denote by f N 1 , is a direct summand of M 2 . If M 1 has an f -decomposition, we say that f is a splitter. Note that the condition ker(f ) ≤ K 1 implies that N 1 ∼ = f N 1 = N 2 , so f induces an isomorphism N 1 ∼ = N 2 .
The following proposition and its proof, together with Proposition 4.3.3, allow us to algorithmically decide if a given homomorphism f is a splitter, and if it is, to produce an f -decomposition. Proposition 4.3.5. Let f ∈ Hom R (M 1 , M 2 ). Then f is a splitter if and only if there exists g ∈ Hom R (M 2 , M 1 ) such that gf is not nilpotent.

Proof. The proof of this proposition is the same as the one given in [START_REF] Brooksbank | Testing isomorphism of modules[END_REF], Lemma 3.3, which treats the case when R is a finitely generated algebra over a field and M 1 , M 2 are finite-dimensional over that field. For completeness we include the proof of the "if" statement here.

Suppose g ∈ Hom R (M 2 , M 1 ) is such that gf is not nilpotent. Let s = gf and t = f g. Since M 1 and M 2 have finite length over k (so are both artinian and noetherian over R), we can apply Fitting's Lemma (see Proposition 1.3.12) to say that

M 1 = ker(s d )⊕im(s d ), M 2 = ker(t d )⊕im(t d ), for d = max{length R (M 1 ), length R (M 2 )
} and the restriction of t to im(t d ) is an automorphism. We have that s d M 1 = 0 since s is not nilpotent, ker(f ) ≤ ker(s d ) by definition of s and

f (s d M 1 ) = t d (f M 1 ) ⊆ t d M 2 = f g(t d M 2 ) = f s d (gM 2 ) ⊆ f (s d M 1 ), so f im(s d ) = f (s d M 1 ) = t d M 2 = im(t d ),
which is what is required for f to be a splitter.

Suppose now that we are given f ∈ Hom R (M 1 , M 2 ) and we wish to know whether it is a splitter. To do this, we first compute a set C of k-generators of Hom R (M 2 , M 1 ). Now consider the left ideal I of End R (M 1 ) generated by the set Cf = {cf | c ∈ C}. If I is nilpotent (which we can determine by Proposition 4.3.3), then since Hom R (M 2 , M 1 )f = span k (Cf ) = I, we will not be able to find a non-nilpotent element of the form gf , so f cannot be a splitter. Otherwise the algorithm of Proposition 4.3.3 will produce some g ∈ Hom R (M 2 , M 1 ) witnessing that f is a splitter and we can produce an f -decomposition by Proposition 4.3.5.

We now have a way of identifying splitters. But we would not like to have to look for them over all homomorphisms. The following proposition tells us that we can restrict our attention to a considerably smaller set. Proof. To see that a set of End R (M 1 )-module generators is enough, note that

f is not a splitter ⇐⇒ Hom R (M 2 , M 1 )f ⊆ J(End R (M 1 )).
Let B be a set of End R (M 1 )-module generators of Hom R (M 1 , M 2 ). Suppose that B does not contain any splitters. Then

Hom R (M 2 , M 1 ) Hom R (M 1 , M 2 ) = b∈B Hom R (M 2 , M 1 )b End R (M 1 ) ⊆ J(End R (M 1 )),
and therefore Hom R (M 1 , M 2 ) cannot contain a splitter.

Finally, note that any set of left-k-module generators is also a set of right-End R (M 1 )module generators.

Putting these results together, we can construct an algorithm satisfying the requirements of Theorem 4.1.1 as follows.

Proof of Theorem 4.1.1: We view R as an algebra over its prime subring k. Let C be an auxiliary variable that at the end of the algorithm will become equal to the desired maximal length R-module that is isomorphic to a direct summand both of M 1 and of M 2 . At the beginning of the algorithm, we put C equal to zero. Similarly, we define an auxiliary variable f ∈ Hom R (M 1 , M 2 ) and initialise it at zero.

We compute B, a set of k-generators of Hom R (M 1 , M 2 ) (or a set of End R (M 1 )module generators thereof). For each element of B, we test if it is a splitter: by Proposition 4.3.6, if a splitter exists, we will find one inside B. Finding a splitter b ∈ B also gives us a homomorphism c ∈ Hom R (M 2 , M 1 ) such that cb is not nilpotent, and a decomposition Proposition 4.3.5). We make the following replacements:

M 1 = N 1 ⊕ K 1 and M 2 = N 2 ⊕ K 2 , where N 1 = im((cb) d ), K 1 = ker((cb) d ), N 2 = im((bc) d ), K 2 = ker((bc) d ), and d = max{length R (M 1 ), length R (M 2 )} (see
C := C ⊕ N 1 and f := f ⊕ (the restriction of b to N 1 ), M 1 := K 1 , M 2 := K 2 , B := (set of k-module generators of the new Hom R (M 1 , M 2 )
), and we repeat the process. Note that we are all the time assuming the Krull-Remak-Schmidt Theorem (see Theorem 1.3.13), which ensures existence and uniqueness up to isomorphism of the direct summands of M 1 and M 2 .

The algorithm produces the following data: the R-module C and the R-module homomorphism f such that f :

C ∼ -→ f (C). Put D := f (C).
The algorithm also produces injections of C and D into M 1 and M 2 respectively, that define them as submodules. By splitting these injections (see Proposition 2.5.1), we can recover the direct complements of C and D in M 1 and M 2 respectively, together with the corresponding isomorphisms.

MIP via an approximation of the Jacobson radical

In this section, another solution to the module isomorphism problem for finite rings is presented. We start with a problem reduction, showing that it is enough to be able to test if a module is free of rank 1. We then construct an algorithm that, given a finite ring and a finite module over that ring, computes a set of generators of minimum cardinality for that module.

Problem reduction

Let R be a finite ring. We observe that determining whether two finite R-modules M 1 and M 2 are isomorphic reduces to determining if a module is free of rank one. Let E := End R (M 1 ) and K := Hom R (M 2 , M 1 ). Note that K is a left E-module.

Proposition 4.4.1. Let R, M 1 , M 2 , E, K be as above. The following are equivalent:

(i) M 1 ∼ = M 2 as R-modules.
(ii) E ∼ = K as E-modules and the image of 1 E in K under any such isomorphism is an isomorphism between M 1 and M 2 . (iii) There exists an E-module isomorphism φ : E → K such that φ(1 E ) is an isomorphism between M 1 and M 2 .

Proof. The implications (ii)⇒(iii) and (iii)⇒(i) are immediate. For (i)⇒(ii), suppose

f : M 2 ∼ -→ M 1 . Then E ∼ = K, so let φ : E ∼ -→ K be any such isomorphism. Let λ := φ(1)
. Then there exists a unique ∈ E such that

f = φ( ) = φ( • 1) = φ(1) = λ,
where the third equality follows by E-linearity of φ. Since f is injective, so must λ be. Moreover, since M 1 and M 2 have the same length, λ must also be surjective.

Hence an algorithm that can establish freeness of rank one of a module provides a solution to the module isomorphism problem in the following way. Given M 1 and M 2 , we might first test whether they have the same cardinality, otherwise it is pointless to proceed. If the cardinalities do agree, we compute E and K, and test if E ∼ = K as E-modules (in the case that E ∼ = K, we are assuming this test will also produce an isomorphism). If this is not the case, we conclude that M 1 M 2 . Otherwise, suppose we have found an isomorphism ψ :

E ∼ -→ K. Set λ := ψ(1 E ). Then by Proposition 4.4.1, we have that M 1 ∼ = M 2 if and only if λ is an isomorphism.
For the remainder of this section we will concentrate on the task of computing the minimum number of generators of a given module. In particular, this will allow us to test for cyclicity and, by comparing cardinalities, for freeness of rank 1.

Computing minimum number of generators

Let R be a left-artinian ring. Suppose, along with R, we are given a collection S 1 , . . . , S t of nonzero left R-modules of finite length. Ideally, we would like this collection to be a set of representatives for the isomorphism classes of simple R-modules. However, for now, we only require that each simple R-module occurs in at least one of the S i , i.e. it occurs as a quotient in its composition series. We can take, for example, t = 1 and

S 1 = R R. Let a = t i=1 ann R (S i ),
where ann R (S i ) = ker(R → End Z (S i )). Again, ideally we would like a to be the Jacobson radical, J(R). In reality, we only have one inclusion, namely a ⊆ J(R), since an element of a will kill all the S i 's and so will kill all submodules, quotients and submodules of quotients of the S i . Since every simple R-module occurs in at least one of the S i , we have that a kills all simple R-modules, which is equivalent to being inside the Jacobson radical. Furthermore, since R is left-artinian, J(R) is nilpotent and hence a is nilpotent.

We will construct an algorithm that, given R and a collection of S i , either "improves" the sequence of S i or computes a and an isomorphism of R-modules

R/a ∼ -→ t i=1 S ai i , (4.1)
for suitable a i ∈ Z ≥0 . Similarly, we construct an algorithm that, when also given a finitely generated R-module M , either "improves" the sequence of S i or computes an isomorphism of R-modules

M/aM ∼ -→ t i=1 S ci i ,
for suitable c i ∈ Z ≥0 . Consider the quantity l(S i ) t i=1 = t i=1 (2 length(S i ) -1) ∈ Z ≥0 . An "improvement" in the sequence is measured by a decrease in l(S i ) t i=1 and occurs either when we remove one of the S i from the list (either because the list already contains an isomorphic copy of it or because it is not needed) or when we discover a nonzero proper submodule T of one of the S i which witnesses nonsimplicity of S i and which we use to replace S i by S i /T and T , that now stand a better chance of being simple. Note that the factor 2 in the expression of l(S i ) t i=1 ensures it decreases even when we remove an S i from the list.

Let us first write out the details of the routine that finds an isomorphism as in (4.1). We will call this routine UPDATE and within the main algorithm we will call it whenever we have improved on our sequence of S i 's and we want to update our a, the sequence of a i 's and the isomorphism R/a

∼ -→ t i=1 S ai i . Let S = {(S i ) t i=1 | t ∈ Z ≥0
, each S i is a nonzero finite length R-module and each simple R-module occurs as a factor in the composition series of at least one S i }. Proposition 4.4.2. There exists a deterministic polynomial-time algorithm that takes as input a finite ring R and a collection of modules (S i ) t i=1 ∈ S and outputs a sequence of integers a 1 , . . . , a t ∈ Z >0 , a two-sided nilpotent ideal a of R and an isomorphism ϕ : R/a

∼ -→ t i=1 (S i ) ai , where t ∈ Z ≥0 , a = t i=1 ann R (S i ) and (S i ) t i=1 ∈ S is such that l(S i ) t i=1 ≤ l(S i ) t i=1 .
Proof. Let b be a left ideal of R which we will use as an intermediate variable that at the end of the algorithm will become equal to the desired a . We start off by setting b = R, t = t, a i = 0 and S i = S i for 1 ≤ i ≤ t, and ϕ = 0. Throughout the algorithm ϕ : R/b ∼ -→ t i=1 (S i ) ai and t i=1 ann R (S i ) ⊆ b will be invariant. If for all i we have bS i = 0, then we are done. Otherwise, we choose 1 ≤ h ≤ t and s ∈ S h such that bs = 0. We define

ψ : R → S h ⊕ t i=1 (S i ) ai , ψ(r) = (rs, ϕ(r)).
Then ker(ψ) = ann R (s) ∩ b b, since b did not annihilate s. Let ψ be the map induced by ψ on R/ ker(ψ). Then

ψ isomorphism ⇐⇒ ψ surjective ⇐⇒ S h ⊕ {0} ⊆ im(ψ) ⇐⇒ bs = S h .
This comes as a confirmation of our intuition: we are treating the S i as if they were simple, so if 0 = bs ≤ S h , then we would want bs to be the whole of S h .

If ψ is surjective, we make the following replacements: a h := a h + 1, ϕ := ψ and b := ker ψ. Note that now b has smaller length than before.

If ψ is not surjective, we replace S h by S h /bs, t by t + 1 and put S t +1 := bs and a t +1 := 0. In addition, we replace ϕ by the composition π • ϕ, where π is the canonical map π :

t i=1 [old(S i ) old ai ] → t +1 i=1 [new(S i ) new ai ]
and we replace b by the kernel of our new ϕ. Note that the new b will contain the old b, but the improvement is now sitting in the new S i .

Consider the quantity l(S i ) t i=1 = t i=1 (2 length(S i ) -1). Then 0 ≤ t ≤ l(S i ) t i=1 , since each S i has length at least 1. Also, l(S i ) t i=1 is bounded above by its initial value. At each iteration of the algorithm, we either see a decrease in the value of l(S i ) t i=1 , when we improve our sequence, or we see a decrease in the length of b, whose length is initially equal to length(R). Since length(R) ≤ log 2 (|R|) (recall that R was finite), the algorithm runs in polynomial time.

We now turn to the main algorithm: Theorem 4.4.3. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , computes a set of generators for M of minimum cardinality.

Proof. We begin by running the UPDATE algorithm presented in Proposition 4.4.2 with input t = 1 and S 1 = R R. Let X = {x 1 , . . . , x d } be a set of R-generators of M . Then X = {x i + aM | 1 ≤ i ≤ d} generates M/aM over R/a. This gives a surjective homomorphism (R/a) d ∼ = t i=1 S aid i M/aM . Relabel the S i to get a map i∈I S i M/aM . We would like to find a subset J ⊆ I for which this map becomes an isomorphism. In this process, the standard proof of its existence in the case where the S i are simple (see [START_REF] Lang | Algebra. Graduate Texts in Mathematics[END_REF], Chapter XVII, Lemma 2.1) may produce a witness of nonsimplicity of some S i , in which case we refine the sequence and call the UPDATE subroutine to start over. In the end, we will have produced an isomorphism

t i=1 S ci i ∼
-→ M/aM , for some c i ∈ Z >0 (note that the ideal a may now be different from the one we started with).

Let n = max i { ci ai }. If for all i = h we have Hom R (S i , S h ) = 0, then there is a surjective map (R/a) n M/aM and n is minimal with this property. Since a ⊆ J(R), we can lift this to a map R n M and produce n generators of M . If, however, for some i = h we have that Hom R (S i , S h ) contains a nonzero element f , then we can once again refine our sequence (either using ker(f ) = 0 or im(f ) = S h or removing one of S i or S h from the list if they are isomorphic) and start over by calling the UPDATE routine on our newly improved sequence.

To establish the running time, consider again the quantity

l(S i ) t i=1 = t i=1
(2 length(S i ) -1).

At each iteration of the algorithm, we either produce an output or we improve on our sequence, which results in a decrease in l(S i ) t i=1 .

Note 4.4.4. As we have described the algorithm in Theorem 4.4.3, after we have improved our sequence, calling the UPDATE subroutine overwrites our so far acquired knowledge about a. There is possibly a way of saving some of this information by running a modified version of the UPDATE routine, which would thus make the main algorithm slightly more efficient. However, being more precise about this here would obscure the idea of the algorithm.

Remark on implementation and performance

Since our goal was to place the module isomorphism problem in the complexity class P, we have not been concerned with calculating running time exponents or performing a detailed complexity analysis. A more careful organisation of the subroutines of the algorithms presented, or indeed considering randomised variations thereof may yield better running times, but such endeavours are beyond our scope at this moment.

Note 5.1.4. A deterministic polynomial-time algorithm for the case where R + = (Z/pZ) n , for some prime p and some n ∈ Z >0 is given in [START_REF] Eggermont | Modellen voor eindige lichamen[END_REF], Section 4.

Testing if a ring is simple

We have seen in Theorem 1.1.3 that primality testing is in P. It is therefore natural to ask whether we can construct a deterministic polynomial-time algorithm which decides whether a finite ring is simple.

Lemma 5.2.1. Let R be a semisimple ring. Then the centre of R is a field if and only if R is simple.

Proof. Since R is semisimple, it is a finite product of simple rings. Hence the centre of R is the product of the centres of these simple rings, and so, is a finite product of fields. This product is then a field itself if and only if R was simple to begin with.

Theorem 5.2.2. There exists a deterministic polynomial-time algorithm that, given a finite ring R, determines whether R is simple, and if it is, outputs a prime p and two positive integers m and n such that R ∼ = M n (F p m ).

Proof. Compute k := Z(R) and test if it is a field using Theorem 5.1.2. If k is not a field, then R cannot be simple. If it is a field, then R is a finite-dimensional algebra over k, and we can compute its Jacobson radical using Theorem 3.4.1. If J(R) = 0, then R cannot be simple. If J(R) = 0, then R is a semisimple algebra whose centre is a field, which by Lemma 5.2.1 implies R is simple. Proceed by computing m ∈ Z >0 , the dimension of k over F p , and n ∈ Z >0 , the size of the matrix ring, both of which can be done in polynomial time.

Note 5.2.3. Given two finite rings R and R , we can now decide if they are simple and isomorphic: simply compare the size of the matrices which will be produced by Theorem 5.2.2 and test if the centres of R and R are isomorphic fields, using Theorem 3.5.2.

The algorithm above does not explicitly exhibit an isomorphism between R and M n (Z(R)). We can use Theorem 3.5.2 to get an isomorphism of fields Z(R) ∼ = F p m , for some m ∈ Z >0 , but we can say no more than that.

The problem of exhibiting an isomorphism R ∼ = M n (Z(R)) is often referred to as the explicit isomorphism problem, and has received recent attention in [START_REF] Ivanyos | Splitting full matrix algebras over algebraic number fields[END_REF][START_REF] Ivanyos | Improved algorithms for splitting full matrix algebras[END_REF]. In the case that Z(R) is a finite field and n is a power of 2, this problem has a deterministic polynomial-time solution. In general, the problem of finding an isomorphism between finite algebras over finite fields is not believed to be NP-hard, but is at least as hard as the graph isomorphism problem ( [START_REF] Ivanyos | Trading GRH for algebra: Algorithms for factoring polynomials and related structures[END_REF][START_REF] Kayal | On the ring isomorphism and automorphism problems[END_REF]).

Testing if a module is simple

Testing simplicity of a module can also be done in polynomial time.

Theorem 5.3.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , determines whether M is simple or not.

Proof. By Schur's Lemma (Theorem 1.6.1), if M is simple, then End R (M ) is a division ring, so we start by computing n := char(End R (M )) = exp(M + ) using Theorem 3.3.1. If n is not a prime, then we conclude that M is not simple. Otherwise, if n is a prime, then nR is a two-sided ideal in R, and R := R/nR is an algebra over a finite field, so we may compute its Jacobson radical using Theorem 3.4.1. Now M is an R -module, since nR annihilates M .

If J(R ) does not annihilate M , then M is not simple over R , and hence M is not simple over R. Otherwise, M is an R / J(R )-module and by Theorem 1.6.4, it is now enough to test whether End R / J(R ) (M ) is a field, which can be done by Theorem 5.1.2.

Second proof. Alternatively, compute

I := ann(M ) = ker(R → End Z (M + ), r → r • m),
where "•" denotes the action of R on M . Then M is a faithful R/I-module and so if M is simple, we claim that R/I is simple as a ring. To see this, suppose M is simple. Then the Jacobson radical of R/I annihilates M , but since M is faithful, J(R/I) = 0, hence R/I is semisimple. Now M is a faithful simple module over a semisimple ring, so R/I must in fact be simple.

We thus begin by testing simplicity of R/I as a ring, using Theorem 5.2.2. If R/I is not simple, then M cannot be simple and we are done. Otherwise, the algorithm in Theorem 5.2.2 will output a prime p, and two integers m, n such that R/I ∼ = M n (F p m ) as rings. Now, by Theorem 1.4.2, the only simple M n (F p m )-module, up to isomorphism, is (F p m ) n , and the other modules over M n (F p m ) are direct sums of (F p m ) n . Moreover, R/I-modules are exactly the R-modules annihilated by I. Hence M is simple over R if and only if |M | = p nm .

Testing if a module is projective

For many future algorithms it will be very useful to be able to test if a module is projective.

Theorem 5.4.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a R-module M , together with a generating set of cardinality d, for some d ∈ Z ≥0 , determines if M is R-projective or not, and if it is, produces a splitting of the natural surjection R d M .

Proof. Recall that M is projective if and only if the natural surjection f : R d M has a left inverse. The latter can be tested using Proposition 2.5.1, which will also produce a left inverse.

Second proof. Another way to determine whether M is projective comes as a consequence of Theorem 4.1.1, since M is projective if and only if M is a direct summand of R d . We compute the largest isomorphic common direct summand of R d and M , say S. If M ∼ = S, then M is projective and the isomorphism M → S, which is also produced by the algorithm, induces a splitting of R d → M . Otherwise the algorithms concludes that M is not projective.

Constructing projective covers

Recall the definition of a projective cover given in Definition 1.6.24 and the fact that over left-artinian rings, all modules have a projective cover, unique up to isomorphism (Theorem 1.6.25).

Theorem 5.5.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , outputs a projective cover of M .

Proof. Use the algorithm in the proof of Theorem 4.1.3 to construct a sequence of R-modules (S i ) t i=1 , two sequences of integers (a i ) t i=1 and (c i ) t i=1 , and a two-sided nilpotent ideal a such that

R/a ∼ = t i=1 S ai i and M/aM ∼ = t i=1 S ci i ,
where for all 1 ≤ i ≤ t, we have that a i > 0 and c i ≥ 0. Relabel, to write R/a ∼ = i∈I S i and M/aM ∼ = j∈J S j . Then for each j ∈ J we have a surjective map g j : M S j , such that aM = j∈J ker(g j ). For each j ∈ J, pick j ∈ I such that S j ∼ = S j . Since S j is a direct summand of R/a, there exists an idempotent e j ∈ R/a such that S j ∼ = (R/a)e j (see Theorem 1.5.4). To find e j , look at the image of 1 under the isomorphism R/a ∼ = i∈I S i and identify the entry corresponding to j . Replace all other entries by zeros and let e j be the preimage of this element under the same isomorphism.

Thus, the decomposition R/a ∼ = i∈I S i gives rise to a sequence of idempotent elements e 1 , . . . , e |J| in R/a such that for all j ∈ J we have S j ∼ = (R/a)e j .

By Proposition 1.5.8, these idempotents can then be lifted deterministically in polynomial time to idempotents e 1 , . . . , e |J| in R. For all j ∈ J, let P j = Re j . Since e j is an idempotent in R, we can write R = Re j ⊕ R(1 -e j ), so P j is projective. Hence we can construct a sequence of maps f j such that for each j ∈ J the following diagram commutes: P j M S j , πj fj gj where π j : P j → S j is the natural projection map. This can be done by solving a system of linear equations over R. Let P = j∈J P j and let f : P → M be the direct sum of the f j .

We claim that for each j ∈ J, the pair (P j , π j ) is a projective cover of S j . Clearly π j is surjective and P j is projective. We need to show that ker(π j ) ⊆ s P j . Let N ≤ P j be a submodule such that ker(π j ) + N = P j . By construction, ker(π j ) = aP j . Since a ⊆ J(R), by Nakayama's Lemma we must have N = P j . Since taking projective covers commutes with direct sums, (P, j∈J π j ) is a projective cover for M/aM . Since a is nilpotent, f is surjective and (P, f ) is a projective cover of M .

Constructing injective hulls

Recall the definition of injective hulls given in Definition 1.6.28 and the fact that injective hulls exist for modules over any ring. Moreover, two injective hulls of a module M are isomorphic (Theorems 1.6.29).

To construct injective hulls, we will make use of the character module (see Definition 1.9.1). Recall that for a finite ring R, the character functor defines a duality between fg R M and M fg R . (see Theorem 1.9.2). Moreover, the following holds.

Proposition 5.6.1. Let R be a left-noetherian ring and M a finitely generated Rmodule. Then

(i) M is projective in R M if and only if M is projective in fg R M. (ii) M is injective in R M if and only if M is injective in fg R M.
Proof. The "only if" directions of both (i) and (ii) are clear. We prove the converse statements below. Suppose M is projective in R M. Then M is a direct summand of a finitely generated free R-module, so it is projective in fg R M. Suppose M is injective in R M. Since R is left-noetherian, all its left ideals are finitely generated. Hence by Theorem 1.6.12, part (iii) (Baer's test), M is injective in fg R M. Note 5.6.2. The left-noetherian condition on R is not needed for part (i).

Corollary 5.6.3. Let R be a finite ring and M an R-module. Then M is injective over R if and only if M is projective over R o , the opposite ring of R. Note 5.6.4. If R is a finite ring and M is a finite R-module, then we may take

M = Hom Z (M, 1 e Z/Z), (5.1)
where e is a multiple of exp(M + ).

Theorem 5.6.5. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , computes an injective hull of M .

Proof. Compute M = Hom Z (M, 1 e Z/Z), where e is a multiple of exp(M + ). Using Theorem 5.5.1, compute a projective cover (P, f ) of M over R o . Now set I := P = Hom Z (P, 1 e Z/Z), where e is a multiple of exp(P + ). Then (I, g) is an injective hull of M by Theorem 1.9.2. The algorithm also produces a map g : M → I, given by precomposition with f , such that im(g) ⊇ e I.

Testing if a module is injective

Recall that a module is injective if and only if it is isomorphic to its injective hull (Theorem 1.6.30).

Theorem 5.7.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R and a finite R-module M , determines if M is injective.

Proof. Construct an injective hull I of M using Theorem 5.6.5. Now check if the map g : M → I produced by Theorem 5.6.5 is bijective.

Testing if a ring is quasi-Frobenius

Recall that a finite ring R is quasi-Frobenius if R is left self-injective (Theorem 1.7.1, Definition 1.7.2).

Theorem 5.8.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R, determines whether R is quasi-Frobenius.

Proof. Use Theorem 5.7.1 to determine if the left-regular R-module R R is injective.

Constructive tests for existence of injective and surjective module homomorphisms

In this section we discuss the algorithmic problem of testing for existence and of finding injective and surjective homomorphisms between two finite length modules over a ring R. If R is a finite-dimensional algebra over a field, this problem can be cast in the context of matrix completion, and has been shown to be NP-hard in [START_REF] Ivanyos | Deterministic polynomial time algorithms for matrix completion problems[END_REF].

In view of the results of [START_REF] Brooksbank | Testing isomorphism of modules[END_REF][START_REF] Chistov | Polynomial time algorithms for modules over finite dimensional algebras[END_REF] and of Theorem 4.1.2, this result is striking. It is not however an isolated type of result: the subgraph isomorphism problem is an NP-hard problem, while the graph isomorphism problem is believed to be NP-intermediate. While in the general case, testing constructively for existence of injective and surjective module homomorphisms is NP-hard, with certain restrictions on the modules considered, the problem turns out to be tractable. We are interested in the case where R is a finite ring and one of the modules is either projective or injective over R, for which the problem simplifies somewhat. Theorem 5.9.1. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M and N , one of which is projective, determines whether there exists a surjection M N . If one exists, the algorithm exhibits one such.

Proof. If N is projective, then it suffices to test whether N is a direct summand of M , which can be done by Theorem 4.1.3. This will also produce a surjection M N . If M is projective, then we proceed by constructing a projective cover (P, f ) of N . Note that existence of a surjection M N is equivalent to existence of a surjection M P . If there exists a surjection M P , simply compose it with f to get a surjection M N . Conversely, if there exists a surjection M N , then, since P is a projective cover of N , there exists a surjective map g : M P making the following diagram commute

P M N. f g
This reduces the problem to the previous case.

Second proof for the case where M is projective. If M is projective, we can also decide existence of a surjection M → N in a more direct manner. Use the algorithm in the proof of Theorem 4.1.3 to construct a two-sided nilpotent ideal a ⊂ R and a sequence of R-modules (S i ) t i=1 that is "compatible" both with M and with N , i.e. such that

M/aM ∼ = t i=1 S ai i and N/aN ∼ = t i=1 S bi i ,
for some a i , b i ∈ Z ≥0 . This is done by running the algorithm in the proof of Theorem 4.1.3 on the ring R and the module M , and including N as one of the candidates for the isomorphism classes of simple R-modules in the UPDATE subroutine. Note that, by construction, the algorithm ensures that for all i = j, we have Hom R (S i , S j ) = 0. We claim that existence of a surjection M/aM N/aN , which can be easily tested by comparing a i and b i for each 1 ≤ i ≤ t, is equivalent to existence of a surjection M → N . If there exists a surjection M → N , then clearly it induces a surjection M/aM N/aN . Conversely, if there exists a surjection f : M/aM N/aN , then, since M is projective, there exists a map f : M → N making the following diagram commute:

M N M/aM N/aN, f f
and f is surjective since a is nilpotent.

Note 5.9.2. The case where M ∼ = R n , for some n ∈ Z >0 can be settled using the algorithm for computing the minimum number of generators of a module, given in Theorem 4.1.3.

Dually to Theorem 5.9.1, we have the following result:

Theorem 5.9.3. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M and N , one of which is injective, determines whether or not there exists an injection M → N . If one exists, the algorithm exhibits one such.

Proof. Let k := 1 e Z/Z, where e ∈ Z >0 is a multiple of exp(M + ) and exp(N + ), and apply Theorem 5.9.1 to modules Hom k (N, k) and Hom k (M, k).

The remaining cases, not treated by Theorems 5.9.1 and 5.9.3, are constructive tests for existence of the following R-module homomorphisms:

• P → M , for P a projective module,

• M → P , for P a projective module, and their respective duals,

• N I, for I an injective module,

• I N , for I an injective module.

Mimicking the construction given in the proof of Theorem 1.2 of [START_REF] Ivanyos | Deterministic polynomial time algorithms for matrix completion problems[END_REF], we settle these as being NP-hard, even when R is a finite local commutative ring and P = R. This is done by a reduction from an instance of the nonsingular matrix completion problem, which is known to be NP-hard.

The nonsingular matrix completion problem is an algorithmic question that can be formulated as follows: given a square matrix A, whose entries are homogeneous linear polynomials in F[x 1 , . . . , x n ], for some field F, decide if there exist values from F that can be assigned to the variables x 1 , . . . , x n , so as to make A nonsingular. The constructive version of this problem asks for values of x 1 , . . . , x n making A nonsingular to be exhibited.

Nonsingular matrix completion problems arise naturally in spaces of linear transformations. Let n ∈ Z >0 and F be a field. Let A ⊂ M n (F) be a linear subspace and let {A 1 , . . . , A m } be a basis of A over F. Deciding existence of (resp. finding) a nonsingular matrix in A is equivalent to deciding existence of (resp. finding) a sequence c 1 , . . . , c m ∈ F such that m i=1 c i A i is nonsingular. The complexity of the nonsingular matrix completion problem is very much dependent on the size of the field F (see [START_REF] Ivanyos | Generalized Wong sequences and their applications to Edmonds' problems[END_REF][START_REF] Ivanyos | Deterministic polynomial time algorithms for matrix completion problems[END_REF]). If F is "large enough", then the Schwartz-Zippel lemma (see [START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF]) provides an efficient randomized solution. However, over finite fields, nonsingular matrix completion is NP-complete ( [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF][START_REF] Ivanyos | Generalized Wong sequences and their applications to Edmonds' problems[END_REF]). Theorem 5.9.4. There exists a deterministic polynomial-time reduction from the decision (resp. constructive) version of nonsingular matrix completion to the problem of deciding existence of (resp. finding) an injective module homomorphism from a finite commutative local ring R containing a field, to an R-module M .

where U 0 = f ∈L ker(f ) and the isomorphism in (5.2) is given by mapping f → f (1). Let φ be an R-module homomorphism. Then φ corresponds uniquely to an element (0, l 0 , u 0 , v 0 ) ∈ L ⊕ U 0 ⊕ V and im(φ) ∼ = F(0, l 0 , u 0 , v 0 ) + (0, 0, 0, l 0 U ).

Hence φ ∈ Hom R (M, R) is injective if and only if l 0 ∈ L is an isomorphism.

We consider now another weaker variant of the problem of testing constructively for injective and surjective module homomorphisms. Suppose we are given a finite ring R and two modules M and N . Instead of looking for a surjection M N , we may ask if there is an integer k such that there exists a surjective homomorphism f : M k N . If such a pair (k, f ) exists, we would like to exhibit it. Note that we do not ask for k to be minimal with this property. This problem turns out to have an easy solution.

Theorem 5.9.6. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M, N , decides if there exists a pair (k, f ), where k ∈ Z ≥0 and f : M k → N is a surjective R-module homomorphism. If it exists, the algorithm exhibits such a pair. Proof. Compute a set S of Z-generators of Hom R (M, N ). If N = f ∈S f (M ), then output (|S|, f ∈S f ). Otherwise conclude that there does not exist a pair as required.

Dually, we have the following result: Theorem 5.9.7. There exists a deterministic polynomial-time algorithm that, given a finite ring R and two finite R-modules M, N , decides if there exists a pair (k, f ), where k ∈ Z ≥0 and f : M → N k is an injective R-module homomorphism. If it exists, the algorithm exhibits such a pair. Proof. Compute a set S of Z-generators of Hom R (M, N ). If f ∈S ker(f ) = {0}, then output (|S|, f ∈S f ). Otherwise conclude that there does not exist a pair as required.

Chapter 6

Approximating the Jacobson radical of a finite ring

When trying to answer questions about left-artinian rings and modules over them, it is often convenient to reduce the problem at hand to the semisimple case, where structures are much more manageable, and then "lift". However, this approach requires the computation of the Jacobson radical of the ring, which we cannot efficiently carry out in general. But how "close" can we get to semisimplicity with a deterministic polynomial-time algorithm in the case of finite rings?

In this chapter, we give two deterministic polynomial-time algorithms that, given a finite ring A, produce two-sided nilpotent ideals j A , such that A/j A is "almost semisimple". We think of such ideals j A as approximations to the Jacobson radical.

Introduction

When considering the module isomorphism problem for finite rings, not being able to compute Jacobson radicals was the main obstacle in the way of generalising methods that had worked in the case of finite-dimensional algebras over finite fields (cf. [START_REF] Chistov | Polynomial time algorithms for modules over finite dimensional algebras[END_REF]). The side-exit algorithm of Theorem 4.1.3 was designed to construct an approximation of the Jacobson radical which was good enough for the purpose at hand, namely determining the minimum number of generators of a module. Motivated by this, we design deterministic polynomial-time algorithms that compute good working approximations of the Jacobson radical of a finite ring, that is, two-sided nilpotent ideals such that when we quotient the ring by them, we are left with something that is "almost" semisimple.

The notion we will use to approximate semisimplicity is that of separability. Given a commutative ring R, an R-algebra S is said to be separable over R if S is projective as an S ⊗ R S o -module, where S o denotes the opposite ring of S. A ring is said to be separable if it is separable as a Z-algebra. Section 6.2 explores the structure and properties of separable algebras and attempts to make an argument for why they Note 6.2.2. For any R-algebra S, the ring S e is called the enveloping algebra of S, which justifies the choice of notation. A left S e -module is the same as an S-S-bimodule whose induced R-structures coincide.

Let φ : S e → S be the S e -module homomorphism given by a ⊗ a → aa . Note that ker(φ) is then generated as an S e -module by elements of the form s ⊗ 1 -1 ⊗ s. (i) Let τ : S e → (S o ) e be the map given by x ⊗ y → y ⊗ x. Then τ is a ring isomorphism. For this, note that for all x 1 , x 1 , y 1 , y 2 ∈ S:

τ ((x 1 ⊗ y 1 )(x 2 ⊗ y 2 )) = τ (x 1 x 2 ⊗ y 2 y 1 ) = y 2 y 1 ⊗ x 1 x 2 and τ (x 1 ⊗ y 1 )τ (x 2 ⊗ y 2 ) = (y 1 ⊗ x 1 )(y 2 ⊗ x 2 ) = y 2 y 1 ⊗ x 1 x 2 .
(ii) The map τ : S e → S e given by x ⊗ y → y ⊗ x is an involutive ring antiautomorphism, since (τ ) 2 = id and τ ((

x 1 ⊗ y 1 )(x 2 ⊗ y 2 )) = y 2 y 1 ⊗ x 1 x 2 = (y 2 ⊗ x 2 )(y 1 ⊗ x 1 ) = τ (x 2 ⊗ y 2 )τ (x 1 ⊗ y 1 )
. A separability idempotent that satisfies τ (e) = e is called a symmetric separability idempotent. Proposition 6.2.6. Let R be a commutative ring and S be a separable R-algebra.

Then S o is a separable R-algebra. where φ : S e → S is given by φ(s⊗s ) = ss , ψ : (S o ) e → S o is given by ψ(s ⊗s) = ss and τ is the ring isomorphism described in Note 6.2.5. Let σ be a splitting of φ, which exists since S is a separable algebra over R. It is easy to see that the above diagram commutes and since σ is S e -linear, τ • σ is (S o ) e -linear. Hence τ • σ gives a splitting of ψ, showing that S o is separable over R.

The following proposition describes separability over fields.

Theorem 6.2.8.

(i) ( [START_REF] Knus | Théorie de la descente et algèbres d'Azumaya[END_REF], Chapter III, Proposition 3.4). Let R ⊂ S be a finite field extension. Then S is separable over R if and only if for all s ∈ S, the minimal polynomial of s over R has distinct roots in a splitting field over R. (ii) ( [20], Chapter II, Theorem 2.5). Let R be a field and S an R-algebra. Then S is separable over R if and only if S is finite-dimensional over R and for every field extension R ⊂ K, we have that S ⊗ R K is semisimple. (iii) ( [START_REF] Knus | Théorie de la descente et algèbres d'Azumaya[END_REF], Chapter III, Theorem 3.1). Let R be a field and S an R-algebra. Then S is separable over R if and only if S is isomorphic to an algebra of the form n i=1 M ni (D i ), for some n ∈ Z ≥0 and n i ∈ Z >0 , with D i finite-dimensional division algebras over R and Z(D i ) ⊃ R finite-dimensional separable field extensions. Corollary 6.2.9. A separable algebra over a field is semisimple.

Proof. Put K = R in Proposition 6.2.8, part (ii).

Since finite extensions of perfect fields are separable, semisimplicity and separability are equivalent notions for finite-dimensional algebras over perfect fields. Corollary 6.2.10. Let R be a perfect field and S a finite-dimensional R-algebra. Then S is a separable R-algebra if and only if S is semisimple. Example 6.2.11. Let R be a commutative ring and let n ∈ Z ≥0 . Then the matrix ring M n (R) is a separable R-algebra. To see this, let E ij denote the matrix with (i, j) th entry equal to 1 and all other entries equal to 0. Then for any fixed i, the element e i = n j=1 E ij ⊗ E ji is a separability idempotent. Example 6.2.12. Let R be a commutative ring and let G be a finite group such that |G| is a unit in R. Then the group algebra R[G] is a separable R-algebra. To see that, note that e := |G| -1 g∈G g ⊗ g -1 is a separability idempotent. Parts (i) and (ii) of Proposition 6.2.8 establish that the definition of separability is compatible with the classical definitions of separability in the cases of finite field extensions and finite-dimensional algebras over a field. The reason the extra finiteness condition is required is that separable algebras, as we have defined them, turn out to have a lot of structure, as shown in the following series of results. Proposition 6.2.13 ([20], Chapter II, Proposition 2.1). Let R be a commutative ring and S a separable R-algebra. Suppose that S is projective as an R-module. Then S is finitely generated as an R-module. Proposition 6.2.14 ([20], Chapter II, Proposition 1.12, Theorem 3.8). Let R be a commutative ring.

(i) Let A be a separable commutative algebra over R. Suppose S is a separable A-algebra. Then S is an R-algebra and it is separable over R. (ii) Let S be a separable R-algebra and A be any R-subalgebra of the centre of S.

Then S is separable over A. (iii) Suppose S is an R-algebra. Then S is separable over R if and only if S is separable over its centre, and its centre is separable over R. (i) Let R be a commutative ring and R 1 , R 2 be two commutative R-algebras. Let S 1 be a separable R 1 -algebra and S 2 a separable R 2 -algebra. Then 20], Chapter II, Theorem 7.1). Let R be a commutative ring and S an R-algebra that is finitely generated as an R-module. Then the following are equivalent:

S 1 ⊗ R S 2 is a separable R 1 ⊗ R R 2 -algebra, with (r 1 ⊗ r 2 )(s 1 ⊗ s 2 ) = r 1 s 1 ⊗ r 2 s 2 . Moreover, Z(S 1 ⊗ S 2 ) = Z(S 1 ) ⊗ Z(S 2 ). (ii) Let R 1 ,
(i) S is separable over R.

(ii) For every maximal ideal m of R, we have that S ⊗ R R m is separable over R m .

(iii) For every maximal ideal m of R, the quotient S/mS is separable over R/m.

Separability is testable deterministically in polynomial time (cf. Note 3.4.2).

Theorem 6.2.19. There exists a deterministic polynomial-time algorithm that, given a finite commutative ring R and a finite R-algebra S, decides whether or not S is separable over R.

Proof. Using Proposition 2.4.1, we compute the enveloping algebra S e = S ⊗ R S o , after which we test projectivity of S over S e using Theorem 5.4.1.

Azumaya and finite-étale algebras

There are two distinguished classes of separable algebras that deserve special attention: Azumaya and finite-étale algebras.

Recall the definition of a progenerator (Definition 1.8.6).

Theorem 6.2.20 ([54], Chapter III, Theorem 6.1, [20], Chapter II, Theorem 3.4).

Let R be a commutative ring and S an R-algebra. Then the following are equivalent.

(i) S is separable over R and Z(S) = R.

(ii) S is an R-progenerator and the map α : S e → End R (S), given by s ⊗ s → (f : t → sts ), is an isomorphism of R-algebras. (iii) S is an S e -progenerator and Z(S) = R. (iv) There exist an R-algebra T and an R-progenerator P such that S ⊗ R T ∼ = End R (P ) as R-algebras. Proof. This follows from Proposition 6.2.25 and the fact that extension of scalars does not change the rank.

In the commutative setting, the notion we are interested in is that of a finite-étale algebra. Definition 6.2.27. Let R be a commutative ring. An R-algebra S is finite-étale over R if S is commutative, separable as an R-algebra and projective as an R-module.

We state a couple of results describing the behaviour of finite-étale algebras and Azumaya algebras with respect to tensor products and direct products. These are consequences of Proposition 6.2.16. Proposition 6.2.28. Let R be a commutative ring and let R 1 , R 2 be two commutative R-algebras.

(i) Let S 1 be an Azumaya R 1 -algebra and S 2 an Azumaya R 2 -algebra. Then

S 1 ⊗ R S 2 is Azumaya over R 1 ⊗ R R 2 . (ii) Let S 1 be a finite-étale R 1 -algebra and S 2 a finite-étale R 2 -algebra. Then S 1 ⊗ R S 2 is finite-étale over R 1 ⊗ R R 2 .
Corollary 6.2.29. Let R be a commutative ring and R a commutative R-algebra.

(i) Let S be an Azumaya R-algebra. Then S ⊗ R R is Azumaya over R .

(ii) Let S be a finite-étale R-algebra. Then S ⊗ R R is finite-étale over R . Proposition 6.2.30. Let R 1 , R 2 be two commutative rings. Let S 1 be an R 1 -algebra and S 2 an R 2 -algebra. Then

(i) S 1 × S 2 is Azumaya over R 1 × R 2 if and only if S 1 is Azumaya over R 1 and S 2 is Azumaya over R 2 . (ii) S 1 × S 2 is finite étale over R 1 × R 2 if and only if S 1 is finite-étale over R 1 and S 2 is finite-étale over R 2 .
Moreover, if R := R 1 = R 2 , then S 1 × S 2 is finite étale over R if and only if S 1 and S 2 are both finite-étale over R. Note 6.2.31. If R := R 1 = R 2 = 0 and S 1 , S 2 are Azumaya R-algebras, then S 1 × S 2 is not Azumaya over R.

The Brauer group

For a commutative ring R, we can define an equivalence relation on the collection of Azumaya R-algebras such that the equivalence classes form an abelian group with binary operation given by taking tensor products over R. Suppose A 1 , A 2 are two finite rings that are separable projective over their prime subrings. Then it is not necessarily true that A 1 × A 2 will also be separable projective over its prime subring. However, the class of separable rings is closed under taking products by Proposition 6.2.16, part (iii). Being closed under taking products is also an important property of the class of semisimple rings. For a finite ring A, we would like to identify a subring S ⊂ A such that A is separable over Z if and only if A is separable projective over S. That is the aim of this section.

Let A be a finite ring. Then A has a unique block decomposition, A = i∈I A i , where I is the set of centrally primitive idempotents of A and each A i is connected (see Definition 1.5.3, Theorem 1.5.5), and hence has prime power characteristic (see Theorem 1.5.5). We group together the A i according to their characteristics to get

A = i∈I A i = p prime e∈Z>0     i char(Ai)=p e A i     . (6.3) Let B p,e := i char(Ai)=p e A i .
Definition 6.2.48. Let A be a finite ring. We define the generalised prime subring of A, denoted by P A , to be the product of the prime subrings of B p,e . Proposition 6.2.49. Let A be a finite ring and let k be its prime subring. Then P A is separable as a k-algebra.

Proof. The ring P A is a product of rings, each of which is separable over k by Proposition 6.2.16, part (ii). The result now follows from Proposition 6.2.16, part (iii). Lemma 6.2.50. Let A be a finite ring. Then P A = P Z(A) .

Proof. This follows since a block decomposition of A induces a block decomposition of Z(A) (see Theorem 1.5.6), together with the fact that any ring has the same prime subring as its centre. Proposition 6.2.51. Let A be a finite separable ring. Then A is projective as a module over P A .

Proof. By Proposition 6.2.16 we may assume that A is connected. Further, by Proposition 6.2.13 and Proposition 6.2.14, part (iii), we may assume that A is commutative. Hence A is local. Suppose A has prime subring Z/p n Z, for some prime p and some n ∈ Z >0 . Then A/pA is a separable F p -algebra. By Corollary 6.2.9, we have that A/pA is semisimple, so it must be a finite field extension of F p . Suppose the degree of this extension is d. We are left with showing that A + ∼ = (Z/p n Z) d . Consider the map A → p n-1 A, given by f : a → p n-1 a. This map is surjective. Moreover, pA ⊆ ker(f ). Since A/pA is a field, pA is a maximal ideal of A, so it must be the case that pA = ker(f ). Hence |A/pA| = |p n-1 A| = p d .

Since A/pA ∼ = F d p as F p -vector spaces, we may choose a basis {a 1 , . . . , a d } ⊂ A of A/pA over F p . Since p n A = 0, it follows that {a 1 , . . . , a d } generate A over Z/p n Z. Then the map (Z/p n Z) d A, given by sending the generator of the i th copy of Z/p n Z to a i , is surjective. To see that it is also injective it is enough to show that the cardinalities agree. Consider the chain of ideals A ⊃ pA ⊃ . . .

⊃ p n-1 A ⊃ {0}. Since |p i A/p i+1 A| = p d , for all 0 ≤ i ≤ n -1, we have that |A| = p nd . Hence (Z/p n Z) d ∼ = A.
Theorem 6.2.52. Let A be a finite ring. Then A is separable if and only if A is separable projective over P A .

Proof. Let k be the prime subring of A. The "only if" direction follows from Proposition 6.2.49 and the fact that A is separable over Z if and only if it is separable over k. The "if" direction follows from Proposition 6.2.14, parts (i), (ii) and Proposition 6.2.51. Note 6.2.53. If A is separable, but not finite, it is not necessarily projective over any proper subring. To see this, consider the Z-algebra Q. Then Q is certainly separable over Z, since Q ⊗ Z Q ∼ = Q, but it cannot be projective over any proper subring, since then it would have to be finitely generated over it (see Proposition 6.2.13).

Suppose R ⊆ Q is a subring such that Q is finitely generated as a module over R. Then Q is integral over R, i.e. for every q ∈ Q, there exists a monic polynomial f ∈ R[X] such that f (q) = 0. But then it is easy to see that Q * ∩ R = R * , where R * denotes the unit group of R. Hence R * = R\{0}, so R is a field and then it must be the case that R = Q.

Classification of finite separable rings

For finite-dimensional semisimple algebras over a field and separable algebras over a field, we have explicit descriptions in terms of matrix rings over certain division rings (see Theorem 1.4.5 and Theorem 6.2.8, part (iii), respectively). The aim of this section is to provide a similar classification result for finite separable rings. It turns out that finite separable rings are isomorphic to products of finitely many matrix algebras over certain special commutative rings, called Witt rings.

Recall that a ring C is said to be connected (or indecomposable) if C has exactly two central idempotents, namely 0 and 1. Note that a connected ring is nonzero.

Here, we develop the theory concerning Witt rings that we require. We restrict our attention to truncated Witt rings over finite fields, as this is a sufficient level of generality for our purposes. For more on Witt rings, see Chapter II: §6 of [START_REF] Serre | Local Fields. Graduate Texts in Mathematics[END_REF] or Chapter VI: Exercises 46-51 of [START_REF] Lang | Algebra. Graduate Texts in Mathematics[END_REF].

: C -→ D A -→ A Red := A/ √ 0 A , (6.4)
where √ 0 A denotes the nilradical of A (which equals the maximal ideal of A).

Theorem 6.2.54. The functor Red has a left adjoint.

Proof. We will show that if R ∈ D, then there exists a pair (W e (R), ϕ), with W e (R) ∈ C and ϕ : R → W e (R) Red a ring homomorphism, such that for every A ∈ C and every ring homomorphism R f -→ A Red , there exists a unique ring homomorphism

F : W e (R) F -→ A such that f = F Red • ϕ, i.e. such that the following diagram commutes: R W e (R) Red A Red W e (R) A. ϕ f F Red ∃!F
Moreover, ϕ is an isomorphism, and the pair (W e (R), ϕ) is unique up to unique isomorphism. We may assume that R = F p [X]/(g(X)), where g(X) ∈ Z/p e Z is a monic polynomial of degree d, for some d ∈ Z >0 , and g(X) := (g(X) mod p) ∈ F p [X] is irreducible. Let W e (R) = (Z/p e Z)[X]/(g(X)). Then W e (R) Red ∼ = R. Let ϕ : R ∼ -→ W e (R) Red be the natural isomorphism. We are left with showing that for all A ∈ D and f : R → A Red , there is a unique F : W e (R) → A, making the following diagram commute:

R A Red W e (R) A. f ∃!F
This follows from Hensel's lemma. The last part follows by properties of universal objects. This shows that there is a functor

W e : D -→ C R -→ W e (R)
that is left adjoint to Red.

if

|A| = p den 2 , | Z(A)| = p de , | Z(A)/p Z(A)| = p d .
The inverse of the map in (6.7) is given by Note that an Azumaya algebra over a commutative local ring is free as a module over that ring (since projective modules over local rings are free). The fact that the maps (6.7) and (6.8) are mutual inverses now follows from Proposition 6.2.61, Theorem 6.2.20, part (ii), and Example 6.2.34, part 3. Corollary 6.2.63. Let A be a finite separable ring. Then A ∼ = A o as rings.

M n (W e (F p d )) ←-(p, d, e, n). ( 6
We know from Theorem 1.2.11 that for R a commutative ring, n ∈ Z >0 and S = M n (R), every two-sided ideal of S is of the form M n (I), for some two-sided ideal I of R. Conversely, if I is a two-sided ideal of R, then M n (I) is a two-sided ideal of S. Corollary 6.2.64. The set of two-sided ideals of a finite connected separable ring is in bijection with the set of ideals of its prime subring.

Proof. Recall from Proposition 6.2.58 that all ideals of W e (F p d ), where p is a prime, are generated by powers of p. In particular, there are exactly e+1 ideals, with maximal ideal generated by p. The result now follows from Theorem 6.2.62.

The trace map and the trace radical

In this section we introduce the notions of trace map and trace ideal, which are closely related to separability.

Let k be a commutative ring and P a finitely generated k-module. Consider the map Hom k (P, k)

⊗ k P ϕ -→ End k (P ), f ⊗ x → (y → f (y)x). (6.9)
Then ϕ induces a map

: (Hom k (P, k) ⊗ k P ) × (Hom k (P, k) ⊗ k P ) -→ Hom k (P, k) ⊗ k P, (f ⊗ x, g ⊗ y) -→ f (y)g ⊗ x, ( 6
P : x = n i=1 f i (x)x i , i.e. ϕ n i=1 f i ⊗ x i = id P ,
where ϕ is the map defined in (6.9). Note 6.2.66. Part (ii) above is equivalent to requiring 1 ∈ im(ϕ), where ϕ is the map defined in (6.9).

Strongly separable algebras

We now study the connections between the trace radical and separability. Let k be a commutative ring. We would like to characterise k-algebras A that are finitely generated and projective as k-modules and have the property that Tr A/k generates Hom k (A, k) as a right A-module, but are not necessarily commutative. Theorem 6.2.88 ([21], Theorem 1, [START_REF] Kadison | Separability and Hopf algebras[END_REF], Theorem 3.4). Let k be a commutative ring and let A be a k-algebra with centre R := Z(A) such that A is a finitely generated projective k-module. Then the following are equivalent:

(i) The trace map Tr A/k generates Hom k (A, k) as a right A-module. (ii) A is k-separable and A = R ⊕ [A, A] as R-modules, where [A, A] is the R- submodule of A generated by elements of the form ab -ba, with a, b ∈ A. (iii) A is k-separable and Tr A/R (1) is a unit in k • 1 A , the image of k in R.
(iv) A has a symmetric separability idempotent over k. Definition 6.2.89. An algebra satisfying any of the conditions of Theorem 6.2.88 is called a strongly separable algebra. Note 6.2.90. We see that strongly separable algebras are a special kind of symmetric algebras, namely ones for which a nonsingular, symmetric, associative bilinear map B : A × A → k is given by B(a, b) = Tr A/k (ba). We have seen in Theorem 6.2.45 that any separable algebra that is finitely generated, projective and faithful as a module over its base ring is symmetric, but the trace map need not be nonsingular, and thus may not give rise to such a map B. Example 6.2.91. Let k be a finite field and let A = M n (k). Suppose char k divides n. Then A is separable (and symmetric) over k, but Tr A/k = n • (the usual trace) = 0, so A is not strongly separable over k. To see that A is a symmetric k-algebra, we must look at the usual trace map, which we denote by tr 0 . Consider the map B : A × A → k given by B(a, b) = tr 0 (ab). This is now bilinear, symmetric, associative and nonsingular, as required for it to witness the fact that A is symmetric as a kalgebra.

Example 6.2.92. (Strongly separable algebras) 1. Let n ∈ Z >0 and k be a commutative ring. If n • 1 is a unit in k, then M n (k) is strongly separable over k with symmetric separability idempotent n -1 n i,j=1 E ij ⊗ E ji , where E ij denotes the n × n matrix whose (i, j) th entry is equal to 1 and all other entries are equal to 0.

2. Let n ∈ Z >0 and k be a finite commutative ring. Put A = M n (k). If n • 1 is not a unit in k, then n • 1 is a zero-divisor. Since Tr A/k = n • (usual trace), we have that I A/k = 0 and hence A is not strongly separable. 3. Let G be a finite group, k a commutative ring, and put A := kG. If |G| is a unit in k, then A is strongly separable over k, with symmetric separability idempotent |G| -1 g∈G g ⊗ g -1 . 4. ([3], Corollary 3.1) Let k be a field with char(k) = 0 and A a k-algebra. Then

A is strongly separable if and only if it is finite-dimensional and semisimple.

An approximation of the Jacobson radical

We have seen in Sections 6.2.4 and 6.2.5 that separable projective algebras and separable rings have many nice properties. Until now, however, we have mainly stayed on theoretical ground. We would now like to be able to algorithmically reduce any finite ring to this "state". In other words, given a finite ring, we would like to quotient out by some two-sided ideal and obtain a ring that is separable. Our goal in a perfect world would have been to quotient out by the Jacobson radical and obtain a semisimple ring. Since computing the Jacobson radical is in general out of our reach (see Note 3.4.2), we will have to content ourselves with quotienting out by something that is almost the Jacobson radical and obtaining something that is almost semisimple, more precisely, something that is separable.

note that by Proposition 6.2.72, part (iv), we have Tr A/n A ≡ Tr A mod n . Hence [START_REF] Agrawal | Primes is in P[END_REF] is an element of additive order m in A/I. is injective, and since A 1 is a finite projective Z/mZ-module, φ is an isomorphism of Z/mZ-modules, i.e. the trace map generates Hom Z/mZ (A 1 , Z/mZ) as a left module, which is equivalent to A being strongly separable over Z/mZ by Theorem 6.2.88.

x + n A ∈ I A/n A ⇐⇒ Tr A/n A ((A/n A)(x + n A)) = 0 ⇐⇒ Tr A/n A (Ax + n A) = 0 ⇐⇒ Tr A (Ax) ⊂ n Z/mZ ⇐⇒ m n Tr A (Ax) = 0 ⇐⇒ m n x ∈ I A ⇐⇒ x + n A ∈ I A : m n A /n
If I = 0, then we treat A 2 as we did A 0 , i.e. we make it projective as a module and calculate the trace radical of the resulting ring. We continue in this manner until the trace radical becomes equal to 0. In the end we will have produced a strongly separable algebra over its prime subring.

By Proposition 2.8.1, for every prime p dividing the characteristic of the final ring, a unique power of p occurs as an invariant of the underlying abelian group of the ring. Hence the generalised prime subring of the final ring is equal to its prime subring.

Set j A to be the kernel of the map induced by the successive quotienting. Since length(A i ) < length(A i-1 ), for all i, the algorithm terminates in polynomial time. Note 6.3.23. Suppose char(A) = n = t i=1 p ei i , for some n ∈ Z >0 , p i distinct primes and e i ∈ Z >0 . Then the number of iterations performed by the algorithm is bounded above by t i=1 e i -t. This is because at each step we have to make the ring at hand projective over its prime subring in such a way that the radical of the characteristic is not changed.

Calculating the trace radical over and over again is a costly operation. There is a more economic way of proceeding, which we describe in the remaining part of this section. We begin with an auxiliary result. Second proof of Theorem 6.3.22. By Theorem 6.3.21, we may assume that the characteristic of A is only divisible by large primes. We will construct a sequence of rings that terminates at a separable state. We begin as in the proof of Theorem 6.3.22:

A 0 := A, A 1 := A 0 /mA 0 , A 2 := A 1 /I A1/(Z/mZ) ,

where m | char(A 0 ) is such that mA 0 is a two-sided nilpotent ideal of A 0 , and A 1 is projective over Z/mZ. We then proceed by putting

A 3 := A 2 /A 2 [m ],
where m is computed using the deterministic polynomial-time algorithm described in Proposition 2.8.2. Then m | m is the least integer such that A 3 is projective over Z/ m m Z. By Proposition 6.3.24 (taking B := A 2 and C := A 3 ), the ideal A 2 [m ] is nilpotent and A 3 is separable over Z/ m m Z. By Propositions 2.8.1 and 2.8.2, for every prime p dividing the characteristic of the final ring, a unique power of p occurs as an invariant of the underlying abelian group of the ring. Hence the generalised prime subring of the final ring is equal to its prime subring.

Set j A = ker(A → A 3 ) under the map induced by the successive quotienting.

Note 6.3.25. A natural question that arises is whether we have to compute any trace radical at all, i.e. whether given a finite ring A, the ideal given by A[m ] is not already an approximation of the Jacobson radical. The answer is no. To see this, consider the ring A = Z/pZ × Z/p 2 Z, where p is a prime. Then char A = p 2 and m = p. Now dim Fp (A/ J(A)) = 2, but A/A[m ] ∼ = F p has rank 1 < 2. This contradicts Theorem 6.3.4. We can also produce a connected example of this type of failure. Let p be a prime and consider the ring A = (Z/p 2 Z)[X]/(pX 2 , X 3 ). Then char(A) = p 2 and m = p. Again, dim Fp (A/ J(A)) = 3, but dim Fp (A/A[m ]) = 2.

An illustration

For more clarity, let us explore a graphical illustration of the above results. For simplicity, we restrict to the case that m = p e for some large prime p and some e ∈ Z >0 . Suppose

A + ∼ = t i=1
Z/p ei Z, where e i+1 ≥ e i , e 1 > 0 and e = e t . We will represent finite abelian p-groups by

p e1 p et ,
where the number of vertical boxes is equal to the number of cyclic direct summands of A and the height of each such box is equal to the corresponding invariant. Now any finitely generated projective Z/p e Z-module is free of finite rank, so is represented by a rectangle. To make A projective over its prime subring, we quotient out by p e1 A, where p e1 is the smallest nonzero invariant appearing in the decomposition of A + (or by p e A, for any e ≤ e 1 ).

p et p e1

.

Suppose we have already made A projective as a module over Z/mZ, so that now A + ∼ = (Z/p e Z) t . Then the next step in the algorithm is to quotient out by the trace radical to obtain A 2 := A/I A with quotient map ϕ : A → A 2 . We represent this graphically as:

p e p ei

I A

, where the shaded lower-right part represents the trace radical. Note that the trace radical must touch the bottom line since when quotienting out by the trace radical, the characteristic remains unchanged (see Proposition 6.3.17). However, it may not touch the top line.

In the first algorithm, we proceed by making the remaining A 2 := A/I A projective over its prime subring, which we achieve by quotienting out by p ei A 2 . This corresponds to looking at the upper-left grey rectangle in the first picture below, which we now treat as our initial box. In the second algorithm we proceed directly by quotienting out by A 2 [p e-e ], where p e-e is the second largest invariant in A 2 (or by quotienting out by A 2 [p e-f ], for any 0 < f ≤ e ). This leaves us looking at the upper-left grey rectangle in the second picture below, which is now separable projective over its prime subring by the second proof of Theorem 6. Note that by Theorem 6.3.4, the rank of A/j A 1 and that of A/j A 2 must be equal to 1. Suppose that e = 2e N + r, for some N ∈ Z >0 and some 1 ≤ r ≤ 2e . Then To see this, note that

I A = k • p e-2e X - p e 2
and the rank of A/I A is still 2. For the next trace radical computation, we simply replace e by e-2e . Hence if e > 2e N , then the first algorithm performs at least N trace radical computations. Graphically, the algorithm computing j A 1 can be represented by the following diagram: Note that if q ∈ Z >0 \Q, then e q = 0. Moreover, q∈Q e q = 1. We claim that if e q = 0, then there exists d ∈ D such that d is exactly divisible by q, i.e. q | d and gcd(q, d/q) = 1. This is because if e q = 0, then there exists m such that exp(A + m ) = q and Z/qZ is a direct summand of A + m , and hence of A + . Further, we claim that for every d ∈ D and every prime p | d, we have that Then f d = f d1 + f d2 , so Zf d ⊆ Zf d1 + Zf d2 . Moreover, the additive orders of f d1 and f d2 are coprime, and so the additive order of f d1 + f d2 is equal to the additive order of f d . Hence Zf d ⊆ Zf d1 + Zf d2 . Suppose that for some prime p and some r ∈ Z >0 , we have that p r divides d exactly. Take d 1 = p r . Then f d1 = 0≤i≤r e p i ∈ Zf d , as required.

We now show that d∈D Zf d = B, where B is as in (6.25). That d∈D Zf d ⊆ B follows from (6.26). For the other inclusion, we will show that for all q = p r , with p a prime and r ∈ Z >0 , we have e q ∈ d∈D Zf d . Fix a prime p. If e q = 0, then we are done. Otherwise, pick d ∈ D that is exactly divisible by q. Then e p r + 1≤i<r e p i ∈ d∈D Zf d . By induction on r, we have e q ∈ d∈D Zf d . Note 6.4.2. Proposition 6.4.1 is true for any choice of D. However, if we choose D such that d 1 | d 2 | . . . | d t , where t = |D|, then the relations between the f di become simpler. First note that f di is an idempotent for every 1 ≤ i ≤ t. To make them orthogonal, put f di := f di -f di-1 for every 1 < i ≤ t. Let s i be the order of f di . Then

P A = t i=1 Zf di ∼ = t i=1

Algorithmes pour les anneaux finis -Résumé

Cette thèse s'attache à décrire des algorithmes qui répondent à des questions provenant de la théorie des anneaux et des modules. Nous restreindrons essentiellement notre étude à des algorithmes déterministes, en temps polynomial, ainsi qu'aux anneaux et modules finis.

Les trois premiers chapitres préparent le terrain pour le reste du texte. Nous y rappelons les notions nécessaires de la théorie des modules et des anneaux, et nous présentons une collection d'algorithmes qui permettent de réaliser des calculs dans les groupes abéliens et les anneaux finis.

Le premier des principaux résultats de cette thèse concerne le problème de l'isomorphisme entre modules : nous décrivons deux algorithmes distincts qui, étant donné un anneau fini R et deux R-modules M et N finis, déterminent si M et N sont isomorphes. S'ils le sont, les deux algorithmes exhibent un tel isomorphisme.

De plus, nous montrons comment calculer un ensemble de générateurs de taille minimale pour un module donné, et comment construire des couvertures projectives et des enveloppes injectives. Nous décrivons ensuite des tests mettant en évidence le caractère simple, projectif ou injectif d'un module, ainsi qu'un test constructif de l'existence d'un homomorphisme de modules surjectif entre deux modules finis, l'un d'entre eux étant projectif. Par contraste, nous montrons le résultat négatif suivant : le problème consistant à tester l'existence d'un homomorphisme de modules injectif entre deux modules, l'un des deux étant projectif, est NP-complet.

La dernière partie de cette thèse concerne le problème de l'approximation du radical de Jacobson d'un anneau fini. Il s'agit de déterminer un idéal bilatère nilpotent tel que l'anneau quotient correspondant soit "presque" semi-simple. La notion de "semi-simplicité approchée" que nous utilisons est la séparabilité.

Algoritmen voor eindige ringen -Samenvatting

We zijn in dit proefschrift geïnteresseerd in het beschrijven van algoritmen voor problemen over ringen en modulen. De nadruk ligt op deterministische algoritmen die in polynomiale tijd werken, en op ringen en modulen die eindig zijn.

De eerste drie hoofdstukken leggen de basis voor de rest: we behandelen voorkennis over ringen en modulen, en stellen een compendium van algoritmen samen die ons basisbewerkingen op eindige abelse groepen en eindige ringen laten uitvoeren.

Het eerste hoofdresultaat van dit proefschrift betreft het isomorfieprobleem voor modulen: we beschrijven twee verschillende algoritmen die voor een eindige ring R en twee eindige R-modulen M en N , in polynomiale tijd beslissen of er een Rmoduulisomorfisme tussen M en N bestaat. Als er zo'n isomorfisme bestaat, wordt het door de algoritmen berekend.

Verder laten we zien hoe men een verzameling voortbrengers van minimale grootte voor een gegeven moduul kan berekenen, en hoe men projectieve overdekkingen en injectieve omhulsels kan berekenen. We beschrijven ook methoden om te toetsen of een moduul simpel, projectief of injectief is, en constructieve tests voor het bestaan van een surjectief moduulhomomorfisme tussen twee modulen, waarvan er een projectief is. Als negatief resultaat, laten we zien dat testen of er een injectief moduulhomomorfisme bestaat tussen twee modulen, waarvan er een projectief is, NP-volledig is.

Het laatste deel van dit proefschrift is erop gericht, een goede benadering voor het Jacobson-radicaal te vinden, dat wil zeggen, een tweezijdig nilpotent ideaal waarvan de resulterende quotiëntring "bijna" semisimpel is. Het begrip dat we gebruiken om semisimpliciteit te benaderen is separabiliteit. 127

1 . 1

 11 Algorithms and complexity . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Basic ring theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Basic module theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 More ring theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Idempotents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 More module theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Quasi-Frobenius rings . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Frobenius algebras and symmetric algebras . . . . . . . . . . . . . . . 1.9 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

F q finite field with q elements Z

 elements ring of integers Z >0 set of positive integers Z ≥0 set of non-negative integers |S| cardinality of a set S M n (R) ring of n × n matrices with entries in the ring R M n×m (R) set of n × m matrices with entries in the ring R R e the enveloping algebra of R (page 76) R o the opposite ring of the ring R R[G] the group ring of G over R Max(R) set of maximal ideals of a commutative ring R Spec(R) set of prime ideals of a commutative ring R J(R) Jacobson radical of a ring R Z(R) centre of a ring R char(R) characteristic of a ring R rad(n) the product of all primes dividing an integer n → injective map surjective map M ⊗ R N tensor product of M with N over R End R (M ) ring of R-endomorphisms of M Hom R (M, N ) group of R-homomorphisms from M to N M fg R category of finitely generated right R-modules M R category of right R-modules v vi Algorithms for finite rings fg R M category of finitely generated left R-modules R M category of left R-modules R M S R-S-bimodule M Chapter 1

Definition 1 .

 1 1.1 ([8],Section 4,7). Let S be a finite set of positive integers. A coprime base for S is a set of positive integers B such that:(i) 1 /∈ B, (ii) elements of B are pairwise coprime, (iii) each element of S can be written as a product of powers of elements of B.Theorem 1.1.2 ([8], Algorithm 18.1). (Coprime Base Algorithm) There exists a deterministic polynomial-time algorithm that takes as input a finite set of positive integers S and outputs a coprime base B for S, and a factorisation of each element of S into products of powers of elements of B.

Definition 1 . 3 . 8 .

 138 where R is nonzero and I is infinite, then |I| = |J|. Let R be a ring with left IBN and let M ∼ = R (I) be a free R-module, for some indexing set I. The rank of M over R, which we denote by rk R (M ) is the cardinality of I. Example 1.3.9 ([56], Example 1.6). The following rings have left IBN: division rings, local rings, nonzero commutative rings, nonzero left-artinian rings. Definition 1.3.10. Let R be a ring and M, N two R-modules. A module homomorphism f : M → N is a homomorphism of the underlying abelian groups, such that for all r ∈ R, we have f (rm) = rf (m). Definition 1.3.11. Let R be a ring and M an R-module. Then (i) M is simple if M = 0 and its only submodules are 0 and M . (ii) M is indecomposable if M = 0 and M cannot be written as the direct sum of two nontrivial, proper submodules. (iii) M is semisimple if for any submodule N ≤ M , there exists C ≤ M such that M = N ⊕ C. (iv) M is artinian if every descending chain of submodules of M stabilizes. (v) M is noetherian if every ascending chain of submodules of M stabilizes.

  , where : R → R/I. Clearly M is then annihilated by I. 1.4 More ring theory 1.4.1 Menagerie of rings I Definition 1.4.1. Let R be a ring. Then

Theorem 1 .

 1 4.3 ([57], Theorems 2.5, 2.8, Corollary 3.7). Let R be a ring. Then the following are equivalent: (i) The left-regular module, R R, is semisimple. (ii) All left R-modules are semisimple. (iii) All left R-modules are projective. (iv) All left R-modules are injective. Replacing "left" with "right" gives further equivalent conditions. Definition 1.4.4. Let R be a ring. If R satisfies any of the conditions of Theorem 1.4.3, then R is said to be a semisimple ring. Theorem 1.4.5 ([57], Theorem 3.5). (Wedderburn's Theorem) Let R be a ring. Then R is semisimple if and only if

Theorem 1 .

 1 5.5 ([57], Proposition 22.2). Let R be a left-noetherian ring. Then R has a block decomposition. Proposition 1.5.6. Let R be a ring. If R has a block decomposition R = Re 1 + . . . + Re n , where {e i } n i=1 is a set of orthogonal centrally primitive idempotents of sum 1, then Z(R) has block decomposition Z(R) = Z(R)e 1 + . . . + Z(R)e n . Theorem 1.5.7 ([57], Corollary 19.19). A nonzero left-artinian ring R is local if and only if R has no nontrivial idempotents. Proposition 1.5.8. Let R be a left-artinian ring with Jacobson radical J(R). Then the natural projection p : R → R/ J(R) induces a surjective map on the set of idempotents.

Definition 1 . 6 . 11 .

 1611 Let R be a ring. If R is injective as a left-regular (resp. rightregular) module, we say that R is left (resp. right) self-injective. Theorem 1.6.12 ([56], §3A; [76], Proposition 3.42). Let R be a ring and I an Rmodule. Then the following are equivalent: (i) I is injective. (ii) Every injective R-module homomorphism I → M splits. (iii) (Baer's Test) For all left ideals K ⊂ R, any R-homomorphism K → I can be extended to a map R → I. (iv) Every short exact sequence 0 → I → M → N → 0, where M is an R-module and N is a cyclic R-module, splits. (v) The functor Hom R (-, I) is exact on R M.

Proposition 1 . 6 .

 16 19 ([58], Corollary 3.6). If R is connected, then every projective R-module has constant rank.

1. 6 . 6

 66 Hom & ⊗ Let R, S, T be rings, let M be an R-S-bimodule, N an R-T -bimodule and P an S-Tbimodule. Then

(

Definition 1 . 6 . 23 .

 1623 Let M be an R-module. A superfluous submodule of M is an R-module S ⊆ M such that ∀N ≤ M : (S + N = M ⇒ N = M ).

Theorem 1 . 6 .

 16 25 ([57], Proposition 24.10, Example 24.11(3), Theorem 24.18). Let R be a ring.

Note 2 . 1 . 5 .

 215 (i) The dual lattice is a lattice. (ii) rank(L ) = rank(L) and det(L ) = det(L) -1 . (iii) L = L.

Theorem 2 . 1 . 6 (

 216 [START_REF] Lenstra | Lattices. In Algorithmic number theory: lattices, number fields, curves and cryptography[END_REF],Section 14). There exists a deterministic polynomial-time algorithm that, given a triple (m, n, f ), with n, m ∈ Z ≥0 and f ∈ M n×m (Z) a matrix representing a group homomorphism f : Z m → Z n , computes k := rank(f ) and a basis b 1 , . . . , b m for Z m such that b 1 , . . . , b m-k is a basis for ker f and f (b m-k+1 ), . . . , f (b m ) is a basis for im f .

Definition 2 . 3 . 2 .

 232 Let G be a finitely generated abelian group. An exact-sequence representation of G consists of a triple (m, n, f ), where m, n ∈ Z >0 and f ∈ Hom(Z m , Z n ) are such that coker(f ) ∼ = G. Proposition 2.3.3. Let G be a finitely generated abelian group and let f ∈ M n×m (Z) be a presentation matrix of G. If n = m, then G is finite if and only if det(f ) = 0. In this case, |G| = | det(f )|.

  1.2) to the set {n, m} to obtain a set P of coprime divisors of nm and a factorisation n = p∈P p np and m = p∈P p mp , where n p , m p ∈ Z ≥0 . Define n = p∈P np>mp p np and m = p∈P np≤mp p mp Let x = n n x and y = m m y. Since n and m are coprime, the order of z := x + y is equal to lcm(n , m ) = lcm(n, m).

Lemma 2 . 6 . 8 .

 268 Let L = Z n and H ⊆ L a subgroup. Suppose B = {b 1 , . . . , b n } is a basis of L. Then the exponent of L/H is equal to the lowest common multiple of the orders of b 1 , . . . , b n in L/H.

t n=1 b ijn e n . Then e k e i s j = m a

 m kim e m s j = m,n a kim b mjn e n .(3.9)

1 .

 1 Ring Isomorphism Problem (i) Decision version: Given two finite rings, decide if they are isomorphic. (ii) Search version: Given two finite rings, find an isomorphism if one exists. (iii) Counting version: Given two finite rings, compute the number of isomorphisms between them. 2. Ring Automorphism Problem (i) Decision version: Given a finite ring, decide if it has a nontrivial ring automorphism. (ii) Search version: Given a finite ring, find a nontrivial automorphism if one exists. (iii) Counting version: Given a finite ring, compute the number of its automorphisms.

Proposition 4 . 3 . 1 .

 431 If R is a left-artinian ring, then a left (or right) ideal I of R is nil if and only if it is nilpotent.

  Then 0 = I 2n = α∈A β∈B Rβα, so there exists b ∈ B and a ∈ A such that b • a = 0.

Proposition 4 . 3 . 6 .

 436 If a splitter exists, then there exists a splitter in any set of k-module generators of Hom R (M 1 , M 2 ) and in any set of End R (M 1 )-generators of Hom R (M 1 , M 2 ).

Theorem 6 . 2 . 3 (

 623 [20], Chapter II, Proposition 1.1). Let R be a commutative ring and S an R-algebra. Then the following are equivalent:(i) S is separable over R.(ii) The exact sequence of S e -modules 0 → ker(φ) → S e φ -→ S → 0 splits. (iii) There exists an element e ∈ S e such that φ(e) = 1 and ∀s ∈ S, (s⊗1)e = (1⊗s)e. Note 6.2.4. The element e in (iii) is necessarily an idempotent, since e 2 -e = (e -(1 ⊗ 1))e ∈ ker(φ)e = 0, and it is referred to as a separability idempotent. It arises as the image of 1 ∈ S under a splitting of φ and is in general not unique. Note 6.2.5.

Proof.

  Let S e = S ⊗ R S o and (S o ) e = S o ⊗ R S. Consider the two exact sequences 0

Definition 6 . 2 . 32 .

 6232 Let R be a commutative ring. Let B(R) be a collection of Azumaya R-algebras such that every Azumaya R-algebra is isomorphic to exactly one element of B(R). LetB o (R) = {A ∈ B | A ∼ = End R (P ) as R-algebras, for some R-progenerator P }.Define an equivalence relation ∼ on B(R) by:A ∼ B ⇐⇒ there exist Y, Z ∈ B o (R) such that A ⊗ R Y ∼ = B ⊗ R Z as R-algebras.Denote by[A] the equivalence class of A ∈ B(R) under ∼. The set of all such equivalence classes, denoted by Br(R), together with binary operation given by [A] • [B] = [A ⊗ R B] is an abelian group called the Brauer group of R. The identity is given by [R] and inverses are given by [A] -1 = [A o ].

  Let p be a prime and e ∈ Z >0 . Let C = category of finite local commutative Z/p e Z-algebras, D = category of finite fields of characteristic p, and consider the covariant functor Red

  (ii) Let C := B/B[p e-e ] and consider the canonical map π : A C. First note that ker(π) := ker(A B := A/I A/(Z/p e Z) C := B/B[p e-e ]) = (I A/(Z/p e Z) : p e-e A), where (I A/(Z/p e Z) : p e-e A) := {x ∈ A | p e-e x ∈ I A/(Z/p e Z) }. Further, π -1 C[p e -1 ] = {x ∈ A | p e -1 x ∈ (I A/(Z/p e Z) : p e-e A)} = (I A/(Z/p e Z) : p e-1 A). Since C is free as a Z/p e Z-module, we have that C[p e -1 ] = pC, so π -1 C[p e -1 ] = pA + ker(π). Hence (I A/(Z/p e Z) : p e-e A) + pA = (I A/(Z/p e Z) : p e-

Proposition 6 . 3 . 24 .

 6324 Let A be a finite ring and let char(A) := m, for some m ∈ Z >0 . Suppose that A is projective as a Z/mZ-module and that all primes dividing m are large. Let B := A/I A/(Z/mZ) . Let m | m be such that rad(m) = rad(m/m ) and B/B[m ] is projective as a Z/ m m Z-module. Then B[m ] is nilpotent and B/B[m ] is separable over Z/ m m Z. Proof. Let p be a prime dividing m. Suppose its exponent in the prime factorisation of m is e, and its exponent in the prime factorisation of m is e-e ≥ 0. Let C := B/B[m ] and ϕ : A → B := A/I A/(Z/mZ) be the canonical map. Then ϕ -1 (B[p e-e ]) = {x ∈ A | p e-e x ∈ I A/(Z/p e Z) } = I A/(Z/p e Z) : p e-e A .We have already seen in Propositions 6.3.15 and 6.3.14 that (I A/(Z/p e Z) : p e-e A) + pA = (I A/(Z/p e Z) : p e-1 A).

  1 (B[p e-e ]) + pA)/pA = J(A/pA), so that ϕ -1 (B[p e-e ]) is nilpotent, and hence B[p e-e ] is nilpotent.Glueing along all primes (using Lemma 6.2.84), we get thatϕ -1 (B[m ]) + n A /n A = J(A/n A),(6.21) and B[m ] is nilpotent. Hence C/n C = (A/n A)/ J(A/n A) is semisimple. In particular, since n is squarefree, C/n C is separable over Z/n Z, by Theorem 6.2.44. Since n = rad(m) = rad(m/m ), we have by Theorem 6.2.18, part (iii) and Proposition 6.2.16, part (ii), that C is separable over Z/ m m Z.

.

  Note 6.3.26. The equality in (6.20) can be easily seen from the following diagram, since both sides of the equality are represented by the upper-left grey area left unhatched: is already projective over its prime subring, in the notation of our algorithms, we have A 0 := A = A 1 . Write k := Z/p e Z, Tr A := Tr A/k and I A := I A/k . Then Tr A (1) = 2, Tr A (X) = p e . The matrix representing the map A → Hom(A, Z/p e Z) is then given by F = 2 p e p e p 2e .

  three remarks: Remark I. The number of iterations performed by the first algorithm is unbounded.

  where the product is taken over maximal ideals of A and A m denotes the localisation of A at m. Let e m be the primitive idempotent corresponding to A m . Then e m has order a prime power, equal to exp(A + m ).Let Q = {exp(A + m ) | m ⊆ A maximal ideal}. Define a map Z >0 → A, q → e q, where e q = exp(A + m )=q e m . (6.24)

Proposition 6 . 4 . 1 . 26 )

 64126 B is a subring of A, since the e q are orthogonal idempotents of sum 1 (see Theorem 1.5.4). It is easy to see from Definition 6.2.48 that B = P A . Let A be a finite commutative ring such thatA + ∼ = d∈D (Z/dZ) n d .wheren d ∈ Z >0 for all d ∈ D. For d ∈ D, let A[d] = ker(A → A, a → da)andI d := n A[d] n .Then for all d ∈ D, there exists a unique element f d ∈ I d such that for all x ∈ I d , we have f d x = x. Moreover, P A = d∈D Zf d . Proof. Let d ∈ D. First note that A[d] is an ideal of A, and hence so is I d . Note that A[d] = m A m [d] = a d,m A m contained in the maximal ideal of A m . Then For uniqueness, suppose f d ∈ I d is another element such that for all x ∈ I d , we have f d x = x. Then f d = f d f d = f d .

i p i |d e p i ∈d∈D

  Zf d . To see this, let d ∈ D and suppose d = d 1 d 2 , where d 1 , d 2 ∈ Z >0 and (d 1 , d 2 ) = 1.

  Representing objects and basic constructions . . . . . . . . . . . . . . 2.4 Homomorphism groups and tensor products . . . . . . . . . . . . . . . 2.5 Splitting exact sequences . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Torsion subgroups, exponents, orders, cyclic decompositions . . . . . . 2.7 Homomorphism groups and tensor products reconsidered . . . . . . . 2.8 Projective Z/mZ-modules . . . . . . . . . . . . . . . . . . . . . . . . .

2 Linear algebra over Z: basic algorithms for finite abelian groups 2.1 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Hermite and Smith normal forms . . . . . . . . . . . . . . . . . . . . . 2.3 3 Linear algebra over Z: basic algorithms for finite rings 3.1 Representing objects and basic constructions . . . . . . . . . . . . . . 3.2 Computations with ideals . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Computing the centre and the prime subring of a finite ring . . . . . . 3.4 Computing the Jacobson radical . . . . . . . . . . . . . . . . . . . . . 3.5 Other known algorithms and open questions . . . . . . . . . . . . . . .

  Definition 1.2.6. A ring R is said to be simple if R is nonzero and the only two-sided ideals of R are 0 and R.

Definition 1.2.7. Let (R, + R , • R ), (S, + S , • S ) be two rings. A ring homomorphism F : R → S is a homomorphism of the underlying abelian groups, such that F (1 R ) = 1 S and for all r 1 , r 2 ∈ R, we have

1 )

 1 Proposition 1.4.11 ([57], Exercise 4.12B). For any collection of rings {A i } i∈I we have J( i A i ) = i J(A i ).Proposition 1.4.12 ([57], Example 21.14). Let R be a ring and n

  but M is not simple.

	Definition 1.6.3. Let R be a ring. We say R M, the category of R-modules, satisfies
	the converse of Schur's Lemma if every R-module whose endomorphism ring is a
	division ring, is in fact simple.
	Theorem 1.6.4 ([71], Theorem 1.6). (Converse Schur) Let R be a semiprimary ring.
	Then the category of R-modules, R M, satisfies the converse of Schur's Lemma if and
	only if R is a finite direct product of full matrix rings over local rings.
	1.6.2 Nakayama's Lemma
	Theorem 1.6.5 ([57], Lemma 4.22). (Nakayama's Lemma) Let R be a ring and
	J ⊆ R a left ideal of R. Then the following are equivalent:

  The functor Hom R (P, -) is exact on R M. Let p be a prime and let e ∈ Z >0 . A Z/p e Z-module is finitely generated projective if and only if it is free of finite rank. (iii) Let n ∈ Z >0 . A Z/nZ-module is finitely generated projective if and only if it is a direct sum of copies of modules of the form Z/mZ, with m | n such that

	(iii) Every surjective R-module homomorphism M	P splits.
	(iv) Finitely generated projective modules over Z and Z/nZ, for n ∈ Z >0 , are easy to
	describe.
	Proposition 1.6.8. (i) A Z-module is finitely generated projective if and only if
	it is free of finite rank.
	(ii) gcd( n m , m) = 1.
	Proof. Part (i) is a consequence of Z being a principal ideal domain. Part (ii) holds
	since Z/p e Z is a local ring.
	For part (iii), note that Z/mZ is a Z/nZ-module if and only if m | n. It is now
	enough to show that if m | n, then Z/mZ is Z/nZ-projective if and only if gcd( n m , m) = 1. Suppose n = i∈I p ai i , where I is a finite indexing set and all p i are distinct primes. Then gcd( n aj m , m) = 1 if and only if m = j∈J p j
	1.6.3 Projective and injective modules
	Definition 1.6.6. Let R be a ring and P an R-module. Then P is said to be pro-
	jective if for any surjective R-module homomorphism g : B	C and any R-module
	homomorphism f : P → C, there exists an R-module homomorphism h : P → B such
	that f = gh:
			P
	h		f
	B	g	C	0.
	Theorem 1.6.7 ([56], §2A). Let R be a ring and P an R-module. Then the following
	are equivalent:
	(i) P is projective.
	(ii) P is a direct summand of a free R-module.

  1.6.4 Flat and finitely presented modulesDefinition 1.6.13. Let R be a ring and M an R-module. We say M is flat over R if the functor -⊗ R M is exact. Definition 1.6.15. Let R be a ring and M an R-module. We say M is finitely presented over R if there is an exact sequence R m → R n → M → 0, for some m, n ∈ Z ≥0 .

	Proposition 1.6.14 ([56], Proposition 4.3; [57], Theorem 23.20). Over a left-artinian
	ring, the notions of projective modules and flat modules coincide.
	Proposition 1.6.16 ([56], Proposition 4.29). A ring R is left-noetherian if and only
	if every finitely generated R-module is finitely presented.

  Theorem 1.6.27([57], Theorem 3.30). Let R be a ring and M ⊆ I two R-modules. Let M be an R-module. Suppose I and I are two injective hulls of M . Then there exists an isomorphism I → I which is the identity on M . (iii) Let M 1 , . . . , M n be R-modules. Suppose I j is an injective hull of M j , for all 1 ≤ j ≤ n. Then Let I be an injective hull of M . Then M is injective if and only if M = I.

	Then the following are equivalent:
	(i) I is maximal essential over M , i.e. I ⊇ e M and no module properly containing
	I can be an essential extension of M .
	(ii) I is injective, and is essential over M .
	(iii) I is minimal injective over M , i.e. I is injective and if I is an injective module
	such that M ⊆ I ⊆ I, then I = I .
	Definition 1.6.28. Let M be an R-module. An injective hull of M is an R-module
	I ⊇ M satisfying one of the conditions of Theorem 1.6.27.
	Theorem 1.6.29 ([57], Lemma 3.29, Corollary 3.32, Example 3.38). Let R be a ring.
	(i) Every R-module has an injective hull.
	(ii) n j=1 I j is an injective hull of	n j=1 M j .
	Theorem 1.6.30 ([56], Lemma 3.28, Theorem 3.30). Let R be a ring and M an
	R-module. 1.7 Quasi-Frobenius rings
	Theorem 1.7.1 ([56], Theorems 15.1, 15.9, Remark 15.10). Let R be a ring. Then
	the following are equivalent:
	(i) R is left-noetherian and left self-injective.
	(ii) R is right-noetherian and left self-injective.
	(iii) R is left-noetherian and right self-injective.
	(iv) R is right-noetherian and right self-injective.
	(v) all projective R-modules are injective.
	(vi) all injective R-module are projective.
	Definition 1.7.2. Let R be a ring. If R satisfies any of the conditions of Theorem
	1.7.1, then R is said to be a quasi-Frobenius ring.
	Example 1.7.3. The following rings are quasi-Frobenius:
	(i) fields,
	(ii) Z/nZ, for n ∈ Z >0 ,
	(iii) semisimple rings,
	(iv) M n (R), for R a quasi-Frobenius ring and n ∈ Z ≥0 , (v) the group ring R[G], for R a quasi-Frobenius ring and G a finite group,
	(vi) Galois rings (see Note 6.2.59).

  •, • denotes the standard inner product on R n . A sublattice of L is a subgroup of L.

	Proposition 2.1.2 ([68], Section 2). A subset L ⊂ R n is a lattice if and only if there
	exists a set B ⊂ R n of R-linearly independent vectors such that
	L =

b∈B

Zb.

  is a basis of H over Z. Note that by Theorem 2.1.6, we can recover a basis of H from any generating set. Proposition 2.1.8. There exists a deterministic polynomial-time algorithm that, given n ∈ Z >0 and two subgroups H 1 , H 2 ⊆ Z n , computes H 1 ∩ H 2 and H 1 + H 2 , together with the inclusion maps H 1 ∩ H 2 → H i and H i → H 1 + H 2 , for i = 1, 2. Proof. Consider the group H 1 ⊕ H 2 , i.e. the group with elements of the form (h 1 , h 2 ), where h 1 ∈ H 1 and h 2 ∈ H 2 , together with componentwise addition. Let φ : H 1 ⊕ H 2 → Z n be the map given by (h 1 , h 2 ) → h 1 -h 2 . Then ker(φ) = H 1 ∩ H 2 and im(φ) = H 1 + H 2 , and both can be efficiently computed by Theorem 2.1.6. This produces bases of H 1 ∩ H 2 and H 1 + H 2 in terms of the standard basis of Z n . Now H 1 ∩H 2 is equal to the image of the projection ker(φ) → H 1 . This gives a basis for H 1 ∩H 2 in terms of the basis of H 1 . Similarly for H 2 . Further,

  To represent a subgroup H of G, we need to represent it as a group and additionally, to produce an embedding H → G that tells us how H sits inside G, i.e. we need to give the algorithm a triple (r, s, h) and a map of free Z-modules g, that induces an injective map H → G.Example 2.3.9. It is important to specify the injection: if G = Z/2Z ⊕ Z/2Z, then the subgroup Z/2Z sits inside G in three different ways.Proposition 2.3.10. There exists a deterministic polynomial-time algorithm that, given a finitely generated abelian group G and a finite set S ⊂ G, computes the subgroup H ≤ G generated by S.

Proof. The desired output of the algorithm is a triple (r, s, h) representing H as a group, together with an injective group homomorphism i : H → G. Suppose the group G is represented by triple (m, n, f ).

  2.1.6 and Proposition 2.1.8. The maps ker(g) → G 1 , im(g) → G 2 and G 2 → coker(g) can be obtained from Propositions 2.3.10 and 2.3.13.

	2.3.4 Direct sums of groups

Proposition 2.3.16. There exists a deterministic polynomial-time algorithm that, given two finitely generated abelian group

G 1 , G 2 , computes the direct sum G 1 ⊕ G 2 .

Proof. Suppose G 1 and G 2 are represented via triples (m 1 , n 1 , f 1 ) and (m 2 , n 2 , f 2 ) respectively. Then the direct sum G 1 ⊕G 2 is represented by triple (m 1 +m 2 , n 1 +n 2 , F ), where F is an (m 1 + m 2 ) × (n 1 + n 2 ) integer matrix with block form

  where t is a left splitting of i, that is, a group homomorphism such that t • i = id H .

	2.6 Torsion subgroups, exponents, orders, cyclic de-
	compositions

2.6.1 Computing the order of a finite abelian group

Recall that a finitely generated abelian group G represented by triple (m, n, f ) is finite if and only if the basis of im f given by the algorithm in Theorem 2.1.6 has n elements.

Proposition 2.6.1. There exists a deterministic polynomial-time algorithm that, given a finitely generated abelian group G, computes the order of G.

Proof. To test if G is finite, we run the algorithm of Theorem 2.1.6 and check if the basis of im f has n elements. If so, we compute the determinant of the matrix whose columns are given by these n basis elements, which is then equal to |G|. Otherwise we conclude that G has infinite order.

  Proposition 6.2.15 ([54], Chapter III, Theorem 5.1). Let S be a ring. If S is separable over its centre, then S is projective as a module over its centre.

	Proposition 6.2.16 ([54], Chapter III, Proposition 1.7).

  R 2 be two commutative rings. Let S 1 be an R 1 -algebra andS 2 an R 2algebra. Then S 1 × S 2 is separable over R 1 × R 2 if and only if S 1 is separable over R 1 and S 2 is separable over R 2 .(iii) Let R be a commutative ring and S 1 , S 2 two R-algebras. Then S 1 ×S 2 is separable over R if and only if both S 1 and S 2 are separable over R.Corollary 6.2.17. Let R be a commutative ring, R a commutative R-algebra and S a separable R-algebra. Then S ⊗ R R is separable over over R .Proof. In Proposition 6.2.16, part (i), take R 1 := R, R 2 := R , S 1 := S and S 2 := R .

	Theorem 6.2.18 ([

  Definition 6.2.21. An R-algebra S satisfying the conditions of Theorem 6.2.20 is called an Azumaya algebra over R. Note 6.2.22. From Theorem 6.2.20, part (ii), it is easy to see that if S is Azumaya over R, then S o is also Azumaya over R. This gives another, more conceptual way of showing that separability is stable under taking opposites. Suppose S is separable as an algebra over a commutative ring R. Then S is Azumaya over Z(S) and Z(S) is separable over R. Now R o = R and Z(S) = Z(S o ). So Z(S o ) is separable over R o and S o is Azumaya over Z(S o ). Hence S o is separable over R, by Theorem 6.2.14, part (iii). Proposition 6.2.25 ([80], Proposition 3.9). Let R be a commutative ring and A an R-algebra that is Azumaya of constant rank over R. Then there exists a faithfully flat ring extension S of R, and n ∈ Z >0 such that A ⊗ R S ∼ = M n (S). Corollary 6.2.26. Let R be a commutative ring and A an Azumaya R-algebra. Then the rank of A over R, as a function on Spec(R), is a square.

	Example 6.2.23 ([26], §8). Over a field, an algebra is Azumaya if and only if it is
	central simple.
	Example 6.2.24 ([20], Chapter II, Proposition 4.1). Let R be a commutative ring.
	Then the endomorphism ring of any R-progenerator is Azumaya over R.

  The inverse of the map in (6.5) is given byW e (F p d ) ←-(p, d, e).Theorem 6.2.62. Let P denote the set of primes. Then there is a bijection between the sets {finite connected separable rings}/ ∼ = ←→ P × Z >0 × Z >0 × Z >0 ,

	(6.6)
	Proof. This is a consequence of Theorem 6.2.54, Definition 6.2.55 and Proposition
	6.2.60.
	where
	[A] -→ (p, d, e, n),

  .8)Proof. By Theorem 6.2.52, a finite connected ring is separable if and only if it is separable projective over its prime subring, which by Theorem 6.2.36 is equivalent to being Azumaya over its centre and its centre being separable over its prime subring. Given Proposition 6.2.61, we are thus left with classifying Azumaya algebras over truncated Witt rings.The map given in (6.7) is well-defined, since W e (F p d ) is a local ring, and hence the degree of any Azumaya W e (F p d )-algebra is well-defined and is a square (Corollary 6.2.26). Injectivity follows from Example 6.2.34, part 3. Surjectivity follows from the fact that matrix rings over commutative rings are separable (Example 6.2.11).

  P is finitely generated projective if and only if there exist n ∈ Z >0 and a collection {x i , f i } n i=1 with x i ∈ P and f i ∈ Hom

	.10)
	which makes the following diagram commute:
	End

k (P ) × End k (P ) End k (P )

(Hom k (P, k) ⊗ k P ) × (Hom k (P, k) ⊗ k P ) Hom k (P, k) ⊗ k P.

composition ϕ×ϕ ϕ (6.11) Recall the definition of a dual basis. Lemma 6.2.65 ([57], Lemma 2.9, Remark 2.11). (Dual Basis Lemma) Let k be a ring and let P be a k-module. Then (i) P is projective if and only if there exists a collection {x i , f i } i∈I for some index set I, with x i ∈ P and f i ∈ Hom k (P, k) such that ∀x ∈ P : f i (x) = 0 for almost all i, and x = n i=1 f i (x)x i . (ii) k (P, k) such that ∀x ∈

  Proposition 6.2.86 ([64],Proposition 6.11). Let k be a commutative ring and R a commutative k-algebra. Then R is finite-étale over k if and only if R is finitely generated projective as a module over k and Tr R/k generates Hom k (R, k). Note 6.2.87. This is usually taken to be the definition of finite-étale.

  1 A).(6.18) Since C is free as a Z/p e Z-module, by Theorem 6.2.18, part (iii), we have that C is separable over Z/p e Z if and only if C/pC is semisimple. But, since p is large, Let i ∈ I A/(Z/nZ) . By(6.19), the image of i in A/pA lies in J(A/pA), so it annihilates all simple A/pA-modules. In particular, it annihilates S. Hence i annihilates all simple A-modules. So i ∈ J(A). otherwise it would be a nilpotent element of A. Hence Tr A/(Z/mZ)

	C/pC = (A/pA)/((I A/(Z/p e Z) : p e-e A) + pA)/pA)
	= (A/pA)/(I A/(Z/p e Z) : p e-1 A)/pA), by (6.18)
	= (A/pA)/I (A/pA)/Fp , by (6.17)
	= (A/pA)/ J(A/pA), by Theorem 6.3.8.
	A	A/pA
	Tr A/(Z/nZ)	Tr (A/pA)/Fp
	Z/nZ	F p .
	Since p is large, by Theorem 6.3.8 we have
	(I A/(Z/nZ) + pA)/pA ⊆ J(A/pA).	(6.19)
	Proposition 6.3.17. Let A be a finite ring and let m := char(A). Suppose A is
	projective over Z/mZ and that all primes dividing m are large. Then char(A) =
	char(A/I A/(Z/mZ) ).
	Proof. Write I := I A/(Z/mZ) . By Proposition 6.2.72, for all primes p | m, we have
	that Tr

Proposition 6.3.16. Let A be a finite ring and let n := char(A). Suppose that A is projective as a Z/nZ-module. If all primes p dividing n are large, then

I A/(Z/nZ) ⊆ J(A).

Proof. Let S be a simple A-module. Then S has exponent p for some prime p | n. So S is a simple module over A/pA. By Proposition 6.2.72, part (iv), the following diagram commutes: A/(Z/mZ) (1) ≡ dim Fp (A/pA) mod p. Since all primes dividing m are large, we have p > dim Fp (A/pA), and so p Tr A/(Z/mZ) (1) for all p | m. Hence Tr A/(Z/mZ) (1) is a unit in A. Now by Proposition 6.3.16 we have I ⊆ J(A), so Tr A/(Z/mZ) (1) / ∈ I,

Acknowledgements

CV Acknowledgements I would like to thank... Professor Hendrik Lenstra, for his inspiring guidance. Professor Karim Belabas, for being so generous with his time. Dr. Gábor Ivanyos, for many useful comments regarding my work. Professor Peter Stevenhagen. Professor Bart de Smit. Raphael Hochard, for the French translation of the abstract of this thesis (page 126). my parents. Dr. Radu Gaba, Mihai Bȃlunȃ and Professor Oliver Riordan, my mathematical parents. Erik Thörnblad. Pınar Kılıçer, Dino Festi, Martin Djukanovic, Abtien Javanpeykar and Valerio Dose. Djordjo Milovic. Maarten Kampert. Lucian Corchiş. Dr. Alvaro Guevara. Romina Lupşeneanu.

Chapter 5

A miscellaneous collection of algorithms

Testing if a ring is a field

One basic question we may ask ourselves when presented with a finite ring is if it is not in fact a field. Lemma 5.1.1. Let p be a prime and R a finite commutative F p -algebra. Then the following are equivalent:

(i) The map F : R → R given by x → x p is injective. (ii) R has no nonzero nilpotent elements. (iii) R is a field.

Proof. Note that F is an F p -linear map.

(i)⇒(ii): Suppose there exists 0 = x ∈ R and n ∈ Z >1 such that x n-1 = 0 and x n = 0. Choose d ∈ Z ≥0 maximal such that dp < n. Then (d + 1)p ≥ n and d + 1 < n, so 0 = x d+1 ∈ ker(F ).

(ii)⇒(iii): If R has no nonzero nilpotent elements, then R is semisimple (see Theorem 1.4.9, part (iii)). Since R is commutative, it must be a field.

(iii)⇒(i) is clear.

Theorem 5.1.2. There exists a deterministic polynomial-time algorithm that, given a finite ring R, determines whether or not R is a field.

Proof. If char(R) is not a prime or R is not commutative, then R is not a field. This can be tested using Theorem 1.1.3 and Theorem 3.3.1. Otherwise R is a commutative F-algebra and we use Lemma 5.1.1, part (i) to test whether it is a field.

Note 5.1.3. Another deterministic polynomial-time algorithm for testing if a finite ring is a field is given in [START_REF] Arvind | The complexity of black-box ring problems[END_REF], Section 5, Theorem 4.

Proof. Let F be a finite field and let U, V be two finite-dimensional F-vector spaces of the same dimension. Let 0 = L ≤ Hom F (U, V ) be a linear subspace. Consider the ring R = F ⊕ U, with componentwise addition and multiplication given by (a, x)(b, y) = (ab, ay + bx).

Then R is a commutative local ring, with maximal ideal U , and

We make M into an R-module by defining an action:

(a, u) • (l, v) := (al, av + l(u)), for all a ∈ F, u ∈ U , l ∈ L and v ∈ V . Note that any homomorphism R → M is determined by the image of 1 R . Let ψ : R → M be an R-module homomorphism, and suppose 1 → (l, v), for some (l, v) ∈ M . Then im(ψ) = F(l, v) + (0, lU ) and ψ ∈ Hom R (R, M ) is injective if and only if l ∈ L is an isomorphism.

Theorem 5.9.5. There exists a deterministic polynomial-time reduction from the decision (resp. constructive) version of nonsingular matrix completion to the problem of deciding existence of (resp. finding) an injective module homomorphism from an R-module M to R, where R is a finite commutative local ring containing a field.

Proof. Let F be a finite field and let U, V be two finite-dimensional F-vector spaces of the same dimension. Let 0 = L ⊆ Hom F (U, V ) be a linear subspace. Consider the ring

with componentwise addition and multiplication given by

Then R is a commutative ring with unique maximal ideal L ⊕ U ⊕ V . Note that L ⊕ V is a two-sided ideal in R. Put

Note that U 2 = 0, so M also has the structure of a local commutative ring, with maximal ideal U . Note that Hom R (M, R)

are a good "approximation" to semisimple algebras. Section 6.2.6 gives a complete classification of finite rings that are separable over Z, as finite products of matrix rings over certain commutative rings. It turns out that finite separable rings are automatically projective over a certain subring, which we will refer to as the generalised prime subring (see Section 6.2.5). With this in mind, we make the following definition. Definition 6.1.1. Let A be a finite ring. We say an ideal j A ⊂ A is an approximation of the Jacobson radical of A if it satisfies the following conditions:

The prime subring and generalised prime subring of A/j A coincide.

If j A is an approximation of the Jacobson radical of A, then the ring A/j A has many of the good properties that semisimple rings have: it has "many" projective and injective modules, it is quasi-Frobenius, it is a symmetric algebra over its prime subring and it is isomorphic to a product of matrix rings over commutative local rings. However, as opposed to semisimplicity, which can be neither tested nor enforced (see Note 3.4.2), separability is a much friendlier notion in algorithmic contexts. In Sections 6.3 and 6.4, we prove the following results. Theorem 6.1.2. There exists a deterministic polynomial-time algorithm that, given a finite ring A, computes an approximation of the Jacobson radical of A.

We prove Theorem 6.1.2 by exhibiting two algorithms that produce approximations of Jacobson radicals of finite rings. Proposition 6.1.3. Let F be the class of finite rings. The two families of ideals (j A ) A∈F and (j A ) A∈F , produced by the two algorithms described in the proof of Theorem 6.1.2 are functorial under isomorphisms, i.e. if φ : A → B is an isomorphism of finite rings, then φ(j A ) = j B and φ(j A ) = j B . Theorem 6.1.4. There exists a deterministic polynomial-time algorithm that, given a finite ring A, computes the generalised prime subring of A.

In Section 6.3.6, we look at some basic examples of the running of these algorithms.

Separability

Separable algebras

We begin with a study of separable algebras and some of their basic properties. We argue that the notion of separability is a good starting point in our quest to approximate semisimplicity. The main references for this section are [20,[START_REF] Knus | Théorie de la descente et algèbres d'Azumaya[END_REF]. Definition 6.2.1. Let R be a commutative ring and S an R-algebra. We say S is separable over R if S is projective as a module over S e := S ⊗ R S o , where S o denotes the opposite ring of S and the module structure is given by (s ⊗ s )t = sts , for s, s , t ∈ S. Note 6.2.33. Since all Azumaya R-algebras are finitely generated projective as Rmodules, B(R) is indeed a set. It is also easy to check that ∼ is an equivalence relation and that Br(R) is an abelian group. Example 6.2.34. (Brauer groups) 1. If k is a finite field, Br(k) is trivial (see [START_REF] Serre | Local Fields. Graduate Texts in Mathematics[END_REF], Chapter X, §7). 2. Br(Z) is trivial (see [START_REF] Farb | Noncommutative Algebra[END_REF], page 196). 3. If k is a finite commutative ring, then Br(k) is trivial (see [START_REF] Szymik | The Brauer group of Burnside rings[END_REF], Proposition 4.1).

For more on Brauer groups, see [20], Chapter III, Section 5.

Separable projective algebras

It is often convenient to look at algebras that are both finitely generated projective as modules and separable as algebras over the underlying commutative ring. Definition 6.2.35. Let R be a commutative ring. An R-algebra S that is separable as an R-algebra and projective as an R-module is said to be separable projective over R.

This notion can be linked to the notions of Azumaya and finite-étale. Theorem 6.2.36. Let k be a commutative ring and S a k-algebra. Let R := Z(S). Then the following are equivalent:

(i) S is Azumaya over R and R is finite-étale over k. (ii) S is separable projective over k.

Proof. (i)⇒(ii) By Theorem 6.2.20, part (i), Definition 6.2.27 and Proposition 6.2.14, part (iii), we have that S is separable as a k-algebra. From Corollary 6.2.15 we know that S is projective as an R-module and so by transitivity of projectivity, S is projective as a k-module.

(ii)⇒(i) By Proposition 6.2.14, part (ii), we have that S is separable over R so it is Azumaya over R, and R is separable over k. All that remains to be established is that R is projective as a k-module.

From Theorem 6.2.20 we know that S is an R-progenerator, so

Since S is finitely generated and projective as an R-module, Hom R (S, R) is finitely generated as an R-module, so we can restrict the sum to a finite set of generators.

In particular, there exists a surjective R-homomorphism S n R for some n ∈ Z >0 . But R is R-projective, so this map splits, giving S n ∼ = R ⊕ Q for some R-module Q. Now S is k-projective by hypothesis, so S n is also k-projective and since R is a direct summand of S n , we have that R is also k-projective. Note 6.2.41. We will refer to the property induced by the "if" direction as "injectivity lift". Corollary 6.2.42. Let S be a finite ring that is separable projective over its prime subring. Then S is a quasi-Frobenius ring.

Proof. Since S is finite, its prime subring is isomorphic to R = Z/nZ, where n = char(S) ∈ Z >0 . Since R is quasi-Frobenius (see Example 1.7.3), an R-module is injective if and only if it is projective. Since S admits both projectivity and injectivity lift from R by Propositions 6.2.38 and 6.2.40, it follows that S itself is quasi-Frobenius.

We record some other properties of separable projective algebras. Proposition 6.2.43. Let A be a finite semisimple ring. Then A is separable projective over its prime subring.

Proof. Since A is semisimple, the characteristic of A is squarefree. By Proposition 6.2.16, part (ii), Proposition 1.6.9 and the fact that A is semisimple, we may assume that A has prime subring F p , for some prime p, and that A ∼ = M n (D), for some n ∈ Z >0 , where D is a finite field extension of F p . Now A is separable projective over D by Example 6.2.23 and D is separable projective over F p , since finite extensions of perfect fields are separable. Hence A is separable projective over F p . Theorem 6.2.44. Let A be a nonzero finite ring. Then A is semisimple if and only if A is separable projective over its prime subring and char(A) is squarefree.

Proof. Let n := char(A). The "if" direction follows from Proposition 6.2.43 and the fact that for any d ∈ Z >0 such that d 2 | n, we have 0 = n d A ⊆ J(A). The other direction follows from Theorem 6.2.18, part (iii) and Proposition 6.2.16, part (ii).

Moreover, separable projective algebras that are faithful as modules over the base ring, are symmetric (see Definition 1.8.1 and Theorem 1.8.2). Theorem 6.2.45 ([24], Theorem 4.2). Let k be a commutative ring and A a separable projective k-algebra that is faithful as a module over k. Then A is a symmetric kalgebra.

Separable rings

Let A be a ring. Then A is a Z-algebra, as well as an algebra over its prime subring. By Proposition 6.2.14, parts (i) and (ii), we have that A is separable over Z if and only if A is separable over its prime subring. Definition 6.2.46. We say a ring is separable if it is separable as a Z-algebra. Theorem 6.2.47. There exists a deterministic polynomial-time algorithm that, given a finite ring A, decides whether or not it is separable.

Proof. We begin by computing the prime subring of A using Theorem 3.

From the above construction, we have the following result. Proposition 6.2.58. Let p be a prime and e, d ∈ Z >0 . Then the ring W e (F p d ) is local, with maximal ideal p W e (F p d ), which has cardinality p d(e-1) . Moreover, the set of ideals of

Note 6.2.59. Another way of constructing Witt rings is via Galois theory for commutative rings. In the case of finite rings, the notion of a Witt ring is then replaced by that of a Galois ring. This is the more common terminology in literature on separability (see [START_REF] Bini | Finite Commutative Rings and Their Applications[END_REF]20]). Proposition 6.2.60. Let R be a finite commutative ring. Then R is local separable if and only if R ∼ = W e (F p d ), for some prime p and some e, d ∈ Z >0 .

Proof. For the "only if" direction, suppose that R is local separable. Then it has prime power characteristic, p e , for some prime p and some e ∈ Z >0 . By Theorem 6.2.18, part (iii), we have that R is separable over Z/p e Z if and only if R/pR is separable over F p . By Corollary 6.2.9, we have that R/pR is semisimple. Hence R/pR ∼ = F p d . We have the following commutative diagram:

By the proof of Theorem 6.2.54, we have that R ∼ = W e (F p d ).

The "if" direction follows by construction of truncated Witt rings.

We can now turn to the classification of finite separable rings. By Proposition 6.2.16, part (ii) it suffices to classify finite connected separable rings. Proposition 6.2.61. Let P be the set of primes. There is a bijection between the sets

if for m, the maximal ideal of A, we have

Definition 6.2.67. Let k be a ring and P a projective k-module. A collection {x i , f i } i as described in the previous lemma is called a dual basis of P . Lemma 6.2.68. Let k be a commutative ring, M a k-module and N a finitely generated projective k-module. Then

Proof. If N = k, then ψ is clearly an isomorphism. Then, by properties of tensor products and Hom's, for any n ∈ Z >0 , we have that N = k n also gives an isomorphism. But then ψ remains an isomorphism for N a finitely generated projective k-module, since then N is a direct summand of some multiple of k.

Note 6.2.69. Lemma 6.2.68 remains true if it is M that is finitely generated projective as a k-module (the proof of this follows the same lines). Now let P be a finitely generated projective k-module. Then the map ϕ as defined in (6.9) is an isomorphism. Further, if we consider the map

then we get an induced map tr P/k := ψϕ -1 : Proposition 6.2.71. Let k be a commutative ring and P a finitely generated kmodule. Then P is projective if and only if Hom k (P, k) ⊗ k P is a ring with multiplication given by , as defined in (6.10).

Proof. If P is finitely generated projective, then Hom k (P, k) ⊗ k P ∼ = End k (P ), so it is a ring and the map is simply composition of maps by diagram (6.11).

For the other direction, note that Hom k (P, k) ⊗ k P being a ring implies the existence of an element α = n i=1 f i ⊗ x i ∈ Hom k (P, k) ⊗ k P such that for all β ∈ Hom k (P, k) ⊗ k P , we have (α, β) = β. But then for any x ∈ P ,

Applying ψ (as defined in (6.12))to both sides, we get

i=1 is a dual basis of P and so P is finitely generated projective by Lemma 6.2.65.

The following result says that the trace map tr P/k behaves "as expected". Proposition 6.2.72 ([7], Section 1). Let k be a commutative ring and P a finitely generated projective k-module. Let us now consider the case when P is in fact a k-algebra. Definition 6.2.73. Let k be a commutative ring and let A be a k-algebra that is finitely generated and projective as a k-module. Then the map A → End k (A) given by a → (x → ax) induces a map Tr A/k : A → k in the following diagram:

We call Tr A/k the trace map of A over k. We give a second definition of the trace map, using a more element-oriented approach. Definition 6.2.75. Let k be a commutative ring and A a k-algebra that is finitely generated projective as a k-module. Let {x i , f i } be a dual basis of A over k. We define

and

Note 6.2.76. The above definition is independent of the choice of dual basis. One way to see this is the following proposition. Proposition 6.2.77. The two definitions of Tr A/k agree.

Proof. Let {a i , f i } n i=1 be a dual basis of A as a finitely generated projective module over k. Let Tr A/k be the trace map as in Definition 6.2. [START_REF] Papadimitriou | Computational Complexity. Theoretical computer science[END_REF]

and Tr

(2)

A/k , the trace map as in Definition 6.2.75. For any a ∈ A, consider the two trace maps:

A k :

Consider the element

A/k (a). Example 6.2.78. Let k be a commutative ring and let A be a k-algebra such that A ∼ = k n as k-modules, for some n ∈ Z >0 . Let B = {b i | 1 ≤ i ≤ n} be a basis of A over k. Then a dual basis of A over k is given by {b i , f i } n i=1 , where f j :

Example 6.2.79. Let k be a commutative ring and let A = M n (k). Then

Example 6.2.80. Let A be a finite-dimensional algebra over a field k. Then nilpotent elements of A have trace zero. This is because nilpotent matrices over a field have trace zero. Example 6.2.81. Let A be a finite-dimensional algebra over a field F p , where p is a prime and let S be a finite A-module. Since S is a vector space over F p , we have a ring homomorphism ρ : A → End Fp (S) given by sending an element a ∈ A to the endomorphism of S corresponding to the action of a on S. Define Tr (S) : A → F p to be the map tr S/Fp •ρ, where tr S/Fp is the trace of S over F p . Note that Tr (A) = Tr A/Fp is the usual trace map, as defined in 6.2.73. If 0 → S → T → U → 0 is an exact sequence of A-modules, then Tr (T ) = Tr (S) + Tr (U ) .

To see this, suppose C 1 , C 2 are bases for S and U respectively. Then the matrix of Tr (T ) can be represented as an upper triangular block matrix, where the two diagonal blocks are the matrices of Tr (S) and Tr (U ) with respect to C 1 and C 2 respectively. Moreover, if a basis of T contains a basis of S, then the rest is a basis of U . Definition 6.2.82. Let k be a commutative ring and A a k-algebra that is finitely generated projective as a k-module. The trace radical of A over k is the kernel of the right A-module homomorphism:

In other words, Lemma 6.2.84. Let A be a finite ring. Suppose A = l i=1 A i , for some l ∈ Z >0 and A i finite rings. Let n i := char(A i ) and suppose that for all i = j we have gcd(n i , n j ) = 1 and that each A i is free as a module over Z/n i Z. Then

Proof. Write k := Z/ char(A)Z. First note that char(A) = i n i and that A is indeed projective over k, so that I A/k is well-defined. The result now follows from Proposition 6.2.72, part (iv). Theorem 6.2.85. There exists a deterministic polynomial-time algorithm that, given a finite commutative ring k and a finite k-algebra A that is projective as a k-module, computes the trace radical I A/k . Proof. We begin by computing Hom k (A, k), using Proposition 2.4.1. Then I A/k is computed as the kernel of the map ψ from Definition 6.2.82.

Defining an approximation

Definition 6.3.1. Let A be a finite ring and j A ⊂ A an ideal. We say j A is an approximation of the Jacobson radical of A if (A1) j A is a two-sided nilpotent ideal of A. (A2) A/j A is finite separable. (A3) The prime subring and generalised prime subring of A/j A coincide. Note 6.3.2. Let A be a finite ring. Then by Theorem 1.4.9, Proposition 6.2.43 and Theorem 6.2.52, the Jacobson radical is an approximation of itself. Note 6.3.3. Approximations of Jacobson radicals are not unique. Let p be a prime and let A = Z/p 2 Z. Then A is finite separable with prime subring and generalised prime subring equal to Z/p 2 Z. Hence 0 and J(A) = pZ/p 2 Z are both approximations of the Jacobson radical of A. Theorem 6.3.4. Let A be a finite ring and j A a two-sided ideal of A such that j A is nilpotent and A/j A is separable projective over its prime subring. Suppose, moreover, that the characteristic of A is a power of some prime p. Then

and

(A/j A ) + ∼ = (Z/p e Z) r , where r = dim Fp (A/ J(A)) and e ∈ Z >0 is such that p e = char(A/j A ).

Proof. Let e ∈ Z >0 and p be a prime such that char(A/j A ) = p e . First note that, since A/j A is separable over Z/p e Z, we have that (A/pA)/((j A + pA)/pA) is semisimple by Corollary 6.2.10 and Theorem 6.2.18, part (iii). This implies that (j A + pA)/pA) ⊇ J(A/pA). Moreover, j A is nilpotent. We thus have that (j A + pA)/pA = J(A/pA). Hence (A/j A )/(p(A/j A )) = (A/pA)/((j A + pA)/pA)

By Nakayama's Lemma, the minimum number of generators of A/j A as a Z/p e Zmodule is equal to the dimension of A/ J(A) over F p . But A/j A is projective over Z/p e Z, so it is free of finite rank. Thus the rank of A/j A as a Z/p e Z-module is equal to dim Fp (A/ J(A)).

Example 6.3.5. Let p be a prime and M an F p -vector space of dimension 1. Let A = Z/p 2 Z ⊕ M be the ring with componentwise addition and multiplication given by (a, x) • (b, y) = (ab, ay + bx).

In particular, A is a commutative ring with M 2 = 0. Moreover, J(A) = pZ/p 2 Z ⊕ M .

For any approximation j of the Jacobson radical of A we must have A/j ∼ = Z/p 2 Z or A/j ∼ = F p . If A/j ∼ = F p , then it must be the case that j = J(A).

Let S be the set of all approximations of the Jacobson radical of A. We have bijections between the following sets

The latter set has p elements and each of these gives rise to an approximation of the Jacobson radical of A of the same size. Note 6.3.6. Example 6.3.5 shows that, even though the set of all approximations of the Jacobson radical of a finite ring always has a maximal element with respect to inclusion, given by the Jacobson radical, it does not necessarily have a minimal element.

The aim of this section is to describe deterministic polynomial-time algorithms that produce approximations of the Jacobson radical of a finite ring. We are interested in algorithms that have the additional property that, when run on two isomorphic rings, they output isomorphic approximations of their Jacobson radicals (induced by the same isomorphism), even when the ring isomorphism is unknown (cf. Section 3.5).

Algorithms for finite rings

We will treat rings in a differentiated manner, depending on the size of the primes dividing their characteristic. We define convenient notions of "small" and "large" primes that allow us to split the ring into two parts and deal with them separately. The case of small primes is easy to deal with, since we can actually compute the Jacobson radical and thus arrange for genuine semisimplicity. The case of large primes requires more work and what allows us to deal with them is Theorem 6.2.88, part (iii).

Trace radical vs. Jacobson radical

We start by proving a series of results about the trace ideal (see Definition 6.2.73) that we will make use of within our algorithms. Proposition 6.3.7. Let A be a finite-dimensional algebra over a field k. Then the trace ideal I A/k contains the Jacobson radical J(A).

Proof. Since A is left-artinian, its Jacobson radical is nilpotent and so by Example 6.2.80, all its elements lie in I A/k . Theorem 6.3.8. Let A be a finite-dimensional algebra over the finite field F p , where p is a prime and p > dim Fp (A). Then I A/Fp = J(A). where the sum is taken over isomorphism classes of simple A-modules and length S (A) is the number of times that S occurs in a composition series of A.

Proof. The inclusion J(A) ⊆ I

Recall from Note 1.4.6 that

as F p -algebras. Since I A/Fp is a two-sided ideal of A (by Note 6.2.83) and I A/Fp ⊇ J(A), we have that I A/Fp / J(A) is a two-sided ideal of A/ J(A), and so it is a subproduct of (6.16). Suppose I A/Fp = J(A). Then there is at least one simple S 0 occurring in this subproduct. Then I A/Fp contains all elements of A that act as 0 on all simple Amodules not isomorphic to S 0 . Consider such an element that acts as 1 on S 0 and as 0 on all other simples. Since it lies in the product of (6.16), it is represented by an element r ∈ A. Then by (6.15), the trace of r is length S0 (A) • dim Fp (S 0 ). This quantity is strictly positive and less than or equal to dim Fp (A), so, for p > dim Fp (A), it is nonzero in F p . Hence r / ∈ I A/Fp , giving a contradiction.

Corollary 6.3.9. There exists a deterministic polynomial-time algorithm that, given a finite algebra over a finite field F p , where p is a prime satisfying p > dim Fp (A), computes the Jacobson radical J(A).

Proof. From Theorem 6.3.8 we have I A/Fp = J(A), and the trace ideal can be computed deterministically in polynomial time by Theorem 6.2.85.

Note 6.3.10. We already knew this ( [START_REF] Cohen | Finding the radical of an algebra of linear transformations[END_REF][START_REF] Friedl | Polynomial time solutions of some problems of computational algebra[END_REF]).

p.

Then n A ⊆ J(A) and

where I A/(Z/mZ) is the trace radical of A over Z/mZ, as before, and

Proof. To simplify notation, we write I A := I A/(Z/mZ) and I A/n A := I (A/n A)/(Z/n Z) . We will use similar abbreviations for the trace maps. Note that A/n A is projective as a module over Z/n Z, so the trace map and the trace radical are well-defined.

It is easy to see that n A is nilpotent in A, since some power of n is divisible by m. The first equality of (6.17) follows since n A is nilpotent and the second equality follows by Proposition 1.4.11, Theorem 6.3.8 and Lemma 6.2.84. For the last part,

Separating small primes from large primes

To develop algorithms from the theory in the previous sections, we first need to address the problem of separating small primes from large primes. Proposition 6.3.18. There exists a deterministic polynomial-time algorithm that, given a finite ring A of characteristic n, outputs two positive integers n 1 and n 2 , such that:

(iii) all primes dividing n 1 are small and all primes dividing n 2 are large.

Moreover, the algorithm produces a prime factorisation of n 1 .

Proof. Suppose the finite abelian group A + is given to the algorithm as the direct sum of cyclic groups

So the set S will certainly contain all small primes. Now we decide which of the primes which occur in the factorisation of the d i are actually small, by checking the condition p ≤ dim Fp (A/pA). Finally, we gather all small primes, with their exponents, into n 1 .

To see that the algorithm is polynomial-time, note that t ≤ log 2 (|A|).

Note 6.3.19. In the process of running the algorithm of Proposition 6.3.18, we have obtained a complete factorisation of n 1 , i.e. we know what all the small primes dividing n are, and what their multiplicities are. Note that any two isomorphic rings have the same small primes, with the same multiplicities.

Lemma 6.3.20. There exists a deterministic polynomial-time algorithm that, given a finite ring A, computes a two-sided nilpotent ideal I of A and two positive integers n 1 and n 2 such that

) all primes dividing n 1 are small for A/I and all primes dividing n 2 are large for A/I, (iv) n 1 is squarefree.

Proof. We start by computing the characteristic of A using Theorem 3.3.1 and then apply Proposition 6.3.18 to compute n 1 and n 2 , i.e. to separate small primes for A from large primes for A. This also gives a complete factorisation of n 1 . Let m ∈ Z >1 be the largest integer such that m 2 | n 1 and write n = m • l. Then lA = 0, but (lA) 2 = 0, so we have found a nilpotent two-sided ideal, I = lA ⊂ A. Put n 1 = n 1 /m and n 2 = n 2 . Note also that the small (resp. large) primes for A are the same as the small (resp. large) primes for A/I. Theorem 6.3.21. There exists a deterministic polynomial-time algorithm that, given a finite ring A, computes a two-sided nilpotent ideal i such that

where A 1 is semisimple and all primes dividing n 2 are large for A/i. Proof. By Lemma 6.3.20, we may write

for some two-sided nilpotent ideal I ⊆ A, where n 2 is divisible only by large primes for A/I and n 1 is squarefree. For each prime p | n 1 , the ring A/pA is an algebra over F p , so by Theorem 3.4.1 we may compute its Jacobson radical and factor it out of A, making the first component genuinely semisimple.

Algorithms

Theorem 6.3.22. There exists a deterministic polynomial-time algorithm that, given a finite ring A, computes an approximation of the Jacobson radical of A.

Proof. By Theorem 6.3.21, we may assume that char(A) is only divisible by large primes, i.e. for all primes p | n, we have p > dim Fp (A/pA). We proceed by building a sequence of rings that will terminate with a strongly separable ring (see Theorem 6.2.88 and Definition 6.2.89). We start by putting

To continue, we would like to make use of the trace and the trace radical and for this, we must ensure that we are working with a projective module. We thus quotient out by a multiple of A 0 to get

where m | char(A) is such that mA 0 is a nilpotent two-sided ideal of A 0 , and A 1 is projective as a module over Z/mZ. The way to do this deterministically in polynomial time has been described in Proposition 2.8.1.

We proceed by computing the trace radical I := I A1/(Z/mZ) using Theorem 6.2.85. By Proposition 6.3.8, we have I ⊆ J(A 1 ). The next term in our sequence is

Examples

In this section we look at some specific instances of trace computation and running of the algorithms given as proofs of Theorem 6.3.22. We will only consider examples where the characteristic of the given ring is divisible exclusively by large primes. Note 6.3.27. If A is a finite ring of prime characteristic, then by Theorem 6.2.44, both our algorithms will output the Jacobson radical of A.

Note that rings that are finite products rings of the form Z/nZ, with n ∈ Z >0 and componentwise addition and multiplication, are separable over their prime subrings (see Proposition 6.2.16, part (iii)). Thus, if they are projective over their prime subring, they are strongly separable over their prime subring (see Proposition 6.2.86), so their trace ideal is trivial. Example 6.3.28 (Integers modulo n). Let A = (Z/5Z) 2 × (Z/3 2 Z). Note that 5 > 2 and 3 > 1, so the primes occurring are large. The prime subring of A is k = Z/45Z and A is projective as a k-module and hence A is strongly separable over k. Thus, if A is given to the algorithms proving Theorem 6.3.22, they will find that I A/(Z/45Z) = 0, and will therefore output j A = 0.

It is easy to check that a projective basis of A over k is given by {F i , x i } 3 i=1 , where Hence by Definition 6.2.75,

where p > 2 is a prime, M is a 1-dimensional F p -vector space, addition is componentwise and multiplication is given by (a, x) • (b, y) = (ab, ay + bx).

Then A is a commutative local ring with maximal ideal pZ/p Example 6.3.31 (Matrix rings). The smallest example of a matrix ring over a commutative ring whose characteristic is divisible only by large primes is A = M 2 (F 5 ). In this case, A is simple, but since the primes occurring are large, the algorithms will not be able to detect this. Since 2 is a unit in F 5 , the ring A is strongly separable, so the algorithms will output j A = 0.

Remarks

Functoriality Proposition 6.3.32. Let F be the class of finite rings. The two families of ideals (j A ) A∈F and (j A ) A∈F , produced by the two algorithms described in the two proofs of Theorem 6.1.2 are functorial under isomorphisms, i.e. if φ : A → B is an isomorphism of finite rings, then φ(j A ) = j B and φ(j A ) = j B .

Proof. It is clear by construction (Propositions 2.8.1 and 2.8.2) that two isomorphic rings will yield the same m and m . Trace ideals are compatible with ring isomorphisms by Proposition 6.2. 72, part (iv).

Comparison between proofs of Theorem 6.3.22

We have already noted that the algorithm given in the second proof of Theorem 6.3.22 performs only 3 steps. But what can we say about the number of iterations (trace radical computations) needed in the first algorithm?

If A is a finite ring, let us write j A 1 for the approximation of the Jacobson radical of A produced by the first proof of Theorem 6.3.22, and j A 2 for the approximation of the Jacobson radical of A produced by the second proof. So far we have only seen examples where j A 1 = j A 2 . A natural question to ask is how j 1 and j 2 compare (with respect to inclusion), or indeed whether they are comparable at all.

We give partial answers to these questions in this section.

Let e ∈ Z >0 and let p > 2 be a prime. Let e ∈ Z >0 be such that 2e < e. Set A = (Z/p e Z) [X]/(X 2 -p e X).

Remark II. The cardinality of A/j A 2 may be larger than the cardinality of A/j A 1 . Compare (6.22) with (6.23). Remark III. It is possible that j A 2 ⊆ j A 1 . Compare (6.22) with (6.23).

Good properties

We summarize the good properties of the ring A/j A , where j A is an approximation of the Jacobson radical of A. Theorem 6.3.33. Let A be a finite ring and j A an approximation of the Jacobson radical of A. Then (i) A/j A is separable, (ii) the prime subring and the generalised prime subring of A/j A coincide, (iii) A/j A admits projectivity and injectivity lift from its prime subring, (iv) A/j A is a quasi-Frobenius ring, (v) A/j A is a symmetric algebra over its prime subring.

Applications and further questions

The exploration of possible applications of the computation of an approximation of the Jacobson radical of a finite ring is a problem for future research. We record here an application to testing simplicity of a finite module M over a finite ring R. More basic algorithms for this were given in Chapter 5, Section 5.3.

Third proof of Theorem 5.3.1. We begin by computing an approximation j R of the Jacobson radical of R using either of the proofs of Theorem 6.3.22. By Proposition 1.3.14, it is enough to test whether M is simple as an R/j R -module, which by Theorem 1.6.4 reduces to testing whether End R/j R (M ) is a field. This can be done by Theorem 5.1.2.

It is also an interesting question to decide if for a finite ring A, we have j A 2 ⊆ j A 1 in general. This has not been contradicted by the examples we have considered.

Computing the generalised prime subring

Let A be a finite ring and denote its generalised prime subring by P A (see Definition 6.2.48). The two algorithms proving Theorem 6.3.22 each produce approximations j A of the Jacobson radical of A. In particular, the prime subring of the ring A/j A is equal to its generalised prime subring (see Definition 6.3.1). In what follows, we give a deterministic polynomial-time algorithm that, given a finite ring A, computes P A .

By Lemma 6.2.50, the generalised prime subring of a finite ring is equal to the generalised prime subring of its centre. Hence we may restrict to the case that A is a Algorithms for finite rings Theorem 6.4.3. There exists a deterministic polynomial-time algorithm that, given a finite ring A, computes the generalised prime subring P A .

Proof. Since P Z(A) = P A , we may assume A = Z(A). Suppose A + is given to the algorithm as The computation of the generalised prime subring gives another way of testing whether a finite ring is separable.

Second proof of Theorem 6.2.19. By Theorem 6.2.52, a finite ring is separable if and only if it is separable projective over its generalised prime subring. So compute P A using Theorem 6.4.3 and then test projectivity of A over P A using Theorem 5.4.1.

Algorithms for finite rings -Abstract

In this thesis we are interested in describing algorithms that answer questions arising in ring and module theory. Our focus is on deterministic polynomial-time algorithms and rings and modules that are finite.

The first three chapters prepare the ground for the rest of the text by introducing the underlying ring and module theory, and providing a compendium of algorithms that allow us to perform basic computations with finite abelian groups and finite rings.

The first main result of this thesis concerns the module isomorphism problem: we describe two distinct algorithms that, given a finite ring R and two finite R-modules M and N , determine whether M and N are isomorphic. If they are, the algorithms exhibit such an isomorphism.

In addition, we show how to compute a set of generators of minimal cardinality for a given module, and how to construct projective covers and injective hulls. We also describe tests for module simplicity, projectivity, and injectivity, and constructive tests for existence of surjective module homomorphisms between two finite modules, one of which is projective. As a negative result, we show that the problem of testing for existence of injective module homomorphisms between two finite modules, one of which is projective, is NP-complete.

The last part of the thesis is concerned with finding a good working approximation of the Jacobson radical of a finite ring, that is, a two-sided nilpotent ideal such that the corresponding quotient ring is "almost" semisimple. The notion we use to approximate semisimplicity is that of separability.

CV

Iuliana Ciocȃnea-Teodorescu was born June 2 nd 1990 in Bucharest, Romania. From 1997 to 2004 she was simultaneously a student of the Goethe German College and the George Enescu Music High School (piano studies), in Bucharest (Romania). In 2009 she graduated from the Mihai Viteazul National College in Bucharest.

Between 2009 and 2013 she was a student of the University of Oxford (UK), where she completed her bachelor's and master's studies in mathematics. Her master's thesis, entitled "Of Galois groups in polynomial time" was supervised by Professor Jonathan Pila.

In 2012 she obtained a DAAD RISE scholarship to undertake a research internship of three months within the Section of Systems Neuroscience, Faculty of Medicine, Dresden University of Technology, Germany.

In 2013 she was awarded an ALGANT-DOC scholarship and started her PhD under the joint supervision of Hendrik W. Lenstra (Leiden University, Netherlands) and Karim Belabas (University of Bordeaux, France).