# The L3-U3-quotient algorithm

The L3-U3-quotient algorithm computes for a finitely presented group on two generators all quotients isomorphic to PSL(3,q), PGL(3, q), PSU(3, q), or PGU(3, q), simultaneously for all prime powers q.

A Magma implementation is available here: l3.tgz. This includes an algorithm to compute minimal associated primes.
The algorithm requires a Magma version >= 2.19.

To use the algorithm, after starting magma, type

```> Attach("minass.magma");
> AttachSpec("l3.spec");
```

Note that the algorithm does not return images onto the group PSL(3,2) = PSL(2,7).

## Basic usage

### L3Quotients

The main method is L3Quotients, which takes a finitely presented group and computes all L3-quotients.

```> G := Group< a,b | a^2, b^3, (a*b)^11, (a,b)^11 >;
> L3Quotients(G);
[
U_2(43)
]
> H := Group< a,b | a^2, b^3, (a*b)^11, (a,b)^28  >;
> L3Quotients(H);
[
U_3(43),
U_3(14057)
]
```
This means that G has PSU(3,43) as quotient, but no other PSL(3,q), PGL(3, q), PSU(3, q), or PGU(3, q) is a quotient of G. Similarly, the only L3- or U3-quotients of H are PSU(3, 43) and PSU(3, 14057).
```> G := Group< a,b | a^2, b^3, (a*b)^18, (a,b)^16  >;
> L3Quotients(G);
[
PGU(3, 71),
U_3(1889),
PGU(3, 17),
PGU(3, 17),
PGU(3, 17),
PGL(3, 19)
]
```
In this example, PGU(3,17) occurs three times. This means that there are three epimorphisms of G onto PGU(3,17) which do not differ by an automorphism of PGU(3,17). In other words, the kernels of the epimorphisms are distinct.

Some groups have infinitely many L3-quotients. This is indicated by one of the L3-quotients L_3(infty^k), L_3(p^(infty^d)), or L_3(infty^(infty^d)). See below for an interpretation of this output, and how to use Magma to get more information about the quotients.
```> G := Group< a, b | a^2, b^3, (a*b)^9 >;
> L3Quotients(G);
[
L_3(infty^18)
]
> H := Group< a, b | a^2, b^3, (a,b)^5, (a, b*a*b*a*b)^3 >;
> L3Quotients(H);
[
L_3(2^infty)
]
> K := Group< a, b | a^2, b^3 >;
> L3Quotients(K);
[
L_3(infty^(infty^2))
]
```
Even without further interpretation of the output, this tells us that these groups are all infinite.

### GetMatrices

For a finite L3-U3-quotient of G, that is, a quotient L_3(p^k), PGL(3, p^k), U_3(p^k), or PGU(3, p^k), we can compute the matrix images of the generators, using GetMatrices. This method takes an L3-U3-quotient and returns a matrix group H generated by two elements, corresponding to the generators of G.
```> G := Group< a, b | a^2, b^3, (a*b)^11, (a,b)^28 >;
> quot := L3Quotients(G); quot;
[
U_3(43),
U_3(14057)
]
> H := GetMatrices(quot[2]);
> H;
MatrixGroup(3, GF(14057^2))
Generators:
[ 13479*\$.1 + 8387  13479*\$.1 + 8388  12480*\$.1 + 1163]
[ 13727*\$.1 + 1669  13727*\$.1 + 1668   9677*\$.1 + 9154]
[ 11763*\$.1 + 3700  11763*\$.1 + 3700    908*\$.1 + 4001]

[  562*\$.1 + 11659 11987*\$.1 + 12203  4961*\$.1 + 13767]
[11922*\$.1 + 10773   5054*\$.1 + 6130   3695*\$.1 + 3079]
[  3814*\$.1 + 8470   4617*\$.1 + 9807  8441*\$.1 + 10325]
```
Note that G -> H, G.i -> H.i does in general not define a homomorphism, but the induced map G -> H/Z(H) does.

## Intermediate usage

### Specifying orders

We often are only interested in quotients where certain orders are satisfied (for instance, we might know that the generator must have a certain order). Usually this yields a great speed-up in the computation, or even allows the computation to finish in the first place.
The orders can be specified using the optional parameter exactOrders. This is a list of pairs, where the first entry is a word in the group, and the second entry is the order.
```> G := Group< a, b | a^2, b^3, (a*b)^32 >;
> time quot := L3Quotients(G : exactOrders := [< a, 2 >, < b, 3 >, < a*b, 32 >]);
Time: 13.710
```

There are several parameters to influence the run of L3Quotients

### exclude

The optional boolean parameter exclude is a list of primes (default: []). The algorithm does not compute L3-quotients in characteristic p if p is in exclude.

### Parameters influencing minimal associated primes

The optional parameters useRandomTechniques, factorizationBound, trialDivisionBound, and groebnerBasisBound are passed to the method MinimalAssociatedPrimes (see documentation there).

## Handling infinite L3-quotients

There are three types of infinite quotients, L_3(infty^k), L_3(p^(infty^d)), and L_3(infty^(infty^d))

### Quotients of type L_3(infty^k)

If G has a quotient L_3(infty^k), then for almost all (all but finitely many) primes p, G has finitely many quotients of type PSL(3,p^r), PGL(3, p^(r/3)), PSU(3, p^(r/2)), or PGU(3, p^(r/6) with r <= k. So L_3(infty^k) is a mnemonic, where infty in the base stands for infinitely many primes, and k stands for the highest possible exponent.

There are two basic methods to further investigate such quotients. The first is SpecifyCharacteristic, which takes an L3-quotient and an integer n, and computes the L3-quotients in characteristic p|n.
```> G := Group< a, b | a^2, b^3, (a*b)^9 >;
> quot := L3Quotients(G); quot;
[
L_3(infty^18)
]
> Q := quot[1];
> SpecifyCharacteristic(Q, 103);
[
PGL(3, 103^3)
]
> SpecifyCharacteristic(Q, 107);
[
U_3(107),
U_3(107),
U_3(107)
]
> SpecifyCharacteristic(Q, 109);
[
L_3(109),
L_3(109),
L_3(109)
]
> SpecifyCharacteristic(Q, 113);
[
PGU(3, 113^3)
]
```
The second is AddGroupRelations, which takes an L3-quotient and a list of group elements interpreted as relations, and computes the L3-quotients which satisfy these relations.
```> G< a, b > := Group< a, b | a^2, b^3, (a*b)^11 >;
> quot := L3Quotients(G); quot;
[
L_3(infty^20)
]
> Q := quot[1];
[
L_3(353^2),
U_3(241)
]
```

### Quotients of type L_3(p^(infty^d))

If G has a quotient L_3(p^(infty^d)), then there are infinitely many positive integers k such that G has a quotient of type PSL(3,p^k), PGL(3, p^k), PSU(3, p^k), or PGU(3,p^k). So L_3(p^(infty^d)) is a mnemonic, where infty in the exponent stands for infinitely many possible exponents. The parameter d describes the degree of infinity, and is ommited if d = 1.

Again, we can use AddGroupRelations to sudy this quotient further.
```> H< a, b > := Group< a, b | a^2, b^3, (a,b)^5, (a, b*a*b*a*b)^3 >;
> quot := L3Quotients(H); quot;
[
L_3(2^infty)
]
> Q := quot[1];
[
PGL(3, 2^2),
U_3(2^2)
]
```
Another possibility is to add further ring relations to the ideal describing the L3-quotient, using the method AddRingRelations. It takes an L3-quotient and a list of polynomials, and computes the L3-quotients whose traces satisfy these polynomial relations.
```> H< a, b > := Group< a, b | a^2, b^3, (a,b)^5, (a, b*a*b*a*b)^3 >;
> quot := L3Quotients(H); quot;
[
L_3(2^infty)
]
> Q := quot[1];
> Q`Ideal;
Ideal of Graded Polynomial ring of rank 10 over Integer Ring
Order: Grevlex with weights [8, 2, 2, 2, 2, 4, 4, 4, 4, 1]
Variables: xcom, x1, xm1, x2, xm2, x12, xm12, xm21, xm2m1, zeta
Variable weights: [8, 2, 2, 2, 2, 4, 4, 4, 4, 1]
Inhomogeneous, Dimension >0
Groebner basis:
[
xcom + zeta + 1,
xm12*xm2m1 + zeta,
x12 + xm12,
xm21 + xm2m1,
x1 + 1,
xm1 + 1,
x2,
xm2,
zeta^2 + zeta + 1,
2
]
> R< xcom, x1, xm1, x2, xm2, x12, xm12, xm21, xm2m1, zeta > := Generic(Q`Ideal);
> AddRingRelations(Q, [x12^5 + xm21^2 + 1]);
[
L_3(2^8),
L_3(2^6)
]
```

### Quotients of type L_2(infty^(infty^d))

If G has a quotient L_2(infty^(infty^d)), then for almost all primes p and infinitely many positive integers k, G has a quotient of type PSL(3,p^k), PGL(3, p^k), PSU(3, p^k), or PGU(3, p^k). So L_3(infty^(infty^d)) is a mnemonic, where infty in the base stands for infinitely many primes, and infty in the exponent stands for infinitely many possible exponents. The parameter d describes the degree of infinity, and is ommited if d = 1. These quotients can be further investigated using the methods AddGroupRelations, AddRingRelations, and SpecifyCharacteristic.

## Verbose printing

Use SetVerbose("L3Quotients", d) to set the verbose printing for L3Quotients, where d is a value between 0 and 3.

## References

 [1] S. Jambor An L3-U3-quotient algorithm for finitely presented groups PhD Thesis (2012).