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

Please Login to access more options.

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.

The following pages link to this page.