The L2-quotient algorithm

The L2-quotient algorithm computes for a finitely presented group all quotients isomorphic to PSL(2,q) or PGL(2,q), simultaneously for all prime powers q.

A Magma implementation is available here: l2.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("l2.spec");

Note that the algorithm does not return images onto the groups PSL(2,2) = Sym(3), PSL(2,3) = Alt(4), and PSL(2,4) = PSL(2,5) = Alt(5).

Basic usage
- L2Quotients
- GetMatrices
Intermediate usage
- Coxeter groups
- Specifying orders
Advanced Usage
Handling infinite L2-quotients
Verbose printing
References

Basic usage

L2Quotients

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

> G := Group< a,b | a^2, b^3, (a*b)^7, (a,b)^11 >;
> L2Quotients(G);
[
    L_2(43)
]
> H := Group< a,b,c | a^3, b^7, c^19, (a*b)^2, (a*c)^2, (b*c)^2, (a*b*c)^2 >;
> L2Quotients(H);
[
    L_2(113)
]

This means that G has PSL(2,43) as quotient, but no other PSL(2,q) or PGL(2,q) is a quotient of G. Similarly, the only L2-quotient of H is PSL(2,113).

> G := Group< a,b | a^2, b^3, (a*b)^16, (a,b)^11 >;
> L2Quotients(G);
[
    PGL(2,23),
    PGL(2,23),
    PGL(2,463)
]

In this example, PGL(2,23) occurs twice. This means that there are two epimorphisms of G onto PGL(2,23) which do not differ by an automorphism of PGL(2,23). In other words, the kernels of the epimorphisms are distinct.

Some groups have infinitely many L2-quotients. This is indicated by one of the L2-quotients L_2(infty^k), L_2(p^(infty^d)), or L_2(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,c | a^3, b^7, (a*b)^2, (a*c)^2, (b*c)^2, (a*b*c)^2 >;      
> L2Quotients(G);                      
[
    L_2(infty^6)
]
> H := Group< a,b,c | a^3, (a,c) = (c,a^-1), a*b*a = b*a*b, a*b*a*c^-1 = c*a*b*a >;
> L2Quotients(H);
[
    L_2(3^infty)
]
> K := Group< a,b | a^3*b^3 >;
> L2Quotients(K);
[
    L_2(infty^infty)
]

Even without further interpretation of the output, this tells us that these groups are all infinite.

GetMatrices

For a finite L2-quotient of G, that is, a quotient L_2(p^k) or PGL(2,p^k), we can compute the matrix images of the generators, using GetMatrices. This method takes an L2-quotient and returns a matrix group H and a list A of 2x2 matrices in H, where A[i] corresponds to the i-th generator of G.

> H := Group< a,b,c | a^3, b^7, c^19, (a*b)^2, (a*c)^2, (b*c)^2, (a*b*c)^2 >;
> quot := L2Quotients(H); quot;
[
    L_2(113)
]
> H, A := GetMatrices(quot[1]);
> H;
MatrixGroup(2, GF(113))
Generators:
    [  0   1]
    [112 112]

    [  0  85]
    [109  24]

    [102 104]
    [ 63  72]
> A;
[
    [  0   1]
    [112 112],

    [  0  85]
    [109  24],

    [102 104]
    [ 63  72]
]

Note that G -> H, G.i -> A[i] does in general not define a homomorphism, but the induced map G -> H/Z(H) does.

Intermediate usage

Coxeter groups

A Coxeter group is a finitely presented group on m generators, such that the only other relations are (g_i*g_j)^M[i,j], where M is a symmetric matrix with non-negative integer entries and 1's along the diagonal. The matrix M is also called a Coxeter matrix. Often when dealing with Coxeter groups we are only interested in smooth quotients, that is, those which preserve the orders. The method L2Quotients accepts a Coxeter matrix as input, and computes the smooth quotients of the associated Coxeter group. However, it omits the quotients in characteristic p if M[1,2] = p. Furthermore, if a quotient has characteristic p and p divides some entry of M, then the quotient is not guaranteed to be smooth.

> M := Matrix([[1,2,3,3],[2,1,4,5],[3,4,1,6],[3,5,6,1]]);
> L2Quotients(M);
[
    L_2(4391),
    L_2(71)
]

Specifying orders

Even if the finitely presented group in question is not a Coxeter group, 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< a,b,c > := Group< a,b,c | a^16, b^4, c^2, (a*b)^8, (a,b)^4 >;
> time quot := L2Quotients(G : 
time> exactOrders := [< a, 16 >, < b, 4 >, < c, 2 >, < a*b ,8 >, < (a,b), 4 >]);
Time: 1.530

Advanced usage

There are several parameters to influence the run of L2Quotients

saturate

The algorithm discards prime ideals containing rho = x1^2 + x2^2 + x12^2 - x1*x2*x12 - 4. If the optional boolean parameter saturate is true (default: false), then prior to the primary decomposition the ideal is saturated at rho, which can be faster in some cases.

addMoreRelations

If the optional boolean parameter addMoreRelations is true (default: false), then the algorithm adds further relations to the ideal, which speeds up the computation in some cases.

exclude

The optional boolean parameter exclude is a list of primes (default: []). The algorithm does not compute L2-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 L2-quotients

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

Quotients of type L_2(infty^k)

If G has a quotient L_2(infty^k), then for almost all (all but finitely many) primes p, G has finitely many quotients of type PSL(2,p^r) or PGL(2,p^(r/2)) with r <= k. So L_2(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 L2-quotient and an integer n, and computes the L2-quotients in characteristic p|n.

> G := Group< a,b | a^2, b^3, (a*b)^7 >;
> quot := L2Quotients(G); quot;
[
    L_2(infty^3)
]
> Q := quot[1];
> SpecifyCharacteristic(Q, 7);  
[
    L_2(7)
]
> SpecifyCharacteristic(Q, 11);
[
    L_2(11^3)
]
> SpecifyCharacteristic(Q, 13);
[
    L_2(13),
    L_2(13),
    L_2(13)
]

The second is AddGroupRelations, which takes an L2-quotient and a list of group elements interpreted as relations, and computes the L2-quotients which satisfy these relations.

> G := Group< a,b | a^2, b^3, (a*b)^7 >;
> quot := L2Quotients(G); quot;
[
    L_2(infty^3)
]
> Q := quot[1];
> AddGroupRelations(Q, [(a*b*a*b^-1*a*b)^12]);
[
    L_2(13),
    L_2(7)
]

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

If G has a quotient L_2(p^(infty^d)), then there are infinitely many positive integers k such that G has a quotient of type PSL(2,p^k) or PGL(2,p^k). So L_2(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,c > := Group< a,b,c | a^3, (a,c) = (c,a^-1), a*b*a = b*a*b, a*b*a*c^-1 = c*a*b*a >;
> quot := L2Quotients(H); quot;
[
    L_2(3^infty)
]
> Q := quot[1];
> AddGroupRelations(Q, [((b^2*c^3)^2*a)^5]);
[
    L_2(3^2),
    L_2(3^4)
]

Another possibility is to add further ring relations to the ideal describing the L2-quotient, using the method AddRingRelations. It takes an L2-quotient and a list of polynomials, and computes the L2-quotients whose traces satisfy these polynomial relations.

> H< a,b,c > := Group< a,b,c | a^3, (a,c) = (c,a^-1), a*b*a = b*a*b, a*b*a*c^-1 = c*a*b*a >;
> quot := L2Quotients(H); quot;
[
    L_2(3^infty)
]
> Q := quot[1];
> Q`Ideal;
Ideal of Graded Polynomial ring of rank 7 over Integer Ring
Order: Grevlex with weights [3, 2, 2, 2, 1, 1, 1]
Variables: x123, x23, x13, x12, x3, x2, x1
Variable weights: [3, 2, 2, 2, 1, 1, 1]
Inhomogeneous, Dimension >0
Groebner basis:
[
    x123^2 + 2*x123*x3 + 1,
    x23 + 2*x3,
    x13 + 2*x3,
    x12 + 2,
    x2 + 1,
    x1 + 1,
    3
]
> R< x123, x23, x13, x12, x3, x2, x1 > := Generic(Q`Ideal);
> AddRingRelations(Q, [x3^(3^4) - x3]);
[
    L_2(3^2),
    L_2(3^4),
    L_2(3^4),
    L_2(3^4),
    L_2(3^4),
    L_2(3^4),
    L_2(3^4),
    PGL(2,3^2),
    PGL(2,3^2),
    L_2(3^4),
    L_2(3^8),
    L_2(3^8),
    L_2(3^8),
    L_2(3^8),
    L_2(3^8),
    L_2(3^4)
]

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(2,p^k) or PGL(2,p^k). So L_2(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("L2Quotients", d) to set the verbose printing for L2Quotients, where d is a value between 0 and 3.

References

[1]	S. Jambor An L2-quotient algorithm for finitely presented groups on aribtrarily many generators Preprint (2014).
[2]	W. Plesken and A. Fabianska An L2-quotient algorithm for finitely presented groups J. Algebra 322 (2009), no. 3, 914--935.