Please Login to access more options.

Problem 4 (The Set Of Simple Shift Permutations)

Let $S = \{a,b,c,\ldots,z\}$ be the set of letters in the Roman alphabet. For each $n\in\mathbb{Z}$, let $\phi_{n}:S\to S$ represent the encryption key that shifts each letter in the alphabet right $n$, where we wrap around from $z$ to $a$ for letters that need to be shifted past $z$. So $\phi_3(a)=d$, $\phi_3(b)=e$, and $\phi_3(z)=c$. We've called this a simple shift permutation of $S$.

  1. For which $n$ does $\phi_n$ not change the message?
  2. Consider the encryption key $\phi_{9}$, which shifts each letter right 9. If a message had been encrypted using $\phi_9$, then clearly $\phi_{-9}$ would decrypt the message as $\phi_{-9}(\phi_9(s))=s$ for any letter $s$. Give a positive integer $n$ that we could also use to decode a message that has been encrypted using $\phi_9$.
  3. Does $\phi_{30}=\phi_7$? Does $\phi_{33}=\phi_7$? For which $n$ does $\phi_n=\phi_7$? Explain.
  4. Consider the set of all shifts of $S$, namely $H=\{\phi_n\mid n\in\mathbb{Z}\}$. How many different functions are in $H$? Prove your answer is correct.

Solution

We will show that $|H| = 26$. This requires four facts.

  1. First, note that the function $\phi_{26}(m) = m$ for all $m \in S$. Thus we have that any number of applications of $\phi_{26}$ to $m$ is equal to $m$. We denote $k$ applications of a function $\phi_{n}$ to $m$ as $\phi_{n}^k(m)$.
  2. Second, note that $\phi_{n_1}(\phi_{n_2}(m)) = \phi_{n_1+n_2}(m)$ for all $m \in S$.
  3. Third, note that there are at least $26$ distinct functions $\phi_n$, because all of $\phi_0$ through $\phi_{25}$ are clearly distinct.
  4. Last, recall the Division Algorithm Theorem, which shows that for all $n, d \in \mathbb{Z}$ with $d\neq0$, there exist integers $q, r$ with $r < n$ such that $n = qd + r$. We will use this with $d = 26$ throughout this proof.

Consider $\phi_n(m)$ for some integer $n$ and some $m \in S$. By the division algorithm theorem, we know that $n = 26q + r$ for some integers $q, r$ with $r < 26$. Then we have $$ \begin{align} \phi_{n}(m) = \phi_{26q + r}(m) &= \phi_{26q}(\phi_r(m)) & \text{(by 2)}\\ &= \phi_{26}^q(\phi_r(m)) & \text{(by 2)}\\ &= \phi_r(m) & \text{(by 1)}. \end{align}$$

By the division algorithm theorem, we know that $0 \leq r \leq 25$. This shows that each $\phi_n$ with $n \in \mathbb{Z}$ corresponds to a $\phi_r$ with $0 \leq r \leq 25$. Therefore, there can be at most $26$ distinct permutations in $H$. Since we already know (by 3) that there are at least $26$ distinct permutations in $H$, it must be that there are exactly $26$ permutations in $H$, meaning that $|H| = 26$, which is what we wanted to prove.

Tags

Change these as needed.

  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.