Ask Your Question
1

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

asked 2015-04-18 22:50:47 +0100

skylibrary gravatar image

updated 2015-04-20 11:47:41 +0100

slelievre gravatar image

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
0

answered 2015-04-19 23:43:26 +0100

vdelecroix gravatar image

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

edit flag offensive delete link more
0

answered 2015-04-20 23:35:16 +0100

skylibrary gravatar image

updated 2015-04-20 23:39:30 +0100

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))
edit flag offensive delete link more

Comments

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

vdelecroix gravatar imagevdelecroix ( 2015-04-21 15:24:22 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-04-18 22:50:47 +0100

Seen: 939 times

Last updated: Apr 20 '15