HCSSiM Workshop, day 11

Home > math education > HCSSiM Workshop, day 11

HCSSiM Workshop, day 11

July 14, 2012 Cathy O'Neil, mathbabe

This is a continuation of this, where I take notes on my workshop at HCSSiM.

Lagrange

We reminded people that a finite group is a finite set with an associative multiplication law “*”, and an identity and inverses with respect that law. A subgroup is a subset which is a group in its own right with the same multiplication law. Given a subgroup $H$ of a group $G,$ we defined the cosets of $H$ to be, for some $x \in G,$ of the form:

$x * H = \{y \in G | \exists h \in H, y = x *h \}.$

We proved that “being in the same coset as” is an equivalence relation and that each coset has the same size. Altogether the cosets form a partition of the group, so the size of the group is the product of the size of any coset and the number of cosets.

One of the students decided that you could form a group law on the set of cosets, inheriting the multiplication operation from $G.$ When it didn’t quite work out, he postulated that he could do it if the group is commutative. Pretty smart kid.

Primitive Roots modulo p

Next we spent more time than you’d think proving there’s a nonzero number $a$ modulo $p$ whose powers generate all of the nonzero elements modulo $p.$ In other words, that there is an isomorphism

$\mathbb{Z}/p\mathbb{Z} -$ $\{0\} \rightarrow \mathbb{Z}/(p -1) \mathbb{Z}.$

The left group is a group under multiplication, and the right one is a group under addition, which means this can be seen as a kind of logarithm in finite groups. Indeed an element $x$ on the left is mapped to that power $i$ of $a$ such that $a^i = x.$ So it’s very much like a logarithm.

To prove such an $a$ exists, we actually show that $\phi(p-1)$ such roots exist, and that in fact there are $\phi(d) d$ th roots of unity for any $d$ which divides $p-1.$ Another case where it helps to prove something harder than what you actually want.

To do that, we have a few lemmas. First, that there are at most $n$ roots to a degree $n$ polynomial modulo $p$ unless it’s the “zero” polynomial. Second, that if there’s a polynomial which achieves this maximum, it must divide the “Fermat’s Little Theorem” polynomial $X^p - X.$ These two lemmas aren’t hard.

Next we proved that there are at most $\phi(d)$ primitive $d$ th roots of unity for any $d,$ by showing that, if we had one, then we’d take certain powers to get all $\phi(d)$ of them, and then if we hadn’t counted one then we’d be able to produce too many roots of the polynomial $X^d -1.$

Finally, we wrote out boxes labeled with the divisors of $p-1$ and we labeled $p-1$ balls the non-zero numbers mod $p.$ We put a ball with label $b$ into the box with its order (the smallest positive number $i$ so that $b^i =1$ ). Since there are at most $\phi(d)$ in each box, and since we need to put every ball in some box, there must be exactly $\phi(d)$ balls in each box since we proved a few days ago that:

$p-1 = \sum_{d | (p-1)} \phi(d).$

Platonic Solids

Riffing on our proof of Euler’s formula for planar graphs, we convinced the kids that we could just as well consider a graph to be on a sphere, using a stereographic projection.

Then, using graphs on spheres as guides, we looked at how many examples we could come up with for a regular polytope, where each face has the same number of edges and each vertex has the same number of edges leaving it. We came up with the five platonic solids.

mathbabe