All Problems

Please Login to access more options.

Today

Since elementary school, you've been doing division. The following theorem is a crucial beginning place for much of our work in abstract algebra. It gives a formal meaning to the quotient and remainder when performing division.

Theorem (Division Algorithm)

Let $a,n\in\mathbb{Z}$, with $n> 0$. Then there exists unique integers $q$ and $r$ (called the quotient and remainder) such that $a=qn+r$ where $0\leq r<n$.

Anytime you see a new word, a new theorem, a new problem, etc., making an example to illustrate the new idea is crucial, as well as being able to recognize when something closely related is not an example. As the semester progresses, we'll be doing this with each new problem we work on. Sometimes the problem itself will ask you to create the example, and sometimes you'll just need to make it yourself. Here's an example of how to give an example and non example of the theorem given above.

Example

If we let $a=23$ and $n=5$, then we can write $23=4\cdot 5+3$. The quotient is $q=4$ and the remainder is $r=3$. Notice that $0\leq r<5$.

Non Example

Let $a=-23$ and $n=5$. We can write $-23=(-4)\cdot 5-3$, so it might be tempting to say that the quotient is $q=-4$ and the remainder is $r=-3$. However notice that it is not true that $0\leq r<5$. The remainder cannot be negative, and must be less than $n$. Instead we can write $-23=(-5)\cdot 5+2$. This means the quotient is $q=-5$ and the remainder is $r=2$.

We'll come back to the division algorithm very soon, and give a formal proof. You are welcome to start working on the proof now for homework. You'll see the division algorithm show up in several places as you work the first few weeks of problems.

Problem 1 (The Game Of Scoring)

The game of Scoring is a two-player game. Start by creating a pile of $n\geq 1$ objects (feel free to choose $n$ however you want). On each player's turn, they must choose 1, 2, or 3 items from the pile. Players alternate taking turns until someone takes the last object. Whoever takes the last object wins.

1. Play this game several times with various values of $n$.
2. For which values of $n$ does the first player have a winning strategy (meaning they are guaranteed to win if they play correctly). Remember to always fully justify your answers.
3. For which values of $n$ does the second player have a winning strategy? Why?
4. For which values of $n$ does the first player have a winning strategy if we change the rules so that now each player must choose 1, 2, 3, or 4 items from the pile.
5. We'll now change the rules and require a player to take anywhere from 1 to $k$ objects each turn. Conjecture the values of $n$ for which the first player has a winning strategy.

Problem 2 (The Game Of Scoring Misere)

A misere game is a game played by the regular rules with one change; whoever wins the game according the regular rules is the loser. Consider again the game of Scoring, but this time we'll play it as a misere game.

1. For which values of $n$ does the first player have a winning strategy when playing misere, provided each player must take 1, 2, or 3 objects?
2. For which values of $n$ does the first player have a winning strategy when playing misere, provided each player must take 1, 2, 3, or 4 objects?
3. If instead a player must take between 1 and $k$ objects, conjecture the values of $n$ for which the first player has a winning strategy when playing misere.

Definition (Encryption Key)

An encryption key is an algorithm which specifies how a message is to be encoded. The encrypted message is often called ciphertext. The original message is called plain text. See Wikipedia for more information.

Definition (Simple Shift Permutation Of The Alphabet)

Let $M$ be a message, which we will think of as a sequence of letters from the standard 26 letter Roman alphabet. We can write $M=(m_1,m_2,m_3, \ldots, m_n)$ where $m_i\in\{a, b, c, \ldots, z\}$. For simplicity, our messages are not case-sensitive and all spaces and punctuation have been removed. To send the phrase "Let's meet at dawn." we'd just use the plain text message $M=(l,e,t,s,m,e,e,t,a,t,d,a,w,n)$.

We now define an encryption key to produce ciphertext from a message $M$. Given a message $M=(m_1,m_2,m_3, \ldots, m_n)$, let $\phi_3(m_i)$ be the letter in the alphabet that has been shifted three right from the current letter. When we hit the end of the alphabet, we'll wrap around so that shifting $z$ right one gets us to $a$. Let's call this the simple shift permutation $\phi_3$. So we now have $\phi_3(a)=d$, $\phi_3(m)=p$, and $\phi_3(z)=c$. In a similar manner, we can define the simple shift permutation $\phi_n$ which shifts each letter right $n$ units.

Problem 3 (First Encryption Key)

Suppose you encounter some ciphertext $(i,q,x,x,p,a,z,q)$ that you know has been encrypted using a simple shift permutation $\phi_n$ for some $n$.

1. Decode the ciphertext and state the original message. State the value of $n$ that was used to encode the original message.
2. Encode the plain text message "attack at dawn" into ciphertext using the same encryption key you discovered in the first part.
3. Are there any other $n$ that would have produced the same results as above? Be ready to fully justify your answer.

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.

Definition (Permutation)

Let $X$ be a set. A $\textdef{permutation}$ of $X$ is a bijection from $X$ to $X$, so it's a function from $X$ into $X$ that is both one-to-one and onto. We can think of a permutation of $X$ as a way of rearranging the elements in $X$. The identity permutation is the permutation $id_X:X\to X$ defined by $id_X(x)=x$.

Problem 5 (Number Of Permutations)

Given finite set $X$ with $n$ elements, how many permutations are there of $X$?

• Show that if $X=\{1\}$, then there is only one permutation of $X$.
• Show that if $X=\{1,2\}$, then there are two permutations of $X$. List them.
• Make a list of all permutations of $X=\{1,2,3\}$, and then of $X=\{1,2,3,4\}$. What pattern do you see?
• Make a conjecture about the number of permutation of $X$ if $|X|=n$. Then prove your conjecture.

Definition (Automorphism Of A Graph)

An $\textdef{automorphism of a graph}$ is a permutation $\sigma$ of the set of vertices such that two vertices $x$ and $y$ form an edge if and only if $\sigma(x)$ and $\sigma(y)$ form an edge. The $\textdef{automorphism group of a graph}$ is the set of all automorphisms of the graph. If $\mathcal{G}$ is a graph, its automorphism group is denoted $\aut(\mathcal{G})$.

Problem 6 (Automorphisms Of A Square)

Consider the graph $\mathcal{G} = (V,E)$ drawn below. The vertex set is $V = \{1,2,3,4\}$ and the set of edges is $$E = \{\{1,2\},\{2,3\},\{3,4\},\{1,4\}\}.$$

Write down all the automorphisms of $\mathcal{G}$ (there are more than 4, but less than 10). Explain how you know you have listed every automorhpism of $\mathcal{G}$.

This problem continues in AutomorphismsOfASquare2.

Problem 7 (Automorphisms Of A Square 2)

Again consider the graph $\mathcal{G} = (V,E)$ shown below with vertex set $V = \{1,2,3,4\}$ and edges $$E = \{\{1,2\},\{2,3\},\{3,4\},\{1,4\}\}.$$

Recall that set of all automorphisms of $\mathcal{G}$ is written $\aut(\mathcal{G})$. We listed all the elements in this set in problem AutomorphismsOfASquare. Determine if each statement below is true or false. Make sure you justify your answers.

1. There is an automorphism $a\in \aut(\mathcal{G})$ such that $a^2=a\circ a$ (the composition) is the identity automorphism, but $a$ is not the identity.
2. There is an $a\in \aut(\mathcal{G})$ such that $a^3=a\circ a\circ a$ is the identity but $a$ is not the identity.
3. There is an $a\in \aut(\mathcal{G})$ such that every other $b\in \aut(\mathcal{G})$ is of the form $b=a^n$ for some $n$. [Hint: for each element in $\aut(G)$, find the smallest $n$ such that $a^n=id_V$. ]
4. For every $a,b\in \aut(\mathcal{G})$, we have $a\circ b = b\circ a$.

Problem 8 (Automorphisms Of A Directed Square)

Consider the directed graph $\mathcal{G} = (V,A)$ shown below with vertex set $V = \{1,2,3,4\}$ and arrows (directed edges) $$A = \{(1,2),(2,3),(3,4),(4,1)\}.$$

1. How would you define an automorphism of a directed graph?
2. List all the automorphisms of this directed graph. You should have 4.
3. Is there is an automorphism $a\in \aut(\mathcal{G})$ such that $a^2=a\circ a$ (the composition) is the identity automorphism, but $a$ is not the identity?
4. Is there is an $a\in \aut(\mathcal{G})$ such that $a^3=a\circ a\circ a$ is the identity but $a$ is not the identity?
5. Is there is an $a\in \aut(\mathcal{G})$ such that every other $b\in \aut(\mathcal{G})$ is of the form $b=a^n$ for some $n$?
6. For every $a,b\in \aut(\mathcal{G})$, do we have $a\circ b = b\circ a$?

Problem 9(Simple Shift Repetition)

Let's now devise a way to not only encrypt a message, but also keep track of who has seen the message? There are several ways to do this. Let's look at an example that involves repeated application of the same encrpytion key. For this example, let's use the encryption key $\phi_4:S\to S$ (the simple shift permutation that shifts right 4).

A group of military commanders decide to send messages using a message chain. The message passes sequentially from one person to the next, where at each stage they apply the encryption key to the ciphertext before sending it on. If I want to send the plain text message $attackatdawn$, then I'd send the message $exxegoexhear$ to the person after me in the chain. This person would decipher the text using $\phi_4^{-1}$ (shift left 4), and then apply $\phi_4$ to the cipher text $exxegoexhear$ and then send the ciphertext $ibbiksibliev$ to the person after them in the chain. This would repeat until the message made it to every commander.

1. You receive the cipher text $skkzgzkomnz$. What is the plain text message? How many people have seen this message?
2. How many commanders can we include in this encryption scheme and still tell who sent the message?
3. If we use $\phi_5$ instead of $\phi_4$, how many commanders can we include in this encryption scheme and still tell who sent the message?
4. Is there an encryption key $\phi_n$ so that $\phi_n^2=\phi_0$. In other words, is there an encryption key $\phi_n$ that will only allow up to two commands to be in the chain?

Problem 10 (Cryptography Reading Assignment)

Download the free open source book Abstract Algebra: Theory and Applications by Thomas W. Judson. See http://abstract.ups.edu/. (For a direct link use http://abstract.ups.edu/download/aata-20160809.pdf .)

1. Read pages 76-81. This is chapter 7, Introduction to Cryptography. It's OK if you don't understand all the notation.
2. Come with at least three questions about parts of the reading you would like to understand more about.

It's OK if you don't understand all of the reading. He uses some theorems and notation that we have not yet covered. If you want to know more about how some of the things worked in the reading, please make sure you ask a question.

Once we have a set of permutations, we'd like to be able to combine them to get new permutations. The previous problem used repetition on simple shift permutations of the alphabet to obtain additional permutations. The next problem has you show that the composition of any finite collection of permutations on a set is always a permutation.

Theorem (The Composition Of Permutations Is A Permutation)

Let $X$ be a set. Suppose that $\sigma_1, \sigma_2, \ldots,\sigma_k$ are permutations of $X$. Then the composition $\sigma_1\circ \sigma_2\circ \ldots\circ \sigma_k$ is a permutation of $X$.

Problem 11 (The Composition Of Permutations Is A Permutation)

Prove theorem (The Composition Of Permutations Is A Permutation). As some reminders, you may use the following facts that you proved in either Math 301 or Math 340. You may use these facts without proof.

• The composition of two injective functions is injective.
• The composition of two surjective functions is surjective.
• A function is a bijection if it is both injective (1 to 1) and surjective (onto). Hence, the composition of two bijective functions is a bijection.
• You might find induction helps you get from a composition of two bijective functions is bijective to the composition of $n$ bijective functions is bijective.

Remember, anytime you see a new theorem, definition, idea, etc., start by making an example, and a non example. If someone in class wants to see an example, I'd love to have you share your work there.

Problem 12 (Do We Need The Associative Law)

In this problem, your job is to explain each step in the process of solving $2x=3$ for $x$. Try to break each part of your computation down into the most basic processes. The only two operations we have on the real numbers are addition and multiplication. Subtraction and division are inverse operations, so rather than saying "divide by 2", you would multiply by the multiplicative inverse of 2. As always, write your solution using complete sentences.

• If you did not use the associative law of multiplication in your work, then go back through your work. It should be there somewhere.
• Did you use the commutative law of multiplication in your work? If you did, make sure you pinpoint where you did. It is possible to solve this problem without the commutative law.
• You might try to justify this as follows:
  First divide both sides of $2x=3$ by 2. Then cancel the 2's on the left side of the equation and we have $x=3/2$.

Exercise (Simple Matrix Encryption)

Consider the matrix $A = \begin{bmatrix} 2&1&-1\\ 5&2&-3\\ 0&2&1\end{bmatrix}$. Joe decides to send a message to Sam by encrypting the message with the matrix $A$. He first takes his message and converts it to numbers by replacing A with 1, B with 2, C with 3, and so on till replacing Z with 26. He uses a 0 for spaces. After replacing the letters with numbers, he breaks the message up into chunks of 3 letters. He then multiplies each chunk of 3 by the matrix $A$, resulting in a coded message. For example, to send the message "good job ben" he firsts converts the letters to the numbers and places them in a large matrix $M$ (top to bottom, left to right) $$ \left[ \begin{bmatrix}g\\o\\o\end{bmatrix}, \begin{bmatrix}d\\ \ \\ j\end{bmatrix},\begin{bmatrix}o\\b\\\ \end{bmatrix},\begin{bmatrix}b\\e\\n\end{bmatrix}\right] \rightarrow \left[\begin{bmatrix}7\\15\\15\end{bmatrix}, \begin{bmatrix}4\\0\\10\end{bmatrix},\begin{bmatrix}15\\2\\0\end{bmatrix},\begin{bmatrix}2\\5\\14\end{bmatrix}\right] = M= \begin{bmatrix} 7 & 4 & 15 & 2 \\ 15 & 0 & 2 & 5 \\ 15 & 10 & 0 & 14 \end{bmatrix} .$$ To encode the matrix, he computes $$AM = \begin{bmatrix} 14 & -2 & 32 & -5 \\ 20 & -10 & 79 & -22 \\ 45 & 10 & 4 & 24 \end{bmatrix}.$$ and then sends the numbers \([ [ 14, 20, 45], [ -2, -10, 10], [ 32, 79, 4], [ -5, -22, 24] ]\) to Sam. Sam uses the inverse of $A$ to decode the message.

1. Use $A^{-1}$ to decode \([ [ 14, 20, 45],[ -2, -10, 10],[ 32, 79, 4],[ -5, -22, 24] ]\) and show the message is "good job ben."
2. Decode the message \([[39, 89, 22],[20, 48, 4],[39, 88, 33]]\). The answer should let you know you did a good job.

Recall that given a set of vectors $S=\{\vec v_1, \vec v_2,\ldots, \vec v_k\}$, a linear combination of these vectors was a sum of the form $$c_1\vec v_1+c_2\vec v_2+\cdots+c_k\vec v_k.$$ The span of a set of vectors is the set of all linear combinations of the vectors. In linear algebra we took a small set of vectors and spanned the vectors to create vector spaces. We defined the span of $S$ to be the set of all linear combinations of vectors in $S$.

Given a permutation, we've shown that we can use function composition to create new permutations. If $S$ is a set of permutations on $X$, we'd like to have a way to talk about combining the permutations. Instead of multiplying by a scalar and adding, we'll decide how many times to repeatedly apply the function, and then compose different functions together.

Definition (Composition Combination Of Permutations)

Let $X$ be a set, and $S$ be a set of permutations of $X$.

• If $\sigma$ is a permutation of $X$, we'll use exponential notation to express repeated composition of $\sigma$. This gives us $\sigma^2=\sigma\circ \sigma$ and $\sigma^5=\sigma\circ\sigma\circ\sigma\circ\sigma\circ\sigma$, etc.
• We'll use negative exponents when we want to repeated apply an inverse, which gives us $\sigma^{-n}=\left(\sigma^{-1}\right)^n$.
• A composition combination of permutations in $S$ is a composition of the form $$\sigma_1^{n_1}\circ\sigma_2^{n_2}\circ\cdots\circ \sigma_k^{n_k},$$ where $k\in\mathbb{N}$, each $\sigma_i\in S$, and each $n_i\in \mathbb{Z}$ for $i\in \{1,2,3,\ldots,k\}$.
• The span of $S$, written $\text{span}(S)$ is the set of all composition combinations of permutations in $S$. We'll say that the set $S$ generates $\text{span}(S)$.

As an example, if $S=\{a,b,c,d\}$ is a set of permutations of $X$, then the composition $a^2\circ b^{-1}\circ c^3$ is a composition combination of permutations in $S$, and so are $d^{-3}$, $b^5\circ a^{-2}$, and more.

Problem 13 (Simple Shift Repetition Game)

Consider the set of simple shift permutations $H=\{\phi_n\mid n\in \mathbb{Z}\}$ on a 26 letter alphabet. We've shown that there are 26 different functions in this set. Consider the following game.

• The first player picks an element $\sigma_1\in H$. They then remove from $H$ the span of $\sigma_1$ (so everything generated by $\{\sigma_1\}$).
• The second player now chooses an element $\sigma_2\in H$ that hasn't yet been removed. They then remove from $H$ any element in the span of $\{\sigma_1,\sigma_2\}$. At this stage, any permutation that can be written as a composition combination of the permutations $\sigma_1$ and $\sigma_2$ has been removed.
• Players alternate taking turns, choosing an element $\sigma_k\in H$ that hasn't been removed in a previous stage, and then removing from $H$ any element in the span of $\{\sigma_1,\sigma_2,\ldots,\sigma_k\}$.
• Whoever take the last element of $H$ wins. The game can also be played as a misere game.

Answer the following questions.

1. Player 1 takes $\phi_6$. Which elements should be removed from $H$
2. Is there a way for player 1 to win on the first move? Explain.
3. What's the largest number of turns that can occur in this game (so if neither player tries to win, how long can the game go on)?
4. If we play this as a misere game, does player 1 have a winning strategy?

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.

Much of our work up to this point has been based on the ability to compute a remainder. This is all based on the Division Algorithm.

Theorem (Division Algorithm)

Let $a,n\in\mathbb{Z}$, with $n> 0$. Then there exists unique integers $q$ and $r$ (called the quotient and remainder) such that $a=qn+r$ where $0\leq r<n$.

Problem 15(Division Algorithm Proof)

Prove the Division algorithm.

One of our main uses of the division algorithm is modular arithmetic.

Definition (Modular Arithmetic)

Let $a,b,n\in \mathbb{Z}$ with $n>0$. We say that two integers $a$ and $b$ are congruent mod $n$, and write $a \mod n= b\mod n$, if they have the same remainder after dividing by $n$. If $a=qn+r$ where $r$ is the remainder after dividing by $n$, then we'll often write $r=a\mod n$. There are lots of ways to denote this in the literature. We might say $r\equiv a\mod n$, $r=a\pmod n$, $a\mod n \equiv b \mod n$, and more.

Problem 16(Remainders Equal Iff Difference Is A Multiple)

Let $a,b,n\in\mathbb{Z}$ with $n>0$. Prove that $a\pmod n = b \pmod n$ if and only if $a-b$ is a multiple of $n$.

Many encryption algorithms depend entirely on modular arithmetic. The RSA public key encryption algorithm requires that we compute extremely large powers of rather large numbers. For example, we might need to compute $2348971^{986871578457358918334698187}$. This can be an expensive operation, unless we find some patterns to help us. The next problem provides a beginning at doing this.

Problem 17(Computing Powers Modn Conjecture)

We need to be able to compute $a^k\pmod n$.

1. Compute $2^k\pmod 5$ for $k=1,2,3,4,5,6,7$. What pattern do you see. What is $2^k\pmod 5 $ for $k=257$ and for $k=49827512$.
2. Compute $5^k\pmod {11}$ for $k=1,2,3,4,5,6,7,8,9,10,11,12$. Can you discover a pattern. What if $k=3047$ or $k=478209183234$?
3. Make a conjecture about $a^k\pmod n$. Come up with a different example to back your conjecture.

We need a common notation to talk about permutations. If $\sigma$ is a permutation of $X=\{1,2,3,4,5,6\}$, then we could use the matrix notation $ \sigma= \begin{bmatrix}1&2&3&4&5&6\\2&4&6&1&5&3\end{bmatrix} $ to represent the permutation $$ \sigma(1)=2,\sigma(2)=4,\sigma(3)=6,\sigma(4)=1,\sigma(5)=5,\sigma(6)=3 $$ Alternately, we could look at cycling patterns that occur in the permutation and write $1\to 2\to 4\to 1$ and then stop because at this point the cycle repeats. We'd also need to write $3\to 6\to 3$ and $5\to 5$, though if we left the $5\to 5$ part off we could assume that 5 did not change. Rather than writing the arrows, we'll represent this permutation by writing $\sigma=(1,2,4)(3,6)(5)$, or leaving off the fact that 5 maps to itself we could just write $\sigma=(1,2,4)(3,6)$. We can use this notation to express any permutation. We need a formal definition for this cycle notation. You can read more about disjoint cycle notation on page 98 in Gallian's Contemporary Abstract Algebra.

Definition (Disjoint Cycle Notation)

Let $X=\{1,2,3,\ldots ,n\}$ for some positive integer $n$. Let $\sigma$ be a permutation which we have written in the matrix form $ \sigma= \begin{bmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{bmatrix}. $ Let $a_1\in X$ (often we choose $a_1=1)$ and then compute $\sigma(a_1),\sigma^2(a_1),\sigma^3(a_n),\ldots, \sigma^{k_1}(a_n)$ until the next application of $\sigma$ returns $a_1$. This gives the first cycle (vector) $\alpha_1=(a_1,\sigma(a_1),\ldots,\sigma^{k_1}(a_1))$. We then pick $a_2\in X$ so that $a_2$ is not an entry in $\alpha_1$, and repeat this process to obtain a second cycle $\alpha_2=(a_2,\sigma(a_2),\sigma^2(a_2),\ldots,\sigma^{k_2}(a_2))$. We then pick $a_3\in X$ so that $a_3$ is not an entry in $\alpha_1$ nor $\alpha_2$, and repeat the process to obtain the cycle $\alpha_3$. At each stage we pick a new element $a_k\in X$ that is not an entry in any of $\alpha_1,\alpha_2,\ldots, \alpha_{k-1}$, and then repeatedly apply $\sigma$ to obtain the cycle $a_k$. The process stops when every element of $X$ is in $\alpha_k$ for some $k$. We then write $$\sigma=\alpha_1\circ\alpha_2\circ\cdots \circ \alpha_m = \alpha_1\alpha_2\cdots\alpha_m$$ where $m$ is the number of cycles needed to represent the permutation. Whether we include the composition symbol or not is a matter of preference.

We will often omit writing singleton vectors $(a)$. So if $X=\{1,2,3,4\}$, then instead of writing $(1)(2,3)(4)$, we'll just write $(2,3)$. The permutation $(2,3)$ does not change the elements $1$ and $4$, so we omit writing them. The identity permutation would be $(1)(2)(3)(4)$. We could omit all singletons which would leave us with nothing, so in this case we'll write $()$ to represent the identity permutation.

Problem 18(Disjoint Cycle Notation Practice With Automorphisms Of A Square)

We have already shown that there are 8 automorphisms of the graph below.

Write each of these automorphism using disjoint cycle notation. As an example, the automorphism that leaves 1 and 3 unchanged, but swaps 2 and 4, we write as $(1)(2,4)(3)$.

Problem 19(Automorphisms On Several Graphs With 4 Vertices)

Consider the two graphs below.

1. For each graph, list the automorphisms of the graph. Use disjoint cycle notation to represent each automorphism.
2. For each automorphism, state the smallest positive value of $k$ for which $\sigma^k$ is the identity automorphism. This is called the order of the automorphism.
3. Construct another graph on 4 vertices different than the three we have seen so far. How many automorphisms does this graph have? Explain.

Exercise (The Product Of The GCD And LCM)

Prove that for positive integers $m$ and $n$, we always have $mn=\gcd(m,n)\text{lcm}(m,n)$, in other words the product of the greatest common divisor and least common multiple of two natural numbers is always the same as their product.

Definition (The Order Of A Permutation)

The order of a permutation $\sigma$ is the smallest positive integer $n$ such that $\sigma^n$ equals the identity permutation.

Definition (The Game of Permutation Scoring also called Generate/Don't Generate)

Just as in the Simple Shift Repetition Game, we can play a similar game with any set of permutations of the same set $X$. Let $H$ be a set of permutations of a set $X$. We'll generally assume that the set $X$ is finite so that the game is guaranteed to end. However, you can play this game with an infinite set $X$.

Here are the rules.

• The first player picks an element $\sigma_1\in H$. They then remove from $H$ the span of $\{\sigma_1\}$ (so everything generated by $\sigma_1$).
• The second player now chooses an element $\sigma_2\in H$ that hasn't yet been removed. They then remove from $H$ any element in the span of $\{\sigma_1,\sigma_2\}$. At this stage, any permutation that can be written as a composition combination of the permutations $\sigma_1$ and $\sigma_2$ has been removed.
• Players alternate taking turns, choosing an element $\sigma_k\in H$ that hasn't been removed in a previous stage, and then removing from $H$ any element in the span of $\{\sigma_1,\sigma_2,\ldots,\sigma_k\}$.
• Whoever takes the last element of $H$ wins.

There are several variations:

• The game can also be played as a misere game, where whoever takes the last element of $H$ wins.
• You win by taking the last element. However, you cannot take the last element unless there are no other legal choices. So you can't try to win, rather you must be forced to win.

Problem 20(The Game Of Permutation Scoring On A Square)

Let's play the game of scoring on the automorphism group of the square. We know there are 8 automorphism. Play this game a few times to get a feel for what different choices will give.

1. Show there is no way for player 1 to win on the first move.
2. If player 1 takes any of the flips for their first move, what should player 2 choose to win the game?
3. Does player 1 have a winning strategy? What is it?

It would be nice if we could create a way to visually keeping track of which elements of $H$ have been taken. Let me describe how we can do this with an example. Suppose you are playing the game on a square (as above). Player one takes the permutation $(1,2,3,4)$. Then player $2$ chooses the element $(1,2)(3,4)$. Here's how we make the graph.

• Each element in $H$ will represent a vertex.
• When player 1 chooses $(1,2,3,4)$, pick a color (I'll choose red) and then draw a red arrow from each permutation $\sigma\in H$ to the permutation $(1,2,3,4)\circ \sigma$. In other words, we're going to draw a graph that shows what happens if we apply the automorphism $(1,2,3,4)$ after doing any other automorphism. If we start at the identity permutation $()=(1)(2)(3)(4)$, then we have $(1,2,3,4)\circ ()=(1,2,3,4)$, so we draw a red arrow from $()$ to $(1,2,3,4)$. Similarly, starting at $(1,2,3,4)$ we draw an arrow to $(1,2,3,4)\circ(1,2,3,4)=(1,3)(2,4)$. Continuing in this fashion for each permutation gives us the graph below, with two red cycles of 4.

• The elements that are removed after choosing $(1,2,3,4)$ are any elements that we can get to by following a path that contains $(1,2,3,4)$. These are the 4 automorphisms in the cycle on the left.
• Now player 2 chooses $(1,2)(3,4)$. We now use a different color (I chose blue in the example below), and then at each vertex draw an arrow starting at $\sigma\in H$ and ending at $(1,2)(3,4)\circ \sigma$. The tricky part is finding a nice way to draw the graph without to many edge crossings (do you see how the outer circle flipped directions). Both of the examples below are ways to represent this graph. We can use an edge with an arrow on each end to illustrate that there is an arrow going both ways.

• The arrows in the graph above represent composition by either $(1,2,3,4)$ or $(1,2)(3,4)$. If you start at $(1,3)$ and want to compute $(1,2,3,4)\circ(1,2)(3,4)\circ(1,3)$, then you just have to start at $(1,3)$, follow the blue arrow to get to $(1,2)(3,4)\circ(1,3)=(1,4,3,2)$, and then follow the red arrow to get to $(1,2,3,4)\circ(1,4,3,2)$.

The mathematical program Sage can also help with the computations. The command PermutationGroup() below creates the span of the permutations listed. The command cayley_graph() creates the graph described above, but only shows the part of the graph that contains the permutations listed. Try executing the block of code below.

g1 = PermutationGroup(["(1,2,3,4)"])   #The set g1 is the span of the permutations listed.
d1=g1.cayley_graph()                   #This creates the Cayley graph of the g1. 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True) #This shows the Cayley graph. 
print(g1.list())                       #This print a list of the elements in g1. 

g2 = PermutationGroup(["(1,2,3,4)", "(1,2)(3,4)"])
d2=g2.cayley_graph()
d2.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)
print(g2.list())

Problem 21 (Composing Permutations Using Disjoint Cycle Notation)

Let $R_{90}=(1,2,3,4)$ and $H=(1,2)(3,4)$.

1. Express the compositions $R_{90}\circ H$ and $H\circ R_{90}$ in cycle notation. Be prepared to explain how you computed this.
2. Express the compositions $R_{90}\circ (1,3)$ and $H\circ (1,3)$ in cycle notation. Can you see these products in the graph above?
3. Express the composition $(1,2,4)\circ (1,4)(2,3)\circ (2,4)$ in cycle notation. Note that $(1,2,4)$ is not an automorphism of the square, but is a permutation.
4. Evalute the Sage command below. In the second graph below you should see that starting at $()$ and following the colored arrows corresponding to $(2,4)$ and then $(1,4)(2,3)$ gets you to the element $(1,4,3,2)$ which is precisely the composition $(1,4)(2,3)\circ (2,4)$. In the third graph below, if you start at the identity $()$ and the follow the colored arrow corresponding to $ (2,4)$, and then $(1,4)(2,3)$, and then $(1,2,4)$, you should end up at the same spot as you did in part 3. Click evaluate again if the graph you have is hard to read (as the graph will redraw).

g1 =  PermutationGroup(["(2,4)"])      #The set g1 is the span of the permutations listed.
d1=g1.cayley_graph()                   #This creates the Cayley graph of the g1. 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True) #This shows the Cayley graph. 
print(g1.list())                       #This print a list of the elements in g1. 

g2 = PermutationGroup(["(2,4)","(1,4)(2,3)"]) 
d2=g2.cayley_graph()
d2.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)
print(g2.list())

g3 = PermutationGroup(["(2,4)","(1,4)(2,3)", "(1,2,4)"]) 
d3=g3.cayley_graph()
d3.show(color_by_label=True, vertex_size=0.03, vertex_labels=True,figsize=8)
print(g3.list())

Problem 22 (Creating Cayley Graphs Of Simple Shift Permutations)

Let's make some Cayley graphs as they relate with the game of Scoring on simple shift permutations. To get Sage to make the graphs, you'll first have to write the simple shift permutation in disjoint cycle notation. As an example, if there are 6 letters in our alphabet $X=\{1,2,3,4,5,6\}$, then we could write the simple shift $\phi_2$ as $(2,4,6)(1,3,5)$. If player 1 chooses $\sigma_1=\phi_2$ and player 2 chooses $\sigma_2=\phi_3$, then the following Sage code visually provides a graph of $\text{span}(\{\sigma_1\})$ and then $\text{span}(\{\sigma_1,\sigma_2\})$.

g1 =  PermutationGroup(["(2,4,6)(1,3,5)"])    
d1=g1.cayley_graph()                                                 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)   
print(g1.list())                                                     

g2 = PermutationGroup(["(2,4,6)(1,3,5)","(1,4)(2,5)(3,6)"]) 
d2=g2.cayley_graph()
d2.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)
print(g2.list())

By hand, my first graph would contain two unconnected triangles. My second graph would look similar to the graph above.

1. Suppose the alphabet is $X=\{1,2,3,4,5,6\}$. Player 1 chooses $\phi_1$. Draw the associated graph.
2. Suppose the alphabet is $X=\{1,2,\ldots,10\}$. Player 1 chooses $\phi_5$. Player 2 chooses $\phi_4$. Draw the two associated graphs.
3. Suppose the alphabet is $X=\{1,2,\ldots,12\}$. Player 1 chooses $\phi_5$. Draw the associated graph.
4. Suppose the alphabet is $X=\{1,2,\ldots,12\}$. Player 1 chooses $\phi_6$. Player 2 chooses $\phi_2$. Player 1 then chooses $\phi_3$. Draw the three associated graphs. The first graph should consist of 6 arrows between pairs of vertices (Sage will only show you the segment connnecting $()$ and $\phi_6$). Your second graph should have 2 hexagons with arrows crossing in the middle. The last graph should connect the edges of the hexagons.

Here's a blank Sage cell that you can use to perform some computations. You'll probably want to copy code from above and make some changes.

When we create graphs with Sage, it always creates a graph of the span of the permutations given. These graphs have a lot of really nice symmetry properties, and these properties are central to abstract algebra.

Problem 23 (Permutation Scoring On S 3)

Consider the game of permutation scoring on the set $S_3$, where $S_3$ represents the set of all permutations of $X=\{1,2,3\}$. We already know that there are 6 elements in $S_3$.

1. Play the game of permutation scoring on $S_3$. Play it a few times.
2. Can player 1 win by choosing a single permutation in $S_3$?
3. Does player $1$ have a winning strategy? What is it?
4. Pick an element in $S_3$ other than the identity, and call it $\sigma$. Let $S=\text{span}(\sigma)$. What is the span of $S$?
5. Repeat part 4 with a different element of $S_3$. You can use Sage to make this part fast (first compute the span of $\sigma$ with Sage. The list below the graph gives you the elements of the span. Then create a graph using these elements.
6. Make a conjecture.

Definition (A Closed Set Of Permutations)

We say that a set of permutations is closed if the set $S$ is equal to its span, so notionally we write $$S=\text{span}{(S)}.$$ In other words, we say that $S$ is closed if the set $S$ already contains every composition combination of permutations of elements in $S$.

Problem 24 (The Span Of A Set Of Permutations Is Closed)

Let $S$ be a set of permutations of $X$. Show that $\text{span}(S)$ is closed. In other words, show that once you form the span of a set $S$ of permutations of $X$, you cannot obtain any new permutations by spanning the span. For this reason, we'll often refer to $\text{span}(S)$ as the closure of $S$.

We'll be using modular arithmetic in a lot of things that we do throughout the semester. Let's invent a notation to help us talk about modular arithmetic.

Definition (The Set ZN Of Integers Mod N)

For each positive integer $n$, let $\mathbb{Z}_n=\{0,1,2,\ldots, n-1\}$ which is the same as $\mathbb{Z}_n = \{k\mod n\mid k\in \mathbb{Z}\}$. This is just the set of remainders when dividing by $n$. We'll refer to them as the integers modulo $n$, or the integers mod $n$.

Question

Take a look at the last question of The Set Of Simple Shift Permutations. Does this definition look familiar?

In previous problems, we've been using without proof some facts about modular arithmetic, namely that we can perform addition and subtraction either before or after we compute a remainder. Let's prove this is true.

Problem 25 (Modular Arithmetic Properties)

Let $n$ be a positive integer. Let $a,b\in \mathbb{Z}$.

1. Show that $((a \mod n)+(b\mod n))\mod n = (a+b)\mod n$. In other words, show that the sum of the remainders has the same remainder as the original sum.
2. Show that $((a \mod n)(b\mod n))\mod n = (ab)\mod n$. In other words, show that the product of the remainders has the same remainder as the original product.

Remember, you'll want to use the division algorithm to obtain quotient and remainders when dividing $a$, $b$, $ab$, and $a+b$ by $n$. You'll need to use the problem, Remainders Equal Iff Difference Is A Multiple, to complete your work.

Problem 26 (Powers With Modular Arithmetic)

1. We know that $481\mod {483} =(-2)\mod {483}$. Use this fact to quickly compute $481^2\mod{483}$ without a calculator. [How can you use the $-2$ to simplify this?]
2. Using the same idea, what is $481^{3}\mod{483}$ and $481^4\mod{483}$? You should be giving a positive integer less than 483 for all your answers.
3. Explain why $12\cdot 16 \mod 17$ is the same as $(-5)(-1)\mod 17$.
4. Now compute $14^k \pmod {17}$ without a calculator for as many values of $k$ as needed until you find a repeating pattern. See the hint below.

Let me give you a suggestion. Rather than trying to compute $14^4$, instead first compute $14^2$ by considering $(-3)^2$. To compute $(14)^3$, instead use the product $(14)^2(14)=(9)(-3)=(-8)(-3)$. Use your work from the previous power to figure out the next power. If you try to do this with brute force, it gets outrageously large really fast. If you swap from positive to negative values when the numbers get large (above 8), you should be able to do this without ever needing long division. You should find that no product ever gets above 24.

The following Sage code will compute powers with modular arithmetic. You are welcome to check your answers with this, but the whole point to the problem is to learn how to simplify the computations by hand. To compute $a^m\mod n$ you would write "power_mod($a$,$m$,$n$)."

power_mod(481, 4, 483)

Problem 27 (Matrix Encryption Mod 5)

In the Problem (Simple Matrix Encryption), we took a plain text message written in columns of a matrix $M$ and a matrix $A$ and used the product $AM$ to encode a message. Let's now combine matrix encryption with modular arithmetic to obtain a new encryption scheme. Once we have done this, we'll be one step closer to understanding modern encryption techniques. To simplify our work, let's use a small alphabet consisting of 5 letters. Instead of using the set $S=\{a,b,c,d,e\}$, let's just use numbers for our letters and we'll consider the alphabet $S=\{0,1,2,3,4\}=\mathbb{Z}_5$. Given the plain text "bad bed" or "10 31 43", we can encode it in the columns of the matrix $$M=\begin{bmatrix}1&3&4\\0&1&3\end{bmatrix}.$$ An 2 by 2 encryption key using coefficients mod 5 is a 2 by 2 matrix $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ where $a,b,c,d\in \mathbb{Z}_5$. Here are the steps to our encryption scheme.

• First convert the plain text to a matrix $M$ where the letters are place in the matrix top to bottom, column by column.
• Take the encryption key $A$ and compute the product $AM$.
• Reduce all the entries in $AM$ mod 5. So the cipher text only consists of the numbers in $\mathbb{Z}_5$.

Answer the following questions.

1. Suppose we let $A=\begin{bmatrix}4&2\\1&3\end{bmatrix}$. Why is this matrix not suitable as an encryption key? (Hint: what is the determinant, and why is that a problem?)
2. Suppose we let $A=\begin{bmatrix}2&1\\4&3\end{bmatrix}$. The inverse of $A$ if we ignore modular arithmetic is $\frac{1}{2}\begin{bmatrix}3&-1\\-4&2\end{bmatrix}$. We know that we can replace $-4$ with $1$ when working modular 5. Similarly we can replace $-1$ with a positive number. We need to find the multiplicative inverse of 2 when working modular 5. Find a value $b\in \mathbb{Z}_5$ so that $2b\mod 5=1$. This number $b$ is the inverse of $2$ modular 5.
3. State a matrix $B$ with coefficients in $\mathbb{Z}_5$ so that $AB$ is the identity matrix after reducing each entry mod 5. Actually perform the product by hand, and show how this matrix product reduces to the identity.

Definition (Modular Multiplicative Inverse and $U(n)$)

Let $n$ be a positive integer, and let $a\in \mathbb{Z}_n$. Then the modular multiplicative inverse of $a \mod n$ is an integer $b\in \mathbb{Z}_n$ such that $(ab)\mod n=1$. If such an integer exists, then we'll write $a^{-1}\mod n$ to represent the modular multiplicative inverse. If the context is clear, we may just refer to this as the inverse instead of the modular multiplicative inverse. We'll use the notation $U(n)$ to represent the set of elements in $\mathbb{Z}$ that have a modular multiplicative inverse. Notationaly, we write $$U(n)=\{a\in\mathbb{Z}_n\mid \text{ there exists } b\in \mathbb{Z}_n \text{ such that } (ab)\mod n=1\}.$$

The Sage code "inverse_mod(a,n)" will compute the modular multiplicative inverse of $a\mod n$ or return an error.

inverse_mod(7, 11)

Problem 28 (Computing Multiplicative Inverses For Small N)

To use modular arithmetic in matrix encryption, we must be able to find the modular multiplicative inverse of $a \mod n$. For each $n\leq 13$ and $a\in \mathbb{Z}_n$, we now compute the inverse of $a\mod n$ or explain why it does not have one.

1. Why does $0\mod n$ never have an inverse?
2. What is the multiplicative inverse of $1\mod n$?
3. For $n=3$, what is the multiplicative inverse of $a=2$.
4. For $n=4$, show that 2 does not have an inverse by computing $2\cdot 0$, $2\cdot 1$, $2\cdot 2$, and $2\cdot 3$ all modulo $4$. What is $3^{-1}\mod 4$?
5. For each $n$ between 5 and 13, create a table that shows the inverse of each $a\in \mathbb{Z}_n$. List the elements of $\mathbb{Z}_n$ along the top row, and beneath each element list the multiplicative inverse, or cross off the number if there is no multiplicative inverse.

When you are done you should have a list of the elements of $U(n)$ for each $n$ up to 13, as well as the inverse of each element in $U(n)$. Do you see any patterns?

For $n=9$, you should obtain a table somewhat similar to the following table.

Definition (Cayley Graph Of A Span Of Permutations)

Let $X$ be a set. Let $S$ be a set of permutations of $X$. Then a Cayley graph of $H=\text{span} (S)$ generated by $S$, which we'll write as $(H,S)$, is a colored directed graph that satisfies the the following three properties:

1. The vertex set is $\text{span} (S)$. Each vertex corresponds to a permutation.
2. Each element $s \in S$ is assigned a unique color which we'll denote by $c_s$.
3. For each color $c_s$, and each vertex $\sigma$, we draw the colored arrow $(\sigma ,s \circ \sigma)$.

Most of the time we assume that $S$ does not contain the identity. However, if it does contain the identity, then we just draw a colored loop $(\sigma,\sigma)$ at each vertex.

Problem 29 (Cayley Graph Patterns)

In each scenario below, you should draw a Cayley graph.

1. Let $X=\mathbb{Z}$, an infinite set. Consider the permutation $\phi_1:\mathbb{Z}\to \mathbb{Z}$ defined by $\phi_1(x)=x+1$. This permutation shifts elements in $\mathbb{Z}$ right one, with no wrap around. If we let $S=\{\phi_1\}$, give a rough sketch of the Cayley graph of $\text{span}(S)$. It's a rough sketch of the graph because there are infinitely many vertices.
2. How would you change your graph in part 1 if instead you used $S=\{\phi_2,\phi_3\}$, where these are shifts right 2 and 3 respectively?
3. Suppose that $X$ is a set, and that $S$ contains a single automorphism $s$ of $X$. Suppose also that we know $s^6$ is the identity (so following the arrow colored $c_s$ 6 times will return us to where we started). Construct a Cayley graph of $\text{span}(S)$. Is there more than one right answer to this?
4. Suppose that we know $S$ contains two elements $a$ and $b$. We also know that $a^2$ and $b^4$ are both the identity. In addition, we know that $a\circ b=b\circ a$, so if we start somewhere and follow the arrows colored $c_a$ and then $c_b$, then we should end up at the same place if we followed the arrows colored $c_b$ and then $c_a$. Construct a graph that satisfies these relationships. We'll often write this as $$\left<a,b\mid a^2=id, b^4=id, a\circ b=b\circ a\right>.$$

If $X$ is a set, and $S$ is a set of permutations of $X$, then we can create a Caley graph for the span of $S$. Here's a formal definition.

Definition (Cayley Graph Of A Span Of Permutations)

Let $X$ be a set. Let $S$ be a set of permutations of $X$. Then a Cayley graph of $H=\text{span} (S)$ generated by $S$, which we'll write as $(H,S)$, is a colored directed graph that satisfies the the following three properties:

1. The vertex set is $\text{span} (S)$. Each vertex corresponds to a permutation.
2. Each element $s \in S$ is assigned a unique color which we'll denote by $c_s$.
3. For each color $c_s$, and each vertex $\sigma$, we draw the colored arrow $(\sigma ,s \circ \sigma)$.

Most of the time we assume that $S$ does not contain the identity. However, if it does contain the identity, then we just draw a colored loop $(\sigma,\sigma)$ at each vertex.

We've done this with several automorphism groups of graphs, as well as simple shift permutation groups.

Problem 30 (Cayley Graphs Of Two Automorphism Groups)

Consider the two graphs below. Let $L$ be the automorphism group of the graph on the left, and let $R$ be the automorphism group of the graph on the right.

We listed the automorphisms of the graph in Problem (Automorphisms On Several Graphs With 4 Vertices).

1. For the graph on the left, use disjoint cycle notation to state two automorphisms $\alpha,\beta\in L$ so that $\text{span}(\{\alpha,\beta\})=L$. Then draw the Cayley graph of $L$ generated by $\{\alpha,\beta\}$, i.e. the Cayley graph $(L,\{\alpha,\beta\})$.
2. For the graph on the right, use disjoint cycle notation to state two automorphisms $\alpha,\beta\in R$ so that $\text{span}(\{\alpha,\beta\})=R$. Then draw the Cayley graph of $R$ generated by $\{\alpha,\beta\}$, i.e. the Cayley graph $(R,\{\alpha,\beta\})$.

Sometimes we can create a Cayley graph of a set of automorphisms without even knowing what the sets $X$ or $S$ are. All we need to know is how many automorphisms are in $S$, and some relationships about the automorphisms. The next problem has you examine a few more Cayley graphs.

Problem 31 (Cayley Graphs From Relations)

In each scenario below, you should draw a Cayley graph.

1. Suppose that $X$ is a set, and that $S$ contains a single automorphism $s$ of $X$. Suppose also that we know $s^6$ is the identity (so following the arrow colored $c_s$ 6 times will return us to where we started). Construct a Cayley graph of $\text{span}(S)$. Is there more than one right answer to this?
2. Suppose that we know $S$ contains two elements $a$ and $b$. We also know that $a^2$ and $b^4$ are both the identity. In addition, we know that $a\circ b=b\circ a$, so if we start somewhere and follow the arrows colored $c_a$ and then $c_b$, then we should end up at the same place if we followed the arrows colored $c_b$ and then $c_a$. Construct a graph that satisfies these relationships. We'll use the notation $$\left<a,b\mid a^2=id, b^4=id, a\circ b=b\circ a\right>$$ to tell us that $S=\{a,b\}$ with the relations listed after the $\mid$.
3. Generalize your result above to draw a Cayley graph if instead of $b^4=id$ we have $b^k=id$.

If $X$ is a set, and $S$ is a set of permutations of $X$, then we already know how to create the span of $S$. In general, the span of $S$ will include more permutations than what we started with. However, sometimes we won't be able to obtain any new permutations by spanning $S$. When this happens, we say that the set of permutations is closed (under function composition). Here's a formal definition.

Definition (A Closed Set Of Permutations)

We say that a set of permutations is closed if the set $S$ is equal to its span, so notionally we write $$S=\text{span}{(S)}.$$ In other words, we say that $S$ is closed if the set $S$ already contains every composition combination of permutations of elements in $S$.

The next problem has you prove some relationships between a set of permutations $S$ and its span.

Problem 32 (Relationship Between S And Its Span)

Let $S$ be a set of permutations of $X$.

1. Prove that $S\subseteq \text{span}(S)$. In other words, we know that $S$ is always contained in its span; the span might be larger.
2. Prove that if $\text{span}(S)\subseteq S$, then $S$ is closed.
3. If $T\subseteq S$, then show that $\text{span}(T)\subseteq\text{span}(S)$.

Definition (Integer Linear Combination Of Integers)

Let $a_1, a_2, \ldots, a_k$ be $k$ integers.

• An integer linear combination of these integers is an expression of the form $$c_1a_1+c_2 a_2+ \cdots+c_k a_k$$ where each coefficient $c_i$ is an integer.
• The span of the set of integers $\{a_1, a_2, \ldots, a_k\}$ is the set of all possible integer linear combinations of these integers, namely $$\text{span}(\{a_1, a_2, \ldots, a_k\})=\text{span}(a_1, a_2, \ldots, a_k)=\{c_1a_1+c_2 a_2+ \cdots+c_k a_k\mid c_i\in \mathbb{Z} \text{ for }1\leq i\leq k\}.$$ For ease of notation, we'll often leave off the set notation when spanning a set of integers.
• If the set $S$ of integers is infinite, then we still define the span of $S$ to be the set of all integer linear combinations of integers in $S$. Hence we know $x\in S$ if and only if there exists a natural number $k$ such that $x=c_1a_1+c_2 a_2+ \cdots+c_k a_k$ where $a_i\in S$ and $c_i\in \mathbb{Z}$ for $1\leq i\leq k$.
• When there are only two integers, we'll often use $a$ and $b$ as the integers, and $s$ and $t$ as the coefficients. So the set of all integer linear combinations of $a$ and $b$ is $$\text{span}(a,b) = \{sa+tb\mid s,t\in\mathbb{Z}\}.$$

Problem 33 (Integer Linear Combination Practice)

Complete the following.

1. Compute the span of $3$, i.e. make a list of the elements in this set. In general, what is the span of a single integer $a$? (We know it by a different name.)
2. What is $\text{span}(4,6)$? List the elements. Find a single number $a$ so that $\text{span}(a)=\text{span}(4,6)$.
3. What is $\text{span}(4,5)$?
4. Let $S=\{a_1,a_2,\ldots,a_k\}$ be a set of integers. Show that if $c\in \text{span}(S)$, then so is every multiple of $c$.

We've seen a lot of relationships in class about modular arithmetic, inverses mod $n$, simple shift encryption schemes, and more. The next problem makes a connection between some of these. We'll connect it to even more next time.

Problem 34 (When Does An Integer Have A Modular Multiplicative Inverse)

Let $a$ and $n$ be integers, with $n>1$. Show that the following are equivalent.

1. The integer $a$ has a multiplicative inverse mod $n$
2. We have $1\in \text{span}(a,n)$. In other words, we can write 1 as a linear combination of $a$ and $n$.
3. We have $\text{span}(a,n)=\mathbb{Z}$. Remember that $\text{span}(a,n) = \{sa+tn\mid s,t\in\mathbb{Z}\}.$

Remember, to show that three things are equivalent you must show that each implies the other. One way to do this is show that 1 implies 2, then show that 2 implies 3, and then show that 3 implies 1. Then each implies the other.

The two problems above, together with much of our work from the previous weeks, leads us to one of the biggest theorems in number theory. We'll prove this theorem later in the semester.

Theorem (The GCD Theorem)

Let $a$ and $b$ be nonzero integers. The greatest common divisor of $a$ and $b$ is an integer linear combination of $a$ and $b$, or symbolically we have $\gcd(a,b)\in\text{span}(a,b)$. In addition, the smallest positive integer linear combination of $a$ and $b$ is $\gcd(a,b)$.

Corollary (When Are Two Numbers Relatively Prime)

Two nonzero numbers $a$ and $b$ are relatively prime (i.e. their greatest common divisor is 1) if and only if there exists $s$ and $t$ such that $sa+tb=1$.

Problem 35 (Connecting Multiples And Spans Of Integers)

Suppose that $a$ and $b$ are integers.

1. Prove that if $a$ is a multiple of $b$, then we must have $\text{span}(a)\subseteq\text{span}(b)$.
2. Is the converse of the statement above true or false? Make sure you prove your result.

Problem 36 (Permutations of $U(n)$)

Suppose $n$ is an integer greater than 1 and let $X=U(n)$, so the set of integers mod $n$ that have a multiplicative inverse mod $n$. For each $a\in U(n)$, we can define a permutation of $U(n)$ by $f_a(x)=xa\pmod n$ for each $x\in U(n)$. This problem asks you to show that this is indeed a permutation of $U(n)$. This requires that you show the following:

1. For each integer $n\geq 2$, show that if $a\in U(n)$ and $x\in U(n)$, then the product $f_a(x)=xa\pmod n\in U(n)$. This shows that $f_a:U(n)\to U(n)$ is a map from $U(n)$ to $U(n)$.
2. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is one-to-one. (As a reminder, one-to-one means that if $f_a(x)=f_a(y)$, then $x=y$.)
3. Given $n\geq 2$ and $a\in U(n)$, show that $f_a$ is onto. (As a reminder, onto means that if $y\in U(n)$, then there exists $x\in U(n)$ such that $f_a(x)=y$.)

Problem (Bonus) (The Point Group Of A Cube)

Consider a cube with vertices located at the 8 points $(\pm 1, 1,1)$, $(\pm 1, 1,-1)$, $(\pm 1, -1,1)$, $(\pm 1, -1,-1)$, and edges that connect each vertex to the three nearest points. For example, vertex $(1,1,1)$ has three edges, one connecting to each of $(1,1,-1)$, $(1,-1,1)$, and $(-1,1,1)$. We can view this as a graph whose vertices are these 8 points, along with the 12 edges. We will let $O_h$ represent the set of automorphisms of the graph of the cube.

1. How many elements are in $O_h$? Explain.
2. We will say that a set $S$ of permutations of $X$ is independent if for each $s\in S$, we have $\span (S\setminus\{s\})\neq \span (S)$. In other words, every element in $S$ is not in the span of the other permutations in $S$. Find an independent set $S$ of elements in $O_h$ so that $\span(S) = O_h$.
3. Use sage to draw the Cayley graph of $O_h$ using S. In addition show the Cayley graph of $O_h$ using $S\setminus\{s\}$ for each $s\in S$. The code provided below can do this for you, by adding and/or removing elements from $S$.
4. Challenge: Find another set $S_2$ with a different number of elements than $S$, so that $S_2$ is also an independent set whose span is $O_h$.

S = ["(1,2,3,4)(5,6,7,8)","(1,5,8,4)(2,6,7,3)"]
g = PermutationGroup(S)    
d = g.cayley_graph()                                                 
print("There are " + str(order(g)) + " elements in the graph below.")
#To see a readable list of the elements, uncomment the line below.
#print(g.list()) 
d.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)   

#We now make a graph of what happens if we remove one element.
for s in S:
    T=S[:]; #This makes a copy of S
    T.remove(s); #from which we remove s without affecting S. 
    gT=PermutationGroup(T)
    print("Removing " + s + " yields " + str(order(gT)) + " elements.")
    gT.cayley_graph().show(color_by_label=True, vertex_size=0.03, vertex_labels=True)

#The graph you create may be difficult to read in 2D. 
#Uncomment the next line to see a 3D Cayley graph. Note, it may cause your browser to hang for a moment. 
#d.show3d(color_by_label=True, vertex_size=0.03, vertex_labels=False)

For information on this group, see Wikipedia.

Problem 37 (Three Similar Cayley Graphs From Different Contexts)

This problem asks you to draw 3 Cayley graphs. Each Cayley graph should only have 4 vertices.

1. Draw a Cayley graph for the set $H_4$ of simple shift permutations of $X=\{1,2,3,4\}$ using the generating set $S=\{\phi_1\}$.
2. Then draw a Cayley graph for the span of the permutation $(1,4,3,2)$, which we wrote in disjoint cycle notation.
3. Then draw a Cayley graph for $\{f_a\mid a\in U(5)\}$ using the generating set $S=\{f_2\}$. Remember that $f_a$ is a permutation of $U(5)$ defined by $f_a(x)=xa\pmod 5$.
4. What do you notice about these Cayley graphs?

The three graphs from the previous problem look very similar, so much so that we could obtain one from the other if we just relabeled the vertex sets. This suggests that in some sense these graphs are the same. We now introduce a formal way to talk about when two graphs are the same.

Definition (Isomorphic Graphs)

Let $G$ and $H$ be two graphs, where we use $V(G)$ and $V(H)$ to denote the vertex sets. A function $f:V(G)\to V(H)$ is called an isomorphism of graphs $G$ and $H$ if $f$ is a bijection and $\{x,y\}$ is an edge of $G$ if and only if $\{f(x),f(y)\}$ is an edge of $H$ (see Wikipedia).

• We call this function $f$ an isomorphism because it "preserves the edge structure" in the graph. In general the word isomorphism refers to a bijection that preserves some kind of structure.
• If there exists an isomorphism of graphs between $G$ and $H$, then we say that $G$ and $H$ are isomorphic.
• If $G$ and $H$ are directed graphs, then an isomorphism of directed graphs would preserve the arrow structure.
• If the directed graphs $G$ and $H$ are colored, then an isomorphism also preserves the color structure, in the sense that $(a,b)$ and $(c,d)$ share the same color if and only if $(f(a),f(b))$ and $(f(c),f(d))$ share the same color.

Problem 38 (Introduction To Cayley Graph Isomorphisms)

Let $H_6 = \{\phi_0,\phi_1,\ldots,\phi_5\}$ be the set of simple shift permutations on an alphabet with 6 letters. Let $K=\{f_a\mid a\in U(7)\}$ be the set of permutations $f_a:U(7)\to U(7)$ defined by $f_a(x)=xa\pmod 7$. Let $S_3$ be the set of all permutations on $X=\{1,2,3\}$.

1. Draw the Cayley graph of $H_6$ generated by $\{\phi_1\}$. Then draw the Cayley graph of $K$ generated by $\{f_3\}$. Finally show that the function $g:H_6\to K$ defined by $$ g(\phi_0)=f_1, g(\phi_1)=f_3, g(\phi_2)=f_2, g(\phi_3)=f_6, g(\phi_4)=f_4, g(\phi_5)=f_5, $$ is an isomorphism of Cayley graphs.
2. Draw the Cayley graph of $H_6$ generated by $\{\phi_2, \phi_3\}$. Then draw the Cayley graph of $K$ generated by $\{f_2,f_6\}$. Do you believe these two Cayley graphs are isomorphic? You can just give a heuristic argument, rather than a formal proof.
3. Let $S_3$ be the set of all permutations on $X=\{1,2,3\}$. We've already shown this set has 6 permutations. Draw a Cayley graph of $S_3$ generated by the permutations $(1,2,3)$ and $(1,2)$. Do you think that this Cayley graph is isomorphic to any of the Cayley graphs above? Why?

Definition (Binary Operation)

Let $G$ be a set. A binary operation on $G$ is a way of combining two elements of $G$ to obtain a new element in $G$. Formally, we just say that a binary operation $*$ is function $*:G\times G\to G$, and we use the notation $a*b$ to represent the function notation $*(a,b)$.

You've been using binary operations your whole life.

Problem 39 (Binary Operation Introduction)

In which of the following scenarios do we have a binary operation on a set $G$. Justify your answers.

1. Addition $a+b$ of integers.
2. Multiplication $A\cdot B$ of 3 by 3 matrices.
3. The dot product $\vec u\cdot \vec v$ of two dimensional vectors.
4. The cross product $\vec u\times \vec v$ of three dimensional vectors.
5. The scalar product $c\cdot \vec v$.
6. Composition $f\circ g$ of permutations on the same set $X$.
7. Composition $f\circ g$ of functions from $X$ to $Y$.

Up to this point in the semester, we've been focusing solely on sets of permutations. Every element was a function, which often required keeping track of a bunch of information that wasn't necessary. Spanning a set of permutations gave us closed sets of permutations. We found that there are 4 key properties of a set of closed permutations. Let's now drop the requirement that we have permutations, and instead focus on sets, together with a binary operation, that satisfy these 4 properties. We call a set with these properties a group.

Definition (Group)

Let $G$ be a nonempty set, and let $*$ be a binary operation on $G$, which means for every $x,y\in G$ we have $x*y\in G$ $\textbf{[Closure]}$. The structure $\mathbb{G} = (G,*)$ is called a $\textdef{group}$ if the following hold.

1. $\textbf{[Associativity]}$ For all $x,y,z\in G$ we have $(x* y)* z = x* (y* z)$.
2. $\textbf{[Identity]}$ There is an $e\in G$ such that for all $x\in G$ we have $x * e = e* x = x$.
3. $\textbf{[Inverses]}$ For all $x\in G$ there is a $y\in G$ such that $x* y = y* x = e$.

We usually simply write $G$ when referring to the entire structure $\mathbb{G}=(G,*)$. The element $e$ from the second point is called the $\textdef{identity}$. The element $y$ from the third point is called the $\textdef{inverse}$ of $x$ and is usually denoted $x^{-1}$. One often simply writes $xy$ in place of $x*y$, and for every positive integer $n$, we'll write $x^n$ as shorthand for $x* x* \cdots * x$ ($n$ times).

We've already seen many groups throughout the semester. Since the span of any set of permutations is closed, then every time we span a set of permutations, we end up with a group. All of the patterns you have discovered about simple shift permutations, automorphisms of graphs, and more, we will be able to transfer to your understanding of abstract groups. Let's look an example, namely a group of matrices that we used before to encrypt messages.

Problem 40 (General Linear Group Introduction)

We've used matrices mod $5$ to encrypt a simple message. The set of possible 2 by 2 matrices mod $5$ that we can use as an encryption key is an important set in cryptography. It's called a general linear group and written $\text{GL}(2,\mathbb{Z}_5)$. We can generalize this to $m$ by $m$ matrices mod $n$ and write $\text{GL}(m,\mathbb{Z}_n)$, though generally we require that $n$ be a prime. With each of the problems below, a single sentence or two is enough to answer the question.

1. If we want $A$ to serve as a valid matrix for encryption, what must we require about $A$? One sentence is fine.
2. If $A\in \text{GL}(2,\mathbb{Z}_5)$, show that $A^{-1}\in \text{GL}(2,\mathbb{Z}_5)$.
3. If $A\in \text{GL}(2,\mathbb{Z}_5)$ and $B\in \text{GL}(2,\mathbb{Z}_5)$, why is $AB\in \text{GL}(2,\mathbb{Z}_5)$?
4. Prove that if we know for some integer $k$ that $A_1,A_2,A_3,\ldots,A_k \in \text{GL}(2,\mathbb{Z}_5)$, then we know $A_1A_2A_3\cdots A_k\in \text{GL}(2,\mathbb{Z}_5)$.
5. Is $\text{GL}(2,\mathbb{Z}_5)$ a group? (Which of the group properties did we not show above? Are they true?)
6. Do your arguments above hold when considering $\text{GL}(m,\mathbb{Z}_n)$ for every $m,n \in \mathbb{N}$ such that $n\geq 2$? A conjecture with a reasonable justification (not a complete a proof) is fine in this part.

In the definition of a group, it said that there exists an element $e\in G$ such that $ex=xe=e$ for each $x\in G$. It refers to this element as the identity. Could there be two such elements? Similarly, could an element have two inverses? The next problem has you show that the identity and inverses are unique.

Problem 41 (The Identity And Inverses Are Unique)

Suppose that $(G,\cdot)$ is a group.

1. Prove that the identity of the group is unique.
2. Prove that if $x\in G$, then the inverse of $x$ is unique.

Problem 42 (The GCD Theorem Proof)

Prove the GCD Theorem.

Theorem (The GCD Theorem)

Let $a$ and $b$ be nonzero integers. The greatest common divisor of $a$ and $b$ is an integer linear combination of $a$ and $b$, or symbolically we have $\gcd(a,b)\in\text{span}(a,b)$. In addition, the smallest positive integer linear combination of $a$ and $b$ is $\gcd(a,b)$.

We've spent quite a bit of time looking at modular multiplicative inverses and the sets $\mathbb{Z}_n$ and $U(n)$. Let's take a minute and explore an encryption problem that uses these sets.

Definition (Affine Encryption Key)

Suppose we have an alphabet with $n$ letters. Set up a 1-1 correspondence between the letters in your alphabet and the integers 0 to $n-1$. As an example, we could let $n=27$ for the standard alphabet with 26 letters and a space (the 27th letter which we'll number 0), and then use the correspondence in the table below.

Pick an integer $m\geq n$. Then an affine encryption key is an invertible function \( f:\mathbb{Z}_m \to \mathbb{Z}_m\) defined by $$f(x)=ax+b\pmod {m}$$ for some $a,b\in\mathbb{Z}_m$.

Problem 43 (Affine Encryption Key Introduction)

If we let $m=31$, then we can use the function $f(x)=5x+12\pmod m$ to encrypt the message "save them" by (1) swapping the letters to the numbers (19,1,22,5,0,20,8,5,13) and then (2) applying $f(x)$ to each letter to obtain the encrypted numbers (14, 17, 29, 6, 12, 19, 21, 6, 15).

1. Find $c,d\in \mathbb{Z}_{31}$ so that the inverse of $f$ is $f^{-1}(x)=cx+d$ where $c,d\in \mathbb{Z}_{31}$.
2. If instead we let $m=27$, then find the inverses of $f(x)=2x+17\pmod{27}$ or explain why it cannot be done.
3. Give an example of nonzero $a,b\in \mathbb{Z}_{27}$ so that $f(x)=ax+b\pmod{27}$ is not invertible.

You've been studying groups since you started adding integers back in grade school. Just about every idea we've encountered since the start of the semester has also been a group. Now that we have isolated the key properties that make up a group, we need to become comfortable with showing that sets with a binary operation are groups, i.e. we need to become comfortable with checking the four properties of closure, associativity, identity, and inverses.

Let's practice showing that some sets are groups by showing that $\mathbb{Z}_n$ and $U(n)$ are groups. If we already showed a key fact in a previous problem, feel free to refer to problem by name and state the fact that was proved there. We have already shown most of the reasons why the sets below are groups.

Problem 44 ($\mathbb{Z}_n$ and $U(n)$ are groups)

Show the following. You need to briefly explain why the set together with its binary operation satisfies the definition of a group.

1. For each $n\geq 1$, the set $\mathbb{Z}_n$ is a group under addition mod $n$.
2. For each $n\geq 2$, prove that $U(n)$ is a group under multiplication mod $n$.

Try to solve the problems above without looking up the definition of a group.

Because of how we defined groups, anytime we span a collection of permutations of a set $X$ we should get a group. The next problem has you show this. Each question can be answered by referring to things we have already shown.

Problem 45 (Spans Of Permutations Are Subgroups)

Let $X=\{1,2,3,\ldots,n\}$. Let $S_n$ be the set of all permutations of $X$ (so we know there are $n!$ such permutations).

1. Show that $S_n$ is a group under function composition $\circ$.
2. If $H$ is a subset of $S_n$ that is closed (under composition combinations of permutations), prove that $H$ is a group under function composition.
3. Let $S$ be a nonempty subset of $S_n$. Show that $\text{span}(S)$ is a group under function composition.

In the previous problem, we saw if $S\subseteq S_n$ then $\text{span}(S)$ is a not only just a subset of the group $S_n$, but is itself a group. The operation we use in the smaller group $(\text{span}(S),\circ)$ comes from the operation we used in the larger group $(S_n,\circ)$. Because of this close connection, we call $\text{span}(S)$ a subgroup of $S_n$ and write $\text{span}(S)\leq S_n$. Let's now make a formal definition.

Definition (Subgroup)

Let $(G,\cdot)$ be a group, and let $H$ be a nonempty subset of $G$. Then $H$ is called a $\textdef{subgroup}$ of $G$ if the following hold:

1. $\textbf{[Closure]}$ for all $h,k\in H$ we have $h\cdot k\in H$, and
2. $(H,\cdot)$ is a group.

When $H$ is a subgroup of $G$, we write $H\le G$. Any subgroup of $G$ that is not equal to $G$ itself we call a $\textdef{proper subgroup}$. The subset of $G$ consisting of just the identity we call the $\textdef{trivial subgroup}$.

Problem 46 (The Subgroup Test - Subgroups Are Subsets That Are Closed Under Products And Taking Inverses)

A graph of the first 1000 values of $\varphi(n)$. See Wikipedia.

Problem 48 (Orders Of $\mathbb{Z}_n$ And $U(n)$ And Their Elements)

We've already shown that $\mathbb{Z}_n$ under addition mod $n$ and $U(n)$ under multiplication mod $n$ are groups.

1. For each $n$ between 2 and 10, compute the order of $Z_n$ and the order of each element of $\mathbb{Z}_n$. Organize your work into a table where you first make a list of the elements, and then underneath each element state the order. For example, if $n=6$ then our table would look like the one below. $$\begin{array}{|c|c|c|c|c|c|c|} \hline \text{Element}&0&1&2&3&4&5\\\hline \text{Order}&1&6&3&2&3&6\\\hline \end{array}$$
2. For each $n$ between 2 and 10, compute the order of $U(n)$ (state $\varphi(n)$) and then compute the order of each element of $U(n)$. You can check your work with the sage code below. I kept the numbers under 10 because you can do these by hand (or in your head) fairly quickly. Make sure you do enough by hand that you feel comfortable with this process.
3. You should have noticed that $U(8)$ and $U(10)$ both have order 4. Is there a 1-1 correspondence between these two groups that matches elements with the same order?

Here's some Sage code you can use to check your computations with $U(n)$.

for n in (2..20):
 Zn = Integers(n)
 Un = [x for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
 show(table(["U("+str(n)+r") has order $\varphi($"+str(n)+"$)=$"+str(len(Un))+
             ".The elements, with orders below them, are listed below."]))
 orders=[x.multiplicative_order() for x in Un] #This computes the multiplicative order of each element.
 show(table([Un,orders])) #This creates a table of elements (top row) and their orders (bottom row).