Represents a finite presentation of a group. More...

#include <algebra/grouppresentation.h>

Inheritance diagram for regina::GroupPresentation:

Public Member Functions
	GroupPresentation ()
	Creates a new presentation with no generators and no relations. More...

	GroupPresentation (const GroupPresentation &src)=default
	Creates a clone of the given group presentation. More...

	GroupPresentation (GroupPresentation &&src) noexcept=default
	Moves the contents of the given group presentation to this new group presentation. More...

	GroupPresentation (unsigned long nGenerators)
	Creates the free group on the given number of generators. More...

	GroupPresentation (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...

GroupPresentation &	operator= (const GroupPresentation &src)=default
	Sets this to be a clone of the given group presentation. More...

GroupPresentation &	operator= (GroupPresentation &&src) noexcept=default
	Moves the contents of the given group presentation to this group presentation. More...

void	swap (GroupPresentation &other) noexcept
	Swaps the contents of this and the given group presentation. More...

unsigned long	addGenerator (unsigned long numToAdd=1)
	Adds one or more generators to the group presentation. More...

void	addRelation (GroupExpression rel)
	Adds the given relation to the group presentation. More...

unsigned long	countGenerators () const
	Returns the number of generators in this group presentation. More...

size_t	countRelations () const
	Returns the number of relations in this group presentation. More...

const GroupExpression &	relation (size_t index) const
	Returns the relation at the given index in this group presentation. More...

const std::vector< GroupExpression > &	relations () const
	Returns the list of all relations in this group presentation. More...

bool	isValid () const
	Tests whether all of the relations for the group are indeed words in the generators. More...

std::optional< HomGroupPresentation >	intelligentSimplify ()
	Attempts to simplify the group presentation as intelligently as possible without further input. More...

std::optional< HomGroupPresentation >	smallCancellation ()
	Attempts to simplify the group presentation using small cancellation theory. More...

bool	simplifyAndConjugate (GroupExpression &word) const
	Uses small cancellation theory to reduce the input word, modulo conjugation, 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 (bool moreUtf8=false) 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...

size_t	relatorLength () const
	The sum of the word lengths of the relators. More...

AbelianGroup	abelianisation () const
	Computes the abelianisation of this group. More...

unsigned long	abelianRank () const
	Computes the rank of the abelianisation of this group. More...

MarkedAbelianGroup	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...

std::optional< HomGroupPresentation >	intelligentNielsen ()
	Looks for Nielsen moves that will simplify the presentation. More...

std::optional< HomGroupPresentation >	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::optional< HomGroupPresentation >	prettyRewriting ()
	An entirely cosmetic re-writing of the presentation, which is fast and superficial. More...

bool	operator== (const GroupPresentation &other) const
	Determines whether this and the given group presentation are identical. More...

bool	operator!= (const GroupPresentation &other) const
	Determines whether this and the given group presentation are not identical. More...

bool	identifySimplyIsomorphicTo (const GroupPresentation &other) const
	Attempts to prove that this and the given group presentation are simply isomorphic. More...

template<int index, typename Action , typename... Args>
size_t	enumerateCovers (Action &&action, Args &&... args) const
	Enumerates all transitive representations of this group into the symmetric group S(k). More...

Matrix< bool >	incidence () const
	Returns a matrix indicating which generators are used by which relations. More...

std::string	tex () 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	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 one-line represesentation of this group to the given output stream. More...

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream. More...

void	writeTextLong (std::ostream &out) const
	Writes a detailed text representation of this object to the given output stream. More...

std::string	gap (const std::string &groupVariable="g") const
	Returns a sequence of GAP commands that create this group. More...

FinitelyPresentedGroup	sage () const
	A SageMath-only routine that returns a copy of this group presentation in a format native to SageMath. More...

std::string	str () const
	Returns a short text representation of this object. More...

std::string	utf8 () const
	Returns a short text representation of this object using unicode characters. More...

std::string	detail () const
	Returns a detailed text representation of this object. More...

Protected Attributes
unsigned long	nGenerators_
	The number of generators. More...

std::vector< GroupExpression >	relations_
	The relations between the generators. More...

Detailed Description

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.

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

Todo:: Let's make intelligent simplify a tad more intelligent, and the GUI call a bit more safe. Perhaps parallelize the GUI call, and give users parameters to ensure it won't crash the computer. Also look at the FPGroup package. We should also have a simple way of creating GroupPresentation objects directly from text strings. We would like to have something like GroupPresentation( numGens, "abAAB", "bccd" ) etc., with arbitrary numbers of relators. Maybe std::tuple. Or "variadic templates"?

Constructor & Destructor Documentation

◆ GroupPresentation() [1/5]

regina::GroupPresentation::GroupPresentation ( )

inline

Creates a new presentation with no generators and no relations.

◆ GroupPresentation() [2/5]

regina::GroupPresentation::GroupPresentation ( const GroupPresentation & src )

default

Creates a clone of the given group presentation.

Parameters

src	the group presentation to clone.

◆ GroupPresentation() [3/5]

regina::GroupPresentation::GroupPresentation ( GroupPresentation && src )

defaultnoexcept

Moves the contents of the given group presentation to this new group presentation.

This is a fast (constant time) operation.

The group presentation that was passed (src) will no longer be usable.

Parameters

src	the group presentation to move.

◆ GroupPresentation() [4/5]

regina::GroupPresentation::GroupPresentation ( unsigned long nGenerators )

inline

Creates the free group on the given number of generators.

Parameters

nGenerators the number of generators.

◆ GroupPresentation() [5/5]

regina::GroupPresentation::GroupPresentation	(	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 GroupExpression::GroupExpression(const std::string&) constructor notes for information on what format these strings can take.

If you wish to create a group presentation from a hard-coded list of relations, you can use this constructor with an initialiser list, via syntax of the form GroupPresentation(nGens, { "rel1", "rel2", ... }).

Exceptions

InvalidArgument One or more of the given strings could not be interpreted as a group expression, and/or contains an out-of-range generator.

Parameters

nGens	the number of generators.
rels	a vector of relations each given in string form, as outlined above.

Member Function Documentation

◆ abelianisation()

AbelianGroup regina::GroupPresentation::abelianisation ( ) const

Computes the abelianisation of this group.

Returns: the abelianisation of this group.

◆ abelianRank()

unsigned long regina::GroupPresentation::abelianRank ( ) const

Computes the rank of the abelianisation of this group.

This is the number of Z summands in the abelianisation (i.e., ignoring any torsion summands).

This is much less informative than computing the full abelianisation, but in some cases it might be significantly faster (since it involves just a matrix rank computation as opposed to a Smith normal form).

The result of this routine should be the same as the output of abelianisation().rank().

Returns: the rank of the abelianisation of this group.

◆ addGenerator()

unsigned long regina::GroupPresentation::addGenerator ( unsigned long numToAdd = 1 )

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.

Parameters

numToAdd the number of generators to add.

Returns: the number of generators in the new presentation.

◆ addRelation()

void regina::GroupPresentation::addRelation ( GroupExpression rel )

inline

Adds the given relation to the group presentation.

The relation must be of the form expression = 1.

Warning: This routine does not check whether or not your relation is a word only in the generators of this group. In other words, it does not stop you from using generators beyond the countGenerators() bound.

Parameters

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`.

◆ compact()

std::string regina::GroupPresentation::compact ( ) const

Returns a compact one-line representation of this group presentation, including details of all generators and relations.

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.

Currently str() and compact() are identical functions, though the output from str() may change in future versions of Regina.

Returns: a compact representation of this group presentation.

◆ countGenerators()

unsigned long regina::GroupPresentation::countGenerators ( ) const

inline

Returns the number of generators in this group presentation.

Returns: the number of generators.

◆ countRelations()

size_t regina::GroupPresentation::countRelations ( ) const

inline

Returns the number of relations in this group presentation.

Returns: the number of relations.

◆ detail()

std::string regina::Output< GroupPresentation , false >::detail ( ) const

inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns: a detailed text representation of this object.

◆ enumerateCovers()

template<int index, typename Action , typename... Args>

size_t regina::GroupPresentation::enumerateCovers	(	Action &&	action,
		Args &&...	args
	)		const

inline

Enumerates all transitive representations of this group into the symmetric group S(k).

Each representation is produced exactly once up to conjugacy.

Each such representation corresponds to an index k subgroup, and the multiset of the abelianisations of all these subgroups is a group invariant that (for small enough k) can be computed in reasonable time.

If this is the fundamental group of a manifold, then each such representation also corresponds to a connected k-sheeted cover.

For each representation that is produced, this routine will call action (which must be a function or some other callable object).

The first argument to action must be a group presentation. This will be the index k subgroup corresponding to the representation. This argument will be passed as an rvalue; a typical action could (for example) take it by const reference and query it, or take it by value and modify it, or take it by rvalue reference and move it into more permanent storage.
If there are any additional arguments supplied in the list args, then these will be passed as subsequent arguments to action.
action must return void.
It is completely safe for action to (if you wish) make changes to the original presentation (i.e., the group presentation upon which enumerateCovers() is being called). This will not interfere with the enumeration or change the results in any way.

This routine produces a constant stream of output (i.e., it calls action as soon as each representation is found).

Warning: The running time is (k!)^g, where k is the subgroup index described above, and g is the number of generators of this group presentation. In particular, the running time grows extremely quickly with k. Moreover, for larger indices this routine may precompute some tables that will never be released (but which only need to be computed the first time that index is used); for index 10 these tables will consume roughly 30MB, and for index 11 they will consume around 320MB.; This routine does not simplify the group presentation before it runs. You should make sure that you have simplified the presentation, either using Regina or some other tool, before running this routine, since (as noted above) the running time is exponential in the number of generators.; Likewise, this routine does not simplify the subgroup presentations before passing them to action. These presentations can be quite large, and (for example) if all you care about is their abelianisations then you are better off using the abelian group simplification / computation instead (which is much faster).

Precondition: Arrays on this system can be large enough to store 2⋅(n-2)! objects. This is a technical condition on the bit-size of size_t that will be explicitly checked (with an exception thrown if it fails). On a 64-bit system this condition will be true for all supported n, but on a 32-bit system or smaller it will mean that enumerateCovers() cannot be used for larger values of n.

Exceptions

FailedPrecondition A signed integer of the same bit-size as size_t cannot hold 2⋅(n-2)!. See the precondition above for further discussion on this constraint.

Warning: The API for this class or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release to see if you need to make changes to your code.

Python: There are two versions of this function available in Python. The first form is enumerateCovers(index, action), which mirrors the C++ function: it takes action which may be a pure Python function, it returns the number of representations found, but it does not take an addition argument list (args). The second form is enumerateCovers(index), which returns a Python list containing all of the corresponding subgroups, each given as a GroupPresentation. In both forms, the template parameter index becomes the first argument to the Python function.

Template Parameters

index the number k in the description above; in other words, the index of the resulting subgroups. Currently this must be between 2 and 11 inclusive; this range is limited because some of the cached precomputations can consume a lot of space for larger indices.

Parameters

action	a function (or other callable object) to call for each representation that is found.
args	any additional arguments that should be passed to action, following the initial subgroup presentation argument.

Returns: the total number of representations found.

◆ gap()

std::string regina::GroupPresentation::gap ( const std::string & groupVariable = "g" ) const

Returns a sequence of GAP commands that create this group.

GAP is a widely-used computational algebra system, and can be downloaded from http://gap-system.org/ .

Other than the variable for the group itself, the commands returned will not use or modify any other GAP variables with the current GAP scope.

The string that is returned will be presented as a single (possibly very long) GAP function call, and will not contain any newlines.

Parameters

groupVariable the name of the GAP variable to which this group will be assigned.

Returns: a sequence of commands to create this group in GAP.

◆ homologicalAlignment()

std::optional< HomGroupPresentation > regina::GroupPresentation::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.

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 HomGroupPresentation class notes for details on what this means.

Note: If you all care about is whether the presentation changed, you can simply cast the return value to a bool. This will then mirror the behaviour of homologicalAlignment() from Regina 6.0 and earlier, when the return type was simply bool.

Returns: an isomorphism describing the reduction map from the original presentation to the new presentation, or no value if this presentation was not changed.

◆ identifyAbelian()

bool regina::GroupPresentation::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.

Warning: If you have not adequately simplified this presentation this routine will most likely return false. Consider running intelligentSimplify, possibly in concert with proliferateRelators(), in order to discover adequately many commutators.

Returns: true if the group is shown to be abelian, or false if the result is inconclusive.

◆ identifySimplyIsomorphicTo()

bool regina::GroupPresentation::identifySimplyIsomorphicTo ( const GroupPresentation & 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:

The groups are not isomorphic;
The groups are isomorphic, but not simply isomorphic;
The groups are simply isomorphic but this routine could not prove it, due to difficulties with the word problem.

Parameters

other the group presentation to compare with this.

Returns: true if this routine could certify that the two group presentations are simply isomorphic, or false if it could not.

◆ incidence()

Matrix< bool > regina::GroupPresentation::incidence ( ) const

Returns a matrix indicating which generators are used by which relations.

The rows of the matrix correspond to the relations 0,1,..., and the columns correspond to the generators 0,1,.... The matrix entry in row r, column g will be true if and only if relation r uses generator g.

Precondition: The numbers of generators and relations are both non-zero.

Returns: the incidence matrix between relators and generators.

◆ intelligentNielsen()

std::optional< HomGroupPresentation > regina::GroupPresentation::intelligentNielsen ( )

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 HomGroupPresentation class notes for details on what this means.

This routine is guaranteed to be deterministic: within the same version of Regina, simplifying identical group presentations will give identical results. These results could, however, change between different versions of Regina.

Note: If you all care about is whether the presentation changed, you can simply cast the return value to a bool. This will then mirror the behaviour of intelligentNielsen() from Regina 6.0 and earlier, when the return type was simply bool.

Returns: an isomorphism describing the map from the original presentation to the new presentation, or no value if this presentation was not changed.

◆ intelligentSimplify()

std::optional< HomGroupPresentation > regina::GroupPresentation::intelligentSimplify ( )

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 HomGroupPresentation class notes for details on what this means.

This routine is guaranteed to be deterministic: within the same version of Regina, simplifying identical group presentations will give identical results. These results could, however, change between different versions of Regina.

Note: If you all care about is whether the presentation changed, you can simply cast the return value to a bool. This will then mirror the behaviour of intelligentSimplify() from Regina 6.0 and earlier, when the return type was simply bool.

Returns: an isomorphism describing the reduction map from the original presentation to the new presentation, or no value if this presentation was not changed.

◆ isValid()

bool regina::GroupPresentation::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.

Returns: true if and only if all of the relations are words in the generators.

◆ markedAbelianisation()

MarkedAbelianGroup regina::GroupPresentation::markedAbelianisation ( ) const

Computes the abelianisation of this group.

The coordinates in the chain complex correspond to the generators and relators for this group.

Returns: the abelianisation of this group.

◆ nielsenCombine()

bool regina::GroupPresentation::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.

Precondition: Both i and j are strictly less than countGenerators().

Parameters

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)`.

Returns: true if and only if the nielsen automorphism had an effect on at least one relation.

◆ nielsenInvert()

bool regina::GroupPresentation::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.

Precondition: i is strictly less than countGenerators().

Parameters

i	indicates the generator to invert.

Returns: true if and only if the Nielsen automorphism had an effect on at least one relation.

◆ nielsenTransposition()

bool regina::GroupPresentation::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.

Precondition: Both i and j are strictly less than countGenerators().

Parameters

i	indicates the first of the two generators to switch.
j	indicates the second of the two generators to switch.

Returns: true if and only if the Nielsen automorphism had an effect on at least one relation.

◆ operator!=()

bool regina::GroupPresentation::operator!= ( const GroupPresentation & other ) const

inline

Determines whether this and the given group presentation are not identical.

This routine does not test for isomorphism (which in general is an undecidable problem). Instead it tests whether this and the given presentation use exactly the same generators and exactly the same relations, presented in exactly the same order.

Parameters

other the group presentation to compare with this.

Returns: true if and only if this and the given group presentation are not identical.

◆ operator=() [1/2]

GroupPresentation & regina::GroupPresentation::operator= ( const GroupPresentation & src )

default

Sets this to be a clone of the given group presentation.

Parameters

src	the group presentation to copy.

Returns: a reference to this group presentation.

◆ operator=() [2/2]

GroupPresentation & regina::GroupPresentation::operator= ( GroupPresentation && src )

defaultnoexcept

Moves the contents of the given group presentation to this group presentation.

This is a fast (constant time) operation.

The group presentation that was passed (src) will no longer be usable.

Parameters

src	the group presentation to move.

Returns: a reference to this group presentation.

◆ operator==()

bool regina::GroupPresentation::operator== ( const GroupPresentation & other ) const

inline

Determines whether this and the given group presentation are identical.

This routine does not test for isomorphism (which in general is an undecidable problem). Instead it tests whether this and the given presentation use exactly the same generators and exactly the same relations, presented in exactly the same order.

Parameters

other the group presentation to compare with this.

Returns: true if and only if this and the given group presentation are identical.

◆ prettyRewriting()

std::optional< HomGroupPresentation > regina::GroupPresentation::prettyRewriting ( )

An entirely cosmetic re-writing of the presentation, which is fast and superficial.

If there are any length 1 relators, those generators are deleted, and the remaining relators simplified.
It sorts the relators by number of generator indices that appear, followed by relator numbers (lexico) followed by relator length.
It inverts relators if the net sign of the generators is negative.
Given each generator, it looks for the smallest word where that generator appears with non-zero weight. If negative weight, it inverts that generator.
It cyclically permutes relators to start with smallest gen.

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 HomGroupPresentation class notes for details on what this means.

This routine is guaranteed to be deterministic: within the same version of Regina, simplifying identical group presentations will give identical results. These results could, however, change between different versions of Regina.

Note: If you all care about is whether the presentation changed, you can simply cast the return value to a bool. This will then mirror the behaviour of prettyRewriting() from Regina 6.0 and earlier, when the return type was simply bool.

Todo:: As a final step, make elementary simplifications to aid in seeing standard relators like commutators.

Returns: an isomorphism describing the map from the original presentation to the new presentation, or no value if this presentation was not changed.

◆ proliferateRelators()

void regina::GroupPresentation::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.

Warning: Do not call this routine with depth n before having called it at depth n-1 first. Depth=0 is invalid, and depth=1 should be your first call to this routine. This routine gobbles up an exponential amount of memory (exponential in your presentation size times n). So do be careful when using it.

Parameters

depth controls the depth of the proliferation, as described above; this must be strictly positive.

◆ recogniseGroup()

std::string regina::GroupPresentation::recogniseGroup ( bool moreUtf8 = false ) 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, the groups this routine recognises include: the trivial group, abelian groups, free groups, extensions over the integers, and free products of any group the algorithm can recognise (inductively).

The string returned from this routine may use some unicode characters, which will be encoding using UTF-8. If moreUtf8 is passed as false then unicode will be used sparingly; if moreUtf8 is true then unicode will be use more liberally, resulting in strings that look nicer but require more complex fonts to be available on the user's machine.

Examples of the format of the returned string are:

0 for the trivial group;
Z_n for cyclic groups with n > 1;
Free(n) for free groups with n > 1 generators - see AbelianGroup::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 HomMarkedAbelianGroup.str() for details on how these are presented.

Todo:
Feature (long-term): Make this recognition more effective.

Returns: a simple string representation of the group if it is recognised, or an empty string if the group is not recognised.

◆ relation()

const GroupExpression & regina::GroupPresentation::relation ( size_t index ) const

inline

Returns the relation at the given index in this group presentation.

The relation will be of the form expresson = 1.

Parameters

index the index of the desired relation; this must be between 0 and countRelations()-1 inclusive.

Returns: the expression that the requested relation sets to 1; for instance, if the relation is g1^2 g2 = 1 then this will be the expression g1^2 g2.

◆ relations()

const std::vector< GroupExpression > & regina::GroupPresentation::relations ( ) const

inline

Returns the list of all relations in this group presentation.

Python: This routine returns a python list of copied GroupExpression objects. In particular, modifying this list or the relations within it will not modify the group presentation from which they came.

Python: The list itself is not returned by reference (instead this routine returns a new Python list). However, the relations within this list are still returned by reference.

Returns: the list of relations.

◆ relatorLength()

size_t regina::GroupPresentation::relatorLength ( ) const

inline

The sum of the word lengths of the relators.

Word lengths are computing using GroupExpression::wordLength(). Used as a coarse measure of the complexity of the presentation.

Returns: the sum of word lengths.

◆ sage()

FinitelyPresentedGroup regina::GroupPresentation::sage ( ) const

A SageMath-only routine that returns a copy of this group presentation in a format native to SageMath.

C++: Not present.

Python: Only present when run within SageMath.

Returns: a copy of this group as a mathematical object native to SageMath.

◆ simplifyAndConjugate()

bool regina::GroupPresentation::simplifyAndConjugate ( GroupExpression & word ) const

Uses small cancellation theory to reduce the input word, modulo conjugation, using the current presentation of the group.

The input word will be modified directly.

By "modulo conjugation", we mean: if w represents the input word, then this routine might (as part of the reduction process) transform w into a different group element of the form g w g^-1.

In Regina 7.2 and earlier, this routine was called simplifyWord(). It was renamed to simplifyAndConjugate() in Regina 7.3 to make it clear to the user that conjugation might take place. Note that, even in older versions of Regina, this routine could always potentially conjugate.

Warning: This routine is only as good as the relator table for the group. You might want to consider running intelligentSimplify(), possibly in concert with proliferateRelators(), before using this routine for any significant tasks.

Parameters

word	the word you would like to simplify (modulo conjugation). This must be a word in the generators of this group.

Returns: true if and only if the input word was modified.

◆ smallCancellation()

std::optional< HomGroupPresentation > regina::GroupPresentation::smallCancellation ( )

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 HomGroupPresentation class notes for details on what this means.

This routine is guaranteed to be deterministic: within the same version of Regina, simplifying identical group presentations will give identical results. These results could, however, change between different versions of Regina.

Note: If you all care about is whether the presentation changed, you can simply cast the return value to a bool. This will then mirror the behaviour of smallCancellation() from Regina 6.0 and earlier, when the return type was simply bool.

Todo:: Optimise (long-term): This routine could use some small tweaks - recognition of utility of some score==0 moves, such as commutators, for example.

Returns: an isomorphism describing the reduction map from the original presentation to the new presentation, or no value if this presentation was not changed.

◆ str()

std::string regina::Output< GroupPresentation , false >::str ( ) const

inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python __str__() and __repr__() functions.

Python: The Python "stringification" function __str__() will use precisely this function, and for most classes the Python __repr__() function will incorporate this into its output.

Returns: a short text representation of this object.

◆ swap()

void regina::GroupPresentation::swap ( GroupPresentation & other )

inlinenoexcept

Swaps the contents of this and the given group presentation.

Parameters

other the group presentation whose contents should be swapped with this.

◆ tex()

std::string regina::GroupPresentation::tex ( ) const

Returns a TeX representation of this group presentation.

The output will be of the form < generators | relators >. There will be no final newline.

Returns: a TeX representation of this group presentation.

◆ utf8()

std::string regina::Output< GroupPresentation , false >::utf8 ( ) const

inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns: a short text representation of this object.

◆ writeTeX()

void regina::GroupPresentation::writeTeX ( std::ostream & out ) const

Writes a TeX represesentation of this group presentation to the given output stream.

See tex() for details on how this is formed.

Python: Not present. Instead use the variant tex() that takes no arguments and returns a string.

Parameters

out	the output stream to which to write.

◆ writeTextCompact()

void regina::GroupPresentation::writeTextCompact ( std::ostream & out ) const

Writes a compact one-line represesentation of this group to the given output stream.

See compact() for details on how this is formed.

Currently writeTextShort() and writeTextCompact() are identical functions, though the output from writeTextShort() may change in future versions of Regina.

Python: Not present. Instead use the variant compact() that takes no arguments and returns a string.

Parameters

out	the output stream to which to write.

◆ writeTextLong()

void regina::GroupPresentation::writeTextLong ( std::ostream & out ) const

Writes a detailed text representation of this object to the given output stream.

Python: Not present. Use detail() instead.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

void regina::GroupPresentation::writeTextShort ( std::ostream & out ) const

inline

Writes a short text representation of this object to the given output stream.

Currently writeTextShort() and writeTextCompact() are identical functions, though the output from writeTextShort() may change in future versions of Regina.

Python: Not present. Use str() instead.

Parameters

out	the output stream to which to write.

◆ writeXMLData()

void regina::GroupPresentation::writeXMLData ( std::ostream & out ) const

Writes a chunk of XML containing this group presentation.

Python: The argument out should be an open Python file object.

Parameters

out	the output stream to which the XML should be written.

Member Data Documentation

◆ nGenerators_

unsigned long regina::GroupPresentation::nGenerators_

protected

The number of generators.

◆ relations_

std::vector<GroupExpression> regina::GroupPresentation::relations_

protected

The relations between the generators.

The documentation for this class was generated from the following file:

algebra/grouppresentation.h

Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ GroupPresentation() [1/5]

◆ GroupPresentation() [2/5]

◆ GroupPresentation() [3/5]

◆ GroupPresentation() [4/5]

◆ GroupPresentation() [5/5]

Member Function Documentation

◆ abelianisation()

◆ abelianRank()

◆ addGenerator()

◆ addRelation()

◆ compact()

◆ countGenerators()

◆ countRelations()

◆ detail()

◆ enumerateCovers()

◆ gap()

◆ homologicalAlignment()

◆ identifyAbelian()

◆ identifySimplyIsomorphicTo()

◆ incidence()

◆ intelligentNielsen()

◆ intelligentSimplify()

◆ isValid()

◆ markedAbelianisation()

◆ nielsenCombine()

◆ nielsenInvert()

◆ nielsenTransposition()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ prettyRewriting()

◆ proliferateRelators()

◆ recogniseGroup()

◆ relation()

◆ relations()

◆ relatorLength()

◆ sage()

◆ simplifyAndConjugate()

◆ smallCancellation()

◆ str()

◆ swap()

◆ tex()

◆ utf8()

◆ writeTeX()

◆ writeTextCompact()

◆ writeTextLong()

◆ writeTextShort()

◆ writeXMLData()

Member Data Documentation

◆ nGenerators_

◆ relations_