# Add generator to a group? Combine generators of two groups?

Hi guys, I am wondering how to efficiently do the following two things in Sage

1. add a generator h to a existing group G to create a new group, e.g. from

sage: h = (3,4)
sage: G = PermutationGroup([(1,2),(1,3)])


how to get a new group N with generators [(1,2),(1,3),(3,4)].

I can do this by using G.gens() and adding (3,4) to the list and calling PermutationGroup(), but it looks awkward, is there a more efficient way?

2. create a new group from generators of two existing group, e.g. from

sage: G =  PermutationGroup([(1,2),(1,3)])
sage: H =  PermutationGroup([(3,4)])


how to get a new group N with generators [(1,2),(1,3),(3,4)]?

Currently I can do this by : N = PermutationGroup(G.gens()+H.gens())

Thanks, Kevin

edit retag close merge delete

Sort by » oldest newest most voted

Hello,

Most of the operations on permutations group are answered by the software GAP. So if you find something interesting in GAP it can be used for permutation groups! Some of it are already interfaced directly in Sage, but some not. For your problem, it seems that in GAP one can use ClosureGroupAddElm (for question 1) and ClosureGroup (for question 2). You can have a look at this page for more informations on these two functions. To use it from Sage just do

sage: G = SymmetricGroup(5)
sage: P1 = PermutationGroup([G('(1,2,3,4,5)')])
sage: P2 = PermutationGroup([G('(1,2)')])
sage: P_gap = gap.ClosureGroup(P1, P2)         # creates a GAP object
sage: P = PermutationGroup(gap_group=P_gap)    # converts it to a Sage object
sage: P
Permutation Group with generators [(1,2), (1,2,3,4,5)]


Though I am not sure it will be more efficient than what you suggest (and I am very curious about it!). It is quite possible that GAP has some optimization when doing this.

Vincent

more

Thank you Vincent, that's what I am looking for. I did the test to compare the speed, I did it first for small groups repeat 5000 times, then for large groups.

test on small groups repeat 5000 times.
Runing time for ClosureGroup(H,J) is 0:00:25.837925
Runing time for ClosureGroup(H,w) is 0:00:21.571264
Runing time for PermutationGroup(H.gens()+J.gens()) is 0:00:00.943834
Runing time for PermutationGroup(H.gens()+list(w)) is 0:00:00.810795

test on large groups only 1 time.
Runing time for ClosureGroup(H,J) is 0:01:09.245275
Runing time for ClosureGroup(H,w) is 0:01:10.550019
Runing time for PermutationGroup(H.gens()+J.gens()) is 0:00:00.001400
Runing time for PermutationGroup(H.gens()+list(w)) is 0:00:00.000649


Notes: 25.837925 means 25 seconds, 0:01:09.245275 means 1 minutes and 9 seconds. H and J are groups, w is a generator of a group, somehow PermutationGroup(H.gens()+J.gens()) is way faster than ClosureGroup, maybe ClosureGroup is doing some extra validation or computation?

Here is the python/sage code:

from sage.all import *
from datetime import datetime

case = 'small'
#case = 'large'

if case == 'small':
H = PermutationGroup([(2,3),(4,5)])
J = PermutationGroup([(1,2),(3,4,5)])
W = PermutationGroup([(1,4)])
w = W.gen(0)
iteration = 5000
print 'test on small groups repeat {0} times.'.format(iteration)
elif case == 'large':
H = CyclicPermutationGroup(200)
J = AlternatingGroup(200)
W = AlternatingGroup(200)
#J = DihedralGroup(10000)
#W = DihedralGroup(10000)
w = W.gen(1)
iteration = 1
print 'test on large groups only {0} time.'.format(iteration)

start = datetime.now()
for i in range(iteration):
P1_gap = gap.ClosureGroup(H,J)  # close two group
P1 = PermutationGroup(gap_group=P1_gap)
print 'Runing time for ClosureGroup(H,J) is {0}'.format(str(datetime.now() - start))

start = datetime.now()
for i in range(iteration):
P2_gap = gap.ClosureGroup(H,w)  # close one group with one generator
P2 = PermutationGroup(gap_group=P2_gap)
print 'Runing time for ClosureGroup(H,w) is {0}'.format(str(datetime.now() - start))

start = datetime.now()
for i in range(iteration):
P3 = PermutationGroup(H.gens()+J.gens())
print 'Runing time for PermutationGroup(H.gens()+J.gens()) is {0}'.format(str(datetime.now() - start))

start = datetime.now()
for i in range(iteration):
P4 = PermutationGroup(H.gens()+list(w))
print 'Runing time for PermutationGroup(H.gens()+list(w)) is {0}'.format(str(datetime.now() - start))

more

Indeed, this is a very huge difference in timings. Actually, most of the time is spent in the interface between Sage and GAP. You can see that by using %prun as in

sage: %prun my_function()


some documentation is here