Sharedenumerate_permutation_triples.sageOpen in CoCalc
Author: Michael Musty
Views : 11
1# simultaneous conjugation (isomorphism)
2def 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
21def 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
30def 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
41def 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
48def 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
65def 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
79def 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
87def 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
114def 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
122def 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:
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
137def 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