Comparison of elements of the quotient group of a FreeGroup

[ppurka]

The following never finishes.

F.<x,y> = FreeGroup()
H = F.quotient([x^2*y^-3])
L = H(y*x)
R = H(x*y)
L == R

Another example with a segmentation fault.

F.<x,y> = FreeGroup()
r = x^2*y^-3
H = F.quotient([r])
H(r) == H.one_element()

Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
   File "_sage_input_3.py", line 10, in <module>
     exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8  
-*-\\n" +  
_support_.preparse_worksheet_cell(base64.b64decode("Ri48eCx5PiA9IEZyZWVHcm91cCgpCnIgPSB4XjIqeV4tMwpIID0gRi5xdW90aWVudChbcl0pCnRpbWVpdCgiSChyKSA9PSBILm9uZV9lbGVtZW50KCkiKQ=="),globals())+"\\n");  
execfile(os.path.abspath("___code___.py"))
   File "", line 1, in <module>

   File "/tmp/tmpjvXomU/___code___.py", line 6, in <module>
     exec compile(u'timeit("H(r) == H.one_element()")
   File "", line 1, in <module>

   File "sage_timeit_class.pyx", line 114, in  
sage.misc.sage_timeit_class.SageTimeit.__call__  
(sage/misc/sage_timeit_class.c:931)
   File "sage_timeit_class.pyx", line 78, in  
sage.misc.sage_timeit_class.SageTimeit.eval  
(sage/misc/sage_timeit_class.c:731)
   File  
"/usr/local/src/sage/sage-5.6.rc1.server/local/lib/python2.7/site-packages/sage/misc/sage_timeit.py",  
line 236, in sage_timeit
     if timer.timeit(number) >= 0.2:
   File  
"/usr/local/src/sage/sage-5.6.rc1.server/local/lib/python/timeit.py", line  
195, in timeit
     timing = self.inner(it, self.timer)
   File "<magic-timeit>", line 6, in inner
   File "libgap_wrapper.pyx", line 492, in  
sage.groups.libgap_wrapper.ElementLibGAP.__richcmp__  
(sage/groups/libgap_wrapper.c:4013)
   File "element.pyx", line 876, in sage.structure.element.Element._richcmp  
(sage/structure/element.c:8426)
   File "element.pyx", line 923, in  
sage.structure.element.Element._richcmp_c_impl  
(sage/structure/element.c:8727)
   File "libgap_wrapper.pyx", line 483, in  
sage.groups.libgap_wrapper.ElementLibGAP._cmp_c_impl  
(sage/groups/libgap_wrapper.c:3957)
   File "element.pyx", line 913, in sage.structure.element.Element.__cmp__  
(sage/structure/element.c:8597)
   File "element.pyx", line 826, in sage.structure.element.Element._cmp  
(sage/structure/element.c:7601)
   File "element.pyx", line 539, in  
sage.libs.gap.element.GapElement._cmp_c_impl (sage/libs/gap/element.c:4484)
ValueError: libGAP: cannot compare: Segmentation fault

Depends on #12339

CC: @vbraun

Component: group theory

Issue created by migration from https://trac.sagemath.org/ticket/14025

[ppurka]

Description changed:

--- 
+++ 
@@ -7,3 +7,58 @@
 R = H(x*y)
 L == R

+Another example with a segmentation fault. + +``` +F.<x,y> = FreeGroup() +r = x^2*y^-3 +H = F.quotient([r]) +H(r) == H.one_element() + +Traceback (most recent call last):

• File "", line 1, in
• File "_sage_input_3.py", line 10, in
• exec compile(u'open("code.py","w").write("# -- coding: utf-8
  +--\n" +
  +support.preparse_worksheet_cell(base64.b64decode("Ri48eCx5PiA9IEZyZWVHcm91cCgpCnIgPSB4XjIqeV4tMwpIID0gRi5xdW90aWVudChbcl0pCnRpbWVpdCgiSChyKSA9PSBILm9uZV9lbGVtZW50KCkiKQ=="),globals())+"\n");
  +execfile(os.path.abspath("code.py"))
• File "", line 1, in
• File "/tmp/tmpjvXomU/code.py", line 6, in
• exec compile(u'timeit("H(r) == H.one_element()")
• File "", line 1, in
• File "sage_timeit_class.pyx", line 114, in
  +sage.misc.sage_timeit_class.SageTimeit.call
  +(sage/misc/sage_timeit_class.c:931)
• File "sage_timeit_class.pyx", line 78, in
  +sage.misc.sage_timeit_class.SageTimeit.eval
  +(sage/misc/sage_timeit_class.c:731)
• File
  +"/usr/local/src/sage/sage-5.6.rc1.server/local/lib/python2.7/site-packages/sage/misc/sage_timeit.py",
  +line 236, in sage_timeit
• if timer.timeit(number) >= 0.2:
• File
  +"/usr/local/src/sage/sage-5.6.rc1.server/local/lib/python/timeit.py", line
  +195, in timeit
• timing = self.inner(it, self.timer)
• File "", line 6, in inner
• File "libgap_wrapper.pyx", line 492, in
  +sage.groups.libgap_wrapper.ElementLibGAP.richcmp
  +(sage/groups/libgap_wrapper.c:4013)
• File "element.pyx", line 876, in sage.structure.element.Element._richcmp
  +(sage/structure/element.c:8426)
• File "element.pyx", line 923, in
  +sage.structure.element.Element._richcmp_c_impl
  +(sage/structure/element.c:8727)
• File "libgap_wrapper.pyx", line 483, in
  +sage.groups.libgap_wrapper.ElementLibGAP._cmp_c_impl
  +(sage/groups/libgap_wrapper.c:3957)
• File "element.pyx", line 913, in sage.structure.element.Element.cmp
  +(sage/structure/element.c:8597)
• File "element.pyx", line 826, in sage.structure.element.Element._cmp
  +(sage/structure/element.c:7601)
• File "element.pyx", line 539, in
  +sage.libs.gap.element.GapElement._cmp_c_impl (sage/libs/gap/element.c:4484) +ValueError: libGAP: cannot compare: Segmentation fault +```

[miguelmarco]

comment:2

In general, that is an undecidable problem, so it is not surprising that we don't get an answer.

In some cases there are some things that could be done, like trying to get a normal form (by using rewriting systems, or automatic structures), or symmetric representations (if the group is finite). But again, these methods will only work for some groups, and in general we cannot know in advance if they will work for a given group, so it is not advisable to implement these methods as a general way to compare words. We will have to live with the fact that finitely presented groups present this kind of undecidable problems.

When/if we get kbmag to work under libgap, we could be able to compute automatic structures for FP groups, which would work in this particular example (but not in general).