Cosets that multiply, and cosets that do not

"""When is "multiply the cosets" a well-defined operation?

For every subgroup H of the groups S3, D4 and A4 (as permutation groups), the
program tests the rule (aH)(bH) = abH against every choice of representatives,
and separately tests whether H is normal (gHg^-1 = H for all g). The two tests
always agree, as the lesson proves. For each normal subgroup it reports the
order of the quotient group G/H and the orders of its elements; for each
non-normal one it prints a witness showing the rule depends on the choice of
representative. Exact and exhaustive for these three groups.
"""

from collections import Counter

def compose(p, q):
    """The permutation 'first q, then p'."""
    return tuple(p[i] for i in q)

def inverse(p):
    """Inverse permutation."""
    inv = [0] * len(p)
    for i, image in enumerate(p):
        inv[image] = i
    return tuple(inv)

def closure(gens):
    """The group generated by a list of permutations of the same degree."""
    identity = tuple(range(len(gens[0])))
    elements, frontier = {identity}, [identity]
    while frontier:
        new = []
        for x in frontier:
            for g in gens:
                y = compose(g, x)
                if y not in elements:
                    elements.add(y)
                    new.append(y)
        frontier = new
    return frozenset(elements)

def subgroups(group):
    """All subgroups, as iterated joins of cyclic subgroups (exhaustive)."""
    found = {closure([g]) for g in group}
    frontier = list(found)
    while frontier:
        new = []
        for h in frontier:
            for k in list(found):
                join = closure(sorted(h | k))
                if join not in found:
                    found.add(join)
                    new.append(join)
        frontier = new
    return sorted(found, key=lambda s: (len(s), sorted(s)))

def coset(a, sub):
    """The left coset aH as a frozenset."""
    return frozenset(compose(a, h) for h in sub)

def is_normal(sub, group):
    """gHg^-1 = H for every g in the group."""
    return all(compose(compose(g, h), inverse(g)) in sub
               for g in group for h in sub)

def product_witness(sub, group):
    """Return (a, a2, b) with aH = a2H but abH != a2bH, or None if the
    coset product is well defined. Left factors are varied; right factors
    are fixed, which already detects every failure (see the lesson)."""
    for a in sorted(group):
        for h in sorted(sub):
            a2 = compose(a, h)
            for b in sorted(group):
                if coset(compose(a, b), sub) != coset(compose(a2, b), sub):
                    return a, a2, b
    return None

def quotient_orders(sub, group):
    """Orders of the elements of G/N, computed on cosets."""
    cosets = {coset(g, sub) for g in group}
    identity = frozenset(sub)
    orders = []
    for c in cosets:
        rep = next(iter(c))
        power, k = rep, 1
        while coset(power, sub) != identity:
            power, k = compose(rep, power), k + 1
        orders.append(k)
    return sorted(Counter(orders).items())

def groups():
    """The three groups, as (name, generators)."""
    return [
        ("S3", [(1, 0, 2), (1, 2, 0)]),
        ("D4", [(1, 2, 3, 0), (0, 3, 2, 1)]),
        ("A4", [(1, 2, 0, 3), (1, 0, 3, 2)]),
    ]

def main():
    agree = True
    witness_shown = False
    for name, gens in groups():
        group = closure(gens)
        print(f"{name} (order {len(group)}): |H|  normal  product defined  G/H")
        for sub in subgroups(group):
            normal = is_normal(sub, group)
            witness = product_witness(sub, group)
            agree &= normal == (witness is None)
            info = f"order {len(group) // len(sub)}, orders "
            info += str(quotient_orders(sub, group)) if normal else "-"
            print(f"   {len(sub):>3}  {str(normal):<6}  {str(witness is None):<15}"
                  f"  {info if normal else 'not a group'}")
            if witness and not witness_shown:
                witness_shown = True
                a, a2, b = witness
                print(f"     e.g. a={a}, a'={a2} lie in one coset, but ab and")
                print(f"     a'b lie in different cosets (b={b})")
    print(f"'product well defined' agrees with 'normal' every time: {agree}")
    print()
    print("Epistemic status: exact and exhaustive for every subgroup of S3, D4")
    print("and A4. It illustrates the theorem (well defined <=> normal), which")
    print("the lesson proves for all groups; the witnesses are genuine proofs")
    print("that those particular subgroups are not normal.")

if __name__ == "__main__":
    main()