Representation theory of finite groups

"""Character tables of S3, S4, D4 and Q8 found from permutation characters.

Each group is built concretely (permutations, or 2 x 2 complex matrices for
the quaternion group Q8). We compute conjugacy classes by brute force and the
permutation characters of G acting on the cosets of each cyclic subgroup,
plus the trace of a natural matrix representation. Using the inner product
<a, b> = (1/|G|) sum_g a(g) b(g)^*, we strip off known irreducible components
and keep any remainder with <chi, chi> = 1 (an irreducible character, by the
orthogonality relations), also trying products of characters, until there are
as many irreducibles as classes. We then check sum of squares of degrees = |G|
and compare the tables of D4 and Q8. Exact rational arithmetic.
"""

from fractions import Fraction
from itertools import permutations

def compose(p, q):
    """Permutation composite p after q (tuples)."""
    return tuple(p[i] for i in q)

def perm_group(gens):
    """Closure of a list of permutations under composition."""
    elems = {tuple(range(len(gens[0])))}
    frontier = list(elems)
    while frontier:
        new = []
        for x in frontier:
            for g in gens:
                y = compose(g, x)
                if y not in elems:
                    elems.add(y)
                    new.append(y)
        frontier = new
    return sorted(elems)

def matmul2(a, b):
    """Product of 2 x 2 complex matrices stored as 4-tuples."""
    return (a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3],
            a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3])

def quaternion_group():
    """Q8 as matrices generated by i = diag(i, -i) and j = [[0, 1], [-1, 0]]."""
    gens = [(1j, 0, 0, -1j), (0, 1, -1, 0)]
    elems = {(1, 0, 0, 1)}
    frontier = list(elems)
    while frontier:
        new = [matmul2(g, x) for x in frontier for g in gens]
        new = [y for y in new if y not in elems]
        elems.update(new)
        frontier = new
    return sorted(elems, key=str)

class Group:
    """A finite group given by its elements and multiplication."""

    def __init__(self, elems, mul):
        self.elems, self.mul = list(elems), mul
        self.one = next(e for e in self.elems
                        if all(mul(e, x) == x for x in self.elems))
        self.inv = {x: next(y for y in self.elems if mul(x, y) == self.one)
                    for x in self.elems}
        self.classes = []
        seen = set()
        for x in self.elems:
            if x not in seen:
                cls = {mul(mul(g, x), self.inv[g]) for g in self.elems}
                seen |= cls
                self.classes.append(sorted(cls, key=str))
        self.classes.sort(key=lambda c: (self.order(c[0]), len(c)))
        self.class_of = {x: i for i, c in enumerate(self.classes) for x in c}

    def order(self, x):
        """Order of an element."""
        k, y = 1, x
        while y != self.one:
            y, k = self.mul(y, x), k + 1
        return k

    def cyclic_subgroup(self, x):
        """The subgroup generated by x."""
        out, y = [self.one], x
        while y != self.one:
            out.append(y)
            y = self.mul(y, x)
        return out

    def coset_character(self, sub):
        """Permutation character of G acting on the left cosets of sub."""
        cosets = {frozenset(self.mul(x, h) for h in sub) for x in self.elems}
        return tuple(sum(1 for c in cosets
                         if frozenset(self.mul(cls[0], y) for y in c) == c)
                     for cls in self.classes)

    def inner(self, a, b):
        """<a, b> = (1/|G|) sum over classes |C| a(C) b(C) (real characters)."""
        total = sum(len(c) * a[i] * b[i] for i, c in enumerate(self.classes))
        return Fraction(total, len(self.elems))

def irreducibles(group, candidates):
    """Irreducible characters extracted from candidates and their products."""
    irr, pool = [], list(candidates)
    while len(irr) < len(group.classes) and pool:
        progress = False
        for chi in pool + [tuple(a * b for a, b in zip(x, y))
                           for x in irr for y in pool]:
            rest = list(chi)
            for psi in irr:
                m = group.inner(chi, psi)
                rest = [r - m * p for r, p in zip(rest, psi)]
            rest = tuple(int(r) for r in rest)
            if any(rest) and group.inner(rest, rest) == 1:
                if rest[0] < 0:
                    rest = tuple(-r for r in rest)
                if rest not in irr:
                    irr.append(rest)
                    progress = True
        if not progress:
            break
    return sorted(irr, key=lambda c: (c[0], [-v for v in c]))

def fs_indicator(group, chi):
    """Frobenius-Schur indicator (1/|G|) sum_g chi(g^2): +1 real,
    -1 quaternionic, 0 not real-valued."""
    total = sum(chi[group.class_of[group.mul(x, x)]] for x in group.elems)
    return Fraction(total, len(group.elems))

def same_table(g, h, tg, th):
    """Equal character tables up to reordering rows and same-size columns."""
    if sorted(len(c) for c in g.classes) != sorted(len(c) for c in h.classes):
        return False
    n = len(g.classes)
    for perm in permutations(range(n)):
        if all(len(g.classes[i]) == len(h.classes[perm[i]]) for i in range(n)):
            rows = {tuple(row[perm[i]] for i in range(n)) for row in th}
            if rows == set(tg):
                return True
    return False

def sign(p):
    """Sign of a permutation, by counting inversions."""
    inv = sum(1 for i in range(len(p)) for j in range(i + 1, len(p))
              if p[i] > p[j])
    return -1 if inv % 2 else 1

def natural_characters(group, kind):
    """Sign and fixed-point characters of a permutation group, or the trace
    of the defining 2 x 2 matrices of Q8."""
    reps = [c[0] for c in group.classes]
    if kind == "perm":
        return [tuple(sign(x) for x in reps),
                tuple(sum(1 for i, v in enumerate(x) if i == v) for x in reps)]
    return [tuple(int((x[0] + x[3]).real) for x in reps)]

def build_groups():
    """The four groups, with the kind of their natural representation."""
    return {"S3": (Group(perm_group([(1, 0, 2), (1, 2, 0)]), compose), "perm"),
            "S4": (Group(perm_group([(1, 0, 2, 3), (1, 2, 3, 0)]), compose),
                   "perm"),
            "D4": (Group(perm_group([(1, 2, 3, 0), (0, 3, 2, 1)]), compose),
                   "perm"),
            "Q8": (Group(quaternion_group(), matmul2), "matrix")}

def character_table(group, kind):
    """Irreducible characters of the group, from coset and natural
    characters."""
    cands = [group.coset_character(group.elems)]        # trivial character
    cands += [group.coset_character(group.cyclic_subgroup(x))
              for x in group.elems]
    cands += natural_characters(group, kind)
    return irreducibles(group, list(dict.fromkeys(cands)))

def main():
    groups = {name: g for name, (g, _) in build_groups().items()}
    kinds = {name: kind for name, (_, kind) in build_groups().items()}
    tables = {}
    for name, g in groups.items():
        t = character_table(g, kinds[name])
        tables[name] = t
        sizes = [len(c) for c in g.classes]
        degrees = [row[0] for row in t]
        print(f"{name}: |G| = {len(g.elems)}, class sizes {sizes}, "
              f"degrees {degrees}")
        print(f"  irreducibles = classes: {len(t) == len(sizes)}; "
              f"sum of squares = |G|: {sum(d * d for d in degrees) == len(g.elems)}")
        if name in ("S3", "S4", "Q8"):
            for row in t:
                print("   ", row)
    d4, q8 = groups["D4"], groups["Q8"]
    print("D4 and Q8 have the same character table:",
          same_table(d4, q8, tables["D4"], tables["Q8"]))
    inv_d4 = sum(1 for x in d4.elems if d4.order(x) == 2)
    inv_q8 = sum(1 for x in q8.elems if q8.order(x) == 2)
    print(f"  but elements of order 2: D4 has {inv_d4}, Q8 has {inv_q8}")
    two = {name: next(r for r in tables[name] if r[0] == 2) for name in tables
           if name in ("D4", "Q8")}
    print("  Frobenius-Schur indicator (1/|G|) sum chi(g^2) of the 2-dim "
          "character:")
    print(f"    D4: {fs_indicator(d4, two['D4'])} (real), "
          f"Q8: {fs_indicator(q8, two['Q8'])} (quaternionic)")
    print()
    print("Epistemic status: exact computations for four specific groups; "
          "the extraction\nuses the orthogonality relations (proved in the "
          "lesson) to certify each\ncharacter as irreducible. It does not "
          "prove anything about other groups.")

if __name__ == "__main__":
    main()