20131016

Please Login to access more options.

Today

Today in class we'll do the following:

• Hand in your induction proof, together with the revision.
• Have Rich prove the last problem from last time.
• View and comment on Joe's proof.

The following problem again asks you to make sure you are comfortable with the definitions of a binary operation and a group. Thanks to Justin for coming by my office and asking some questions that led to the creation of this problem. Thanks to all of you for your consistent daily effort. I'm really enjoying being your teacher. Keep up the great work.

Problem 47 (Can We Use Division To Create A Group)

Let $G=\mathbb{R}$ and $H=\mathbb{R}\setminus \{0\}$.

1. Show that division $a\div b$ is not a
   binary operation

   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)$.
   on $G$.
2. Show that division $a\div b$ is a binary operation on $H$.
3. Since division is a binary operation on $H$, determine if $(H,\div)$ is 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).
   .
   • Does $e=1$ satisfy the property of being an identity?
   • If $x\in H$, find an inverse $x^{-1}\in H$ or explain why none exists.
   • Is the operation $\div$ associative?

Just as we spanned sets of permutations, we can span subsets of a group. After defining this, we'll show that spanning a subset of a group always gets you a subgroup of the group. This should be analogous to the fact that spanning a subset of permutations leads to a closed set of permutations.

Definition (The Subgroup Generated By A Subset)

Let $G$ be a group. Suppose that $S$ is a subset of $G$.

1. A word from the alphabet $S$ is a product of the form $$x=s_1s_2\cdots s_k$$ where for each $i$ either $s_i\in S$ or $s_i^{-1}\in S$.
2. The subgroup generated by $S$ is the set of words from the alphabet $S$, namely $$\left<S\right> = \{s_1s_2\cdots s_k\mid k\in \mathbb{N} \text{ and either $s_i\in S$ or $s_i^{-1}\in S$ for each } i\in\{1,2,\ldots, k\}\}.$$
3. If $H=\left<S\right>$, then we say that $H$ is the subgroup generated by $S$, or that $S$ is a generating set for $H$.
4. If $S=\{a\}$, then we'll write $\left<a\right>$ instead of $\left<\{a\}\right>$. We call $\left<a\right>$ the subgroup generated by $a$.

We call $\left<S\right>$ the subgroup of $G$ generated by $S$, but we have not yet shown this is in fact a subgroup. The next problem has you verify this, so that we can definitely refer to $\langle S\rangle$ as a subgroup.

Problem 51 (The Subgroup Generated By S Is Actually A Subgroup)

Let $G$ be a group and $S$ be a nonempty subset of $G$. Prove that $\left<S\right>$ is a subgroup of $G$.

Definition ($|a|$ and $|G|$ - Order For Elements and Groups)

Let $G$ be a group with identity $e$, and let $g\in G$.

• The $\textdef{order}$ of $G$, denoted $|G|$, is the cardinality of $G$.
• The $\textdef{order}$ of $g$, denoted $|g|$, is the smallest positive integer $n$ such that $g^n = e$, if such an $n$ exists. If no such $n$ exists, we say $g$ has infinite order.

Definition (The Euler Phi Function)

The Euler phi function $\varphi:\mathbb{Z}\to\mathbb{Z}$ is defined by letting $\varphi(n)$ equal the order of $U(n)$.

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

Definition (Group Isomorphism)

Let $(G,\cdot)$ and $(H,\times)$ be groups. We say that the function $f:G\to H$ is a group $\textdef{isomorphism}$ if $f$ is a bijection and $f$ preserves the group structures, which means $f(a\cdot b)=f(a)\times f(b)$ for every $a,b\in G$. We say that $G$ and $H$ are isomorphic groups, and write $G\approx H$ if there exists an isomorphism between them.

When two groups are isomorphic, they must have the same order because the function $f$ is a bijection. However, not only do two isomorphic groups need to have the same cardinality, but in addition the bijection creates a correspondence between elements of the same order. Each group must have the same number of elements of each order, and any isomorphism must map an element of order $k$ to an element of order $k$. The next problem has you prove this.

Problem 68 (The Orders Of Elements Match In Isomorphic Groups)

Suppose that $f:G\to H$ a group isomorphism. Suppose that $f(g)=h$. Prove that the order of $g$ and the order of $h$ are the same, in other words show that $|g|=|h|$. In particular, since the only elements of order 1 in each group are the identities $e_G\in G$ and $e_H\in H$, then we must have $f(e_G)=e_H$.

We used Cayley graphs to give us a visual representation of the span of a set of permutations. Similarly, we can use Cayley graphs to help us visualize groups. The definition is very similar.

Definition (Cayley Graph Of A Group)

Let $G$ be a group that is generated by a set $S$. The Cayley graph of $G$ generated by $S$, which we'll write as $(G,S)$, is a colored directed graph that satisfies the the following three properties:

1. The vertex set is $G$. Each vertex corresponds to an element of the group.
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 $g$, we draw the colored arrow $(g ,s g)$.

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 $(g,g)$ at each vertex.

If the Cayley graphs of two groups are isomorphic, we would expect the groups to be isomorphic as well. We'll prove this eventually, but for now let's just use this fact to start sorting out isomorphic groups. The next problem has you look at 60+ Cayley graphs and visually start sorting groups.

Problem (Cayley Graphs and Isomorphisms between $\mathbb{Z}_n$ and $U(m)$)

In this problem, we will construct Cayley graphs of $\mathbb{Z}_n$ and $U(n)$ for many values of $n$. Our goal is to build a table of groups, where each row of the table consists of isomorphic groups.

1. Start by drawing the Cayley graphs of $\mathbb{Z}_2$, $\mathbb{Z}_3$, $\mathbb{Z}_4$, and $\mathbb{Z}_5$ using $x=1$ as the generator. What pattern do you notice?
2. If you wanted to draw the Cayley graph of $\mathbb{Z}_{50}$ using $x=1$ as the generator, what would your graph look like?
3. If $\mathbb{Z}_n\cong\mathbb{Z}_m$, what do you know about $n$ and $m$?
4. The two blocks of sage code below will draw Cayley graphs of $U(n)$ for each $n$ from 2 to 60. Evaluate each block of code now.

   for n in (2..30):
    Zn = Integers(n)
    Un = [x for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    show(table(["U("+str(n)+") has order "+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).
   
    Un = [int(x) for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    S=Zn.unit_gens()
   
    CG=DiGraph([Un,lambda i,j:False])
    for k in S:
     CGk=DiGraph([Un,lambda i,j: mod(j*inverse_mod(i,n),n)==k])
     for u,v,l in CGk.edges():
      CGk.set_edge_label(u,v,k)
     CG.add_edges(CGk.edge_iterator()) 
   
    CG.graphplot(color_by_label=True,edge_labels=True).show()
   

   for n in (31..60):
    Zn = Integers(n)
    Un = [x for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    show(table(["U("+str(n)+") has order "+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).
   
    Un = [int(x) for x in Zn if gcd(ZZ(x), n) == 1]  #This creates Un
    S=Zn.unit_gens()
   
    CG=DiGraph([Un,lambda i,j:False])
    for k in S:
     CGk=DiGraph([Un,lambda i,j: mod(j*inverse_mod(i,n),n)==k])
     for u,v,l in CGk.edges():
      CGk.set_edge_label(u,v,k)
     CG.add_edges(CGk.edge_iterator()) 
   
    CG.graphplot(color_by_label=True,edge_labels=True).show()
   
5. For each $n$ between 2 and 60, use a Cayley graph to determine if $U(n)$ is isomorphic to $U(m)$ for some $m<n$. Place your results in a table. If $U(n)$ is not isomorphic to any previous group on your table, put it in the left column of the table as a new row. Otherwise, place $U(n)$ to the right of the corresponding $U(m)$ to which it is isomorphic. If $U(n)$ has a single generator, add the appropriate $\mathbb{Z}_m$ to your table as well. Each row in your table should consists of isomorphic groups, and groups on different rows should not be isomorphic to each other. I've already done up through $U(12)$ in the table below, but I suggest you start at $U(2)$ and check that the table below is correct. $$\begin{array}{|c|c|} \hline \text{Group}&\text{Isomorphic Groups}\\ \hline U(2)&\mathbb{Z}_1, \\ U(3)&\mathbb{Z}_2, U(4), U(6),\\ U(5)&\mathbb{Z}_4, U(10), \\ U(7)&\mathbb{Z}_6, U(9), \\ U(8)&U(12)\\ U(11)&\mathbb{Z}_{10} \\ \vdots&\vdots\\ \end{array} $$
   • When you encounter a graph that is not generated by a single element, compare it to previous graphs that you've already seen. How could you make the new graph by combining previous graphs? For example, the graph of $U(8)$ looks like a bunch of graphs of $\mathbb{Z}_2$. The graph of $U(15)$ looks like two copies of $\mathbb{Z}_4$ connected with $\mathbb{Z}_2$'s. The first 5 new graphs (not generated by a single element) that you should encounter after $U(12)$ are at 15, 21, 24, 32, and 33.

We've made tons of conjectures about patterns we've seen in $Z_n$ and $U(n)$. It's time to prove them and start using them as facts, instead of conjectures. For example, we've already noticed that something has a multiplicative modular inverse mod $n$ if and only if it is relative prime to $n$. In problem .... (click to expand), we showed that .... The following problem provides the key tool to proving most of the conjectures we've made. While you'll find the proof to this in chapter 0 of the text, please try doing it without reading the proof. We'll use this theorem to prove most of our conjectures on Friday.

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

The definition of $\langle S\rangle$ above is very similar to our definition of span that we used earlier. It's missing the exponents that we had in our definition of the span. The next problem has you show that including the powers or not gives us the same thing.

Problem 66 (The Subgroup Generated By S Equals The Span Of S)

Let $G$ be a group. Suppose that $S$ is a subset of $G$. To parallel our definition of the span of a set of permutations, we could have defined the span of $S$ to be $$\text{span}(S)= \{t_1^{n_1}t_2^{n_2}\cdots t_j^{n_j}\mid j\in \mathbb{N} \text{ and $t_i\in S$ with $n_i\in \mathbb{Z}$ for each } i\in\{1,2,\ldots, j\}\}.$$ Instead we defined the subgroup generated by $\langle S \rangle$ to be $$\left<S\right> = \{s_1s_2\cdots s_k\mid k\in \mathbb{N} \text{ and either $s_i\in S$ or $s_i^{-1}\in S$ for each } i\in\{1,2,\ldots, k\}\}.$$ Using the definitions above, prove that these two sets are the same, so prove $\text{span}(S)=\left<S\right>$. In other words, prove that the subgroup generated by $S$ and the span of $S$ are precisely one and the same.

For more problems, see AllProblems