01f-group-visualization.ipynb

Kernel: SageMath 10.7

Visualizing Group Structure

Module 01f | Modular Arithmetic and Groups

A single picture can reveal structure that tables of numbers hide.

Question: You've computed orders, generators, subgroups, and cosets with numbers and equations. But can you see them? What does a cyclic group actually look like?

Objectives

By the end of this notebook you will be able to:

1. Draw Cayley graphs for small groups and interpret their structure

2. Construct and read a subgroup lattice diagram

3. Use multiplication table heatmaps to spot symmetry and subgroup boundaries

From Symbols to Pictures

In 01a–01e everything was symbolic: equations, tables, lists. Now we make it visual. You'll literally see why generators reach everywhere, how subgroups nest, and where symmetry hides.

Cayley Graphs

A Cayley graph represents a group as a picture:

• Nodes = group elements (one node per element)

• Edges = the action of a chosen element $g$: draw an arrow from $a$ to $a + g$ (additive) or $a \cdot g$ (multiplicative) for every element $a$

If $g$ is a generator, following the arrows visits every node before returning to the start. If $g$ is not a generator, the arrows break into disconnected loops. Let's see both cases in $(\mathbb{Z}/6\mathbb{Z}, +)$.

# Cayley graph of (Z/6Z, +) with generator 1
R = Zmod(6)
g = R(1)

print(f'Cayley graph of (Z/6Z, +) with generator g = {int(g)}.')
print(f'Rule: draw an arrow from a to a + {int(g)} (mod 6) for every a.\n')

G_graph = DiGraph()
for a in R:
    target = a + g
    print(f'  {int(a)} -> {int(a)} + {int(g)} = {int(target)}')
    G_graph.add_edge(int(a), int(target))

p = G_graph.plot(layout='circular', vertex_size=500, vertex_color='lightblue',
       edge_color='steelblue')
p.show(figsize=5, xmin=-1.5, xmax=1.5, ymin=-1.5, ymax=1.5)
print(f'One connected cycle visiting all 6 elements.')
print(f'Generator 1 reaches everything, just like we proved in 01d.')

One connected cycle. Following the arrows from any node, you visit all 6 elements and return to the start. That is what "generator" looks like as a picture.

Now let's try element 2. Since $\gcd(2, 6) = 2 \neq 1$, element 2 is NOT a generator (01d). What does the Cayley graph look like?

# Cayley graph of (Z/6Z, +) with non-generator 2
R = Zmod(6)
g = R(2)

print(f'Cayley graph of (Z/6Z, +) with g = {int(g)} (not a generator).')
print(f'Rule: draw an arrow from a to a + {int(g)} (mod 6) for every a.\n')

G_graph = DiGraph()
for a in R:
    target = a + g
    print(f'  {int(a)} -> {int(a)} + {int(g)} = {int(target)}')
    G_graph.add_edge(int(a), int(target))

print(f'\nLook: 0 -> 2 -> 4 -> 0 forms one loop. 1 -> 3 -> 5 -> 1 forms another.')
print(f'Element 2 never crosses from evens to odds.\n')

p = G_graph.plot(layout='circular', vertex_size=500, vertex_color='lightblue',
       edge_color='red')
p.show(figsize=5, xmin=-1.5, xmax=1.5, ymin=-1.5, ymax=1.5)
d = gcd(int(g), 6)
print(f'gcd({int(g)}, 6) = {d}.')
print(f'The graph splits into {d} disconnected cycles, each of length 6/{d} = {6//d}.')
print(f'This is the visual meaning of "not a generator": the arrows cannot reach everyone.')

Common mistake: "A Cayley graph shows the group." More precisely, a Cayley graph depends on the choice of generator, not just the group. The same group $\mathbb{Z}/6\mathbb{Z}$ looks like a hexagon with generator 1, but decomposes into two triangles with generator 2.

Subgroup Lattice Diagrams

In 01e we found every subgroup of a group and verified that their sizes divide the group size. A subgroup lattice arranges all those subgroups in a diagram:

• Each node is a subgroup

• A line going up from $H_1$ to $H_2$ means $H_1 \subseteq H_2$ (every element of $H_1$ is also in $H_2$)

• The bottom is always the trivial subgroup $\{0\}$, the top is the whole group

For cyclic groups, the subgroup structure mirrors the divisor lattice of $n$. Let's build this step by step for $\mathbb{Z}/12\mathbb{Z}$.

# Subgroup lattice of (Z/12Z, +)
n = 12
R = Zmod(n)
divs = divisors(n)

# Step 1: why does each divisor of n give a subgroup?
print(f'Divisors of {n}: {divs}')
print(f'So (Z/{n}Z, +) has exactly {len(divs)} subgroups. But why?\n')

# Walk through one example to show the pattern
print(f'Take d = 3 (we want a subgroup of size 3).')
print(f'We need a generator that cycles back to 0 after exactly 3 steps.')
print(f'Try {n}/3 = 4:')
print(f'  0 -> 0+4 = 4 -> 4+4 = 8 -> 8+4 = 12 = 0 (mod {n})')
print(f'Three steps, back to 0. So <4> = {{0, 4, 8}}, size 3.\n')

print(f'The pattern: to get a subgroup of size d, use generator {n}/d.')
print(f'Why? Adding {n}/d to itself d times gives d * ({n}/d) = {n} = 0 (mod {n}).\n')

# List all subgroups
subgroups = {}
for d in divs:
    gen = n // d
    elems = sorted(set(int(R(gen) * k) for k in range(d)))
    subgroups[d] = (gen, elems)
    print(f'  <{gen}> = {elems}   (size {d})')

# Step 2: show containment with actual element overlap
print(f'\nWhich subgroups sit inside which?')
print(f'Check: does every element of H1 also appear in H2?\n')

print(f'  <6> = {subgroups[2][1]}')
print(f'  <3> = {subgroups[4][1]}')
print(f'  Every element of <6> appears in <3>? Yes. So <6> is inside <3>.\n')

print(f'  <4> = {subgroups[3][1]}')
print(f'  <6> = {subgroups[2][1]}')
print(f'  Is 4 in <6>? No. So <4> is NOT inside <6>.\n')

print(f'All direct containments (no intermediate subgroup in between):')
for d1 in divs:
    gen1, elems1 = subgroups[d1]
    for d2 in divs:
        if d2 <= d1 or d2 % d1 != 0:
            continue
        # Skip if there is a subgroup strictly between d1 and d2
        if any(d1 < d3 < d2 and d2 % d3 == 0 and d3 % d1 == 0 for d3 in divs):
            continue
        gen2, elems2 = subgroups[d2]
        print(f'  <{gen1}> {elems1}  inside  <{gen2}> {elems2}')

# Step 3: draw the lattice
print(f'\nNow the picture:')
relations = [(d1, d2) for d1 in divs for d2 in divs if d1 != d2 and d2 % d1 == 0]
P = Poset((divs, relations))
P.plot(figsize=6, vertex_size=800, vertex_color='lightyellow',
       element_labels={d: f'<{n//d}>\n|{d}|' for d in divs}).show()
print(f'Each node: <generator> on top, |size| on bottom.')
print(f'Bottom = {{0}} (trivial). Top = all of (Z/{n}Z, +).')
print(f'A line going up means "is contained in."')

The lattice mirrors the divisor lattice of 12. This is no coincidence: for cyclic groups, subgroups of $\mathbb{Z}/n\mathbb{Z}$ correspond exactly to divisors of $n$. The subgroup of size $d$ is $\langle n/d \rangle$.

Notice how the lattice captures containment at a glance. For example, $\langle 6 \rangle = \{0, 6\}$ (size 2) sits inside $\langle 3 \rangle = \{0, 3, 6, 9\}$ (size 4), which sits inside $\langle 1 \rangle = \{0, 1, \ldots, 11\}$ (size 12). Each step up means "the smaller subgroup is entirely contained in the larger one."

Checkpoint. $\mathbb{Z}/8\mathbb{Z}$ has divisors $\{1, 2, 4, 8\}$. Predict what its subgroup lattice looks like before trying Exercise 2.

Multiplication Table Heatmaps

A color-coded multiplication table can reveal structure that raw numbers hide. Let's start by looking at the actual table, then color it.

# Multiplication table of (Z/7Z*, ×)
R = Zmod(7)
units = sorted(int(u) for u in R.list_of_elements_of_multiplicative_group())

print(f'Multiplication table of (Z/7Z*, x):')
print(f'Elements: {units}\n')

# Print the numeric table
header = '   x |' + ''.join(f'{u:>4}' for u in units)
print(header)
print('   --+' + '-' * (4 * len(units)))
for a in units:
    row = [int(R(a) * R(b)) for b in units]
    print(f'  {a:>2} |' + ''.join(f'{r:>4}' for r in row))

print(f'\nEvery row is a permutation of {units} (each value appears exactly once).')
print(f'The table is symmetric about the diagonal: a*b = b*a (the group is abelian).')
print(f'\nNow the same table as a heatmap (color = product value):')

M = matrix(ZZ, len(units), len(units),
           lambda i, j: int(R(units[i]) * R(units[j])))
matrix_plot(M, cmap='viridis', figsize=5, flip_y=False).show()
print(f'Symmetric pattern = commutativity visible at a glance.')
print(f'Each color appears once per row and once per column (Latin square property).')

Does this pattern hold for other primes? Let's compare with a smaller group to see what changes and what stays the same.

# Multiplication table of (Z/5Z*, ×) for comparison
R = Zmod(5)
units = sorted(int(u) for u in R.list_of_elements_of_multiplicative_group())

print(f'Multiplication table of (Z/5Z*, x):')
print(f'Elements: {units}\n')

header = '   x |' + ''.join(f'{u:>4}' for u in units)
print(header)
print('   --+' + '-' * (4 * len(units)))
for a in units:
    row = [int(R(a) * R(b)) for b in units]
    print(f'  {a:>2} |' + ''.join(f'{r:>4}' for r in row))

print(f'\nSame properties: Latin square (each value once per row/column), symmetric.')

M = matrix(ZZ, len(units), len(units),
           lambda i, j: int(R(units[i]) * R(units[j])))
matrix_plot(M, cmap='viridis', figsize=4, flip_y=False).show()
print(f'Smaller group, different colors, but the same structural pattern.')
print(f'Both are cyclic abelian groups, so both have symmetric Latin square tables.')

Exercises

Exercise 1 (Worked)

Draw the Cayley graph of $(\mathbb{Z}/8\mathbb{Z}, +)$ with generator 3. Since $\gcd(3, 8) = 1$, it should visit all 8 elements. Then change to generator 2 and observe the difference.

# Exercise 1 — Cayley graphs of Z/8Z
R = Zmod(8)
n = 8

for g_val, color, label in [(3, 'steelblue', 'generator 3'), (2, 'red', 'non-generator 2')]:
    g = R(g_val)
    print(f'=== Z/{n}Z with {label} ===\n')

    G_graph = DiGraph()
    for a in R:
        target = a + g
        print(f'  {int(a)} -> {int(a)} + {int(g)} = {int(target)}')
        G_graph.add_edge(int(a), int(target))

    d = gcd(g_val, n)
    print(f'\n  gcd({g_val}, {n}) = {d} -> {d} cycle(s) of length {n // d}')

    p = G_graph.plot(layout='circular', vertex_size=500, vertex_color='lightblue',
           edge_color=color, title=f'Z/{n}Z with {label}')
    p.show(figsize=4, xmin=-1.5, xmax=1.5, ymin=-1.5, ymax=1.5)
    print()

Exercise 2 (Guided)

Compare the subgroup lattice of $\mathbb{Z}/12\mathbb{Z}$ and $\mathbb{Z}/8\mathbb{Z}$. Which has more subgroups? Why?

# Exercise 2 — Compare subgroup lattices
# Z/12Z lattice (provided above)
# TODO: adapt the lattice code for Z/8Z
n = 8
divs = divisors(n)
print(f'Divisors of {n}: {divs}')
print(f'Number of subgroups: {len(divs)}')
# TODO: build and plot the Poset for Z/8Z
# TODO: compare with Z/12Z (which has divisors {1,2,3,4,6,12} = 6 subgroups)

Exercise 3 (Independent)

Create a multiplication table heatmap for $(\mathbb{Z}/15\mathbb{Z}^*, \times)$. The group has $\varphi(15) = 8$ elements. Can you identify visual "blocks" in the heatmap? What subgroup do they correspond to?

# Exercise 3 — Your code here

Summary

Concept	Key idea
Cayley graphs	Nodes are elements, edges show the action of a generator. Full connection means generator, disconnected components mean non-generator
Subgroup lattices	For cyclic groups, the subgroup structure mirrors the divisor lattice of $n$
Heatmaps	Color-coded multiplication tables make commutativity and subgroup boundaries visible as symmetry patterns

Visualization turns abstract algebraic properties into spatial intuition. Generators that reach everything look connected, subgroups that nest look hierarchical, and commutativity shows up as symmetry about the diagonal.

Crypto teaser: In elliptic curve cryptography, the "group" is a set of points on a curve, not numbers mod $p$. Visualizing EC group structure, and how it differs from $\mathbb{Z}/p\mathbb{Z}^*$, will be the subject of Module 06.

---

This concludes the Explore phase of Module 01. Next steps:

• Implement: Open rust/src/lib.rs and build these functions from scratch in Rust:

  1. mod_exp (guided, loop structure provided)

  2. gcd (guided, algorithm outline provided)

  3. is_generator (scaffolded, signature + hints)

  4. element_order (scaffolded, signature + hints)

  5. find_all_generators (independent, just the signature)

  Each function has todo!() stubs to fill in. When you finish one, remove #[ignore] from its tests and run:

  cd foundations/01-modular-arithmetic-groups/rust
  cargo test                        # run all non-ignored tests
  cargo test test_mod_exp           # run tests for one function
  cargo test -- --include-ignored   # preview all tests, even ones you haven't unlocked yet
  

• Break: Attack smooth-order groups and weak generators

• Connect: See these concepts in RSA and Diffie-Hellman