Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
During class time, we'll do the following:
- Start by splitting into small groups for a discussion of 3 4, 5, and then problem 1 from Monday (Automorphisms Of A Directed Square), using cycle notation to list the 4 automorphisms.
- Each group will be assigned one of the three proofs to write up on the chalk board. Then well discuss these proof together as a class.
Here are the groups
| Problem | 1 | 2 | 3 | 4 | 5 |
| Front | Brennan | Alexander | Kimberly | Darrel | |
| Right | Laura | Bryce | Li | Sam | |
| Back | Rich | Megan | Tim | Caley | |
| Left | Tara | Rob | Austin | Kinsey |
Much of our work up to this point has been based on the ability to compute a remainder. This is all based on the Division Algorithm.
Theorem (Division Algorithm)
Let $a,n\in\mathbb{Z}$, with $n> 0$. Then there exists unique integers $q$ and $r$ (called the quotient and remainder) such that $a=qn+r$ where $0\leq r<n$.
Problem 15(Division Algorithm Proof)
Prove the Division algorithm.
If you are unable to complete this problem, then please move on to the next. You may find that reading chapter 0 in your abstract algebra text can help you with this one.
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$.
- 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$.
- 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$?
- 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.
- For each graph, list the automorphisms of the graph. Use disjoint cycle notation to represent each automorphism.
- 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.
- Construct another graph on 4 vertices different than the three we have seen so far. How many automorphisms does this graph have? Explain.
We made the following conjecture in class
Problem
Prove this conjecture.
If you are unable to prove this conjecture, try making a simpler conjecture and proving it. For example, we conjectured in class that if $\phi_1\in \text{span}(\phi_k)$, then we must have $\text{span}(\phi_k)=H_k$. Can you prove this? What is required to have $\phi_1\in \text{span}(\phi_k)$? Make a conjecture about the relationship between 1 and $k$ that would force $\phi_1\in \text{span}(\phi_k)$. Make as many conjectures as you can, and see if you can prove one of them.
For more problems, see AllProblems