|
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.
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
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:
UseUserGenerators: Bool Default: false
PollardRhoRParam: RngInt Default: 20
PollardRhoTParam: RngInt Default: 8
PollardRhoVParam: RngInt Default: 3
Their meaning is detailed in Section Computing Abelian Group Structure.
In our first example we create the subset U of Z/34384Z 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
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
So the structure of the subgroup is Z 2 x Z 516
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.
The universe over which the generic abelian group A is defined.
The i-th generator for the generic abelian group A.
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.
A sequence containing the user-supplied generators for the generic abelian
group A as elements of A.
Ngens(A) : GrpAbGen -> RngIntElt
The number of generators for the generic abelian group A.
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 [Tes98a].
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.
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 [Tes98b]), therefore there
should be no need to set these
parameters in general.
The following statement computes the structure of the unit group of
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|