18.783 Problem Set 6 Problem 2.sagews

def tuplify(A): return tuple(map(tuple,A))

def extend_to_group(S):
    ### simple O(|S||G|) algorithm to compute the group G generated by S (for larger groups use Dimino's algorithm) ###
    one = S[0].parent().one()
    G = S; G.append(one)
    T=set(map(tuplify,G))
    for g in G:
        for s in S:
            h=g*s
            if not tuplify(h) in T:
                G.append(h); T.add(tuplify(h))
    return G

def order (A):
    ### computes the multiplicative order of A using brute force (fast for elements with small orders and much faster than Sage for some reason) ###
    B=A; n=1
    while not B.is_one(): B *= A; n+=1
    return n

def group_stats(G):
    S=dict()
    for A in G:
        key = (A.det(),A.trace(),order(A))
        if not key in S: S[key]=1
        else: S[key]+=1
    N=len(G)
    for key in S: S[key]/=N
    return S
    
GL23 = extend_to_group([matrix(GF(3),2,2,m) for m in [[2,0,0,1],[2,1,2,0]]])                       # group of order 48 GL(2,3)
Q16 = extend_to_group([matrix(GF(3),2,2,m) for m in [[1,1,2,1],[0,1,1,0]]])                        # group of order 16 (semidihedral Q16)
D6 = extend_to_group([matrix(GF(3),2,2,m) for m in [[1,2,1,0],[0,1,1,0]]])                         # group of order 12 (dihedral)
D4 = extend_to_group([matrix(GF(3),2,2,m) for m in [[2,0,0,1],[0,2,1,0]]])                         # group of order 8  (dihedral)
C8 = extend_to_group([matrix(GF(3),2,2,m) for m in [[1,1,1,0]]])                                   # group of order 8  (cyclic)
S3 = extend_to_group([matrix(GF(3),2,2,m) for m in [[2,1,2,0],[1,0,1,2]]])                         # group of order 6  (dihedral = sym(3))
D2 = extend_to_group([matrix(GF(3),2,2,m) for m in [[2,0,0,1],[2,0,0,2]]])                         # group of order 4  (dihedral)
C2 = extend_to_group([matrix(GF(3),2,2,m) for m in [[2,0,0,1]]])                                   # group of order 2  (cyclic)

GL23_subgroups = (("GL23",group_stats(GL23)),("Q16",group_stats(Q16)),("D6",group_stats(D6)),("D4",group_stats(D4)),("C8",group_stats(C8)),("S3",group_stats(S3)),("D2",group_stats(D2)),("C2",group_stats(C2)))

E1 = EllipticCurve([1,0])
E2 = EllipticCurve([0,1])
E3 = EllipticCurve([0,432])
E4 = EllipticCurve([1,1])
E5 = EllipticCurve([21,26])
E6 = EllipticCurve([-112,784])
E7 = EllipticCurve([-3915,113670])
E8 = EllipticCurve([4752,127872])
E9 = EllipticCurve([5805,-285714])
E10 = EllipticCurve([652509,-621544482])

curves = [E1,E2,E3,E4,E5,E6,E7,E8,E9,E10]