[MathJax on]

3 Functions for Singer algebras

3.1 Singer Algebras as Algebraic Structures

3.1-1 SingerAlgebra

For nonnegative integers q, z with q > 1, and a field R (with default the field of Rationals, see Rationals (Reference: Rationals)), let n be the multiplicative order of q modulo z, set e = (q^n - 1) / z, and define A[q, z] as the free R-module with basis (b_0, b_1, ..., b_z) and multiplication defined as follows. If there is no carry in the addition of the q-adic expansions of i e and j e then b_i b_j = b_{i+j} holds, and otherwise b_i b_j is zero.

This function returns the algebra A[q, z].

Alternatively, a record arec can be given, which must have the components q and z or the components q, n, e.

The idea is to use the algebra object first of all as a container for the attributes that belong to the parameters q and z, see LoewyLength (3.1-6), MinimalDegreeOfSingerAlgebra (3.1-8), and LoewyStructureInfo (3.1-11). This works well also for high dimensional algebras.

If one really wants to do computations beyond this context, for example compute with elements of the algebra, then special methods for CanonicalBasis (Reference: CanonicalBasis), Representative (Reference: Representative), GeneratorsOfAlgebra (Reference: GeneratorsOfAlgebra), or GeneratorsOfAlgebraWithOne (Reference: GeneratorsOfAlgebraWithOne) will trigger the computation of a structure constants table, and afterwards the algebra behaves like other algebras in GAP that are defined via structure constants.

gap> A:= SingerAlgebra( 6, 2, 7 );
A[6,2,7]
gap> Dimension( A );   # is always z+1
8
gap> LeftActingDomain( A );
Rationals
gap> A2:= SingerAlgebra( 6, 2, 7, GF(2) );
A[6,2,7,GF(2)]
gap> Print( A2, "\n" );
SingerAlgebra( 6, 2, 7, GF(2) )
gap> String( A2 );
"SingerAlgebra( 6, 2, 7, GF(2) )"
gap> SingerAlgebra( rec( q:= 6, n:= 2, e:= 5 ) );
A[6,2,7]

3.1-2 IsSingerAlgebra

This filter is set in all algebras constructed with SingerAlgebra (3.1-1).

gap> A:= SingerAlgebra( 6, 7 );
A[6,2,7]
gap> IsSingerAlgebra( A );
true
gap> AA:= AlgebraByStructureConstants( Rationals,
>             StructureConstantsTable( Basis( A ) ) );
<algebra of dimension 8 over Rationals>
gap> IsSingerAlgebra( AA );
false

3.1-3 ParametersOfSingerAlgebra

For a Singer algebra A= A[q,n,z] (see SingerAlgebra (3.1-1)), the value is the list [ q, n, z ].

gap> A:= SingerAlgebra( 6, 7 );
A[6,2,7]
gap> ParametersOfSingerAlgebra( A );
[ 6, 2, 7 ]

3.1-4 DimensionsLoewyFactors

For a Singer algebra A (see SingerAlgebra (3.1-1)), this function returns the Loewy vector of A, that is, the list of nonzero dimensions J^{i-1} / J^i, for i ≥ 1, where J is the Jacobson radical of A and J^0 =A.

LoewyVector is a synonym of DimensionsLoewyFactors.

gap> A:= SingerAlgebra( 6, 2, 7 );
A[6,2,7]
gap> DimensionsLoewyFactors( A );
[ 1, 6, 1 ]

In the GAP Reference Manual, this attribute is declared for groups, see DimensionsLoewyFactors (Reference: DimensionsLoewyFactors). In that context, it means the dimensions of the Loewy factors of the group algebra of its argument over the field with p elements, where the argument is required to be a finite p-group. Note that this value can be computed just from the group, without constructing a group algebra.

3.1-5 LoewyVectorAbbreviated and LoewyVectorExpanded

For a dense list v of positive integers, LoewyVectorAbbreviated returns a new list in which each maximal sublist of at least two consecutive equal entries is replaced by the list containing this element and its multiplicity.

For a dense list v whose entries are non-lists and pairs whose second entries are positive integers, LoewyVectorExpanded returns a new list in which each such pair is replaced by a sublist that contains the first entry with multiplicity given by the second entry.

gap> LoewyVectorAbbreviated( [ 1, 1, 1, 1 ] );
[ [ 1, 4 ] ]
gap> LoewyVectorAbbreviated( [ 1, 7, 7, 3, 3, 1, 1, 1 ] );
[ 1, [ 7, 2 ], [ 3, 2 ], [ 1, 3 ] ]
gap> LoewyVectorExpanded( [ [ 1, 4 ] ] );
[ 1, 1, 1, 1 ]
gap> LoewyVectorExpanded( [ 1, [ 7, 2 ], [ 3, 2 ], [ 1, 3 ] ] );
[ 1, 7, 7, 3, 3, 1, 1, 1 ]

3.1-6 LoewyLength

Let q, n, z be positive integers such that z divides q^n - 1; the default for n is the multiplicative order of q modulo z. These functions return the Loewy length of the Singer algebra A[q,n,z], see SingerAlgebra (3.1-1).

Alternatively, also a Singer algebra A can be given as an argument.

Note that it may be cheap to compute the Loewy length of this algebra, using criteria from [BHHK20] and [BHHK21], even if computing its Loewy vector (see DimensionsLoewyFactors (3.1-4)) would be hard.

If Julia is available then LoewyLength uses LoewyLengthJulia, otherwise it uses LoewyLengthGAP.

gap> A:= SingerAlgebra( 6, 2, 7 );
A[6,2,7]
gap> LoewyLength( A );
3

3.1-7 SufficientCriterionForLoewyBoundAttained

Returns: a string.

Let q, n, z, m be positive integers, where q and z are coprime. SufficientCriterionForLoewyBoundAttained returns a string that describes the criterion from [BHHK20] or [BHHK21] from which it follows that the Loewy length of the algebra A[q,z] is equal to the upper bound ⌊ n (q-1) / m ⌋ + 1, where n = OrderMod(q, z), e = (q^n-1) / z, and m = m(q, e); if no such criterion was found then the returned string is empty.

gap> expls:= [ [3,2], [2,5], [3,70], [13,70], [19,70], [5,72],
>              [2,73], [5,76], [11,80], [13,80], [2,85], [4,123],
>              [3,164], [4,369], [2,771], [15,791] ];;
gap> for l in expls do
>      q:= l[1];  z:= l[2];  n:= OrderMod( q, z );  e:= (q^n-1)/z;
>      nn:= OrderModExt( q, e, n );
>      m:= MinimalDegreeOfSingerAlgebra( q, nn, e );
>      Print( "q = ", String( q, 2 ), ", z = ", String( z, 3 ), ":  ",
>      SufficientCriterionForLoewyBoundAttained( q, n, z, m ), "\n" );
>    od;
q =  3, z =   2:  Cor. I.7.1 (n <= 3)
q =  2, z =   5:  z < 70
q =  3, z =  70:  
q = 13, z =  70:  Thm. I.7.1
q = 19, z =  70:  La. I.7.1 (iii)
q =  5, z =  72:  La. II.4.1 for r = 1
q =  2, z =  73:  Prop. II.6.1 (e <= 32)
q =  5, z =  76:  Prop. II.5.1 (ii)
q = 11, z =  80:  Prop. II.5.3, II.5.6 (e | (q^n-1)/(q-1), n <= 5)
q = 13, z =  80:  Prop. II.3.15
q =  2, z =  85:  La. I.6.3
q =  4, z = 123:  Prop. II.5.1 (iii)
q =  3, z = 164:  La. II.5.2 (ii)
q =  4, z = 369:  Prop. II.5.1 (i)
q =  2, z = 771:  La. II.4.1
q = 15, z = 791:  Thm. II.4.3 (iii)

3.1-8 MinimalDegreeOfSingerAlgebra

Returns: a positive integer.

For two coprime positive integers q and e, MinimalDegreeOfSingerAlgebra computes the minimal number of powers of q such that e divides the sum of these powers.

If a Singer algebra A[q,z] is given as the argument A (see SingerAlgebra (3.1-1)) then the value for the parameters q and e = (q^n-1)/z is returned, where n is the multiplicate order of q modulo z, see OrderMod (Reference: OrderMod); note that the minimal degree does not depend on n.

The same value is returned by MinimalDegreeOfSingerAlgebraGAP and MinimalDegreeOfSingerAlgebraJulia, which use implementations in GAP and Julia, respectively. MinimalDegreeOfSingerAlgebra delegates to the Julia variant if the package JuliaInterface is available, and to the GAP variant otherwise.

gap> A:= SingerAlgebra( 6, 2, 7 );
A[6,2,7]
gap> MinimalDegreeOfSingerAlgebra( A );
5
gap> MinimalDegreeOfSingerAlgebra( 6, 5 );
5

3.1-9 RadicalSeriesOfAlgebra

For an algebra A with radical J (see RadicalOfAlgebra (Reference: RadicalOfAlgebra)), RadicalSeriesOfAlgebra returns the list [ J^0, J^1, J^2, J^3, ..., J^k ], where k is the smallest index such that J^k is zero.

gap> A:= SingerAlgebra( 2, 7 );
A[2,3,7]
gap> ser:= RadicalSeriesOfAlgebra( A );
[ A[2,3,7], <algebra of dimension 7 over Rationals>, 
  <algebra of dimension 4 over Rationals>, 
  <algebra of dimension 1 over Rationals>, 
  <algebra of dimension 0 over Rationals> ]

3.1-10 SocleSeriesOfAlgebra

For an algebra A, SocleSeriesOfAlgebra returns the list [ S_0, S_1, S_2, S_3, ..., S_k ], where S_0 is the trivial subalgebra of A and S_{i+1}/S_i is the socle of A/S_i and k is the smallest index such that S_k = A holds. (Thus S_1 is the socle of A.)

gap> A:= SingerAlgebra( 2, 7 );
A[2,3,7]
gap> ser:= SocleSeriesOfAlgebra( A );
[ <algebra of dimension 0 over Rationals>, 
  <algebra of dimension 1 over Rationals>, 
  <algebra of dimension 4 over Rationals>, 
  <algebra of dimension 7 over Rationals>, A[2,3,7] ]

3.1-11 LoewyStructureInfo

For a Singer algebra A (see SingerAlgebra (3.1-1)) with parameters q, n, z, or for these parameters themselves, these three operations compute the distribution of the canonical basis in A[q,z] to Loewy layers, using the algorithm from [BHHK20, Proposition 3.2].

Let e = (q^{n}-1)/z.

LoewyStructureInfoJulia returns a Julia dictionary whose keys are the following symbols.

:monomials

the array of reversed (see CoefficientsQadicReversed (3.1-12)) q-adic expansions for multiples of e, each of length n,

:layers

the array of the Loewy layers to which the monomials belong,

:chain

an array of positions of monomials of a longest ascending chain,

:m

the value m(q, e) (see MinimalDegreeOfSingerAlgebra (3.1-8)

:LL

the Loewy length of A (see LoewyLength (3.1-6)), equal to the length of the :layers value plus 1,

:parameters

the array [ q, n, z ] of parameters of A.

LoewyStructureInfoGAP returns a GAP record whose components correspond to the keys listed above. LoewyStructureInfo returns the same; however, if Julia is available then this result is computed by converting the result of LoewyStructureInfoJulia to a GAP object.

gap> LoewyStructureInfo( 6, 7 );
rec( LL := 3, chain := [ 8, 2, 1 ], 
  layers := [ 0, 1, 1, 1, 1, 1, 1, 2 ], m := 5, 
  monomials := [ [ 0, 0 ], [ 0, 5 ], [ 1, 4 ], [ 2, 3 ], [ 3, 2 ], 
      [ 4, 1 ], [ 5, 0 ], [ 5, 5 ] ], parameters := [ 6, 2, 7 ] )

3.1-12 CoefficientsQadicReversed

Let k, z, q, n be positive integers such that 0 ≤ k ≤ z, q > 1, and n > 0.

This function computes the coefficients of the q-adic expansion of e = k (q^n-1)/z, of length n, without creating this number, which may be a large integer although all arguments are small (see [BHHK21, Remark 2.23 (iv)] and section 2.2-1).

If e = v_n q^0 + v_{n-1} q^1 + ⋯ + v_1 q^{n-1} then the returned array is [ v_1, v_2, ..., v_n ].

gap> CoefficientsQadicReversed( 2, 7, 6, 2 );
[ 1, 4 ]
gap> e:= (6^2-1)/7;
5
gap> CoefficientsQadic( 2*e, 6 );
[ 4, 1 ]

3.2 Visualization of Singer Algebras

The following functions can be used to show the canonical basis of a Singer algebra in a two-dimensional array, where the rows correspond to Loewy layers.

3.2-1 DisplaySingerMonomials

Returns: nothing.

Let A be a Singer algebra A[q, n, z], where n is the multiplicative order of q modulo z, or let q and z be two coprime integers that define such an algebra A[q, n, z], or let q, n, e be parameters such that z = (q^{n}-1) / e holds.

DisplaySingerMonomials prints a table showing three column parts: The first column contains the positions 0, 1, ... of the Loewy layers of A, the second column contains the dimensions of the Loewy layers, and the remaining columns describe the elements of the canonical basis of A in each layer; by default, the element b_i is represented by i, but when the global option m is present (which stands for "monomials") then B_i is represented by the coefficients of the q-adic expansion of i e.

gap> DisplaySingerMonomials( 2, 7 );  # e = 1
A[2,3,7]

0 | 1 | 0
1 | 3 | 1 2 4
2 | 3 | 3 5 6
3 | 1 | 7
gap> DisplaySingerMonomials( 2, 7 : m );  # same, show monomials
A[2,3,7]

0 | 1 | (0,0,0)
1 | 3 | (0,0,1) (0,1,0) (1,0,0)
2 | 3 | (0,1,1) (1,0,1) (1,1,0)
3 | 1 | (1,1,1)
gap> DisplaySingerMonomials( 9, 8 : m );  # uniserial case
A[9,1,8]

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

0 | 1 | (0,0)
1 | 6 | (0,5) (1,4) (2,3) (3,2) (4,1) (5,0)
2 | 1 | (5,5)
gap> DisplaySingerMonomials( 14, 15 : m );  # wrapped output
A[14,2,15]

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

3.2-2 BrowseSingerMonomials

Returns: nothing.

Let A be a Singer algebra A[q, n, z], where n is the multiplicative order of q modulo z, or let q and z be two coprime integers that define such an algebra A[q, n, z], or let q, n, e be parameters such that z = (q^{n}-1) / e holds.

BrowseSingerMonomials opens a Browse table showing three column parts: The first column contains the positions 0, 1, ... of the Loewy layers of A, the second column contains the dimensions of the Loewy layers, and the remaining columns describe the elements of the canonical basis of A in each layer; by default, the element b_i is represented by i, but when the global option m is present (which stands for "monomials") then B_i is represented by the coefficients of the q-adic expansion of i e. The first two columns are regarded as row labels, that is, their horizontal position is fixed on the screen when one scrolls to the left or right in the third column

BrowseSingerMonomials is based on the NCurses.BrowseDenseList (Browse: NCurses.BrowseDenseList) function from the Browse package [BL20]; it is available only if this package is available.

gap> if IsBound( BrowseSingerMonomials ) then
>   n:= [ 14, 14, 14 ];;  # ``do nothing'' input
>   BrowseData.SetReplay( Concatenation( n, n, "Q" ) );
>   BrowseSingerMonomials( 2, 7 );
>   BrowseData.SetReplay( false );
> fi;

3.2-3 Changing the display format: User preference DisplayFunction

The way how the function DisplaySingerMonomials (3.2-1) shows tabular information can be customized via the user preference "DisplayFunction" of the SingerAlg package. The value must be a string that evaluates to a GAP function. Useful values are "Print" (see Print (Reference: Print)), "PrintFormattedString" (see PrintFormattedString (GAPDoc: PrintFormattedString) in [LN19]), and "SingerAlg.Pager", which means that Pager (Reference: Pager) is called with the formatted option, which is necessary for switching off GAP's automatic line breaking. The default value is "SingerAlg.Pager" if GAPInfo.TermEncoding has the value "UTF-8", and "Print" otherwise.

3.3 Singer Algebras as Combinatorial Structures

Many interesting subalgebras and subspaces U, say, of a Singer algebra A = A[q,z] or A = A[q,z]_p have vector space bases that are subsets of the canonical basis B(A), that is, U is spanned by the set U ∩ B(A). We call these subspaces combinatorial, and write B(U) = U ∩ B(A), the canonical basis of U. The examples of combinatorial subspaces for which implementations are provided are listed below.

Each of the GAP functions in question returns the set of indices i such that the basis vectors B(A[q,z])_i are members of B(U). The idea is that this set can be computed combinatorially, without performing computations with elements of the algebra A, and that for example the product space of two combinatorial subspaces is again combinatorial. The availability of the attribute GeneratingSubsetOfCanonicalBasisOfSingerAlgebra (3.3-1) in a subspace U marks U as combinatorial, and the attribute value is the set of indices of B(U).

3.3-1 GeneratingSubsetOfCanonicalBasisOfSingerAlgebra

Let U be a subspace of a Singer algebra A, say. If this attribute is set in U then the value is a strictly sorted list of nonnegative integers such that the corresponding subset of the canonical basis of A is a basis of U. In particular, U is a combinatorial subspace of A, see the introduction of Section 3.3.

There is no default method for computing the value of this attribute. On the other hand, if the value is known then there are efficient methods to compute annihilators, product spaces, etc.

gap> A:= SingerAlgebra( 3, 7 );
A[3,6,7]
gap> J:= RadicalOfAlgebra( A );;
gap> HasGeneratingSubsetOfCanonicalBasisOfSingerAlgebra( J );
true
gap> GeneratingSubsetOfCanonicalBasisOfSingerAlgebra( J );
[ 2 .. 8 ]
gap> P:= ProductSpace( J, J );
<vector space of dimension 1 over Rationals>
gap> HasGeneratingSubsetOfCanonicalBasisOfSingerAlgebra( P );
true
gap> GeneratingSubsetOfCanonicalBasisOfSingerAlgebra( P );
[ 8 ]
gap> V:= Subspace( A, Basis( A ){ [ 2, 3 ] } );;
gap> HasGeneratingSubsetOfCanonicalBasisOfSingerAlgebra( V );
false

3.3-2 SingerAlg.MultTable

Let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A[q,z], and let B = B(A). SingerAlg.MultTable returns the (z+1) × (z+1) matrix that contains at the position (i,j) the value i+j-1 if the product B_i ⋅ B_j is nonzero (hence equal to B_{i+j-1}, the i+j-1-th basis vector), and 0 otherwise.

gap> data:= LoewyStructureInfoGAP( 2, 3, 7 );;
gap> Display( SingerAlg.MultTable( data ) );
[ [  1,  2,  3,  4,  5,  6,  7,  8 ],
  [  2,  0,  4,  0,  6,  0,  8,  0 ],
  [  3,  4,  0,  0,  7,  8,  0,  0 ],
  [  4,  0,  0,  0,  8,  0,  0,  0 ],
  [  5,  6,  7,  8,  0,  0,  0,  0 ],
  [  6,  0,  8,  0,  0,  0,  0,  0 ],
  [  7,  8,  0,  0,  0,  0,  0,  0 ],
  [  8,  0,  0,  0,  0,  0,  0,  0 ] ]

The multiplication table of a Singer algebra of dimension N has the value N on the antidiagonal (i+j = N+1), is zero below the antidiagonal, and contains only N-i and zero on the i parallel above the antidiagonal.

3.3-3 SingerAlg.BasisOfSum and SingerAlg.BasisOfIntersection

For two subsets I, J of { 1, 2, ..., z+1 }, these functions just return the union and the intersection, respectively, of I and J.

I and J describe subsets of a basis, which generate the spaces U and V, say, then the result describes the subset of this basis that generates the sum and the intersection, respectively, of U and V.

gap> SingerAlg.BasisOfSum( data, [ 1, 2, 3 ], [ 2, 4, 6 ] );
[ 1, 2, 3, 4, 6 ]
gap> SingerAlg.BasisOfIntersection( data, [ 1, 2, 3 ], [ 2, 4, 6 ] );
[ 2 ]

3.3-4 SingerAlg.BasisOfProductSpace

Let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], let B = B(A), and let I, J be subsets of { 1, 2, ..., z+1 }, describing subspaces U, V of A with bases ( B_i; i ∈ I ) and ( B_i; i ∈ J ), respectively. SingerAlg.BasisOfProductSpace returns the subset K of { 1, 2, ..., z+1 } such that ( B_i; i ∈ K ) is a basis of the product space U ⋅ V.

gap> data:= LoewyStructureInfoGAP( 2, 7 );;
gap> radser:= SingerAlg.BasesOfRadicalSeries( data );
[ [ 2 .. 8 ], [ 4, 6, 7, 8 ], [ 8 ] ]
gap> SingerAlg.BasisOfProductSpace( data, radser[1], radser[1] );
[ 4, 6, 7, 8 ]
gap> SingerAlg.BasisOfProductSpace( data, radser[1], radser[2] );
[ 8 ]
gap> SingerAlg.BasisOfProductSpace( data, radser[2], radser[2] );
[  ]

3.3-5 SingerAlg.BasisOfIdeal

Let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], let B = B(A), and let I be a subset of { 1, 2, ..., z+1 }, describing a subspace U of A with basis ( B_i; i ∈ I ). SingerAlg.BasisOfIdeal returns the subset J of { 1, 2, ..., z+1 } such that ( B_i; i ∈ J ) is a basis of the ideal U ⋅ A.

gap> data:= LoewyStructureInfoGAP( 2, 7 );;
gap> SingerAlg.BasisOfIdeal( data, [ 4 ] );
[ 4, 8 ]

3.3-6 SingerAlg.BasisOfAnnihilator

Let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], let B = B(A), and let I be a subset of { 1, 2, ..., z+1 }, describing a subspace U of A with basis ( B_i; i ∈ I ). SingerAlg.BasisOfAnnihilator returns the subset J of { 1, 2, ..., z+1 } such that ( B_i; i ∈ J ) is a basis of the annihilator { x ∈ A; x ⋅ U = 0 } of U in A.

gap> data:= LoewyStructureInfoGAP( 2, 7 );;
gap> radser:= SingerAlg.BasesOfRadicalSeries( data );
[ [ 2 .. 8 ], [ 4, 6, 7, 8 ], [ 8 ] ]
gap> List( radser, I -> SingerAlg.BasisOfAnnihilator( data, I ) );
[ [ 8 ], [ 4, 6, 7, 8 ], [ 2, 3, 4, 5, 6, 7, 8 ] ]

3.3-7 SingerAlg.BasesOfRadicalSeries

Let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], and let B = B(A). SingerAlg.BasesOfRadicalSeries returns the list [ I_1, I_2, ..., I_l ] of subsets of { 1, 2, ..., z+1 } such that ( B_i; i ∈ I_j ) is a basis of the j-th power of the Jacobson radical J of A, and such that J^l is nonzero and J^{l+1} is zero.

gap> data:= LoewyStructureInfoGAP( 2, 7 );;
gap> radser:= SingerAlg.BasesOfRadicalSeries( data );
[ [ 2 .. 8 ], [ 4, 6, 7, 8 ], [ 8 ] ]

3.3-8 SingerAlg.BasesOfSocleSeries

Let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], and let B = B(A). SingerAlg.BasesOfSocleSeries returns the list [ I_1, I_2, ..., I_l ] of subsets of { 1, 2, ..., z+1 } such that ( B_i; i ∈ I_j ) is a basis of S_j, where S_1 is the socle of A, S_{j+1}/S_j is the socle of A/S_j, and A/S_l is nonzero and its own socle.

gap> socser:= SingerAlg.BasesOfSocleSeries( data );
[ [ 8 ], [ 4, 6, 7, 8 ], [ 2 .. 8 ] ]

3.3-9 SingerAlg.BasisOfPowers

Let p be a prime integer, let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], let B = B(A_p), let I be a subset of { 1, 2, ..., z+1 }, describing a subspace U of A_p with basis ( B_i; i ∈ I ), and let m be a positive integer. SingerAlg.BasisOfPowers returns the subset J of { 1, 2, ..., z+1 } such that ( B_i; i ∈ J ) is a basis of the subspace { x^{p^m}; x ∈ U } of A_p.

gap> data:= LoewyStructureInfoGAP( 3, 8 );;
gap> SingerAlg.BasisOfPowers( data, [ 1 .. 9 ], 2, 1 );
[ 1, 3, 7, 9 ]
gap> SingerAlg.BasisOfPowers( data, [ 1 .. 9 ], 2, 2 );
[ 1 ]
gap> SingerAlg.BasisOfPowers( data, [ 1 .. 9 ], 3, 1 );
[ 1 ]

3.3-10 SingerAlg.BasisOfPMRoots

Let p be a prime integer, let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], let B = B(A_p), let I be a subset of { 1, 2, ..., z+1 }, describing a subspace U of A_p with basis ( B_i; i ∈ I ), and let m be a positive integer. (See Section 1.2 for the definition of A_p.)

SingerAlg.BasisOfPMRoots returns the subset J of { 1, 2, ..., z+1 } such that ( B_i; i ∈ J ) is a basis of the subspace { x ∈ A_p; x^{p^m} ∈ U } of A_p.

gap> data:= LoewyStructureInfoGAP( 3, 8 );;
gap> SingerAlg.BasisOfPMRoots( data, [], 2, 1 );
[ 3, 6, 7, 8, 9 ]
gap> SingerAlg.BasisOfPMRoots( data, [], 2, 2 );
[ 2, 3, 4, 5, 6, 7, 8, 9 ]
gap> SingerAlg.BasisOfPMRoots( data, [ 3 ], 2, 1 );
[ 2, 3, 6, 7, 8, 9 ]

3.3-11 SingerAlg.BasisOfPC

Let data be the record returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], let B = B(A), let I and J be subsets of { 1, 2, ..., z+1 }, describing subspaces U and V of A with bases ( B_i; i ∈ I ) and ( B_i; i ∈ J ), respectively. SingerAlg.BasisOfPC returns the subset K of { 2, 3, ..., z+1 } such that ( B_i; i ∈ K ) is a basis of the subspace { x ∈ J(A); x ⋅ U ⊆ V } of J(A).

(The perhaps strange name "BasisOfPC" was chosen because the result contains the indices of those basis vectors such that the Product with the space U is Contained in the space V.)

gap> data:= LoewyStructureInfoGAP( 23, 585 );;
gap> soc:= SingerAlg.BasesOfSocleSeries( data );;
gap> rad:= SingerAlg.BasesOfRadicalSeries( data );;
gap> I1:= SingerAlg.BasisOfPC( data, soc[3], rad[3] );;
gap> Length( I1 );
581
gap> data:= LoewyStructureInfoGAP( 212, 585 );;
gap> soc:= SingerAlg.BasesOfSocleSeries( data );;
gap> rad:= SingerAlg.BasesOfRadicalSeries( data );;
gap> I2:= SingerAlg.BasisOfPC( data, soc[3], rad[3] );;
gap> Length( I2 );
545

3.4 Permutation Isomorphism of Singer Algebras

Proving that two given Singer algebras are isomorphic is in general hard. An easier question is whether an algebra isomorphism exists that maps the canonical basis of the first to the canonical basis of the second. (And fortunately this situation occurs in quite a few cases, see 4.3-4.)

The following functions can be used to check for such permutation isomorphisms.

3.4-1 SingerAlg.IsInducedAlgebraIsomorphism

Returns: true or false.

Let t1 and t2 be the multiplication tables of two Singer algebras A_1, A_2, respectively, of the same dimension z+1, say, as returned by SingerAlg.MultTable (3.3-2). Let perm be a permutation with largest moved point at most z.

This function returns true if mapping the i-th vector of the canonical basis of A_1 to the i^perm-th vector of the canonical basis of A_2 defines an algebra isomorphism, and false otherwise.

gap> # Loewy length 3, naturally isomorphic
gap> t1:= SingerAlg.MultTable( LoewyStructureInfo( 3, 7 ) );;
gap> t2:= SingerAlg.MultTable( LoewyStructureInfo( 6, 7 ) );;
gap> SingerAlg.IsInducedAlgebraIsomorphism( t1, t2, () );
true
gap> # q1 and q2 generate the same group of residues modulo z,
gap> # naturally isomorphic
gap> t1:= SingerAlg.MultTable( LoewyStructureInfo( 2, 7 ) );;
gap> t2:= SingerAlg.MultTable( LoewyStructureInfo( 4, 7 ) );;
gap> SingerAlg.IsInducedAlgebraIsomorphism( t1, t2, () );
true
gap> # one of the explicitly computed natural isomorphisms
gap> t1:= SingerAlg.MultTable( LoewyStructureInfo( 3, 65 ) );;
gap> t2:= SingerAlg.MultTable( LoewyStructureInfo( 9, 65 ) );;
gap> SingerAlg.IsInducedAlgebraIsomorphism( t1, t2, () );
true
gap> # one of the explicitly computed permutation isomorphisms
gap> # that are not natural isomorphisms
gap> t1:= SingerAlg.MultTable( LoewyStructureInfo(  41, 275 ) );;
gap> t2:= SingerAlg.MultTable( LoewyStructureInfo( 116, 275 ) );;
gap> SingerAlg.IsInducedAlgebraIsomorphism( t1, t2, () );
false
gap> pi:= (2,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3)
> (28,29,30,31,32)(38,39,40,41,42)(43,44,45,46,47,48,49,50)
> (54,55,57,79,77,94,91,89,87,83,82,81,80,78,76,75,74,73,72,64,65,63,62,
> 61,60)
> (85,99,97,93,90,88,86)(92,108,107,106,105,98,96,95)
> (109,110,112,113,115)
> (114,116,117,120,118,121,124,127,119,122,125,129,132,149,146,144,143,
> 142,141,140,154,151,147,163,161,160,157,159,156,153,150,158,155,152,
> 148,145,128,131,133,134,135,136,137,123,126,130)(162,168,167,165,164)
> (169,170,171,172,179,181,182,185)(178,180,184,187,189,191,192)
> (183,186,188,190,194,195,196,197,199,201,202,203,204,205,213,212,214,
> 215,216,217,223,222,220,198,200)(227,234,233,232,231,230,229,228)
> (235,239,238,237,236)(245,249,248,247,246)
> (253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,
> 270,271,272,273,274,275);;
gap> SingerAlg.IsInducedAlgebraIsomorphism( t1, t2, pi );
true
gap> SingerAlg.IsInducedAlgebraIsomorphism( t1, t2, pi^-1 );
false

3.4-2 SingerAlg.ProposedPermutationIsomorphism

Returns: a string, a permutation, fail, or a record.

Let data1 and data2 be the LoewyStructureInfo (3.1-11) values of two Singer algebras A_1, A_2, respectively, of the same dimension z+1, say.

If only two arguments are given then this function returns either a string that describes why there is no algebra isomorphism induced by mapping the canonical basis of A_1 to the permuted canonical basis of A_2, or fail (indicating that the relevant functionality of the GraPe package is not available), or a permutation π such that at least the following necessary conditions for such a mapping are satisfied.

• π maps pairs (i,j) where b_i ⋅ b_j is zero to pairs (k,l) where B_k ⋅ B_l is zero.

• The basis vectors b_i and B_{π(i)} lie in the same Loewy layer and in the same socle layer.

• The basis vector b_i is a p^m-th power if and only if B_{π(i)} is a p^m-th power.

The first condition is forced via a call to the function GraphIsomorphism (GRAPE: GraphIsomorphism) (which is based on [McK90]) from the GAP package GraPe [Soi19] with two graphs whose incidence relation is defined by this property, and the other conditions are translated into colorings of these graphs.

When a permutation is returned, one can check with SingerAlg.IsInducedAlgebraIsomorphism (3.4-1) whether it does in fact induce an algebra isomorphism. (For Singer algebras A[q,z] with z ≤ 10000, this is always the case, see Section 4.3-4.)

If the string "reduced" is given as the third argument then a record is returned instead of a permutation, with the following components.

preims:

a subset of [ 2 .. z ] denoting indices of the canonical basis of A_1,

imgs:

a subset of [ 2 .. z ] denoting indices of the canonical basis of A_2,

iso:

a permutation.

The proposed permutation isomorphism maps the preims[i]-th basis vector of A_1 to the imgs[i^iso]-th basis vector of A_2, and maps the other basis vectors of A_1 such that pairs (b_i, b_{z-i}) go to such pairs in A_2.

gap> # a canonical isomorphism
gap> data1:= LoewyStructureInfo( 3, 7 );;
gap> data2:= LoewyStructureInfo( 6, 7 );;
gap> SingerAlg.ProposedPermutationIsomorphism( data1, data2 );
()
gap> # a proper permutation isomorphism
gap> data1:= LoewyStructureInfo(  41, 275 );;
gap> data2:= LoewyStructureInfo( 116, 275 );;
gap> pi:= SingerAlg.ProposedPermutationIsomorphism( data1, data2 );;
gap> t1:= SingerAlg.MultTable( data1 );;
gap> t2:= SingerAlg.MultTable( data2 );;
gap> SingerAlg.IsInducedAlgebraIsomorphism( t1, t2, pi );
true
gap> # the reduced variant
gap> pi:= SingerAlg.ProposedPermutationIsomorphism( data1, data2,
>                                                   "reduced" );;
gap> pi.iso;  # achieved by a suitable sorting of the bases
()
gap> # no permutation isomorphism
gap> data1:= LoewyStructureInfo(  11, 171 );;
gap> data2:= LoewyStructureInfo(  68, 171 );;
gap> SingerAlg.ProposedPermutationIsomorphism( data1, data2 );
"different distributions of products"

3.5 Invariants of Singer Algebras

The following functions can be used to prove the nonisomorphism of given Singer algebras via invariants.

3.5-1 ConsiderInvariantsByParameters

Returns: a record.

Let z ∈ { 1, 2, ..., 10000 }, and qs be a list of prime residues modulo z. ConsiderInvariantsByParameters tries to find an invariant (under algebra isomorphisms) that is not equal for all Singer algebras A[q,z], for q ∈qs. The invariants used here are the dimensions of suitable subspaces or the numbers of solutions of suitable equations.

The function returns a record with at least the components success (with value true if an invariant was found that distinguishes at least two algebras corresponding to qs, and false otherwise) and comment (a string). If the search was successful then the result contains also the components label (a string that decribes the distinguishing invariant) and lists (a partition of qs according to the values of this invariant).

If a record bounds is given then it controls how many checks are performed, as follows.

• If the component maxnumber is bound then the function returns a record with success value false as soon as at least maxnumber invariants have been checked without success; the default value of maxnumber is 100.

• If the components RCdim and RCnum are bound then the function SingerAlg.NumberOfProductsInSubspace (3.5-3) gets called after the combinatorial invariants have been computed, with the first two arguments taken from the first RCnum of these invariants and with third argument equal to the value of RCdim; by default, SingerAlg.NumberOfProductsInSubspace (3.5-3) is not called at all.

  If such a call is successful for two subspaces U and V then the label component of the result has the form "RC(U,V)".

• If the component LL4QuoDerMax is bound then its value is taken as the maxdim argument of SingerAlg.LL4QuoDerDim (3.5-4), the default is 50.

• If the component SubquoDerMax is bound then its value is taken as the maxdim argument of SingerAlg.SubquoDerDim (3.5-5), the default is 50.

The following invariant subspaces of a Singer algebra A or its reduction A_p modulo some prime p, respectively, are considered.

• The members J(A)^i of the radical series of A (denoted by "J^1", "J^2", ... in the label component; see SingerAlg.BasesOfRadicalSeries (3.3-7)),

• the members S(A)_i of the socle series of A (denoted by "S_1", "S_2", ...; see SingerAlg.BasesOfSocleSeries (3.3-8)),

• the space of elements in A_p whose p^m-th powers are zero, for primes p and positive integers m (denoted by "Roots(0,p,m)"; see SingerAlg.BasisOfPMRoots (3.3-10)),

• the ideal in A or A_p that is spanned by an invariant subspace U described in this list (denoted by "Ideal(U)"; see SingerAlg.BasisOfIdeal (3.3-5)),

• the annihilator in A or A_p of an invariant subspace U described in this list (denoted by "Annihilator(U)"; see SingerAlg.BasisOfAnnihilator (3.3-6)),

• the space of p^m-th powers of elements in U, for primes p and positive integers m, where U is an invariant subspace of A or A_p described in this list (denoted by "Power(U,p,m)"; see SingerAlg.BasisOfPowers (3.3-9)),

• the space of elements in A_p whose p^m-th powers are in U, for primes p and positive integers m, where U is an invariant subspace of A or A_p described in this list (denoted by "Roots(U,p,m)"; see SingerAlg.BasisOfPMRoots (3.3-10)),

• the product space of two subspaces U, V in the same characteristic (denoted by "Prod(U,V)"; see SingerAlg.BasisOfProductSpace (3.3-4)),

• the sum of two subspaces U, V in the same characteristic (denoted by "Sum(U,V)"; see SingerAlg.BasisOfSum (3.3-3)),

• the intersection of two subspaces U, V in the same characteristic (denoted by "Intersection(U,V)"; see SingerAlg.BasisOfIntersection (3.3-3)),

• the space of elements { x ∈ J(A); x ⋅ U ⊆ V }, for two subspaces U, V in the same characteristic (denoted by "PC(U,V)"; see SingerAlg.BasisOfPC (3.3-11)),

A basis for the invariant subspace can be recovered from the label string of the result, using the function SingerAlg.InfoFromInvariantString (3.5-2).

A different kind of invariant is given by the number of solutions of some equation, as computed with SingerAlg.NumberOfProductsInSubspace (3.5-3), the corresponding label has the form "RC(U,V)", and the function SingerAlg.InfoFromInvariantString (3.5-2) can be used to compute the number of solutions.

gap> inv:= ConsiderInvariantsByParameters( 117, [ 29, 35 ] );
rec( comment := "total 12 invariants checked", 
  label := "Prod(Annihilator(Power(J^1,2,1)),Roots(0,2,1))", 
  lists := [ [ 29 ], [ 35 ] ], success := true )
gap> ConsiderInvariantsByParameters( 247, [ 37, 46 ] );
rec( comment := "total 4 invariants plus LL4QuoDerDim checked", 
  label := "LL4QuoDerDim", lists := [ [ 46 ], [ 37 ] ], 
  success := true )
gap> ConsiderInvariantsByParameters( 171, [ 11, 68 ] );
rec( comment := "no decision, checked 11 invariants", 
  labels := [ "J^3", "Power(J^1,2,1)", "Annihilator(Roots(0,2,1))", 
      "Sum(Power(J^1,2,1),J^3)", 
      "Sum(Power(J^1,2,1),Annihilator(Roots(0,2,1)))", "J^2", "S_2", 
      "Annihilator(Sum(Power(J^1,2,1),Annihilator(Roots(0,2,1))))", 
      "Roots(0,2,1)", "Annihilator(Power(J^1,2,1))", "J^1" ], 
  success := false )
gap> res:= ConsiderInvariantsByParameters( 171, [ 11, 68 ],
>              rec( SubquoDerMax:= 158 ) );;
gap> res.success;
true

3.5-2 SingerAlg.InfoFromInvariantString

Returns: a record.

Let data be a GAP record as returned by LoewyStructureInfoGAP (3.1-11) or a Julia dictionary as returned by LoewyStructureInfoJulia (3.1-11), which describes a Singer algebra A, say, and let str be a string as in the label component of a record returned by ConsiderInvariantsByParameters (3.5-1).

SingerAlg.InfoFromInvariantString returns a record with one of the following components.

basisIndices:

the list I of indices such that { B(A)_i; i ∈ I } is a basis of the subspace defined by str,

derivationsDim:

the dimension of the algebra of derivations (see Derivations (Reference: Derivations)) of the algebra,

LL4QuoDerDim:

the dimension of the algebra of derivations of the algebra considered by the function SingerAlg.LL4QuoDerDim (3.5-4) or its Julia variant,

SubquoDerDim:

the dimension of the algebra of derivations of the subquotient described by str that is considered by the function SingerAlg.SubquoDerDim (3.5-5) or its Julia variant,

solutionCount:

the pair [ e, o ] such that the number of solutions is 2^e ⋅ o, where o is an odd number.

If data is a GAP record then the invariants in question are computed with GAP functions, otherwise the Julia implementations are used.

gap> SingerAlg.InfoFromInvariantString(
>        LoewyStructureInfoGAP( 29, 6, 117 ),
>        "Prod(Annihilator(Power(J^1,2,1)),Roots(0,2,1))" );
rec( basisIndices := [ 36, 64, 69, 73, 80, 93, 95, 100, 101, 118 ] )
gap> SingerAlg.InfoFromInvariantString(
>        LoewyStructureInfoGAP( 35, 6, 117 ),
>        "Prod(Annihilator(Power(J^1,2,1)),Roots(0,2,1))" );
rec( basisIndices := [ 37, 51, 60, 64, 73, 77, 86, 87, 91, 100, 109, 
      113, 118 ] )
gap> SingerAlg.InfoFromInvariantString(
>        LoewyStructureInfoGAP( 2, 3, 7 ),
>        "Derivations" );
rec( derivationsDim := 24 )
gap> SingerAlg.InfoFromInvariantString(
>        LoewyStructureInfoGAP( 37, 12, 247 ),
>        "LL4QuoDerDim" );
rec( LL4QuoDerDim := 656 )
gap> SingerAlg.InfoFromInvariantString(
>        LoewyStructureInfoGAP( 68, 6, 171 ),
>        "SubquoDerDim(J^2,J^3)" );
rec( SubquoDerDim := 2025 )
gap> SingerAlg.InfoFromInvariantString(
>        LoewyStructureInfoGAP( 23, 12, 259 ),
>        "RC(J^3,J^1)" );
rec( solutionCount := [ 492, 51055 ] )

3.5-3 SingerAlg.NumberOfProductsInSubspace

Returns: a pair of nonnegative integers, or fail.

Let data be a record as returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z], let B = B(A), and let J, I be subsets of { 1, 2, ..., z+1 }, describing subspaces V and U of A with bases ( B_i; i ∈ J ) and ( B_i; i ∈ I ), respectively.

SingerAlg.NumberOfProductsInSubspace tries to compute the cardinality of the set

X = { (x,y) ∈ U × U; x ⋅ y ∈ V }.

For that, we set

If |K| is larger than bound then fail is returned, otherwise the list [ e, o ] such that |X| = 2^e ⋅ o holds. The default value for bound is 15, the maximal possible value for bound is 59 (which is much too large for practical purposes).

gap> data:= LoewyStructureInfoGAP( 23, 12, 259 );;
gap> radser:= SingerAlg.BasesOfRadicalSeries( data );;
gap> SingerAlg.NumberOfProductsInSubspace( data, radser[3], radser[1] );
[ 492, 51055 ]
gap> data:= LoewyStructureInfoGAP( 60, 12, 259 );;
gap> radser:= SingerAlg.BasesOfRadicalSeries( data );;
gap> SingerAlg.NumberOfProductsInSubspace( data, radser[3], radser[1] );
[ 493, 161051 ]

Note that for x = ∑_{i ∈ I} x_i B_i and y = ∑_{j ∈ I} y_j B_j, we have

x ⋅ y = ∑_{i, j ∈ I} x_i y_j (B_i ⋅ B_j) = v + ∑_{i, j ∈ K} x_i y_j (B_i ⋅ B_j) = v' + ∑_{k ∈ D} ( ∑_{i, j ∈ K, B_i ⋅ B_j = B_k} x_i y_j ) B_k,

for some v, v' ∈ V, thus x ⋅ y ∈ V if and only if x' M_k y' = 0 holds for all k ∈ D, where [M_k]_{i,j} is 1 if B_i ⋅ B_j = B_k holds, and 0 otherwise, for i, j ∈ K, and where x', y' are the restrictions of x, y to K. Let M(x') be the matrix with rows x' M_k, k ∈ D. Then

|X| = 4^{|I|-|K|} ⋅ ∑_{x' ∈ F_2^{|K|}} 2^{|K|-rank( M(x') )}.

3.5-4 SingerAlg.LL4QuoDerDim

Returns: a positive integer, or fail.

Let data be a record as returned by LoewyStructureInfoGAP (3.1-11) that describes a Singer algebra A = A[q,z] of Loewy length 4. We consider A as an algebra over the field F with two elements. Let J denote the Jacobson radical of A, S_2(A) denote the annihilator of J^2, and let V(A) be the F-vector space generated by those elements of the canonical basis of A that lie in J(A) ∖ S_2(A).

SingerAlg.LL4QuoDerDim tries to compute the dimension of the algebra of derivations of the algebra (J(A)^2 ⊕ V(A)) / S_1(A), using SingerAlg.RightDerivationsDimension (3.6-5). If the return value is a positive integer then it is this dimension. The return value fail means that either A has Loewy length different from 4 or that the dimension of V(A) is larger than the optional argument maxdim (the default is 50).

(Note that we have dim(J(A)^2 ⊕ V(A)) = 2 dim(J(A)^2) - 1.)

gap> data:= LoewyStructureInfoGAP( 37, 247 );;
gap> SingerAlg.LL4QuoDerDim( data );
656
gap> data:= LoewyStructureInfoGAP( 46, 247 );;
gap> SingerAlg.LL4QuoDerDim( data );
585

3.5-5 SingerAlg.SubquoDerDim

Returns: a record or fail.

Let datalist be a list of length n, say, of records as returned by LoewyStructureInfoGAP (3.1-11), which belong to Singer algebras A_1, A_2, ..., A_n of the same dimension. We consider the A_i as algebras over the field F with two elements.

Let labels be a list of length m, say, that consists of strings.

Let subspaces be a list of length m, where each entry is a list of length n such that subspaces[i][j] is a list of positive integers that describes the basis of the subspace of A_j that corresponds to the label labels[i].

Let maxdim be a positive integer; the default is 50.

SingerAlg.SubquoDerDim runs over the pairs (i, j) such that, for 1 ≤ k ≤ n, both subspaces[i][k] and subspaces[j][k] describe bases of ideals I_{i,k} and I_{j,k}, respectively, in A_k, such that I_{j,k} ⊂ I_{i,k} holds and I_{i,k} / I_{j,k} has dimension at most maxdim. Then it computes the dimensions of the algebras of derivations of the quotients I_{i,k} / I_{j,k}.

If not all of these dimensions are equal for some pair (i, j) then a record with the components labels (the list [ i, j ]) and derdim (the list of computed dimensions) is returned. Otherwise fail is returned.

gap> z:= 171;;  qs:= [ 11, 68 ];;
gap> datalist:= List( qs, q -> LoewyStructureInfoGAP( q, z ) );;
gap> ids:= [ Difference( [ 2 .. z+1 ], [ 10, 37, 55, 64, 82, 100 ] ),
>            [ 73, 91, 109, 118, 136, 163, 172 ] ];;
gap> ideals:= [ [ ids[1], ids[1] ], [ ids[2], ids[2] ] ];;
gap> labels:= [ "I", "J" ];;
gap> SingerAlg.SubquoDerDim( datalist, labels, ideals, 150 );
fail
gap> SingerAlg.SubquoDerDim( datalist, labels, ideals, 158 );
rec( derdim := [ 14179, 14201 ], labels := [ "I", "J" ] )

3.6 Miscellaneous variables related to Singer Algebras

3.6-1 SingerAlg

This global record is used to store information about the SingerAlg package. Some of its components are documented individually, see the manual index.

3.6-2 OrderModExt

Returns: a nonnegative integer.

When called with two arguments n and m, OrderModExt returns the same as the GAP library function OrderMod (Reference: OrderMod), that is, the multiplicative order of the integer n modulo the positive integer m. If n and m are not coprime the order of n is not defined and OrderModExt will return 0.

If n and m are relatively prime the multiplicative order of n modulo m is the smallest positive integer i such that n^i ≡ 1 mod m.

If no a priori known multiple bound of the desired order is given, OrderModExt usually spends most of its time factoring m for computing a default for bound, and then factoring bound. Thus it is advisable to enter bound whenever one knows a reasonable bound.

If an incorrect bound is given then the result will be wrong.

gap> OrderModExt( 2, 7 );
3
gap> OrderModExt( 3, 7 );  # 3 is a primitive root modulo 7
6
gap> m:= (5^166-1) / 167;;      # about 10^113
gap> OrderModExt( 5, m, 166 );  # needs minutes without third argument
166

3.6-3 SingerAlg.ContentsOfDataFile

Returns: the GAP object stored in the given file.

Let filename be a string that denotes the name of a file in the data subdirectory of the SingerAlg package directory. SingerAlg.ContentsOfDataFile evaluates the contents of this file (assuming that it is GAP readable) and returns the result.

gap> val:= SingerAlg.ContentsOfDataFile( "mqe.json" );;
gap> val[1][2];
"This file contains the sorted list of values '[ e, q, m(q,e) ]', "

3.6-4 GrayCodeSwitchIndexIterator

Returns: an iterator (see Reference: Iterators).

For a nonnegative integer n, this function returns an iterator for the sequence of the positions of those bits in an n-bit Gray code where the next flip takes place.

For n tending to infinity, this is series A001511 of the OEIS [Slo].

gap> l:= [];;
gap> for i in GrayCodeSwitchIndexIterator( 4 ) do
>      Add( l, i );
>    od;
gap> l;
[ 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 ]

The idea of a Gray code is to run over the vectors of a GF(2)-vector space in such a way that subsequent vectors differ in exactly one position.

gap> F:= GF(2);;  one:= One( F );;  V:= F^4;;
gap> v:= ShallowCopy( Zero( V ) );;  l:= [ ShallowCopy( v ) ];;
gap> for i in GrayCodeSwitchIndexIterator( 4 ) do
>      v[i]:= v[i] + one;
>      Add( l, ShallowCopy( v ) );
>    od;
gap> Set( l ) = Elements( V );
true

3.6-5 SingerAlg.RightDerivationsDimension

Returns: a positive integer.

Let T be a symmetric square matrix with n rows and columns, whose entries are integers in [ 0 .. n ]. We interpret T as the multiplication table of a commutative algebra A over the field with two elements, as follows. Let B = [ b_1, b_2, ..., b_n ] be a basis of A. If T[i,j] = k holds then the product b_i b_j is zero if k = 0, and b_i b_j = b_k otherwise.

SingerAlg.RightDerivationsDimension returns the dimension of (right) derivations of A.

Let the structure constants of A w.r.t. the basis B be c_{i,j,k}, that is, we have b_i b_j = ∑_{k=1}^n c_{i,j,k} b_k. For each pair (i, j), we have thus c_{i,j,k} = 1 if T[i,j] = k (not= 0) holds, and c_{i,j,k} = 0 otherwise. A linear map D: b_i ↦ ∑_{j=1}^n d_{i,j} b_j is a right derivation if and only if the equation ∑_{k=1}^n ( c_{i,j,k} d_{k,m} - c_{k,j,m} d_{i,k} - c_{i,k,m} d_{j,k} ) = 0 is satisfied for all 1 ≤ i, j, m ≤ n. Thus the right derivations of A are given by the solution space of this linear equation system, in terms of the n^2 indeterminates d_{i,j}, 1 ≤ i, j ≤ n, and we can compute the dimension of this space by computing the rank of the matrix of the equation system.

Since the algebra A is commutative, we have c_{i,j,k} = c_{j,i,k}, thus we need only the equations with i ≤ j.

gap> q:= 3;;  z:= 40;;  a:= SingerAlgebra( q, z, GF(2) );;
gap> T:= SingerAlg.MultTable( LoewyStructureInfo( 3, 40 ) );;
gap> SingerAlg.RightDerivationsDimension( T );
118
gap> Dimension( Derivations( CanonicalBasis( a ) ) );
118

generated by GAPDoc2HTML