Sharedenumerate_permutation_triples.sageOpen in CoCalc
Author: Michael Musty
Views : 11
1
# simultaneous conjugation (isomorphism)
2
def is_isomorphic(sigma, tau, get_element=False):
3
G = sigma[0].parent()
4
Gtau = tau[0].parent()
5
assert(G==Gtau)
6
S = SymmetricGroup(G.degree())
7
g = libgap.RepresentativeAction(S, sigma, tau, libgap.OnTuples)
8
try:
9
g = S(g)
10
assert(g^-1*sigma[0]*g == tau[0])
11
assert(g^-1*sigma[1]*g == tau[1])
12
assert(g^-1*sigma[2]*g == tau[2])
13
if get_element:
14
return True, g
15
else:
16
return True
17
except TypeError:
18
return False
19
20
# S3 action
21
def S3_action(g, sigma):
22
sigmap = [sigma[g(i)-1] for i in [1,2,3]]
23
if sign(g) == -1:
24
sigmap = [s^-1 for s in sigmap]
25
G = sigmap[0].parent()
26
assert(sigmap[2]*sigmap[1]*sigmap[0] == G.identity())
27
return sigmap
28
29
# lax isomorphism
30
def is_lax(sigma, tau, get_element=False):
31
for g in SymmetricGroup(3):
32
sigmap = S3_action(g, sigma)
33
if is_isomorphic(sigmap, tau):
34
if get_element:
35
return True, g
36
else:
37
return True
38
return False
39
40
# sort representatives by partition
41
def sort_reps(reps):
42
parts = [a.cycle_type() for a in reps]
43
pairs = list(zip(parts, reps))
44
pairs = sorted(pairs)
45
return [pair[1] for pair in pairs]
46
47
# canonical order
48
def is_in_canonical_order(reps, perm1, perm2):
49
G = reps[0].parent()
50
N = G.normalizer(SymmetricGroup(G.degree()))
51
assert(G == perm1.parent())
52
assert(G == perm2.parent())
53
ind_perm1 = -1
54
ind_perm2 = -1
55
for rep in reps:
56
if libgap.IsConjugate(N, rep, perm1):
57
ind_perm1 = reps.index(rep)
58
if libgap.IsConjugate(N, rep, perm2):
59
ind_perm2 = reps.index(rep)
60
assert(ind_perm1 >= 0)
61
assert(ind_perm2 >= 0)
62
return ind_perm1 <= ind_perm2
63
64
# conjugacy class representatives of G up to N
65
def class_representatives_mod_ambient(G, N):
66
reps = G.conjugacy_classes_representatives()
67
if G == N:
68
return reps
69
else:
70
repsModN = []
71
for i in range(len(reps)):
72
CCModN = ConjugacyClass(N, reps[i])
73
for j in range(len(reps)-1, i, -1):
74
if reps[j] in CCModN:
75
reps.remove(reps[j])
76
return repsModN
77
78
# the fundamental lemma
79
def passport_lemma(G, N, tau0, tau1):
80
Z0 = N.centralizer(tau0)
81
Z1 = N.centralizer(tau1)
82
nus = gap.DoubleCosetRepsAndSizes(N, Z0, Z1)
83
nus = [nu[1] for nu in nus] # GAP indexes at 1
84
return [[G(tau0), G(nu*tau1*nu^-1)] for nu in nus]
85
86
# representatives for all passports of G
87
def passport_reps(G):
88
S = SymmetricGroup(G.degree())
89
N = G.normalizer(S)
90
reps = class_representatives_mod_ambient(G, N)
91
# reps = sort_reps(reps)
92
pairs = Tuples(reps, 2).list()
93
for i in range(len(pairs)-1, 0, -1):
94
pair = pairs[i]
95
# if pair[1] > pair[0]:
96
if not is_in_canonical_order(reps, pair[0], pair[1]):
97
pairs.remove(pair)
98
triples = []
99
for tau in pairs:
100
U = passport_lemma(G, N, tau[0], tau[1])
101
for i in range(len(U)):
102
sigma0 = U[i][0]
103
sigma1 = U[i][1]
104
sigmaoo = (sigma1*sigma0)^-1
105
#if sigma1 <= sigmaoo:
106
if is_in_canonical_order(reps, sigma1, sigmaoo):
107
Gtest = S.subgroup([sigma0, sigma1])
108
if G == Gtest:
109
triples.append([sigma0, sigma1, sigmaoo])
110
# sort triples by cycle structure
111
return triples
112
113
# representatives for all passports of degree d
114
def passport_representatives(d):
115
groups = TransitiveGroups(d)
116
triples = []
117
for i in range(1, groups.cardinality()+1):
118
triples += passport_reps(groups[i])
119
return triples
120
121
# sort list of triples by cycle structure
122
def cycle_type_dict(triples):
123
cycle_types = [(t[0].cycle_type(), t[1].cycle_type(), t[2].cycle_type()) for t in triples]
124
cycle_types_set = set()
125
for cycle_type in cycle_types:
126
cycle_types_set.add(cycle_type)
127
d = {}
128
for key in cycle_types_set:
129
d[key] = []
130
for t in triples:
131
t_key = (t[0].cycle_type(), t[1].cycle_type(), t[2].cycle_type())
132
assert(t_key in d)
133
d[t_key] += [t]
134
return list(d), d
135
136
# key to passport
137
def key_to_passport(d, key):
138
a,b,c = key
139
triple = d[key][0]
140
G = triple[0].parent()
141
C0 = G.conjugacy_class(triple[0])
142
C1 = G.conjugacy_class(triple[1])
143
Coo = G.conjugacy_class(triple[2])
144
print(G, key)
145
return None
146