Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
There is no prep required for today. The point is that you should be using your time to prepare for and take the exam.
I will be introducing the last half of the semester today in class. We'll be drawing a lot of Caley graphs, and using the time to introduce many of the patterns that we'll be proving during the last half of the semester. The hope is that today should be a fun introduction to the rest of the semester, with activities to work in small groups as well as a large class discussion.
If you have finished the exam and want to get started on your prep for Monday, feel free to head to Monday's prep.
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.
- 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?
- If you wanted to draw the Cayley graph of $\mathbb{Z}_{50}$ using $x=1$ as the generator, what would your graph look like?
- If $\mathbb{Z}_n\cong\mathbb{Z}_m$, what do you know about $n$ and $m$?
- 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() - 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.
Solution
Ignoring the groups that are isomorphic to $\mathbb{Z}_n$ for some $n$, you should encounter new groups at $$n=8,15,21,24,32,33,35,39,40,51,55,56,57.$$ The graphs of these groups are below.
for n in (8,15,21,24,32,33,35,39,40,51,55,56,57):
Zn = Integers(n)
Un = [x for x in Zn if gcd(ZZ(x), n) == 1] #This creates Un
html.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.
html.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())
show(CG.graphplot(color_by_label=True,edge_labels=True))
Every other graph you obtained should be isomorphic to one of the graphs above, or to a graph that is generated by a single element and hence isomorphic to $\mathbb{Z}_m$ for some $m$. For example, there are 4 groups that are isomorphic to $U(21)$, which you can see by evaluating the code below.
for n in (21,28,36,42):
Zn = Integers(n)
Un = [x for x in Zn if gcd(ZZ(x), n) == 1] #This creates Un
html.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.
html.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())
show(CG.graphplot(color_by_label=True,edge_labels=True))
Another interesting one that occurs a few times is $U(40)$. This looks like 4 copies of $U(8)$, connected with $\mathbb{Z}_4$'s.
for n in (40,48,60,8):
Zn = Integers(n)
Un = [x for x in Zn if gcd(ZZ(x), n) == 1] #This creates Un
html.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.
html.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())
show(CG.graphplot(color_by_label=True,edge_labels=True))
I think the groups $U(35)\cong U(45)$ and $U(56)$ are an interesting pair to compare. The latter looks like its six $\mathbb{Z}_4$'s connected with $\mathbb{Z}_6$'s, or it's four $\mathbb{Z}_6$'s connected with $\mathbb{Z}_4$'s. The former looks like 6 copies of $U(8)$ connected with $\mathbb{Z}_6$'s, or 4 copies of $\mathbb{Z}_6$ connected with $U(8)'s$.
for n in (35,45,56):
Zn = Integers(n)
Un = [x for x in Zn if gcd(ZZ(x), n) == 1] #This creates Un
html.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.
html.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())
show(CG.graphplot(color_by_label=True,edge_labels=True))
The more complicated graphs in every instance look like they can be pieced together by using multiple copies of $\mathbb{Z}_m$. Is this always true? What are the simple graphs from which we can build all others? This is one of the questions we want to explore.
Cayley Tables
H = DihedralGroup(4) print(H.cayley_table()) H.cayley_graph().show(color_by_label=True)
General Linear Groups
n=3
matrices=[];
for i in [0..n-1]:
for j in [0..n-1]:
tempmatrices=[]
for k in [0..n-1]:
for l in [0..n-1]:
tempmatrices.append(matrix(2,2,[i,j,k,l]))
matrices.append(tempmatrices)
html.table(matrices)
dets=[];
for i in [0..n-1]:
for j in [0..n-1]:
tempdets=[]
for k in [0..n-1]:
for l in [0..n-1]:
tempdets.append(matrix(2,2,[i,j,k,l]).det().mod(n))
dets.append(tempdets)
html.table(dets)
Here's a Cayley graph of $GL(2,\mathbb{Z}_3)$.
g1 = GL(2,3) d1=g1.cayley_graph() d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=False) d1.show3d(color_by_label=True, vertex_size=0.03, vertex_labels=False)
Cayley Graphs of Presentations
We've seen presentations before. The dihedral group of order $8$ has the presentation $$\left<a,b\mid a^4=b^2=(ab)^2=e \right>.$$ We can get all the other dihedral groups by changing the 4 on $a^4$ to an $n$, namely $$\left<a,b\mid a^n=b^2=(ab)^2=e \right>.$$ What happens if we change some of the other parts? What's the Cayley graph of the following: $$\left<a,b\mid a^3=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^4=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^5=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^6=b^2=(ab)^3=e \right>$$ $$\left<a,b\mid a^3=b^2=(ab)^4=e \right>$$ $$\left<a,b\mid a^4=b^2=(ab)^4=e \right>$$ $$\left<a,b\mid a^5=b^2=(ab)^4=e \right>$$ $$\left<a,b\mid a^6=b^2=(ab)^4=e \right>$$
The answers to the questions above is non trivial, and we won't be able to answer them all in our course. Here's a few.
$$\left<a,b\mid a^3=b^2=(ab)^3=e \right>$$
g1 = PermutationGroup(["(1,2,3)(4,5,6)(7,8,9)(10,11,12)","(1,12)(2,4)(3,9)(6,7)(8,10)(5,11)"]) d1=g1.cayley_graph() d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True) g1.subgroups() g1 = PermutationGroup(["(1,2,3)(4,5,6)(7,8,9)(10,11,12)","(1,12)(2,4)(3,9)(6,7)(8,10)(5,11)","(1,6)(2,8)(3,11)(4,10)(5,9)(7,12)", "(1,7)(2,10)(3,5)(4,8)(6,12)(9,11)"]) d1=g1.cayley_graph() d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True) g1 = PermutationGroup(["(1,2,3)(4,5,6)(7,8,9)(10,11,12)","(1,12)(2,4)(3,9)(6,7)(8,10)(5,11)", "(1,7)(2,10)(3,5)(4,8)(6,12)(9,11)"]) d1=g1.cayley_graph() d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True) d1.show3d(color_by_label=True, vertex_size=0.03, vertex_labels=True)
Here's the graph of $$\left<a,b\mid a^5=b^2=(ab)^3=e \right>.$$
g1 = PermutationGroup(["(1,2,3,4,5)","(1,2)(3,4)"]) d1=g1.cayley_graph() d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=False) d1.show3d(color_by_label=True, vertex_size=0.03, vertex_labels=False)
Subgroups
D = AlternatingGroup(5) D.cayley_graph().show(color_by_label=True) for K in D.conjugacy_classes_subgroups(): K.cayley_graph().show(color_by_label=True)
For more problems, see AllProblems