Opened 9 years ago

Last modified 8 years ago

#14025 new defect

Comparison of elements of the quotient group of a FreeGroup

Reported by: ppurka Owned by: joyner
Priority: major Milestone: sage-wishlist
Component: group theory Keywords:
Cc: vbraun Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12339 Stopgaps:

Status badges

Description (last modified by 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

Change History (2)

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.