HCSSiM Workshop, day 13

Home > math education > HCSSiM Workshop, day 13

HCSSiM Workshop, day 13

July 17, 2012 Cathy O'Neil, mathbabe

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

Permutation notation

Using a tetrahedron as inspiration, we found the group of rotational symmetries as a subgroup of the permutation group $S_4.$ We then spent a lot of time discussing how to write good notation for permutations, coming up finally with the standard form but complaining about how multiplication is in a weird direction, stemming from the composition rule $(f \circ g)(x) = f(g(x)).$

Quadratic Reciprocity

Today we proved quadratic reciprocity, which totally rocks. In order to get there we needed three lemmas, which were essentially a bunch of different formulas for computing the Jacobi symbol.

The first was that, modulo $p$ we have:

$\left( \frac{a}{p} \right) \cong a^{(p-1)/2}.$

The second one was that we could write $\left( \frac{a}{p} \right)$ as -1 to the $n$ , where $n$ is the number of negative numbers you get when you write the numbers $a, 2a, 3a, \dots, \frac{p-1}{2} a$ modulo $p$ with a number of absolute value less than $p/2.$

In the third one we assume $a$ is odd (we deal with $a=2$ separately). We prove we can write $\left( \frac{a}{p} \right)$ as -1 to the $n$ , where $n$ is (also) the sum of the greatest integers $\left[ \frac{a j}{p} \right]$ for $j = 1, 2, 3, \dots, \frac{p-1}{2}.$

Each of these lemmas, in other words, gave us different ways to compute the symbol $\left( \frac{a}{p} \right)$ . They are each pretty easy to prove:

The first one uses the fact that if $a$ is not a square, then the product of all nonzero numbers mod $p$ can be paired up into $\frac{p-1}{2}$ pairs of different numbers whose product is $a$ , so we get altogether $a^{\frac{p-1}{2}},$ but on the other hand we already know by Wilson’s Theorem that that product is -1.

The second one just uses the fact that, ignoring negative signs, $a, 2a, 3a, \dots, \frac{p-1}{2} a$ is the same list as $j = 1, 2, 3, \dots, \frac{p-1}{2},$ but paying attention to negative signs we can take out an $a^{\frac{p-1}{2}}$ and also a $(-1)^n.$ Since we already know the first lemma we’re done.

The third lemma follows from repeatedly applying the division algorithm to $p$ and $aj$ , so writing

$\displaystyle{a j = p \cdot \left[\frac{aj}{p} \right] + r_j}$

for all $j= 1, 2, 3, \dots, \frac{p-1}{2}$ . We replace the remainders by the previous form of “small representatives” which we call $s_j$ modulo $p$ , making the remained positive or negative but smaller than $p/2;$ this replacement requires that we add $n p$ . We add all the division formulas up and realize that we only need to care about the parity of $n,$ so in other words we work modulo 2. It looks like this:

$a (1 + 2 + \dots + \frac{p-1}{2}) = \left( \left[\frac{a}{p} \right] + \left[\frac{2a}{p} \right]+ \dots + \left[\frac{\frac{p-1}{2} a}{p} \right] \right) p + s_1 + s_2 + \dots + s_{\frac{p-1}{2}} + n \cdot p.$

Since $a$ is odd, we can ignore it modulo 2. Since $p$ is odd same there. We get:

$1 + 2 + \dots + \frac{p-1}{2} = \left[\frac{a}{p} \right] + \left[\frac{2a}{p} \right]+ \dots + \left[\frac{\frac{p-1}{2} a}{p} \right] + s_1 + s_2 + \dots + s_{\frac{p-1}{2}} + n.$

Up to signs, $s_1 + s_2 + \dots + s_{\frac{p-1}{2}} = 1 + 2 + \dots + \frac{p-1}{2},$ so we can conclude our lemma.

Incidentally, using the formula above (before we ignore $p$ ) it’s also easy to see that $\left( \frac{2}{p} \right) = -1^{\frac{p^2-1}{8}}.$

Finally, we show that the sum $\left[\frac{a}{p} \right] + \left[\frac{2a}{p} \right]+ \dots + \left[\frac{\frac{p-1}{2} a}{p} \right]$ is just the number of lattice points in the region above the x-axis, to the left of the line $x = p/2,$ and below the line $y = \frac{a}{p} x.$

But, letting $a = q$ some other odd prime, we can do the same exact thing and we find that $\left[\frac{p}{q} \right] + \left[\frac{2p}{q} \right]+ \dots + \left[\frac{\frac{q-1}{2} p}{q} \right]$ is just the number of lattice points in the region above the x-axis, to the left of the line $x = q/2,$ and below the line $y = \frac{p}{q} x.$ Flipping the second triangle over the line $y = \frac{q}{p} x$ demonstrates that we have two halves of the rectangle with $\frac{p-1}{2} \frac{q-1}{2}$ lattice points. Here’s the picture for $p=19$ and $q = 7$ (ignore the dotted lines):

Therefore we’ve proved:

$\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = -1^{\frac{p-1}{2} \frac{q-1}{2}}.$

Alternating Group

We introduced cyclic notation, showing everything is a product of transpositions, then we introduced the sign function and showed that $e$ can only be written as a product of an even number of transpositions. This means the sign function is well defined, and it’s easy to see then that it’s a homomorphism, so we can define its kernel to be the alternating group.

Transformation of the Plane

We discussed rotations, shears, shrinks, reflections, and translations of the plane and demonstrated them in Mathematica using this.

mathbabe