GAP (SingerAlg) - Chapter 2: Tutorial for the SingerAlg package

This chapter shows small introductory computations with the functions of the package. More examples can be found in Section 4.3.

In order to force that the examples in this manual consist only of ASCII characters, we set the user preference DisplayFunction of the package (see Section 3.2-3) to the value "Print". This is necessary because the LaTeX and HTML versions of GAPDoc documents do not support non-ASCII characters.

gap> origpref:= UserPreference( "SingerAlg", "DisplayFunction" );;
gap> SetUserPreference( "SingerAlg", "DisplayFunction", "Print" );

2.1 How to Study Singer Algebras

The definition of Singer algebras given in Section 1.2 suggests that GAP's tools for algebras defined by structure constants (see Section Reference: Constructing Algebras by Structure Constants) might be suitable for them, and Section 3.1 takes this approach.

However, the fact that the canonical bases of Singer algebras have a very special structure –the product of two basis elements is either another basis element or zero– implies that many interesting subalgebras and subspaces can be described in terms of subsets of the canonical basis. Thus many questions can be answered using combinatorial computations, without the need to add or multiply or even create elements of the algebra. Section 3.3 lists functions where this approach is taken.

Most of the functions of the SingerAlg package do not involve objects that represent algebraic structures. In particular, the Julia code does not introduce such objects.

2.2 Number Theoretic Caveats

When one deals with Singer algebras A[q,z] = A(q,n,e), with q^n-1 = e z, seemingly trivial computations can become expensive even if the dimensions (equal to z+1) and the parameters q and n are small, because the number e can still be huge; see Section 2.2-1 for examples. The point is that there are situations where one can (and then should) avoid dealing with large numbers, but there are also situations where this is not possible. Since GAP knows just one type of integers, there is no need to write different GAP code for computations with small or large integers. This is different in Julia, where one can (and wants to) write special code for computing with small integers whenever one knows in advance that there will be no overflow.

Other computational problems arise from factorization questions. One instance is the computation of the multiplicative order of q modulo z or e; an example where calling OrderMod( q, e ) runs into problems is shown in the documentation of OrderModExt (3.6-2). Here the point is that one should enter a known multiple of the desired multiplicative order as the third argument of OrderModExt (3.6-2) whenever this is possible.

Also primality tests in the context of natural questions about Singer algebras may run into problems, see Section 2.2-2.

2.2-1 Large values of e

Computational examples in the study of A(q,n,e) often avoid dealing with e because this number can be very large when the algebra itself has small dimension. Let us look at the database of A[q,z] with z ≤ 10000.

gap> cand:= AllSingerAlgebraInfos( "e", e -> e > 2^64 );;   
gap> Length( cand );                                     
543989
gap> cand:= AllSingerAlgebraInfos( "e", e -> e > 10^10000 );;         
gap> Length( cand );
12
gap> SortParallel( List( cand, r -> r.e ), cand );
gap> cand[ Length( cand ) ];
rec( LL := 3, d := [ 1, 9438 ], dec := 0, diff := 0, 
  e := <integer 646...617 (12666 digits)>, isom := [ 9439, 2 ], 
  m := 99099, n := 9438, q := 22, vprime := [ 1, 9438, 1 ], z := 9439 
 )

We see that for the majority of entries in the database, the value of e cannot be represented by a 64-bit integer, and that the largest value of e in the database is bigger than 10^12666.

When one deals with A[q,z], one of the basic tasks is to compute the q-adic coefficients of some multiple of e, i. e., to write k e = ∑_{i = 0}^n a_i q^i, with 0 ≤ a_i < q. By [BHHK21, Remark 2.23 (iv)], one can compute the a_i without dealing explicitly with numbers of the magnitude of e.

gap> q:= 22;;  n:= 9438;;  z:= 9439;;
gap> e:= (q^n-1)/z;;
gap> coeffs1:= CoefficientsQadic( e, q );;
gap> coeffs2:= CoefficientsQadicReversed( 1, z, q, n );;
gap> Length( coeffs1 );
9436
gap> Length( coeffs2 );
9438
gap> coeffs1 = Reversed( coeffs2 ){[1..9436]};  
true

Note that CoefficientsQadicReversed (3.1-12) is several times faster than CoefficientsQadic (Reference: CoefficientsQadic); the two functions in question are interpreted GAP functions. The Julia variant Julia.SingerAlg.CoefficientsQadicReversed is faster than the GAP function CoefficientsQadicReversed (3.1-12), whereas the Julia variant Julia.SingerAlg.CoefficientsQadic needs about the same time as CoefficientsQadic (Reference: CoefficientsQadic). Note that computations with small integers are much faster in Julia than in GAP, but that the Julia data type of big integers is not supported well.

2.2-2 Primality tests

Suppose we want to check whether [BHHK21, Thm. 4.3 (i)] yields that the Loewy length of a given Singer algebra A(q,n,e) is equal to the upper bound ⌊ n (q-1) / m(q,e) ⌋ + 1; for that, we have to decide whether e/2 is a prime power.

In the case of (q, z) = (8390, 21), GAP prints a message and then nothing happens for a long time.

ap> z:= 8390;
8390
gap> r:= OneSingerAlgebraInfo( "z", z, "q", 21 );;
gap> LogInt( r.e, 10 );
550
gap> IsEvenInt( r.e );
true
gap> IsPrimePowerInt( r.e/2 );
#I  Straightforward Fermat-Lucas primality proof failed on 6096...
[...]

(Fortunately, we need not check whether e/2 is a prime power; if we look into the proof of [BHHK21, Thm. 4.3 (i)], we find out that a cheaper criterion can be used.)

2.3 Some Examples from the Papers

We show the examples of Singer algebras A(q,n,e) that appear in [BHHK20]. See Section 1.2 for the meaning of the term "monomial", and Section DisplaySingerMonomials (3.2-1) for the meaning of the output that is shown.

gap> DisplaySingerMonomials( 3, 4, 5 );
A[3,4,16]

0 | 1 |  0
1 | 6 |  1  2  3  6  9 11
2 | 7 |  4  5  7  8 12 13 15
3 | 2 | 10 14
4 | 1 | 16
gap> DisplaySingerMonomials( 3, 4, 5 : m );
A[3,4,16]

0 | 1 | (0,0,0,0)
1 | 6 | (0,0,2,1) (0,1,0,1) (0,2,1,0) (1,0,0,2) (1,0,1,0) (2,1,0,0)
2 | 7 | (0,1,2,2) (0,2,0,2) (1,1,1,1) (1,2,2,0) (2,0,1,2) (2,0,2,0)
  |   | (2,2,0,1)
3 | 2 | (1,2,1,2) (2,1,2,1)
4 | 1 | (2,2,2,2)

gap> DisplaySingerMonomials( 13, 2, 8 );
A[13,2,21]

0 | 1 |  0
1 | 4 |  1  2  5 13
2 | 5 |  3  4  7 10 18
3 | 4 |  6  9 12 15
4 | 5 |  8 11 14 17 20
5 | 2 | 16 19
6 | 1 | 21
gap> DisplaySingerMonomials( 13, 2, 8 : m );
A[13,2,21]

0 | 1 | ( 0, 0)
1 | 4 | ( 0, 8) ( 1, 3) ( 3, 1) ( 8, 0)
2 | 5 | ( 1,11) ( 2, 6) ( 4, 4) ( 6, 2) (11, 1)
3 | 4 | ( 3, 9) ( 5, 7) ( 7, 5) ( 9, 3)
4 | 5 | ( 4,12) ( 6,10) ( 8, 8) (10, 6) (12, 4)
5 | 2 | ( 9,11) (11, 9)
6 | 1 | (12,12)

gap> DisplaySingerMonomials( 5, 4, 78 );
A[5,4,8]

0 | 1 | 0
1 | 3 | 1 2 5
2 | 3 | 3 4 7
3 | 1 | 6
4 | 1 | 8
gap> DisplaySingerMonomials( 5, 4, 78 : m );
A[5,4,8]

0 | 1 | (0,0,0,0)
1 | 3 | (0,3,0,3) (1,1,1,1) (3,0,3,0)
2 | 3 | (1,4,1,4) (2,2,2,2) (4,1,4,1)
3 | 1 | (3,3,3,3)
4 | 1 | (4,4,4,4)

gap> DisplaySingerMonomials( 11, 2, 4 );
A[11,2,30]

 0 | 1 |  0
 1 | 3 |  1  3 11
 2 | 5 |  2  4  6 14 22
 3 | 5 |  5  7  9 17 25
 4 | 5 |  8 10 12 20 28
 5 | 3 | 13 15 23
 6 | 3 | 16 18 26
 7 | 3 | 19 21 29
 8 | 1 | 24
 9 | 1 | 27
10 | 1 | 30
gap> DisplaySingerMonomials( 11, 2, 4 : m );
A[11,2,30]

 0 | 1 | ( 0, 0)
 1 | 3 | ( 0, 4) ( 1, 1) ( 4, 0)
 2 | 5 | ( 0, 8) ( 1, 5) ( 2, 2) ( 5, 1) ( 8, 0)
 3 | 5 | ( 1, 9) ( 2, 6) ( 3, 3) ( 6, 2) ( 9, 1)
 4 | 5 | ( 2,10) ( 3, 7) ( 4, 4) ( 7, 3) (10, 2)
 5 | 3 | ( 4, 8) ( 5, 5) ( 8, 4)
 6 | 3 | ( 5, 9) ( 6, 6) ( 9, 5)
 7 | 3 | ( 6,10) ( 7, 7) (10, 6)
 8 | 1 | ( 8, 8)
 9 | 1 | ( 9, 9)
10 | 1 | (10,10)

2.4 Example: The case n = 4

For fixed (small) n, we are interested in the question for which values of q and z the upper bound ⌊ n (q-1) / m(q,e) ⌋ + 1 on the Loewy length of A[q,n,z] is not attained.

If n ≤ 3 holds then we know by [BHHK20, Cor. 7.1] that the upper bound is always attained. For n = 5, the database of Singer algebras contains a few examples where the bound is not attained (cf. [BHHK21, Remark 7.13]).

gap> expls:= AllSingerAlgebraInfos( "n", 5,                                 
>                r -> r.LL = Int( r.n * ( r.q-1 ) / r.m ) + 1, false );;
gap> Length( expls );
13
gap> expls[1];
rec( LL := 7, d := [ 43, 408 ], dec := 0, diff := 1, e := 407592814, 
  isom := [ 1353, 223 ], m := 148, n := 5, q := 223, 
  vprime := [ 1, 261, 375, 395, 260, 61, 1 ], z := 1353 )

From now on, we fix n = 4. The upper bound is attained for all relevant entries in the database.

gap> OneSingerAlgebraInfo( "n", 4,
>        r -> r.LL = Int( r.n * ( r.q-1 ) / r.m ) + 1, false );
fail

We comute the Loewy lengths of the algebras A[q,4,z], for 2 ≤ q ≤ 40 and for all divisors z of q^4 - 1, and compare them with the upper bound.

gap> n:= 4;;
gap> for q in [ 2 .. 40 ] do
>      for z in DivisorsInt( q^n-1 ) do
>        if z > SingerAlg.MaxZ then
>          A:= SingerAlgebra( q, n, z );
>          m:= MinimalDegreeOfSingerAlgebra( A );
>          if LoewyLength( A ) <> Int( n * (q-1) / m ) + 1 then
>            Print( "found an example\n" );
>          fi;
>        fi;
>      od;
>    od;

The above computations should need less than a minute, provided that the Julia code can be used; much more time is needed if only GAP can be used. [BHHK21, Section 1] states that the bound is always attained for q ≤ 100; the computations for that need several hours (using Julia).