Opened 9 years ago

# Comparison of elements of the quotient group of a FreeGroup

Reported by: Owned by: ppurka joyner major sage-wishlist group theory vbraun N/A #12339

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

### comment:1 Changed 9 years ago by ppurka

• Description modified (diff)

### comment:2 Changed 8 years ago by mmarco

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

Note: See TracTickets for help on using tickets.