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 H78E89.
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.
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 H78E11 for a sample application.Iterations: RngIntElt Default: 10000This parameter sets the maximal number of iterations of the main elimination / simplification cycle which will be performed.EliminationLimit: RngIntElt Default: 100This 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: 150If 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: 0Any eliminations which would reduce the number of generators below the value of GeneratorsLimit will not be performed (default: 0).SaveLimit: RngIntElt Default: 10If 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: 20This parameter sets the number of relators processed simultaneously in a simplification phase.Print: RngIntElt Default: 0This 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.
> 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
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: 10000EliminationLimit: RngIntElt Default: 100LengthLimit: RngIntElt Default: ∞ExpandLimit: RngIntElt Default: 150GeneratorsLimit: RngIntElt Default: 0SaveLimit: RngIntElt Default: 10SearchSimultaneous: RngIntElt Default: 20Print: RngIntElt Default: 0These 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.
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.
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: 0If 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: 0If 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.
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.
The number of generators for the presentation currently stored by the Tietze process P.
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.
<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, ab3a - 1ba - 1b2abab - 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 * yAlternatively, 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 x1 and x2. We utilise the function Simplify to obtain a presentation H of F(8) on x1 and x2, using the parameter Preserve to indicate that x1 and x2 -- 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 = x1 and y = x2. 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 x1 and x2.
> F8 ! f(x5*x6); x1 * x2^2 * x1 * x2 * x1^2 * x2^-1 * x1 * x2^-1