In this domain we want to represent finitely generated group presentations, that is, groups represented by their generators and relations.
The code is avialible on Github here.
My motivation is to represent homotopy group such as fundamental group. For more documentation see page here.
The domain representation holds the group as a pair:
- a set of generators
- and a set of relations
Rep := Record(gens:PrimitiveArray(NNI),rels: List(List(Integer))) |
Which is shown like this: <A,B | A , B>
- Each generator is a NNI
- Each relation is a list of indexes to generators. Negative values indicate
the inverse of the generator. So if '1' represents the generator 'A' then
'-1' represents its inverse 'A-1'
Working with Group Presentations
Finitely presented group presentations are difficult to work with:
- It is not, in general, algorithmically computable into other representations of a group.
- We cannot determine if this is the simplest representation or determine if two such groups are isomophic (their corresponding simplicial complexes are homeomorphic).
We can therefore compute 'a' (not 'the') homotopy group for a given simplicial complex. We may also be able to apply some simplifications to this group.
Despite these fundamental limits on what is theoretically possible I still believe it is worthwhile to have the capability to generate 'a' homotopy group for a given structure.
Simplify
There may not be a simplest form but it is possible to do some simplifications.
In order to try to simplify a finitely generated presentation to produce simpler but isomorphic groups we can apply certain transformations or automorphisms (isomorphisms of the group back to itself).
For example:
- remove all zero terms in rules
- if a rule consists of a single generator then remove that generator
- if a rule consists of a pair of generators then make the second generator the inverse of the first
- if a generator is adjacent to its inverse then cancel them out.
- remove duplicate rules.
These automorphisms were studied and categorised by Tietze and Nielsen.
Tietze Transformations
Tietze transformations are of 4 kinds:
Kind | Examples | |
---|---|---|
T1 | Add a relation | < A | A3 >->< A | A3 , A6 > |
T2 | Remove a relation | for example we can reverse the above < A | A3 , A6>->< A | A3> |
T3 | Add a generator | < A | A3 >-><A , B | A3, B = A2 > |
T4 | Remove a generator | for example we can reverse the above <A , B | A3, B = A2 >->< A | A3 > |
We are interested in simplifying so we are mostly interested in T2 and T4.
T2
T2 allows us to remove a relation but not generators. This happens when a rule is redundant, that is it contains no additional information than is already contained in the other rules.
This happens, for example, where:
One rule is a multiple of another - In this case we can remove the highest multiple but not the lowest.
One rule is the inverse of another - In this case we can remove any one, but not both of these rules.
We can also simplify rules, for example, where an element and its inverse are next to each other they can be cancelled out and removed.
T4
T4 allows us to remove a generator and corresponding rules.
Nielsen Transformations
The following transformations on a finitely generated free group produce isomorphic groups.
- Switch A and B
- Cyclically permute A, B, … to B, …, A.
- Replace A with A-1 : That is invert any element.
- Replace A with A*B
Group domains in FriCAS
Subject: Re: [fricas-devel] Group domains in FriCAS To: fricas-devel@googlegroups.com Date: Wed, 7 Dec 2016 02:01:20 +0100 (CET) From: Waldek Hebisch About your proposal: note that notion of permutation group is closely related to notion of subgroup (and at categorical level with final object of a category). Finitely presented groups are related to quotients (and first object of a category). As a little remark note that in both cases we natuarally get semigroup first, in case of permutations semigroup of all mappings from a set to itself, in case of free group we get free semigroup. Then we "correct" deficiency, in case of permutations taking subsemigroup of invertible maps, in case of free group taking quotient (declaring some generators of free semigroup as inverses of group generators). Now, one natural thing would be a way to produce group given group presentation. There is very strong obstacle to this due to unsolvability of word problem. IMO the right way to go forward it to look at cases when word problem is solvable. This happens if we know something special about groups, for example for abelian groups word problem is solvable. This happens if presentation has special form, like for result of Knuth-Bendix completition. We could try postpone solving hard problems and require that to create finitely presented group the user has to provide solver for word problem Concerning structure on Type: currently this is done by declaring specific categories/domains. Union represets /implements sum. There is Product domain. There is Subdomian. Each are very special I do not see how to "generalize" them at computational level. In principle we could try to add "quotient" constructor. Namely, to get quotient we need equvalence relation and we could have something like: Quitient(S : Type, = : (S, S) -> Boolean) : .... but that would be of limited use, because for products there are important features which are preserved, while for quotients everything depends on equivalence relation. Existing algebra cheats in some cases, uncoditionaly declaring features which are valid only if special conditions are satisfied. For quotient I do not think cheats are appropriate -- we can not even claim that features are preserved "in most interesting cases". And I would like to get rid of cheating. Orbits need extra structure for example semigroup structure. Orbits of group actions have specific properties, so they probably should be studied separately from more general notions of orbits. And efficient computations with orbits are possible only in some specific situations. So no, I think that currently it is not possible to put more _useful_ general structure on Type. |