SymmetricGroup.word_problem returns incorrect result

[Chase Meadors]

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.

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

[Dima Pasechnik]

On Fri, Oct 4, 2019 at 5:17 AM Chase Meadors <c.ed...@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-devel+...@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.

[Chase Meadors]

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

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:

> To unsubscribe from this group and stop receiving emails from it, send an email to sage-...@googlegroups.com.

[David Joyner]

On Fri, Oct 4, 2019 at 1:03 PM Chase Meadors <c.ed...@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)

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@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.

[Chase Meadors]

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:

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/7115fd14-812f-49dd-8c62-5d9ee6026ea3%40googlegroups.com.

[Frédéric Chapoton]

I have made a proposal to fix the behaviour in the ticket 

https://trac.sagemath.org/ticket/28556

Please review.

[Chase Meadors]

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!

[Linden Disney]

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