On 10 November 2016 at 10:37, Martin Baker <ax87...@martinb.com> wrote:
> Hi Kurt, > > > Your "GroupPresentation" actually isn't a group, so I wonder whether it > wouldn't > > be favourable to implement a domain, e.g. "FinitelyPresentedGroup" which > could > > be reused elsewhere. If you take on the burden to augment some group > theory to > > Fricas anyway, you might consider doing it along the lines of GAP: > > http://www.gap-system.org/Manuals/doc/ref/chap47.html > > > > (1) -> GroupPresentation has Group > > > > (1) false > > Well in Fricas terms PermutationGroup isnt a group either: > > (1) -> PermutationGroup(Integer) has Group > > (1) false > Type: Boolean > > I'm surprised, indeed :( I had a look in permgrps.spad where we find the explanation: <https://github.com/hemmecke/fricas/blob/master-hemmecke/src/algebra//permgrps.spad#L1> -- PermutationGroup implements permutation groups acting on a set S, i.e. all subgroups of the symmetric group of S, represented as a list of permutations (generators). Note that therefore the objects are not members of the Language category *Group* <http://fricas.github.io/api/Group.html#l-group>. Using the idea of base and strong generators by Sims, basic routines and algorithms are implemented so that the word problem for permutation groups can be solved. -- > Hopefully they are all equivalent for *finite* groups, that is, the round > trip: > PermutationGroup -> GroupPresentation -> PermutationGroup > and > GroupPresentation -> PermutationGroup -> GroupPresentation > may not get back to exactly the same place but it gets back to somewhere > isomorphic to where it started. > > This shouldn't be a problem. > The problem seems to be simplifying the relations, the simplest case may > not be computable? > Yes, unfortunately not. The GAP manual tells us: -- The method employed by *GAP* for such an equality test use the underlying finitely presented group. First (unless this group is known to be infinite) *GAP* tries to find a faithful permutation representation by a bounded Todd-Coxeter. If this fails, a Knuth-Bendix (see 52.6 <http://www.gap-system.org/Manuals/doc/ref/chap52.html#X87693BDC79DC6EBF>) is attempted and the words are compared via their normal form. -- K-B is semi-decidable > > I have added a coercion from PermutationGroup to GroupPresentation to > permgrps.spad here: > https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps.spad > (relies on above patch) > > This was not hard and it works fine: > > permgp := dihedralGroup(3)$PermutationGroupExamples > > (1) <(1 2 3),(1 3)> > Type: PermutationGroup(Integer) > permgp::GroupPresentation > > That's fine. If you can also provide the reverse direction it will be a useful tool. > (2) > <a b | > a*a*a, a*a*b*a*a*b, a*a*b*a*a*-b, a*b*a*b, a*b*a*-b, b*b, > a*a*b*-a*b > , > a*b*-a*-a*b, b*a*a*-b*-a, a*a*b*-a*-b, a*a*-b*a*a*-b, a*-b*a*-b > > > Type: GroupPresentation > > The problem, as you can see, is that it does not produce a simplest or > canonical solution (if such a thing exists). That is there are redundant > relations. > That's unavoidable unless you can find a confluent (and terminating) rewriting system. The K-B completion algorithm also depends on the reduction ordering used, so it's getting complicated very fast. GAP has the same problems: -- gap> a*b = b*a; falsegap> (b^2*a*b)^2 = a^0; true Such calculations comparing elements of an FpGroup may run into problems: There exist finitely presented groups for which no algorithm exists (it is known that no such algorithm can exist) that will tell for two arbitrary words in the generators whether the corresponding elements in the FpGroup are equal. Therefore the methods used by *GAP* to compute in finitely presented groups may run into warning errors, run out of memory or run forever. If the FpGroup is (by theory) known to be finite the algorithms are guaranteed to terminate (if there is sufficient memory available), but the time needed for the calculation cannot be bounded a priori. See 47.6 <http://www.gap-system.org/Manuals/doc/ref/chap47.html#X7BD0CEBA7B225416> and 47.16 <http://www.gap-system.org/Manuals/doc/ref/chap47.html#X86C43E3B81ED25DC>. -- https://en.wikipedia.org/wiki/Confluence_(abstract_rewriting) > > In the above example it is probably easy to see extra rules that would > simplify to a minimal solution but I cant see a general strategy for > reduction rules even for very simple cases like this. > > Going in the opposite direction it is easy to implement Todd-Coxeter, the > problem again is simplifying the resulting permutations. > > I am planning (already started as you can see) to implement two-way > conversions between these 'group like' structures. > I'm definitely encouraging you to implement T-C. Then we will rely on (permgrps.spad): "Using the idea of base and strong generators by Sims, basic routines and algorithms are implemented so that the word problem for permutation groups can be solved." > > Martin B > > > -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel+unsubscr...@googlegroups.com. To post to this group, send email to fricas-devel@googlegroups.com. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
