Balls in Cayley graphs: polynomial and exponential growth

"""Growth of groups: counting balls in Cayley graphs.

For three groups with two generators we count, by breadth-first search, the
ball B(r) of radius r in the word metric (all elements that are products of
at most r generators and their inverses):

* Z^2 with the standard generators: |B(r)| = 2r^2 + 2r + 1 (quadratic);
* the group generated by Sanov's matrices A = [[1, 2], [0, 1]] and
  B = [[1, 0], [2, 1]] in SL(2, Z), computed with integer matrices. If the
  group is free, |B(r)| = 2 * 3^r - 1, the ball in the 4-regular tree;
* the integer Heisenberg group (a, b, c)(a', b', c') = (a + a', b + b',
  c + c' + ab'), which is nilpotent; its growth is polynomial of degree 4
  (Bass-Guivarc'h formula: 1 * 2 + 2 * 1 = 4).

The counts are exact. The growth degrees are numerical estimates from a finite
range of radii; matching 2 * 3^r - 1 up to radius 8 checks Sanov's theorem
only for words of length at most 16.
"""

import math

def ball_sizes(identity, generators, multiply, radius):
    """Sizes |B(0)|, ..., |B(radius)| of balls in the Cayley graph.

    ``generators`` must be closed under inverses; elements must be hashable.
    """
    seen = {identity}
    frontier = [identity]
    sizes = [1]
    for _ in range(radius):
        new = []
        for g in frontier:
            for s in generators:
                h = multiply(g, s)
                if h not in seen:
                    seen.add(h)
                    new.append(h)
        frontier = new
        sizes.append(len(seen))
    return sizes

def z2_mul(g, h):
    """Addition in Z^2."""
    return (g[0] + h[0], g[1] + h[1])

Z2_GENERATORS = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def mat_mul(g, h):
    """Product of 2x2 integer matrices stored as tuples (a, b, c, d)."""
    a, b, c, d = g
    e, f, p, q = h
    return (a * e + b * p, a * f + b * q, c * e + d * p, c * f + d * q)

SANOV_GENERATORS = [(1, 2, 0, 1), (1, -2, 0, 1), (1, 0, 2, 1), (1, 0, -2, 1)]

def heis_mul(g, h):
    """Multiplication in the integer Heisenberg group."""
    return (g[0] + h[0], g[1] + h[1], g[2] + h[2] + g[0] * h[1])

HEIS_GENERATORS = [(1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0)]

def growth_degree(sizes, r):
    """Estimate d in |B(r)| ~ c r^d from radii r and 2r."""
    return math.log(sizes[2 * r] / sizes[r]) / math.log(2)

def main():
    z2 = ball_sizes((0, 0), Z2_GENERATORS, z2_mul, 12)
    sanov = ball_sizes((1, 0, 0, 1), SANOV_GENERATORS, mat_mul, 8)
    heis = ball_sizes((0, 0, 0), HEIS_GENERATORS, heis_mul, 12)
    print("Ball sizes |B(r)| in Cayley graphs (exact, by breadth-first search)")
    print(" r     Z^2  2r^2+2r+1   <A,B> in SL2(Z)  2*3^r-1  Heisenberg")
    for r in range(9):
        print(f"{r:2d} {z2[r]:7d} {2 * r * r + 2 * r + 1:10d} "
              f"{sanov[r]:17d} {2 * 3 ** r - 1:8d} {heis[r]:11d}")
    free_ok = all(sanov[r] == 2 * 3 ** r - 1 for r in range(9))
    print(f"Sanov's group matches the free group up to radius 8: {free_ok}")
    print()
    print("Estimated growth degree log2(|B(2r)| / |B(r)|):")
    for r in (2, 4, 6):
        print(f"  r = {r}:  Z^2 {growth_degree(z2, r):.3f}"
              f"   Heisenberg {growth_degree(heis, r):.3f}")
    ratio = sanov[8] / sanov[7]
    print(f"Free group: |B(8)| / |B(7)| = {ratio:.4f} (exponential, base 3)")
    print()
    print("Epistemic status: the ball sizes are exact counts. Agreement with")
    print("2 * 3^r - 1 up to r = 8 is exhaustive evidence that no reduced word")
    print("of length <= 16 in A, B is trivial; Sanov's theorem (proved in the")
    print("lesson and in Lean) covers all lengths. The degree estimates come from")
    print("a finite range of radii; that the Heisenberg degree is exactly 4 is")
    print("the Bass-Guivarc'h theorem, not something this computation proves.")

if __name__ == "__main__":
    main()