[sage-devel] Re: Shortest expressions in permutation groups with generators
On Friday, 19 June 2015 11:35:36 UTC+1, Christian Stump wrote: the reason must be efficiency. E.g. for permutation groups one would work with a strong generating set S, rather than the original generators; expressing an element in terms of S is very quick, and then you hold expressions for each element of S in terms of the original generators (which need not be the shortest one); so you get some kind of expression quite quickly. I agree, but I still wonder why gap is not providing also an algorithm along the Cayley graph. Or would you expect that to be slower than the algorithm used in `Factorization` ? yes, sure, this would be slow. What sizes of groups are you talking about? GAP has functions to investigate the group grows: GrowthFunctionOfGroup( G, radius ) which are fast; e.g. gap GrowthFunctionOfGroup(PSL(3,101),5); is kind of instant... So it would be natural to extend GAP here. But even if it were, it wouldn't need to ruin through the complete group for elements that are close to the identity in the Cayley graph (i.e., which have short reduced factorizations). Since this means that there is no algorithm available for big groups, it might be nice to have that in sage by adding the naive algorithm to the perm_grp element class, don't you think so? -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Shortest expressions in permutation groups with generators
the reason must be efficiency. E.g. for permutation groups one would work with a strong generating set S, rather than the original generators; expressing an element in terms of S is very quick, and then you hold expressions for each element of S in terms of the original generators (which need not be the shortest one); so you get some kind of expression quite quickly. I agree, but I still wonder why gap is not providing also an algorithm along the Cayley graph. Or would you expect that to be slower than the algorithm used in `Factorization` ? But even if it were, it wouldn't need to run through the complete group for elements that are close to the identity in the Cayley graph (i.e., which have short reduced factorizations). Since this means that there is no algorithm available for big groups, it might be nice to have that in sage by adding the naive algorithm to the perm_grp element class, don't you think so? -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Shortest expressions in permutation groups with generators
GAP4 has 39.5-2 Factorization ( http://www.gap-system.org/Manuals/doc/ref/chap39.html) calling GAP from Sage is not hard... Thanks for your reply -- but I am still a little puzzled: gap has two algorithms to compute a word in generators. This one, and the one implemented in `word_problem` using the gap commands `EpimorphismFromFreeGroup` and `PreImagesRepresentative`. The first ensures the word to be reduced by iterating through the complete group, while the second does not necessarily provide a reduced word. Is there any reason for not travelling the group along the Cayley graph with the given set of generators, and returning a word once the element it found in this graph, without expanding the complete group? -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Shortest expressions in permutation groups with generators
On Friday, 19 June 2015 09:02:49 UTC+1, Christian Stump wrote: GAP4 has 39.5-2 Factorization ( http://www.gap-system.org/Manuals/doc/ref/chap39.html) calling GAP from Sage is not hard... Thanks for your reply -- but I am still a little puzzled: gap has two algorithms to compute a word in generators. This one, and the one implemented in `word_problem` using the gap commands `EpimorphismFromFreeGroup` and `PreImagesRepresentative`. The first ensures the word to be reduced by iterating through the complete group, while the second does not necessarily provide a reduced word. Is there any reason for not travelling the group along the Cayley graph with the given set of generators, and returning a word once the element it found in this graph, without expanding the complete group? the reason must be efficiency. E.g. for permutation groups one would work with a strong generating set S, rather than the original generators; expressing an element in terms of S is very quick, and then you hold expressions for each element of S in terms of the original generators (which need not be the shortest one); so you get some kind of expression quite quickly. -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: Shortest expressions in permutation groups with generators
GAP4 has 39.5-2 Factorization (http://www.gap-system.org/Manuals/doc/ref/chap39.html) calling GAP from Sage is not hard... On Tuesday, 16 June 2015 17:02:35 UTC+1, Christian Stump wrote: Hi there, I wasn't able to find the following functionality: Let W = PermutationGroup(gens) be a permutation group and let w in W. Find a *shortest* expression as a group of w as a word in gens and their inverses. w.word_problem() finds a word, but this has not necessarily the shortest possible length. In GAP3 there was such a functionality which I currently use. * Is there already such functionality in Sage (and I was simply ignorant)? * Does anyone know how to achieve this using Sage and GAP4? * Should I open a ticket and provide GAP3 code for this functionality for permutation groups? Thanks! Christian -- 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 post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
