Quadratische und hermitische Gitter über Zahlkörpern

The algorithms explained in my habilitation for computing with quadratic and hermitian lattices over number fields have been implemented in Magma and can be downloaded here.

Note that the text below does not explain all intrinsics in this package but only the most important ones. For a complete list of intrinsics and all their options, please refer to the source code.

How to use this package with Magma

First, attach the package to your running Magma process.

> AttachSpec("lat.spec");

Constructing quadratic lattices

Let K be an absolute abgebraic number field (note that the rationals are not a number field in Magma, but you can use K:= QNF(); to construct a degree one extension of Q which is a number field).

LatticeModule(M, F) : ModDed, Mtrx -> LatMod

LatticeModule(M, F) : Mtrx, Mtrx -> LatMod

LatticeModule(F) : Mtrx -> LatMod

Given a Dedekind module M over ZK and a non-degenerate symmetric matrix F over K, construct the lattice with module M in the quadratic space with Gram matrix F. If M is a matrix, the module is taken to be generated be the rows of M. If M is omitted, it is taken to be the free standard module.

MaximalIntegralLattice(F) : Mtrx -> LatMod

Given a non-degenerate symmetric matrix F over K, constructs a maximal integral lattice L in the quadratic space with Gram matrix F. Note that the lattice L is not unique, but its genus is.

Here are two examples:

> K:= QuadraticField(5); > L:= LatticeModule( Matrix(K, 2, [1,2, 2,3]), MatrixRing(K, 2) ! 3);

This constructs the lattice with module generated by (1,2) and (2,3) inside the bilinear space K2 equipped with the form given by 3*I2.

> M:= MaximalIntegralLattice(Matrix(K, 2, [1,2,2,1]));

Constructing hermitian lattices

Suppose now E is a degree 2 extension of an algebraic number field K. (K might be the field of rationals Q.)

HermitianLattice(M, F) : ModDed, Mtrx -> LatModHerm

HermitianLattice(M, F) : Mtrx, Mtrx -> LatModHerm

HermitianLattice(F) : Mtrx -> LatModHerm

Given a Dedekind module M over ZE and a non-degenerate hermitian matrix F over E, construct the lattice with module M in the hermitian space with Gram matrix F. If M is a matrix, the module is taken to be generated be the rows of M. If M is omitted, it is taken to be the free standard module.

In the following example, we consider E = Q(\zeta_5) as a quadratic extension over K = Q(\sqrt(5)) and construct a binary hermitian lattice over E.

> C:= CyclotomicField(5); > K:= sub< C | C.1+C.1^-1>; > E:= RelativeField(K, C); > HermitianLattice( Matrix(E, 2, [1,2, 2,3]), Matrix(E, 2, [1, E.1, E.1^-1, 0]));

MaximalIntegralHermitianLattice(F) : Mtrx -> LatModHerm

Given a non-degenerate hermitian matrix F over K, constructs a maximal integral lattice L in the hermitian space with Gram matrix F. Note that the lattice L is not unique, but its genus is.

Constructing forms from local invariants

Let E and K be as before.

Every quadratic space V over K of rank n admits an orthogonal Gram matrix Diag(a1,...,an) say. Given a place p of K, let (a,b)p be the Hilbert symbol of a and b over Kp. Then ∏i<j (ai, ai)p denotes the Hasse symbol of V at the place p.

QuadraticFormWithInvariants(Dim, Det, P, N) : RngIntElt, FldAlgElt, {}, [] -> Mtrx

Returns a Gram matrix of a quadratic space over K with rank Dim, determinant Det, whose local Hasse invariants are -1 at the finite places in P and whose signature has Ni negative entries at the i-th real place of K. The field K is taken to be the parent of Det.

HermitianFormWithInvariants(E, Dim, Finite, N) : FldAlg, RngIntElt, {}, [] -> Mtrx

Returns a Gram matrix of a hermitian space over E with rank Dim, whose determinant is a non-norm at the finite places in P and whose signature has Ni negative entries at the i-th real place of K which remains real in E.

Here is an example:

> K:= QuadraticField(5); > QuadraticFormWithInvariants(3, K ! 1, {2 * Integers(K)}, [2, 0]); [ 2 0 0] [ 0 1/2*(-K.1 - 1) 0] [ 0 0 -K.1 - 1] > HermitianFormWithInvariants(QuadraticField(3), 2, {3,5}, []); [1 0] [0 5]

Intrinsics for all lattices

Let L,M be quadratic or hermitian lattices over the same field.

Module(L) : LatMod -> ModDed

Returns the underlying Dedekind module of L.

InnerProductMatrix(L) : LatMod -> Mtrx

Returns the Gram matrix of the ambient quadratic or hermitian space.

BaseRing(L) : LatMod -> RngOrd

Returns the ring of integers of K of E depending on L is a quadratic of hermitian lattice.

Scale(L) : LatMod -> RngOrdFracIdl

Returns the fractional ideal { (x,y) | x,y in L }.

Norm(L) : LatMod -> RngOrdFracIdl

Returns the fractional ideal generated by { (x,x) | x in L }.

Volume(L) : LatMod -> RngOrdFracIdl

Determinant(L) : LatMod -> RngOrdFracIdl

Returns the fractional ideal D such that Dp is generated by det(Lp) at all finite places p.

Dual(L) : LatMod -> LatMod

Returns the dual lattice of L.

IsLocallyIsotropic(L, p) : LatMod, . -> BoolElt

Given a place of K or a prime ideal of ZK, tests whether Lp is isotropic.

IsLocallyIsometric(L, M, p) : LatMod, RngOrdIdl -> BoolElt

Tests whether Lp and Mp are isometric at the prime ideal p of ZK.

IsSameGenus(L, M) : LatMod, LatMod -> BoolElt

IsSimilarGenus(L, M) : LatMod, LatMod -> BoolElt

Test whether L and M lie in the same (a similar) genus.

GenusRepresentatives(L) : LatMod -> []

Computes a list of representatives of the isometry classes in the genus of L.

TODO: Add some more?

Intrinsics for definite lattices

Given definite lattices L and M, the following additional intrinsics are available:

IsIsometric(L, M) : LatMod, LatMod -> BoolElt, Mtrx

Tests if the lattices L and M are isometric. If so, the second return value is an isometry between L and M (with respect to the standard basis of the ambient spaces of L and M).

IsSimilar(L, M) : LatMod, LatMod -> BoolElt, Mtrx, FldAlgElt

Tests if the lattices L and M are similar.

AutomorphismGroup(L) : LatMod -> GrpMat

Returns the automorphism group of L with respect to the standard basis of the ambient space of L.

Mass(L) : LatMod -> FldRatElt

Returns the Siegel mass of L.

OrthogonalDecomposition(L) : LatMod -> []

Returns the (unique) indecomposable sublattices of L. They are pairwise orthogonal and their sum is L.

Zwei-Erzeuger Untergruppen von PSL(2,R)

The algorithms explained in

  • "The constructive membership problem for discrete free subgroups of SL(2,R)"
  • "The constructive membership problem for discrete two-generator subgroups of SL(2,R)"

have been implemented in Magma and can be downloaded here.

How to use this file with Magma:

The above package has to be loaded into your Magma workspace using:

> Attach("sl2r.m");

Constructing a two-generator subgoup

Suppose A, B are matrices over K. To generate the group G:= <A, B> as a subgroup of (P)SL(2,R) one uses the commands TwoGeneratorSubgroupSL2R and TwoGeneratorSubgroupPSL2R. Besides the matrices A and B they also expect an embedding of K into R as a third parameter. If K is the field of rationals, one has to use Infinity() as embedding.

> A:= Matrix(2, [ 2, 0, 2, 1/2 ]); > B:= Matrix(2, [ 5, 2, -3, -1 ]); > G:= TwoGeneratorSubgroupSL2R(A, B, Infinity()); G; Two generator subgroup of SL(2,R) generated by [ 2 0] [ 2 1/2], [ 5 2] [-3 -1]

Predicates of two-generator subgoups

The generators of G can be accessed as G.1 and G.2. The following functions

  • IsDiscrete
  • IsDiscreteAndFree
  • IsDiscreteAndFreeProduct
  • IsDiscreteAndElementary
  • IsTriangleGroup
  • IsFinite

can be used to decide if G is discrete, etc. In the example above,

> IsDiscreteAndFree(G); true

So the group G is discrete and free.

Constructive membership for two-generator subgoups

Whenever the group G is discrete, the membership problem can be decided using the Membership intrinsic. In the example above,

> Membership(G, A^10 * B^3 * A); true $.1^10 * $.2^3 * $.1 > Membership(G, -A); false

The first return value indicates whether the element is in G. If this is the case, then the second return value is a word in a free group of rank 2 that expresses the element in the generators of G. Note that if G was created as a subgroup of PSL(2,R) then the second membership test above would yield true:

> H:= TwoGeneratorSubgroupPSL2R(A, B, Infinity()); > Membership(H, -A); true $.1

As explained in the papers mentioned in the beginning, the algorithm usually computes a witness pair for G. The chosen witness pair can be obtained using the WitnessPair intrinsic.

Another example

We construct a (2,3,7)-triangle group:

> K:= NumberField( Polynomial([-1, 0, -2, 0, 1, 0, 1]) ); > eta:= K.1^2; > X:= Matrix(K, 2, [0, -K.1, K.1^5 + K.1^3 - 2*K.1, 0 ]); > Y:= Matrix(K, 2, [1/2, 1/2*(-K.1^5 - K.1^4 - K.1^3 + K.1 + 1), 1/2*(-K.1^5 + K.1^4 + 3*K.1 - 2) , 1/2] ); > plc:= InfinitePlaces(K)[1]; > G:= TwoGeneratorSubgroupSL2R(X, Y, plc); > IsTriangleGroup(G); true <2, 3, 7>

Algorithmen für die modulare Gruppe

The algorithms explained in the paper have been implemented in Magma and can be downloaded here. Note that currently all elements and subgroups of the modular groups have to be given as elements and subgroups of SL(2, Z). The following example shows the main features of our implementation.

How to use this file with Magma:

Attach the downloaded file to your running Magma process.

Attach("sl2z.m");

To check if some subgroup H of PSL(2,Z) has finite index in PSL(2,Z), one uses the IndexInPSL2Z intrinsic.

> H:= sub< SL(2, Integers()) | [1,4,0,1], [0,1,-1,0] >; > IndexInPSL2Z(H); Infinity > G:= sub< SL(2, Integers()) | [1,2,0,1], [1,0,2,1] >; > IndexInPSL2Z(G); 6

So the group H has infinite index in the modular group while G has index 6. To decide if G is a congruence subgroup, one can use MyIsCongruence.

> MyIsCongruence(G); true

So G is indeed a congruence subgroup. To test whether an element of PSL(2,Z) lies in H one can use the Membership command.

> M:= SL(2, Integers()) ! [1,2,0,1]; > ok:= Membership(H, M); ok; false

If one turns the CosetRep flag on, the second return value will be some data representing the right coset. This data can be turned into a matrix with CosetToMatrix. The coset data as well as the matrix are unique and can therefore be used for comparing cosets.

> M:= SL(2, Integers()) ! [1,2,0,1]; > ok, coset:= Membership(H, M : CosetRep); > CosetToMatrix(coset); [ 1 2] [-4 -7] > ok, coset2:= Membership(H, H.1 * M : CosetRep); coset eq coset2; true

Suppose H is given by n generators and h in H. If the Word flag is turned on, the Membership intrinsic will return a straight line progam (SLP) representing h as the third return value. Evaluating this SLP in H itself yields (not surprisingly) h. Evaluating the SLP in a free group of rank n expresses h as a word in the n generators of H. This solves the constructive membership problem. Here is an example.

> M:= SL(2, Integers()) ! [ -40, -159, -1, -4 ]; > ok, _, w:= Membership(H, M : Word); > assert ok and Evaluate(w, H) in {M, -M}; > Evaluate( w, FreeGroup(Ngens(H)) ); $.1^2 * $.2^2 * $.1^8 * $.2^-1 * $.1 > H.1^2 * H.2^2 * H.1^8 * H.2^-1 * H.1 in {M, -M}; true