Groups and Monoids

The abstract types Group <: Monoid encompass all multiplicative groups and monoids. Since these are already abstract, we skip the Abstract prefix.

Assumptions

GroupsCore implements some methods with default values, which may not be generally true for all groups. The intent is to limit the extent of the required interface. This requires special care when implementing groups/monoids that need to override these default methods.

The methods we currently predefine are:

  • GroupsCore.hasgens(::Monoid) = true This is based on the broad assumption that reasonably generic functions manipulating groups/monoids can be implemented only with an access to a generating set.

  • For finite groups/monoids only we define Base.length(M) = order(Int, M)

Danger

In general length should be used for iteration purposes only. If you are interested in the number of distinct elements of a groups/monoids, use order(::Type{<:Integer}, ::Group). For more information see Iteration.

Obligatory methods

Here we list the minimal set of functions that a group object must extend to implement the Monoid interface:

  • Base.one(::Monoid) and
GroupsCore.order — Method
order([::Type{T} = BigInt, ]M::Monoid) where T

Return the order of M as an instance of T. If M is of infinite order, GroupsCore.InfiniteOrder exception will be thrown.

Warning

Only arbitrary sized integers are required to return a mathematically correct answer.

source

Iteration

If a group/monoid is defined by generators (i.e. hasgens(M) returns true) an important aspect of this interface is the iteration over a group.

Iteration over infinite objects seem to be useful only when the returned elements explore the whole group or monoid. To be precise, for the example of the free group $F_2 = ⟨a,b⟩$, one could implement iteration by sequence

\[a, a^2, a^3, \ldots,\]

which is arguably less useful than

\[a, b, a^{-1}, b^{-1}, ab, \ldots.\]

Therefore we put the following assumptions on iteration.

  • Iteration is mandatory only if hasgens(M) returns true.
  • The first element of the iteration (e.g. given by Base.first) is the group identity.
  • Iteration over an infinite group/monoid should exhaust every fixed radius ball around the identity (in word-length metric associated to gens(M)) in finite time.
  • There is no requirement that in the iteration sequence elements are returned only once.

These are just the conventions, the iteration interface consists of standard julia methods:

Base.IteratorSize — Method
IteratorSize(::Type{M}) where {M <: Monoid}

Given the type of a monoid, return one of the following values:

  • Base.IsInfinite() if all instances of groups of type M are infinite.
  • Base.HasLength() or Base.HasShape{N}() if all instances are finite.
  • Base.SizeUnknown() otherwise, [the default].
source

In contrast to julia we default to Base.SizeUnknown() to provide a mathematically correct fallback. If a group or monoid is finite by definition, implementing the correct IteratorSize (i.e. Base.HasLength(), or Base.HasShape{N}()) will simplify several other methods, which will be then optimized to work only based on the type of the object. In particular when the information is derivable from the type, there is no need to extend Base.isfinite.

Note

In the case that IteratorSize(Gr) == IsInfinite(), one should could Base.length(Gr) to be a "best effort", length of the group/monoid iterator. For practical reasons the largest object you could iterate over in your lifetime is of order that fits well into an Int ($2^{63}$ nanoseconds comes to 290 years).

Additional methods

Base.isfinite — Method
isfinite(M::Monoid)

Test whether monoid M is finite.

The default implementation is based on Base.IteratorSize. Only groups of returning Base.SizeUnknown() should extend this method.

source
GroupsCore.istrivial — Method
istrivial(M::Monoid)

Test whether monoid M is trivial.

The default implementation is based on isfinite and order.

source

Random elements

We provide two methods for generating random elements of a group or monoid.

GroupsCore.ProductReplacementSampler — Type
ProductReplacementSampler

Implements Product Replacement Algorithm for a group or monoid generated by an explicit finite set of generators.

Product Replacement Algorithm performs a random walk on the graph of n-generating tuples of a group (or monoid) with two accumulators. Each step consists of

  1. multiplying the right accumulator by a random generator,
  2. replacing one of the generators with the product with the right accumulator,
  3. multiplying the left accumulator (on the left) by a random generator.

The left accumulator is returned as a random element.

By default for a group with k generators we set n = 2k + 10 and perform 10*n scrambling steps before returning a random element.

PRASampler provides provably uniformly distributed random elements for finite groups. For infinite groups RandomWordSampler is used.

Warning

Using PRASampler for an infinite group is ill-advised as the exponential growth of words during scrambling will result in excessive memory use and out-of-memory situation.

source
GroupsCore.RandomWordSampler — Type
RandomWordSampler(S, distribution)

Return elements from a monoid represented by words of length in S, obeying distribution.

Usually for a monoid (group) S is a (symmetric) generating set.

distribution object must implement cdf(distribution, x::Float64)::Integer.

For finite monoids or groups when uniformity of results is needed ProductReplacementSampler should be used.

source

By default for finite monoids ProductReplacementSampler is used and RandomWordSampler following Poisson(λ=8) is employed for inifinite ones.