Read Chapter 1 from the book, and then do problems:
Remember: There are hints & solutions for some problems in the back of the book.
Read Chapter 2 and do the following:
Then try these extra Python problems:
Enter the following commands in Python:
import sympy
sympy.factorint(360)Try the factorint function on a couple of other numbers in addition to 360. What does the function factorint in the sympy library do?
It is easy to find the quotient and remainder from the division algorithm in Python, here’s how:
# To find the quotient and remainder of a divided by b
a // b # quotient
a % b # remainder Try computing 37 // 5 and 37 / 5. What is the difference?
Write a Python function to implement the Euclidean algorithm. Your function should accept positive integers \(a\) and \(b\) and output the \(\operatorname{gcd}(a,b)\).
Read Chapter 3 and do the following:
Read Chapter 4 and do the following:
Read Section 5.1 of Chapter 5 on Permutation Groups and do the following:
Then try this additional programming problem.
Suppose I give you the information for a permutation of the set \(\{0,1,2,\ldots, n-1\}\) encoded as a list by just giving you the bottom row of the permutation in permutation notation, encoded as a Python list. So, for example, I would give you the list [3,1,0,1] to encode the permutation: \[\begin{pmatrix} 0 & 1 & 2 & 3 \\ 3 & 1 & 0 & 2 \end{pmatrix}.\] Write a Python function called disjointCycles to decompose a permutation into a product of disjoint cycles. For example, the permutation above can be expressed as a product of the disjoint cycles \((0~3~2)\) and \((1)\). Your function should output these cycles as a list of lists: [[0,3,2],[1]]. Here are some more examples of how the function disjointCycles should work:
disjointCycles([1,2,0,4,3]) # Should return [[0,1,2],[3,4]]
disjointCycles([5,4,3,2,1,0]) # Should return [[0,5],[1,4],[2,3]]
disjointCycles([0,1,2]) # Should return [[0],[1],[2]]We continued talking about permutation groups this week. Try these exercises:
Click here for more details
Create a Permutation class for Python. To create a Permutation class in Python, you’ll need to fill in the details for the following methods.
class Permutation:
def __init__(self, permutationList):
# Initialize a permutation. The input permuationList is the bottom row of
# the permutation in permutation notation.
self.permutationList = permuationList
def __mul__(self, other):
# Write a function that returns the permutation self * other.
def disjointCycles(self):
# You can re-use your disjointCycles function as a method for Permutation objects.
def order(self):
# This method should return the order of the Permutation.
def __str__(self):
# This method tells Python how your Permutation objects should be represented as strings. Once you finish this class, it should be able to do things like the following:
P = Permutation([3,2,1,0])
P.order() # 2
Q = Permutation([1,2,3,0])
print(P*Q) # [2,1,0,3]Read Chapter 6 from the book. Then try these exercises.
For next week, read Chapter 7 from the book. There are no homework problems this week. On Thursday, March 17, we did this activity:
For week 9, read Section 9.1 from Chapter 9 in the book. Then try these exercises.
For next week, read the rest of Chapter 9 and try these exercises.
For next week, read Chapter 10 and try these exercises.
For next week, read Chapter 11 and try these exercises.
Hint on #12: For each \(g \in G\) prove that \(i_g: x \mapsto gxg^{-1}\) is an isomorphism from \(G\) to \(G\). Then consider \(i_g(H)\).
For next week, read Chapter 16 sections 16.1 and 16.2 about rings and fields. Then try these exercises.
For the final week, read Chapter 17 and try these exercises.
A hint on #10 is to try to factor equivalent polynomials (mod 10), like x2 + 11x + 18.
In our final week, we discussed how the following two theorems let us prove that the multiplicative group for a finite field is cyclic.
If \(G\) is a finite abelian group, then there are (not necessarily distinct) prime numbers \(p_1, \ldots, p_n\) and powers \(r_1, \ldots, r_n \in \mathbb{N}\) such that \(G\) is isomorphic to \(\mathbb{Z}_{p_1^{r_1}} \times \cdots \times \mathbb{Z}_{p_n^{r_n}}.\)
If \(F\) is any field and \(p(x) \in F[x]\) is a polynomial of degree \(m\), then \(p(x)\) has at most \(m\) roots.
If \(F\) is a finite field, then the multiplicative group \(F^\times\) is cyclic.
To prove this, observe the following:
Let \(m\) be the least common multiple of the orders of the elements in \(F^\times\). Then every \(x \in F^\times\) is a root of \(x^m - 1\). So \(m\) is at least \(|F^\times|\).
The order of every element in \(F^\times\) divides \(|F^\times|\) by the Theorem of Lagrange. Therefore \(|F^\times|\) is a multiple of all of the orders, and therefore \(m \le |F^\times|\). Combined with the previous observation, we have \(|F^\times| = m\).
Since \(F^\times\) is a finite abelian group, it is isomorphic \(\mathbb{Z}_{p_1^{r_1}} \times \cdots \times \mathbb{Z}_{p_n^{r_n}}.\) Therefore the least common multiple of the orders of the elements of \(F^\times\) is the product of each distinct prime factor \(p\) of \(p_1^{r_1} \cdots p_n^{r_n}\) raised to the highest power \(r_i\) corresponding to that prime factor. In particular, the order of \(F^\times\) can only be \(m\) if each \(p_i\) is distinct.
If the \(p_i\) are all distinct, then the group \(F^\times \cong \mathbb{Z}_{p_1^{r_1}} \times \cdots \times \mathbb{Z}_{p_n^{r_n}}\) is cyclic.
Your grade in the course will be based on how many of the assigned problems you complete correctly. You can resubmit assigned problems if you don’t get a correct solution the first try. Here are the thresholds needed to get various grades: