October 2017

Please Login to access more options.

Today

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\})$.

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 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. In the problem Characterizing Closed Sets Of Permutations, we showed that any closed set of permutations is a group. 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. Feel free to look at the pages September 2016 and October 2016 for a list of all the problems we have solved each day. If you have not yet printed the work we are doing, I would suggest that you print a copy for reference as you work on new problems.

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}$.

In the proof of problem Characterizing Closed Sets Of Permutations, we did not need to use the first and fourth properties listed to show that the set of permutations $H$ was closed. The next problem replicates this, but now in terms of subgroups instead of in terms of closed sets of permutations.

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).