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 leftover 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 leftover generators mapping to zero (if possible). More...  
bool  prettyRewriting () 
An entirely cosmetic rewriting of the presentation, which is fast and superficial. More...  
std::auto_ptr < NHomGroupPresentation >  prettyRewritingDetail () 
An entirely cosmetic rewriting 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 oneline representation of this group presentation. More...  
std::string  compact () const 
Returns a compact oneline 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, ..., g1.

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 g1, g2 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 oneline 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 leftover generators mapping to zero (if possible).
Consider this a homologicalalignment 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 leftover generators mapping to zero (if possible).
Consider this a homologicalalignment of the presentation.
If the abelianisation of this group has rank N and M invariant factors d0  d2  ...  d(M1)
, this routine applies Nielsen moves to the presentation to ensure that under the markedAbelianisation() routine, generators 0 through M1 are mapped to generators of the relevant Z_di
group. Similarly, generators M through M+N1 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 nonabelian, 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 g_{i} of this presentation is sent to some generator g_{j}^{+/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 g_{i} of this presentation correspond to distinct generators g_{j} 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 mosteffective 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 mosteffective 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 outofbound 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 rewriting 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 rewriting 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 presentationshortening 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 oneline 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 humanreadable, 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 humanreadable, 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.