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

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?

Return to the overview of Part 3.1 (Cycle Decomposition).

Continue to the overview of Part 3.2 (Rejewski's Theorems).