Construction of a Generic Abelian Group#

The term generic abelian group refers to the situation in which a group \(A\) is described by giving a set \(X\) together with functions acting on \(X\) that perform the fundamental group operations for \(A\). Specifically, the user must provide functions which compute the product, the inverse and the identity. For efficiency, the user may also optionally specify the order and a generating set for the group. This is made explicit below.

Going from such a definition of an abelian group \(A\) to a presentation for \(A\) will often be extremely expensive and so a small number of operations are implemented so as to not require this information. The two key operations are computing the order of an element and computing the discrete logarithm of an element to a given base. For many abelian group operations, knowledge of a presentation is required and if such an operation is invoked, the structure of \(A\) (and hence a presentation) will be automatically constructed.

There are two possible ways of computing the structure of the group. If the order of the group is known (or can be computed) then it is relatively easy to construct each of the \(p\)-Sylow subgroups. If the order is not available, the structure is computed from a set of generators supplied by the user.

Specification of a Generic Abelian Group#

GenericAbelianGroup(U: parameters): . -> GrpAbGen#

IdIntrinsic      : MonStg                       Default: 
AddIntrinsic     : MonStg                       Default: 
InverseIntrinsic : MonStg                       Default: 
UseRepresentation: Bool                         Default: false
Order            : RngIntElt                    Default: 
UserGenerators   : SetEnum                      Default: 
ProperSubset     : Bool                         Default: false
RandomIntrinsic  : MonStg                       Default: 
ComputeStructure : Bool                         Default: false
UseUserGenerators: Bool                         Default: false
PollardRhoRParam : RngInt                       Default: 20
PollardRhoTParam : RngInt                       Default: 8
PollardRhoVParam : RngInt                       Default: 3

Construct the generic abelian group \(A\) over the domain \(U\). The domain \(U\) can be an aggregate (set, indexed set or sequence) of elements or it can be any structure, for example, an elliptic curve, a jacobian, a magma of quadratic forms.

If the parameters IdIntrinsic, AddIntrinsic and InverseIntrinsic are not set, then the identity, the composition and the inverse function of \(A\) are taken to be the identity, the composition and the inverse function of \(U\) or of Universe(U) if \(U\) is an aggregate. If the parameters IdIntrinsic, AddIntrinsic and InverseIntrinsic are set, they define the identity, the composition and the inverse function of \(A\).

The parameter IdIntrinsic must be a function name whose sole argument is \(U\) or Universe(U) if \(U\) is an aggregate. AddIntrinsic must be a function name whose only two arguments are elements of \(U\) or of Universe(U) if \(U\) is an aggregate. InverseIntrinsic must be a function name whose only two arguments are elements of \(U\) or of Universe(U) if \(U\) is an aggregate. That is, it is required that InverseIntrinsic be a binary operation (see the example below where InverseIntrinsic := "/" is indeed binary). Defining any of the three above parameters implies that the other two must be defined as well.

Setting the parameter UseRepresentation to true implies that all elements of \(A\) will be internally represented as linear combinations of the generators of \(A\) obtained while computing the structure of \(A\). This can be a costly procedure, since such a representation is akin to solving the discrete logarithm problem. The advantage of such a representation is that arithmetic for elements of \(A\) as well as computing the order of elements of \(A\) are then essentially trivial operations.

The parameter Order can be set to the order of the group, if known. Knowledge of the order may save a considerable amount of time for operations such as computing a Sylow subgroup, determining the group structure or solve a discrete logarithm problem. More importantly, if \(A\) is a proper subset of \(U\), or of Universe(U) if \(U\) is an aggregate, then one of Order or UserGenerators must be set.

One can set UserGenerators to some set of elements of \(U\), or of Universe(U) if \(U\) is an aggregate, which generate the group \(A\). This can be useful when \(A\) is a subset of \(U\) (Universe(U)), or more generally when the computation of the group structure of \(A\) is made from a set of generators. Finally, setting UserGenerators may be an alternative to setting RandomIntrinsic.

The parameter ProperSubset must be set when \(A\) is a proper subset of \(U\) (Universe(U)).

The parameter RandomIntrinsic indicates the random function to use. If it is not set, the random function (if it is required) is taken to be the random function applying to \(U\) (Universe(U)).

The parameter RandomIntrinsic must be the name of a function taking as its sole argument \(U\) (Universe(U)) and returning an element of \(U\) (Universe(U)) which is also an element of the group \(A\), which is important when \(A\) is a proper subset of \(U\) (Universe(U). Therefore, if \(A\) is a proper subset of \(U\) (Universe(U)), then RandomIntrinsic must be set, unless the parameter UserGenerators is set.

The parameter Structure indicates that the group structure should be determined at the time of creation. If this parameter is set then the user may also want to set the following parameters:

Their meaning is detailed in Section Computing Abelian Group Structure.

Example: Creation (ex-5df08f)#

In our first example we create the subset \(U\) of \({\mathbb{Z}}/34384{\mathbb{Z}}\) corresponding to its unit group as a generic abelian group \(G\). Note that \(U\) is an indexed set.

> m :=  34384;
> Zm := Integers(m);
> U := {@ x : x in Zm | GCD(x, m) eq 1 @};
> G := GenericAbelianGroup(U :
>        IdIntrinsic := "Id",
>        AddIntrinsic := "*",
>        InverseIntrinsic := "/");
> G;
Generic Abelian Group over
Residue class ring of integers modulo 34384

Run in calculator

In our next example we construct unique representatives for the classes of binary quadratic forms corresponding to elements of a subgroup of the class group of the imaginary quadratic field of discriminant \(-4000004\).

> n := 6;
> Dk := -4*(10^n + 1);
> Q := QuadraticForms(Dk);
>
> p := 2;
> S := { };
> while #S lt 10 do
>    if KroneckerSymbol(Dk,p) eq 1 then
>       I := Reduction(PrimeForm(Q,p));
>       Include(~S, I);
>    end if;
>    p := NextPrime(p);
> end while;
>
> QF := GenericAbelianGroup(Q : UserGenerators := S,
>                               ComputeStructure := true,
>                               UseUserGenerators := true);
> QF;
Generic Abelian Group over
Binary quadratic forms of discriminant -4000004
Abelian Group isomorphic to Z/2 + Z/516
Defined on 2 generators
Relations:
  2*$.1 = 0
  516*$.2 = 0

Run in calculator

So the structure of the subgroup is \(Z_2 \times Z_{516}\)

Accessing Generators#

These functions give access to generating sets for a generic group \(A\). If a generating set is requested and none has been supplied by the user then this will require the determination of the group structure which could be very expensive. Note the distinction between Generators and UserGenerators. From now on, unless otherwise specified, whenever mention is made of the generators of \(A\), we refer to the generators as given by the Generators function.

Universe(A): GrpAbGen#: The universe over which the generic abelian group \(A\) is defined.

A . i: GrpAbGen, RngIntElt -> GrpAbGenElt#: The \(i\)-th generator for the generic abelian group \(A\).

Generators(A): GrpAbGen -> [ GrpAbGenElt ]#: A sequence containing a generating set for the generic abelian group \(A\) as elements of \(A\). The set of generators returned for \(A\) is a reduced set of generators as constructed during the structure computation. Therefore, if the group structure of \(A\) has been computed from a user-supplied set of generators, it is unlikely that Generators(A) and UserGenerators(A) will be the same.

UserGenerators(A): GrpAbGen -> [ GrpAbGenElt ]#: A sequence containing the user-supplied generators for the generic abelian group \(A\) as elements of \(A\).

NumberOfGenerators(A): GrpAbGen -> RngIntElt#
Ngens(A): GrpAbGen -> RngIntElt#: The number of generators for the generic abelian group \(A\).

Computing Abelian Group Structure#

If the order of a generic abelian group \(A\) can be obtained then the structure of \(A\) is found by constructing each \(p\)-Sylow subgroup of \(A\). The \(p\)-Sylow subgroups are built from random elements of the underlying set \(X\) of \(A\). Recall that \(U\) (Universe(U)) is the domain of \(A\). Random elements are obtained using either a random function attached to \(X\) or using a user-supplied function (the RandomIntrinsic parameter), or using user-supplied generators (the UserGenerators parameter). It is therefore vital that user-supplied generators truly generate the group one wishes to construct. A drawback of this method of obtaining the structure of \(A\) is the memory needed to store all the elements of a specific \(p\)-Sylow subgroup while under construction. This algorithm is mostly based on work by Michael Stoll.

The second approach computes the group structure from a set of generators as supplied by the user, removing the need to compute the order of \(A\). This can be particularly useful when computing this order is expensive. Note that computing the structure of a group from a set of generators is akin to solving a number of the discrete logarithm problems. This second algorithm uses a variant of the Pollard–Rho algorithm and is due to Edlyn Teske [Teske, 1998].

If \(A\) is a subgroup of a generic abelian group, \(G\) say, then the structure of \(G\) is computed first. The rationale is that once the structure of \(G\) is known, computing the structure of \(A\) is almost always cheap.

AbelianGroup(A: parameters): GrpAbGen -> GrpAb, Map#

UseUserGenerators: Bool                      Default: false
PollardRhoRParam : RngInt                    Default: 20
PollardRhoTParam : RngInt                    Default: 8
PollardRhoVParam : RngInt                    Default: 3

Compute the group structure of the generic abelian group \(A\), which may be a subgroup as created by the subgroup constructor or the Sylow function. The two values returned are the abstract abelian group and the invertible map from the latter into \(A\).

If UseUserGenerators is false, then the group structure computation is made via the construction of each \(p\)-Sylow subgroup, using the factorization of the order of \(A\).

If UseUserGenerators is set to true, the group structure computation uses the user-supplied set of generators for \(A\). In this case, the additional parameters PollardRhoRParam, PollardRhoTParam, and PollardRhoVParam can be supplied. Their values will be passed to the Pollard–Rho algorithm used in the group structure computation: PollardRhoRParam sets the size of the \(r\)-adding walks, PollardRhoTParam sets the size of the internal storage of elements, and PollardRhoVParam is used for an efficient finding of the periodic segment. It is conjectured that the default values as given above are ‘best’ (see [Teske, 1998]), therefore there should be no need to set these parameters in general.

Example: Group Computation (ex-0d76ee)#

The following statement computes the structure of the unit group of \({\mathbb{Z}}_{34384}\).

> G := AbelianGroup(G); G;
Generic Abelian Group over
Residue class ring of integers modulo 34384
Abelian Group isomorphic to Z/2 + Z/2 + Z/6 + Z/612
Defined on 4 generators
Relations:
  2*G.1 = 0
  2*G.2 = 0
  6*G.3 = 0
  612*G.4 = 0

Run in calculator