Please Login to access more options.


Today

« September 2016 »

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

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

For more problems, see AllProblems