|
Simplification may be achieved by setting some parameters and trusting that
the built-in strategy will produce the result desired. Alternatively the
user may create a Tietze process allowing the user to interactively
perform the simplification.
Subgroups of finitely presented groups constructed in certain ways may be
have a generating set containing redundant generators. The most
important case in which this situation may occur is a subgroup of the domain
of a homomorphism f of groups, defined as the preimage under f of some
given subgroup of the codomain of f. In this case, the
generating set of the preimage will contain generators of the kernel of f
and is likely to be not minimal.
Since reducing the generating set may be expensive and is not necessary in all
situations, a reduction is not done automatically. Instead, Magma provides
a function for reducing generating sets of finitely presented groups.
Given a finitely presented group G, attempt to construct a presentation H
on fewer generators. H is returned as a subgroup of G (which of course is
equal to G), so that element coerce is possible. The isomorphism from G
to H is returned as second return value.
If a presentation for G is known, this function attempts to simplify this
presentation (cf. section Interactive Simplification). Otherwise, it
tries to rewrite G with respect to a suitable supergroup to obtain a
presentation on fewer generators.
For a sample application of this function, see Example
H80E89.
Given a finitely presented group G, the user can attempt to simplify
its presentation using Tietze transformations and substring searching. The
choice of simplification strategy can either be left to Magma or selected
by the user.
Simplify(G: parameters) : GrpFP -> GrpFP, Map
Given a finitely presented group G, attempt to simplify the presentation
of G by
repeatedly eliminating generators and subsequently shortening relators by
substitution of substrings that correspond to the left or right hand side
of a relation. The order in which transformations are applied is determined
by a set of heuristics. The transformation process terminates when no more
eliminations of generators and no more length reducing substring replacements
are possible. A new group K isomorphic to G is returned as a subgroup
of G which is (hopefully) defined by a simpler presentation than G. The
isomorphism f:G -> K is returned as second return value.
The simplification process can be controlled by a set of parameters described
below.
The strategy employed by the function Simplify can be
controlled using the following set of parameters.
Preserve: [RngIntElt] Default: []
This parameter can be used to indicate that certain generators of G should
not be eliminated (default: no restrictions). Preserve is assigned
a sequence of integers in the range [1, ..., n], where n is the number of
generators of G, containing the numbers of those generators of G which
should be preserved. See Example H80E11 for
a sample application.
Iterations: RngIntElt Default: 10000
This parameter sets the maximal number of iterations of the main elimination /
simplification cycle which will be performed.
EliminationLimit: RngIntElt Default: 100
This parameter sets the maximal number of generators which may be eliminated
in each elimination phase.
LengthLimit: RngIntElt Default: ∞
If LengthLimit is set to n, any eliminations which would make the
total length of the relators grow beyond n will not be performed
(default: no limit).
ExpandLimit: RngIntElt Default: 150
If ExpandLimit is set to n, the total length of the relators is not
permitted to grow by more than a factor of n% in any elimination phase
(default: 150%). If this limit is reached, the elimination phase is
aborted.
GeneratorsLimit: RngIntElt Default: 0
Any eliminations which would reduce the number of generators below the value
of GeneratorsLimit will not be performed (default: 0).
SaveLimit: RngIntElt Default: 10
If SaveLimit is set to n, any simplification phase is repeated, if
the reduction in the total length of the relators achieved during this phase
exceeds n% (default: 10%).
SearchSimultaneous: RngIntElt Default: 20
This parameter sets the number of relators processed simultaneously in a
simplification phase.
Print: RngIntElt Default: 0
This parameter controls the volume of printing. By default its value
is that returned by GetVerbose("Tietze"), which is
0 unless it has been changed through use of SetVerbose.
Consider the Fibonacci group F(8).
> F<x1, x2, x3, x4, x5, x6, x7, x8> := FreeGroup(8);
> F8<x1, x2, x3, x4, x5, x6, x7, x8> :=
> quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
> x5*x6=x7, x6*x7=x8, x7*x8=x1, x8*x1=x2>;
We use the function Simplify in order to obtain a presentation
of F(8) on two generators.
> H<[y]>, f := Simplify(F8);
> H;
Finitely presented group H on 2 generators
Generators as words in group F8
y[1] = x3
y[2] = x4
Relations
y[2] * y[1]^-2 * y[2] * y[1]^-1 * y[2]^2 * y[1] * y[2]^2 *
y[1]^-1 = Id(H)
y[1] * y[2] * y[1] * y[2]^2 * y[1] * y[2] * y[1]^2 * y[2]^-1
* y[1] = Id(H)
The isomorphism f can be used to express the old generators in terms of
the new ones.
> f;
Mapping from: GrpFP: F8 to GrpFP: H
> f(x1);
y[1]^2 * y[2]^-1
SimplifyLength(G: parameters) : GrpFP -> GrpFP, Map
Given a finitely presented group G, attempt to eliminate generators and
shorten relators by locating substrings that correspond to the left or
right hand side of a relation. The order in which transformations are applied
is determined by a set of heuristics. As opposed to the function
Simplify, this function terminates the transformation
process when the total length of the presentation starts to increase with
the elimination of further generators.
A new group K isomorphic to G is
returned which is (hopefully) defined by a simpler presentation than
G. K is returned as a subgroup of G. The isomorphism f:G -> K
is returned as second return value. This function accepts the same set of
parameters as the function Simplify.
The user may exercise fine control over the simplification of a
presentation by creating a Tietze process which allows the user to
look at the result of a simplification operation before specifying
the next step.
Create a Tietze process that takes the presentation for the fp-group G
as its starting point. This process may now be manipulated by various
procedures that will be described below.
Preserve: [RngIntElt] Default: []
Iterations: RngIntElt Default: 10000
EliminationLimit: RngIntElt Default: 100
LengthLimit: RngIntElt Default: ∞
ExpandLimit: RngIntElt Default: 150
GeneratorsLimit: RngIntElt Default: 0
SaveLimit: RngIntElt Default: 10
SearchSimultaneous: RngIntElt Default: 20
Print: RngIntElt Default: 0
These parameters define the defaults used for the Tietze operations.
Each of the various procedures described below allows some or all of
these control parameters to be overridden.
For the meanings of the parameters, see the description
under Simplify above.
Display the defaults associated with the Tietze process P.
The current status of all the control parameters may be viewed by using
this function.
Change the defaults associated with the Tietze process P. All of
the control parameters may be overridden permanently by using this
function.
SimplifyPresentation(~P : parameters) : GrpFPTietzeProc ->
Use the default strategy to simplify the presentation as much as possible. The
transformation process is terminated when no more eliminations of generators
and no more length reducing substring replacements are possible.
All the control parameters may be overridden for this function.
Use the default strategy to simplify the presentation as much as possible. The
transformation process is terminated when the total length of the presentation
starts to increase with the elimination of further generators.
All the control parameters may be overridden for this function.
EliminateGenerators(~P: parameters) : GrpFPTietzeProc ->
Eliminate generators in the presentation defined by the Tietze process P
under the control of the parameters. First any relators of length one are
used to eliminate trivial generators. Then, if there are any non-involutory
relators of length two, the generator with the higher number is eliminated.
Of the control parameters, only EliminationLimit, ExpandLimit,
GeneratorsLimit and LengthLimit may be overridden by this function.
Relator: RngIntElt Default: 0
If n > 0, try to eliminate a generator using the n-th relator.
If no generator is
specified by the parameter Generator below, then the generator which
is eliminated will be the one occurring once in the relator that
produced the smallest total relator length.
Generator: RngIntElt Default: 0
If n > 0, try to eliminate the n-th generator.
If no relation is specified by the parameter Relator above, then
the shortest relator in which the n-th generator occurs exactly
once (if any) is used.
Simplifies the presentation by repeatedly searching for common
substrings in pairs of relators where the length of the substring
is greater than half the length of the shorter relator and making
the corresponding transformations. Relators of length 1 or 2 are
also used to generate simplifications. The control parameters
SaveLimit and SearchSimultaneous can be overridden.
Modifies the presentation by repeatedly searching for common
substrings in pairs of relators where the length of the substring
is exactly half the length of the shorter relator and making
the corresponding transformations.
The control parameter SearchSimultaneous can be overridden.
Group(P) : GrpFPTietzeProc -> GrpFP, Map
Extract the group G defined by the current presentation
associated with the Tietze process P, together with the
isomorphism between the original group and G. G is returned as a
subgroup of the original group underlying P.
Ngens(P) : GrpFPTietzeProc -> RngIntElt
The number of generators for the presentation currently stored by
the Tietze process P.
Nrels(P) : GrpFPTietzeProc -> RngIntElt
The number of relations in the presentation currently stored by
the Tietze process P.
The sum of the lengths of the relators in the presentation
currently stored by the Tietze process P.
The Fibonacci group F(n) is generated by { x 1, ..., x n }
with defining relations
x ix i + 1 = x i + 2, i ∈{ 1, ..., n },
where the subscripts are taken modulo n.
Consider the Fibonacci group F(7), which is defined in terms of
the presentation
<x_1,x_2,x_3,x_4,x_5,x_6,x_7 | x_1x_2=x_3, x_2x_3=x_4, x_3x_4=x_5,
x_4x_5=x_6, x_5x_6=x_7, x_6x_7=x_1, x_7x_1=x_2>.
The following code will produce a 2-generator, 2-relator presentation for
F(7):
> F<x1, x2, x3, x4, x5, x6, x7> := FreeGroup(7);
> F7<x1, x2, x3, x4, x5, x6, x7> :=
> quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
> x5*x6=x7, x6*x7=x1, x7*x1=x2 >;
> P := TietzeProcess(F7);
> for i := 7 to 3 by -1 do
> Eliminate(~P: Generator := i);
> end for;
> Search(~P);
> H<x, y>, f := Group(P);
> H;
Finitely presented group H on 2 generators
Generators as words in group F7
x = x1
y = x2
Relations
x^-1 * y^-1 * x^-1 * y^-2 * x^-1 * y * x^-1 * y * x^-1 = Id(H)
x * y^3 * x^-1 * y * x^-1 * y^2 * x * y * x * y^-1 = Id(H)
The resulting presentation is
<a, b | a - 1b - 1a - 1b - 2a - 1ba - 1ba - 1, ab 3a - 1ba - 1b 2abab - 1>.
We can use the isomorphism f returned by the function
Group to express arbitrary words in the original
generators of F(7) in terms of the new generators x and y:
> f;
Mapping from: GrpFP: F7 to GrpFP: H
> f(x7);
x * y^2 * x * y^2 * x * y * x * y^2 * x * y
Alternatively, a similar effect may be obtained using the
Simplify function:
> F<x1, x2, x3, x4, x5, x6, x7> := FreeGroup(7);
> F7<x1, x2, x3, x4, x5, x6, x7> :=
> quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
> x5*x6=x7, x6*x7=x1, x7*x1=x2>;
> H<x, y>, f := Simplify(F7: Iterations := 5);
> H;
Finitely presented group H on 2 generators
Generators as words in group F7
x = x2
y = x3
Relations
x * y^-1 * x * y^2 * x * y * x^2 * y^-1 = Id(H)
y * x * y^2 * x^-1 * y * x^-2 * y * x^-2 = Id(H)
Again, we can use the isomorphism f returned by the function
Simplify to express arbitrary words in the original
generators of F(7) in terms of the new generators x and y:
> f;
Mapping from: GrpFP: F7 to GrpFP: H
> f(x7);
y * x * y * x * y^2 * x * y
In a situation where some proper subset S of the original generating set of
a finitely group G is sufficient to generate G, the function
Simplify can also be used to rewrite words in the original
generators in terms of the elements of S. Consider again one of the Fibonacci
groups, say F(8).
> F<x1, x2, x3, x4, x5, x6, x7, x8> := FreeGroup(8);
> F8<x1, x2, x3, x4, x5, x6, x7, x8> :=
> quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
> x5*x6=x7, x6*x7=x8, x7*x8=x1, x8*x1=x2>;
Obviously, F(8) is generated by x 1 and x 2. We utilise the function
Simplify to obtain a presentation H of F(8) on x 1 and
x 2, using the parameter Preserve to indicate that x 1 and x 2 --
i.e. the first and the second generator -- are to be retained in the new
presentation. We also compute the isomorphism f:F(8) -> H.
> H<x, y>, f := Simplify(F8: Preserve := [1,2]);
Mapping elements of F(8) to H using the map f basically means to
rewrite these elements in terms of the generators x = x 1 and y = x 2.
Since H is returned as a subgroup of F(8), the resulting words can be
coerced from H back into F(8), yielding words explicitly in x 1 and
x 2.
> F8 ! f(x5*x6);
x1 * x2^2 * x1 * x2 * x1^2 * x2^-1 * x1 * x2^-1
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|