# The Theorem that Won the War: Activities for Part 3.1 (Cycle Decomposition)

Author(s):
Jeff Suzuki (Brooklyn College)

NOTE: In the following, we'll gradually scale our way up towards the full Enigma encryption on 26 letters.

1. Suppose $E_{1}, E_{2}$ are two Enigma permutations, and $E_{1}$ contains $(\alpha c)$ while $E_{2}$ contains $(\alpha f)$. You should assume both contain a number of other transpositions as well.
1. Prove: $E_{2}E_{1} ( c) = f$. (In particular, why can we disregard the effect of the other transpositions in $E_{2}, E_{1}$?)
2. Suppose $E_{1}, E_{2}$ contained the same transposition $(\alpha\beta)$. Find $E_{2}E_{1}(\alpha)$ and $E_{2}E_{1}(\beta)$.
2. Suppose $\sigma = (ab)(cd)(ef)$ and $\tau = (ab)(cf)(de)$ are two permutations on six symbols.
1. Find the product $\sigma\tau$.
2. Classify the cycles in the product $\sigma\tau$. In particular: How many 1-cycles? How many 2-cycles? How many 3-cycles?
3.  $(ab)$ is in both $\sigma$ and $\tau$. What do you notice about $a, b$ in the product $\sigma\tau$?
4. The transposition $(cd)$ is in $\sigma$. What do you notice about $c, d$ in the product $\sigma\tau$?
5. The transposition $(de)$ is in $\tau$. What do you notice about $d, e$ in the product $\sigma\tau$?
3. Suppose $\alpha = (ab)(cd)(ef)(gh)$ and $\beta = (ad)(bg)(ce)(fh)$ are two permutations on eight symbols.
1. Find the product $\alpha\beta$.
2. Classify the cycles in the product $\alpha\beta$. In particular: How many 1-cycles? How many 2-cycles? How many 3-cycles?
3. What do you notice about the elements of each transposition of $\alpha$?
4. Suppose $\mu = (ab)(ce)(dj)(fg)(kl)(hi)$ and $\nu = (aj)(cd)(db)(fk)(gl)(hi)$ are two permutations on twelve symbols.
1. Find $\mu\nu$.
2. Classify the cycles in the product $\mu\nu$.
3. Suppose $(xy)$ is a transposition in exactly one of $\mu$ or $\nu$. What can you say about $x, y$ in the product $\mu\nu$?
5. Note that all the preceding involutions are proper. Suppose $\kappa = (ab)(cd)(ef)$ and $\lambda = (ac)(be)$ are two permutations on six symbols.
1. Find $\kappa\lambda$.
2. What happens with products of proper involutions that does not happen when one of the involutions is not proper?