Improving Permutation Groups in Sage
- PDL C-401 Fridays 3:30 -- 5:30 is reserved just for us!
- all invited to Sage status reports, Wednesdays 3:30 -- 5:30 across the hall from Parnassus.
Existing Code
- To get the Sage source, just download and install sage. The relevant files are in SAGE_ROOT/devel/sage-main/sage/groups/perm_gps.
- Easiest way to look at the GAP source: download the Sage source tarball, and extract (tar -xvf) SAGE_ROOT/spkg/standard/gap-4.4.12.p1.spkg. The relevant files to look at include:
- gap-4.4.12.p1/src/lib/gpprmsya.gi
- gap-4.4.12.p1/src/lib/grpperm.gi
- gap-4.4.12.p1/src/pkg/guava3.9/src/leon/src/chbase.c
- gap-4.4.12.p1/src/pkg/guava3.9/src/leon/src/permgrp.c
- gap-4.4.12.p1/src/pkg/guava3.9/src/leon/src/randschr.c
- gap-4.4.12.p1/src/pkg/guava3.9/src/leon/src/stcs.c
Goals
Goal 1: Order, membership testing, and element enumeration
The algorithm for doing this was (almost) first described in section 4 of Charles Sims' 1970 paper, *Computational methods for permutation groups*. It is based on Schreier's Lemma and is thus called the Schreier-Sims method.
Definitions of base and strong generating set.
Knuth's article with specific recommendations about data structures and algorithmic specifics. Sage implementation of this article:
def check_perm(perm, n):
if len(perm) != n+1 or sorted(perm) != range(n+1):
raise RuntimeError("Incorrect format for perm.")
def invert_perm(perm):
# checks
check_perm(perm, len(perm)-1)
# work
L = [None]*len(perm)
for i in range(len(perm)):
L[perm[i]] = i
return L
def multiply_perms(perm1, perm2):
# checks
assert len(perm1) == len(perm2)
n = len(perm1)-1
check_perm(perm1, n)
check_perm(perm2, n)
# work
return [perm1[perm2[i]] for i in range(n+1)]
class StabChainKnuth:
def __init__(self, n):
# checks
n = Integer(n)
assert n >= 1
# work
self.degree = n
self.sigmas = [None]
self.T = [None]
for i in range(1,n+1):
self.sigmas.append([None]*i + [range(n+1)])
self.T.append( [range(n+1)] )
# Sigma(k) == [a for a in self.sigmas[k] if a is not None]
def sigma(self, k, j):
# checks
k = Integer(k); j = Integer(j)
assert self.degree >= k and k >= j and j >= 1
# work
return self.sigmas[k][j]
def contained(self, perm, k):
# checks
k = Integer(k); assert self.degree >= k and k >= 1
check_perm(perm, self.degree)
# work
for i in range(k+1,self.degree+1):
if perm[i] != i:
return False
j = perm[k]
sigma_k_j = self.sigma(k, j)
if sigma_k_j is None:
return False
if k == 1:
return True
perm = multiply_perms(invert_perm(sigma_k_j),perm)
return self.contained(perm, k-1)
def A_k(self, perm, k):
# checks
k = Integer(k); assert self.degree >= k and k >= 1
check_perm(perm, self.degree)
for i in range(k+1,self.degree+1):
assert perm[i] == i, 'must be in S_k'
assert not self.contained(perm, k)
# A1
self.T[k].append(perm)
# A2
current_Sigma_k = []
for sigma in self.sigmas[k]:
if sigma is not None:
current_Sigma_k.append(sigma)
for sigma in current_Sigma_k:
self.B_k(multiply_perms(perm, sigma), k)
def B_k(self, perm, k):
# checks
k = Integer(k); assert self.degree >= k and k >= 1
check_perm(perm, self.degree)
for i in range(k+1,self.degree+1):
assert perm[i] == i, 'must be in S_k'
# B1
j = perm[k]
# B2
sigma_k_j = self.sigma(k, j)
if sigma_k_j is None:
self.sigmas[k][j] = copy(perm)
current_T_k = copy(self.T[k])
for tau in current_T_k:
self.B_k(multiply_perms(tau, perm), k)
return
# B3
perm = multiply_perms(invert_perm(sigma_k_j),perm)
if self.contained(perm, k-1):
return
# B4
self.A_k(perm, k-1)
def order(self, k):
# checks
k = Integer(k); assert self.degree >= k and k >= 1
# work
return prod(len([b for b in a if b is not None]) for a in self.sigmas[1:k+1])
def members(self, k):
# checks
k = Integer(k); assert self.degree >= k and k >= 1
# work
if k == 1:
yield range(self.degree+1)
else:
for perm in self.members(k-1):
for sigma in self.sigmas[k]:
if sigma is not None:
yield multiply_perms(sigma, perm)
def random_element(self, k):
# checks
k = Integer(k); assert self.degree >= k and k >= 1
# work
if k == 1:
return range(self.degree+1)
perm = self.random_element(k-1)
sig_sigmas = [a for a in self.sigmas[k] if a is not None]
sigma = randint(0,len(sig_sigmas)-1)
sigma = sig_sigmas[sigma]
return multiply_perms(sigma, perm)example usage:
sage: S = StabChainKnuth(3) sage: for a in S.sigmas: ... print a None [None, [0, 1, 2, 3]] [None, None, [0, 1, 2, 3]] [None, None, None, [0, 1, 2, 3]] sage: S.T[1:] [[[0, 1, 2, 3]], [[0, 1, 2, 3]], [[0, 1, 2, 3]]] sage: print S.order(1) sage: print S.order(2) sage: print S.order(3) 1 1 1 sage: print list(S.members(1)) sage: print list(S.members(2)) sage: print list(S.members(3)) [[0, 1, 2, 3]] [[0, 1, 2, 3]] [[0, 1, 2, 3]] sage: S.A_k([0,2,1,3], 1) Traceback (most recent call last): ... AssertionError: must be in S_k sage: S.A_k([0,2,1,3], 2) sage: for a in S.sigmas: ... print a None [None, [0, 1, 2, 3]] [None, [0, 2, 1, 3], [0, 1, 2, 3]] [None, None, None, [0, 1, 2, 3]] sage: S.T[1:] [[[0, 1, 2, 3]], [[0, 1, 2, 3], [0, 2, 1, 3]], [[0, 1, 2, 3]]] sage: print S.order(1) sage: print S.order(2) sage: print S.order(3) 1 2 2 sage: print list(S.members(1)) sage: print list(S.members(2)) sage: print list(S.members(3)) [[0, 1, 2, 3]] [[0, 2, 1, 3], [0, 1, 2, 3]] [[0, 2, 1, 3], [0, 1, 2, 3]] sage: S.A_k([0,2,3,1], 3) sage: for a in S.sigmas: ... print a None [None, [0, 1, 2, 3]] [None, [0, 2, 1, 3], [0, 1, 2, 3]] [None, [0, 2, 3, 1], [0, 3, 1, 2], [0, 1, 2, 3]] sage: S.T[1:] [[[0, 1, 2, 3]], [[0, 1, 2, 3], [0, 2, 1, 3]], [[0, 1, 2, 3], [0, 2, 3, 1]]] sage: print S.order(1) sage: print S.order(2) sage: print S.order(3) 1 2 6 sage: print list(S.members(1)) sage: print list(S.members(2)) sage: print list(S.members(3)) [[0, 1, 2, 3]] [[0, 2, 1, 3], [0, 1, 2, 3]] [[0, 3, 2, 1], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 1, 2, 3]] sage: for _ in range(10): ... perm = S.random_element(2) ... print perm, S.contained(perm, 2), S.contained(perm, 3) [0, 1, 2, 3] True True [0, 2, 1, 3] True True [0, 1, 2, 3] True True [0, 2, 1, 3] True True [0, 2, 1, 3] True True [0, 2, 1, 3] True True [0, 1, 2, 3] True True [0, 1, 2, 3] True True [0, 1, 2, 3] True True [0, 2, 1, 3] True True sage: for _ in range(10): ... perm = S.random_element(3) ... print perm, S.contained(perm, 3), S.contained(perm, 2) [0, 2, 3, 1] True False [0, 3, 1, 2] True False [0, 1, 2, 3] True True [0, 2, 1, 3] True True [0, 1, 2, 3] True True [0, 2, 3, 1] True False [0, 1, 2, 3] True True [0, 1, 3, 2] True False [0, 3, 2, 1] True False [0, 3, 1, 2] True False
Tom Boothby's implementation of deterministic shallow Schreier trees:
Note, this works on permutations which support multiplication, inversion, and evaluation. Like the Sage ones.
def cube_orbit(cube,k,a,oorb):
parents = {a:None}
labels = {a:0}
print cube
walk = [(-j,cube[-j]) for j in range(k,0,-1)]
walk+= [( j,cube[ j]) for j in range(1,k+1)]
orb = [a]
new = {}
for j,g in walk:
norb = []
for b in orb:
c = g(b)
if parents.has_key(c):
continue
norb.append((b,c))
for b,c in norb:
parents[c] = b
labels[c] = j
orb.append(c)
if not oorb.has_key(c):
new[c] = True
return parents,labels,new.keys()
def shallowtree(S,a,n):
k = 1
s = S[0]
cube = {0:s*~s, 1:~s, -1:s}
def search(new):
for s in S:
for n in new:
if not parents.has_key(s(n)):
return n,s
return None
parents,labels,new = cube_orbit(cube,k,a,{a:True})
found = search(new)
while found is not None:
gammai, ui = found
g = cube[labels[gammai]]
cur = parents[gammai]
while cur is not None:
g *= cube[labels[cur]]
cur = parents[cur]
gi = g*ui
print gi
k+=1
cube[-k] = gi
cube[k] = ~gi
parents,labels,new = cube_orbit(cube,k,a,parents)
found = search(new)
return parents,labels,cubeExample:
Sn = SymmetricGroup(12) S = [Sn((1,2,3,4,5,6,7,8,9,10,11,12)),Sn((1,2))] par,lab,cub = shallowtree(S,1,12)
Tickets, discussions or links which are relevant:
Goal 2: Partition refinement
This consists of tying the partition refinement code already in Sage into the permutation group functionality. This will allow for partition refinement traversals in proper subgroups of S_n. Applications include
- group intersection
- stabilizers
- element normalizers
- conjugacy
- group isomorphism
- and others
Goal 3: Remove as much GAP dependence as possible
The previous two goals will make this goal tenable.
Goal 4: Subgroup Normalizers
This is an NP complete problem, which is strictly harder than the problems in Goal 2.