Regina Calculation Engine
|
Represents a finite presentation of a group. More...
#include <algebra/ngrouppresentation.h>
Public Member Functions | |
NGroupPresentation () | |
Creates a new presentation with no generators and no relations. More... | |
NGroupPresentation (const NGroupPresentation &cloneMe) | |
Creates a clone of the given group presentation. More... | |
NGroupPresentation (unsigned long nGens, const std::vector< std::string > &rels) | |
Constructor that allows you to directly pass an arbitrary number of relators in string format. More... | |
virtual | ~NGroupPresentation () |
Destroys the group presentation. More... | |
NGroupPresentation & | operator= (const NGroupPresentation &cloneMe) |
Assignment operator. More... | |
unsigned long | addGenerator (unsigned long numToAdd=1) |
Adds one or more generators to the group presentation. More... | |
void | addRelation (NGroupExpression *rel) |
Adds the given relation to the group presentation. More... | |
unsigned long | getNumberOfGenerators () const |
Returns the number of generators in this group presentation. More... | |
unsigned long | getNumberOfRelations () const |
Returns the number of relations in this group presentation. More... | |
const NGroupExpression & | getRelation (unsigned long index) const |
Returns the relation at the given index in this group presentation. More... | |
bool | isValid () const |
Tests whether all of the relations for the group are indeed words in the generators. More... | |
bool | intelligentSimplify () |
Attempts to simplify the group presentation as intelligently as possible without further input. More... | |
std::auto_ptr < NHomGroupPresentation > | intelligentSimplifyDetail () |
Attempts to simplify the group presentation as intelligently as possible without further input. More... | |
bool | smallCancellation () |
Attempts to simplify the group presentation using only small cancellation theory. More... | |
std::auto_ptr < NHomGroupPresentation > | smallCancellationDetail () |
Attempts to simplify the group presentation using small cancellation theory. More... | |
bool | simplifyWord (NGroupExpression &input) const |
Uses small cancellation theory to reduce the input word, using the current presentation of the group. More... | |
void | proliferateRelators (unsigned long depth=1) |
A routine to help escape local wells when simplifying presentations, which may be useful when small cancellation theory can't find the simplest relators. More... | |
std::string | recogniseGroup () const |
Attempts to recognise the group corresponding to this presentation. More... | |
void | writeXMLData (std::ostream &out) const |
Writes a chunk of XML containing this group presentation. More... | |
unsigned long | relatorLength () const |
The sum of the word lengths of the relators. More... | |
std::auto_ptr< NAbelianGroup > | abelianisation () const |
Computes the abelianisation of this group. More... | |
std::auto_ptr < NMarkedAbelianGroup > | markedAbelianisation () const |
Computes the abelianisation of this group. More... | |
bool | identifyAbelian () const |
Attempts to determine if the group is abelian. More... | |
bool | nielsenTransposition (unsigned long i, unsigned long j) |
Switches the generators in the presentation indexed by i and j respectively, and recomputes the appropriate presentation. More... | |
bool | nielsenInvert (unsigned long i) |
Replaces a generator in a presentation by its inverse, and recomputes the appropriate presentation. More... | |
bool | nielsenCombine (unsigned long i, unsigned long j, long k, bool rightMult=true) |
Replaces a generator gi by either (gi)(gj)^k or (gj)^k(gi) in the presentation. More... | |
bool | intelligentNielsen () |
Looks for Nielsen moves that will simplify the presentation. More... | |
std::auto_ptr < NHomGroupPresentation > | intelligentNielsenDetail () |
Looks for Nielsen moves that will simplify the presentation. More... | |
bool | homologicalAlignment () |
Rewrites the presentation so that generators of the group map to generators of the abelianisation, with any left-over generators mapping to zero (if possible). More... | |
std::auto_ptr < NHomGroupPresentation > | homologicalAlignmentDetail () |
Rewrites the presentation so that generators of the group map to generators of the abelianisation, with any left-over generators mapping to zero (if possible). More... | |
bool | prettyRewriting () |
An entirely cosmetic re-writing of the presentation, which is fast and superficial. More... | |
std::auto_ptr < NHomGroupPresentation > | prettyRewritingDetail () |
An entirely cosmetic re-writing of the presentation, which is fast and superficial. More... | |
bool | identifySimplyIsomorphicTo (const NGroupPresentation &other) const |
Attempts to prove that this and the given group presentation are simply isomorphic. More... | |
std::string | toTeX () const |
Returns a TeX representation of this group presentation. More... | |
void | writeTeX (std::ostream &out) const |
Writes a TeX represesentation of this group presentation to the given output stream. More... | |
std::string | toStringCompact () const |
A deprecated alias for compact(), which returns a compact one-line representation of this group presentation. More... | |
std::string | compact () const |
Returns a compact one-line representation of this group presentation, including details of all generators and relations. More... | |
void | writeTextCompact (std::ostream &out) const |
Writes a compact represesentation of this group to the given output stream. More... | |
virtual void | writeTextShort (std::ostream &out) const |
Writes this object in short text format to the given output stream. More... | |
virtual void | writeTextLong (std::ostream &out) const |
Writes this object in long text format to the given output stream. More... | |
Input and Output | |
std::string | str () const |
Returns the output from writeTextShort() as a string. More... | |
std::string | toString () const |
A deprecated alias for str(), which returns the output from writeTextShort() as a string. More... | |
std::string | detail () const |
Returns the output from writeTextLong() as a string. More... | |
std::string | toStringLong () const |
A deprecated alias for detail(), which returns the output from writeTextLong() as a string. More... | |
Protected Attributes | |
unsigned long | nGenerators |
The number of generators. More... | |
std::vector< NGroupExpression * > | relations |
The relations between the generators. More... | |
Represents a finite presentation of a group.
A presentation consists of a number of generators and a set of relations between these generators that together define the group.
If there are g generators, they will be numbered 0, 1, ..., g-1.
|
inline |
Creates a new presentation with no generators and no relations.
regina::NGroupPresentation::NGroupPresentation | ( | const NGroupPresentation & | cloneMe | ) |
Creates a clone of the given group presentation.
cloneMe | the presentation to clone. |
regina::NGroupPresentation::NGroupPresentation | ( | unsigned long | nGens, |
const std::vector< std::string > & | rels | ||
) |
Constructor that allows you to directly pass an arbitrary number of relators in string format.
The first argument nGens is the number of generators one wants the group to have. The second argument rels is a vector of strings, where each string gives a single relator. See the NGroupExpression::NGroupExpression(const std::string&, bool*) constructor notes for information on what format these strings can take.
If any of the given strings could not be interpreted as words, this routine will insert the trivial (unit) word in its place.
If you are compiling Regina against C++11, you can use the C++11 initializer_list construction to construct an NGroupPresentation directly using syntax of the form NGroupPresentation(nGens, { "rel1", "rel2", ... })
.
nGens | the number of generators. |
rels | a vector of relations each given in string form, as outlined above. |
|
inlinevirtual |
Destroys the group presentation.
All relations that are stored will be deallocated.
std::auto_ptr<NAbelianGroup> regina::NGroupPresentation::abelianisation | ( | ) | const |
Computes the abelianisation of this group.
|
inline |
Adds one or more generators to the group presentation.
If the new presentation has g generators, the new generators will be numbered g-1, g-2 and so on.
numToAdd | the number of generators to add. |
|
inline |
Adds the given relation to the group presentation.
The relation must be of the form expression = 1
.
This presentation will take ownership of the given expression, may change it and will be responsible for its deallocation.
rel | the expression that the relation sets to 1; for instance, if the relation is g1^2 g2 = 1 then this parameter should be the expression g1^2 g2 . |
std::string regina::NGroupPresentation::compact | ( | ) | const |
Returns a compact one-line representation of this group presentation, including details of all generators and relations.
See writeTextCompact() for details on how this is formed.
|
inherited |
Returns the output from writeTextLong() as a string.
|
inline |
Returns the number of generators in this group presentation.
|
inline |
Returns the number of relations in this group presentation.
|
inline |
Returns the relation at the given index in this group presentation.
The relation will be of the form expresson = 1
.
index | the index of the desired relation; this must be between 0 and getNumberOfRelations()-1 inclusive. |
g1^2 g2 = 1
then this will be the expression g1^2 g2
. bool regina::NGroupPresentation::homologicalAlignment | ( | ) |
Rewrites the presentation so that generators of the group map to generators of the abelianisation, with any left-over generators mapping to zero (if possible).
Consider this a homological-alignment of the presentation.
See homologicalAlignmentDetail() for further details on what this routine does.
true
if presentation was changed, or false
if the presentation was already homologically aligned. See homologicalAlignmentDetail() if you wish to get the isomorphism. std::auto_ptr<NHomGroupPresentation> regina::NGroupPresentation::homologicalAlignmentDetail | ( | ) |
Rewrites the presentation so that generators of the group map to generators of the abelianisation, with any left-over generators mapping to zero (if possible).
Consider this a homological-alignment of the presentation.
If the abelianisation of this group has rank N and M invariant factors d0 | d2 | ... | d(M-1)
, this routine applies Nielsen moves to the presentation to ensure that under the markedAbelianisation() routine, generators 0 through M-1 are mapped to generators of the relevant Z_di
group. Similarly, generators M through M+N-1 are mapped to +/-1 in the appropriate factor. All further generators will be mapped to zero.
If this routine does return a homomorphism (because the presentation was changed), then this homomorphsm will in fact be a declared isomorphism. See the NHomGroupPresentation class notes for details on what this means.
bool regina::NGroupPresentation::identifyAbelian | ( | ) | const |
Attempts to determine if the group is abelian.
A return value of true
indicates that this routine successfully certified that the group is abelian. A return value of false
indicates an inconclusive result: either the group is non-abelian, or the group is abelian but this routine could not prove so.
If the group is abelian, then markedAbelianization() is the easiest way to see precisely which abelian group it is, and how the generators sit in that group.
You will have better results from this algorithm if the presentation has been simplified, since this algorithm uses small cancellation theory in an attempt to reduce the commutators of all pairs of generators.
false
. Consider running intelligentSimplify, possibly in concert with proliferateRelators(), in order to discover adequately many commutators.true
if the group is shown to be abelian, or false
if the result is inconclusive. bool regina::NGroupPresentation::identifySimplyIsomorphicTo | ( | const NGroupPresentation & | other | ) | const |
Attempts to prove that this and the given group presentation are simply isomorphic.
A simple isomorphism is an isomorphism where each generator gi of this presentation is sent to some generator gj+/-1 of the other presentation. Moreover, at present this routine only looks for maps where both presentations have the same number of generators, and where distinct generators gi of this presentation correspond to distinct generators gj of the other presentation (possibly with inversion, as noted above).
If this routine returns true
, it means that the two presentations are indeed simply isomorphic.
If this routine returns false
, it could mean one of many things:
other | the group presentation to compare with this. |
true
if this routine could certify that the two group presentations are simply isomorphic, or false
if it could not. bool regina::NGroupPresentation::intelligentNielsen | ( | ) |
Looks for Nielsen moves that will simplify the presentation.
Performs one of the most-effective moves, if it can find any.
true
if and only if it performed a Nielsen move. You can call intelligentNielsen() to get the isomorphism. std::auto_ptr<NHomGroupPresentation> regina::NGroupPresentation::intelligentNielsenDetail | ( | ) |
Looks for Nielsen moves that will simplify the presentation.
Performs one of the most-effective moves, if it can find any.
If this routine does return a homomorphism (because some move was performed), then this homomorphsm will in fact be a declared isomorphism. See the NHomGroupPresentation class notes for details on what this means.
bool regina::NGroupPresentation::intelligentSimplify | ( | ) |
Attempts to simplify the group presentation as intelligently as possible without further input.
See intelligentSimplifyDetail() for further details on how the simplification is done.
true
if and only if the group presentation was changed. You can call intelligentSimplifyDetail() to get the isomorphism. std::auto_ptr<NHomGroupPresentation> regina::NGroupPresentation::intelligentSimplifyDetail | ( | ) |
Attempts to simplify the group presentation as intelligently as possible without further input.
The current simplification method uses a combination of small cancellation theory and Nielsen moves.
If this routine does return a homomorphism (because the presentation was changed), then this homomorphsm will in fact be a declared isomorphism. See the NHomGroupPresentation class notes for details on what this means.
bool regina::NGroupPresentation::isValid | ( | ) | const |
Tests whether all of the relations for the group are indeed words in the generators.
This routine returns false
if at least one relator uses an out-of-bound generator, and true
otherwise.
This routine is intended only for sanity checking: you should never have an invalid group presentation in the first place.
true
if and only if all of the relations are words in the generators. std::auto_ptr<NMarkedAbelianGroup> regina::NGroupPresentation::markedAbelianisation | ( | ) | const |
Computes the abelianisation of this group.
The coordinates in the chain complex correspond to the generators and relators for this group.
bool regina::NGroupPresentation::nielsenCombine | ( | unsigned long | i, |
unsigned long | j, | ||
long | k, | ||
bool | rightMult = true |
||
) |
Replaces a generator gi
by either (gi)(gj)^k
or (gj)^k(gi)
in the presentation.
It it is the third type of Nielsen move one can apply to a presentation.
This means that, if the new generator Gi
is the old (gi)(gj)^k
or (gj)^k(gi)
, then we can construct the new presentation from the old by replacing occurrences of Gi
by (Gi)(gj)^(-k)
or (gj)^(-k)(Gi)
respectively.
i | indicates the generator to replace. |
j | indicates the generator to combine with gi . |
k | indicates the power to which we raise gj when performing the replacement; this may be positive or negative (or zero, but this will have no effect). |
rightMult | true if we should replace gi by (gi)(gj)^k , or false if we should replace gi by (gj)^k(gi) . |
true
if and only if the nielsen automorphism had an effect on at least one relation. bool regina::NGroupPresentation::nielsenInvert | ( | unsigned long | i | ) |
Replaces a generator in a presentation by its inverse, and recomputes the appropriate presentation.
This is the second generator type of the automorphism group of a free group.
i | indicates the generator to invert. |
true
if and only if the Nielsen automorphism had an effect on at least one relation. bool regina::NGroupPresentation::nielsenTransposition | ( | unsigned long | i, |
unsigned long | j | ||
) |
Switches the generators in the presentation indexed by i and j respectively, and recomputes the appropriate presentation.
It is one of the standard Nielsen moves, which is the first of three generator types of the automorphism group of a free group.
i | indicates the first of the two generators to switch. |
j | indicates the second of the two generators to switch. |
true
if and only if the Nielsen automorphism had an effect on at least one relation. NGroupPresentation& regina::NGroupPresentation::operator= | ( | const NGroupPresentation & | cloneMe | ) |
Assignment operator.
cloneMe | the group presentation that this will become a copy of. |
bool regina::NGroupPresentation::prettyRewriting | ( | ) |
An entirely cosmetic re-writing of the presentation, which is fast and superficial.
See prettyRewritingDetail() for further details on what this routine does.
true
if and only if the choice of generators for the group has changed. You can call prettyRewritingDetail() to get the the isomorphism. std::auto_ptr<NHomGroupPresentation> regina::NGroupPresentation::prettyRewritingDetail | ( | ) |
An entirely cosmetic re-writing of the presentation, which is fast and superficial.
If this routine does return a homomorphism (because the choice of generators was changed), then this homomorphsm will in fact be a declared isomorphism. See the NHomGroupPresentation class notes for details on what this means.
void regina::NGroupPresentation::proliferateRelators | ( | unsigned long | depth = 1 | ) |
A routine to help escape local wells when simplifying presentations, which may be useful when small cancellation theory can't find the simplest relators.
Given a presentation <g_i | r_i>, this routine appends consequences of the relators {r_i} to the presentation that are of the form ab, where both a and b are cyclic permutations of relators from the collection {r_i}.
Passing depth=1 means it will only form products of two relators. Depth=2 means products of three, etc. Depth=4 is typically the last depth before the exponential growth of the operation grows out of hand. It also conveniently trivializes all the complicated trivial group presentations that we've come across so far.
depth | controls the depth of the proliferation, as described above; this must be strictly positive. |
std::string regina::NGroupPresentation::recogniseGroup | ( | ) | const |
Attempts to recognise the group corresponding to this presentation.
This routine is much more likely to be successful if you have already called intelligentSimplify().
Currently, if successful the only groups this routine recognises is: the trivial group, abelian groups, free groups, extensions over the integers, and free products of any group the algorithm can recognise (inductively).
Return strings have the form:
0
for the trivial group;Z_n
for cyclic groups with n > 1;Free(n)
for free groups with n > 1 generators - see NAbelianGroup::str() for how abelian groups are presented;FreeProduct(G1, G2, ... , Gk)
for free products, where one replaces G1 through Gk by text strings representing the free summands;Z~G w/ monodromy H
for extensions over Z, where G is a description of the kernel of the homomorphism to the integers, and H is a text string representing the monodromy - see NHomMarkedAbelianGroup.str() for details on how these are presented.
|
inline |
The sum of the word lengths of the relators.
Word lengths are computing using NGroupExpression::wordLength(). Used as a coarse measure of the complexity of the presentation.
bool regina::NGroupPresentation::simplifyWord | ( | NGroupExpression & | input | ) | const |
Uses small cancellation theory to reduce the input word, using the current presentation of the group.
The input word will be modified directly.
input | is the word you would like to simplify. This must be a word in the generators of this group. |
true
if and only if the input word was modified. bool regina::NGroupPresentation::smallCancellation | ( | ) |
Attempts to simplify the group presentation using only small cancellation theory.
See smallCancellationDetail() for further details on how the simplification is done.
true
if and only if the group presentation was changed. You can call smallCancellationDetail() to get the isomorphism. std::auto_ptr<NHomGroupPresentation> regina::NGroupPresentation::smallCancellationDetail | ( | ) |
Attempts to simplify the group presentation using small cancellation theory.
The simplification method is based on the Dehn algorithm for hyperbolic groups, i.e. small cancellation theory. This means we look to see if part of one relator can be used to simplify others. If so, make the substitution and simplify. We continue until no more presentation-shortening substitutions are available. We follow that by killing any available generators using words where generators appear a single time.
If this routine does return a homomorphism (because the presentation was changed), then this homomorphsm will in fact be a declared isomorphism. See the NHomGroupPresentation class notes for details on what this means.
|
inherited |
Returns the output from writeTextShort() as a string.
__str__()
function.
|
inlineinherited |
A deprecated alias for str(), which returns the output from writeTextShort() as a string.
std::string regina::NGroupPresentation::toStringCompact | ( | ) | const |
A deprecated alias for compact(), which returns a compact one-line representation of this group presentation.
|
inlineinherited |
A deprecated alias for detail(), which returns the output from writeTextLong() as a string.
std::string regina::NGroupPresentation::toTeX | ( | ) | const |
Returns a TeX representation of this group presentation.
See writeTeX() for details on how this is formed.
void regina::NGroupPresentation::writeTeX | ( | std::ostream & | out | ) | const |
Writes a TeX represesentation of this group presentation to the given output stream.
The output will be of the form < generators | relators >. There will be no final newline.
out | the output stream to which to write. |
void regina::NGroupPresentation::writeTextCompact | ( | std::ostream & | out | ) | const |
Writes a compact represesentation of this group to the given output stream.
The output will be of the form < generators | relators >. The full relations will be included, and the entire output will be written on a single line. There will be no final newline.
out | the output stream to which to write. |
|
virtual |
Writes this object in long text format to the given output stream.
The output should provide the user with all the information they could want. The output should be human-readable, should not contain extremely long lines (so users can read the output in a terminal), and should end with a final newline.
The default implementation of this routine merely calls writeTextShort() and adds a newline.
out | the output stream to which to write. |
Reimplemented from regina::ShareableObject.
|
inlinevirtual |
Writes this object in short text format to the given output stream.
The output should be human-readable, should fit on a single line, and should not end with a newline.
out | the output stream to which to write. |
Implements regina::ShareableObject.
void regina::NGroupPresentation::writeXMLData | ( | std::ostream & | out | ) | const |
Writes a chunk of XML containing this group presentation.
out | the output stream to which the XML should be written. |
|
protected |
The number of generators.
|
protected |
The relations between the generators.