Kandidátusi Értekezés

(Ph. D. Thesis submitted to the Hungarian Academy of Sciences)

Algorithms for algebras over global fields

Ivanyos Gábor

Abstract

The main results in this dissertation concern the computational complexity of structural decomposition problems in finite dimensional associative algebras over global fields (algebraic number fields and global function fields, i.e., function fields of plane algebraic curves over finite fields).

Polynomial time algorithms for isolating the radical and finding the simple components of the semisimple part of an algebra over a global function field are presented.

We propose a method for computing the dimension of minimal one-sided ideals of a simple algebra over a global field. The method is based on computing a maximal order in the algebra, a non-commutative analogue of the ring of algebraic integers in a number field. The algorithm makes oracle calls to factor integers in the number fields case.

A generalization of the LLL basis reduction algorithm is used to demonstrate that computing a maximal order in an algebra isomorphic to M_{2}(ℚ) is equivalent to finding an explicit isomorphism with M_{2}(ℚ).

We also present some applications, such as an efficient membership test in commutative matrix groups as well as a polynomial time method for computing dimensions of irreducible representations of finite groups over number fields.

Some results are also valid in more general contexts. For example, a deterministic polynomial time method for finding a maximal toral subalgebra in a semisimple algebra is presented as an application of a method for computing a Cartan subalgebra in a Lie algebra.

Acknowledgements

I am grateful to my scientific collaborators, in particular to László Babai, Robert Beals, Jin-yi Cai, Arjeh M. Cohen, Willem A. de Graaf, Eugene M. Luks, Lajos Rónyai, Ágnes Szántó, and David B. Wales, who were coauthors of the papers this dissertation is based on. I am especially indebted to my supervisor Lajos Rónyai for his invaluable advice.

My thanks also go to my colleagues at the Computer and Automation Institute of the Hungarian Academy of Sciences, in particular to the collective led by János Demetrovics for ensuring support and the excellent working atmosphere making my research possible. I am grateful as well to the collective around András Recski, (the Department of Mathematics and Computer Science of the Faculty of Electrical Engineering and Informatics at the Technical University of Budapest) for hosting me as a corresponding research student.

Finally, but not least I would like to thank my family: my wife, my children and my parents for their sacrifice and the warm, loving atmosphere they provided.

Contents

1 Introduction 1 1.1 Basic facts and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 The computational model . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Previous results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2 Testing membership in abelian matrix groups 18 2.1 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Computing the radical 22 3.1 Trace functions and the radical . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Computing trace functions via lifting . . . . . . . . . . . . . . . . . . . . . 27 3.3 Trace functions and composition factors . . . . . . . . . . . . . . . . . . . 30 3.4 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4 Wedderburn decomposition over 𝔽_{q}(X_{1}, …, X_{m}) 39 4.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Cartan subalgebras 49 5.1 The Sparse Zeros Lemma and a reduction procedure . . . . . . . . . . . . . 50 5.2 Non-nilpotent elements in Lie algebras . . . . . . . . . . . . . . . . . . . . 52 5.3 Locally regular endomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 55 5.4 Cartan subalgebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.5 Tori in associative algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6 Maximal orders 61 6.1 Basic facts about orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 6.2 Radicals of orders over local rings . . . . . . . . . . . . . . . . . . . . . . . 69 6.3 Extremal orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.4 Computing maximal orders . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.5 Computing indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7 Isomorphism with M_{2}(ℤ) 81

7.1 Basis reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 7.2 Finding zero divisors in M_{2}(ℤ) . . . . . . . . . . . . . . . . . . . . . . . . . 87

8 Problems for further research 89 8.1 Faster radical algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 8.2 Decomposition of simple algebras . . . . . . . . . . . . . . . . . . . . . . . 89

Bibliography 92 Appendix 97

Chapter 1

Introduction

There is a considerable interest in computations with finite dimensional algebras as they emerge naturally in several fields of mathematics and its applications. For example, understanding the structure of associative algebras is an important tool in the theory of matrix groups. Since decomposition of problems into smaller ones plays an important role in designing efficient algorithms, structural decomposition of algebras serve as a general tool in solving computational problems related to matrices. In this thesis we present some recent developments in the area of symbolic computations related to the structure of finite dimensional algebras.

The organization of the dissertation is as follows. In this introductory chapter we give a short summary of the mathematical background of problems addressed (Section 1.1) as well as a description of the computational model and the basic algorithmic ingredients of the methods presented later (Section 1.2). A short survey of the most important results obtained by other authors is given in Section 1.3. Throughout, the term algebra is reserved for a finite dimensional associative algebra over a field.

In Chapter 2, based on part of the paper [BBCIL], joint work with László Babai, Robert Beals, Jin-yi Cai, and Eugene M. Luks, we present an application (Theorem 2.1.1) of algebra decompositions over number fields to a strong membership test for commutative matrix groups.

Efficient algorithms are known over finite fields and algebraic number fields for computing the radical and for finding the simple components of the radical-free part of algebras. Here, in Chapters 3 and 4, we extend these results to algebras over global function fields, i.e., finite algebraic extensions of the field 𝔽_{q}(X) of rational functions over the field 𝔽_{q} consisting of q elements. It turns out, however, that the methods admit natural extensions to algebras over algebraic function fields over 𝔽_{q} (finite extensions of 𝔽_{q}(X_{1}, …, X_{m})), therefore the results are presented in this more general setting.

In Chapter 3, based on parts of the papers [IRSz] (joint work with Lajos Rónyai and Ágnes Szántó) and [CIW] (joint work with Arjeh M. Cohen and David B. Wales), a polynomial time algorithm for computing the radical of algebras over global function fields is presented (Corollary 3.4.6 to Theorem 3.4.5). The method is based on Theorem 3.1.4, a characterization of the radical of algebras over arbitrary fields of positive characteristic. This extends a result of Rónyai [Ró2], who gave a characterization for finite ground fields. In contrast to the method in [Ró2], which was based on certain functions obtained from lifting matrices over the finite prime field 𝔽_{p} to matrices over ℤ, we use certain coefficients of the characteristic polynomial. However, in the finite case, the functions in both methods turn out to be essentially the the same (Proposition 3.2.3), whence the methods presented here give alternatives to some details of Rónyai’s original method. As demonstrated in Theorem 3.3.2, the collection of these coefficients generalize the role of the trace in representation theory of semisimple algebras over fields of characteristic zero.

In Chapter 4, based on part of the paper [IRSz], a deterministic polynomial time method which is allowed to make oracle calls to factor polynomials over the prime field (an f-algorithm) for computing the Wedderburn decomposition of semisimple algebras over global function fields is presented (Corollary 4.1.5 to Theorem 4.1.3). The method is an improved analogue of the algorithm of Gianni, Miller and Trager [GMT], which was designed for decomposition of algebras over number fields.

Chapter 5 is mostly about Lie algebras. Cartan subalgebras are extremely important in the classification of (simple) Lie algebras. Here, based on the paper [GIR], joint work with Willem A. de Graaf and Lajos Rónyai, we present deterministic polynomial time algorithms for finding Cartan subalgebras in Lie algebras over sufficiently large fields (Theorem 5.4.1) as well as in Lie algebras over finite fields belonging to an important subclass (Theorem 5.4.2). How this result can be applied to derandomize several randomized methods for associative algebras is shown in Section 5.5.

Chapter 6, based on the paper [IR], joint work with Lajos Rónyai, is devoted to results related to the structure of simple algebras over global fields. The methods are based on certain noncommutative generalizations of ideas from algebraic number theory. The central result, stated in Theorem 6.4.2, is a deterministic polynomial time method allowed to make oracle calls to find prime factors of integers and to factor polynomials over finite fields (an ff-algorithm), that finds a maximal order (a noncommutative analogue of the ring of algebraic integers in number fields) in a semisimple algebra over a number field. An interesting application (Theorem 6.5.5) is a polynomial time algorithm for computing the dimensions of the irreducible constituents of a representation of a finite group over a number field. Analogous f-algorithms for computing maximal orders and indices in algebras over global function fields are also discussed.

In Chapter 7, based on the paper [ISz], joint work with Ágnes Szántó, we address the problem of complexity of finding zero divisors in maximal orders in simple algebras. We present a polynomial time method for central simple algebras of dimension four over the field of rationals (Theorem 7.2.1). The method is based on a generalization of the celebrated basis reduction procedure by A. K. Lenstra, H. W. Lenstra and L. Lovász [LLL] to the case of indefinite quadratic forms, discussed in Section 7.1.

We conlude with some open problems in Chapter 8.

1.1 Basic facts and definitions

(Nonassociative) algebras

A linear space A over the field K is an algebra over K if it is equipped with a binary, K-bilinear operation (x, y) ↦ xy (called multiplication). A is associative if

x(yz) = (xy)z holds for every x, y, z ∈ A.

Throughout this thesis we reserve the term algebra for associative algebras. In order to distinguish from the general case, for not necessarily associative algebras we use the term nonassociative algebra. We restrict ourselves to finite dimensional K-algebras. Besides associative algebras, important examples are Lie algebras. In the Lie case, we use the traditional bracket notation for multiplication. A nonassociative K-algebra L with multiplication (x, y) ↦ [x, y] is a Lie algebra over K if

[x, y] = −[y, x] (anticommutativity)

and

[[x, y], z] + [[y, z], x] + [[z, x], y] = 0 (the Jacobi identity)

hold for every x, y, z ∈ L.

We say that two elements x, y ∈ A commute if xy = yx. A nonassociative algebra A is called commutative (or abelian), if every pair of its elements commute. A K-subspace B of A is a subalgebra of A (B ≤ A in notation) if it is closed under multiplication. A K-subspace L of A is a left ideal of A if yx ∈ L holds whenever x ∈ L and y ∈ A. A right ideal is defined in an analogous fashion. A K-subspace I of A is an ideal (two-sided ideal) of A if I is both left and right ideal of A. We use the standard notation I ⊲ A. Note that in commutative algebras as well as in Lie algebras the notions of left ideal, right ideal and ideal coincide.

For nonassociative K-algebras A and B a K-linear map ϕ : A → B is a homomorphism if it preserves multiplication. The kernel ker ϕ is an ideal in A, while the image im ϕ is a subalgebra of B. An isomorphism is a bijective homomorphism. If I ⊲ A is an ideal, then the factor space Ā = A/I inherits the multiplication of A in the natural way: (x + I)(y + I) ⊆ xy + I holds for every x, y ∈ A. Here we used the standard notation for extending operations to complexes (subsets): if X, Y ⊆ A then X ∗Y stands for the subset {x ∗ y|x ∈ X, y ∈ Y }, where ∗ is one of the operations on A. The map ϕ : x ↦ x + I is a homomorphism A → Ā, called the natural map. We have ker ϕ = I and im ϕ = Ā.

A nonassociative algebra A is simple if it has only trivial ideals (i.e., (0) and A) and A ≠ (0). We say that A is the direct sum of its (left) ideals A_{1}, …, A_{r} (written as A_{1} ⊕ ⋯ ⊕ A_{r}) if A is the direct sum of these linear subspaces.

Associative algebras

Throughout this subsection A is a finite dimensional associative algebra over the field K. Because of associativity, the product x_{1}x_{2} ⋯ x_{r} of r elements x_{1}, x_{2} …, x_{r} ∈ A can be defined in a straightforward way.

The centralizer C_{A}(X) of a subset X of A is the set consisting of elements of A commuting with every element of the subset X. Obviously, C_{A}(X) ≤ A. The center C(A) of A is the subalgebra C_{A}(A).

An element e ∈ A is called an identity element if

ex = xe = x holds for every x ∈ A.

If A admits an identity element then the identity element is known to be unique and denoted by 1_{A} or simply by 1. Note that if A has no identity element then we can adjoin one using the Dorroh extension: Let A′ = Ke ⊕ A as vector spaces with multiplication defined by

(αe + x)(βe + y) = αβe + βx + αy + xy.

It is easy to see that A′ is an associative K-algebra with identity element e such that A is an ideal in A′. The left, right, or two-sided ideals of A′ are A′ and those of A.

A pair of nonzero elements x, y ∈ A is a pair of zero divisors in A if xy = 0. From the assumption that A is finite dimensional it follows that x ∈ A is the left member of a pair of zero divisors if and only if x is the right member of a pair of zero divisors. We call such an x a zero divisor. It turns out, that x is a zero divisor iff for the left ideal Ax we have A > Ax and iff for the right ideal xA we have A > xA. Algebras without zero divisors (called division algebras over K or skewfield extensions of K) are obviously simple and a commutative algebra A is simple if and only if A admits no zero divisors. Therefore every finite dimensional commutative simple algebra over K is isomorphic to a finite extension field of K.

If V is an n-dimensional vector space over K then End_{K}(V), the algebra of K-linear transformations of V with the usual operations, is a simple K-algebra of dimension n^{2}. By choosing a basis, we can identify V with the space K^{n} of column vectors of length n and End_{K}(V) with M_{n}(K), the algebra of n by n matrices over K with the usual matrix operations.

Subalgebras of End_{K}(V) or, equivalently, those of M_{n}(K), called matrix algebras, appear to be typical examples of associative algebras. If A has an identity element then A can be efficiently embedded as a subalgebra of M_{n}(K), where n = dim_{K}A. This is easily seen using the (left) regular representation. For x ∈ A we define the linear map L_{x} : A → A, called the left action of x on A as L_{x}(y) = xy for every y ∈ A. It is straightforward that x ↦ L_{x} is an algebra homomorphism of A to the algebra of linear transformations of the linear space A. Moreover, if A has an identity element then x ↦ L_{x} is an injective map. If A has no identity element then the regular representation of the Dorroh extension induces an embedding A → M_{n+1}(K).

Matrix algebras arise naturally in problems related to common invariant subspaces of matrices. Let X ⊆ End_{K}(V) be a set (e.g., a group) of linear transformations of the finite dimensional linear space V. Obviously, if W is an X-invariant subspace (i.e., xW ⊆ W for every x ∈ X) then W is also A-invariant where A is the subalgebra of End_{K}(V) generated by X and the identity (the smallest subalgebra containing X ∪{Id_{V} }). The centralizer algebra C_{End_{K}(V)}(X) plays an important role in problems related to direct decompositions. To be more specific, decompositions of C_{End_{K}(V)}(X) into direct sums of left ideals correspond to decompositions of V into direct sums of X-invariant subspaces. Other important examples of finite dimensional algebras are group algebras of finite groups.

An element x ∈ A is nilpotent if x^{N} = 0 for some positive integer exponent N. For a positive integer j and a subset X ⊆ A we denote the set {x_{1} ⋯ x_{j}|x_{1}, …, x_{j} ∈ X} by X^{j}. It is straightforward to see that if X is a K-subspace (subalgebra, left ideal, right ideal, ideal) of A then X^{j} is a K-subspace (subalgebra, left ideal, right ideal, ideal, resp.) as well. A subalgebra B is called nilpotent if B^{N} = 0 for some integer N > 0. This in turn is equivalent to that B^{N} = 0 for some integer 0 < N ≤ dim_{K}B + 1. It is known that a subalgebra B is nilpotent if and only it consists of nilpotent elements. There exists a largest nilpotent ideal of A, called the radical of A and denoted by Rad(A). There are several characterizations of the radical, such as the intersection of the maximal ideals, or the set of strongly nilpotent elements (where x is said to be strongly nilpotent if x, xy, yx are nilpotent for every y ∈ A), etc. Note that the two-sided characterizations above could be replaced by analogous left-sided or right-sided ones.

A is called semisimple if Rad(A) = {0}. It turns out that the factoralgebra A/Rad(A) is semisimple. We call A/Rad(A) the semisimple part (or radical-free part) of A. There is a very strong and useful characterization of semisimple algebras, due to Wedderburn.

Wedderburn’s Theorem. Let A be a finite dimensional algebra over the field K.

(i) A is semisimple if and only if A is a direct sum of simple algebras

A = A_{1} ⊕ ⋯ ⊕ A_{r},

where the A_{i} are the only minimal nontrivial ideals of A. (ii) A is simple if and only if

A ≅ M_{t}(D),

where D is a division algebra over K and t is a positive integer.

Let A be semisimple. We keep ourselves to the notation of the theorem. The minimal ideals A_{1}, …, A_{r} are also called the simple components of A, and the decomposition (i) in the theorem is the Wedderburn decomposition of A. We remark that the Wedderburn decomposition of the center corresponds to the decomposition of A: the minimal ideals of C(A) are C(A_{1}), …, C(A_{r}).

A semisimple algebra A necessarily admits an identity element. In that case we identify K with the subalgebra K1_{A} ≤ C(A). An algebra A is central over K if C(A) = K. Every simple algebra is central over its center, which is a finite extension field of K. Assume that A is central simple over K. We know that dim_{K}A is a square, say n^{2}, the number t in Wedderburn’s theorem (ii) is a divisor of n, while D is a central division algebra over K of dimension (\frac{n}{t})^{2}. The number \frac{n}{t} is called the index of A. The minimal left ideals of A have dimension \frac{n^{2}}{t} over K.

The minimal polynomial of an element a of a K-algebra A with identity is the monic polynomial f ∈ K[X] such that f(a) = 0 and f is of minimum degree among the polynomials satisfying this property. (For a polynomial g(X) = ∑_{i=0}^{d} α_{i}X^{i}, g(a) is defined as g(a) = ∑_{i=0}^{d} α_{i}a^{i} ∈ A, using the convention a^{0} = 1_{A}.) It is known if f is the minimal polynomial of a then the set {g ∈ K[X]|g(a) = 0} is the principal ideal (f) of K[X] generated by f.

If L is an arbitrary extension field of K then the L-space A_{L} = L⊗_{K}A can be considered as an L-algebra in a natural way. Multiplication is the K-bilinear extension of

α ⊗ x · β ⊗ y = αβ ⊗ xy.

A can be identified with the K-subalgebra 1⊗A of A_{L}. Note that if a_{1}, …, a_{n} is a K-basis of A then a_{1}, …, a_{n} is an L-basis of A_{L}.

A is called separable over K if A_{L} is semisimple over any field extension L of K. It turns out that a finite dimensional K-algebra is separable over K if and only if A is semisimple and the simple components of C(A) are separable extension fields of K. In particular, every central simple algebra is separable as well as every semisimple algebra over a perfect field.

Ground fields

We are primarily interested in symbolic computations over global fields. Global fields are algebraic number fields (finite extensions of the field ℚ of the rational numbers) and global function fields, that are finitely generated extensions of transcendence degree one over finite fields. Some of our methods have natural extensions to transcendence degree more than one as well. Therefore sometimes we work in the more general setting of algebraic function fields over finite fields, i.e., finite extensions of the field 𝔽_{q}(X_{1}, …, X_{m}) of rational functions in m variables over the finite field 𝔽_{q} consisting of q elements. However, the methods of Chapter 6 rely on arithmetic properties specific to global fields. Global function fields are subject of a beautiful branch of algebraic number theory, called global class field theory.

Orders

Let R be a Noetherian integrally closed domain, K be the field of quotients of R and let A be a finite dimensional algebra over K. An R-order in A is a subring Λ of A satisfying the following properties:

– Λ is a finitely generated module over R, i.e., there exists a finite set {a_{1}, …, a_{N}} ⊆ A such that every element of Λ can be written as a sum ∑_{i=1}^{N} α_{i}a_{i} with coefficients α_{i} ∈ R;

– Λ contains the identity element 1_{A} of A;

– Λ generates A as a linear space over K.

An important special example of an R-order is the case of integral structure constants. Assume that a_{1}, …, a_{n} is a basis of A such that every product a_{i}a_{j} written as a linear combination ∑_{l=1}^{n} γ_{ij}^{l}a_{l} of the basis elements has coefficients γ_{ij}^{l} ∈ R. Then the free Rsubmodule Λ generated by the basis a_{1}, …, a_{n} is a subring of A and if we in addition assume that 1_{A} has integral coefficients as well (e.g., 1_{A} = a_{1}), then Λ is an R-order. In fact, if R is a principal ideal domain then every R-order is of this form.

An R-order Λ in A is a maximal R-order if it is not a proper subring of any other R-order of A. It is known that in separable K-algebras there exists a maximal order, however, in general it is not unique. For example, for every matrix a ∈ GL_{n}(ℚ), the ring a^{−1}M_{n}(ℤ)a is a maximal ℤ-order in the central simple ℚ-algebra M_{n}(ℚ). (Actually, every maximal ℤ-order in M_{n}(ℚ) is of this form, however, this fact does not generalize to the case where the ground ring R is not a principal ideal domain). On the other hand, if R is a Dedekind domain, i.e. Noetherian integrally closed domain such that every prime ideal of R is maximal and A is a finite separable extension field of K, then the integral closure Λ of R in A defined by

Λ = {x ∈ A|there exists a monic polynomial f(X) ∈ R[X] s. t. f(x) = 0}

is the a unique maximal R-order in A.

Orders are often used for reducing computation in A “modulo” certain ideals I of R (computing in the ring Λ/IΛ). In particular, if P is a maximal ideal in the Dedekind domain R and Λ is a maximal R-order in the central simple algebra A, then, the structural invariants of the R/P -algebra Λ/P Λ do not depend on the choice of Λ. These invariants are called local invariants of A at P. If K is a number field and R is the ring of algebraic integers in K, then the local invariants at the prime ideals of R, together with other invariants corresponding to embeddings of K into ℂ, determine the structure of A up to isomorphism. Analogous statement holds for the case of global function fields. This fairly nontrivial fact has a beautiful unified formulation in terms valuations and completions. Phenomena of this flavour, i.e., the possibility to ascertain a “global” property from “local” ones are often referred as Hasse’s principle for the particular property.

Lie algebras and Cartan subalgebras

We restrict ourselves to finite dimensional Lie algebras. Through the theory of Lie groups, Lie algebras play an important role in the study of certain matrix groups.

A Lie algebra L over the field K is nilpotent if there exists an integer N > 1 such that [… [[x_{1}, x_{2}], x_{3}], …, x_{N}] = 0 for arbitrary elements x_{1}, …, x_{N} ∈ L. In every Lie algebra L there exists a largest nilpotent ideal, called the nilradical of L. A Lie algebra L is semisimple if it admits no nontrivial nilpotent ideal. Unlike associative algebras, it is possible that the factoralgebra by the nilradical is not semisimple. However, there exists a smallest ideal, called the radical of L, such that the factoralgebra is semisimple. The radical is in fact the largest solvable ideal, where solvability is a similar, but weaker property than nilpotence. Like the associative analogue, semisimple Lie algebras are characterized as direct sums of simple Lie algebras. There is a characterization of simple Lie algebras over algebraically closed fields of characteristic zero. The classification of simple Lie algebras over fields of positive characteristic is still a living area of research.

The normalizer N_{L}(H) of a subalgebra H of L is defined as

N_{L}(H) = {x ∈ L|[x, y] ∈ H for every y ∈ H}.

N_{L}(H) is the largest subalgebra of L containing H as an ideal. A subalgebra H of L is a Cartan subalgebra of L if H is nilpotent and N_{L}(H) = H. It is known that if K contains sufficiently many elements (compared to the dimension of L) then L contains a Cartan subalgebra.

Cartan subalgebras play extremely important role in the theory of Lie algebras, in particular, in classification of simple Lie algebras over fields of characteristic zero.

An interesting example of Lie algebras is A_{Lie}, the Lie algebra of an associative algebra A. This is the same vector space as A and Lie multiplication is defined by [x, y] = xy −yx. The Lie algebras M_{n}(K)_{Lie}, denoted by gl_{n}(K) deserve special interest. Subalgebras of gl_{n}(K) are called matrix Lie algebras. A matrix representation of a Lie algebra L is a (Lie algebra)-homomorphism L → gl_{n}(K). The analogue of the regular representation of associative algebras is the adjoint representation ad_{L} defined as follows. For every x ∈ L, ad_{L}(x) is the K-linear transformation on the vector space L defined by ad_{L}(x)y = [x, y]. The kernel of the adjoint representation is the center of L, consisting of the elements x ∈ L such that [x, y] = 0 for every y ∈ L. Obviously, the center is a nilpotent ideal, therefore the adjoint representation of a semisimple Lie algebra is in fact an embbeding of L into gl_{n}(K). The (associative) subalgebra of End_{K}(L) generated by the transformations ad_{L}(x) (x ∈ L) is called the enveloping algebra of L. The simple components of the enveloping algebra of a semisimple Lie algebra L correspond to the simple components of L, whence the Wedderburn decomposition is a relevant tool to decompose semisimple Lie algebras as well.

1.2 The computational model

Representation of data

We are interested in exact (symbolic) computations over finite fields, algebraic number fields and algebraic function fields (finitely generated transcendental extensions) over finite fields.

To obtain sufficiently general results, we consider nonassociative algebras to be given by a collection of structure constants. If A is a nonassociative algebra over the field K and a_{1}, a_{2}, …, a_{n} is a linear basis of A over K then multiplication can be described by representing the products a_{i}a_{j} as linear combinations of the basis elements a_{i}

a_{i}a_{j} = c_{ij1}a_{1} + ⋯ + c_{ijn}a_{n}.

The coefficients c_{ijk} ∈ K are called structure constants. We consider algebras to be given as an array of structure constants. Since identities like associativity, (anti-)commutativity, and the Jacobi identity are homogeneous and multilinear, it is sufficient to test the corresponding identities on the basis elements to decide whether A is an associative, a commutative, or a Lie algebra. An element of A is represented as the array of its coordinates w.r.t. the basis a_{1}, …, a_{n}. Substructures (such as subalgebras, ideals, subrings, subspaces) are represented by bases whose elements are given as linear combinations of basis elements of a larger structure.

We use the dense representation for elements of K, i.e, every element of K is represented (and inputted) as the array of its coordinates with respect to a basis of K over an appropriate subfield K_{0}. Note that this is the same as considering K as an algebra over K_{0}. If K is a finite field 𝔽_{q} consisting of q elements, then we take K_{0} = 𝔽_{p}, the prime field of 𝔽_{q}. If K is an algebraic number field, K_{0} = ℚ (again the prime field). Algebraic function fields of transcendence degree m over the finite field 𝔽_{q} are assumed to be given as algebras over 𝔽_{q}(X_{1}, …, X_{m}). Let d = [K : K_{0}]. K can be inputted with structure constants from K_{0}. Note however that in many cases K is a simple extension of K_{0} specified by giving the (monic) minimal polynomial f of a single generating element (primitive element) α over the prime field K_{0}. This representation can be considered as a special case of the representation with structure constants. The structure constants with respect to the basis 1, α, α^{2}, …, α^{d−1} of K are either zeros and ones, or certain coefficients of f. Even if K is given in this way, we consider f to be given in the dense representation, i.e., an array of d elements from K_{0}. We can, and often shall, consider n-dimensional K-algebras as algebras of dimension n × d over K_{0}. Since the structure constants are assumed to be inputted as arrays of d elements from K_{0}, polynomial time algorithms for K_{0}-algebras result in polynomial time algorithms for K-algebras.

A rational number is represented by a not necessarily reduced fraction of two integers. The size of an integer is the number of its binary digits. The size of a rational number r is, however, size(p) + size(q), where p/q is the reduced form of r. Modulo p residue classes have size ⌈log_{2}(p + 1)⌉.

The height of a polynomial 0 ≠ f ∈ 𝔽_{q}[X_{1}, …, X_{m}] is the maximum of the degrees of f in the variables X_{1}, …, X_{m}. We use the height as a tool to measure size of objects over the ring 𝔽_{q}[X_{1}, …, X_{m}]. Polynomials are considered in the dense representation, i.e., if f is of height d then f is viewed as a vector of d^{m} elements of the ground field, corresponding to the coefficients of the monomials of height at most d. A polynomial f ∈ 𝔽_{q}[X_{1}, …, X_{m}] of height d has size Θ(d^{m} log q).

A rational function f ∈ 𝔽_{q}(X_{1}, …, X_{m}) is represented as a quotient of two (not necessarily relatively prime) polynomials. The height of f is, however, the maximum height of the numerator and denominator of its reduced form. The size of a rational function of height d is Θ(d^{m} log q).

The size of compound objects (polynomials, vectors, matrices, etc.) is the sum of the sizes of their components. The height of a compound object over 𝔽_{q}(X_{1}, …, X_{m}) is the maximum height of the components.

Another important way to represent an associative algebra is in the form of a matrix algebra. In this case it suffices to specify a set of matrices which generates the algebra. However, from this representation one can efficiently find a basis of the algebra and structure constants with respect to this basis. In the opposite direction, the regular representation gives an efficient method to obtain a matrix representation from structure constants. Similarly, representation of matrix Lie algebras (subspaces of M_{n}(K) closed under the operation [x, y] = xy − yx) by structure constants can be efficiently computed. On the other hand, no efficient method is known to find a faithful matrix representation of a Lie algebra. (The celebrated Ado–Iwasawa theorem asserts the existence of such representations. No subexponential bound is known on the degree of the smallest faithful representation in general.) Note however, that in many important cases (such as computing Cartan subalgebras) taking the adjoint representation (the analogue of the regular representation of associative algebras) is sufficient for our purposes.

Since integrality generally simplifies our computations, we often compute integral bases of our substructures. If K = ℚ or K = 𝔽_{q}(X_{1}, …, X_{m}), K is the field of quotients of a nice factorial domain R, namely that of R = ℤ or R = 𝔽_{q}[X_{1}, …, X_{m}], respectively. With some sloppyness we shall call the elements of R integral elements. (The terminology is justified by the fact that R is integrally closed in K, i.e., R is the set elements of K integral over R.) In these cases by a standard trick we may achieve the situation where the structure constants are integral. If δ ∈ R is a common multiple of the denominators of the structure constants of the algebra A with respect to the basis a_{1}, …, a_{n}, then the structure constants w.r.t. the basis δa_{1}, …, … δa_{n} are from R.

We shall also work with R-lattices, i.e., finitely generated R-submodules of linear Kspaces. Typical examples are free R-lattices given by bases. A set of vectors is a basis of a free lattice if and only if they are linearly independent over K. Note that if R = ℤ or R = 𝔽_{q}[X] then R is a Euclidean domain and every R-lattice is free. Furthermore, from a set of generators of a lattice a basis can be computed in polynomial time by the method of [Fr]. If W is a K-subspace of a K-linear space V given by a basis, then it is very easy to compute an integral basis of W, i.e., a basis from the lattice generated by the basis consisting of vectors that have integral coordinates w.r.t. the basis of V.

Basic computations over number fields and finite fields

There are deterministic polynomial time algorithms for the arithmetical operations in K (as well as for polynomial arithmetic over K) if K is a finite field or an algebraic number field. The reader is referred to [Kn] for more details. The basic algorithmic tasks of linear algebra (such as computing ranks, determinants, and solving systems of linear equations) can also be accomplished in deterministic polynomial time. The standard textbook methods (such as Gaussian elimination) use polynomially many arithmetical operations over K. If K is finite, the size of intermediate data cannot explode therefore these methods are directly applicable. In the number field case it will be sufficient to solve linear algebra problems over ℚ. Polynomial time methods are available to solve systems of linear equations over ℚ and over ℤ (cf. [Bar], [Ed], [Fr], [KB]).

Basic computations over 𝔽_{q}(X_{1}, …, X_{m})

We summarize here some basic methods for computing over the field 𝔽_{q}(X_{1}, …, X_{m}). We will need bounds on heights in Chapters 3 and 4.

Operations

The arithmetical operations in 𝔽_{q}(X_{1}, …, X_{m}) can be carried out using (d^{m} log q)^{O(1)} bit operations, where d is a bound on the height of the operands. Computing a linear combination of l vectors of dimension n has complexity (d^{m}ln log q)^{O(1)}, where d is a bound on the height of the operands. The complexity of multiplication in an algebra over 𝔽_{q}(X_{1}, …, X_{m}) is ((dΔ)^{m}n log q)^{O(1)}, where in addition to the preceding notation, Δ is a bound on the height of the structure constants. As we have the bound (nΔ)^{O(1)} on the height of the output object, we infer that the bit size of the output object is ((nΔ)^{m} log q)^{O(1)}.

The product and sum of r elements of 𝔽_{q}(X_{1}, …, X_{m}) of heights d_{1}, …, d_{r} has height at most d_{1} + … + d_{r}, and a similar bound can easily be obtained for linear combinations of vectors. An important case is the addition of integral operands, i.e., if the operands are all in 𝔽_{q}[X_{1}, …, X_{m}] or they are vectors with all coordinates in 𝔽_{q}[X_{1}, …, X_{m}]. In this case, the height of a sum is bounded by the largest of the heights of the operands.

Height of factors of polynomials

The height of a polynomial over 𝔽_{q}(X_{1}, …, X_{m}) is the maximum height of its coefficients. Let f, g, h ∈ 𝔽_{q}[X_{1}, …, X_{m}][X] be polynomials such that f = gh. Let r resp. s be the smallest indices such that the coefficients of X^{r} resp. X^{s} have the largest height among the coefficients of g, h, resp. Then all other summands in the coefficient of X^{r+s} have height less than the height of the product of the coefficients of X^{r} and X^{s}. We infer that in the ring of the polynomials with integral coefficients the height of a factor of a polynomial f is not greater than the height of f.

Specializations

We often need “sufficiently many” relatively prime maximal ideals of 𝔽_{q}[X_{1}, …, X_{m}] such that the residue class fields are small finite fields. We have q^{m} specializations over the ground field: maximal ideals of type ((X_{1} − c_{1}), …, (X_{m} − c_{m})), c_{i} ∈ 𝔽_{q}. In this case the residue class field is 𝔽_{q}. In some cases (when q is small) we shall work with a suitably chosen finite extension of 𝔽_{q}.

Linear algebra problems

Determinant Let the height of a matrix M from M_{n}(𝔽_{q}(X_{1}, …, X_{m})) be Δ. If M is integral (i.e., M ∈ M_{n}(𝔽_{q}[X_{1}, …, X_{m}]) ) then the height of its determinant is bounded by nΔ. In the general case we have the bound n^{3}Δ. (The numerators become of height at most n^{2}Δ when we clear the denominators.) We can compute the determinant of an integral matrix via Chinese Remaindering: we specialize the matrix at (nΔ + 1)^{m} places from I^{m}, where I is a subset of cardinality nΔ+1 of the ground field 𝔽_{q} (or of an extension of degree ⌈log_{q}(nΔ + 1)⌉ if q is small), compute the determinant in the residue class fields and then using Lagrange interpolation compute in each step (nΔ + 1)^{m−i} interpolating polynomials of maximum degree at most nΔ in 𝔽_{q}[X_{1}, …, X_{i}].

Matrix inversion, nonsingular systems of linear equations With the aid of determinants we can readily compute the inverse of a matrix from M_{n}(𝔽_{q}[X_{1}, …, X_{m}]) of height Δ. In this (not necessarily reduced) representation, the elements of the inverse matrix have numerators of height at most (n − 1)Δ and a common denominator of height at most nΔ. Thus, as a simple observation, we have that the height of the inverse of an integral matrix will be at most nΔ; for an arbitrary element of M_{n}(𝔽_{q}(X_{1}, …, X_{m})) we have a factor n^{3} instead of n. Similarly, determinants allow us to use Cramer’s rule for solving nonsingular systems of linear equations. For the height of the solution, we have bounds similar to the bounds for inverse matrices.

Linear independence of vectors, rank of matrices. If we have l integral vectors (i.e., the components are in 𝔽_{q}[X_{1}, …, X_{m}]) of length n and height at most Δ, then the rank of the matrix consisting of these vectors is at most min(n, l) and the height of the subdeterminants is at most min(n, l)Δ, hence we can test their independence via (1 + min(n, l)Δ)^{m} specializations. The case of matrices whose components are general rational functions can be reduced to the case of integral matrices of the same rank and of height min(n, l)Δ by clearing denominators.

Homogeneous systems of linear equations Given a homogeneous system of l linear equations for n variables, the solution is the kernel V of the n × l matrix of the system and our objective is to compute a basis of V. We can assume that the coefficients are integral (we can readily obtain an equivalent system with coefficients from 𝔽_{q}[X_{1}, …, X_{m}] of height at most nl times larger than the height of the original coefficients) and compute an integral basis of the solution. Let us denote the rank of the matrix by r. We can obtain a basis of the solution space in the standard way. This involves solving n − r nonsingular systems of linear equations in r variables each. Multiplication with the determinant provides integral solutions. In this way we obtain an integral basis of the solution space of height at most rΔ, where Δ is a bound on the height of the coefficients.

Alternatively, if we already know a bound Γ on the height of an integral basis of the solution space (min(n, l)Δ in general), then we can solve a homogeneous system of linear equations over the ground field 𝔽_{q} consisting of at most (Γ+Δ)^{m} equations for Γ^{m} variables (i.e., the system describing that all the coefficients vanish), and from a solution choose a maximal independent set over 𝔽_{q}[X_{1}, …, X_{m}].

Elementary computations in algebras

The identity element of A, if exists, can obviously be obtained as a solution of a system of linear equations. The same holds for certain substructures such as the center and centralizer. Bases of subalgebras, left ideals, right ideals, two-sided ideals generated by a finite subset X ⊂ A, as well as structure constants for subalgebras and factoralgebras can also be computed in straightforward ways. The minimal polynomial of an element x ∈ A can be computed using the standard method. There are obvious polynomial bounds on the sizes of these objects in algebras over number fields as well as on their heights in the function field case.

f-algorithms and ff-algorithms

It will be handy to use some conventions introduced by Rónyai ([Ró3, Ró4]). Some of our methods rely on solutions of subproblems not known to have deterministic polynomial time algorithms. These subproblems are finding the prime factorization of an integer and factoring polynomials over a finite prime field. An ff-algorithm is a deterministic method if it is allowed to call oracles for these two problems. Similarly an f-algorithm is a deterministic method which is allowed to call an oracle for factoring polynomials over finite fields. In both cases the cost of a call is the size of the input of the call.

The use of f-algorithms is convenient because of the fact that the monic polynomials g ∈ K[X] dividing a polynomial f ∈ K[X] are in one-to-one correspondence with the ideals in the factoralgebra K[X]/(f), whence factoring polynomials over K is in fact a subcase of, say, finding the maximal ideals of commutative K-algebras.

The first deterministic polynomial time algorithm for factoring polynomials over ℚ was proposed in the seminal paper [LLL]. This result was later extended to arbitrary number fields in [Ch], [Gri], [La], and [Len]. For factoring polynomials over finite fields a deterministic method was given by Berlekamp in [Ber1, Ber2]. The method is based on a deterministic polynomial time reduction to factor polynomials that split into linear factors over the prime field, and a brute force search method for solving the latter special case. The time complexity of this algorithm is polynomial in the parameters p, log_{p} q and deg (f), where f ∈ 𝔽_{q}[x] is the polynomial to be factored and the characteristic of 𝔽_{q} is the prime p. Note that the input size is in fact Θ(log q deg f), therefore the running time of the method is not polynomial in the input size. In [Ber3], Berlekamp proposed a randomized (Las Vegas) factoring algorithm that runs in time polynomial in the input size. (In contrast to Monte Carlo methods, Las Vegas methods never give incorrect answer.) It follows that a polynomial time f-algorithm can be replaced with a polynomial Las Vegas method.

For factoring integers no polynomial time methods are known, neither deterministic nor randomized. This problem is widely believed to be difficult. We will use ff-algorithms for some problems related to simple algebras over number fields.

1.3 Previous results

In this section we give a short summary of the most important results in the area of computing the structure of algebras. For more bibliographic details the reader is referred to the survey paper [Ró4]. We continue to use the term algebra for a finite dimensional associative algebra over the field K (given by structure constants). The ground field is always either a finite field or an algebraic number field.

The radical

The first method for computing the radical of algebras over fields of zero characteristic is due to Dickson [Di]. The method is based on a characterization via a system of linear equations.

In [Ró2], L. Rónyai proposed an analogous, although much more sophisticated characterization of the radical of algebras over finite prime fields. This characterization results in a deterministic polynomial time algorithm for computing the radical of algebras over finite fields. Note that Eberly extended the characterization to algebras over arbitrary finite fields.

Wedderburn decomposition

The first efficient algorithm for computing the minimal ideals of semisimple algebras over finite fields and algebraic number fields was given by K. Friedl (cf. [FR]). The method is an iteration based on factoring minimal polynomials of a basis of the center over certain extensions of the ground field obtained from earlier steps of iteration. In the number field case, the method is a deterministic polynomial one, while in the finite case the method is a polynomial time f-algorithm.

Eberly in [Eb2] presented a polynomial time Las Vegas algorithm which avoids iteration. The key idea is that (under the reasonable assumption that the ground field has sufficiently many elements) a random element of a commutative semisimple algebra is in fact a generating element. (We note that this method can be derandomized using the techniques of Chapter 5.) In the same paper, a deterministic (and parallelizable) reduction to factoring minimal polynomials of the basis elements of the center is also presented.

In [GMT], Gianni, Miller and Trager outline a method, based on lifting primitive idempotents modulo an appropriate small prime, for computing the Wedderburn decomposition of a commutative semisimple algebra over ℚ. The running time is exponential in the dimension. The authors claim that a combination with lattice basis reduction techniques of [LLL] leads to a polynomial time method. In fact, our method of Chapter 4 could be applied to algebras over ℚ.

Decomposition of simple algebras

In this subsection we denote by A a central simple algebra of dimension n^{2} over the field K.

In the case when K is finite, by a theorem of Wedderburn, A is isomorphic to M_{n}(K). In [Ró2], L. Rónyai proposed a polynomial time f-algorithm for computing such an isomorphism.

The problem of decomposition of simple algebras over number fields appears to be much more difficult. In [Ró1], Rónyai gives a Las Vegas polynomial time reduction from the quadratic residuosity problem to computing the index of central simple algebras of dimension 4 (so-called quaternion algebras) over ℚ. Note that the result is conditional on the Generalized Riemann Hypothesis (GRH for short). (For generalizations of the Riemann Hypothesis and their significance in computational number theory the reader is referred to Bach [Bach].) The quadratic residuosity problem, formulated by Goldwasser and Micali in [GM], is to decide whether a number is quadratic residue modulo a squarefree number, and is believed to be difficult. It is also shown in [Ró1] that finding a zero divisor in a quaternion algebra over ℚ is (again under GRH) at least as hard as finding solutions of quadratic congruences x^{2} ≡ a (mod n) (taking a square root of a if exists) modulo a squarefree number n, which is, up to a Las Vegas polynomial time reduction (see [Ra] or [GM]) is as hard as factoring n. This fact justifies the use of ff-algorithms to solve related problems.

On the other hand, Rónyai proved [Ró3] that the decision problem related to computing the index of the central simple algebra A over the number field K is in NP ∩ coNP. In fact, the existence of a maximal order with short description and verification is proved and the result is combined with a technique, based on Hasse’s principle to compute the index from a maximal order. For testing maximality of an order a polynomial time ff-algorithm is used.

An easier task is to compute an isomorphism A_{L} ≅ M_{n}(L) for an appropriate extension L of K. Using again the technique of random elements, Eberly in [Eb1] and [Eb3] presents a Las Vegas polynomial time method to construct such an extension L together with an isomorphism A_{L} ≅ M_{n}(L). He applies this to compute isomorphism A_{ℝ} ≅ M_{n}(ℝ) or A_{ℝ} ≅ M\frac{n}{2} (ℍ) for embeddings K → ℝ. Here, ℍ stands for the skewfield of the Hamiltionian quaternions. Note that this method can be derandomized using the results in [Ró5] or techniques of Chapter 5.

Testing membership in abelian matrix groups over number fields

In this brief chapter we present an application of algebra decompositions over number fields to a basic problem related to matrix groups. This material has been published as a part of the paper [BBCIL], joint work with László Babai, Robert Beals, Jin-yi Cai, and Eugene M. Luks. Let K be a number field, n and r be positive integers, and h, g_{1}, …, g_{r} ∈ GL_{n}(K) be invertible n by n matrices over K. We assume the dense representation, i.e., matrices are inputted as arrays of n^{2} elements from K, where elements of K are represented as arrays of d = [K : ℚ] rational numbers and K is given by structure constants (or by the minimal polynomial of a primitive element) over ℚ. The membership problem is the problem of deciding whether h is in the subgroup G of GL_{n}(K) generated by g_{1}, …, g_{r}. The constructive membership problem is, in addition to testing membership, to express h in terms of the generators in the case when h is in the group G. Note that the membership problem is in general undecidable for n ≥ 4 (see [Mi]). We restrict ourselves to the abelian case, i.e., we assume that the matrices h, g_{1}, …, g_{r} ∈ GL_{n}(K) are pairwise commuting. (This condition can be efficiently tested in the straightforward way.)

The constructive membership problem for abelian matrix groups is to test whether the equation

(∗)  g_{1}^{x_{1}} ⋯ g_{r}^{x_{r}} = h

admits an integer solution (x_{1}, …, x_{r}) ∈ ℤ^{r}, and if it does, find such a solution.

We present a deterministic polynomial time algorithm for this problem. Our method is based on a reduction to the case n = 1, which was recently solved by G. Ge in [Ge1, Ge2]. Ge’s theorem. Given an algebraic number field K and nonzero elements α_{1}, …, α_{r} ∈ K, one can in polynomial time compute a basis of the lattice consisting of the solutions (x_{1}, …, x_{r}) ∈ ℤ^{r} to the equation

1 = α_{1}^{x_{1}} ⋯ α_{r}^{x_{r}}.

Note that the analogous problem for commutative semigroups (where the matrices a_{1}, …, a_{r} are not necessarily regular but the exponents x_{1}, …, x_{r} are required to be nonnegative) was solved for the special case r = 2 in [CLZ]. For generalizations of the problem the reader is referred to the paper [BBCIL]. More recent developments for the membership problem in matrix groups can be found in [Bea].

2.1 The algorithm

First we observe that it is sufficient to find bases of lattices given as solutions to equations of the form

(∗∗)  g_{1}^{x_{1}} ⋯ g_{r}^{x_{r}} = Id_{n},

a special case of (∗) taking h = Id_{n}. Indeed, we take g_{0} = h^{−1}, introduce a new variable x_{0}, and find a basis of the lattice L of the solutions to the equation

g_{0}^{x_{0}}g_{1}^{x_{1}} ⋯ g_{r}^{x_{r}} = Id_{n}

in r + 1 variables. An element of L with first coordinate x_{0} = 1 can be found by solving a linear equation over ℤ.

Let A ≤ M_{n}(K) be the subalgebra of M_{n}(K) generated by the matrices g_{1}, …, g_{r}. Obviously, A is commutative and, since g_{1} is invertible, contains the identity matrix Id_{n}. We can compute a basis of A and the corresponding structure constants in polynomial time. We use Dickson’s method [Di] to compute the radical Rad(A), and then the method [FR] to compute the simple components \overline{A_{1}}, …, \overline{A_{s}} of the factoralgebra \overline{A} = A/Rad(A). For every j ∈ {1, …, s}, we compute the maximal ideal

∑_{l≠j} \overline{A_{l}}

of \overline{A} complementary to \overline{A_{j}} and hence the natural homomorphism ϕ_{j} : A → \overline{A_{j}}. Since \overline{A_{j}} is simple, we can apply Ge’s method to compute bases of the lattices L_{j} given by

L_{j} = \{(x_{1}, …, x_{r}) ∈ ℤ^{r}| ∏_{i=1}^{r} ϕ_{j}(g_{i})^{x_{i}} = 1\overline{A_{j}}\}.

A basis

\underline{b}_{1} = (b_{11}, b_{12}, …, b_{1r}), …, \underline{b}_{t} = (b_{t1}, b_{t2} …, b_{tr})

of the intersection

L = ⋂_{j=1}^{s} L_{j}

can then be found in polynomial time via solving a system of linear equations over ℤ. Since for the natural homomorphism ϕ : A → \overline{A} we have

ϕ = ⨁_{j=1}^{s} ϕ_{j}.

L is in fact the lattice of the solutions to the equation

∏_{i=1}^{s} ϕ(g_{i})^{x_{i}} = 1\overline{A}.

Obviously, L contains the solutions of (∗∗). Therefore it is sufficient to look for the solutions of (∗∗) in terms of the vectors \underline{b}_{1}, …, \underline{b}_{t}. In other words, our task is to construct a basis of solutions (y_{1}, …, y_{t}) ∈ ℤ^{t} to

∏_{i=1}^{r} g_{i}^{∑_{j=1}^{t} b_{ji}y_{j}} = Id_{n},

which can also be written as

(∗∗∗)  ∏_{j=1}^{t} g′_{j}^{y_{j}} = Id_{n},

where for every j ∈ {1, …, t}, the matrix g′_{j} is defined as

g′_{j} = ∏_{i=1}^{r} g_{i}^{b_{ji}}.

Since \underline{b}_{1}, …, \underline{b}_{r} are in L, we have ϕ(g′_{j}) = 1\overline{A}, whence g′_{j} − Id_{n} ∈ Rad(A) for every j = 1, …, t.

In an algebra A with identity the elements u = 1+v where v ∈ Rad(A) form a subgroup U(A) (called the unipotent radical) in the multiplicative group A^{∗} of units (invertible elements). For an element u = 1+v ∈ 1+Rad(A), we define the logarithm log u ∈ Rad(A) to be the sum

log u = ∑_{i=1}^{∞} \frac{(−1)^{i−1}}{i} v^{i}.

(Note that this sum has only at most dim_{K}Rad(A) nonzero terms.) The logarithm-map log : U(A) → Rad(A) is invertible, the inverse is

exp(v) = ∑_{i=0}^{∞} \frac{1}{i!}v^{i}

for v ∈ Rad(A). In addition, if A is commutative (as in our case) then these maps are group isomorphisms (U(A), ·) ≅ (Rad(A), +). It follows that equation (∗∗∗) is equivalent to

∑_{j=1}^{t} y_{j} log g′_{j} = 0.

Expanding this equation w.r.t. matrix entries, we obtain a system of n^{2} homogeneous linear equations with coefficients from K, which is, after further expansion, equivalent to a system of n^{2} × [K : ℚ] homogeneous linear equations with coefficients from ℚ. After clearing denominators, we obtain a system with coefficients from ℤ, which can be solved in polynomial time.

We have proved the following

Theorem 2.1.1 The constructive membership problem for commutative matrix groups over number fields can be solved in deterministic polynomial time. □

Computing the radical

The material presented in this chapter is a combination obtained from parts of the papers [IRSz] (joint work with Lajos Rónyai and Ágnes Szántó) and [CIW] (joint work with Arjeh M. Cohen and David B. Wales). In [Di], Dickson gave a nice characterization of the radical of a matrix algebra A ≤ M_{n}(K), where charK = 0. Namely, Rad(A) is the largest left (right, or two-sided) ideal L of A such that the trace of every element of L is zero. This characterization leads to an efficient computation of Rad(A). It can be obtained as the solution space of a system of homogeneous linear equations.

If K is of positive characteristic p then the trace of a matrix algebra A ≤ M_{n}(K) can vanish even if A is semisimple. For the case K = 𝔽_{p}, Rónyai introduced in [Ró2] a new linear function Tr′ : A → K when the ordinary trace is identically zero on A. This new function can still vanish on A, but then a further linear function Tr′′ can be introduced, and so on. However, if A is not nilpotent then this procedure terminates in at most ⌈log_{p} n⌉ rounds. This leads to a method analogous to Dickson’s algorithm for computing the radical. A decreasing sequence of ideals of A can be computed using solutions of systems of linear equations. The sequence collapses to the radical in at most ⌈log_{p} n⌉ steps. The construction of the functions is based on integral lifts of matrices.

Eberly extended Rónyai’s results to matrix algebras over arbitrary finite fields [Eb1]. The construction of Eberly’s functions is still based on lifting matrices to characteristic zero. The new functions are semilinear rather than linear if the ground field is greater than the prime field.

Here we present a construction based on the paper [CIW] that works in matrix algebras over an arbitrary field of positive characteristic. The functions are defined as certain coefficients of the characteristic polynomial.

Section 3.1 is devoted to the definitions and basic properties of the generalized trace functions and a characterization of the radical that extend the above mentioned results of Rónyai and Eberly. In Section 3.2, we relate our functions to those used in [Ró2], [Eb1] and [IRSz]. In the zero characteristic case, the values of the trace function on a basis of A are known to determine the composition factors of the underlying A-module. In Section 3.3, we give a generalization of this fact. In Section 3.4, based on work [IRSz], we present an algorithm to compute the radical of algebras over finitely generated pure transcendental extensions of finite fields.

Throughout this chapter, A denotes a finite dimensional associative algebra over the field K. By U, V, W, etc. we denote finite dimensional A-modules. For standard facts and definitions related to modules and representations the reader is referred to textbooks, e.g., [Pie]. To avoid confusion, we fix here some minor details of the terminology. The A-module {0} is called the trivial A-module. An A-module Z is a zero module if az = 0 for every a ∈ A and z ∈ Z. An A-module V is called simple or irreducible if V is not a zero module and V admits exactly two submodules: {0} and V. The composition factors of a nontrivial module V are either simple modules or one-dimensional zero modules. We shall refer to the composition factors of V that are simple modules as the nonzero composition factors of V.

3.1 Trace functions and the radical

Let V be a finite dimensional A-module. For a ∈ A we denote the action of a on V by a_{V}. This means, that a_{V} ∈ End_{K}V is the linear transformation v ↦ av. The characteristic polynomial χ_{V,a}(X) of the action of a on V is simply the characteristic polynomial χ_{a_{V}} (X) = det (a_{V} − X · Id_{V}) of the linear transformation a_{V}. For our purposes it appears to be more convenient to use the variant

χ̃_{V,a}(X) = det (X · a_{V} + Id_{V}) = X^{dim_{K}V} χ_{V,a}(−1/X)

of the characteristic polynomial. For an integer s > 0 we define the s’th trace Tr_{V} (s, a) of the action a on V as the s’th coefficient of the polynomial χ̃_{V,a}(X) (considered as a formal power series in X):

χ̃_{V,a}(X) = 1 + ∑_{s=1}^{∞} Tr_{V} (s, a)X^{s}.

Obviously, Tr_{V} (s, a) = 0 for s > dimV, while Tr_{V} (1, a), Tr_{V} (2, a), …, Tr_{V} (dimV, a) are up to sign the coefficients of the characteristic polynomial:

(−1)^{dimV} χ_{V,a}(X) = X^{dimV} + ∑_{s=1}^{dimV} (−1)^{s}Tr_{V} (s, a)X^{dimV −s}.

Tr_{V} (1, ·) coincides with the ordinary trace function Tr_{V} (·), therefore it is linear on A. Note that, for general s, Tr_{V} (s, a) is the trace of the (diagonal) action of a on the s’th exterior power of V.

If U is a submodule of V, by choosing a basis appropriately, the corresponding matrix representation has a block-upper triangular form. It is obvious that for every a ∈ A,

χ̃_{V,a}(X) = χ̃_{U,a}(X)χ̃_{V/U,a}(X).

It follows that if two A-modules V and U have the same composition factors (counted with multiplicities), then Tr_{U}(s, a) = Tr_{V} (s, a) for every positive integer s and a ∈ A. Note that if Z is a zero module, then χ̃_{Z,a}(X) is identically 1 for every a ∈ A. Therefore if the nonzero composition factors of W and V coincide then Tr_{W} (s, a) = Tr_{V} (s, a).

If A is semisimple then Wedderburn’s theorems say that A is a direct sum of full matrix rings over division algebras. The irreducible nonzero modules are the natural modules on exactly one of these matrix rings. If A is not semisimple, then Rad(A) is the intersection of the annihilators of all the irreducible modules. As a consequence, the trace functions are in fact defined on A/Rad(A), i.e., Tr_{V} (s, a + b) = Tr_{V} (s, a) for every A-module V, integer s > 0, a ∈ A, and b ∈ Rad(A). In particular, the fuctions Tr_{V} (s, ·) vanish on Rad(A). If V is a faithful A-module and the functions Tr_{V} (s, ·) are identically zero on A for every integer s > 0, then every a ∈ A is nilpotent, whence A is nilpotent. It follows that if V is faithful, and L is a left (or right) ideal in A such that the functions Tr_{V} (s, ·) are identically zero on L for every integer s > 0, then L is a nilpotent one sided ideal in A, whence L ⊆ Rad(A). As a consequence, (assuming again that V is faithful), we have

Rad(A) = {a ∈ A|Tr_{V} (s, a) = Tr_{V} (s, ba) = 0 for every s > 0 and b ∈ A}.

If K is of characteristic zero then Dickson’s classical result [Di] is that

Rad(A) = {a ∈ A|Tr_{V} (1, a) = Tr_{V} (1, ba) = 0 for every b ∈ A},

As Tr_{V} (1, ·) is linear on A, this characterization leads to an efficient algorithm for Rad(A): it can be obtained by solving of a system of homogeneous linear equations.

Our aim is to obtain a similar result in positive characteristic. From now on we assume that K is of positive characteristic p. First we observe that there is an obvious sufficient condition for that trace functions of low index vanish on A. In that case, some higher trace function will be semilinear.

Proposition 3.1.1 Assume that K is of positive characteristic p and the multiplicities of the nonzero composition factors of V are all divisible by p^{j} for an integer j > 0. Then Tr_{V} (s, a) = 0 for every a ∈ A and positive integer s such that p^{j}/|s. Furthermore, the function Tr_{V} (p^{j}, ·) is p^{j}-semilinear on A, i.e., for every α, β ∈ K and a, b ∈ A, we have

Tr_{V} (p^{j}, αa + βb) = α^{p^{j}}Tr_{V} (p^{j}, a) + β^{p^{j}}Tr_{V} (p^{j}, b).

Proof Let V_{1}, …, V_{h} be representatives of the isomorphism classes of the nonzero irreducible A-modules occurring in a composition series of V with multiplicities m_{1}p^{j}, …, m_{h}p^{j}. Let W = V_{1}^{m_{1}} ⊕ … ⊕ V_{h}^{m_{h}}, the formal direct sum of m_{1} copies of V_{1}, m_{2} copies of V_{2}, …, and m_{h} copies of V_{h}. Obviously, for every a ∈ A we have χ̃_{V,a}(X) = χ̃_{W,a}(X)^{p^{j}}, whence Tr_{V} (s, a) is zero for every positive integer s not divisible by p^{j}, Tr_{V} (p^{j}, a) = Tr_{W} (1, a)^{p^{j}}, and semilinearity of Tr_{V} (p^{j}, ·) follows from the linearity of the ordinary trace function Tr_{W} (1, ·) = Tr_{W} (·). □

If K is algebraically closed, then the converse also holds.

Proposition 3.1.2 Assume that K is an algebraically closed field of positive characteristic p. Let j be a positive integer and assume that Tr_{V} (p^{i}, a) = 0 for every a ∈ A and 0 ≤ i < j. Then the multiplicities of the nonzero composition factors of V are all divisible by p^{j}.

Proof Since the values Tr_{V} (p^{i}, a) depend only on a+Rad(A) and the nonzero composition factors of V, we may without loss of generality assume that both A and V are semisimple. Assume that V contains an irreducible constituent W with multiplicity mp^{t}, where t < j and p does not divide m. Since K is algebraically closed, the action of A on W is isomorphic to the full matrix ring M_{d}(K) (where d = dim_{K}W) and there is a primitive idempotent e in A such that e has matrix

( \begin{matrix}1 & 0 & · & · & 0 \\ 0 & 0 & · & · & 0 \\ · & · & · & · & · \\ · & · & · & · & · \\ 0 & 0 & · & · & 0 \end{matrix} )

in its action on W with respect to some basis. Since e is a primitive idempotent, it acts as zero on the irreducible A-modules not isomorphic to W. It follows that

χ̃_{V,e}(X) = χ̃_{W,e}(X)^{mp^{t}} = (1 + X)^{mp^{t}} = (1 + mX + …)^{p^{t}} = 1 + mX^{p^{t}} + …,

in other words, Tr(p^{t}, e) = m · 1_{K} ≠ 0. □

We define a sequence of subsets A = A_{V,0} ⊇ A_{V,1} ⊇ A_{V,2} … inductively by

A_{V,j+1} = {a ∈ A_{V,j}|Tr_{V} (p^{j}, a) = Tr_{V} (p^{j}, ba) = 0 for every b ∈ A_{V,j}}.

Obviously, for every j, A_{V,j} ⊇ Rad(A). If the ground field is algebraically closed, propositions 3.1.1 and 3.1.2 give a characterization of the subsets A_{V,j}. It generalizes the interpretation of the radical Rad(A) of A as the annihilator of all the simple A-modules:

Rad(A) = {a ∈ A | aL = 0 for every simple A-module L} .

Proposition 3.1.3 Assume that K is an algebraically closed field of characteristic p > 0. Let the composition factors of V be V_{1}, …, V_{r} with multiplicities m_{1}, …, m_{r}. Then for every integer j ≥ 0, A_{V,j} equals the annihilator

I_{V,j} = {a ∈ A | aV_{s} = 0 for every s such that p^{j}/|m_{s}}.

As a consequence, for every j, A_{V,j} is an ideal in A.

Proof Again, w.l.o.g., we may assume that A is semisimple. For every j ≥ 0, the annihilator I_{V,j} is the intersection of the kernels of the actions of A on the simple modules V_{s} such that p^{j}/|m_{s}, therefore I_{V,j} is an ideal. Proposition 3.1.1 implies that for every j, I_{V,j} ⊆ A_{V,j}. We prove that A_{V,j} = I_{V,j} by induction on j. The assertion is trivial for j = 0. Assume that for some j ≥ 0 we have A_{V,j} = I_{V,j}. By Proposition 3.1.1, Tr(p^{j}, ·) is semilinear on I_{V,j}, whence A_{V,j+1} is a left ideal in I_{V,j}, therefore it is a left ideal of A as well. In particular, A_{V,j+1} is a subalgebra, and from Proposition 3.1.2 we infer that the multiplicities of the nonzero composition factors of V as an A_{V,j+1}-module are all divisible by p^{j+1}. On the other hand, since A_{V,j+1} is a left ideal, the nonzero simple A_{V,j+1}-modules are simple A-modules as well, giving that A_{V,j+1} ⊆ I_{V,j+1}. □

Now we are ready to prove the most important properties of the trace functions.

Theorem 3.1.4 Let K be an arbitrary field of characteristic p > 0. For every integer j ≥ 0, we have

(i) A_{V,j} is an ideal in A containing Rad(A),

(ii) Tr_{V} (s, a) = 0 for every a ∈ A_{V,j} and positive integer s such that p^{j}/|s,

(iii) The function Tr_{V} (p^{j}, ·) is p^{j}-semilinear on A_{V,j} in the sense that for every a, b ∈ A_{V,j} and α, β ∈ K, we have

Tr_{V} (p^{j}, αa + βb) = α^{p^{j}}Tr_{V} (p^{j}, a) + β^{p^{j}}Tr_{V} (p^{j}, b)

(iv) If V is a faithful A-module and p^{j} > dim_{K}V, then A_{V,j} = Rad(A).

Proof Let K̄ be an algebraic closure of K. Then A can be identified with the subalgebra 1 ⊗ A of \overline{A} = K̄ ⊗_{K} A. Also, if V is a K-module then \overline{V} = K̄ ⊗ V can considered to be an \overline{A}-module in a natural way. (The multiplication is the K-bilinear extension of (α ⊗ a) · (β ⊗ v) := (αβ) ⊗ (av).) If we fix a K-basis v_{1}, …, v_{m} of V then 1 ⊗ v_{1}, …, 1 ⊗ v_{m} is a K̄-basis of \overline{V}, and the matrix of the action of a ∈ A on V with respect to the basis v_{1}, …, v_{m} is also the matrix of the action of 1 ⊗ a on \overline{V} with respect to the basis 1 ⊗ v_{1}, …, 1 ⊗ v_{m}. It follows that the characteristic polynomials χ, their variants χ̃, and therefore our trace functions remain the same on A. We have also Rad(A) = A ∩ Rad(\overline{A}). (Altough there are examples where dim_{K}Rad(A) < dimK̄Rad(\overline{A}).)

The propositions proved above state that all the assertions hold for \overline{A} and \overline{V} in place of A and V, respectively. Obviously, it is enough to prove the equalities

A_{V,j} = A ∩ \overline{A}_{\overline{V} ,j}, (j = 0, 1, 2, …).

But this fact can be proved by an easy induction on j, using the semilinearity of the function Tr\overline{V} (p^{j}, ·) on \overline{A}_{\overline{V} ,j}. □

3.2 Computing trace functions via lifting

In this section we relate our functions to those used in [Ró2], [Eb1], or [IRSz]. We need the following elementary combinatorial fact.

Lemma 3.2.1 Let m and i be positive integers and consider the permutation group G on Ω = {1, …, m^{i}} generated by the cyclic permutation α = (12 ⋯ m^{i}). Let 0 < j ≤ i. Then the size of an orbit of G acting on the j-element subsets of Ω is divisible by m^{i−j+1}.

Proof A subgroup H ≤ G of order r has m^{i}/r orbits of size r in Ω. The subsets of Ω stabilized by H are unions of some of these orbits and hence their sizes are divisible by r. Now if H is the stabilizer of a j-element subset of Ω and |H| = r, then r | j and the size of the orbit of G (among the j-element subsets) containing this set is m^{i}/r. Suppose indirectly that m^{i}/r is not divisible by m^{i−j+1}. Then there exists a prime power factor q of m, such that q^{i−j+1} does not divide m^{i}/r, whence q^{j−1} ≠ r and q^{j−1} | r | j. We have that 2^{j−1} ≤ q^{j−1} < r ≤ j, which is impossible if j ≥ 1. □

Let R be an arbitrary commutative ring with identity and P be an ideal in R. We shall use the customary congruence-notation, i.e, for x, y ∈ R we write x ≡ y (mod P) if x − y ∈ P.

Proposition 3.2.2 Let n be a positive integer, R be a commutative ring with identity and a, b ∈ M_{n}(R). Let m be a positive rational integer and P be an ideal of R containing m1_{R}. Suppose that a ≡ b (mod P M_{n}(R)). Then

Tr(a^{m^{j}}) ≡ Tr(b^{m^{j}}) (mod P^{j+1})

for all nonnegative integers j.

Proof Let d = b − a, then d ∈ P M_{n}(R).

b^{m^{j}} − a^{m^{j}} = (a + d)^{m^{j}} − a^{m^{j}} = ∑_{∅≠σ⊆{1,...,m^{j}}} u_{1}^{σ}u_{2}^{σ} ⋯ u_{m^{j}}^{σ},

where u_{r}^{σ} = d, if r ∈ σ; u_{r}^{σ} = a otherwise. Since Tr(vw) = Tr(wv), the traces of the terms in one orbit of the group G generated by π = (12 ⋯ m^{i}) are all the same. The trace of a term containing i d’s is in P^{i}. If i > j, then we obtain immediately that the contribution of the orbit is in P^{j+1}. If 0 < i ≤ j, then sum of the traces of the terms in a G-orbit is in m^{j−i+1}P^{i} ⊆ P^{j+1} by the preceding lemma. □

We use this in the situation where m = p, a rational prime, P is a maximal ideal in R above p, and K = R/P. We have that, for a matrix a over R, the residue class of Tr(a^{p^{j}}) modulo P^{j+1} depends only on the residue classes of the entries of the matrix a modulo P. In other words the function a ↦ Tr(a^{p^{j}})+P^{j+1} is in fact a function M_{n}(K) → R/P^{j+1}. We use a notation analogous to that we introduced in the preceding section. For a ∈ M_{n}(R), Tr(s, a) stands for the sth coefficient of the polynomial χ̃_{a}(X) = det (Id_{n} + Xa) ∈ R[X]. (Since we work with a fixed module V = R^{n}, we omit the subscript V.)

Proposition 3.2.3 Let n be a positive integer, R be a commutative ring with identity element and p be a rational prime. Let j be a positive integer and P an ideal of R containing p1_{R}. Assume that a ∈ M_{n}(R) is an n × n matrix with entries from R such that

Tr(p^{i}, a^{h}) ≡ 0 (mod P)

for every positive integer h and nonnegative integer i < j. Then

Tr(a^{p^{j}}) ≡ (−1)^{p^{j}−1}p^{j}Tr(p^{j}, a) (mod P^{j+1}).

Proof The congruence holds trivially if j = 0. Assume that j > 0. Let ā ∈ M_{n}(R/P) be the residue of the matrix a modulo P. By Theorem 3.1.4, applied to the matrix algebra generated by ā, the assumption on a is equivalent to that the coefficients Tr(s, a) of the characteristic polynomial χ_{a}(X) are in P whenever p^{j}/|s.

Recall that the companion matrix C_{f} of a polynomial f(X) ∈ R[X] of the form X^{n} − α_{1}X^{n−1} − … − α_{n} is

( \begin{matrix}0 & 0 & 0 & · & · & · & α_{n} \\ 1 & 0 & 0 & · & · & · & α_{n−1} \\ 0 & 1 & 0 & · & · & · & α_{n−1} \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ · & · & · & · & · & · & · \\ 0 & · & · & · & 0 & 1 & α_{1} \end{matrix} ) .

Moreover the (usual) characteristic polynomial of C_{f} is exactly f. Newton’s identities

Tr(a^{s}) + (−1)^{s}sTr(s, a) + ∑_{r=1}^{s−1}(−1)^{r}Tr(a^{s−r})Tr(r, a) = 0 (s = 1, …, n),

Tr(a^{s}) + ∑_{r=1}^{n}(−1)^{r}Tr(a^{s−r})Tr(r, a) = 0 (s > n)

imply that the traces Tr(a^{s}) are uniquely determined by the coefficients Tr(s, a) of the characteristic polynomial of a. We infer that both sides of the congruence to be proved remain the same if we replace a with the companion matrix of χ_{a}(X). Therefore it is enough to prove the congruence for matrices of the form above such that α_{s} ∈ P for every s such that p^{j}/|s. By Proposition 3.2.2, we may further assume that 0 = α_{s} = ±Tr(s, a) for every s such that p^{j}/|s. In the case p^{j} > n both sides are zero. If p^{j} ≤ n, the p^{j}th Newton identity immediately gives Tr(a^{p^{j}}) + (−1)^{p^{j}}p^{j}Tr(p^{j}, a) = 0. □

Assume that R is an integral domain of characteristic zero such that P = pR is a maximal ideal in R and K ≅ R/pR. Obviously, if K = 𝔽_{p}, we can take R = ℤ. A construction for q = p^{h}, K = 𝔽_{q}[X_{1}, …, X_{m}] (possibly with m = 0, when K = 𝔽_{q}), can be the local ring R = ℤ[X][X_{1}, …, X_{m}]_{(p)}/g(X), where g(X) ∈ ℤ[X] is a monic lift of a monic irreducible polynomial in 𝔽_{p}[X]. Assume that A is a subalgebra of M_{n}(K). As in the preceding paragraph, we can define the ideals A = A_{0} ⊇ A_{1} ⊇ A_{2} ⊇ … of A by

A_{j+1} = {a ∈ A_{j}|Tr(p^{j}, a) ≡ Tr(p^{j}, ba) ≡ 0 (mod P) for every b ∈ A_{j}}.

In [Ró2], [Eb1], and [IRSz], the fuctions T^{(j)} : A_{j} → K defined by the congruence

p^{j}T^{(j)}(a) ≡ Tr(a^{p^{j}}) (mod P^{j+1})

are used, where R and P ⊲ R are as described above. The last proposition asserts that these functions up to sign coincide with our trace functions.

3.3 Trace functions and composition factors

We know that if the nonzero composition factors of two A-modules W and V coincide, meaning that they are the same as multisets, then Tr_{W} (s, a) = Tr_{V} (s, a) for every a ∈ A. Also, if K is of characteristic zero then the converse holds (see [Di]) in the following strong sense: If B is a basis of A and Tr_{W} (1, a) = Tr_{V} (1, a) for every a ∈ B then the nonzero composition factors of W and V coincide. We generalize this to positive characteristic. We will need the following additivity property.

Lemma 3.3.1 Assume that K is of characteristic p > 0. Let U be a submodule of V. Suppose that Tr_{U}(p^{i}, a) = 0 for every 1 ≤ i < j and a ∈ A or Tr_{V/U}(p^{i}, a) = 0 for every 1 ≤ i < j and a ∈ A. Then

Tr_{V} (p^{j}, a) = Tr_{U}(p^{j}, a) + Tr_{V/U}(p^{j}, a)

for every a ∈ A.

Proof Obviously

χ̃_{V,a}(X) = χ̃_{U,a}(X)χ̃_{V/U,a}(X),

whence

Tr_{V} (p^{j}, a) = Tr_{U}(p^{j}, a) + Tr_{V/U}(p^{j}, a) + ∑_{r,s≥1,r+s=p^{j}} Tr_{U}(r, a)Tr_{V/U}(s, a).

By Theorem 3.1.4 applied to U or V/U, we have Tr_{U}(s, a) = 0 for 1 ≤ s < p^{j} or Tr_{V/U}(s, a) = 0 for 1 ≤ s < p^{j}, giving the statement. □

Theorem 3.3.2 Let K be of characteristic p > 0. Suppose B ⊆ A is a subset of A such that B ∪ Rad(A) is a K-linear generating set of A (e.g., B induces a basis of A/Rad(A)). For the A-modules U and V the following assertions are equivalent.

(i) U and V have isomorphic nonzero composition factors (counted with multiplicities); (ii) Tr_{U}(s, a) = Tr_{V} (s, a) for every a ∈ A and positive integer s; (iii) Tr_{U}(p^{j}, a) = Tr_{V} (p^{j}, a) for every a ∈ A and nonnegative integer j; (iv) Tr_{U}(p^{j}, a) = Tr_{V} (p^{j}, a) for every a ∈ B and j ≤ max{log_{p} dim_{K}U, log_{p} dim_{K}V }.

Proof Assertion (ii) can be reformulated as follows.

(ii′) χ̃_{U,a}(X) = χ̃_{V,a}(X) for every a ∈ A

As the terms composition factors and trace functions are defined modulo Rad(A), we may assume that A is semisimple and the modules U and V are unital. In that case, condition (i) is equivalent to

(i′) U and V are isomorphic A-modules.

Implications (i) ⇒ (ii′) ⇒ (iii) ⇒ (iv) are obvious. First we prove the implication (iv) ⇒ (ii′). Assume that (iv) holds. Let

N = max{⌈log_{p} dim_{K}U⌉, ⌈log_{p} dim_{K}V ⌉}

and W = U^{p^{N} −1} ⊕ V (direct sum of p^{N} − 1 copies of U and one of V). We work in U ⊕ W. We have

χ̃_{U⊕W,a}(X) = (χ̃_{U,a}(X))^{p^{N}} χ̃_{V,a}(X) ≡ χ̃_{V,a}(X) (mod X^{p^{N}}).

In other words, Tr_{U⊕W} (s, a) = Tr_{V} (s, a) for every a ∈ A and integer 0 < s < p^{N}.

We prove by induction on j that Tr_{W} (p^{j}, ·) is identically zero on A if j < N. For j = 0, it follows from the linearity of the ordinary trace. Assume that 0 < j < N and the functions Tr_{W} (p^{i}, ·) are identically zero on A for i < j. Lemma 3.3.1 implies that

Tr_{W} (p^{j}, a) = Tr_{U⊕W} (p^{j}, a) − Tr_{U}(p^{j}, a).

We have seen that the expression on the right hand side is Tr_{V} (p^{j}, a) − Tr_{U}(p^{j}, a), which is zero for every a ∈ B by condition (iv). By Theorem 3.1.4, the function Tr_{W} (p^{j}, ·) must be identically zero on A.

We have proved that the functions Tr_{W} (p^{j}, ·) 0 ≤ j < N vanish on A. Theorem 3.1.4 implies that the same holds for the functions Tr_{W} (s, ·) for every 1 ≤ s < p^{N}. In other words, for every a ∈ A,

χ̃_{W,a}(X) ≡ 1 (mod X^{p^{N}}),

whence

χ̃_{U⊕W,a}(X) ≡ χ̃_{U,a}(X) (mod X^{p^{N}}).

Combining with the congruence

χ̃_{U⊕W,a}(X) ≡ χ̃_{V,a}(X) (mod X^{p^{N}})

and looking at the degrees we infer χ̃_{V,a}(X) = χ̃_{U,a}(X).

We prove implication (ii′) ⇒ (i′) by induction on dim_{K}U. Assume that (ii′) holds. Note that if U is not the trivial module, then there is an s such that Tr_{U}(s, ·) is not identically zero on A, as witnessed by the identity of A. We immediately see that U is the trivial A-module iff V is the trivial A-module as all traces are 0. Let s be the smallest positive integer such that Tr_{U}(s, ·) is not identically zero on A. By Theorem 3.1.4 we have s = p^{j} for some nonnegative integer j and Tr_{U}(s, ·) = Tr_{V} (s, ·) is semilinear on A. Since A is the sum of its minimal left ideals, there exists a minimal left ideal L such that Tr_{U}(s, ·) = Tr_{V} (s, ·) is not identically zero on L. It is known that L is zero on simple A-modules not isomorphic to L (as a left A-module). Therefore there exist submodules U_{L} ≤ U and V_{L} ≤ V isomorphic to L. Since for every a ∈ A we have

χ̃_{U/U_{L},a}(X) = χ̃_{U,a}(X)/χ̃_{L,a}(X) and χ̃_{V/V_{L},a}(X) = χ̃_{V,a}(X)/χ̃_{L,a}(X),

assumption (ii′) is inherited by U/U_{L} and V/V_{L}, and we can use induction in the case when U > U_{L}. □

Combining with the characteristic 0 case we have the following result.

Corollary 3.3.3 Let K be an arbitrary field and B ⊆ A such that B ∪ Rad(A) is a Klinear generating set of A (e.g., B induces a K-basis of A/Rad(A)). For the A-modules U and V the following assertions are equivalent.

(i) U and V have isomorphic composition factors (counted with multiplicities); (ii) χ_{U,a}(X) = χ_{V,a}(X) for every a ∈ A; (iii) χ_{U,a}(X) = χ_{V,a}(X) for every a ∈ B. □

3.4 Algorithms

In this section K is a field of characteristic p > 0. The results of Section 3.1 suggest a method for computing Rad(A) based on solving p^{j}-semilinear equations. The following simple example demonstrates that the problem of computing the radical of finite dimensional algebras over K involves taking p’th roots of elements of K.

Example Let K be a field of characteristic p, α ∈ K, and A = K[X]/(X^{p} − α). It is known that the polynomial X^{p} − α is either irreducible in K[X] or has a unique root α^{\frac{1}{p}} in K. In the former case Rad(A) is zero, while in the latter the inverse image of Rad(A) is the ideal I in A[X] generated by X − α^{\frac{1}{p}}. Using standard polynomial arithmetic over K, from Rad(A) we can compute the unique monic generator X − α^{\frac{1}{p}} of I. □

The following construction, due to Fröhlich and Shepardson [FSh], demonstrates that it is impossible to take pth roots (therefore computing the radicals of finite dimensional algebras) by algorithms using merely the field operations.

Example Let L be an enumerable but not recursive set and f be an enumeration of L without repetition, i.e., a recursive function ℕ → ℕ, such that f is a bijection ℕ → L. Standard examples exist, such as an appropriate encoding of the halting problem of Turing machines, or that of Hilbert’s tenth problem. We set

𝔽_{0} = 𝔽_{q}(Y_{i} | i ∈ ℕ), R = 𝔽_{0}[X_{i} | i ∈ ℕ],

and K = R/I, where I is the ideal of R generated by all of the polynomials X_{i}^{p} −Y_{f(i)} (i ∈ ℕ). It is straightforward to see that K is the extension field of F_{0} obtained by adjoining p’th roots of all Y_{f(i)} (i ∈ ℕ).

An element of K is represented by a fraction of polynomials in (a finite number of) the variables X_{i}, Y_{j}. The field operations as well as equality tests can be carried out using straightforward calculation in subfields generated by the symbols involved in the operands. Obviously, the a variable Y_{i} has a p’th root in K if and only if i ∈ L, therefore membership test in L can be reduced to the problem of deciding whether an element of K has a pth root in K, whence the latter problem is also undecidable. □

To get around this, we assume that K is a finite extension of the subfield

K^{p} = {x^{p}|x ∈ K}

and we can effectively compute a K^{p}-basis of this extension. Note that since α ↦ α^{p} is an isomorphism K ≅ K^{p}, this implies that for every positive integer j, K is finite over K^{p^{j}}, too. More precisely, we have [K : K^{p^{j}}] = [K : K^{p}]^{j}. Also, we can effectively compute a K^{p^{j}}-basis of K.

In the next proposition we summarize the main computational tasks one encounters when trying to apply the characterization given in Theorem 3.1.4 to compute the radical. As we work in a quite general setting, the issue of size (of field elements obtained during the computation) is not addressed here.

Proposition 3.4.1 Let n be a positive integer and suppose that the field K of positive characteristic p is a finite extension of K^{p^{⌊log_{p}(n+1)⌋}}. Let A be an n-dimensional associative algebra over K given by structure constants. Then the problem of finding a basis of the radical of A can be reduced with (n[K : K^{p^{⌊log_{p}(n+1)⌋}}])^{O(1)} arithmetical operations in K to the following computational subtasks. For each j, 0 ≤ j ≤ ⌊log_{p}(n + 1)⌋,

(i) computing a basis of K over the subfield K^{p^{j}}; (ii) computing the value of Tr(p^{j}, x) of at most n(n+1) at most (n+1)-dimensional matrices over K; (iii) computing the coordinates of at most n(n + 1) elements of K in the basis computed in (i) over the subfield K^{p^{j}}. (iv) solving a system of linear equations over the field K^{p^{j}}. A system has at most (n+1)[K : K^{p^{j}}] equations and at most n variables;

(v) computing the p^{j}’th root x^{\frac{1}{p^{j}}} of at most n^{2} elements x ∈ K^{p^{j}}.

Proof We work with the regular representation of the algebra A or the regular representation of the Dorroh extension of A, if A has no identity element. In either case, we obtain a faithful representation of A with dim_{K}A = ν. (ν = n or ν = n + 1.) We identify A with its image at this representation. We use the notation of Section 3.1 omitting the subscript V. Let {a_{1}, …, a_{n}} be a basis of A over K. Let a_{0} := Id_{ν}. Note that we need this element only if A itself has no identity element.

To prove the proposition, we outline a computation for producing a basis over K of A_{j} from a basis of A_{j−1}. Theorem 3.1.4 shows that Rad(A) = A_{⌈log_{p} ν⌉}. For an integer j ≥ 0, suppose that we are already given a basis {b_{1}, …, b_{h}} of A_{j−1} over K. By the p^{j}-semilinearity of Tr(p^{j}, ·), for the coefficients α_{l} of elements ∑ α_{l}b_{l} ∈ A_{j} we have the following system of equations:

∑_{l=1}^{h} α_{l}^{p^{j}}Tr(p^{j}, b_{l}a_{i}) = 0, i = 0, …, n.

We compute first the values Tr(p^{j}, b_{l}a_{i}), and their coordinates t_{jlis} over the subfield K^{p^{j}}. Next we solve the system of linear equations over K^{p^{j}}

∑_{l=1}^{h} β_{l}t_{jlis} = 0, i = 0, …, n, s = 1, …, [K : K^{p^{j}}].

As a solution, we obtain a K^{p^{j}}-basis {(β_{11}, …, β_{1h}), …, (β_{r1}, …, β_{rh})} of the solution space V ⊂ (K^{p^{j}})^{h}. The Frobenius map Φ_{j}: (K)^{h} → (K^{p^{j}})^{h} is an isomorphism, consequently the inverse images of the elements of this basis will form a basis of A_{j} over K. □

We intend to use the algorithm outlined in the proposition for the field K = 𝔽_{q}(X_{1}, …, X_{m}). For the index of the subfield K^{p^{⌊log_{p}(n+1)⌋}} we have

[K : K^{p^{⌊log_{p}(n+1)⌋}}] = (p^{⌊log_{p}(n+1)⌋})^{m} = O(n^{m}).

Also we can efficiently compute the values of the inverse of the Frobenius map. The characteristic polynomial of an n × n matrix a over K can also be computed in time (n + height(a))^{mO(1)}. The only serious problem could be explosure of data sizes. We have to solve about log_{p} n systems of linear equations in an iteration, where the coefficients of the j’th system depend on the solution of the previous system. We need a bound on the height of a basis of the ideals A_{j}. For a step of the iteration, we have the following.

Lemma 3.4.2 Let A be an n-dimensional algebra over the field K = 𝔽_{q}(X_{1}, …, X_{m}). Assume that the structure constants have numerators of height at most Δ and a common denominator in 𝔽_{q}[X_{1}, …, X_{m}]. Assume further that for a 0 ≤ j ≤ ⌊log_{p}n⌋, the ideal A_{j−1} has an integral basis (in the sense that the coordinates of the basis elements of A_{j−1} with respect to the input basis of A are from 𝔽_{q}[X_{1}, …, X_{m}]) of height at most Γ. Then the ideal A_{j} has an integral basis of height at most n(Γ + 2Δ). In particular, if the algebra A is primary, i.e., if A/Rad(A)) is simple, then Rad(A) has an integral basis of height at most 2nΔ.

Proof The endomorphism Φ_{j}: K → K^{p^{j}} induces an automorphism of the finite field 𝔽_{q} and maps X_{i} to Y_{i} = X_{i}^{p^{j}}, therefore

K^{p^{j}} = 𝔽_{q}(Y_{1}, …, Y_{m}) = 𝔽_{q}(X_{1}^{p^{j}}, …, X_{m}^{p^{j}})

and

{X_{1}^{i_{1}} ⋯ X_{m}^{i_{m}} | 0 ≤ i_{1}, …, i_{m} < p^{j}}

is a basis of K over K^{p^{j}}. Let us use the notation of the proof of Proposition 3.4.1. The elements b_{l}a_{i} expressed in terms of a_{i} have a common denominator and numerators of height at most Γ + Δ. We infer a similar statement for the entries of the ν × ν matrices b_{l}a_{i}. The bound on the height of the numerators becomes Γ + 2Δ. It follows that the expressions Tr(p^{j}, (b_{l}a_{i})) have numerators of height at most p^{j}(Γ + 2Δ) and a common denominator. By clearing the denominator we may assume that t_{jils} ∈ 𝔽_{q}[Y_{1}, …, Y_{m}] of degree at most Γ+2Δ in each Y_{r}. Our system of linear equations has rank at most n. This implies that there exists an integral basis of the solution space of degree at most n(Γ+2Δ) (in Y_{1}, …, Y_{m}). By substituting X_{i} in Y_{i} we obtain a basis of the ideal A_{j}. If A/Rad(A) is simple, then A_{j} = A_{j−1} except for at most one j, therefore the height can increase in at most one step. □

Unfortunately, from this lemma immediately we could only obtain a quasi-polynomial n^{c log n}Δ bound on the radical. The next two statements allow us to obtain manageable bounds on the height of the radical. Also, they turn out to be useful later when we consider the decomposition of semisimple algebras. Our argument is essentially a version of the technique of Eberly [Eb1, Eb2, Eb3] based on splitting elements.

Lemma 3.4.3 Let A be an n-dimensional algebra over the field K = 𝔽_{q}(X_{1}, …, X_{m}). Assume that the structure constants are from 𝔽_{q}[X_{1}, …, X_{m}] and their heights are bounded by Δ. Then for any ideal I of A properly containing Rad(A) there exists an ideal I′ having an integral basis of height at most 2(n⌊2log_{q}n⌋ + (n + 1)Δ), such that I′ is contained in I but not contained in Rad(A).

Proof First we explain the construction over an arbitrary (but sufficiently large) field K. We consider the semisimple algebra Ā = A/Rad(A) over K. Let Ī be the image of an ideal I ≠ A under the natural map and let J̄ be the complement ideal of Ī in Ā. Let us examine the right action of the elements of A on Ī and J̄. The resultant of the characteristic polynomials of the right action on Ī resp. J̄ of a generic element ∑_{i=1}^{n} z_{i}a_{i} of A is a not identically zero polynomial in K[z_{1}, …, z_{n}], and its degree in each variable is at most dim_{K} Īdim_{K} J̄ ≤ n^{2}/4. The sparse zeros lemma (cf. [Sch] or Section 5.1 in this work) implies that if the cardinality of a subset L ⊆ K is greater than n^{2}/4 then there exists an element of the form a = ∑_{i=1}^{n} l_{i}a_{i}, all l_{i} ∈ L, such that the characteristic polynomials f resp. g of the right action of a on Ī resp. J̄ are relatively prime. We now substitute a into g. The element g(a) annihilates J̄, but does not annihilate Ī. We conclude that g(a) ∈ I \ Rad(A).

Returning to the situation at hand K = 𝔽_{q}(X_{1}, …, X_{m}), we select L from elements of small height:

L = {h ∈ 𝔽_{q}[X_{1}] | deg h ≤ ⌊2 log_{q} n⌋}

will suffice. The preceding argument demonstrates the existence of an integral element a of height at most ⌊2log_{q}n⌋ with the property g(a) ∈ I \ Rad(A). The characteristic polynomial g of the right action of a on J̄ is a monic polynomial dividing the monic characteristic polynomial with integral coefficients of the right action on A and the heights of the coefficients of the latter polynomial are bounded by n(⌊2log_{q}n⌋ + Δ). We infer that g has also integral coefficients of height at most n(⌊2log_{q}n⌋ + Δ) and we can bound the height of g(a) by 2n(⌊2log_{q}n⌋ + Δ). The ideal I′ generated by g(a) has an integral basis chosen from the elements {a_{i}g(a)a_{j} | i, j = 1, …, n} of height 2(n⌊2log_{q}n⌋ + (n + 1)Δ). □

We can now prove a polynomial bound on the heights of the ideals over the radical:

Proposition 3.4.4 Let A be an n-dimensional algebra over the field K = 𝔽_{q}(X_{1}, …, X_{m}). Assume that the structure constants are integral (i.e., they are from 𝔽_{q}[X_{1}, …, X_{m}]) and their heights are limited by Δ. Then any ideal of A containing Rad(A) has an integral basis of height O(n^{3}(⌊2log_{q}n⌋ + Δ)).

Proof Let I_{1}, …, I_{r} be the minimal elements of the set of the ideals of A containing Rad(A). Let I′_{1}, …, I′_{r} be ideals corresponding to them according to Lemma 3.4.3 with integral bases of height at most

Γ = 2(n⌊2log_{q}n⌋ + (n + 1)Δ).

The minimality of the ideals I_{j} implies that I′_{j} +Rad(A) = I_{j}. Then the structure constants of I′_{j} have a common denominator and numerators of height at most Δ + (n + 1)Γ. (This can be seen by writing up systems of linear equations for the structure constants of the ideals I′_{j}. The coefficients of the variables are of height at most Γ, while for the heights of the inhomogeneous parts – corresponding to products of basis elements of I′_{j} – the bound is 2Γ + Δ.) We have Rad(I′_{j}) = I′_{j} ∩ Rad(A) and Noether’s isomorphism implies that

(∗)  I′_{j}/Rad(I′_{j}) ≅ (I′_{j} + Rad(A))/Rad(A) = I_{j}/Rad(A).

We infer that I′_{j}/Rad(I′_{j}) is a simple algebra and we can apply Lemma 3.4.2. For the height of the radical of I′_{j} we have the bound 2n(Δ + (n + 1)Γ) with respect to the above basis of I′_{j} and the bound Σ = 2n(Δ + (n + 1)Γ) + Γ with respect to the original basis of A. Also infer that

J = Rad(I′_{1}) + … + Rad(I′_{r}) ⊆ Rad(A)

is an ideal of A having an integral basis of height at most Σ. Moreover J ∩ I′_{j} = Rad(I′_{j}) holds for 1 ≤ j ≤ r. Now an application of Noether’s isomorphism theorem and (∗) gives that the algebras (I′_{j} +J)/J are simple. For the ideal I = I′_{1}+…+I′_{r} this entails that I/J is semisimple as a sum of the simple algebras (I′_{1} + J)/J, …, (I′_{r} + J)/J, whence Rad(I) = J. The residue class algebra

A/I = (Rad(A) + I)/I ≅ Rad(A)/(I ∩ Rad(A)

is a radical algebra, therefore if we assume that A has an identity element, then I = A and then the height of Rad(A) is at most Σ. If A has no identity element, then we can compute the radical of A in its Dorroh extension Ã, since Rad(Ã) = Rad(A). The latter relation follows from Ã/A ≅ K. We have obtained that Rad(A) has an integral basis of height O(n^{3}(⌊2log_{q}n⌋ + Δ)). Now the bound stated for an arbitrary ideal over Rad(A) follows from the fact that any such ideal can be obtained as a sum of Rad(A) and some of the ideals I′_{j}. □

We are now in a position to prove the central result of this section, stating that the Jacobson radical of finite dimensional associative algebras over finitely generated function fields of positive characteristic can be computed by a deterministic algorithm which is exponential only in the parameter m.

Theorem 3.4.5 Let K be a finite extension of 𝔽_{q}(X_{1}, …, X_{m}). Let d := [K : 𝔽_{q}(X_{1}, …, X_{m})]. Suppose that A, an n-dimensional algebra over K is given by structure constants of height not exceeding Δ. Suppose further that K is given by structure constants over 𝔽_{q}(X_{1}, …, X_{m}) of height at most Γ. Then there is a deterministic algorithm that outputs a basis of the Jacobson radical of A at the cost of ((n + d + Δ + Γ)^{m} + log q)^{O(1)} bit operations.

Proof We note that the radical (as the set of strongly nilpotent elements) does not change if we consider A as an algebra over a subfield K_{0} of K such that [K : K_{0}] is finite. Since K is a finite extension of 𝔽_{q}(X_{1}, …, X_{m}), we may assume that K = 𝔽_{q}(X_{1}, …, X_{m}). The height of the structure constants over the latter field is bounded by 2Γ + Δ. We use the algorithm outlined in Proposition 3.2. We may assume that the structure constants are integral. After each step, we can correct the basis of the ideal I_{j} to an integral basis of height O((nd)^{3}(⌊2log_{q}(nd)⌋ + 2Γ + Δ)) This can be done by solving (n + d + Δ + Γ)^{O(m)} linear equations over the finite field 𝔽_{q}. □

Corollary 3.4.6 In addition to the assumptions of Theorem 3.6 suppose that m is a constant (e.g., K is a global function field). Then Rad(A) can be computed in deterministic polynomial time.

Proof In this case the bound of Theorem 3.4.5 is a polynomial of the input size. □

Wedderburn decomposition over 𝔽_{q}(X_{1}, …, X_{m})

In this chapter — based on the paper [IRSz], joint work with Lajos Rónyai and Ágnes Szántó — we give an f-algorithm (a deterministic polynomial time reduction to factoring polynomials over the prime field 𝔽_{p}) for decomposing a finite dimensional semisimple algebra over a finite extension K of the field 𝔽_{q}(X_{1}, …, X_{m}). We actually reduce our problem to decomposing algebras over finite fields, and this problem can in turn be solved by the f-algorithm of Friedl and Rónyai [FR]. For large primes the algorithm presented here is an improved analogue of the method of Gianni, Miller and Trager [GMT], which was proposed for decomposition of algebras over ℚ. The main idea is to find central idempotents in a factor modulo an appropriate maximal ideal I, lift them to idempotents modulo a sufficiently large power of I, and then find zero divisors of reasonable height. For small primes we present a deterministic polynomial time algorithm which is an analogue of Berlekamp’s method (cf. [Ber3]) for factoring polynomials over finite fields.

An extremely simple standard idea is reducing the task of computing the simple components of a not necessarily commutative algebra to the decomposition of the center. It is clear, that the center of the algebra is a direct sum of the centers of its simple components and a component is an ideal generated by its center. The center of an algebra can be computed by solving a system of linear equations.

Let us recall some classical material related to idempotents (cf. [Ke], Sections 31 and 32). Recall that an element e in an arbitrary ring A is idempotent if 0 ≠ e = e^{2}. Two idempotents e, f in A are called orthogonal if ef = fe = 0. The sum of pairwise orthogonal idempotents is again an idempotent. An idempotent e in A is called primitive if there exists no idempotent f ≠ e with ef = f. This in turn is equivalent to that e is not a sum of two orthogonal idempotents. In the important case where A is an Artinian ring, every idempotent is a sum of finitely many orthogonal primitive idempotents.

Assume that A is a commutative Artinian ring. Then there are finitely many idempotents in A, the primitive idempotents are pairwise orthogonal, and every idempotent can be uniquely written as a sum of primitive idempotents. Let J denote the Jacobson radical of A. Then J is nilpotent. Let N be a positive integer such that J^{N} = 0. Two idempotents in A are equal or orthogonal iff modulo J they are equal or orthogonal, respectively. An idempotent e is primitive iff it is a primitive idempotent modulo J. Also, if e_{1} + J is an idempotent in A/J then there is a unique idempotent e in e_{1} + J. The following iterative procedure (cf. [Re], Section 6c) is available for finding the lift e. Define the sequence e_{1}, e_{2}, … by the recurrence formula

e_{i+1} = 3e_{i}^{2} − 2e_{i}^{3}.

Then e = e_{⌈log_{2} N⌉}.

Assume that A is a commutative semisimple finite dimensional K-algebra. Then the primitive idempotents of A are the identity elements of the minimal ideals of A. Therefore (up to solving systems of linear equations over K) it is equivalent to find the primitive idempotents and the minimal ideals of A. Also, if K_{0} is any subfield of A then the K_{0}- subalgebra of A generated by the (primitive) idempotents is the sum of the K_{0}-subalgebras of the simple components of A generated by the identity elements of the simple components. If K is of positive characteristic p, then with K_{0} = 𝔽_{p} this subalgebra is in fact the subring B generated by the (primitive) idempotents and can be characterized as

B = {x ∈ A|x^{p} = x}.

Since the map x ↦ x^{p} is 𝔽_{p}-linear, this leads to an efficient way to compute B in the case when K is a finite field given in the dense representation over the prime field 𝔽_{p}: One computes an 𝔽_{p}-basis a_{1}, …, a_{n} of A, then the elements a_{1}^{p} − a_{1}, …, a_{n}^{p} − a_{n} via fast exponentiation (based on repeated squaring), and finally B as the solution space (in the coordinates x_{1}, …, x_{n} w.r.t. the basis a_{1}, …, a_{n}) of the system

∑ x_{i}(a_{i}^{p} − a_{i}) = 0

of linear equations over 𝔽_{p}. Combining with the method of [FR], essentially this is Berlekamp’s reduction of the problem of factoring polynomials over a finite field to factor polynomials that split into linear factors over 𝔽_{p}.

If we attempt to generalize the method above to the case when K = 𝔽_{q}(X_{1}, …, X_{m}), then, we need first to compute an 𝔽_{p}-subspace B′ of A of small dimension containing B.

This can be done based on Lemma 4.1.2. Then we would need the powers a_{i}^{p} for an 𝔽_{p}- basis a_{1}, a_{2}, … of B′. Unfortunately, these elements can be efficiently computed only if p is small. If p is large, then the size of a_{i}^{p} (and the intermediate powers occurring in repeated squaring) may explode.

We treat the case of large characteristic in a different way. Lemma 4.1.2 makes possible to find a maximal ideal I of 𝔽_{q}[X_{1}, …, X_{m}] such that we can efficiently compute modulo powers of I in an appropriate subring of A containing the idempotents. (In essence, we imitate computations in the maximal order of A over the localization 𝔽_{q}[X_{1}, …, X_{m}]_{I}.) For an appropriately chosen exponent h, we compute the primitive idempotents modulo I^{h} (from the primitive idempotents modulo I via the lifting method described above), and use them to find zero divisors in A.

4.1 Algorithms

Let A be a semisimple algebra over the field 𝔽_{q}(X_{1}, …, X_{m}). The results of Section 3.4 can be applied to obtain polynomial bounds on the height of the simple components of a semisimple algebra. Lemma 3.4.3 gives immediately the next statement.

Corollary 4.1.1 Let A be an n-dimensional semisimple algebra over the field K = 𝔽_{q}(X_{1}, …, X_{m}). Assume that the structure constants are from 𝔽_{q}[X_{1}, …, X_{m}] and their height is limited by Δ. Then any ideal I of A has an integral basis of height at most 2(n⌊2log_{q}n⌋ + (n + 1)Δ). □

If we use a successive decomposition of the algebra, then after computing an ideal I ⊲A we can compute a basis of I of height at most

2(n⌊2log_{q}n⌋ + (n + 1)Δ)

by solving a system of linear equations (of moderate size). This correction step keeps the heights always under the bound.

The task of computing the Wedderburn decomposition is equivalent (up to polynomial time reductions) to the problem of finding a zero divisor in a commutative semisimple algebra A: If a is a zero divisor in A, then A is a direct sum of the ideal generated by a and the annihilator

ann(a) = {x ∈ A | xa = 0}

of a.

As mentioned in the introductory part, our task is equivalent to decomposing the center of A, therefore we may assume that A is a commutative semisimple algebra over K = 𝔽_{q}(X_{1}, …, X_{m}). We can also make another important simplification. It will be convenient to assume that the algebra is separable over K, i.e., the simple components of A are all finite separable extensions of K. This can be achieved as follows. Let j := ⌊log_{p} n⌋, where n is the dimension of A over K. Let us consider the Frobenius map defined on A by

Φ_{j}: x ↦ x^{p^{j}}.

It is clear, that Φ_{j} is a ring-endomorphism of A which extends the Frobenius endomorphisms of the simple components. It is also known (see [Bas], Propositions 2.4.9 and 2.5.13), that the image of each component will be contained in a separable extension of K. Thus, if we take the K-algebra generated by p^{j}th power of all elements of a basis of the algebra, then we obtain a separable subalgebra. On the other hand, the ideal structure is preserved: all the idempotents are left fixed. Since p^{j} ≤ n, the p^{j}th powers of the basis elements are of polynomial size and can be computed in polynomial time and we can assume that our algebra is separable over K.

We use the bilinear trace form of the algebra (see also Chapter 6). It is a symmetric F -bilinear function defined by

tr(x, y) := Tr(xy)

where Tr is the trace of the regular representation. If {a_{1}, …, a_{n}} is a basis of the algebra A over K, then the discriminant of the algebra corresponding to that basis is the determinant

disc_{{a_{1},...,a_{n}}}A := det (tr(a_{i}, a_{j}))_{i,j=1}^{n}.

It is well-known (see [Bas], pp. 166–168), that for any commutative separable algebra the bilinear trace form is nondegenerate, i.e., the discriminant is nonzero.

Since the height of the terms Tr(a_{i}a_{j}) is bounded by 2Δ, we have a bound 2nΔ on the height of the discriminant, where Δ is a bound on the heights of the structure constants. This observation shows that the discriminant can be computed by Chinese Remaindering.

The following lemma gives an estimate of the height of idempotents in a commutative separable algebra. A common multiple of the denominators of the idempotents is also exhibited. The proof is independent from the proof of Corollary 4.1.1.

Lemma 4.1.2 Let A be an n-dimensional commutative separable algebra over the field K = 𝔽_{q}(X_{1}, …, X_{m}). Assume that the structure constants with respect to the basis {a_{1}, …, a_{n}} are from 𝔽_{q}[X_{1}, …, X_{m}] and their heights are limited by Δ. Then any idempotent e ∈ A lies in the 𝔽_{q}-space

\{∑_{i=1}^{n} \frac{α_{i}}{D} a_{i} | α_{i} ∈ 𝔽_{q}[X_{1}, …, X_{m}], deg_{X_{j}}α_{i} ≤ (3n − 2)Δ, 1 ≤ j ≤ m\},

where D is the discriminant disc_{{a_{1},...,a_{n}}}A.

Proof Let e be a nontrivial idempotent in A, I = eA the ideal generated by e and J = ann(e) be the annihilator of e. Then for an arbitrary a ∈ A, the left (or, equivalently, the right) action of ea on I coincides with the action of a on I, while the action of ea on J is zero. The integrality assumption on the structure constants implies that the characteristic roots of a_{j} are integral elements over 𝔽_{q}[X_{1}, …, X_{m}], hence the characteristic roots of ea_{j} are also integral over 𝔽_{q}[X_{1}, …, X_{m}]. This implies that Tr(ea_{j}) ∈ 𝔽_{q}[X_{1}, …, X_{m}] for 1 ≤ j ≤ n and the characteristic polynomial f of the action of ea_{j} on I divides the characteristic polynomial g of the action of a_{j} on A. Let Tr_{I}(d) denote the trace of the action on I of an element d ∈ I. Clearly we have Tr_{I}(d) = Tr(d) for every d ∈ I, in particular Tr_{I}(ea_{j}) = Tr(ea_{j}) holds. We infer that −Tr(ea_{j}) is a coefficient of f, therefore the height of Tr(ea_{j}) is at most nΔ, because this quantity is a bound on the height of the coefficients of g. On the other hand, e = ∑_{i=1}^{n} β_{i}a_{i} is the unique solution of the following system of linear equations:

∑_{i=1}^{n} β_{i}Tr(a_{i}a_{j}) = Tr(ea_{j}), j = 1, …, n.

Cramer’s rule implies the assertion. □

Let M denote the free R = 𝔽_{q}[X_{1}, …, X_{m}]-submodule of A with basis \frac{1}{D}a_{1}, …, \frac{1}{D}a_{n}. We perform computations in M and work with the height of elements of M with respect to the R-basis above, i.e., for u = ∑ α_{i} \frac{1}{D}a_{i},

height(u) = max{deg_{X_{j}}α_{i}|i = 1, …, n, j = 1, …, m}.

Obviously, for u, v ∈ M, α ∈ 𝔽_{q}[X_{1}, …, X_{m}], we have

height(αu) ≤ height(α) + height(u),

height(u + v) ≤ max{height(u), height(v)},

Duv ∈ M, and height(Duv) ≤ Δ + height(u) + height(v).

We can settle now the case when p is small in comparison to the other parameters of the input. More precisely let us assume that p ≤ 2nΔ. In this case we can reduce the problem of finding the Wedderburn decomposition of A to the problem of factoring polynomials over finite fields in a way similar to Berlekamp’s reduction [Ber3]. Let B denote the direct sum of the prime fields in the simple components of our (commutative separable) algebra A. Clearly B is an 𝔽_{p}-algebra consisting of the fixed points of the Frobenius endomorphism x ↦ x^{p} of the K-algebra A. Moreover B is the 𝔽_{p}-algebra generated by the idempotents of A. From Lemma 4.1.2 it follows that every element b ∈ B can be written as a sum b = β_{1}a_{1} + ⋯ + β_{n}a_{n}, where β_{i} = α_{i}/D for some α_{i} ∈ 𝔽_{q}[X_{1}, …, X_{m}] and deg_{X_{j}}α_{i} ≤ (3n − 2)Δ. We infer that a basis over 𝔽_{p} of B can be obtained by solving a system of at most (3pnΔ)^{m} log_{p} q linear equations in (3nΔ)^{m} log_{p} q variables over 𝔽_{p}. The coefficients of the equations can be obtained by fast exponentiation of the matrices of structure constants. Once we have a basis of B, we can readily obtain structure constants over 𝔽_{p} and then compute the primitive idempotents of B (and therefore of A) with the method of Friedl and Rónyai [FR, Ró2]. This completes the algorithm in the case p ≤ 2nΔ.

For a “large” prime p we follow the method of Gianni, Miller and Trager [GMT]. We shall, however, propose an improvement in the final step of constructing zero divisors from the lifted idempotents. As usual, for f ∈ 𝔽_{q}[X_{1}, …, X_{m}] and c_{i} ∈ 𝔽_{q} we denote by f(c_{1}, …, c_{m}) the element of 𝔽_{q} obtained after substituting c_{i} for X_{i}.

Let us assume that q > 2nΔ. We can find, using at most m(2nΔ + 1) tries, elements c_{1}, …, c_{m} ∈ 𝔽_{q} such that D(c_{1}, …, c_{m}) ≠ 0. Indeed, we find first a substitution X_{1} = c_{1} from a set of 𝔽_{q} of cardinality 2nΔ + 1 such that D(c_{1}, X_{2}, … X_{m}) ≢ 0. Then we repeat this for X_{2}, …, X_{m}.

Let I be the ideal of R generated by the polynomials X_{1} − c_{1}, …, X_{m} − c_{m}. Then we have R/I ≅ 𝔽_{q} and for every positive integer h, R/I^{h} is an F_{q}-algebra of dimension at most mh^{m}. (After a change of variables Y_{i} = X_{i} − c_{i}, we may assume that c_{i} = 0, for i = 1, …, m. Then reducing a polynomial in R modulo I^{h} is equivalent to taking only the monomials of total degree less than h.) We also have that, for every h, the R/I^{h}-module M/I^{h}M can be considered as an R/I^{h} algebra by taking multiplication modulo I^{h}. To be more precise, the structure constants with respect to the basis \frac{1}{D}a_{1}, …, \frac{1}{D}a_{n} will be the structure constants of the algebra A with respect to the basis a_{1}, …, a_{n} taken modulo I^{h} and multiplied by the inverse of D modulo I^{h}, which can be computed as follows: we write D as D = c + f where c ∈ 𝔽_{q} and f ∈ I. Then 1 = (\frac{1}{c}D − \frac{1}{c}f)^{h} and hence we have to divide (\frac{1}{c}D − \frac{1}{c}f)^{h} − (\frac{1}{c}f)^{h} by D. From this, we see that elements of M/I^{h}M can be represented by O(h^{m}n log_{q}) bits and the R/I^{h}-algebra operations on M can be carried out in time (h^{m} + n + log_{q})^{O(1)}. In fact, M/I^{h}M is an 𝔽_{q}-algebra of dimension ndim_{𝔽_{q}}I^{h} with identity element 1_{A} + I^{h}M.

If 0 ≠ e is an idempotent of A then e ∈ M by Lemma 4.1.2. The definition of the multiplication gives immediately that ē^{2} = ē, where ē denotes the image of e in M/I^{h}M. Also, e^{2} = e ≠ 0 implies that ē ≠ 0, for otherwise we would have the contradictory e ∈ I^{j}M for every j ≥ h.

The case h = 1 deserves special attention. M/IM is an n-dimensional 𝔽_{q}-algebra. Since this algebra admits a nondegenerate bilinear trace form, it must be semisimple. (See [Di], and for more general results Chapter 3 in this dissertation.) It follows that for every integer h ≥ 1, IM + I^{h}M is the Jacobson radical of the finite ring M/I^{h}M. Using this fact, we can find the idempotents modulo I^{h} as follows. We compute the Wedderburn decomposition and hence the primitive idempotents of the 𝔽_{q}-algebra M/IM with the help of the f-algorithm of Friedl and Rónyai [FR, Ró2]. To be more specific, we obtain elements f_{1}, …, f_{r} ∈ M, such that f_{1} + IM, …, f_{r} + IM are the primitive idempotents of the ring M/IM. Then we can lift these primitive idempotents to primitive idempotents of M/I^{h}M by the classical method described in the introductory part in time ((heightA+h)^{m} log q)^{O(1)}. We obtain elements e_{1}, …, e_{r} ∈ M, that are reduced modulo I^{h}, i.e., with coordinates of total degree less than h, such that e_{1} + I^{h}M, …, e_{r} + I^{h}M are the primitive idempotents in the ring M/I^{h}M.

An idempotent of A in M is also idempotent modulo I^{h}, whence it is a sum of some primitive idempotents of M/I^{h}M. If there are no nontrivial idempotents modulo I^{h}, i.e., M/IM is simple, we can stop, our algebra is simple. On the other hand, if h ≥ (3n−2)Δ, then every idempotent e ∈ M can be obtained as a sum of a subset of {e_{1}, …, e_{r}}.

Unfortunately, it can well happen that there are more idempotents in M/I^{h}M than in A and then we should have to examine exponentially many sums as in [GMT]. The trick below helps. Note that an analogous method (using LLL basis reduction) could also be applied in the situation of [GMT].

If there are nontrivial idempotents in M, then there is one, say e, which is a sum of a subset of e_{2}, …, e_{n}. From Lemma 4.1.2 we infer that the 𝔽_{q}-subspace M_{1} of M generated by e_{2}, …, e_{n} contains an element of height at most (3n − 2)Δ. On the other hand, we claim that if h is large enough (actually, h > m(3n^{2} − n − 1)Δ), then a nonzero element of M_{1} of height at most (3n − 2)Δ is in fact a zero divisor in A. Indeed, assume that h > m(3n^{2} − n − 1)Δ and let

0 ≠ u = ∑_{i=2}^{r} γ_{i}e_{i} ∈ M_{1}

with γ_{2} …, γ_{r} ∈ 𝔽_{q} and height(u) ≤ (3n − 2)Δ. Let ū denote the residue class u + I^{h}M of u modulo I^{h}M. Let β_{1}, …, β_{t} be an enumeration of the distinct nonzero elements from γ_{2}, …, γ_{r}. It is straightforward to see that in the 𝔽_{q}-algebra M/I^{h}M,

ū ∏_{i=1}^{t}(ū − β_{i}1) = 0, but ∏_{i=1}^{t}(ū − β_{i}1) ≠ 0.

Using the definition of multiplication in M/I^{h}M we obtain

D^{t}u ∏_{i=1}^{t}(u − 1_{A}) ∈ I^{h}M, but ∏_{i=1}^{t}(u − 1_{A}) ≠ 0.

Since 1_{A} is also an idempotent, we have height(u − β_{i}1_{A}) ≤ (3n − 2)Δ, whence

height(D^{t}u ∏_{i=1}^{t}(u − β_{i}1_{A})) ≤ tΔ + height(u) + ∑_{i=1}^{t} height(u − β_{i}1_{A}) ≤
tΔ + (t + 1)(3n − 2)Δ ≤ (3n^{2} − n − 1)Δ.

From the fact that I^{h}M does not contain elements of total degree less than h > m(3n^{2} − n − 1)Δ, we infer

u ∏_{i=1}^{t}(u − 1_{A}) = 0,

i.e., u is a zero divisor in A.

As a conclusion of the preceding argument, if we can find an element u ≠ 0 of total degree not greater than m(3n − 2)Δ in the 𝔽_{q}-space M_{1} generated by the reduced lifted idempotents e_{2}, …, e_{n}, then we have a zero divisor in the algebra A. An element u with these properties can be found (if exists) by solving a system of linear equation over 𝔽_{q}. If there is no nonzero solution, then we conclude that A is simple. If we find a solution u, then we can split the algebra to the proper ideal Au and to its complement.

An iteration of this method gives the minimal ideals of A in at most n rounds. Note that we do not need to recompute the lifted idempotents for the ideals. This finishes the description of our f-algorithm for the case K = 𝔽_{q}(X_{1}, …, X_{m}). The overall cost of the method is ((n + Δ)^{m} + log q)^{O(1)} bit operations. We can easily extend this result to the case when K is a finite extension of 𝔽_{q}(X_{1}, …, X_{m}). We consider A as an algebra over 𝔽_{q}(X_{1}, …, X_{m}). This change does not affect the set of the central primitive idempotents. Also, structure constants over A can be computed efficiently. We have the following.

Theorem 4.1.3 Assume that A is an n-dimensional semisimple algebra over a finite extension K of the function field 𝔽_{q}(X_{1}, …, X_{m}) of degree d = [K : 𝔽_{q}(X_{1}, …, X_{m})]. The algebra is given by structure constants of height (maximum degree in each variable) limited by Δ. Suppose further that K is given by structure constants over 𝔽_{q}(X_{1}, …, X_{m}) of height at most Γ. Then there is an f-algorithm that computes (bases of) the minimal ideals of A using ((n + d + Δ + Γ)^{m} + log q)^{O(1)} bit operations. □

Using the fact that we can factor a polynomial f(X) ∈ 𝔽_{p}[X] in randomized polynomial time (cf. Berlekamp [Ber3]), we obtain the following result.

Corollary 4.1.4 Under the assumptions of Theorem 4.1.3, the Wedderburn decomposition of A can be computed in Las Vegas time ((n + d + Δ + Γ)^{m} + log q)^{O(1)}. □

Corollary 4.1.5 In addition to the assumptions of Theorem 4.1.3 suppose that m is a constant, e.g., K is a global function field. Then the Wedderburn decomposition of A can be computed by a polynomial time f-algorithm or a polynomial time Las Vegas algorithm. □

We can make a further improvement to obtain a deterministic algorithm for computing B, the subring generated by the idempotents of A.

We can compute the 𝔽_{p}-subspace L of M generated by e_{1}, …, e_{r} without knowing e_{1}, …, e_{r} explicitly as follows. Since R/I^{h} is a finite dimensional 𝔽_{p}-algebra, the R/I^{h}- algebra M/I^{h}M is a finite dimensional 𝔽_{p}-algebra as well. Let L̄ denote the image of L at the natural homomorphism M → M/I^{h}M. Observe that

L̄ = {x ∈ M/I^{h}M |x^{p} = x}.

First we compute d_{1}, …, d_{r} ∈ M, such that d_{1} + IM, …, d_{r} + IM is a basis of {x ∈ M/IM |x^{p} = x}. This can be done in polynomial time via solving a system of linear equations over 𝔽_{p}. From the fact Rad(M/I^{h}M) = IM + I^{h}M we see that with l = ⌈log_{p} h⌉, the system d_{1}^{p^{l}} + I^{h}M, …, d_{r}^{p^{l}} + I^{h}M forms an 𝔽_{p}-basis of L̄. We can compute d_{i}^{p^{l}} modulo I^{h} using fast exponentiation in M/I^{h}M. This gives a system b_{1}, …, b_{r} of r elements of M with coordinates of total degree less than h, that is an 𝔽_{p} basis L. We prove that, if h is large enough, then B coincides with the 𝔽_{p}-subspace of L consisting of the elements of “small” height.

We set

B′ = {u ∈ L|height(u) ≤ (3n − 2)Δ}.

Obviously, B′ can computed from L in time (h^{m} + n + log q)^{O(1)} as the solution space of a system of homogeneous linear equations over 𝔽_{p}. By Lemma 4.1.2 for every h we have B ⊆ B′. We show that under the assumption h > m(3n^{2} − n − 1)Δ, B′ ⊆ B also holds. Let u ∈ B′. Then there exist β_{1}, …, β_{r} ∈ 𝔽_{p} such that u = ∑ β_{i}e_{i}. It is straightforward to see that with ū = u + I^{h}M we have ∏_{i=1}^{r}(ū − β_{i}1) = 0 in the ring M/I^{h}M, whence

D^{r−1} ∏_{i=1}^{r}(u − β_{i}1_{A}) ∈ I^{h}M.

Observe that for every i = 1, …, r, (since 1_{A} ∈ B ⊆ B′) we have u − β_{i}1_{A} ∈ B′, whence

height(D^{r−1} ∏_{i=1}^{r}(u − β_{i}1_{A})) ≤ (r − 1)Δ + ∑_{i=1}^{r} height(u − β_{i}1_{A}) ≤

(r − 1)Δ + r(3n − 2)Δ ≤ (3n^{2} − n − 1)Δ.

Since I^{h}M does not contain nonzero elements of total degree less than h, we have

∏_{i=1}^{r}(u − β_{i}1_{A}) = 0.

But then the roots of the minimal polynomial of u are all in 𝔽_{p}, whence u ∈ B. We have proved the following.

Theorem 4.1.6 Assume that A is an n-dimensional semisimple algebra over a finite extension K of the function field 𝔽_{q}(X_{1}, …, X_{m}) of degree d = [K : 𝔽_{q}(X_{1}, …, X_{m})] given by structure constants of height (maximum degree in each variable) limited by Δ. Suppose further that K is given by structure constants over 𝔽_{q}(X_{1}, …, X_{m}) of height at most Γ. Then there is a deterministic algorithm running in time ((n + d + Δ + Γ)^{m} + log q)^{O(1)} that computes the 𝔽_{p}-subalgebra B generated by the central idempotents of A. □

Cartan subalgebras

This chapter is based on the paper [GIR], joint work with Willem A. de Graaf and Lajos Rónyai. We consider the algorithmic problem of computing Cartan subalgebras in Lie algebras over finite fields and global fields. We present a deterministic polynomial time algorithm for the case when the ground field K is sufficiently large. Our method is based on a solution of a linear algebra problem: the task of finding a locally regular element in a subspace of linear transformations. Also, we give a polynomial time algorithm for restricted Lie algebras over arbitrary finite fields. Both methods require an auxiliary procedure for finding non-nilpotent elements in subalgebras. This problem is also treated.

Throughout the chapter K denotes a field and L a finite dimensional Lie algebra over K; we write n = dim_{K}L. For the basic definitions and results on Lie algebras the reader is referred to [Hum] and [Jac]. A subalgebra H ≤ L is a Cartan subalgebra of L if H is nilpotent and equals its normalizer: N_{L}(H) = H. Via decompositions into root spaces, Cartan subalgebras proved to be extremely useful in exploring the structure of Lie algebras.

The main result of this chapter (in Section 5.4) is a deterministic polynomial time algorithm for computing Cartan subalgebras in the following two cases:

1. K is a global field or a finite field with |K| > dim_{K}L.

2. K is an arbitrary finite field and L is a restricted Lie algebra.

We point out, that if |K| ≫ dim_{K}L, then a very efficient randomized method is also available.

In the case |K| > dim_{K}L we consider a much more general problem, which, we believe, is interesting on its own right. Let V denote a linear space over the field K, dim_{K}V = n. Let End_{K}V denote the set of K-linear transformations (K-endomorphisms) of V. For an endomorphism a ∈ End_{K}V we denote by V_{0}(a) the Fitting null component of a on V:

V_{0}(a) := {v ∈ V; a^{m}v = 0 for some positive integer m}.

It is immediate that V_{0}(a) is a subspace of V, in fact, it is the largest subspace of V on which a acts as a nilpotent endomorphism.

Let U ≤ V be a subspace of V and D ≤ End_{K}V be a K-subspace of End_{K}V. We denote by N_{D}(U) the subspace of D leaving U invariant:

N_{D}(U) := {a ∈ D| aU ⊆ U}.

An element a ∈ D is locally regular (in D) if every element of N_{D}(V_{0}(a)) acts as a nilpotent endomorphism on V_{0}(a). We give a deterministic procedure for finding a locally regular element in a given D ≤ End_{K}V, provided that |K| > dim_{K}V (Section 5.3). The procedure runs in polynomial time, if we can efficiently find non-nilpotent transformations in subspaces of form N_{D}(V_{0}(a)), where a ∈ D. The algorithm for locally regular elements is applicable to Lie algebras via the adjoint representation. It turns out that V_{0}(ad_{L}a) is a Cartan subalgebra of L, if ad_{L}a is a locally regular element of ad(L).

Our approach requires a solution of an important subtask: for a given subalgebra N ≤ L find an element a ∈ N such that ad_{N}a is not a nilpotent map. Polynomial time algorithms for this problem are considered in Section 5.2.

If K is infinite, then, in addition to the number of arithmetical operations, we have to bound the size of the numbers we work with. This will be done with the aid of the Reduction Lemma (Section 5.1), which allows us to keep the coefficients of the elements small during the computation.

In Section 5.5 we present applications to semisimple associative algebras. In the literature several polynomial time randomized algorithms working in semisimple algebras are known where randomization occurs only at the point of finding so-called splitting elements. Roughly speaking, the minimal polynomial of a splitting element has as many distinct roots (in the algebraic closure of the ground field) as possible. Our methods give a deterministic polynomial time algorithm for finding splitting elements in separable associative algebras over finite fields or global fields, generalizing a result of Rónyai [Ró5].

5.1 The Sparse Zeros Lemma and a reduction procedure

In symbolic computation it is a frequent task to find elements α_{1}, α_{2}, … α_{n} ∈ K efficiently such that f(α_{1}, … α_{n}) ≠ 0, where f ∈ K[X_{1}, …, X_{n}] is a nonzero polynomial. The following statement by J. T. Schwartz [Sch] and R. E. Zippel [Z] provides a powerful randomized solution.

Sparse Zeros Lemma. Let f(X_{1}, X_{2}, …, X_{n}) ∈ K[X_{1}, X_{2}, …, X_{n}] be a polynomial, deg f = d. Let Ω be a subset of K, |Ω| = N. Then the number of vectors u = (α_{1}, …, α_{n}) ∈ Ω^{n} for which f(u) = 0 is at most dN^{n−1}.

Thus, if we select a random vector u ∈ Ω^{n} with uniform distribution, then the probability of f(u) being 0 is at most d/N. By working with a sufficiently large set Ω, we can make this probability arbitrarily small.

The Sparse Zeros lemma implies that if N > d, then there is an u ∈ Ω^{n} for which f(u) ≠ 0. To our knowledge, there is no efficient deterministic algorithm for finding such vectors in general. We have however the following.

Lemma 5.1.1 (Reduction Lemma) Suppose that we have a polynomial f ∈ K[X_{1}, X_{2}, …, X_{n}], deg f = d and a subset Ω ⊂ K with d < |Ω| = N. Suppose further that we are given a substitution (β_{1}, β_{2}, …, β_{n}) ∈ K^{n} with f(β_{1}, β_{2}, …, β_{n}) ≠ 0. Then we can find a v ∈ Ω^{n} for which f(v) ≠ 0, at the expense of at most n(d + 1) tests of the form

f(u) =^{?} 0 on vectors u ∈ (Ω ∪ {β_{1}, β_{2}, …, β_{n}})^{n}.

Proof Starting with v^{(0)} = (β_{1}, β_{2}, …, β_{n}), we construct a sequence of vectors v^{(1)}, …, v^{(n)}, where v^{(i)} is of the form v^{(i)} = (α_{1}, … α_{i}, β_{i+1}, …, β_{n}), α_{1}, …, α_{n} ∈ Ω, and f(v^{(i)}) ≠ 0 for 0 ≤ i ≤ n. In particular v = v^{(n)} will have the required properties. We describe how to obtain v^{(i)} from v^{(i−1)}. Consider the univariate polynomial g_{i}(X) = f(α_{1}, … α_{i−1}, X, β_{i+1}, …, β_{n}) ∈ K[X]. We have deg g_{i} ≤ d and g_{i} is not identically zero because g_{i}(β_{i}) = f(v^{(i−1)}) ≠ 0 by assumption. These imply that among arbitrarily selected d + 1 elements of Ω there must be one, which we denote by α_{i}, for which g_{i}(α_{i}) ≠ 0. We can therefore construct v^{(i)} from v^{(i−1)} with at most d + 1 tests and the statement follows. □

The Reduction Lemma is a tool to control the sizes of coefficients in the algorithms. (In subsequent applications to cases charK = 0, Ω will be a set of small integers. Similarly, for a global function field K, Ω will be a set of polynomials of small degree.)

Suppose that we are given a subspace D ≤ End_{K}V of linear transformations of V by a basis a_{1}, …, a_{l}. Suppose further that we have an element a = γ_{1}a_{1} + ⋯ + γ_{l}a_{l} ∈ D such that dim_{K}V_{0}(a) = r. Let Ω be a subset of K, |Ω| = n+1, where n = dim_{K}V. With the aid of the Reduction Lemma we can construct an element b = α_{1}a_{1} +⋯+α_{l}a_{l} with α_{i} ∈ Ω and dim_{K}V_{0}(b) ≤ r. To see this, consider a “generic element” A = X_{1}a_{1} + X_{2}a_{2} + ⋯ + X_{l}a_{l}, where the X_{j} are indeterminates over K. Let f(Y) ∈ K(X_{1}, …, X_{l})[Y] stand for the characteristic polynomial of the linear transformation A of V ⊗_{K} K(X_{1}, …, X_{l}) as a linear space over K(X_{1}, …, X_{l}). We have

f(Y) = det (Y I_{n} − A) = Y^{n} + f_{1}Y^{n−1} + ⋯ + f_{n−1}Y + f_{n},

where f_{i} ∈ K[X_{1}, X_{2}, …, X_{l}]. Moreover f_{i} is a homogeneous polynomial and if f_{i} ≠ 0, then deg f_{i} = i.

It is also clear that the characteristic polynomial of an element c = δ_{1}a_{1} +⋯+δ_{l}a_{l} ∈ D over K is obtained by making the substitutions x_{i} = δ_{i}. The statement below is immediate.

Proposition 5.1.2 Let c = δ_{1}a_{1} + ⋯ + δ_{l}a_{l} be an element of End_{K}V with characteristic polynomial h(y) ∈ K[y]. The following are equivalent:

(a) dim_{K}V_{0}(c) = s.

(b) s is the largest integer such that y^{s} divides h(y).

(c) f_{n−s}(δ_{1}, δ_{2}, …, δ_{l}) ≠ 0, and f_{j}(δ_{1}, δ_{2}, …, δ_{l}) = 0 for n − s < j ≤ n.

(d) s = n − rank(c^{n}). □

We can apply the Reduction Lemma. With at most (n − r + 1)l ≤ (n + 1)n tests involving values from the set Ω ∪ {γ_{1}, …, γ_{l}} we find an element b = α_{1}a_{1} + ⋯ + α_{l}a_{l} such that α_{i} ∈ Ω and f_{n−r}(α_{1}, α_{2}, …, α_{l}) ≠ 0, and hence dim_{K}V_{0}(b) ≤ r. A test can be done by computing and inspecting the characteristic polynomial of the endomorphism in question. Alternatively, by Proposition 5.1.2 (d) one can test an element c by computing the rank of c^{n}. We have the following.

Corollary 5.1.3 Let K be a global field. In case K is a number field, we set Ω = {1, 2, …, n + 1}. In case K is a finite extension of 𝔽_{q}(X), we assume that Ω consists of polynomials of degree at most ⌈log_{q}(n + 2)⌉. Suppose that we are given a subspace D ≤ End_{K}V of linear transformations of V (dim_{K}V = n) by a basis a_{1}, …, a_{l}. Suppose also that we have an element a = γ_{1}a_{1} + ⋯ + γ_{l}a_{l} ∈ D such that dim_{K}V_{0}(a) = r. Then we can find an element b = α_{1}a_{1} + ⋯ + α_{l}a_{l} with α_{i} ∈ Ω and dim_{K}V_{0}(b) ≤ r in deterministic polynomial time.

Proof It suffices to observe that the tests required by the preceding method can all be performed in time polynomial in the sizes of the matrices a_{i} and the coefficients γ_{j}. □

5.2 Non-nilpotent elements in Lie algebras

Suppose that we are given a Lie algebra L by structure constants over the field K. Let a_{1}, a_{2}, … a_{n} be the input basis of L. Our objective is to find an element a ∈ L such that ad_{L}a is not a nilpotent endomorphism of L, provided that L is not a nilpotent algebra.

The first method we describe is an iterative algorithm. Suppose that we have a subset B_{r} = {b_{1}, b_{2}, …, b_{r}}, (r < n), of linearly independent elements of L such that the linear space KB_{r} generated by B_{r} over K is a (Lie) subalgebra of L which acts nilpotently on L. The latter condition means that ad_{L}c_{1}ad_{L}c_{2} ⋯ ad_{L}c_{n} = 0 (as a product of linear transformations of the K-space L) whenever c_{i} ∈ KB_{r}. The following sub-algorithm either produces a larger such set B_{r+1}, or finds a non-nilpotent element of L.

1. Find an element b ∈ L \ KB_{r} such that [b, B_{r}] ⊆ KB_{r}. This can be done either by solving a system of linear equations, or by letting b be first an element of the input basis which is in L \ KB_{r} and then repeatedly replacing b by [b, b_{i}] if [b, b_{i}] ∉ KB_{r}. As KB_{r} acts nilpotently on L, we need no more than n−1 such replacement steps.

2. Check if ad_{L}b is a nilpotent endomorphism of L. If not, then output b as a non-nilpotent element, otherwise set b_{r+1} = b and B_{r+1} = {b_{1}, b_{2}, …, b_{r+1}}.

We show that if b is ad-nilpotent upon termination, then B_{r+1} is again an independent set and KB_{r+1} is a subalgebra acting nilpotently on L. The first claim is immediate, as b ∉ KB_{r} by construction. As for the second, we have [B_{r+1}, B_{r+1}] ⊆ [b, B_{r}] ∪ [B_{r}, b] ∪ [B_{r}, B_{r}] ⊆ KB_{r}, giving that B_{r+1} is a subalgebra. In fact, we have obtained the slightly stronger fact that the subset U = ad_{L}({b} ∪ KB_{r}) ≤ End_{K}L is closed under the bracket operation. Moreover the elements of U are all nilpotent maps of L. By [Jac], p. 33, Theorem 1, the associative algebra A generated by U is nilpotent, hence ad_{L}(KB_{r+1}) ≤ A is also nilpotent.

Our method for finding a non-nilpotent element starts with the set B_{0} = ∅ and repeatedly applies the sub-algorithm until either a non-nilpotent element is found, or r = n is attained. In this case KB_{n} = L is a nilpotent algebra and therefore every element of L is ad-nilpotent.

The number of arithmetical operations is bounded by a polynomial of n, hence it gives a polynomial time algorithm if K is finite. If K is infinite then we have no satisfactory bound on the size (of the coefficients) of the elements b_{i}. Nevertheless, in the practically very important case charK = 0 a quite simple method is available.

Proposition 5.2.1 Let L be a Lie algebra over a field K of characteristic zero. Let a_{1}, a_{2}, … a_{n} be a basis of L over K. If L is not a nilpotent algebra, then the set {a_{1}, …, a_{n}} ∪ {a_{i} + a_{j}; 1 ≤ i < j ≤ n} contains an element which is not ad-nilpotent.

Proof If L is solvable but not nilpotent, then by [Jac], p. 45, Corollary 2, one of the basis elements a_{i} is not ad-nilpotent. If L is not solvable then [Jac], p. 73, Theorem 5 implies that the Killing form of L is not identically zero: there exist basis elements a_{i}, a_{j} (i ≤ j) such that Tr(ad_{L}a_{i}ad_{L}a_{j}) ≠ 0. From

Tr((ad_{L}a_{i} + ad_{L}a_{j})^{2}) − Tr(ad_{L}a_{i}^{2}) − Tr(ad_{L}a_{j}^{2}) =
= Tr(ad_{L}a_{i}ad_{L}a_{j}) + Tr(ad_{L}a_{j}ad_{L}a_{i}) = 2Tr(ad_{L}a_{i}ad_{L}a_{j}) ≠ 0

we infer that the elements a_{i} + a_{j}, a_{i}, a_{j} cannot be all ad-nilpotent. □

Proposition 5.2.1 provides an efficient method for finding a non-nilpotent element if K is a number field. We can solve the problem by inspecting at most \binom{n+1}{2} elements of L. These elements have small coefficients. If L is semisimple then we can do better. Using the fact that the Killing form is non-degenerate on semisimple algebras, the argument of Proposition 5.2.1 gives that the set {a_{1}, a_{2}, …, a_{n}, a_{1} + a_{2}, …, a_{1} + a_{n}} contains a nonnilpotent element.

Assume now that K = 𝔽_{q}(X) and a_{1}, …, a_{n} is a basis of L such that the structure constants w.r.t. this basis are in 𝔽_{q}[X]. Such a basis can be obtained using the standard trick of clearing the denominators. Assume further that the degrees of structure constants are at most d. Let Λ be the 𝔽_{q}[X]-submodule of L generated by a_{1}, …, a_{n}. Then Λ is a free 𝔽_{q}[X]-module with basis a_{1}, …, a_{n} and it is in fact a Lie subalgebra over the ring 𝔽_{q}[X] of L such that 𝔽_{q}(X)Λ = L. Obviously, L is nilpotent iff Λ^{n+1} = 0. L^{n+1} has a basis consisting of elements of the form [b_{1}, [b_{2}, … [b_{n}, b_{n+1}] …]], where b_{1}, …, b_{n}, b_{n+1} ∈ {a_{1}, …, a_{n}}. The coefficients of these elements, expressed w.r.t. the basis a_{1}, …, a_{n}, are polynomials of degree at most nd. Let f(X) ∈ 𝔽_{q}[X] be an arbitrary polynomial. The factor module L_{f} = Λ/f(X)Λ inherits the Lie-ring structure of Λ. L_{f} is in fact a Lie algebra of rank n over the factor ring 𝔽_{q}[X]/(f(X)) (the structure constants are reduced modulo f). Since 𝔽_{q}[X]/(f(X)) is an associative F_{q}-algebra, we have that L_{f} is a Lie algebra over F_{q} of dimension ndeg f and an 𝔽_{q}-basis of L_{f} together with the structure constants can be computed efficiently. Obviously, if L_{f} turns out to be non-nilpotent and we find an element ā ∈ L_{f} which is not ad-nilpotent, then any lift a of ā to Λ is not ad-nilpotent either. On the other hand, we have that if deg f > nd then L is nilpotent iff L_{f} is nilpotent. Therefore if we choose an arbitrary polynomial f(X) ∈ 𝔽_{q}[X] of degree nd + 1, then, using the iterative method for L_{f}, we can decide in deterministic polynomial time whether L is nilpotent. Moreover, if L is not nilpotent, then find an element a ∈ Λ such that ā = a + f(X)Λ is a non-nilpotent element of L_{f}.

An alternative (and probably more efficient) method is to test successively L_{f_{1}}, L_{f_{2}}, …, where f_{1}, f_{2}, … are distinct irreducible polynomials in 𝔽_{q}[X]. The procedure either stops with a non-nilpotent element modulo f_{i}, or with the conclusion that L is nilpotent if deg f_{1} + deg f_{2} + … + deg f_{i} > nd and L_{f_{1}}, L_{f_{2}}, …, L_{f_{i}} are nilpotent.

We summarize the results of this section in the following statement.

Theorem 5.2.2 Let K be either a finite field or a global field. Suppose that we are given a non-nilpotent Lie algebra by structure constants over K. Then we can find in deterministic polynomial time an element a ∈ L such that ad_{L}a is not a nilpotent linear transformation of L. □

Remarks 1. If L is not nilpotent and |K| ≥ cn for a constant c > 1, then if we select coefficients α_{i} uniformly and independently from a subset Ω ⊂ K, |Ω| ≥ cn, then the element a = α_{1}a_{1} + ⋯ + α_{n}a_{n} will be non-nilpotent with probability at least 1 − 1/c. This follows readily from the Sparse Zeros Lemma and Proposition 5.1.2. Thus, if K is sufficiently large, then we have a good randomized method.

2. Our methods are applicable to subalgebras as well, where the input is represented in a different way: instead of structure constants we have basis vectors from a larger structure.

5.3 Locally regular endomorphisms

In this section we consider a linear algebra problem which includes a major subcase of the task of computing Cartan subalgebras. We believe that the problem is interesting on its own right, therefore we give here a separate treatment. Our method is an extended algorithmic version of the existence argument for Cartan subalgebras given on pp. 78–80, by Humphreys [Hum].

Suppose that we are given a subspace D ≤ End_{K}V (dim_{K}V = n) by a basis a_{1}, a_{2}, … a_{l}. We wish to find a locally regular element a ∈ D.

We assume the existence of an auxiliary procedure NON-NILP(a), which, on input a ∈ D returns an element b ∈ N_{D}(V_{0}(a)) which is not nilpotent on V_{0}(a), or the conclusion, that no such element exists, if N_{D}(V_{0}(a)) acts nilpotently on V_{0}(a). The element a is assumed to be given as a linear combination a = ∑ α_{i}a_{i} of the basis elements. We suppose that NON-NILP runs in polynomial time. We are unable to give such efficient algorithm in general, but, as witnessed by the results of Section 5.2, we have polynomial time algorithms when D = ad(L), where L is a Lie algebra over K (K is either finite or a global field) and V = L. We shall also require that |K| > n. We denote by Ω a fixed subset of K of size n + 1. If the characteristic of K is 0, then we insist that Ω = {1, 2, …, n + 1}. Similarly, if K is a finite extension of 𝔽_{q}(X) then we assume that Ω consists of nonzero polynomials from 𝔽_{q}[X] of degree at most ⌈log_{q}(n+2)⌉. The main steps of our algorithm are as follows.

1. a := 0.

2. b := NON-NILP(a).

3. if every element of N_{D}(V_{0}(a)) is nilpotent on V_{0}(a) then return a. (At this point b ∈ N_{D}(V_{0}(a)) is not nilpotent on V_{0}(a).)

4. Select an element c from the set {a + α(b − a); α ∈ Ω} for which V_{0}(c) is a proper subset of V_{0}(a).

5. Put a := c. If K is infinite, then replace a by an element ∑ α_{i}a_{i}, such that α_{i} ∈ Ω and dim_{K}V_{0}(∑ α_{i}a_{i}) ≤ dim_{K}V_{0}(a), as provided by Corollary 5.1.3.

6. Go back to step 2.

Upon termination N_{D}(V_{0}(a)) acts nilpotently on V_{0}(a), therefore a is then a locally regular element. We claim, that a c can always be selected at step 4.

By construction, W is invariant under the action of the transformations a + β(b − a), β ∈ K, and hence so is the space V/W. The determinant on V/W of a + β(b − a) is a polynomial of β of degree at most n − dim_{K}W and not identically zero (take β = 0). We infer that there exists a subset Ω′ ⊂ Ω of size at least n + 1 − (n − dim_{K}W) = dim_{K}W + 1, such that the elements a + α(b − a), α ∈ Ω′ are nonsingular on the factor V/W. Moreover, as we saw in Section 5.1, the fact that a + β(b − a) is nilpotent on W can be described as h_{i}(β) = 0, where h_{i}(x) ∈ K[x], 1 ≤ i ≤ dim_{K}W and deg h_{i} ≤ dim_{K}W. The polynomials h_{i} cannot be all identically zero, because b = a + 1(b − a) is not nilpotent on W. We infer that there is an α ∈ Ω′ which is not a common zero for all of the polynomials h_{i}. Then the element c = a + α(b − a) is nonsingular on the factor V/W and non-nilpotent on W, consequently V_{0}(c) is a proper subset of W. The claim is proved.

The claim ensures, that the quantity dim_{K}V_{0}(a) decreases at each round of the iteration, therefore the body of the loop is executed at most n times. Steps 2–3 require a polynomial number of arithmetical operations in K by assumption on the procedure NON-NILP. Step 4 is basic linear algebra, it involves the computation of the images of at most n + 1 linear transformations. A polynomial bound on step 5 is given in Corollary 5.1.3. Step 5 also ensures, that the coefficients of a and hence b are kept under control. We summarize the result as

Theorem 5.3.1 Suppose that we are given a subspace D ≤ End_{K}V (dim_{K}V = n) by a basis a_{1}, a_{2}, … a_{l}. Subject to the assumptions made on K, NON-NILP, and Ω ⊆ K, we can find a locally regular element a = ∑ α_{i}a_{i} ∈ D such that the coefficients α_{i} ∈ Ω in deterministic polynomial time. □

Remark. Suppose that |K| ≥ 2n, and Ω ⊆ K, |Ω| = 2n. Then an element a = ∑ α_{i}a_{i} ∈ D with coefficients α_{i} drawn uniformly and independently from Ω will be locally regular with probability at least 1/2. This follows at once from Proposition 5.1.2 and the Sparse Zeros Lemma. Thus, if K is sufficiently large, then a very efficient randomized method is available.

5.4 Cartan subalgebras

Here we present two algorithms for computing Cartan subalgebras in Lie algebras. Throughout L denotes a Lie algebra over the field K. We assume that L is given as input by structure constants with respect to the basis a_{1}, a_{2}, …, a_{n}. We have in particular dim_{K}L = n. Our objective is to find a (basis of a) Cartan subalgebra H ≤ L.

The first method is based on our algorithm for locally regular endomorphisms.

Theorem 5.4.1 Suppose that K is either finite, or a global field, and |K| > n. Let Ω be a fixed subset of K of size n + 1. If charK = 0, then we set Ω = {1, 2, …, n + 1}. If K is a finite extension of 𝔽_{q}(X) then we assume that Ω consists of nonzero polynomials from 𝔽_{q}[X] of degree at most ⌈log_{q}(n + 2)⌉. Then we can find an element a = ∑ α_{i}a_{i} ∈ L with α_{i} ∈ Ω such that H := V_{0}(ad_{L}a) ≤ L is a Cartan subalgebra of L in deterministic polynomial time.

Proof It is known (cf. [Hum], pp. 77–78) that if a ∈ L then H := V_{0}(ad_{L}a) is a subalgebra of L for which N_{L}(H) = H. If in addition ad_{L}a is a locally regular endomorphism of L (as just a linear space over K), then ad_{L}c is nilpotent on L for every element c ∈ H. By Engel’s theorem we obtain that H is nilpotent, hence a Cartan subalgebra of L. It suffices therefore to find a locally regular element in D = ad_{L}(L) with respect to the action on V = L. To this end we can use the algorithm of Theorem 5.3.1. This gives a polynomial time algorithm, because by Theorem 5.2.2 we have an efficient implementation of the procedure NON-NILP. □

Concerning our second algorithm, we assume that K is an arbitrary finite field and L is a restricted Lie algebra. Recall (cf. [Jac], pp. 185–194, or [Win], pp. 102–103) that a restricted Lie algebra L (or a Lie p-algebra) over the field K of characteristic p > 0 is a Lie algebra over K equipped with a map x ↦ x^{p} (called the p-map) such that for every α ∈ K and x, y ∈ A

(i) ad_{L}(x^{[p]} = (ad_{L}x)^{p}; (ii) (αx)^{[p]} = α^{p}x^{[p]}; (iii) (x + y)^{[p]} = x^{[p]} + y^{[p]} + ∑_{i=1}^{p−1} s_{i}(x, y); where is_{i}(x, y) is the coefficient of t^{i−1} in (ad_{L}(y−tx))^{p−1}x. Condition (iii), in paricular the definition of s_{i}(x, y) is rather thechnical, and can be omitted for Lie algebras with trivial center. Important examples are Lie algebras of associative algebras: if A is an associative algebra then its Lie algebra A_{Lie} is a resticted Lie algebra with respect to the natural p-map x^{[p]} = x^{p}.

We only use condition (i). Furthermore, we do not require the p-map to be part of the input. The mere existence will be used in the proof of the correctness of the method. For a subset B ⊆ L we denote by L_{0}(B) the subalgebra {x ∈ L|xad_{L}(b)^{n} = 0 for every b ∈ B} (the intersection of the Fitting null components of the maps ad_{L}(b) for b ∈ B). In the algorithm A stands for a subset of L.

Algorithm Restricted Cartan(L): A = ∅ r := 0. forever do r := r + 1; a_{r} :=Non-nilp(L_{0}(A)) if L_{0}(A) is nilpotent then return L_{0}(A) A := A ∪ {a_{r}} done

Here the auxiliary procedure Non-nilp(S) on a subalgebra S ≤ L returns an element a ∈ S, such that ad_{S}a is not nilpotent, or the conclusion that S is a nilpotent algebra. By Theorem 5.2.2 this can be done in time polynomial in n and log |K|.

It is immediate that the algorithm terminates in at most n rounds, and that the number of arithmetical operations is bounded by a polynomial of n and log |K|; we have therefore a polynomial time algorithm. It is also clear that upon termination H = L_{0}(A) is a nilpotent subalgebra of L. To show that it is in fact a Cartan subalgebra, we establish that N_{L}(H) = H.

Let t be an integer such that p^{t} ≥ n. For a ∈ L we put a^{∗} := a^{[p^{t}]} = (((a^{[p]})^{[p]}) ⋯)^{[p]}. For a subset B ⊆ L let B^{∗} := {b^{∗}|b ∈ B}. We have L_{0}(B) = L_{0}(B^{∗}) = C_{L}(B^{∗}), the centralizer of B^{∗}. The last equality follows because t is sufficiently large to ascertain that ad_{L}(B^{∗}) consists of semisimple endomorphisms.

We consider the final state of A. If A = ∅, then L is nilpotent, hence a Cartan subalgebra. Otherwise A = {a_{1}, a_{2}, …, a_{r}}, where r > 0. We note that for 1 ≤ j ≤ r, a_{j} is selected from L_{0}({a_{1} …, a_{j−1}}) = C_{L}({a_{1}^{∗}, …, a_{j−1}^{∗}}). This implies that if i ≤ j, then [a_{i}^{∗}, a_{j}] = 0 and hence [a_{i}^{∗}, a_{j}^{∗}] = [… [[a_{i}^{∗}, a_{j}], a_{j}] …, a_{j}] = 0. Taking anti-commutativity into consideration, we have [a_{i}^{∗}, a_{j}^{∗}] = 0, whenever 1 ≤ i, j ≤ r. These facts imply that A^{∗} ⊆ C_{L}(A^{∗}) = L_{0}(A). Now let y ∈ N_{L}(L_{0}(A)). We have [[y, A^{∗}], A^{∗}] ⊆ [[y, L_{0}(A)], A^{∗}] ⊆ [L_{0}(A), A^{∗}] = [C_{L}(A^{∗}), A^{∗}] = 0. We obtained that y ∈ L_{0}(A^{∗}) = L_{0}(A), and hence N_{L}(L_{0}(A)) = L_{0}(A). L_{0}(A) is indeed a Cartan subalgebra of L. We have proved the following result:

Theorem 5.4.2 Let K be a finite field and L be a restricted Lie algebra over K, given by structure constants. Then the algorithm Restricted Cartan finds a Cartan subalgebra H ≤ L in deterministic polynomial time. □

5.5 Tori in associative algebras

We conclude this chapter by some remarks on applications to associative algebras. By an n-dimensional torus over the field K we understand a commutative and associative separable K-algebra of dimension n. Let A be a finite dimensional separable associative algebra over the field K. A torus in A is then a commutative separable subalgebra in A. Let A_{Lie} denote the Lie algebra of A. Note that if K is of positive characteristic p then A_{Lie} is a restricted Lie algebra in the natural way. It is easy to see that if B is a torus in A, then the Fitting zero component of the adjoint action of B on A_{Lie} is the centralizer C_{A}(B) (cf. [Win], Corollary 4.5.6). Furthermore, it is known (cf. [Win], Theorems 3.2.7.1 and 4.5.17) that Cartan subalgebras of A_{Lie} are exactly the maximal tori in A (i.e., tori maximal w.r.t. inclusion). The results of the previous section imply

Corollary 5.5.1 Assume that K is either a finite field or a global field. Given A, a finite dimensional separable K-algebra, we can find a maximal torus in A in deterministic polynomial time. □

An element a of the separable K-algebra A is called a splitting element if the Ksubalgebra ⟨1_{A}, a⟩ generated by a and 1_{A} is a maximal torus in A. It is also of interest to find splitting elements in fixed tori. Let B be an n-dimensional torus over K. Assume that K is large enough, e.g., K > n^{2}. The algorithm will be a straightforward generalization of the textbook technique for finding primitive elements in finite extensions of fields K with charK = 0. In order to demonstrate that the method is in fact a special case of the procedure of Section 5.3, we consider the regular representation of B, although the algorithm will use only computations in B. The regular representation allows us to identify B with a maximal torus in A = M_{n}(K). We intend to use the general method of Section 5.3 to find a locally regular element in B with respect to the adjoint action on V = A, (ad_{A}av := av − va). By [Win], Corollary 4.5.6, we have that the Fitting zero component V_{0}(ad_{A}a) of an element a ∈ B is the centralizer of a in A. If follows that for a, c ∈ B we have V_{0}(ad_{A}a) > V_{0}(ad_{A}c) if and only if ⟨1, a⟩ < ⟨1, c⟩. Furthermore, the commutativity of B implies that V_{0}(ad_{A}a) is B-invariant, i.e., N_{B}(V_{0}(ad_{A}a)) = B for every a ∈ B. These facts imply that an element a ∈ B is locally regular iff a is a splitting element and suggest the following implementation of the critical steps 2 and 4 in the general procedure: Step 2. Find an element b ∈ B \ ⟨1, a⟩ (provided that B ≠ ⟨1, a⟩). Step 4. Find an element c ∈ {a + α(b − a)|α ∈ Ω} such that ⟨1, c⟩ > ⟨1, b⟩. Both steps can be accomplished in a straightforward way (computing bases of ⟨1, a⟩ and ⟨1, c⟩, respectively). The argument in Section 5.3 implies that this variant of the procedure finds a splitting element in polynomial time, provided that K is either a global field or K is finite with |K| > n^{2}. Note that a more accurate analysis shows that the method already works for |K| > \binom{n}{2}. Also note that if the ground field K is small then the Wedderburn decompostion of B can be found in deterministic polynomial time by the method of [FR] and a straightforward algorithm is available for finding a splitting element in B, provided that such an element exists. We leave the details to the reader.

Corollary 5.5.2 Assume that K is either a finite field or a global field. Given A, a separable algebra over K, in deterministic polynomial time we can find a splitting element in A, provided that such an element exists. □

In the literature, several randomized algorithms are based on the technique of splitting elements. It turns out, that in most cases the only step that makes use of randomization is finding a splitting element. Randomized algorithms for finding splitting elements in tori and central simple algebras, based on the Sparse Zeros Lemma, were found by Eberly. The first deterministic polynomial time method for finding splitting elements in central simple algebras over number fields was discovered by Rónyai [Ró5]. We conclude with a list of some important algorithmic problems that can be solved in deterministic polynomial time under the assumption that we have a splitting element at hand.

• Assume that K is either a finite field or a global field. The problem of finding the simple components of a finite dimensional separable K-algebra can be reduced to the task of factoring a single polynomial over K (cf. [Eb1, Eb2]).

• Let K be a number field and A be a central simple algebra of dimension n^{2} over K. A subfield L of A can be found together with an isomorphism ϕ : L ⊗_{K} A ≅ M_{n}(L) (cf. [BR]).

• Let K be a number field and A be a central simple algebra of dimension n^{2} over K. Embeddings ϕ : K → ℝ can be constucted such that ℝ ⊗_{ϕ(K)} A ≅ M_{n}(ℝ). (cf. [Eb3]). We shall use this result in Chapter 6.

Maximal orders

The results presented in this chapter are based on (partly improved versions of) the methods from the paper [IR], joint work with Lajos Rónyai. In [Ró3], it was shown that the problem of deciding whether the index of a central simple algebra A over a number field equals a given integer is in NP ∩ coNP. Actually, it was proved that there exists a maximal ℤ-order in A which admits a short description and verification, and the theory of maximal orders and Hasse’s principle can be used to determine the index from invariants of maximal orders. To be more specific, the main technical contribution in [Ró3] is a deterministic polynomial time ff-algorithm (an algorithm that can make oracle calls to factor integers and polynomials over finite fields) for testing maximality of orders. The central result of this chapter is a deterministic polynomial time ff-algorithm for constructing maximal orders in semisimple algebras over number fields. A consequence is the existence of a polynomial time ff-algorithm for computing the index of central simple algebras. In the important special case of computing the indices of algebras related to representations of finite groups (known as Schur indices), the oracle can be substituted with a polynomial time algorithm. The main ideas can be generalized to separable algebras over global fields. For algebras over global function fields we obtain f-algorithms (that make calls to an oracle for factoring polynomials over the prime field).

We start with the basic definitions. Let R be a Dedekind ring, i.e., a Noetherian integrally closed domain such that every nonzero prime ideal in R is a maximal ideal, K be the field of quotients of R and let A be a finite dimensional semisimple algebra over K. An R-order in A is a subring Λ of A satisfying the following properties:

- Λ is a finitely generated module over R,

- Λ has an identity element (this is necessarily the same as the identity element of A and R), - Λ generates A as a linear space over K.

An R-order Λ in A is a maximal R-order if it is not a proper subring of any other R-order of A. It is known that if A is a separable commutative K-algebra (e.g., A is a finite separable extension field of K), then the integral closure Λ of R in A defined by

Λ = {x ∈ A|there exists a monic polynomial f(X) ∈ R[X] such that f(x) = 0}

is the a unique maximal order in A.

If P is a maximal ideal in R then we can consider the localization R_{P} of R at P:

R_{P} = \{\frac{α}{β}|α ∈ R, β ∈ R \ P \}.

R_{P} is a discrete valuation ring, i.e., a local Dedekind ring. We shall represent R_{P} -orders with R-orders. If Λ is an R-order then the localization

Λ_{P} = R_{P} Λ = \{\frac{1}{β} x|x ∈ Λ, β ∈ R \ P \}

is an R_{P} -order. We say that Λ is locally maximal at P if Λ_{P} is a maximal R_{P} -order. It turns out that Λ is maximal if and only if it is locally maximal at every maximal ideal P of R.

Let A be a semisimple algebra over the number field K, and D denote the ring of integers in K. The key result of this chapter is a polynomial time f-algorithm that, given A and a rational prime p, constructs a ℤ-order Λ which is locally maximal at the prime p. An application is a polynomial time ff-algorithm for finding a (globally) maximal D-order in A, as well as one for computing the index of A. For the analogous problems over global function fields, these ideas lead to polynomial time f-algorithms (making oracle calls to factor polynomials over the prime field).

As an application to representation theory of finite groups, we give a deterministic polynomial time method to compute the degrees of the irreducible submodules of a finite matrix group over an algebraic number field K of a finite group G given by generators.

The organization of this chapter is as follows. Section 6.1 contains the basic statements from the theory of orders we need. Most of the material can be found in [Re]. Proofs are given only where a precise reference was hard to locate.

In Section 6.2 we collect some statements about the radicals of orders over discrete valuation rings. These play an important role in the study of extremal orders later on.

Section 6.3 and in particular Proposition 6.3.1 and Theorem 6.3.5 contain the statements which serve as the theoretical foundation for our algorithms. These two statements enable us to reduce the problem of finding maximal orders over discrete valuation rings to that of decomposing associative algebras over the residue class fields. The ideas presented here are not new. They were used by Jacobinski (see [Ja] or [Re], Chapter 39) in his approach to the theory of hereditary orders. We include proofs because Jacobinski worked with complete local rings. In the statements here the completeness of R is not assumed. Also, largely due to the fact that weaker results are sufficient for our purposes, it was possible to simplify some of the original arguments.

Section 6.4 contains the algorithms for computing maximal orders. Theorem 6.4.1 provides the basic ‘iteration step’ of our subsequent methods for constructing (locally) maximal orders. We describe an algorithm that for a given order Λ constructs an order Γ containing Λ such that Γ is “locally greater” than Λ if such an order exists.

In Corollary 6.4.3 we give a polynomial time ff-algorithm for constructing a maximal D-order Λ in a semisimple algebra A over an algebraic number field K. This settles in the affirmative the question raised in [Ró3].

In Section 6.5 algorithms for computing the index are presented. Perhaps the most interesting result of this chapter is Theorem 6.5.5. We propose a deterministic polynomial time algorithm to compute the dimensions of the irreducible G-submodules of K^{n}, where K is a number field and G is a finite subgroup of GL_{n}(K) given by generators. An important special case is computing the degrees of the irreducible representations over an algebraic number field K of a finite group G given by a multiplication table.

Notation and terminology

Throughout this chapter we keep ourselves to the following notation and terminology:

- R: a Dedekind ring, i.e., a Noetherian integrally closed domain in which the nonzero prime ideals are maximal

- K: the field of quotients of R

- P: a unique maximal ideal of R

- π: a prime element of R in case of R is a principal ideal domain, i.e., an element such that the ideal P = (π) is maximal. Typically, π stands for either a rational prime p (case R = ℤ) or an irreducible polynomial f(X) ∈ 𝔽_{q}[X] (case R = 𝔽_{q}[X]).

- A: a finite dimensional separable algebra over K

- order: we use this term for an R-order in the K-algebra A.

- Γ, Λ: orders - lattice: If V is a finite dimensional K-space, an R-lattice in V is a finitely generated submodule M of the R-module V. If, in addition, M is a K-space generating set of the entire space V, we say that M is a full R-lattice in V. Full lattices in the vector space A are of particular interest. Orders are special cases of full lattices in A.

- radical: the Jacobson radical of a ring or algebra, denoted by Rad(R), Rad(Λ), etc.

6.1 Basic facts about orders

In this section we collect the basic facts and some elementary results from the theory of orders we need later on. In this section we assume that A is a separable algebra, i.e., semisimple and the centers of its simple components are separable extensions of the ground field K.

Reduced trace forms and discriminants

First we introduce the reduced trace function of a semisimple algebra using a sequence of progressively more general definitions (for a central simple algebra, then a simple algebra, and finally for a semisimple algebra).

We start from the trace of the left regular representation of A. To be more specific, the trace Tr_{A/K}(x) of an element x ∈ A over K is the trace of the the K-linear transformation L_{x} : A → A defined by L_{x}(a) = xa for a ∈ A.

If A is a full matrix algebra over the field E, dim_{E}A = n^{2}, then there is another way to define traces of elements of A. Namely, if we have an isomorphism ϕ: A ≅ M_{n}(E) then we can take tr_{A/E}(x) as the trace of the matrix ϕx. This is independent from the choice of the isomorphism ϕ.

If A is a central simple K-algebra, dim_{K}A = n^{2}, then there exists an extension field E of K which splits A, i.e., E ⊗_{K} A ≅ M_{n}(E). It can be shown that tr_{A/K}(x) := tr_{E⊗_{K}A/E}(x ⊗ 1) ∈ K is independent of the choice of the splitting field E and we have ntr_{A/K}(x) = Tr_{A/K}(x). Consequently if the characteristic of K is zero (or prime to n), then tr_{A/K}(x) = \frac{1}{n}Tr_{A/K}(x).

If A is a simple K-algebra with center L then we can take tr_{A/K}(x) := Tr_{L/K}tr_{A/L}(x). If A is a semisimple K-algebra with Wedderburn decomposition A = A_{1} ⊕ … ⊕ A_{r}, then we can define tr_{A/K}(x) := tr_{A_{1}/K}(x_{1}) + … + tr_{A_{r}/K}(x_{r}), where x_{i} is the image of x under the projection A → A_{i} onto the ith simple component of A. We call tr_{A/K}(x) the reduced trace of x over K. The map ⟨ , ⟩: A×A → K defined by ⟨x, y⟩ := tr_{A/K}(xy) is a K-bilinear function and is called the bilinear trace form of A over K. If A is separable over K then ⟨ , ⟩ is a nondegenerate bilinear form. For the rest of this subsection we assume that A is separable over K.

We shall omit the subscript A/K from Tr_{A/K} and tr_{A/K} whenever A and K are clear from the context.

Let Λ be an R-order in A. Then for every element x ∈ Λ, we have tr(x) ∈ R (cf. [Re], Thm. 10.1). Let n = dim_{K}A. The discriminant of the order Λ is the ideal disc(Λ) in R generated by the set

{det (tr(x_{i}x_{j}))_{i,j=1}^{n} | (x_{1}, …, x_{n}) ∈ Λ^{n}}.

Proposition 6.1.1 Assume that Λ ⊆ Γ. Then disc(Γ) ⊇ disc(Λ) and Λ = Γ if and only if disc(Γ) = disc(Λ).

Proof [Re], Exercise 10.3 or 4.13. □

From a generating set of Λ as an R-module we can easily obtain a nonzero multiple of disc(Λ): we select a subset {x_{1}, …, x_{n}} of the generating set which is a K-basis of A.

Proposition 6.1.2 Let {x_{1}, …, x_{n}} ⊆ Λ be a K-basis of A. Then the principal ideal generated by the nonzero determinant d = det (tr(x_{i}x_{j}))_{i,j=1}^{n} is contained in the discriminant.

Proof Obvious. □

Proposition 6.1.3 Let {x_{1}, …, x_{n}} and d be as in Proposition 6.1.2. Let Γ be any order containing Λ. Then dΓ ⊆ R{x_{1}, …, x_{n}} ⊆ Λ.

Proof The proof is a version of the argument given in [Re], Thm. 10.3. Let a ∈ Γ and put a = ∑ γ_{i}a_{i}, where γ_{i} ∈ K. Then

tr(aa_{j}) = ∑_{i=1}^{n} γ_{i}tr(a_{i}a_{j}), 1 ≤ j ≤ n.

We have tr(aa_{j}), tr(a_{i}a_{j}) ∈ R because aa_{j}, a_{i}a_{j} ∈ Γ and therefore they are integral elements over R. If we use Cramer’s rule to solve the system of linear equations above for the γ_{i}, we obtain that γ_{i} = \frac{α_{i}}{d} for some α_{i} ∈ R. □

Note that if R is a principal ideal domain then every R-order Λ admits an R-basis, say {x_{1}, …, x_{n}}, and the discriminant disc(Λ) is the principal ideal generated by the determinant det (tr(x_{i}x_{j}))_{i,j=1}^{n} (cf. [Re], Theorem 10.2).

Localizations

If R is a Dedekind domain with quotient field K and P is a prime ideal in R then the ring of quotients R_{P} = (R \ P)^{−1}R ⊂ K is a discrete valuation ring. For an R-lattice M in A we can define the localization at P as follows: M_{P} = R_{P} M ⊂ A. M_{P} is an R_{P} -lattice. If M is a full R-lattice in A (i.e., KM = A), then M_{P} is a full R_{P} -lattice in A. If Λ is an R-order then Λ_{P} is an R_{P} -order, moreover Λ is a maximal R-order if and only if Λ_{P} is a maximal R_{P} order for every prime ideal P of R. More generally,

Proposition 6.1.4 If Γ and Λ are R-orders in A such that Λ ⊂ Γ then there exist a prime ideal P of R such that Λ_{P} ⊂ Γ_{P}.

Proof [Re], Theorem 3.15. □

The next statement demonstrates a simple but useful connection between the orders Λ and Λ_{P}.

Proposition 6.1.5 Let Λ be an R-order in A. The map ϕ : x ↦ x+P Λ_{P} (x ∈ Λ) induces an isomorphism of rings Λ/P Λ ≅ Λ_{P} /P Λ_{P}.

Proof Clearly ϕ : Λ → Λ_{P} /P Λ_{P} is an epimorphism of rings. It is straightforward to check that ker(ϕ) = P Λ. □

To be more specific, if R happens to be a principal ideal domain, and π is a prime element in R, i.e., the principal ideal (π) is a maximal ideal in R, then we can write

R_{(π)} = {r/s ∈ K|r, s ∈ R, gcd(π, s) = 1}.

R_{(π)} is a discrete valuation ring with unique maximal ideal R_{(π)}π. If Λ is an R-order, then we use the notation Λ_{(π)} = R_{(π)}Λ.

Important examples are when R = ℤ and π = p, a rational prime, or R = 𝔽_{q}[X] and π = f(X), a (monic) irreducible polynomial in 𝔽_{q}[X], respectively. Then we use the notation ℤ_{(p)}, Λ_{(p)}, 𝔽_{q}[X]_{(f(X))}, and Λ_{(f(X))}, respectively.

Orders over extensions

Assume that L is a finite separable extension of K, and A is finite dimensional separable L-algebra. Let D be the integral closure of R in L. The next statement will be useful when we change the ring of coefficients from R to D.

Lemma 6.1.6 Let L be a finite separable extension field of K, A a finite dimensional separable algebra over L and let Λ be an R-order in A. Let D be the integral closure of R in L. Then Γ = DΛ is a D-order containing Λ. As a consequence, if Λ is a maximal R-order then Λ ∩ L(= Λ ∩ L1_{A}) = D. Moreover, a maximal R-order in A is a maximal D-order as well.

Proof It is straightforward to check that DΛ (the finite sums of the form ∑ α_{i}x_{i}, α_{i} ∈ D, x_{i} ∈ Λ) is a ring which is a finitely generated D-module. Also we have 1_{Λ} ∈ DΛ, therefore Γ is indeed a D-order. Now the rest is obvious. □

We will use the following statement to compute local properties of D-orders without explicitly computing D.

Lemma 6.1.7 Let L be a finite separable extension field of K, A a finite dimensional separable algebra over L and let D be the integral closure of R in L. Assume that Λ is an R-order in A such that Λ is locally maximal at the prime ideal P of R. Then the R-order Γ = DΛ is a D-order as well, and Γ is locally maximal at every prime ideal P of D above P. Let B = Λ/P Λ and C be the image of Λ ∩ L at the natural map ϕ : Λ → B. The map P ↦ ϕ(P ∩ Λ) is a bijection between the prime ideals of D and the maximal ideals of C such that Γ/PΓ ≅ B/ϕ(P ∩ Λ)B.

Proof The local maximality of Λ implies Γ_{P} = Λ_{P}. Let Δ = Λ ∩ L. Then Δ_{P} = Λ_{P} ∩ L = Γ_{P} ∩L = (Γ∩L)_{P} = D_{P}, i.e., Δ is also locally maximal at P (in L). Let ψ : x ↦ x+P Γ_{P} be the natural map Γ_{P} → Γ/P Γ_{P}. By Proposition 6.1.5, the restriction of ψ to Γ induces an isomorphism Γ/P Γ ≅ Γ_{P} /P Γ_{P}. Similarly, the restriction of ψ to Λ induces an isomorphism Λ/P Λ ≅ Γ_{P} /P Γ_{P}. In fact, we can identify B with Γ_{P} /P Γ_{P} and ϕ with the restriction of ψ to Λ. Using these identifications, we have ψ(D) = ψ(D_{P}) = ψ(Δ_{P}) = ψ(Δ) = C. The kernel of the restriction of ψ to D_{P} is P D_{P}. It follows that ψ induces a bijection between the ideals of D containing P D and the ideals of C. For every maximal ideal P of D above P, we have ψ(PΓ)) = ψ(P)ψΓ = ψ(P)B, whence ψ induces an isomorphism Γ/PΓ ≅ B/ψ(P ∩ Λ)B. □

Orders over ℤ and 𝔽_{q}[X]

There are some simple examples of orders. If M is a full R-lattice in A (i.e., KM = A) then the left order of M defined by O_{l}(M) = {x ∈ A | xM ⊆ M} is an R-order in A (cf. p. 109, [Re]). The right order is defined in a similar way. These examples offer an important algorithmic tool for constructing orders.

For the rest of this section we assume that R = ℤ or R = 𝔽_{q}[X]. The following statement is an easy generalization of [Ró3], Theorem 3.1.

Proposition 6.1.8 If a full R-lattice M in the K-algebra A is given by an R-basis then O_{l}(M) has an R-basis of size (size(A) + size(M))^{O(1)} and such a basis can be computed in time (size(A) + size(M))^{O(1)}.

Proof Let b_{1}, …, b_{n} be the given R-basis of M. Since KM = A, we can express 1_{A} as a K-linear combination of b_{1}, …, b_{n} via solving a system of linear equations over K. Computing a common denominator leads to finding s ∈ R in time (size(A) + size(M))^{O(1)} such that s1_{A} ∈ M. For such an s we have

O_{l}(M) = {x ∈ s^{−1}M|xM ⊆ M}.

Finding an R-basis of O_{l}(M) in terms of s^{−1}b_{1}, …, s^{−1}b_{n} is equivalent to computing an R-basis of the R-integral solutions of a system of linear equations. This can also be done in polynomial time. (For the case R = ℤ, the reader is referred to [Fr] or [KB]. Algorithms for R = 𝔽_{q}[X] are outlined in Section 1.2.) □

The following statement gives a tool to reduce the problem of enlarging an R-order to a similar problem for R_{(π)}-orders.

Lemma 6.1.9 Let π be a prime element in R and Γ be an R-order. Suppose that J is an ideal of Γ_{(π)} such that J ⊇ πΓ_{(π)} and O_{l}(J) ⊃ Γ_{(π)}. Let I denote the inverse image of J with respect to the embedding Γ → Γ_{(π)}. Then we have I ⊇ πΓ, O_{l}(I) ⊃ Γ, and O_{l}(I)_{(π)} ⊃ Γ_{(π)}.

Proof Clearly I ⊇ πΓ and I is an ideal of Γ. Let a_{1}, a_{2}, …, a_{t} be a generating set of I, as an R-module. Then the images of the elements a_{i} (which will also be denoted by a_{i}) form a generating set of J as an R_{(π)}-module. Now let a ∈ O_{l}(J) \ Γ_{(π)} . Then for i = 1, …, t we have

aa_{i} = \frac{α_{i1}}{β_{i1}} a_{1} + \frac{α_{i2}}{β_{i2}} a_{2} + ⋯ + \frac{α_{it}}{β_{it}} a_{t},

where α_{ij}, β_{ij} ∈ R and π does not divide β_{ij}. Now put β = ∏_{i,j} β_{ij}. Then it is straightforward to check that βaI ⊆ I and consequently βa ∈ O_{l}(I). Finally we observe that βa ∉ Γ_{(π)}, for otherwise we have a ∈ Γ_{(π)}. The proof is complete. □

The next statement provides a bound on the number of iterations in algorithms which successively increase orders until a maximal order is obtained.

Proposition 6.1.10 Assume that we have the strictly increasing chain Λ_{0} ⊂ … ⊂ Λ_{m} of R-orders in A. Let d_{i} ∈ R be a generator of the ideal disc(Λ_{i}), for i = 0, …, m. In the case d ∈ R = ℤ, let |d| denote the usual absolute value of the integer d, while in the case 0 ≠ d = d(X) ∈ R = 𝔽_{q}[X], let |d| = 2^{deg d(X)}. Then

m ≤ \frac{1}{2} log_{2} |d_{0}/d_{m}| ≤ \frac{1}{2} log_{2} |d_{0}|.

Proof For each i = 0, …, m − 1, |\frac{d_{i}}{d_{i+1}} | > 1 is the square of an integer (|det T_{i}|^{2}, where T_{i} is a matrix transforming an R-basis of Λ_{i+1} to an R-basis of Λ_{i}). We obtain the statement by taking logarithm of

|\frac{d_{0}}{d_{m}} | = ∏_{i=0}^{m−1} |\frac{d_{i}}{d_{i+1}} | ≥ 2^{2m}.

□

6.2 Radicals of orders over local rings

First we recall some basic facts about the Jacobson radical of rings. For proofs, see for example [Re], Section 6a. Let S denote an arbitrary ring with an identity element. Rad(S), the Jacobson radical of S, is the set of elements x ∈ S such that xM = (0) for all simple left (or, equivalently, Mx = (0) for all simple right) modules M over S. Rad(S) is a two-sided ideal in S containing every nilpotent one-sided ideal of S. Also, Rad(S) can be characterized as the intersection of the maximal left ideals in S, and, equivalently, as the intersection of the maximal right ideals in S. If S is left or right Artinian (this holds for example if S is a finite dimensional algebra with identity over a field) then Rad(S) is the maximal nilpotent ideal in S.

After these preliminaries let us return to our rings of interest. We assume that R is a discrete valuation ring, P is the unique nonzero prime ideal of R, K is the field of quotients of R, and Λ is an R-order in a finite dimensional semisimple K-algebra A.

Proposition 6.2.1 The residue class ring Λ̄ = Λ/P Λ is an algebra with identity element over the residue class field R̄ = R/P and dim_{K}A = dimR̄Λ̄. If ϕ: Λ → Λ̄ is the canonical epimorphism, then P Λ ⊆ Rad(Λ) = ϕ^{−1}Rad(Λ̄) and ϕ induces a ring isomorphism Λ/Rad(Λ) ≅ Λ̄/Rad(Λ̄). As a consequence, a left (or right) ideal I of Λ is contained in Rad(Λ) if and only if I is nilpotent modulo P Λ, i.e., there exists a positive integer t such that I^{t} ⊆ P Λ.

Proof Most of the statements are proved in [Re], Thm. 6.15. The claim about the dimensions follows directly from the fact that R is a principal ideal ring and Λ is a free R-module. As for the ‘only if’ part of the last statement, every nilpotent ideal of Λ̄ is contained in Rad(Λ̄). □

Proposition 6.2.2 If Λ ⊆ Γ are R-orders, then there exists a positive integer s such that Rad(Γ)^{s} ⊆ Λ. For any such s, Rad(Γ)^{s} ⊆ Rad(Λ) is an ideal in Λ.

Proof (A part of the argument below can be found in [Re], hint to Ex. 39.3.) Using that Γ ⊇ Λ are full R-modules in A over a discrete valuation ring R, from Proposition 6.2.1 we infer that there exist positive integers u and t such that P^{u}Γ ⊆ Λ and Rad(Γ)^{t} ⊆ P Γ. Now s = tu will suffice to prove the first claim. If for some s we have I = Rad(Γ)^{s} ⊆ Λ then I is an ideal in Λ because ΛI ⊆ ΓI = I and IΛ ⊆ IΓ = I. Finally for the integers t and u we have

I^{t(u+1)} = Rad(Γ)^{st(u+1)} ⊆ (P Γ)^{s(u+1)} ⊆ (P Γ)^{(u+1)} = P^{(u+1)}Γ = P · P^{u}Γ ⊆ P Λ.

Proposition 6.2.1 implies that I ⊆ Rad(Λ). □

The following observation plays an important role in Jacobinski’s approach (cf. [Ja]) to hereditary orders.

Proposition 6.2.3 Let Λ ⊆ Γ be R-orders in A such that Rad(Γ) ⊆ Λ. Then for any order Λ′ such that Λ ⊆ Λ′ ⊆ Γ we have Rad(Γ) ⊆ Rad(Λ′). The canonical map ϕ: Γ → Γ̄ = Γ/Rad(Γ) induces a bijection Λ′ ↦ Λ′/Rad(Γ) between the set of orders Λ′ lying between Λ and Γ and the set of the subalgebras of the R/P -algebra Γ̄ containing Λ/Rad(Γ). Moreover if Λ ⊆ Λ′ ⊆ Γ, then we have Rad(Λ′) = ϕ^{−1}Rad(ϕΛ′).

Proof We have Rad(Γ) ⊆ Λ ⊆ Λ′. From this Proposition 6.2.2 implies that Rad(Γ) ⊆ Rad(Λ′). The statement about the correspondence of R-orders and R/P -subalgebras is obvious once we observe that any R-subalgebra Λ′ such that Λ ⊆ Λ′ ⊆ Γ is actually an R-order. As for the last statement, we note that if J is a maximal left ideal of Λ′ then Rad(Γ) ⊆ J, because Rad(Γ) ⊆ Rad(Λ′). We infer that ϕ induces a bijection between the set of the maximal left ideals of Λ′ and the set of the maximal left ideals of Λ′/Rad(Γ) and the statement follows. □

6.3 Extremal orders

In this section R is a discrete valuation ring. For R-orders in A we introduce the following partial ordering: Γ radically contains Λ if and only if Γ ⊇ Λ and Rad(Γ) ⊇ Rad(Λ). The orders maximal with respect to this partial ordering are called extremal. Maximal orders are obviously extremal. The notion of extremal orders has been introduced in [Ja]. The next statement is from [Ja], Proposition 1. We note first that if Λ is an R-order then P Λ ⊆ Rad(Λ), so that Rad(Λ) is a full R-lattice. Therefore O_{l}(Rad(Λ)) is an R-order.

Proposition 6.3.1 For any R-order Λ, the order O_{l}(Rad(Λ)) radically contains Λ. Moreover, an R-order Λ of A is extremal if and only if Λ = O_{l}(Rad(Λ)) (if and only if Λ = O_{r}(Rad(Λ))).

Proof Since Rad(Λ) is an ideal in Λ, Λ ⊆ O_{l}(Rad(Λ)). Also, Rad(Λ) is a left ideal in O_{l}(Rad(Λ)) and by Proposition 6.2.1 for some t we have

Rad(Λ)^{t} ⊆ P Λ ⊆ P O_{l}(Rad(Λ)),

hence

Rad(Λ) ⊆ Rad(O_{l}(Rad(Λ))).

This implies that O_{l}(Rad(Λ)) radically contains Λ. We infer that if Λ is extremal then Λ = O_{l}(Rad(Λ)).

In the other direction, we suppose that Λ = O_{l}(Rad(Λ)) and Γ is an order radically containing Λ. By Proposition 6.2.2 there exists an integer s > 0 such that Rad(Γ)^{s} ⊆ Rad(Λ). For any s > 1 with this property we have

Rad(Γ)^{s−1}Rad(Λ) ⊆ Rad(Γ)^{s−1}Rad(Γ) ⊆ Rad(Λ),

implying that

Rad(Γ)^{s−1} ⊆ O_{l}(Rad(Λ)) = Λ.

Proposition 6.2.2 implies that Rad(Γ)^{s−1} ⊆ Rad(Λ). Continuing in this way we obtain Rad(Γ) ⊆ Rad(Λ) and consequently Rad(Γ) = Rad(Λ). We conclude that

Γ ⊆ O_{l}(Rad(Γ)) = O_{l}(Rad(Λ)) = Λ

and Γ = Λ. □

Proposition 6.3.2 Assume that Λ ⊆ Γ are R-orders. Then Λ + Rad(Γ) is an R-order radically containing Λ.

Proof It is straightforward to verify that Λ′ = Λ + Rad(Γ) is an R-order containing Λ. Next, using the characterization of radical-ideals from Proposition 6.2.1, we obtain that Rad(Λ) + Rad(Γ) is an ideal of Λ′ and Rad(Λ) + Rad(Γ) ⊆ Rad(Λ′). □

Proposition 6.3.3 Let Λ ⊆ Γ be R-orders and suppose that Λ is extremal. Then Rad(Γ) ⊆ Rad(Λ).

Proof An immediate consequence of Propositions 6.3.2 and 6.2.2. □

We remark that if Λ is an R-order in A such that Rad(Λ) = P Λ = πΛ then Λ is a maximal order. Indeed, O_{l}(πΛ) = O_{l}(Λ) = Λ, hence Λ is extremal by Proposition 6.3.1. If Γ ⊇ Λ then by Proposition 6.3.3 we have

πΓ ⊆ Rad(Γ) ⊆ Rad(Λ) = πΛ

implying that πΓ = πΛ and Γ = Λ.

Theorem 6.3.5 plays a key role in our method for constructing a maximal R-order. The statement and the proof is a simplified version of [Ja], Proposition 2. We need first an auxiliary lemma on semisimple algebras.

Lemma 6.3.4 Let B be a finite dimensional semisimple algebra over a field F. Let C be a maximal subalgebra of B, such that Rad(C) ≠ 0. Then there exists a two-sided ideal J of C minimal among those containing Rad(C) which is a left ideal of B.

Proof First we reduce the statement to the special case when B is simple. In general by Wedderburn’s theorem we have B = B_{1}⊕⋯⊕B_{r}, where the direct summands B_{i} are simple algebras. We observe first, that C contains the center C(B) of B. Indeed, for the algebra C′ =< C, C(B) > we have C′ ⊇ C. Also, it is straightforward to verify that an element 0 ≠ c ∈ Rad(C) generates a nilpotent left ideal in C′ as well, therefore Rad(C′) ≠ 0. This implies that C′ ⊂ B and hence C′ = C and C ⊇ C(B).

We infer that C contains the identity elements e_{i} ∈ B_{i} of the ideals B_{i} and consequently we have C = e_{1}C ⊕ ⋯ ⊕ e_{r}C. Now the maximality of C implies the existence of an index i, such that e_{i}C is a maximal subalgebra of the simple algebra B_{i} and e_{j}C = B_{j}, if j ≠ i. Clearly we have Rad(e_{i}C) = Rad(C) ≠ 0. Now a two sided ideal J_{i} of e_{i}C minimal among those containing Rad(e_{i}C) which is a left ideal of B_{i} will clearly suffice as J.

For the rest of the proof we assume that B is a simple algebra. Let V be a simple left B-module, and let D stand for the algebra of B-endomorphisms of V. By Schur’s lemma D is a division algebra over the field F and V is a right D-space. Moreover, we have B = End_{D}V and hence Rad(C)V ≠ 0. We define the strictly decreasing chain of D-subspaces V = V_{0} ⊃ V_{1} ⊃ V_{2} by V_{i+1} = Rad(C)V_{i}, for i = 0, 1. From this chain of subspaces we obtain a decreasing chain of subalgebras B = B_{0} ⊇ B_{1} ⊇ B_{2} by letting

B_{i} = {x ∈ B | xV_{j} ⊆ V_{j} for j = 0, …, i}.

Here B ≠ B_{1} follows from B = End_{D}V. Moreover, B_{2} ⊇ C implies that B_{1} = B_{2} = C. We infer that V_{2} = 0 and (Rad(C))^{2} = 0.

Then the annihilator J = {x ∈ B | xV_{1} = 0} is properly contained in B_{1} = C, and in fact is a two-sided ideal of C. It is also obvious, that J is a left ideal of B, and this implies that J ⊃ Rad(C). From B = End_{D}V we obtain that C/Rad(C) ≅ End_{D}V_{1} ⊕ End_{D}V/V_{1}. Thus, C/Rad(C) is a semisimple algebra with exactly two minimal ideals, implying the minimality of J over Rad(C). □

Theorem 6.3.5 Let Λ ⊂ Γ be R-orders in A. Suppose that Λ is extremal and Γ is minimal among the R-orders properly containing Λ. Then there exists an ideal I of Λ minimal among those containing Rad(Λ) such that O_{l}(I) ⊇ Γ.

Proof By Propositions 6.3.3 and 6.2.3 we have that C = Λ/Rad(Γ) is a maximal proper subalgebra of the semisimple F = R/P -algebra B = Γ/Rad(Γ). Moreover Rad(C) ≠ 0, since Λ ⊂ Γ and Λ is extremal. We can apply Lemma 6.3.4. There exists a minimal ideal J of C above Rad(C) such that J is a left ideal in B. Now I, the inverse image of J with respect to the natural map Γ → B clearly satisfies the requirements of the theorem. □

6.4 Computing maximal orders

Let R = ℤ or R = 𝔽_{q}[X], K be the field of quotients of R (i.e., K = ℚ, or K = 𝔽_{q}(X), respectively), L be a finite separable extension of K, A be a finite dimensional separable L-algebra, and Λ is an R-order in A. Let D stand for the integral closure of R in L. Suppose that A is given by structure constants over L and Λ is given by an R-basis.

Suppose further that we are given a prime element π ∈ R (π is a rational prime in case R = ℤ, or an irreducible polynomial over 𝔽_{q} in case R = 𝔽_{q}[X]).

Theorem 6.4.1 There exists an f-algorithm running in time (size(A) + size(Λ) + size(π))^{O(1)} that produces an R-basis of an R-order Γ ⊃ Λ such that Γ_{(π)} ⊃ Λ_{(π)} provided that Λ is not maximal at π. The f-oracle is employed to factor polynomials over R/(π).

Proof We shall test first whether Λ_{(π)} is an extremal R_{(π)}-order by checking if O_{l}(Rad(Λ_{(π)})) = Λ_{(π)}. If not, then we construct an R-order Γ ⊃ Λ such that Γ_{(π)} ⊃ Λ_{(π)}. If Λ_{(π)} passes the test, then we use the following test based on Theorem 6.3.5. If there exists an ideal J minimal among the ideals properly containing Rad(Λ_{(π)}) such that O_{l}(J) ⊃ Λ_{(π)}, then we construct an R-order Γ ⊃ Λ such that Γ_{(π)} ⊃ Λ_{(π)}. Otherwise we correctly conclude that Λ is maximal at π.

As for the first test, we compute the inverse image I ⊆ Λ of Rad(Λ_{(π)}) with respect to the embedding Λ → Λ_{(π)}. By Lemma 6.1.9, Λ passes the first test if and only if O_{l}(I) = Λ. Otherwise Γ = O_{l}(I) is an order containing Λ such that Γ_{(π)} ⊃ Λ_{(π)}.

We shall work with the finite algebra B = Λ/πΛ over the finite field F = R/(π). We have size(F) = size(π)^{O(1)}, dim_{F} B ≤ dim_{K}A = n and structure constants for B are easily obtained, size(B) = (size(A) + size(Λ) + size(F))^{O(1)}. From Propositions 6.2.1 and 6.1.5 we infer that I is the inverse image of Rad(B) with respect to the canonical map Λ → B. Rad(B) can be computed in deterministic time (n + size(F))^{O(1)} with the method of [Ró2]. From an F -basis of Rad(B) we can efficiently find an R-basis of I. (Note that any Rsubmodule M such that πΛ ⊆ M ⊆ Λ has a basis of size bounded by (size(Λ)+size(π))^{O(1)}). Also, by Proposition 6.1.8 we can compute O_{l}(I) efficiently. This finishes the description of the first test.

The second test can be treated in a similar way. Let J_{1}, …, J_{m} denote the minimal ideals of B which contain Rad(B). Note that these ideals are the inverse images, with respect to the canonical map ϕ : B → B/Rad(B), of the minimal ideals of the semisimple algebra B/Rad(B). We have m ≤ n. Let I_{i} denote the inverse image in Λ of J_{i} with respect to the map Λ → B. Propositions 6.1.5 and 6.2.1 imply that I_{1}, …, I_{m} are also the inverse images of the minimal ideals of Λ_{(π)} over Rad(Λ_{(p)}). As in the first case, we obtain that we have to compute the rings O_{l}(I_{i}) for i = 1, …, m. We can stop when Λ ⊂ O_{l}(I_{i}) is detected because then we have an order properly containing Λ.

The ideals J_{i} are obtained by the f-algorithm of Friedl and Rónyai (see [FR, Ró2]). The time requirement is (n + log p)^{O(1)} and we call the f-oracle to factor polynomials over 𝔽_{p}. From the ideals J_{i} the ideals I_{i} and the rings O_{l}(I_{i}) can be computed in deterministic time (size(A) + size(Λ) + log p)^{O(1)}. The description of the algorithm and the proof of Theorem 6.4.1 is complete. □

With the method of Theorem 6.4.1 we can construct a maximal R-order in A as follows. First we need a starting R-order. Let a_{1}, …, a_{n} be the input basis of A over K. Let d be lowest common denominator of the structure constants with respect to this basis. Then the R-module Λ generated by 1_{A}, da_{1}, …, da_{n} is an R-order in A. (This is the same trick that was used in Section 1.2 to make structure constants integral.) We put u = det (tr_{A/K}(d^{2}a_{i}a_{j}))_{i,j=1}^{n}. The elements tr_{A/K}(a_{i}a_{j}) can be computed if we know the Wedderburn decomposition of A over K. In the case K = ℚ, the Wedderburn decomposition can be computed in deterministic polynomial time (cf. [FR]). In the case K = 𝔽_{q}(X), this task can be performed by the deterministic polynomial time f-algorithm of Theorem 4.1.3. Now u is a multiple of disc(Λ), whence, by Proposition 6.1.3, Λ is maximal at every prime π not dividing u. Let S be the set of primes in R dividing u. S is obtained by factoring u in R.

Repeated application of Theorem 6.4.1 gives a sequence of R-orders

Λ = Γ_{0} ⊂ Γ_{1} ⊂ … ⊂ Γ_{m}

until a maximal R-order is obtained. By Proposition 6.1.10, m ≤ \frac{1}{2} log_{2} |u| if K = ℚ and m ≤ \frac{1}{2}deg u if K = 𝔽_{q}[X]. We can control sizes during the iteration. By Proposition 6.1.3 we have Λ ⊆ Γ_{j} ⊆ \frac{1}{u}Λ, therefore Γ_{j} can be represented by an R-basis admitting a short description.

Theorem 6.4.2 Let A be a finite dimensional separable algebra over K given by structure constants.

(a) If K = ℚ, then a maximal ℤ-order Λ can be constructed by an ff-algorithm running in time size(A)^{O(1)}.

(b) If K = 𝔽_{q}(X), then a maximal 𝔽_{q}[X]-order Λ can be constructed by an f-algorithm running in time size(A)^{O(1)}. □

Corollary 6.4.3 Let L be a finite separable extension of K and A a be finite dimensional central simple algebra over L. Let D denote the integral closure of R in L. Suppose that A is given by structure constants over L. Then a maximal D-order Λ in A can be constructed

(a) by an ff-algorithm running in time size(A)^{O(1)}, if R = ℤ.

(b) by an f-algorithm running in time size(A)^{O(1)}, if R = 𝔽_{q}[X].

Proof From K and the structure constants of A over L we can readily obtain structure constants of A over K. With the method of Theorem 6.4.2 we compute an R-basis of a maximal R-order Λ of A. By Lemma 6.1.6 we conclude that Λ is a maximal D-order as well. □

Corollary 6.4.3 (a) gives an affirmative answer to the question proposed in [Ró3].

6.5 Computing indices

First we recall some standard material related to valuations and completions (cf. [Re], Section 5). Assume that A is a central simple K-algebra of dimension n^{2}. Let ϕ be a valuation of K. We consider the completions K_{ϕ} and A_{ϕ} = K_{ϕ}⊗_{K}A, respectively. It is easy to see that A_{ϕ} is a central simple K_{ϕ}-algebra of dimension n^{2}, therefore index(A_{ϕ}) = m_{ϕ} for some m_{ϕ}|n, i.e., A_{ϕ} ≅ M_{n/m_{ϕ}}(D_{ϕ}), where D_{ϕ} is a central skewfield over K_{ϕ} with dim_{K}D_{ϕ} = m_{ϕ}^{2}. We call the index m_{ϕ} the local index of A at the valuation ϕ. Since for every central simple K-algebra B we have M_{r}(B)_{ϕ} = M_{r}(B_{ϕ}), the local index m_{ϕ} is in fact a divisor of index(A).

Assume that ϕ is a nonarchimedean valuation of K. Then R_{ϕ} = {x ∈ K^{∗}|ϕ(x) ≤ 1} is a subring of K, called the valuation ring of ϕ. P_{ϕ} = {x ∈ K^{∗}|ϕ(x) < 1} is the unique maximal ideal in R_{ϕ}, called the valuation ideal. If ϕ is a discrete valuation, then R_{ϕ} is a discrete valuation ring, i.e., the only prime ideal of R_{ϕ} is P_{ϕ}. Assume further that the residue class field R_{ϕ}/P_{ϕ} is finite. This holds for every nonarchimedean valuation of a global field K. (In fact, global fields can be characterized with this property.) The following statement, based on the classification of division algebras over local fields (cf. [Re], Chapter 3) and the theory of maximal orders over discrete valuation rings (cf. [Re], Chapter 5), relates the local index m_{ϕ} of A to the structure of maximal R_{ϕ}-orders in A.

Proposition 6.5.1 Let ϕ be a discrete valuation of K such that the residue class field R_{ϕ}/P_{ϕ} is finite and Λ be a maximal R_{ϕ}-order in the central simple K-algebra A of dimension n^{2}. Then Rad(Λ) is the a unique maximal two-sided ideal in Λ,

P_{ϕ}Λ = (Rad(Λ))^{m_{ϕ}}, and Λ/Rad(Λ) ≅ M_{t}(B),

where B is a field extension of R_{ϕ}/P_{ϕ} of degree m_{ϕ} and t = n/m_{ϕ}.

Proof Let S_{ϕ} be the valuation ring of the valuation ϕ of the field K_{ϕ}, and Q_{ϕ} be the maximal ideal of S_{ϕ}. Let Ω = S_{ϕ} ⊗_{R_{ϕ}} Λ. By [Re], Thm. 11.5, Ω is a maximal S_{ϕ}-order in A_{ϕ}, and by [Re], Thm. 18.7, Rad(Λ) = Λ ∩ Rad(Ω), whence Λ/Rad(Λ) ≅ Ω/Rad(Ω).

By [Re], Thm. 17.3, Ω is conjugate by an inner automorphisms of A_{ϕ} to the order M_{t}(Δ), where A_{ϕ} ≅ M_{t}(D), D is a central skewfield over A_{ϕ} of index m_{ϕ} and Δ is the unique maximal S_{ϕ}-order in D. We have

Λ/Rad(Λ) ≅ Ω/Rad(Ω) ≅ M_{t}(Δ/Rad(Δ)).

By [Re], Thm 14.3, B = Δ/Rad(Δ) is an extension field of degree m_{ϕ} of S_{ϕ}/Q_{ϕ} ≅ R_{ϕ}/P_{ϕ}, and Rad(Δ)^{m_{ϕ}} = Q_{ϕ}Δ. If we identify Ω with M_{t}(Δ), we have Rad(Ω) = M_{t}(Rad(Δ)) and

Q_{ϕ}Ω = M_{t}(Q_{ϕ}Δ) = M_{t}((Rad(Δ))^{m_{ϕ}}) = M_{t}((Rad(Δ)))^{m_{ϕ}} = (Rad(Ω))^{m_{ϕ}}.

It follows that

P_{ϕ}Λ = Λ ∩ Q_{ϕ}Ω = Λ ∩ (Rad(Ω))^{m_{ϕ}}) = (Λ ∩ Rad(Ω))^{m_{ϕ}} = (Rad(Λ))^{m_{ϕ}}.

□

Assume that R is a Dedekind domain with quotient field K. If R is contained in the valuation ring R_{ϕ} of ϕ (i.e., ϕ(x) ≤ 1 for every x ∈ R) then P = R∩P_{ϕ} = {x ∈ R|ϕ(x) < 1} is a maximal ideal in R and ϕ is equivalent to the usual P -adic valuation ϕ_{P} of K. We say in this case that ϕ corresponds to the prime ideal P of R. We call the local index m_{ϕ_{P}} the local index at P and denote it by m_{P}.

From now on, we assume that R = ℤ or R = 𝔽_{q}[X], K is the quotient field of R and A is a separable K-algebra. First we give a method to compute the local indices of simple separable algebras over global fields. (Recall that the simple components of a semisimple ℚ-algebra can be computed by the deterministic polynomial time method of [FR], while the analogous task for algebras over 𝔽_{q}(x) can be done by the deterministic polynomial time f-algorithm of Theorem 4.1.3.)

Assume that the center of A is L, a finite separable extension of K. Let D be the integral closure of R in L. The following simple statement tells us, that we do not have to care about local indices at primes not dividing the discriminant of an order.

Proposition 6.5.2 Let A be a central simple algebra over L, a finite separable extension of K. Let D be the integral closure of R in A. Assume that Λ is an R-order in A. Assume that for some prime ideal P in D above the prime π ∈ R we have m_{P} > 1. Then π|disc_{K}(Λ).

Proof Assume that π does not divide the discriminant. The R/(π)-algebra Λ/πΛ has a nonsingular bilinear trace form, whence it is semisimple. Therefore its factor Λ/P Λ ≅ Λ_{P} /P Λ_{P} is also semisimple implying that Rad(Λ)_{P} = P Λ_{P}. On the other hand, by Proposition 6.5.1 we have P Λ_{P} = (Rad(Λ)_{P})^{m_{P}}, giving that m_{P} = 1. □

Note that in [Re], Theorem 32.1 an exact formula is given for the factorization of the discriminant of a maximal order. This would make possible to compute local indices from the discriminant of a maximal order, as it is done in [Ró3]. We show instead a method based on the structure of the factor of a locally maximal order by the radical.

Proposition 6.5.3 Given a finite separable extension L of K, a central simple algebra A over L, and a prime π ∈ R, we can compute the set of local indices of A at primes of D above π by a deterministic polynomial time f-algorithm.

Proof With the f-algorithm of Theorem 6.4.1, we first compute an R-order Λ in A which is locally maximal at π. Hereon we perform computations in the factor ring B = Λ/πΛ. B is a finite dimensional algebra over the finite field R/(π). We compute the subalgebra C ≅ (Λ ∩ L)/(πΛ ∩ L), the image of Λ ∩ L by the natural map. We use the method of [Ró2] to compute Rad(C). Using the f-algorithm of [FR] for decomposing C/Rad(C), we can find the maximal ideals of C. By Lemma 6.1.7, these ideals correspond to the prime ideals of D over π. For every such ideal M (corresponding to the D-ideal P), we compute the factor ring B/MB. By Lemma 6.1.7, this ring is isomorphic to Γ/P Γ, where Γ = DΛ. By Proposition 6.5.1, the radical-free part of Γ_{P} /P Γ_{P} ≅ Γ/P Γ is a full matrix algebra over an extension of degree m_{P} of D/P. Therefore, by Lemma 6.1.7, the index m_{P} can be obtained as the dimension of the center of the radical-free part of B/MB over the field C/M. □

The last two statements suggest a method to compute the set of all local indices for valuations corresponding to prime ideals in D based on factoring the discriminant of a starting order. This leads to a deterministic polynomial time ff-algorithm in case R = ℤ, or a deterministic polynomial time f-algorithm in case R = 𝔽_{q}[X]. Note that we do not need to compute the ring D.

We show how to compute the local indices for valuations not corresponding to primes in R. If ϕ is archimedean, then, at least in the cases we considered, we may assume that K = ℚ, and the completion L_{ϕ} corresponds to an embedding L → ℂ. In that case L_{ϕ} ≅ ℂ or L_{ϕ} ≅ ℝ, and the only possible proper skewfield is that of the Hamiltonian quaternions (only in the case L_{ϕ} ≅ ℝ). We can use Eberly’s randomized polynomial method ([Eb3]) to determine the set of local indices at nonarchimedean primes. Since in [Eb3] randomization is used only at the point of finding splitting elements, using the results of Section 5.5 (or even using [Ró5]) we can derandomize it. The nonarchimedean valuations of an algebraic number field L correspond to prime ideals in the ring D of algebraic integers in L, therefore they can be treated by the method of Proposition 6.5.1.

If K = 𝔽_{q}(x), then every valuation of L is discrete. If ϕ(X) ≤ 1 then 𝔽_{q}[X] and its integral closure D belong to the valuation ring, the case treated by the method of Proposition 6.5.1. On the other hand, ϕ(X) > 1 implies

ϕ(\frac{g(X)}{h(X)}) = 2^{(deg g(X)−deg h(X)) log_{2} ϕ(X)}.

It follows that ϕ(\frac{1}{X}) < 1 and ϕ corresponds to the prime ideal (\frac{1}{X}) in the ring 𝔽_{q}[\frac{1}{X}]. This case can be treated as above by using 𝔽_{q}[\frac{1}{X}] in place of 𝔽_{q}[X].

We use the following reformulation (cf. [Re], Theorem 32.19) of the celebrated and deep Albert–Brauer–Hasse–Noether theorem.

Theorem. If A is a central simple algebra over the global field L, then

index(A) = lcm_{ϕ}m_{ϕ},

where ϕ runs over the valuations of L.

Corollary 6.5.4 The index of the separable simple algebra A over K can be computed by a polynomial time

(a) ff-algorithm if K = ℚ;

(b) f-algorithm if K = 𝔽_{q}[X].

Next we give an application to group representations. Suppose that K is an algebraic number field. Let G ≤ GL_{n}(K) be a finite matrix group given by a finite set Γ ⊆ GL_{n}(K) of matrices generating G. We assume the dense representation (cf. Section 1.1) of K, elements of K and matrices over K. Note that finiteness of G can be tested by the deterministic polynomial time method of [BBR]. By Maschke’s theorem, the action of G on V = K^{n}, the K-space of column vectors of length n over K, is completely reducible. We are interested in computing the dimensions of the irreducible constituents.

Theorem 6.5.5 We can compute the dimensions of the irreducible constituents of the action of G on K^{n} in deterministic polynomial time.

Proof Let A be the K-subalgebra of M_{n}(K) generated by Γ. A basis of A can be computed in deterministic polynomial time. By Maschke’s theorem, A is semisimple. With the deterministic polynomial time method of [FR] we can compute the simple components A_{1}, …, A_{r} of A together with the centers K_{1}, …, K_{r} of these components. Setting V_{1} = A_{1}V, …, V_{r} = A_{r}V, we have V = V_{1} ⊕…⊕V_{r}, where for every i = 1, …, r, the irreducible constituents of V_{i} are isomorphic to a minimal left ideal L_{i} of A_{i}, whence the dimension of an irreducible constituent of V_{i} is

dim_{K}L_{i} = dim_{K}K_{i}dim_{K_{i}}L_{i} = dim_{K}K_{i}indexA_{i}\sqrt{dim_{K_{i}}A_{i}}.

Applying the projections A → A_{i} to the generators in Γ, our task is reduced to r instances of the problem of computing the index of A in the special case where the K-algebra A generated by Γ is a central simple algebra over K (this K may be different from the field we started with). In that case A is isomorphic to a simple component of the group algebra KG. Let D stand for the ring of algebraic integers in K. It is known (cf. [Re], Section 41) that if p is a prime not dividing |G|, and P is a prime in D above p, then the local index of every simple component of KG at P is 1. In fact, the ℤ-lattice Λ generated by D and Γ is a D-order in A with Λ/P Λ ≅ M\sqrt{dim_{K}A}(D/P).

It follows that it is enough to compute the local indices of A at the archimedean valuations and at the primes P of D above rational primes p such that p divides |G|. It is known that these primes are small. Indeed, using the regular representation of K over ℚ, we may think of elements of G as elements of M_{ndim_{ℚ}K}(ℚ). Let g ∈ G be an element of G of prime order p. Then g is a root of the cyclotomic polynomial \frac{X^{p}−1}{X−1}, which is irreducible over ℚ, therefore \frac{X^{p}−1}{X−1} divides the characteristic polynomial of g, whence p−1 ≤ ndim_{ℚ}K. Therefore it suffices to compute the local indices at primes above rational primes p ≤ ndim_{ℚ}K + 1. Using the f-algorithm of 6.4.1, for every prime p ≤ ndim_{ℚ}K + 1 we compute an order Λ in A such that Λ is locally maximal at p. The f-oracle for factoring polynomials over 𝔽_{p} can be replaced with the deterministic (dim_{ℚ}A + p)^{O(1)}-time method of Berlekamp (cf. [Ber3]). □

Applying this to the regular representation of G we immediately obtain

Corollary 6.5.6 Let K be an algebraic number field given by the monic minimal polynomial f ∈ ℤ[x] of an integral element α ∈ K such that K = ℚ(α). Let G be a finite group given by its multiplication table. Then the degrees of the irreducible representations of G over K can be computed in deterministic time (size(f) + |G|)^{O(1)}. □

Finding isomorphism with M_{2}(ℤ)

The problem of finding a minimal left ideal in a simple algebra remains open in general; even it is not known if a zero divisor of polynomial size exists. Rónyai [Ró1] has proved that the simplest case, i.e., finding a zero divisor in a simple non-commutative 4-dimensional ℚ-algebra is essentially as hard as the problem of decomposing integers into prime factors. The results of the previous chapter suggest that finding certain maximal orders may bring us closer to finding minimal left ideals. Here, based on the paper [ISz] (joint work with Ágnes Szántó), we present evidence in favour of this approach: If we are given a maximal order in an algebra isomorphic to M_{2}(ℚ), i.e., a subring isomorphic to M_{2}(ℤ), then we can find a zero divisor in it in deterministic polynomial time.

Our method is based on a kind of basis reduction with respect to the bilinear trace form of the algebra. The algorithm may be of independent interest. A. K. Lenstra, H. W. Lenstra and L. Lovász (see [LLL] and [Lo]) have constructed a polynomial time algorithm to reduce a positive definite integral quadratic form, i.e., to produce a basis of a full lattice L in an n-dimensional ℝ-vector space V equipped with a positive definite bilinear function with integer values on L, such that the matrix of the bilinear function with respect to this basis consists of integers of absolute values bounded by a constant depending only on the discriminant and the dimension. It turns out, that their algorithm can be extended to the case of non-degenerate indefinite forms. The original algorithm has to be modified only at points where isotropic vectors occur.

Section 7.1 contains the definitions, the reduction algorithm and the main properties of reduced bases. In Section 7.2, we show how a basis reduced with respect to the bilinear trace form of a ring isomorphic to M_{2}(ℤ) can be used to find a zero divisor.

7.1 Basis reduction

A lattice L in ℝ^{n} is a free abelian subgroup generated by an ℝ-basis of ℝ^{n}. A basis of L is a free generating set, i.e., an ℝ-basis of ℝ^{n} generating the additive group L. Let L be a lattice in V = ℝ^{n} and ⟨ , ⟩ : V × V → ℝ a symmetric bilinear function taking integer values on L. The discriminant of L is defined by

disc(L) := |det (⟨b_{i}, b_{j}⟩)_{i,j=1}^{n}|

where (b_{1}, …, b_{n}) is a basis of L. It is known that the discriminant is independent of the choice of the basis of L, and disc(L) ∈ ℕ. The function (form) ⟨ , ⟩ is called degenerate if the discriminant disc(L) is zero. In this paper we assume that ⟨ , ⟩ is non-degenerate, i.e., disc(L) ≠ 0. A nonzero vector x ∈ V is called isotropic if ⟨x, x⟩ = 0, anisotropic if ⟨x, x⟩ ≠ 0. Since ⟨ , ⟩ is assumed to be non-degenerate, isotropic vectors can exist only in the indefinite case, i.e. when ⟨x, x⟩ takes positive as well as negative values.

Our aim is to find a basis (b_{1}, …, b_{n}) of L such that the matrix (⟨b_{i}, b_{j}⟩)_{i,j=1}^{n} consists of integers of “small” absolute values. There exist classical reduction methods (introduced by Hermite for definite forms; for an extension to indefinite forms the reader is referred to [Ca], Section 9.3) based on choosing b_{1} such that |⟨b_{1}, b_{1}⟩| is as small as possible and then recursively continuing the procedure in the component of L orthogonal to b_{1}. The main difficulty with this classical approach is in finding a shortest vector. This task is known to be NP-hard. The key idea in [LLL] is to replace the notion of reducedness in the sense of Hermite by an algorithmically tractable requirement.

Let us try first to imitate the LLL reduction algorithm and to extend the main results. To ensure correctness, we assume that all the denominators appearing are nonzero and postpone the discussion of the modifications necessary to cover the exceptional cases.

We will extensively use some notational conventions related to the Gram–Schmidt orthogonalization of a basis (b_{1}, …, b_{n}) of L.

b_{1}^{∗} := b_{1}, b_{i}^{∗} := b_{i} − ∑_{j=1}^{i−1} \frac{⟨b_{i}, b_{j}^{∗}⟩}{⟨b_{j}^{∗}, b_{j}^{∗}⟩}b_{j}^{∗} (i = 2, …, n),

i.e., b_{i}^{∗} is the component of b_{i} orthogonal to the subspace generated by {b_{1}, …, b_{i−1}}. For the quotients \frac{⟨b_{i},b_{j}^{∗}⟩}{⟨b_{j}^{∗},b_{j}^{∗}⟩}, 1 ≤ j ≤ i ≤ n we will also use the notation μ_{ij}. We have b_{i} = ∑_{j=1}^{i} μ_{ij}b_{j}^{∗}. More generally, let b_{i}(j) denote the component of b_{i} orthogonal to the subspace generated by b_{1}, …, b_{j−1}, i.e.

b_{i}(j) = \{ \begin{matrix}b_{i} − ∑_{t=1}^{j−1} \frac{⟨b_{i},b_{t}^{∗}⟩}{⟨b_{t}^{∗},b_{t}^{∗}⟩}b_{t}^{∗} & if j ≤ i \\ 0 & if j > i. \end{matrix}

In particular, b_{i}^{∗} = b_{i}(i). Note that the vector b_{i}^{∗} depends only on b_{i} and the sublattice L_{i−1} generated by b_{1}, …, b_{i−1}.

A basis is b_{1}, …, b_{n} is called reduced in the sense of LLL if

(1) |μ_{ij}| ≤ \frac{1}{2} for every 1 ≤ j < i ≤ n, and

(2) |⟨b_{i}(i), b_{i}(i)⟩| ≤ \frac{4}{3}|⟨b_{i+1}(i), b_{i+1}(i)⟩| for every 1 ≤ i < n.

Bases satisfying property (1) are called proper. Besides properness, the following consequence of (1) and (2) is crucial in estimates:

(2′) |⟨b_{i+1}^{∗}, b_{i+1}^{∗}⟩| ≥ c|⟨b_{i}^{∗}, b_{i}^{∗}⟩| for every 1 ≤ i < n

with some constant c < 1. (Actually, c = \frac{1}{2}.) The proof of this is identical to the proof for definite forms in [LLL]. In fact, (2′) follows from

\frac{3}{4}|⟨b_{i}^{∗}, b_{i}^{∗}⟩| ≤ |⟨b_{i+1}(i), b_{i+1}(i)⟩| = |⟨b_{i+1}^{∗}, b_{i+1}^{∗}⟩ + μ_{i+1,i}^{2}⟨b_{i}^{∗}, b_{i}^{∗}⟩|
≤ |⟨b_{i+1}^{∗}, b_{i+1}^{∗}⟩| + \frac{1}{4}|⟨b_{i}^{∗}, b_{i}^{∗}⟩|.

From a basis b_{1}, …, b_{n}, it is easy to construct a proper basis such that the Gram–Schmidt orthogonalization results in the same basis b_{1}^{∗}, …, b_{n}^{∗}:

      for i := 1 to n do

          for j := i − 1 downto 1 do

b_{i} := b_{i} − mb_{j} where m is the nearest integer to μ_{ij}

A reduced basis is obtained by repeating the following rounds:

- properness is achieved/maintained with the above procedure;

- we swap b_{i} and b_{i+1} if property (2) does not hold for i.

The crucial part of the analysis of the algorithm relies on the fact that the quantity

∏_{i=1}^{n} disc(L_{i}) = ∏_{i=1}^{n} ∏_{j=1}^{i} |⟨b_{j}^{∗}, b_{j}^{∗}⟩|

is reduced by a factor less than \frac{3}{4} in every execution of the swapping step.

Now we have to treat the “exceptions”: First of all, the definition of b_{i}^{∗} and b_{i}(j) will only work as long as we have ⟨b_{i}^{∗}, b_{i}^{∗}⟩ ≠ 0, since the orthogonalization procedure stops as soon as an isotropic vector b_{i}^{∗} is found. This happens at the first index i such that our form restricted to the subspace L_{i} is degenerate, since disc(L_{i}) = ∏_{j=1}^{i}⟨b_{j}^{∗}, b_{j}^{∗}⟩. A basis (b_{1}, …, b_{n}) is called singular, if there is an i, 1 ≤ i ≤ n, such that disc(L_{i}) = 0. We intend to work only with nonsingular bases, i.e., when ⟨ , ⟩ restricted to L_{i} is non-degenerate for i = 1, …, n.

Finding a nonsingular basis very close to a given singular one appears to be an easy task: Let i be the lowest index such that ⟨b_{i}^{∗}, b_{i}^{∗}⟩ = 0. The vectors b_{1}^{∗}, …, b_{i}^{∗} together with b_{i+1}(i), …, b_{n}(i) form a basis of V. The non-degeneracy of ⟨ , ⟩ implies that b_{i}^{∗} cannot be orthogonal to every element of that basis, hence i < n and there exists some j, i < j ≤ n, such that ⟨b_{i}^{∗}, b_{j}(i)⟩ ≠ 0. Since

⟨b_{i}^{∗}, b_{j}(i)⟩ = \frac{1}{4}(⟨b_{i}^{∗} + b_{j}(i), b_{i}^{∗} + b_{j}(i)⟩ + ⟨b_{i}^{∗} − b_{j}(i), b_{i}^{∗} − b_{j}(i)⟩),

there exists ϵ = ±1 such that b_{i}^{∗} + ϵb_{j}(i) is anisotropic. But this vector is nothing else than the component of the lattice vector b_{i} + ϵb_{j} orthogonal to the subspace generated by b_{1}, …, b_{i−1}, thus by replacing b_{i} with b_{i} + ϵb_{j}, we obtain a basis of L such that for all 1 ≤ k ≤ i, ⟨b_{k}^{∗}, b_{k}^{∗}⟩ ≠ 0. Iterating this step at most n − 1 times a nonsingular basis is obtained.

We prepend this procedure to the usual reduction algorithm to ensure that it works with nonsingular bases. Observe that the procedure for making bases proper preserves nonsingularity.

Let us examine the reduction step related to condition (2) of reducedness. Swapping b_{i} and b_{i+1} does not affect the sublattices L_{j} for j ≠ i and replaces b_{i}^{∗} with b_{i+1}(i), thus it preserves nonsingularity except when b_{i+1}(i) is isotropic. Then we shall find another lattice vector on the line b_{i} − zb_{i+1} with short complement b_{i}^{∗} − zb_{i+1}(i) to replace b_{i}, except in the (very explicit) case when

|μ_{i+1,i}| = |\frac{⟨b_{i}^{∗}, b_{i+1}(i)⟩}{⟨b_{i}^{∗}, b_{i}^{∗}⟩}| = \frac{1}{2}.

If |μ_{i+1,i}| < \frac{1}{2}, then we choose z to be the nearest integer to \frac{1}{2μ_{i+1},i}, so that

|z − \frac{1}{2μ_{i+1}, i}| < \frac{1}{2} < \frac{1}{4|μ_{i+1,i}|}.

This implies that 0 < 1−2zμ_{i+1,i} < \frac{1}{2}, hence for the complement b_{i}^{∗}−zb_{i+1}(i) of b_{i}−zb_{i+1}(i) orthogonal to b_{1}, …, b_{i−1} we have

\frac{|⟨b_{i}^{∗} − zb_{i+1}(i), b_{i}^{∗} − zb_{i+1}(i)⟩|}{|⟨b_{i}^{∗}, b_{i}^{∗}⟩|} = \frac{|⟨b_{i}^{∗}, b_{i}^{∗}⟩ − 2z⟨b_{i}^{∗}, b_{i+1}(i)⟩|}{|⟨b_{i}^{∗}, b_{i}^{∗}⟩|} = |1 − 2zμ_{i+1,i}| < \frac{1}{2}.

The argument also shows that b_{i}^{∗} −zb_{i+1}(i) is anisotropic. Thus, the quantity ∏_{i=1}^{n} disc(L_{i}) is reduced here by a factor less than \frac{1}{2}, rather than \frac{3}{4}. On the other hand, if |μ_{i+1,i}| = \frac{1}{2}, then we have

|⟨b_{i+1}^{∗}, b_{i+1}^{∗}⟩| = |⟨b_{i+1}(i) − μ_{i+1,i}b_{i}^{∗}, b_{i+1}(i) − μ_{i+1,i}b_{i}^{∗}⟩|
= |μ_{i+1,i}^{2}⟨b_{i}^{∗}, b_{i}^{∗}⟩ − 2μ_{i+1,i}⟨b_{i}^{∗}, b_{i+1}(i)⟩|
= | − μ_{i+1,i}^{2}⟨b_{i}^{∗}, b_{i}^{∗}⟩| = \frac{1}{4}|⟨b_{i}^{∗}, b_{i}^{∗}⟩|,

thus (2′) is satisfied with c = \frac{1}{4}. As a conclusion, the reducedness of a basis b_{1}, …, b_{n}

with respect to a possibly indefinite form ⟨ , ⟩ coincides with the original notion with the following modifications:

(0) the basis must be nonsingular,

(1) coincides with the original notion of properness, (2a) same as (2) for indices i, such that ⟨b_{i+1}(i), b_{i+1}(i)⟩ ≠ 0, (2b) |μ_{i+1,i}| = \frac{1}{2} for indices i, such that ⟨b_{i+1}(i), b_{i+1}(i)⟩ = 0.

We have the following method to find a reduced basis:

- we find a nonsingular basis and repeat the following rounds:

- achieve/maintain properness

- make changes described above if the test (2a) or (2b) of reducedness fails for some index i.

Theorem 7.1.1 Given a basis (a_{1}, …, a_{n}) of a lattice L together with the symmetric regular integer matrix (⟨a_{i}, a_{j}⟩)_{i,j=1}^{n} specifying the non-degenerate integral symmetric bilinear function ⟨ , ⟩ on L, the algorithm above finds a reduced basis of L in time polynomial in the input size.

The proof follows very closely the argument from [LLL]. There are only a few points where we have to take into consideration the possible indefiniteness of the form. For this reason, we only sketch here the main differences from the reasoning in [LLL]. The complete proof is relegated to the Appendix.

Proof (Sketch) We have seen how to achieve nonsingularity efficienlty. in the case of failure at test (2b), the “length” of the new b_{i}^{∗} is less than half of the original one, thus the quantity ∏_{j=1}^{n} disc(L_{j}) is reduced by a factor less than \frac{1}{2} (rather than \frac{3}{4}). It follows that on the number of arithmetical operations we have bounds similar to the LLL algorithm.

Except for the coordinates of vectors, we obtain similar bounds (they are slightly worse because of indefiniteness) on the numbers (e.g., the values ⟨b_{i}, b_{j}⟩, numerators and denominators of μ_{ij}) as in the definite case. While definiteness would automatically imply bounds on the coordinates of vectors based purely on bounds on the length, this is no longer true in the indefinite case. Instead, we have to argue as follows: A single round of the algorithm results in a transformation matrix with entries of size bounded polynomially by the size of the values ⟨b_{i}, b_{j}⟩ for the basis b_{1}, …, b_{n} that we have at the entry point of the round. But these bounds can be turned into (also polynomial) bounds in terms of the initial input. Since we have polynomially many rounds, the result (and the intermediate transformation matrices) will be a product of polynomially many matrices of polynomial size, again a matrix of polynomial size. □

Reduced bases have the following properties:

Theorem 7.1.2 Let (b_{1}, …, b_{n}) be a reduced basis of L. Then for every 1 ≤ i ≤ j ≤ n,

|⟨b_{i}, b_{j}⟩| ≤ (2^{n−2} + 2^{n−i−1})disc(L)^{1/(n−i+1)} ≤ 2^{n}disc(L)^{1/(n−i+1)}.

Proof

disc(L) = ∏_{j=1}^{n} |⟨b_{j}^{∗}, b_{j}^{∗}⟩| = ∏_{j=1}^{i−1} |⟨b_{j}^{∗}, b_{j}^{∗}⟩| ∏_{j=i}^{n} |⟨b_{j}^{∗}, b_{j}^{∗}⟩| = disc(L_{i−1}) ∏_{j=i}^{n} |⟨b_{j}^{∗}, b_{j}^{∗}⟩|
≥ ∏_{j=i}^{n} |⟨b_{j}^{∗}, b_{j}^{∗}⟩| ≥ ∏_{j=i}^{n} 4^{−(j−i)}|⟨b_{i}^{∗}, b_{i}^{∗}⟩|,

the latter inequality follows from the fact that (2′) holds with c = \frac{1}{4}. Hence

|⟨b_{i}^{∗}, b_{i}^{∗}⟩| ≤ 2^{n−i}disc(L)^{1/(n−i+1)}.

For i ≤ j we have

|⟨b_{i}, b_{j}⟩| = | ∑_{k=1}^{i} μ_{ik}μ_{jk}⟨b_{k}^{∗}, b_{k}^{∗}⟩| ≤ ∑_{k=1}^{i−1} \frac{1}{4}|⟨b_{k}^{∗}, b_{k}^{∗}⟩| + |⟨b_{i}^{∗}, b_{i}^{∗}⟩|
≤ \frac{1}{4} ∑_{k=1}^{i−1} 2^{n−k}disc(L)^{1/(n−k+1)} + 2^{n−i}disc(L)^{1/(n−i+1)}
≤ (\frac{1}{4} ∑_{k=1}^{i−1} 2^{n−k} + 2^{n−i})disc(L)^{1/(n−i+1)}
= (2^{n−2} + 2^{n−i} − 2^{n−i−1})disc(L)^{1/(n−i+1)}.

□

7.2 Finding zero divisors in M_{2}(ℤ)

The smallest examples of non-commutative simple algebras over ℚ are of dimension 4. Such an algebra is either a division algebra or isomorphic to M_{2}(ℚ), the full ring of 2×2 rational matrices. Rónyai [Ró1] has shown that distinguishing these two cases is essentially as hard as deciding quadratic residuosity modulo composite numbers. On the other hand, in the previous chapter, an ff-algorithm was obtained to compute the dimension of the minimal one-sided ideals of simple algebras over ℚ. The method is based on finding maximal orders in algebras. It is natural to ask whether maximal orders can help in finding zero divisors.

In this section we settle this problem in the affirmative for a 4-dimensional simple noncommutative algebra A over ℚ. Assume that A contains zero divisors. Then every maximal order in A is known to be isomorphic to M_{2}(ℤ), the ring of 2 × 2 integer matrices (cf. [Re], Theorem 21.6). Assume that a maximal order Λ is given by the set of structure constants (c_{ij}^{k})_{i,j,k=1}^{4} with respect to a basis a_{1}, a_{2}, a_{3}, a_{4} of its additive group: a_{i}a_{j} = ∑_{k=1}^{4} c_{ij}^{k}a_{k} for every i, j ∈ {1, 2, 3, 4}. It is clear that c_{ij}^{k} ∈ ℤ. Our aim is to find a zero divisor in Λ.

For an element a ∈ A, tr(a), the reduced trace (cf. the previous chapter) of a can be computed by dividing the trace of the left or right action of a on A by 4. Recall that tr(a) is the trace of a as a 2 × 2 matrix. We know that the bilinear trace form ⟨ , ⟩ : A × A → ℚ defined by ⟨a, b⟩ := tr(ab) is a symmetric non-degenerate bilinear function on A, and takes integer values on Λ. Also, for the discriminant we have disc(Λ) = 1. This can be immediately seen by taking a standard basis of Λ, but it also follows from the theory of maximal orders. In fact, for A ≅ M_{n}(ℚ) checking the condition disc(Λ) = 1 can be used to ensure the maximality of the order Λ: smaller orders have discriminant larger than 1.

Observe that for a 2 × 2 matrix a, such that tr(a) = 0, the characteristic polynomial of the matrix a is x^{2} − \frac{1}{2}tr(a^{2}). We shall find a very special zero divisor: a nontrivial nilpotent element, i.e., 0 ≠ a ∈ A such that a^{2} = 0. Consider the linear subspace A′ of A consisting of elements with zero trace and the corresponding sublattice L′ of Λ, defined by

L′ := {a ∈ Λ : tr(a) = 0}.

Finding a nilpotent element of A is equivalent to finding an isotropic element in A′ with respect to the bilinear trace form. Since nilpotent elements do exist, the form ⟨ , ⟩ must be indefinite. It is easy to check that L′ is a three dimensional lattice and its discriminant is equal to 2. We can find a three element basis a′_{1}, a′_{2}, a′_{3} of L′ using the algorithm in [Fr].

Now we use the reduction algorithm of the previous section to compute a reduced basis (b_{1}, b_{2}, b_{3}) of L′ with respect to the trace form. If we search for an isotropic element in the form a = x_{1}b_{1} + x_{2}b_{2} + x_{3}b_{3} then the task is equivalent to finding a nontrivial integer solution of ∑_{i,j=1}^{3} tr(b_{i}b_{j})x_{i}x_{j} = 0, an equation with coefficients of small size. We can make the computation more explicit: Assume that b_{1}, b_{2}, b_{3} is a reduced basis, such that b_{2}(1) and b_{3}(2) are anisotropic. Then inequality (2′) of the previous section is satisfied with c = \frac{1}{2}, thus

|⟨b_{1}^{∗}, b_{1}^{∗}⟩| ≤ 2|⟨b_{2}^{∗}, b_{2}^{∗}⟩| ≤ 4|⟨b_{3}^{∗}, b_{3}^{∗}⟩|.

It follows that |⟨b_{1}^{∗}, b_{1}^{∗}⟩|^{3} ≤ 8disc(L′) = 16, and since b_{1}^{∗} = b_{1} is an integer matrix with characteristic polynomial x^{2} − \frac{1}{2}⟨b_{1}, b_{1}⟩, we obtain |⟨b_{1}^{∗}, b_{1}^{∗}⟩| = 2. Now we have

8 = 4disc(L′) = |⟨b_{1}^{∗}, b_{1}^{∗}⟩|^{3}|⟨b_{2}^{∗}, b_{2}^{∗}⟩||⟨b_{3}^{∗}, b_{3}^{∗}⟩| ≥ |⟨b_{1}^{∗}, b_{1}^{∗}⟩|^{2}|⟨b_{2}^{∗}, b_{2}^{∗}⟩|^{2} = disc(L′_{2})^{2},

where L′_{2} is the sublattice generated by b_{1} and b_{2}. On the other hand |⟨b_{1}^{∗}, b_{1}^{∗}⟩| ≤ 2|⟨b_{2}^{∗}, b_{2}^{∗}⟩| implies

disc(L′_{2})^{2} = |⟨b_{1}^{∗}, b_{1}^{∗}⟩|^{2}|⟨b_{2}^{∗}, b_{2}^{∗}⟩|^{2} ≥ \frac{1}{4}|⟨b_{1}^{∗}, b_{1}^{∗}⟩|^{4} = 4.

We infer that disc(L′) = 2, which gives |⟨b_{2}^{∗}, b_{2}^{∗}⟩| = 1 and

|⟨b_{3}^{∗}, b_{3}^{∗}⟩| = \frac{disc(L′)}{|⟨b_{1}^{∗}, b_{1}^{∗}⟩||⟨b_{2}^{∗}, b_{2}^{∗}⟩|} = 1.

If ⟨b_{2}^{∗}, b_{2}^{∗}⟩ = −⟨b_{3}^{∗}, b_{3}^{∗}⟩, then b_{2}^{∗} +b_{3}^{∗} is isotropic. If ⟨b_{2}^{∗}, b_{2}^{∗}⟩ = ⟨b_{3}^{∗}, b_{3}^{∗}⟩, then ⟨b_{1}^{∗}, b_{1}^{∗}⟩ = −2⟨b_{2}^{∗}, b_{2}^{∗}⟩ (otherwise ⟨ , ⟩ would be definite) and in that case b_{1}^{∗} + b_{2}^{∗} + b_{3}^{∗} is isotropic. Thus in any case, we can find a nontrivial nilpotent element a ∈ A as one of the vectors

b_{2}(1), b_{3}(2), b_{2}^{∗} + b_{3}^{∗}, or b_{1}^{∗} + b_{2}^{∗} + b_{3}^{∗}.

Since a is a nontrivial zero divisor in A, Aa = {ba|b ∈ A} is a two-dimensional left ideal of A and the lattice Λa = {ba|b ∈ Λ} has rank two. Using [Fr], a ℤ-basis v_{1}, v_{2} of Λa can be found. Now we are given an isomorphism Λ ≅ M_{2}(ℤ) by mapping b ∈ Λ to the matrix of the left action of a on Λa. We have proved

Theorem 7.2.1 Given a maximal order in an algebra isomorphic to M_{2}(ℚ), i.e., a ring Λ isomorphic to M_{2}(ℤ) by its integer structure constants {c_{i,j}^{k} : i, j, k = 1, 2, 3, 4}, we can find a nontrivial zero divisor and give an explicit isomorphism between Λ and M_{2}(ℤ) in time polynomial in the size of the structure constants. □

Note that since we are looking for isotropic elements, we do not need the whole power of the reduction algorithm, we can stop as soon as an isotropic vector is found. In particular, no reduction is necessary if the basis appears to be singular.

Problems for further research

We conclude with some open problems related to the results in this dissertation.

8.1 Faster radical algorithms

The performance of decomposition algorithms for semisimple algebras (and modules) can be improved (see [Eb1, EG]) with the aid of choosing random (or random-like) elements, such as splitting elements defined in Chapter 5. The main idea of these techniques is to perform computations in substructures related to the elements. This usually reduces the size (the number of variables and equations) of linear systems to solve. No such improvements have been developed yet for the radical algorithms of [Di], [Ró2], and Chapter 3. It would be interesting to analyze the possibility of new radical algorithms based on computing first the radical of certain subalgebras of restricted structure, such as a Cartan subalgebra (in the Lie algebra of our associative algebra). Note that Cartan subalgebras can be efficiently computed either with the randomized or even with the deterministic method of Chapter 5.

8.2 Decomposition of simple algebras

The complexity of finding the irreducible representations of algebras over global fields remains open. Note that since we have (partly randomized) polynomial time algorithms for isolating the radical and decomposing the semisimple part, the problem is essentially equivalent to finding minimal one-sided ideals in simple algebras. Efficient algorithms for this problem would also lead to new constructive methods in class field theory.

Explicit isomorphism of simple algebras Assume that our algebra A is in fact isomorphic to M_{m}(K). Note that the ff-algorithms of Chapter 6 can be used to verify this property of A. It is easy to see that finding a minimal one-sided ideal of A is equivalent to computing an isomorphism A ≅ M_{m}(K). Furthermore, using elementary ideas from the theory of Brauer groups (cf. [Re], Chapters 7 and 8), it is not difficult to show that this problem is in fact equivalent to computing an isomorphism between two arbitrary central simple algebras.

The results of Chapter 6, concerning the decision version of the problem, suggest the following question: how is the complexity of the explicit isomorphism problem for simple algebras related to factoring integers and polynomials? Does there exist a polynomial time ff-algorithm to solve the former problem over algebraic number fields? Does there exist a randomized polynomial time method over global function fields?

Quaternion algebras Recall from Chapter 7 that we have an affirmative answer in the special case of a quaternion algebra (a four dimensional central simple algebra) A over ℚ: finding a zero divisor in A is (up to a polynomial time reduction) equivalent to finding a maximal order in A, which is essentially as hard as factoring integers. It would be already interesting to generalize this result to quaternion algebras over arbitrary global fields. Note that it seems to be possible to generalize the method of Chapter 7 to the case where the ground field is 𝔽_{q}(X).

Rational group representations and group rings Recall from Chapter 6 that we have a polynomial time algorithm for computing the Schur indices of a finite group G given by multiplication table. In essence, this is possible since the prime factors of the discriminant of the integral group ring ℤG are small. It does not seem to be hopeless to use the very special structure of the order ℤG in efficient algorithms for constructing the irreducible matrix representations of G over ℚ. Note that the structure of integral group rings is under intensive investigation. Let us mention here the famous conjecture of Zassenhaus: if G and H are finite groups such that the group rings ℤG and ℤH are isomorphic, then G and H are isomorphic groups. A related computational problem is testing isomorphism of integral group rings (or some more general orders).

Explicit isomorphism over the algebraic closure There are efficient algorithm for constructing absolutely irreducible representations of associative algebras over extensions of the ground field, cf. [BR, Eb1, Eb3]. Assume that A is a central simple algebra of dimension m^{2} over the number field K. For extension L of K, the algebra A_{L} = A ⊗_{K} L is a central simple L-algebra. Note that A_{L} has the same multiplication table as A, but the structure constants are considered as elements of L. This construction makes possible a kind of symbolic computation over the field \overline{ℚ} of algebraic numbers. In this model even if the algebra A is inputted over a small field, we are interested in the structure of the algebra A\overline{ℚ}. The results of [BR, Eb1, Eb3] can be formulated as follows. An extension L of K together with an isomorphism A_{L} ≅ M_{m}(L) can be computed in polynomial time.

It would be interesting to obtain analogous results for simple Lie algebras. In the paper [Gra] a polynomial time method is proposed to decompose a semisimple Lie algebra over an algebraic number field into a direct sum of simple ideals and to determine the type (the isomorphism class over \overline{ℚ}) of each simple component. Recall that there are four infinite series (A_{l}, B_{l}, C_{l}, D_{l}) of isomorphism classes of simple Lie algebras over \overline{ℚ}. In addition, in low dimensions there exist five exceptional (E_{6}, E_{7}, E_{8}, F_{4}, G_{2}) classes. It would be important to develop an efficient algorithm for constructing an explicit isomorphism of a simple Lie algebra with one of the standard algebras over a “small” extension of the ground field.

Bibliography

[Bab] L. Babai, Deciding finiteness of matrix groups in Las Vegas polynomial time, Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, (1992), 33-40.

[BBR] L. Babai, R. M. Beals, D. Rockmore, Deciding finiteness of matrix groups in deterministic polynomial time, Israel J. Math., to appear.

[BR] L. Babai, L. Rónyai, Computing irreducible representations of finite groups, Mathematics of Computation 55, 192 (1990), 705-722.

[BBCIL] L. Babai, R. Beals, J.-Y. Cai, G. Ivanyos, E. M. Luks, Multiplicative equations over commuting matrices, Proc. 7th ACM-SIAM Symp. on Discrete Algorithms, (1996), 498-507.

[Bach] E. Bach, Fast algorithms under the extended Riemann Hypothesis: a concrete estimate, Proc. 14th ACM STOC, (1982), 290–295.

[Bar] E. H. Bareiss, Sylvester’s identity and multistep integer-preserving Gaussian elimination, Mathematics of Computation 103, (1968), 565–578.

[Bas] J. R. Bastida, Field Extensions and Galois Theory, in Rota, G-C. (ed), Encyclopedia of Mathematics and Its Applications, Vol. 22. Cambridge University Press and Addison-Wesley, 1984.

[Bea] R. Beals, Algorithms for matrix groups and the Tits alternative, Proc. 36th IEEE FOCS, (1995), 593-602.

[Ber1] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Technical Journal 46, (1967), 1853-1859.

[Ber2] E. R. Berlekamp, Algebraic Coding Theory. McGraw-Hill, 1968.

[Ber3] E. R. Berlekamp, Factoring polynomials over large finite fields, Mathematics of Computation 24, (1970), 713-715.

[BKS] R. E. Beck, B. Kolman, I. N. Stewart, Computing the structure of a Lie algebra, in Computers in Non-associative Rings and Algebras, Academic Press, 1977.

[Ca] J. W. S. Cassels, Rational Quadratic Forms, in L.M.S. Monographs, Academic Press, 1978.

[Ch] A. L. Chistov, Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time, Zapiski Nauchnykh Seminarov LOMI 137, (1984), 124–188. English translation: J. Soviet Math. 34, (1986), 1838–1882.

[CG] A. L. Chistov, D. Yu. Grigoryev, Polynomial time factoring of the multivariable polynomials over a global field, LOMI preprint E-5-82, Leningrad, 1982.

[CIW] A. M. Cohen, G. Ivanyos, D. B. Wales, Finding the radical of an algebra of linear transformations, 4th Int. Symp. on Effective Methods in Algebraic Geometry, (1996). To appear in J. Pure and Applied Algebra.

[CLZ] J. Cai, R. J. Lipton, Y. Zalcstein: The complexity of the membership problem for 2-generated commutative semigroups of rational matrices, Proc. 35th IEEE FOCS, (1994), 135–142.

[Di] L. E. Dickson, Algebras and Their Arithmetics, University of Chicago, 1923.

[Eb1] W. M. Eberly, Computations for Algebras and Group Representations, Ph. D. thesis, Dept. of Computer Science, University of Toronto, 1989.

[Eb2] W. M. Eberly, Decomposition of algebras over finite fields and number fields, Computational Complexity 1, (1991), 179-206.

[Eb3] W. M. Eberly, Decompositions of algebras over R and C, Computational Complexity 1, (1991), 207-230.

[EG] W. M. Eberly, M. Giesbrecht, Efficient decomposition of associative algebras, Proc. ISSAC’96, (1996), 170–178.

[Ed] J. Edmonds, System of distinct representatives and linear algebra, Journal of Research of the National Bureau of Standards 718, 4, (1967), 241-245.

[FR] K. Friedl, L. Rónyai, Polynomial time solution of some problems in computational algebra, Proc. 17th ACM STOC, (1985), 153-162.

[Fr] M. A. Frumkin, Polynomial time algorithms in the theory of linear diophantine equations, Proc. FCT’76, (1976), 386-392.

[FSh] A. Fröhlich, J. C. Shepardson, Effective procedures in field theory, Royal Soc. London, Phil. Trans. A 248, (1955-56), 407-432.

[Ge1] G. Ge, Algorithms Related to Multiplicative Representations of Algebraic Numbers, Ph. D. thesis, Math Dept, U. C. Berkeley, 1993.

[Ge2] G. Ge, Testing equalities of multiplicative representations in polynomial time, Proc. 34th IEEE FOCS, (1993), 422–426.

[GIKR] W. A. de Graaf, G. Ivanyos, A. Küronya, L. Rónyai, Computing Levi decompositions, Applicable Algebra in Engineering, Communication and Computing, to appear.

[GIR] W. A. de Graaf, G. Ivanyos, L. Rónyai, Computing Cartan subalgebras of Lie algebras, Applicable Algebra in Engineering, Communication and Computing 7, (1996), 71-90.

[GM] S. Goldwasser, S. Micali, Probabilistic encryption and how to play mental poker keeping secret all partial information, Proc. 14th ACM STOC, (1982), 365-378.

[GMT] P. Gianni, V. Miller, B. Trager, Decomposition of algebras, Lecture Notes in Computer Science 358, eds. G. Goos and J. Hartmanis, Springer-Verlag 1988, 300-308.

[Gra] W. A. de Graaf, Calculating the structure of a semisimple Lie algebra, 4th Int. Symp. on Effective Methods in Algebraic Geometry, (1996). To appear in J. Pure and Applied Algebra.

[Gri] D. Grigoriev, Factorization of polynomials over finite field and the solution of systems of algebraic equations, Zapiski Nauchnykh Seminarov LOMI 137, (1984), 20–79. English translation: J. Soviet Math. 34, (1986), 1762–1803.

[Ha] M. Harada, Hereditary orders, Trans. Amer. Math. Soc. 107, (1963), 273-290.

[HU] J. E. Hopcroft, J. D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.

[Hum] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Springer-Verlag, New York, Heidelberg, Berlin, 1972.

[IR] G. Ivanyos, L. Rónyai, Finding maximal orders in semisimple algebras over Q, Computational Complexity 3, (1993), 245-261.

[IRSz] G. Ivanyos, L. Rónyai, Á. Szántó, Decomposition of algebras over F_{q}(X_{1}, …, X_{m}), Applicable Algebra in Engineering, Communication and Computing 5, (1994), 71-90.

[ISz] G. Ivanyos, Á. Szántó, Lattice basis reduction for indefinite forms and an application, Discrete Mathemathics 153, (1996), 177-188.

[Ja] H. Jacobinski, Two remarks about hereditary orders, Proc. Amer. Math. Soc. 28, (1971), 1-8.

[Jac] N. Jacobson, Lie Algebras, Dover, New York, 1979.

[KB] R. Kannan, A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. on Computing 4, (1979), 499–507.

[Ke] A. Kertész, Lectures on Artinian rings, Akadémiai Kiadó, Budapest 1987.

[Kn] D. E. Knuth, The art of computer programming, Vol. 2: Seminumerical algorithms, Addison-Wesley 1981.

[La] S. Landau, Factoring polynomials over algebraic number fields, SIAM J. on Computing 14, (1985), 184-195.

[Len] A. K. Lenstra, Factoring polynomials over algebraic number fields, Proc. EURO-CAL, Lect. Notes of Comp. Sci. 162, Springer-Verlag 1983, 245–254.

[LLL] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász, Factoring polynomials with rational coefficients, Math. Annalen 261, (1982), 515-534.

[Lo] L. Lovász, An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM, 1986.

[Mi] K. A. Mihaĭlova, The occurrence problem for a direct product of groups, Dokl. Akad. Nauk 119, (1958), 1103–1105.

[Pie] R. S. Pierce, Associative Algebras, Springer-Verlag, 1982.

[Po1] M. Pohst, A modification of the LLL reduction algorithm, J. Symbolic Computation 4, (1987), 123-127.

[Po] M. E. Pohst, Three principal tasks of computational algebraic number theory, Number Theory and Applications, Proc. NATO Advanced Study Inst., Kluwer Academic Publishers, 1989, 123-133.

[Ra] M. O. Rabin, Digitalized signatures and public-key functions as intractable as factorization, MIT/LCS TR-212, Technical Memo MIT, 1979.

[RWZ] D. Rand, P. Winternitz, H. Zassenhaus, On the Identification of a Lie algebra given by its structure constants. I. Direct decompositions, Levi decompositions, and nilradicals, Linear Algebra and its Applications 109, (1988), 197–246.

[Re] I. Reiner, Maximal Orders, Academic Press, 1975.

[Ró1] L. Rónyai, Zero divisors in quaternion algebras, Journal of Algorithms 9, (1988), 494-506.

[Ró2] L. Rónyai, Computing the structure of finite algebras, J. Symbolic Computation 9, (1990), 355-373.

[Ró3] L. Rónyai, Algorithmic properties of maximal orders in simple algebras over Q, Computational Complexity 2, (1992), 225-243.

[Ró4] L. Rónyai, Computations in associative algebras, Groups and Computation, DIMACS Series, 11, American Mathematical Society, 1993, 221–243.

[Ró5] L. Rónyai, A deterministic method for computing splitting elements in semisimple algebras over Q, Journal of Algorithms 16, (1994), 24-32.

[Sch] J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, Journal of ACM 27, (1980), 701-717.

[Z] R. E. Zippel, Propabilistic algorithms for sparse polynomials, Proc. EUROSAM ’79, Lect. Notes in Comp. Sci. 72, Springer, 1979, 216-226.

[Win] D. J. Winter, Abstract Lie Algebras, The MIT Press, 1972.

Appendix: Proof of Theorem 7.1.1

I. First we show that the algorithm requires a polynomial number of arithmetical operations. This is clear for finding the initial nonsingular basis (denoted by (c_{1}, …, c_{n})). We have already seen that the quantity

D(b_{1}, …, b_{n}) := ∏_{k=1}^{n} ∏_{j=1}^{k} |⟨b_{j}^{∗}, b_{j}^{∗}⟩| = ∏_{k=1}^{n} disc(L_{k}) ∈ ℕ.

remains unchanged during making the basis proper and reduces by a factor less than \frac{3}{4} in every round, where a change is due to failure at tests (2a) or (2b) of reducedness. After p such rounds, we have

1 ≤ D(b_{1}, …, b_{n}) ≤ (\frac{3}{4})^{p}D(c_{1}, …, c_{n}),

and hence

p ≤ \frac{1}{log_{2} \frac{4}{3}} log_{2} D(c_{1}, …, c_{n}) ≤ 3 log_{2} D(c_{1}, …, c_{n}).

We conclude that the number of arithmetical operations is really bounded by a polynomial of the input size.

II. It remains to prove that the size of the numbers we work with during the run of the algorithm is also bounded by a polynomial of the input size (the dimension n, and the sizes of ⟨a_{i}, a_{j}⟩).

Lemmas A.1 and A.2 below are related to the procedure making a basis proper. They establish bounds on the coordinates of vectors in terms of the values of ⟨ , ⟩ on the starting basis. Lemma A.3 provides a universal bound on the values of ⟨ , ⟩ on an arbitrary proper basis produced by the algorithm.

Lemma A.1 For any nonsingular basis (b_{1}, …, b_{n}) of L, writing b_{i} = b_{i}^{∗} + ∑_{j=1}^{i−1} μ_{ij}b_{j}^{∗} for i = 1, …, n,

|μ_{ij}| ≤ (nA)^{n} and either μ_{ij} = 0 or |μ_{ij}| ≥ (nA)^{−n}

where A := max_{k,l} |⟨b_{k}, b_{l}⟩|.

Proof In the arguments below we use Hadamard’s bound on the determinant.

For i > 1 we have

|⟨b_{i}^{∗}, b_{i}^{∗}⟩| = \frac{| ∏_{j≤i}⟨b_{j}^{∗}, b_{j}^{∗}⟩|}{| ∏_{j<i}⟨b_{j}^{∗}, b_{j}^{∗}⟩|} = \frac{|det (⟨b_{k}, b_{l}⟩)_{k,l≤i}|}{|det (⟨b_{k}, b_{l}⟩)_{k,l<i}|}
≥ |det (⟨b_{k}, b_{l}⟩)_{k,l<i}|^{−1} ≥ ((i − 1)A)^{−(i−1)} ≥ (nA)^{1−n},

implying for all 1 ≤ i < j that

|μ_{ij}| = \frac{|⟨b_{i}, b_{j}⟩|}{|⟨b_{j}^{∗}, b_{j}^{∗}⟩|} ≤ A(nA)^{n−1}.

Similarly,

|⟨b_{i}^{∗}, b_{i}^{∗}⟩| ≤ |det (⟨b_{k}, b_{l}⟩)_{k,l≤i}| ≤ (iA)^{i} ≤ (nA)^{n},

thus if ⟨b_{i}, b_{j}⟩ ≠ 0 then |μ_{ij}| ≥ (nA)^{−n}. □

Lemma A.2 Suppose that the coordinates of the vectors b_{i} of a nonsingular basis (b_{1}, …, b_{n}) of L with respect to a fixed other basis (d_{1}, …, d_{n}) are bounded by C in absolute value. Then the coordinates with respect to (d_{1}, …, d_{n}) of the vectors occurring in the course of the procedure making the basis (b_{1}, …, b_{n}) proper (in particular those of the resulting proper basis) will be at most

2^{n^{2}}B^{n}C,

where B := (nA)^{n} with A = max_{kl} |⟨b_{k}, b_{l}⟩|.

Proof First we remark that the change of b_{j} to b_{j}−mb_{k} affects neither the orthogonalization of the basis nor the coefficients μ_{st} for values of s other than j. We also observe that when the procedure pivots the element b_{n}, (b_{1}, …, b_{n−1}) is already a proper basis of L_{n−1}, and by induction we can assume that for k < n the absolute values of the coordinates of b_{k} are at most 2^{(n−1)^{2}}B^{n−1}C. We prove by induction that B2^{t} is an integer upper bound for |μ_{nk}| (k = 1, …, n − 1) after the t’th change of b_{n}. For t = 0 this follows from the first inequality of Lemma A.1. Assume that after the t − 1’st step B2^{t−1} is an upper bound for |μ_{nk}| (k = 1, …, n − 1). In the t’th step we perform b_{n}^{(t)} := b_{n}^{(t−1)} − m^{(t)}b_{n−t} = ∑_{k=1}^{n} μ_{nk}^{(t)}b_{k}^{∗}, where |m^{(t)} − μ_{n,n−t}^{(t−1)}| ≤ \frac{1}{2}. Observe that we just achieve |μ_{n,n−t}^{(t)}| ≤ \frac{1}{2}, while for k > n − t we already have |μ_{nk}^{(t)}| = |μ_{nk}^{(t−1)}| ≤ \frac{1}{2}. On the other hand, from the induction hypothesis and the integrality of B2^{t−1} we obtain |m^{(t)}| ≤ B2^{t−1} and hence |μ_{nk}^{(t)}| = |μ_{nk}^{(t−1)} − m^{(t)}μ_{n−t,k}| ≤ B2^{t−1} + \frac{1}{2}B2^{t−1} < B2^{t} (k = 1, …, n − t − 1). We used here the fact that k < n, n − t < n and therefore we already have |μ_{n−t,k}| < \frac{1}{2}. After the t’th step (1 ≤ t ≤ n − 1), b_{n} changes to

b_{n}^{(t)} = b_{n} − (m^{(1)}b_{n−1} + … + m^{(t)}b_{n−t}).

Using the bound |m^{(s)}| ≤ B2^{s−1} obtained above and the induction hypothesis on b_{1}, …, b_{n−1}, we infer the following upper bound on absolute values of the coordinates of b_{n}^{(t)}:

2^{(n−1)^{2}}B^{n−1}C(1 + B + ⋯ + B2^{t}) ≤ 2^{(n−1)^{2}}B^{n−1}CB2^{t+1} < 2^{n^{2}}B^{n}C,

as claimed. □

Lemma A.3 For any proper basis (b_{1}, …, b_{n}) produced by the algorithm, we have

max_{i,j} |⟨b_{i}, b_{j}⟩| ≤ nD(c_{1}, …, c_{n})

where (c_{1}, …, c_{n}) is the initial nonsingular basis.

Proof If we write b_{i} = ∑_{j=1}^{i} μ_{i,j}b_{j}^{∗} (i = 1, …, n) then |μ_{i,j}| ≤ 1 (i = 1 … n, j = i … n), thus we have

|⟨b_{i}, b_{k}⟩| = | ∑_{j=1}^{min(i,k)} μ_{ij}μ_{kj}⟨b_{j}^{∗}, b_{j}^{∗}⟩| ≤ ∑_{j=1}^{min(i,k)} |⟨b_{j}^{∗}, b_{j}^{∗}⟩|.

We have seen in the first part of the proof that the quantity D(b_{1}, …, b_{n}) is decreasing during the algorithm, thus

|⟨b_{j}^{∗}, b_{j}^{∗}⟩| = \frac{disc(L_{j})}{disc(L_{j−1})} ≤ disc(L_{j}) ≤ D(c_{1}, …, c_{n}),

and the claim follows easily. □

Now we can estimate the size of the numbers we work with. The maximum of {|⟨a_{i}, a_{j}⟩| : i, j = 1, …, n} is denoted by A_{0}. Let (c_{1}, …, c_{n}) be the starting nonsingular basis. We know that either c_{i} = a_{i} or c_{i} = a_{i} + ϵa_{j} for some j > i and ϵ = ±1. From this we infer that |⟨c_{i}, c_{j}⟩| ≤ 4A_{0} and therefore (using Hadamard’s bound on the n discriminants)

D(c_{1}, …, c_{n}) ≤ (4nA_{0})^{n^{2}}.

We denote by C_{1} the maximum of the absolute values of the coordinates of the first proper basis (b_{1}, …, b_{n}). By Lemma A.2 with B_{0} := (4nA_{0})^{n} we have

C_{1} ≤ 2 · 2^{n^{2}}B_{0}^{n}.

This bound is also valid for the intermediate vectors of the procedure making the initial nonsingular basis (c_{1}, …, c_{n}) proper.

Lemma A.3 gives an absolute bound for values of ⟨ , ⟩ on the proper bases produced by the algorithm:

|⟨b_{i}, b_{j}⟩| ≤ nB_{0}^{n} =: E.

A swap performed due to failure at test (2a) does not affect the set of the coordinates. In case of failure at (2b), we perform b_{i} := b_{i} + zb_{i+1} for some i, where |z| ≤ \frac{1}{2}(nE)^{n} + 1 < (nE)^{n}. Since z is an integer, |z + 1| ≤ (nE)^{n}. For the new values we have |⟨b_{i}, b_{j}⟩| ≤ (1 + |z|)^{2}E, thus A := E(nE)^{2n} < (nE)^{2n+1} is an upper bound for the absolute values of ⟨ , ⟩ before each entry to the procedure maintaining properness. Now let C_{k} stand for the maximum of the absolute values of the coordinates of the elements of the k’th proper basis. With B := (nA)^{n} we have

C_{k} ≤ C_{k−1}(nE)^{n}B^{n}2^{n^{2}}.

The algorithm terminates in at most p = 3 log_{2} D(c_{1}, …, c_{n}) iteration steps, and

C_{p} ≤ 2(nEB)^{np}2^{n^{2}p}.

C_{p} is an upper bound for all the coordinates computed in our algorithm. For the size of the coordinates this yields the bound

log_{2} C_{p} = 1 + n^{2}p + np log_{2}(2nE(1 + B)) = O((n^{7}) log^{2}(n) log^{2}(A_{0})),

since p = O(n^{2}(log(n) + log(A_{0}))), log(E) = O(n^{2}(log(n) + log(A_{0}))) and log(B) = O(n^{4}(log(n) + log(A_{0}))). □