In 9.4 I have got the following incorrect output:
sage: G = PermutationGroup([[2,1,4,3,5],[2,3,4,5,1],[2,4,1,3,5]])
sage: G([1,3,5,4,2]).word_problem(G.gens())
x2^-1*x1^-1*x2*(x2*x1^-1)^2
[['(1,2,3,4,5)', -1], ['(1,2)(3,4)', -1], ['(1,2,3,4,5)', 1],
['((1,2,3,4,5)', 1], ['(1,2)(3,4)', 1]]
('x2^-1*x1^-1*x2*(x2*x1^-1)^2',
'(1,2,3,4,5)^-1*(1,2)(3,4)^-1*(1,2,3,4,5)*((1,2,3,4,5)*(1,2)(3,4)^-1)^2')
Note the 4th element in the output list has an additional bracket at the
front of the generator. This seems to come from the bracket in (x2*x1^-1),
and means that the output list does not give the right element of the
group. Further, note that if you define G without the third generator,
which doesn't appear in the word problem, this error does not occur
On Friday, October 4, 2019 at 9:46:24 PM UTC+1 c.ed...@gmail.com wrote:
> I think that's good, but it might be nice to include a minimal non-working
> example:
>
> Input
>
> > G = SymmetricGroup(4)
> > x = G("(1,2,3)")
> > x.word_problem([ x ], False)
>
> Produced output:
>
> > ('x2^-2*x1^-2*x2^-1*x1^-1', 'x2^-2*(1,2,3)^-2*x2^-1*(1,2,3)^-1')
>
> Expected output:
>
> > ('x1', '(1,2,3)')
>
> (certainly x can be written as a length-1 word using the generating set [
> x ]).
>
> Thanks!
>
>
> On Friday, October 4, 2019 at 12:37:53 PM UTC-6, Frédéric Chapoton wrote:
>>
>> I have made a proposal to fix the behaviour in the ticket
>>
>> https://trac.sagemath.org/ticket/28556
>>
>> Please review.
>>
>> Le vendredi 4 octobre 2019 20:23:31 UTC+2, Chase Meadors a écrit :
>>>
>>> Ah, your reply did let me understand how to get the result I actually
>>> want, and perhaps the docs should reflect this / include an example:
>>>
>>> Here is the problem one might want to solve:
>>> Suppose one has a permutation group G, and some element x in G.
>>> One wants to write x in terms of two other permutations y and z (y and z
>>> are arbitary; i.e. they have nothing to do with what Sage thinks G.gens()
>>> is), if possible.
>>>
>>> I had THOUGHT that one could do:
>>>
>>> x.word_problem([y, z])
>>>
>>> To get this result, but this does not work (but seems to be what the
>>> documentation implies).
>>> However, one can do:
>>>
>>> H = G.subgroup([y, z])
>>> H(x).word_problem(H.gens())
>>>
>>> And this does indeed give the correct result (i.e., an expression/word
>>> in y and z that evaluates to x in the group G).
>>>
>>> However, consider the documentation for word_problem:
>>>
>>> > word_problem(words, display=True)
>>> > G and H are permutation groups, g in G, H is a subgroup of G
>>> generated by a list (words) of elements of G. If g is in H, return the
>>> expression for g as a word in the elements of (words).
>>>
>>> I am interpreting "g" in this statement to be "self" (i.e., the element
>>> having word_problem called on it).
>>> As such, this definitely implies that I could solve my original problem
>>> using the first method above.
>>>
>>> So, right now I agree that the documentation is WRONG, but instead of
>>> changing the documentation I think that the method could actually be fixed
>>> so that the documentation is RIGHT.
>>> Sorry this is all a bit confusing!
>>>
>>> On Friday, October 4, 2019 at 11:56:43 AM UTC-6, David Joyner wrote:
>>>>
>>>>
>>>>
>>>> On Fri, Oct 4, 2019 at 1:03 PM Chase Meadors <c.e...@gmail.com> wrote:
>>>>
>>>>> Perhaps I misunderstand word_problem, but I thought that, given a list
>>>>> of group elements [g_1, ..., g_n] that generates a subgroup H, and x some
>>>>> element (hopefully!) in H, that,
>>>>>
>>>>> x.word_problem([ g_1, ..., g_n ])
>>>>>
>>>>
>>>> Is [g1,...,gn] = G.gens() ?
>>>>
>>>> Here's an example:
>>>>
>>>> sage: G = SymmetricGroup(6)
>>>> sage: g = G("(1,2,3,4)")
>>>> sage: Ggens = G.gens()
>>>> sage: g.word_problem(Ggens)
>>>> x1^-2*(x2*x1)^2*x2^-1
>>>> [['(1,2,3,4,5,6)', -2], ['((1,2)', 1], ['(1,2,3,4,5,6))', 2], ['(1,2)',
>>>> -1]]
>>>> ('x1^-2*(x2*x1)^2*x2^-1',
>>>> '(1,2,3,4,5,6)^-2*((1,2)*(1,2,3,4,5,6))^2*(1,2)^-1')
>>>>
>>>> For a more abbreviated output, use
>>>>
>>>> sage: g.word_problem(Ggens, False)
>>>> ('x1^-2*(x2*x1)^2*x2^-1',
>>>> '(1,2,3,4,5,6)^-2*((1,2)*(1,2,3,4,5,6))^2*(1,2)^-1')
>>>>
>>>> Now let's check this:
>>>>
>>>> sage: x1 = Ggens[0]
>>>> sage: x2 = Ggens[1]
>>>> sage: x1^-2*(x2*x1)^2*x2^-1
>>>> (1,2,3,4)
>>>>
>>>>
>>>>
>>>>> would result in an expression (word) for x in terms of the generators
>>>>> g_1, ..., g_n.
>>>>>
>>>>> So, for example, one would expect that x.word_problem([ x ]) would
>>>>> result in a length one word consisting just of x.
>>>>>
>>>>> Indeed, I can get this exact behavior using GAP directly (i.e. by
>>>>> using EpimorphismFromFreeGroup() and PreImagesRepresentative() directly),
>>>>> which makes me think there's a logical error in sage's implementation.
>>>>>
>>>>> Does this make sense, or am I just misunderstanding word_problem?
>>>>>
>>>>> On Friday, October 4, 2019 at 5:21:40 AM UTC-6, Dima Pasechnik wrote:
>>>>>>
>>>>>> On Fri, Oct 4, 2019 at 5:17 AM Chase Meadors <c.e...@gmail.com>
>>>>>> wrote:
>>>>>> >
>>>>>> > Hi! I'm trying to write permutation group elements in terms of a
>>>>>> given set of generators.
>>>>>> > However, the "word_problem" method appears to be giving me complete
>>>>>> nonsense.
>>>>>> >
>>>>>> > Output of version():
>>>>>> > 'SageMath version 8.8, Release Date: 2019-06-26'
>>>>>> >
>>>>>> > Not sure if this is relevant, but this is running in a docker image
>>>>>> based on sagemath/sagemath:8.8
>>>>>> >
>>>>>> > When I run the following code:
>>>>>> >
>>>>>> > G = SymmetricGroup(6)
>>>>>> > G('(1,2,3)').word_problem([ G('1,2,3') ], False)
>>>>>> >
>>>>>> > I get the output:
>>>>>> >
>>>>>> > ('x1^-1*x2^-1*x1*x2^-1', '()^-1*x2^-1*()*x2^-1')
>>>>>> >
>>>>>> > Which looks a lot like nonsense, unless I'm severely
>>>>>> misunderstanding how to use this function.
>>>>>>
>>>>>> The documentation for this function is indeed in need of improvement.
>>>>>> The following works, it seems:
>>>>>>
>>>>>> sage: G=SymmetricGroup(6)
>>>>>> sage: s=G('(1,2,3)')
>>>>>> sage: s.word_problem(G.gens(),False)
>>>>>> ('x1^-1*x2^-1*x1*x2^-1',
>>>>>> '(1,2,3,4,5,6)^-1*(1,2)^-1*(1,2,3,4,5,6)*(1,2)^-1')
>>>>>>
>>>>>> Is this what you're looking for?
>>>>>>
>>>>>> Anyhow, I've opened
>>>>>> https://trac.sagemath.org/ticket/28556
>>>>>>
>>>>>> to fix the docs on it.
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> > I think I've even identified the line with the error here:
>>>>>> https://github.com/sagemath/sage/blob/f0ae571d17e685258c1de89c2a29953f4d8fb302/src/sage/groups/perm_gps/permgroup_element.pyx#L1618
>>>>>>
>>>>>> (It believe it should be H, not G).
>>>>>> >
>>>>>> > Has anyone encountered this? I searched through here and it didn't
>>>>>> seem like this was a known issue, so perhaps I'm just missing something.
>>>>>> >
>>>>>> > Thanks!
>>>>>> >
>>>>>> > -- Chase
>>>>>> >
>>>>>> > --
>>>>>> > You received this message because you are subscribed to the Google
>>>>>> Groups "sage-devel" group.
>>>>>> > To unsubscribe from this group and stop receiving emails from it,
>>>>>> send an email to sage-...@googlegroups.com.
>>>>>> > To view this discussion on the web visit
>>>>>> https://groups.google.com/d/msgid/sage-devel/f48621bb-d462-4e17-aeea-3b82fc13459f%40googlegroups.com.
>>>>>>
>>>>>>
>>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "sage-devel" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>> an email to sage-...@googlegroups.com.
>>>>> To view this discussion on the web visit
>>>>> https://groups.google.com/d/msgid/sage-devel/7115fd14-812f-49dd-8c62-5d9ee6026ea3%40googlegroups.com
>>>>>
>>>>> <https://groups.google.com/d/msgid/sage-devel/7115fd14-812f-49dd-8c62-5d9ee6026ea3%40googlegroups.com?utm_medium=email&utm_source=footer>
>>>>> .
>>>>>
>>>>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-devel/a687e6e8-56bf-4951-acc4-22174f7ae2c2n%40googlegroups.com.
