The figure eight: free group words and covering spaces

"""The fundamental group of the figure eight, and its covering spaces.

By van Kampen's theorem the fundamental group of the figure eight (two
circles joined at a point) is the free group F2 on two loops a and b. We
compute with reduced words (A and B stand for the inverse loops), check that
ab and ba are different, and detect the difference with a homomorphism to
the symmetric group S3. Then we count covering spaces: an n-sheeted covering
of the figure eight is the same as a pair of permutations (where a and b
send each sheet), it is connected exactly when the pair acts transitively,
and connected coverings with a chosen base sheet correspond to subgroups of
index n in F2. Evidence: exact and exhaustive for the finite cases shown.
"""

from itertools import permutations, product

INVERSE = {"a": "A", "A": "a", "b": "B", "B": "b"}

def reduce_word(word):
    """Cancel adjacent inverse pairs (aA, Aa, bB, Bb) until none remain."""
    out = []
    for letter in word:
        if out and out[-1] == INVERSE[letter]:
            out.pop()
        else:
            out.append(letter)
    return "".join(out)

def inverse_word(word):
    """The inverse of a word: reverse it and invert each letter."""
    return "".join(INVERSE[c] for c in reversed(word))

def reduced_words(length):
    """All reduced words of the given length."""
    return [w for w in map("".join, product("aAbB", repeat=length))
            if reduce_word(w) == w]

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

def act(word, sigma, tau):
    """Image of a word under a -> sigma, b -> tau (letters act left to right)."""
    n = len(sigma)
    inv = {
        "a": sigma, "b": tau,
        "A": tuple(sorted(range(n), key=lambda i: sigma[i])),
        "B": tuple(sorted(range(n), key=lambda i: tau[i])),
    }
    result = tuple(range(n))
    for letter in word:
        result = compose(result, inv[letter])
    return result

def is_transitive(sigma, tau):
    """Whether the group generated by sigma and tau moves 0 to every point."""
    seen, frontier = {0}, [0]
    while frontier:
        i = frontier.pop()
        for j in (sigma[i], tau[i]):
            if j not in seen:
                seen.add(j)
                frontier.append(j)
    return len(seen) == len(sigma)

def transitive_pairs(n):
    """All transitive pairs (sigma, tau) of permutations of {0, ..., n-1}."""
    perms = list(permutations(range(n)))
    return [(s, t) for s in perms for t in perms if is_transitive(s, t)]

def subgroups_of_index(n):
    """Subgroups of index n in F2 = transitive pairs / (n - 1)!."""
    count = len(transitive_pairs(n))
    factorial = 1
    for k in range(2, n):
        factorial *= k
    return count // factorial

def connected_covers(n):
    """Connected n-sheeted coverings up to isomorphism: transitive pairs up to
    simultaneous relabelling of the sheets."""
    perms = list(permutations(range(n)))
    seen, classes = set(), 0
    for s, t in transitive_pairs(n):
        if (s, t) in seen:
            continue
        classes += 1
        for g in perms:
            g_inv = tuple(sorted(range(n), key=lambda i: g[i]))
            seen.add((compose(compose(g_inv, s), g), compose(compose(g_inv, t), g)))
    return classes

def main():
    print("Words in F2 = pi_1(figure eight); A, B are the inverse loops.")
    for word in ("abBA", "aAbaB", "ab", "ba", "abAB"):
        shown = reduce_word(word) or "(empty word = constant loop)"
        print(f"  {word:<6} reduces to {shown}")
    counts = [len(reduced_words(k)) for k in range(1, 7)]
    print(f"  reduced words of length 1..6: {counts}  (4 * 3^(k-1))")
    print()
    sigma, tau = (1, 0, 2), (0, 2, 1)
    print("Homomorphism to S3: a -> (0 1), b -> (1 2) as permutations of 0,1,2")
    for word in ("ab", "ba", "abAB"):
        print(f"  {word:<5} -> {act(word, sigma, tau)}")
    print("  ab and ba have different images, so ab != ba in F2: the")
    print("  fundamental group of the figure eight is not abelian.")
    print()
    print("Coverings of the figure eight with n sheets:")
    print("  n  transitive pairs  subgroups of index n  connected covers")
    for n in range(1, 6):
        pairs = len(transitive_pairs(n))
        covers = connected_covers(n) if n <= 4 else "-"
        print(f"  {n} {pairs:17d} {subgroups_of_index(n):21d} {covers:>17}")
    print()
    print("Epistemic status: exact and exhaustive for words of length at most 6")
    print("and coverings with at most 5 sheets (the subgroup counts agree with")
    print("Marshall Hall's 1949 formula). That pi_1 of the figure eight is F2,")
    print("and that coverings match subgroups, are theorems quoted from the")
    print("lesson, not consequences of this computation.")

if __name__ == "__main__":
    main()