All subgroups of S3, D4, A4, S4 and C12

"""Every subgroup of five small groups, found by machine, with Lagrange checked.

Permutations are tuples of images, and a subgroup is generated by closure. Every
subgroup of a finite group is the join of its cyclic subgroups, so starting from
the cyclic subgroups and repeatedly forming the subgroup generated by two known
subgroups finds *all* subgroups. For each group the program lists the subgroup
orders, counts the normal subgroups, checks Lagrange's theorem and reports the
divisors of |G| that are not the order of any subgroup (for A4: 6). This is an
exact, exhaustive computation for these five groups and proves nothing beyond.
"""

from collections import Counter
from math import lcm

def compose(p, q):
    """Return the permutation 'first q, then p' (p after q), as a tuple."""
    return tuple(p[i] for i in q)

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

def closure(gens, n):
    """The subgroup of S_n generated by gens, as a frozenset of tuples.

    In a finite group every inverse is a positive power, so closing the identity
    under multiplication by the generators gives the whole generated subgroup.
    """
    identity = tuple(range(n))
    elements = {identity}
    frontier = [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 order(p):
    """The order of a permutation: the lcm of its cycle lengths."""
    seen, result = set(), 1
    for start in range(len(p)):
        length, i = 0, start
        while i not in seen:
            seen.add(i)
            i = p[i]
            length += 1
        if length:
            result = lcm(result, length)
    return result

def all_subgroups(group, n):
    """Every subgroup of a finite permutation group, as frozensets.

    Begin with the cyclic subgroups; join each newly found subgroup with every
    known one until nothing new appears. A subgroup H is the join of the <h>,
    h in H, built one cyclic subgroup at a time, so H is eventually found.
    """
    gens = {}
    for g in sorted(group):
        gens.setdefault(closure([g], n), [g])
    frontier = list(gens)
    while frontier:
        found = []
        for h in frontier:
            for k in list(gens):
                if h <= k or k <= h:
                    continue
                join = closure(gens[h] + gens[k], n)
                if join not in gens:
                    gens[join] = gens[h] + gens[k]
                    found.append(join)
        frontier = found
    return list(gens)

def is_normal(sub, group):
    """True when g h g^-1 lies in sub for all g in group and h in sub."""
    return all(compose(compose(g, h), inverse(g)) in sub
               for g in group for h in sub)

def census(group, n):
    """Return (subgroup-order counts, number normal, missing divisors)."""
    subs = all_subgroups(group, n)
    counts = Counter(len(s) for s in subs)
    normal = sum(is_normal(s, group) for s in subs)
    size = len(group)
    divisors = [d for d in range(1, size + 1) if size % d == 0]
    missing = [d for d in divisors if d not in counts]
    return counts, normal, missing

def examples():
    """The five groups, as (name, degree n, generators)."""
    return [
        ("S3", 3, [(1, 0, 2), (1, 2, 0)]),
        ("D4", 4, [(1, 2, 3, 0), (0, 3, 2, 1)]),
        ("A4", 4, [(1, 2, 0, 3), (1, 0, 3, 2)]),
        ("S4", 4, [(1, 0, 2, 3), (1, 2, 3, 0)]),
        ("C12", 12, [tuple((i + 1) % 12 for i in range(12))]),
    ]

def main():
    print("group |G| subgroups normal  subgroup orders: order(how many)")
    total, lagrange_ok = 0, True
    for name, n, gen in examples():
        group = closure(gen, n)
        counts, normal, missing = census(group, n)
        total += sum(counts.values())
        lagrange_ok &= all(len(group) % d == 0 for d in counts)
        shown = " ".join(f"{d}({c})" for d, c in sorted(counts.items()))
        print(f"{name:<5} {len(group):>3} {sum(counts.values()):>9} {normal:>6}"
              f"  {shown}")
        if missing:
            print(f"      divisors of {len(group)} with no subgroup: {missing}")
    print(f"Lagrange (subgroup order divides |G|) holds for all {total} "
          f"subgroups: {lagrange_ok}")
    a4 = closure(examples()[2][2], 4)
    hist = sorted(Counter(order(p) for p in a4).items())
    print(f"A4 element orders (order: how many): {hist}")
    print("(Index 2 would force a subgroup of order 6 to contain all nine")
    print("squares in A4: the identity and the eight 3-cycles.)")
    print()
    print("Epistemic status: exact and exhaustive for these five groups. The")
    print("A4 row is a genuine counterexample to the converse of Lagrange's")
    print("theorem; the other rows are evidence, not proofs of general laws.")

if __name__ == "__main__":
    main()