General Commutative Rings in Magma

Introduction

This section lists the commutative rings that are currently supported in Magma.

The calculations that can be performed with a given ring depend upon the abstract properties of a ring (whether or not a field, for example) and the availability of effective algorithms. The various rings are grouped in this section according to their key algebraic properties.

Exact and Non-exact Rings

It is important to note at the outset that commutative rings in Magma are divided into two classes: exact rings and non-exact rings. Exact rings are characterised as rings whose elements have finite representations and so calculations with them produce an exact result. An example is the ring ℚ[x] of univariate polynomials with rational numbers as coefficients. Non-exact rings, on the other hand, are rings whose elements have infinite representations in general. The real field is an example of a non-exact ring, recalling that real numbers such as π or √2, given as real numbers, have infinite representations.

At present all of the non-exact rings are fields: the real and complex fields and the p-adic and formal power series fields. So with these four exceptions, the reader should assume all other rings discussed in this section are exact.

Standard Operations for Commutative Rings

All commutative rings support the following standard operations:

• Internal algorithms for the basic ring arithmetic operations: addition, subtraction, negation, and multiplication.
• A test as to whether an element is zero. This implies a test for the equality of elements.
• A normalization algorithm: for any non-zero a∈R, this computes a unique canonical associate b of a such that b = ua, with u a unit.

In the case of exact rings, the zero has to be a specific element. In the case of non-exact rings, the test for zero may be weakened to require that the value being tested lies in a small disk or interval.

Exact Fields

A computable field in Magma is a field which contains internal algorithms for the standard ring arithmetic operations together with division. The following list summarises each of the computable fields that are supported:

• A finite field GF(q)
• The rational field ℚ
• A quotient ring of the polynomial ring K[x₁, ..., x_n]/I, where K is a computable field and I is a maximal ideal
• A number field ℚ(α₁,…,α_k) (finite degree extension of ℚ)
• A rational function field K(t₁,…, t_k), where K is a computable field, and t_i,i = 1,…,k are transcendental
• An algebraic function field (K(t)[x₁, ..., x_n])/I, where K is a computable field and I is a maximal ideal
• The algebraically closed field (ACF) over GF(q) or ℚ

Exact Euclidean Domains

A commutative ring R is said to have an euclidean function if:

• There exists a function φ: R→ℤ _{≥ 0}∪{- ∞}, such that for all a,b∈R with a,b ≠ 0: φ(a) ≤ φ(ab)
• There exists a division with remainder algorithm such that for all a,b∈R with b ≠ 0, there exist q,r∈R with a = qb + r,   φ(r) < φ(b)

A computable euclidean domain is a computable integral domain R having a euclidean function. The computable euclidean domains supported in Magma are:

• The ring of integers ℤ
• A polynomial ring K[x], where K is any computable field
• A quotient ring O_K/I, where O_K is the maximal order of a number field K, and I is an integral prime ideal of O_K
• A valuation ring (with a discrete non-Archimedean valuation)

Exact Integral Domains

The integral domains in Magma that are not euclidean domains are:

• A ring R[x], where R is a computable integral domain but not a field
• A ring R[x₁,…, x_n], where R is a computable integral domain and n > 1
• A quotient ring K[x₁, ..., x_n]/I, where K is a computable field and I is a prime ideal
• A subring of the maximal order O_K, where K is a number field
• A subring of a maximal order O_K, where K is a function field
• A quotient ring O/I, where O is a subring of the maximal order O_K having coefficient ring ℤ, K is a number field, and I is an integral prime ideal

Exact Principal Rings having an Euclidean Function

The rings in this section may have zero divisors and hence are not integral domains in general, but they do satisfy two useful conditions:

• The ideals are principal, so that the ring is a principal ideal ring or, more concisely, a principal ring.
• The ring has a euclidean function as defined above. In other words there is a division algorithm which can be used to find a generator for any ideal.

The list below contains the computable rings in Magma which are not integral domains, are principal and which have an euclidean function:

• A quotient ring ℤ/<m>, for m∈ℤ
• A quotient ring K[x]/<f>, for f∈K[x], where K is a computable field
• A quotient ring of a p-adic ring ℤ_p/<p^d> (equivalent to using a fixed precision d)
• A quotient ring of a local ring equivalent to using fixed precision d
• A galois ring GR(p^a,d). i.e., the unique galois extension of ℤ/p^aℤ of degree d.

Other Exact Commutative Rings

The commutative rings which are neither integral domains nor have an euclidean function are as follows:

• The rings R[x] and R[x₁,…, x_n], where R is neither an integral domain nor has a euclidean function
• A quotient ring K[x₁, ..., x_n]/I for a non-prime ideal I, where K is a computable field
• A quotient ring O/I, where O is a subring of O_K, K is a number field or function field and I is a non-prime ideal

Non-exact Fields

Recall that non-exact fields are those whose elements have infinite representations and so calculations have to be carried out using a finite approximation to the element and any answer is returned as a finite approximation. The various non-exact fields in Magma allow the user to work at any precision desired. Thus, when computing in the real and complex fields, the user sets the precision and the calculations will be performed to that precision.

When computing in a non-exact field, obvious difficulties arise when deciding whether an element is a identity or whether two elements are equal. If the precision chosen for the calculation is insufficient, it may well result in the calculation crashing or returning meaningless results. In fact a number of algorithms used in Magma that return exact results perform some part of the calculation in non-exact structures. Just as is the case in numerical analysis, careful error analysis has to be undertaken to ensure that the results of a non-exact calculation fall into a bounded region. However, for complex algebraic algorithms the error analysis is often very difficult and has been undertaken in the case of very few algorithms. In the case of Magma, it was decided to avoid developing numerical versions of exact algebraic algorithms because of the very large amount of work that would be needed with an uncertain outcome.

If K is a non-exact computable field then rings defined over K will also be non-exact. For example, the polynomial ring K[x] will also be non-exact. However, basic operations such as addition, subtraction, and multiplication of elements of polynomial rings and matrix rings defined over a non-exact ring or field K are supported.

The six families of non-exact fields are as follows:

• The real field
• The complex field
• A p-adic field ℚ_p
• A local field (a finite degree extension of a p-adic field)
• A field of formal Laurent series, K((x)), where K is a field
• A field of Puiseux series over a field K

Non-exact Commutative Rings

All of the non-exact commutative rings that are not fields are listed in this section.

• A power series ring R[[x]], where R is a integral domain
• An extension of a power series ring K[[x]], where K is a finite field
• A ring of formal Laurent series, R((x)), where R is a ring
• A power series ring being the ring of integers of a Laurent series field K
• A ring of Puiseux series over a ring R