Please Login to access more options.

Problem 14(The Span Of A Simple Shift)

Suppose that our alphabet $S$ consists of only 12 letters $S=\{a,b,c,d,e,f,g,h,i,j,k,l\}$. Let $H_{12}=\{\phi_n\mid n\in \mathbb{Z}\}$ be the set of simple shift permutations on this 12 letter alphabet (we wrap around from $l$ to $a$).

  1. For each $n\in \{0,1,2,\ldots,11\}$, list the elements in $\text{span}(\{\phi_n\} ) $.
  2. For which $n$ does $\text{span}(\{\phi_n\})=H_{12}$.
  3. Make a conjecture about any patterns you see above and their relation to the size (12) of the alphabet.
  4. Whenever you make a conjecture, you should always test your conjecture on an example you have not yet considered. Pick another integer $k\neq 12,26$, and look at the set $H_k$ of simple shift permutations of an alphabet consisting of $k$ letters. Then check if your conjecture holds.

Solution

Part 1.

To organize our answer, we write a table of the elements of $\span(\{\phi_n\})$ for each $n \in \{0,1,2,...,11,12\}$. $$ \begin{array}{c|c} n&\span(\{\phi_n\})\\ \hline 0 & \{\phi_0\} \\ 1 & H_{12} \\ 2 & \{\phi_0, \phi_2, \phi_4, \phi_6, \phi_8, \phi_{10}\} \\ 3 & \{\phi_0, \phi_3, \phi_6, \phi_9\} \\ 4 & \{\phi_0, \phi_4, \phi_8\} \\ 5 & H_{12} \\ 6 & \{\phi_0, \phi_6\} \\ 7 & H_{12} \\ 8 & \{\phi_0, \phi_4, \phi_8\} \\ 9 & \{\phi_0, \phi_3, \phi_6, \phi_9\} \\ 10 & \{\phi_0, \phi_2, \phi_4, \phi_6, \phi_8, \phi_{10}\} \\ 11 & H_{12} \\ \end{array}$$ In order to generate this table, consider for example the permutation $\phi_1$. The table claims that $\text{span}(\{\phi_1\}) = H_{12}$. To find this, we will find all permutation combinations of $\phi_1$. We know that $\phi_0 \in \text{span}(\{\phi_1\})$. We also find $\phi_1\phi_1 = \phi_2 \in \text{span}(\{\phi_1\})$. Multiplying by $\phi_1$ on the right side of $\phi_2$ leads us to conclude that $\phi_3 \in \text{span}(\{\phi_1\})$. We do this until returning to $\phi_0$. This includes all elements in $H_{12}$. Thus, we know that $\text{span}(\{\phi_1\}) = H_{12}$.

Similarly, consider the permutation $\phi_2$. We see that $\phi_2\phi_2 = \phi_4 \in \text{span}(\{\phi_1\})$. Continuing this, we find that $\phi_4\phi_2 = \phi_4 \in \text{span}(\{\phi_1\})$. Continuing this, we find that $\{\phi_0, \phi_2, \phi_4, \phi_6, \phi_8, \phi_{10}\} \in \span(\phi_1)$.

Part 2.

From the previous part of the problem, we found that $\span({\phi_n}) = H_{12}$ for $n = 1,5,7,11$.

Part 3.

My conjecture is that for any number $n$ such that $n$ is relatively prime to $12$, $\span(\{\phi_n\}) = H_{12}$.

Part 4.

To test the conjecture, we choose $k = 11$, and again make a table of the elements, this time for $\span(\{\phi_n\})$ for each $n \in \{0,1,2,...,11,11\}$.

$$ \begin{array}{c|c} n&\span(\{\phi_n\})\\ \hline 0 & \{\phi_0\} \\ 1 & H_{11} \\ 2 & H_{11} \\ 3 & H_{11} \\ 4 & H_{11} \\ 5 & H_{11} \\ 6 & H_{11} \\ 7 & H_{11} \\ 8 & H_{11} \\ 9 & H_{11} \\ 10 & H_{11} \end{array} $$

Similar to part 1, we can find this by inspection. Consider, for example $\span(\{\phi_3\})$. In order of discovery, these are $\{\phi_0, \phi_3, \phi_6, \phi_9, \phi_1, \phi_4, \phi_7, \phi_{10}, \phi_2, \phi_5, \phi_8\}$. Thus, we find that $\span(\{\phi_3\}) = H_{11}$.

Tags

Change these as needed.

  • Week3 - Which week are you writing this problem for?
  • Jason - Sign your name by just changing "YourName" to your wiki name.
  • Submit
  • 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.