Archive

Author Archive

HCSSiM Workshop day 15

July 19, 2012 2 comments

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

Aaron was visiting my class yesterday and talked about Sandpiles. Here are his notes:

Sandpiles: what they are

For fixed m,n \ge 2, an m \times n beach is a grid with some amount of sand in each spot. If there is too much sand in one place, it topples, sending one grain of sand to each of its neighbors (thereby losing 4 grains of sand). If this happens on an edge of the beach, one of the grains of sand falls off the edge and is gone forever. If it happens at a corner, 2 grains are lost. If there’s no toppling to do, the beach is stable. Here’s a 3-by-3 example I stole from here:

Do stable m \times n beaches form a group?

Answer: well, you can add them together (pointwise) and then let that stabilize until you’ve got back to a stable beach (not trivial to prove this always settles! But it does). But is the sum well-defined?

In other words, if there is a cascade of toppling, does it matter what order things topple? Will you always reach the same stable beach regardless of how you topple?

Turns out the answer is yes, if you think about these grids as huge vectors and toppling as adding other 2-dimensional vectors with a ‘-4’ in one spot, a ‘1’ in each of the four spots neighboring that, and ‘0’ elsewhere. It inherits commutativity from addition in the integers.

Wait! Is there an identity? Yep, the beach with no sand; it doesn’t change anything when you add it.

Wait!! Are there inverses? Hmmmmm….

Lemma: There is no way to get back to all 0’s from any beach that has sand.
Proof. Imagine you could. Then the last topple would have to end up with no sand. But every topple adds sand to at least 2 sites (4 if the toppling happens in the center, 3 if on an edge, 2 if on a corner). Equivalently, nothing will topple unless there are at least 4 grains of sand total, and toppling never loses more than 2 grains, so you can never get down to 0.

Conclusion: there are no inverses; you cannot get back to the ‘0’ grid from anywhere. So it’s not a group.

Try again

Question: Are there beaches that you can get back to by adding sand?

There are: on a 2-by-2 beach, the ‘2’ grid (which means a 2 in every spot) plus itself is the ‘4’ grid, and that topples back to the ‘2’ grid if you topple every spot once. Also, the ‘2’ grid adds to the (2, 0, 0, 2) grid and gets it back.

Wow, it seems like the ‘2’ grid is some kind of additive identity, at least for these two elements. But note that the ‘1’ grid plus the ‘2’ grid is the ‘3’ grid, which doesn’t topple back to the ‘1’ grid. So the ‘2’ grid doesn’t work as an identity for everything.

We need another definition.

Recurrent sandpiles

A stable beach C is recurrent if (i) it is stable, and (ii) given any beach A, there is a beach B such that C is the stabilization of A+B. We just write this C = A+B but we know that’s kind of cheating.

Alternative definition: a stable beach C is recurrent if (i) it is stable, and (ii) you can get to C by starting at the maximum ‘3’ grid, adding sand (call that part D), and toppling until you get something stable. C = ‘3’ + D.

It’s not hard to show these definitions are equivalent: if you have the first, let A = ‘3’. If you have the second, and if A is stable, write A + A’ = ‘3’, and we have B = A’ + D. Then convince yourself A doesn’t need to be stable.

Letting A=C we get a beach E so C = C+E, and E looks like an identity.

It turns out that if you have two recurrent beaches, then if you can get back to one using a beach E then you can get back to to the other using that same beach E (if you look for the identity for C + D, note that (C+D)+E = (C+E) + D = C+D; all recurrent beaches are of the form C+D so we’re done). Then that E is an identity element under beach addition for recurrent beaches.

Is the identity recurrent? Yes it is (why? this is hard and we won’t prove it). So you can also get from A to the identity, meaning there are inverses.

The recurrent beaches form a group!

What is the identity element? On a 2-by-2 beach it is the ‘2’ grid. The fact that it didn’t act as an identity on the ‘1’ grid was caused by the fact that the ‘1’ grid isn’t itself recurrent so isn’t considered to be inside this group.

Try to guess what it is on a 2-by-3 beach. Were you right? What is the order of the ‘2’ grid as a 2-by-3 beach?

Try to guess what the identity looks like on a 198-by-198 beach. Were you right? Here’s a picture of that:

We looked at some identities on other grids, and we watched an app generate one. You can play with this yourself. (Insert link).

The group of recurrent beaches is called the m-by-n sandpile group. I wanted to show it to the kids because I think it is a super cool example of a finite commutative group where it is hard to know what the identity element looks like.

You can do all sorts of weird things with sandpiles, like adding grains of sand randomly and seeing what happens. You can even model avalanches with this. There’s a sandpile applet you can go to and play with.

Categories: math education

HCSSiM Workshop, day 14

July 18, 2012 7 comments

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

We switched it up a bit and I went to talk about Rubik’s Cubes in Benji Fisher’s classroom whilst Aaron Abrams taught in mine and Benji taught in Aaron’s. We did this so we could meet each other’s classes and because we each had a presentation that we thought all the classes might want to see.

In my class, besides what Aaron talked about (which I hope to blog about tomorrow), we talked about representing groups with generators and relations and we looked at how to create fractals on the complex plane using Mathematica.

Solving the Rubik’s Cube with group theory

First I talked about the position game, so ignoring orientation of the pieces. In other words, if all the pieces are in the correct position but are twisted or flipped, that’s ok.

Consider the group acting on the set which is the Rubik’s cube. We can fix the centers, and then this group is clearly generated by 90 degree clockwise turns on each of the 6 faces (clockwise when you look straight at the center of the face). It has a bunch of relations too, of course, including (for example) that the “front” move commutes with the “back” move and that any of these generators is trivial if you do it 4 times in a row.

Next we noted that the 8 corners always move to other corners on any of these moves, and that the 12 edges always move to edges. So we could further divide the “positions game” into an “edges game” and a “corners game.” Furthermore, because of this separation, any action can be realized as an element of the group

S_8 \times S_{12}.

But there’s more: any one of these generators is a 4-cycle on both edges and corners, which is odd in both cases, so so is a product of the generators. This means the group action actually lands inside

A_8 \times A_{12} + B_8 \times B_{12},

where I denote by B_n the odd permutations of S_n.

Next I stated and proved that the 3-cycles generate A_n, by writing any product of two transpositions as a product of two or three 3-cycles.

The reason that’s interesting is that, once I show that I can act by arbitrary 3-cycles on the edges or corners, this means I get that entire group up there of the form (even, even) or (odd, odd).

Next I demonstrated a 3-cycle on three “bad pieces” where one needs to go into the position of one of the other two. Namely:

  1. Put two “bad” pieces on the top and one below, including the piece which is the destination of the third.
  2. Do some move U which moves the third bad piece below to its position on the top without changing anything else.
  3. Move the top so you decoy the new piece with the other bad piece on top. Call this decoy move V.
  4. Undo the U move.
  5. Undo the V move.

Seen from the perspective of the top, all that happens is that suddenly it has one piece in the right place (after U), then it gets rid of a piece it didn’t want anyway. From the perspective of the bottom, it sent up a piece it didn’t want to the top, then unmessed itself by taking back another piece from the top.

That’s a 3-cycle on the pieces, on the one hand (and a commutator on the basic moves), and we can perform it on any three corners or edges by first performing some move to get 2 out of the 3 pieces on the same face and the third not on that face. This is essentially acting by conjugation (and it’s still a commutator).

Moreover, the overall effect on the puzzle is that it took 3 pieces that were messed up and got at least 1 in the right spot.

The overall plan now is that you solve the corners puzzle, then the edges puzzle, and you’re done. Specifically, I get to the (even, even) situation by turning one face once if necessary, and then I can perform arbitrary 3-cycles to solve my problem. If I have fewer than three messed up corners (resp. edges), then I have either 0, 1, or 2 messed up corners (resp. edges). But I can’t have exactly 1, and exactly 2 would be odd, so I have 0.

That’s the position game, and I’ve given an algorithm to solve it (albeit not efficient!).

What about the orientations?

Shade the left and right side of a solved cube. Both the position (cubicle) and the piece of plastic (cubie) can be considered as shaded. Also shade a strip  on the front and on the back, so we get the top and bottom edge of the front and back shaded.

Convince yourself that every edge and every corner position has exactly one shaded face.

When the cube is messed up, the shaded face of the position may not coincide with the shaded face of the cubie in that position. For edges it’s either right or wrong – assign each a value of 0 (if it’s right) or 1 (if it’s wrong). These can be considered orientation values modulo 2.

For corners, it can be wrong in two ways. The cubie’s shaded face could coincide with the position’s shaded face (give it a value 0), or it could be clockwise 120 degrees (value 1), or counterclockwise 120 degrees (value -1). These numbers are modulo 3.

Next, convince yourself that all of the generators of the group of actions on the rubik’s cube preserve the fact that the sum of the orientation numbers is 0, considered either mod 3 for the corners or mod 2 for the edges.

In particular, this means we can’t have exactly one edge flipped but everything in the right position. If you see this on a Rubik’s cube then someone took it apart and put it back together wrong.

However, you can twist one corner clockwise and another one counterclockwise, which means you can get any configuration of orientation numbers on the corners that satisfy that their sum is 0. Same with edges – it’s possible to flip two.

Finally, I exhibit how to do each of these basic orientation moves by 2 3-cycles. First I choose a pivot corner and perform a 3-cycle on those three corners, and then I do another 3-cycle, which uses the same 3 corners but is slightly different and results in everything being back in the right position but two corners twisted. I can do the same thing for edges, and I have thus totally solved the cube.

This method of 3-cycles is slow but it generalizes to all Rubik’s puzzles, so for example the 7 by 7 cube:

Or, with some work, something else like this:

p.s. I learned all of this when I was 15 from Mike Reid at HCSSiM 1987.

p.p.s. This was what we ate after singing our Yellow Pig Carols last night:

Categories: math education

HCSSiM Workshop, day 13

July 17, 2012 1 comment

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.

Categories: math education

Yellow Pig Carols

July 16, 2012 6 comments

Tomorrow is Yellow Pig Day, which is a yearly tradition here at HCSSiM during which we celebrate our mascot the yellow pig and our favorite number, 17.

In particular, there will be an hour and a half lecture during which we will hear many surprising and elegant 17 facts (examples: the longest time anybody has ever sat in a tub of ketchup? 17 hours. The average adolescent male has a sexually related thought how often? Every 17 seconds).

Some time after the 17 lecture we get together to sing Yellow Pig Carols. These are usually set to the tune of some song, with the lyrics changed to refer to math, in particular the number 17, and yellow pigs, Weird Al Yankovic- style. Check out this list for a taste.

But there’s a problem, which is that the songs are really old and many of the tunes are unknown to this crop of kids. In desperate need of a revamp, I got my workshop to write a new song, which I’m super proud of. We started out by voting on a song (winner: Somewhere Over the Rainbow) for which we wrote new lyrics. Here they are:

Some July Seventeenth

Some july seventeenth
when pigs fly
we’ll see patches of yellow
scattered across the sky

Some “f” over the reals
satisfy
f of x plus f of y
is f-of-x plus y

someday I’ll find another g
besides f of t is k t or zer-o
and then I will compose the two
and get solutions that are new
they’ll appear-o

Some groups they are abelian
they commute
but some have commutators
whose actions are not moot

The action on the complex plane
by matrices is so in-sanely dum-ber
than even that of conjugation
whose equivalence relation pairs the num-bers

Some july seventeenth
when pigs fly
we’ll see patches of yellow
scattered across the sky

Honestly I thought it would stop there, but people around here have been on a tear. My hilarious junior staff Maxwell Levit has written a brilliant song based on Gotye’s “Somebody I Used to Know”. If you haven’t been living under a rock, you will have heard that song (and if you haven’t heard that song, please go ahead and do so now), about a guy wondering why this woman has left him and won’t talk to him, and then she comes in and tells her story which is how much of a manipulative creep he really was. There’s a dramatic video featuring nakedness and body paint which adds to the drama and to the song.

Well Max just turned that shit around and now it’s Fermat singing to Fermat’s Last Theorem, wondering where he went wrong, and then the theorem talks back and tells us the real deal. Plus he uses the word “marginalia,” which is in itself awesome. Here it is:

A Theorem that I used to know

(Fermat)
Now and then I think of Diophantine equations
Like how Pythagoras showed the case for n=2
Told myself that I understood,
And didn’t write down what I thought I would
Remember when I looked back at my marginalia

You can get addicted to a certain type of hubris
Assuming you don’t need to use elliptic curves
So when I found my proof did not make sense,
I knew it wasn’t my incompetence
But I’ll admit I was confused to say the least.

But you didn’t have to be so hard,
Make out like my intuitive method was for nothing
I don’t even need to know
But they treat you like Wiles solved you and that feels so rough

No you didn’t have to stoop so low
Elliptic curves and modular forms lack in imagination
I guess I don’t need you though,
Now you’re just some theorem that I used to know.

Now you’re just some theorem that I used to know.
Now you’re just some theorem that I used to know.

(theorem)
Now and then I think of when you said you’d solved me.
Part of me believing I had some marvelous proof.
But I don’t really work that way.
Adhering to everything you say.

You said that you could let it go,
And you shouldn’t get too hung up on a theorem that you used to know!

(Fermat)
But you didn’t have to be so hard,
Make out like my intuitive method was for nothing
I don’t even need to know
But they treat you like Wiles solved you and that feels so rough

No you didn’t have to stoop so low
Elliptic curves and modular forms lack in imagination
I don’t even need you though,
Now you’re just some theorem that I used to know.

[x2]
Some Theorem!
(I used to know)
Some Theorem!
(Now you’re just some theorem that I used to know)

(I used to know)
(That I used to know)
(I used to know)
Some Theorem!

We’re gonna make Devin Ivy, a fantastically funny junior staff here as well as a photographer, play Gotye/ Fermat in the video, with yellow pigs getting continually plastered all over his body. He’s Gotye’s spitting image:

Categories: math education

HCSSiM Workshop, day 12

July 15, 2012 8 comments

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

We originally defined \mathbb{C} as \mathbb{R}[x]/(x^2+1), and now we re-introduce it as the set of matrices of the form with the obvious map where a + bi is sent to:

After we reminded people about matrix addition and multiplication, we showed this was an injective homomorphism under addition and also jived with the multiplication that we knew coming from \mathbb{C}. Overall our lesson was not so different from this one.

Then we talked about actions on the plane including translations and scaling and showed that under the above map, “multiplication by r e^{i \theta}” or by its corresponding matrix gives us the same thing.

Platonic Solids

We went over the 5 platonic solids from yesterday- we’d proved it was impossible to have more than 5, and now it was time to show all 5 are actually possible! That’s when we whipped out Wayne Daniel’s “all five” puzzle:

We then introduced the concept of dual graph, and showed which platonic solids go to which under this map. We saw an example of a toy which flips from one platonic solid (cube) to its dual (octahedron) when you toss it in the air, the Hoberman Flip Out.

Here is it in between states:

Finally, we talked about symmetries of regular polyhedra and saw how we could embed an action into the group of symmetries on its vertices. So symmetries on tetrahedra is a subgroup of S_4. It’s a lot easier to understand how to play with 4 numbers than to think about moving around a toy, so this is a good thing. Although it’s more fun to play with a toy.

Then one of our students, Milo, showed us how he projected a tiling of the plane onto the surface of a sphere using the language “processing“. Unbelievable.

After that we went to an origami workshop to construct yellow pigs as well as platonic solid type structures.

Categories: math education

HCSSiM Workshop, day 11

July 14, 2012 1 comment

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) dth 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 dth 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.

Categories: math education

It rocks to be 40

July 13, 2012 8 comments

So it’s my birthday today, I’m finally 40. I’m enjoying it so much I started calling myself 40 like four months ago because I couldn’t wait.

I’m not exactly sure why it is so meaningful to me, this number. You might think I’m enough of a rebel to just not care at all about a number like this, even though it is certainly culturally significant. But here’s the thing, I’m owning it.

Since I’m an alpha female, being 40 frees me up quite a bit. I don’t have to even imagine not being taken seriously or being thought of as too young or inexperienced to have an opinion. I have no urge to be cute or play dumb. Leave that to younger people, it wouldn’t work for me anymore anyhow.

My dad used to tell me to try to be “more demure” so that people wouldn’t be put off by me. Worst advice ever. I definitely have gotten more out of my life by being completely honest and upfront than by playing a synthetic role. It also wastes less time for everyone. At this point I’m able to look over my experiences and know things like that rock-solid, and not second guess myself. That’s a good feeling.

You know what rocks about being 40? It comes down to this: I am old enough to know the difference between bullshit and the good stuff and I’m still feeling healthy and fully capable of enjoying the good stuff. It is seriously freeing, and I’m looking forward to everything about it. And I say this basically unemployed and not knowing what I’m doing next, which for some reason gives rise to the most freeing moments for me.

Presents I don’t want for my 40th birthday:

  • hair dye. I’m letting myself go grey, it’s gorgeous IMHO.
  • anti-wrinkle cream. Screw that.
  • girdles. I’ve already complained about that.

Presents I might want for my 40th birthday:

  • a night out on the town ending with karaoke is always nice.
  • puzzles and games. I’ve always love playing with puzzles. Crosswords too.
  • time with the many people I love. That’s the best part.

Let’s do this, people! Fuck yeah!!

Categories: rant

HCSSiM Workshop day 10

July 13, 2012 2 comments

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

Quadratic equations modulo p

We looked at the general quadratic equation a x^2 + b x + c modulo an odd prime p (assume a \not \cong 0 \; \; (mod \; p)) and asked when it has roots. We eventually found the solution to be similar to the one we recognize over the reals, except you need to multiply by (2 a)^{-1} instead of dividing by 2a. In particular, we achieved the goal, which was to reduce this general form to a question of when a certain thing (in this case b^2 - 4ac) is a square modulo p, in preparation for quadratic reciprocity.

We then defined the Jacobi symbol \left( \frac{a}{p} \right) and proved that \left( \frac{-1}{p} \right) = 1 \iff p=2 or p \cong 1 \; \; (mod \; 4).

Cantor

We then reviewed some things we’d been talking about in terms of counting and cardinality, we defined the \leq notation for sets: we define X \leq Y to mean “exists an injection from X to Y“. We showed it is a partial ordering using Cantor-Schroeder-Bernstein.

Then we used Cantor’s argument to show the power set of a set always has strictly bigger cardinality than the set.

Euler and planar graphs

At this point the CSO (Chief Silliness Officer) Josh Vekhter took over class and described a way of assessing risk for bank robbers. You draw out a map of a bank as a graph with vertices in the corners and edges as walls. It can look like a tree, he said, but it would be a pretty crappy bank. But no judgment. He decided that, from the perspective of a bank robber, corners are good (more places to hide), rooms are good (more places for money to be stashed) but walls are bad (more things you need to break through to get money.

With this system, and assigning a -1 to every wall and a 1 to every corner or room, the overall risk of a bank’s map consistently looks like 2. He proved this is always true using induction on the number of rooms.

Categories: math education

How to lie with statistics, Merck style

July 12, 2012 6 comments

In the pharmaceutical industry, where companies are making enormous bets with huge money and people’s lives, it makes sense that there are conflicting interests. The companies, who are in charge of testing their drugs for safety and for successful treatment, tend to want to emphasize the good and ignore the bad.

That’s why they are expected to describe beforehand how they are planning to do the tests. It stands to reason that, if they did a thousand tests and then only reported on the best ones, the public would get a biased view of the safety of their products.

For some reason, though, this standard doesn’t seem to be universally followed, and lying with statistics seems to be okay.

The newest example comes from Merck (see Pharmalot article here), which changed its statistical methods on testing Vioxx for Alzheimer’s patients from an intent-to-treat analysis to an on-treatment analysis even though their stipulated plans were the former. And even though the standard in the industry is the former.

Intent-to-treat means you choose people and stick with them, even if they get off the drug for some reason. And on-treatment only counts people that stay on the drug the whole time.

The difference is one of survivorship bias; there may be a good reason someone gets off the drug, and that may be because they got sick, and maybe they got sick because they were taking the drug.

What’s the difference in this case? From the article:

A subsequent intent-to-treat analysis found that as of April 11, 2002, when the FDA approved Vioxx labeling, there were 17 confirmed cardiovascular deaths on Vioxx compared with five on placebo in the same two trials.

With their on-treatment analysis, though, they didn’t see an elevated risk. So as it turns out the actual heart attacks happened a couple of weeks after people got off the pill.

So what happened there? Why were they allowed to change their stipulated method? Why were they allowed to not report their stipulated, gold-standard method? That’s complete bullshit and it must mean that someone at the FDA is either insanely stupid or very rich. Or both.

I’ve written about this issue before, specifically here. Just let me remind you of how we might assess the damage done by Merck through their statistical shenanigans:

Also on the Congress testimony I mentioned above is Dr. David Graham, who speaks passionately from minute 41:11 to minute 53:37 about Vioxx and how it is a symptom of a broken regulatory system. Please take 10 minutes to listen if you can.

He claims a conservative estimate is that 100,000 people have had heart attacks as a result of using Vioxx, leading to between 30,000 and 40,000 deaths (again conservatively estimated). He points out that this 100,000 is 5% of Iowa, and in terms people may understand better, this is like 4 aircraft falling out of the sky every week for 5 years.

According to this blog, the noticeable downwards blip in overall death count nationwide in 2004 is probably due to the fact that Vioxx was taken off the market that year.

Finally, I’d like to reiterate my question, why are pharmaceutical companies allowed to do their own trials?

Categories: rant, statistics

HCSSiM Workshop day 9

July 12, 2012 4 comments

A continuation of this, where I take notes on my workshop at HCSSiM.

First we had a few proofs from the previous night’s problem set, including a proof of Hall’s Marriage Problem using Dilworth’s Theorem.

Counting stuff

We then proved an uncountable set union a countable set is uncountable, with the help of Lior’s comment from yesterday.

Then we proved the Cantor-Schroeder-Bernstein Theorem, which states that if you have two injective maps f and g in the opposite directions: f:X \rightarrow Y and g:Y \rightarrow X, then you can construct a bijection between X and Y, and in particular the two sets will have the same cardinality. It’s not that hard – consider the orbits of points in X and Y under repeated applications of the two injective maps f,g, and if possible, by pulling back by f^{-1} and g^{-1}.

It doesn’t take much thinking to convince yourself that these orbits come in three forms: an infinite list in both directions, a finite loop, or an infinite forward path but a finite backwards path, where at some point you can’t pull back any more. In the last case you could get “stuck” in either X or Y. Since the orbits form a partition of all of the points, you can independently decide how to define the bijection depending on what that orbit looks like. Namely, it takes an element x in X to f(x) unless it’s an orbit that gets going backwards in Y, in which case you take x to g^{-1}(x).

Now that I think of it, I’m pretty sure this proof uses the axiom of choice, and according to the wikipage on this theorem it doesn’t need to, but I don’t know a proof which avoids it. The truth is I can never tell. Please explain to me if you can, how you can verify if you’re using the axiom of choice in an argument where you make infinitely many decisions.

Homomorphisms

We defined a homomorphism of groups and wrote it in both additive and multiplicative notation, because it turns out some of the students were getting confused. We proved very basic properties that follow such as the fact that the identity element goes to the identity element under a homomorphism, and the image of the inverse of an element is the inverse of the image. We ended by asking them to consider the set of homomorphisms between a cyclic group of 6 elements and itself, or between a cyclic group of 6 elements to a cyclic group of 7 elements.

Fermat and Wilson

Next we whipped out some theorems modulo a prime p. We looked at the action defined on numbers mod 17 when you multiply them by 3, and noticed it just scrambles the non-zero ones up (and of course sends 0 to 0). We proved that this is true in general. But this means that the product of all the non-zero numbers mod p is the same if we pre-multiply by any a, which means that product is equal to itself times a^{p-1}, and since it’s invertible that means a^{p-1} \cong 1 \, \, (mod \; p). That’s just a hop skip and jump away from Fermat’s Little Theorem, which states that a^{p} \cong a \, \, (mod \; p) for every number a.

Next, we wondered, what was that product of all those non-zero numbers mod p? It turns out that each of those nonzero guys is invertible, so if you pair each up with its inverse their contribution to the product is just 1, and the leftovers are just the guys who are their own inverse, which is only 1 or -1 (which we proved, and which is most definitely not true modulo 8). So the whole product is -1. That’s Wilson’s Theorem, but we called it Wilevson’s Theorem since Lev came up with the argument.

Categories: math education

Mathematicians know how to admit they’re wrong

July 11, 2012 30 comments

One thing I discussed with my students here at HCSSiM yesterday is the question of what is a proof.

They’re smart kids, but completely new to proofs, and they often have questions about whether what they’ve written down constitutes a proof. Here’s what I said to them.

A proof is a social construct – it is what we need it to be in order to be convinced something is true. If you write something down and you want it to count as a proof, the only real issue is whether you’re completely convincing.

Having said that, there are plenty of methods of proof that have been standardized and will help you in your arguments. There are things like proof by contradiction, or the pigeon hole principle, or proof by induction, or taking cases.

But in the end you still need to convince me; if you say there are three cases to consider, and I find a fourth, then I’ve blown away your proof, even if your three cases looked solid. If you try to prove something by induction, but your inductive step argument fails going from the case n=16 to n=17, then it’s not a proof.

Ultimately, then, a proof is a description of why you think something is true. The first half of your training is to problem solve (so, come up with a reason something is true) and construct a really convincing argument.

Coming at it from the other side, how can you check that what you’ve got is really a proof if you’ve written down the reason you think it’s true? That’s when the other half of your training comes in, to poke holes in arguments.

To be a really good mathematician you need to be a skeptic and to walk around with a metaphorical gun to shoot holes in other people’s arguments. Every time you hear a reasoned explanation, you look for the cases it doesn’t cover or the assumptions it’s making.

And you do the same thing with your own proofs to help yourself realize your mistakes before looking like a fool. Because putting out a proof of something is tantamount to asking for other people to shoot holes in your argument.

For that reason, every proof that one of these young kids offers up is an act of courage. They don’t know exactly how to explain their thinking, nor do they yet know exactly how to shoot holes in arguments, including their own. It’s an exercise in being wrong and admitting it. They are being trained to get shot down, to admit their mistake, and then immediately get back up again with better reasoning. The goal is to get so good at being wrong that it doesn’t hurt, that it’s not taken personally, and that it’s even fun to be wrong and to improve your argument.

Not every person gets trained in being wrong and admitting it. I’d wager that most people in the world, for most of their professional lives, are trained to do the opposite in the face of being wrong: namely, to wriggle out of it or deflect criticism. Most disciplines spend more time arguing they’re right, or at least not as wrong, or at least they have different mistakes, than other related fields. In math, you can at the most argue that what you’re doing is more interesting or somehow more important than some other field.

[I’ve never understood why people would think certain math is more important than other math. It’s almost never on the basis of having applications in the real world, or helping people in some way. It’s just some arbitrary snobbery, or at least that’s how it’s seemed. For my part I can’t explain why I love number theory more than analysis, it’s pure sense of smell.]

Most people never even say something that’s provably wrong in the first place. And that makes it harder to prove they’re wrong, of course, but it doesn’t mean they’re always right. Since they’ve not let themselves get pinned down on a provably wrong thing, they tend to stick with their wrong ideas for way too long.

I’m a huge fan of skepticism, and I think it’s generally undervalued. People who run companies, or universities, or government agencies, typically say they like healthy skepticism but actually want people to drink the kool aid. People who are skeptical are misinterpreted as being negative, but there’s a huge difference: negative means you’re not trying to solve the problem, skeptical means you care enough about the problem to want to solve it for real.

Now that I’ve thought about the training I’ve received as a mathematician, though, and that I’m now giving that training to these new students, I’ll add this to my defense of skepticism: I’m also a huge fan of people being able to admit they’re wrong. It’s the flip side of skepticism, and it’s why things get better instead of stay wrong.

By the way, one caveat: I’m not claiming that mathematicians are any better at admitting they’re wrong outside a strictly logical sphere.

Categories: math education, rant

HCSSiM Workshop day 8

July 11, 2012 2 comments

A continuation of this, where I take notes on my workshop at HCSSiM.

We first saw presentations from the students from last night’s problem set. One was a four line proof that the last two digits of 17^{2012} are 61. The other was a beautiful proof that the only real numbers that have more than one decimal representation are rationals of the form a/10^k for some integer k.

Dillworth’s Theorem Revisited

After going over examples of chains and antichains, and making sure we knew that there must be at least as many chains as there are elements in an anti-chains if we want the chains to cover our set, we set up a proof by induction on the number of elements in our set. The base case is easy (one element, one chain, one element in a maximal anti-chain) and then to reduce to a smaller case we remove any maximal element m. Note this just means there’s nothing above it. But now the inductive hypothesis holds, and we cover the remaining set with chains C_1, C_2, \dots, C_k and moreover we define a_i \in C_i to be the largest element in C_i such that it is contained in some maximal anti-chain.

We then stated two lemmas. The first is that any maximal anti-chain must have a unique element in each chain $C_i$, and the second is that, after defining the elements a_i as above, they form a maximal anti-chain. We treat these lemmas as black boxes for the proof (the first we did yesterday, the second is on problem set tonight).

Now we put back the removed point m. There are two cases, either m is incomparable to any of the a_i‘s or it is comparable to at least one of them.

In the first case, we have an anti-chain of size k+1, namely the a_i‘s plus m, and we can form a (k+1)st chain consisting of just m itself.

In the second case, m is comparable to some a_i. Since m is maximal, and since a_i is maximal in its chain C_i with respect to being in a maximal antichain, we can form a new chain which is just the same thing as C_i for a_i and below, and goes straight up to m from a_i. Note we may be missing some stuff that used to be above a_i in C_i. But that doesn’t matter, because if we remove this new chain, we see that the maximal anti-chains leftover is only of size k-1, so by Strong Induction we can cover it with k-1 chains, and then bring back this chain to get an overall covering with k chains.

Dihedral Groups

After reviewing the formal definition of a Karafiol (group), we used rotations and flips of a folder and then of a regular 5-gon to come up with a non-commutative group. We defined a subgroup and explored the different subgroups of the dihedral group as well as other examples we’d seen coming from modular arithmetic.

Euler’s Totient function

We introduced the number of positive integers less than n relatively prime to n as a function of n called \phi(n) and wrote out a table up to 17. We observed that \phi(p) = p-1 and that, from the Chinese Remainder Theorem, we also could infer that for gcd(m, n) = 1 we have \phi(mn) = \phi(m) \phi(n). Writing out a prime factorization for n = \prod_i p_i^{a_i} we realized we’d have a formula for \phi(n) if we just knew \phi(p^a) for any prime p and any positive a. We wrote out a picture and decided \phi(p^a) = p^a - p^{a-1}.

We ended by proving Euler’s formula by induction on the number of distinct prime factors:

\sum_{d | n} \phi(d) = n.

Categories: math education

HCSSiM Workshop day 7

July 10, 2012 4 comments

A continuation of this, where I take notes on my workshop at HCSSiM.

The real numbers are uncountable

Today we used Cantor’s diagonal argument to prove that the real numbers aren’t countable. Namely, we assumed they were, and that we had a bijection f: \mathbb{N} \rightarrow \mathbb{R} and then proved it didn’t contain the real number YP, whose ith digit we defined to be 1 if the ith digit of f(i) is 7, and 7 otherwise. One of our students pointed out that there are some numbers that have more than one decimal expansion, so the general argument that a certain decimal expansion isn’t in the list isn’t a total proof. But we decided that we’d be able to prove on homework that the only numbers that have more than one representative in decimal expansions are rational with their denominators divisible only by 2 and 5, which is not the case for the number YP we’d been talking about.

Then we wanted to show that \mathbb{R} has the same cardinality as \mathbb{R}\times\mathbb{R}. We tried to use a “splicing argument” where we create a new decimal expansion out of two decimal expansions (where the odd digits correspond to the first and the even to the second), but then we decided this map isn’t well defined, since we still have this “overlap” problem where 0.999… = 1 but the pair (0, 0.999...) doesn’t get mapped by the splicing map to the same decimal expansion as the pair (0, 1).

So then we decided to instead consider the set of decimal expansions, which is a bit bigger than the reals, and there the splicing map works. We reduced it to this case and are leaving it to homework to prove that the set of decimal expansions has the same cardinality as the reals. Although I don’t actually know how to do this without Cantor-Schroder-Bernstein, which we haven’t proven yet.

The Chinese Remainder Theorem 

We stated and proved the Chinese (Llama) Remainder Theorem. It was a nice example of a constructive proof that assumes it’s possible and then, when you follow your nose, it’s possible to completely characterize what the solution must look like, and then it falls out. We showed it described a bijection of sets \mathbb{Z}/\prod_i n_i \mathbb{Z} \rightarrow \prod_i \mathbb{Z}/n_i \mathbb{Z}. We haven’t talked about homomorphisms of groups yet though so we can’t prove it’s an isomorphism of groups.

Dilworth’s Theorem on chains and anti-chains in posets

We started the proof of Dilworth’s Theorem but didn’t finish yet (to be continued tomorrow). Turns out that this problem is really hard and that, moreover, there are lots of ways to convince yourself it’s true but be wrong about. The inductive proof in wikipedia, for example, is incomplete, but can be extended to a complete proof.

As an example, try to cover the following poset on the power set of five letters with 10 chains:

In particular you can see we solve a matching problem on the way, between subsets of size two and subsets of size 3 in the set of five letters, which isn’t the normal “take the complement” match, but rather is an inclusion of one in the other. I’m still wondering if there’s a more direct way to do this.

Categories: math education

Center for Popular Economics Summer Institute 2012

July 9, 2012 3 comments

I’ll going to be giving a plenary talk on Tuesday, July 24th at the CPE Summer Institute 2012, which is being held this summer at Columbia the week of July 23rd – July 27th. I’ll be joined by Richard Wolff, an economist, radio show host, and author of multiple books, most recently Occupy the Economy. You can register for the Institute here (sliding scale).

The Summer Institute open to non-experts to teach them about the financial system and economics. They have two core courses, one based in the U.S. and the other international. From their web page:

The U.S. Economy/ Topics include

»     Roots of the economic meltdown and solutions
»     Speculation, finance and housing bubbles
»     Economy, race, class and gender
»     Economic histories – from personal to global
»     Labor and jobs
»     Democratizing the Federal Reserve and banks.
»     Economic alternatives, socialism and the solidarity economy

The International Economy/ Topics include

»     Roots of the economic meltdown and solutions
»     Brief history of the global economy
»     International trade, production and finance
»     The IMF, World Bank, WTO
»     Global climate change and the environment
»     Creating a new world economy

In addition to hosting this cool and open Summer Institute, the Center for Popular Economics also recently came out with a booklet explaining some economic history of the U.S. written for the non-expert; take a look here.

I’m about halfway through, and I’ve spotted things you usually don’t see in economics texts you might read in high school, such as the following phrase:

So What Caused This Crisis?
Neoliberal capitalism has had three features that both explain how it promoted 25 years of economic expansions and why it led to a massive crisis in 2008. First, inequality grew rapidly, as profits rose while workers’ wages actually fell. From 1979 to 2007, the average inflation-corrected hourly wage of non-supervisory workers declined by 1 percent, while inflation-corrected nonfinancial corporate profits after taxes rose by a remarkable 255 percent. While surging profits pleased the capitalists, it brought a problem: who could buy the growing output that comes with economic expansion? The solution was debt. Somehow, people would have to borrow more and more if a form of capitalism that brings skyrocketing profits and falling wages was to function.

I think it would be cool to have a typical high school “history of economics” text side by side with this one, and have students read both and argue them.

I’m going to try to go to as much of the Summer Institute as I can as a student. I hope I see you there!

Categories: finance

Toilet paper rant

July 8, 2012 9 comments

I’ve been here at HCSSiM for almost exactly a week now, and I’ve been exclusively blogging about what mathematics we’ve been teaching this year’s brilliant crop of high school kids. Considering the fact that I usually have lots of opinions on important subjects such as financial reform, data science, and the incorrigible misuse of statistics, you might think I’m dying to also post about such things now that it’s Sunday and I’ve finally had time to catch up on some sleep.

You’d be wrong.

What I really need to vent about this afternoon is toilet paper dispensers. You see, I’ve been using lots of bathrooms with stalls and with those new-fangled huge toilet paper dispensers.

Do you remember in the olden days when a toilet paper dispensing system was relatively easy to understand? There’d be room for at most two rolls, the normal smallish kind, and if that wasn’t enough there’d be extra rolls somewhere for you to use. Granted, sometimes there weren’t, and sometimes there were but they got wet or dirty rolling on the floor.

Nowadays there are they enormous plastic cases which contain about 4 huge rolls of toilet paper, and I guess it’s a good thing in terms of how often toilet paper runs out, although it’s not an excellent idea in terms of the overall cleanliness of the bathroom, since you can mostly fill those fuckers up and leave for vacation.

But I’m not here to complain about dirty bathrooms. What I’d like to complain about is that these huge toilet paper dispensers, which are now about 3 feet in diameter, are for some reason always placed at the same level, at their center, as their older counterparts which contained two small rolls and opened up in the front.

The old dispenser would allow you to get toilet paper at approximately shoulder level. It was a pretty good system.

But these new ones dispense out at the bottom, so now we’re immediately talking about having to bend down to even find a corner of paper, usually blind. God forbid if it’s a new roll.

And once you catch hold of the ephemeral toilet paper corner, you have to then pull out some paper, which sounds easy, but your natural inclination is to pull on the paper by pulling towards yourself. This causes your tiny little corner of toilet paper to be immediately cut off by the serrated edge of the dispenser mouth.

So what you need to do, unless you are satisfied with one square inch of toilet paper (which I am not, in general), is you need to devise a two-handed system of pulling where one hand acts as a soft corner, almost like a ball bearing pulley, directly below the dispenser mouth, and the other hand pulls on it, at first straight down and then around the other hand and up.

A metaphorical second hand when desperately grasping for toilet paper

But mind you, you’re already stooping over to get the paper. So at this point you are basically on hands and knees trying to get more than one square inch of goddamned toilet paper.

People. People. People who install bathrooms, I’m talking to you right now.

Don’t you ever go to the bathroom yourself? Can’t you modify your installation procedure now that these big toilet roll dispensers have been around now for 10 years? Can we get them to dispense at shoulder level some time in the near future? Is this some way of keeping people from using too much toilet paper? If so, it’s not working. I always take too much because I always figure, “what the hell, now that I’ve constructed a pulley system I might as well see what she can do. I’ma gonna let her rip.”

Categories: rant

HCSSiM Workshop day 6

July 8, 2012 4 comments

A continuation of this, where I take notes on my workshop at HCSSiM.

What is a group

We talked about sets with addition laws and what that really means. We noted that associativity seems to be a common condition and that some weird operations aren’t associative. Example: define a*b for a pair of integers (a,b) to be the sum a + b^2. Then we have:

(1*1)*1 = 2*1 = 3 but 1*(1*1) = 1*2 = 5.

We decided those things would make them crappy generalized addition operators. We ended up by defining what a group is, although we call it a “Karafiol” so that when our final senior staff member P.J. Karafiol arrives in a couple of weeks he will already be famous.

We showed that \mathbb{Z}/n \mathbb{Z} is a Karafiol and that, if you remove all of the congruence classes with numbers that aren’t relatively prime to n, you can also turn \mathbb{Z}/n \mathbb{Z} into a group under multiplication. I was happy to hear them challenge us on whether that would be closed under multiplication. The kids proved everything, we were just mediating. They are awesome.

Graphs

We had already talked about graphs (“Visual Representations”) as defined by vertices and edges. Today we talked about being able to put vertices in different groups depending on how the edges go between groups, so we ended up talking about bipartite and tripartite graphs. We ended up being convinced that the complete bipartite graph on 6 vertices (so 3 on each side) is not planar. But we haven’t proven it yet.

Special Lecture

Saturday morning we have only two hours of normal class, instead of 4, and we have a special event for the late morning. Yesterday Johan was visiting so he talked to them about the projective plane over a finite field, and how every line has the same number of points. He talked to them a bit about his REU at Columbia and his Stacks Project and the graph of theorems t-shirt that he wore to the talk. I think it’s cool to show the students this kind of thing because they are the next generation of mathematicians and it’s great to get them into online collaborative math as soon as possible. They were impressed that the Stack Project is more than 3000 pages.

Categories: math education

HCSSiM Workshop day 5

July 7, 2012 2 comments

A continuation of this, where I take notes on my workshop at HCSSiM.

Modular arithmetic

We examined finite sets with addition laws and asked whether they were the “same”, which for now meant their addition table looked the same except for relabeling. Of course we’d need the two sets to have the same size, so we compared \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} and \mathbb{Z}/4\mathbb{Z}. We decided they weren’t the same, but then when we did it for \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/4\mathbb{Z} and \mathbb{Z}/12 \mathbb{Z}, and decided those were. We eventually decided it worked the second time because the moduli are relatively prime.

We essentially finished by proving the base case of the Chinese Remainder Theorem for two moduli, which for some ridiculous reason we are calling the Llama Remainder Theorem. Actually the reason is that one of the junior staff (Josh Vekhter) declared my lecture to be insufficiently silly (he designated himself the “Chief Silliness Officer”) and he came up with a story about a llama herder named Lou who kept track of his llamas by putting them first in groups of n and then in groups of m and in both cases only keeping track of the remaining left-over llamas. And then he died and his sons were in a fight over whether someone stole some llamas and someone had to be called in to arbitrate. Plus the answer is only well-defined up to a multiple of mn, but we decided that someone in town would have noticed if an extra mn llamas had been stolen.

Cardinality

After briefly discussing finite sets and their sizes, we defined two sets to have the same cardinality if there’s a bijection from one to the other. We showed this condition is reflexive, symmetric, and transitive.

Then we stopped over at the Hilbert Hotel, where a rather silly and grumpy hotel manager at first refused to let us into his hotel even though he had infinitely many rooms, because he said all his rooms were full. At first when we wanted to just add us, so a finite number of people, we simply told people to move down a few times and all was well. Then it got more complicated, when we had an infinite bus of people wanting to get into the hotel, but we solved that as well by forcing everyone to move to the hotel room number which was double their first. Then finally we figured out how to accommodate an infinite number of infinite buses.

We decided we’d proved that \mathbb{N} \times \mathbb{N} has the same cardinality as \mathbb{N} itself. We generalized to \mathbb{Q} having the same cardinality as \mathbb{N}, and we decided to call sets like that “lodgeable,” since they were reminiscent of Hilbert’s Hotel.

We ended by asking whether the real numbers is lodgeable.

Complex Geometry

Here’s a motivating problem: you have an irregular hexagon inside a circle, where the alternate sides are the length of the radius. Prove the midpoints of those sides forms an equilateral triangle.

It will turn out that the circle is irrelevant, and that it’s easier to prove this if you actually Circle is entirely prove something harder.

We then explored the idea of size in the complex plane, and the operation of conjugation as reflection through the real line. Using this incredibly simple idea, plus the triangle inequality, we can prove that the polynomial

 3z^{17} + 2iz^{12} - (1+3i)z^{10} + .017z^{5} - 17

has no roots inside the unit circle.

Going back to the motivating problem. Take three arbitrary points A, B, C on the complex plane (i.e. three complex numbers), and a fourth point we will assume is at the origin. Now rotate those three points 60 degrees counterclockwise with respect to the origin – this is equivalent to multiplying the original complex numbers by e^{\frac{i \pi}{6}}. Call these new points A’, B’, C’. Show that the midpoints of the three lines AB’, BC’, and CA’ form an equilateral triangle, and that this result also is sufficient to prove the motivating problem.

Categories: math education

HCSSiM Workshop day 4

July 6, 2012 2 comments

A continuation of this, where I take notes on my workshop at HCSSiM.

As usual, we started with the students showing us solutions to their problem sets. Today one of them showed a sharp lower bound on the Fibonacci numbers, although he hadn’t proved it was sharp.

Arithmetic modulo n

Then we talked more about how we can talk about addition, and now also multiplication, with a finite set of symbols \{0, 1, 2, \dots n-1\}. Then we wrote out the multiplication tables for n = 6 and n = 7. The students noticed and proved that there is a multiplicative inverse for a modulo n if and only if gcd(a, n) = 1, using what we did yesterday with the Edwinian Algorithm and the way we turned it around to express gcd’s as linear combinations. We defined some notation and the natural map:

\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}.

Finally, we wrote down the subsets of \mathbb{Z} which map to each element of \mathbb{Z}/n\mathbb{Z}.

Posets and graphs

We went back to the idea of a partial ordering, and came up with a bunch of examples (including the set of integers under “divides evenly into”). We talked for a while about how to represent partial orderings, and finally settled on a graph. We talked a bit about poset chains and antichains, and then we formally defined a graph (we voted and decided to call it a “visual representation”).

The complex plane

The founder and director of the program is David Kelly. The program has been going for 40 years now and for maybe the first time ever Kelly himself isn’t teaching a workshop, so I’ve invited him to do some guest lectures in my workshop on complex geometry. It’s always a treat to watch him teach.

Kelly came in and built on the idea of “modding out by an integer” by definine \mathbb{R}[x]/(x^2 +1), which he described as “modding out by a polynomial”. He asked the students to investigate this idea and they eventually discovered that if x^2 +1 = 0, it also must be true that x^2 = -1, which allowed them to write every polynomial with as a linear combination of 1 and x, so as a + bx. Then they thought about the addition law and multiplication law and decided they had the complex plane. So we decided to start calling x the symbol “i“.

We then defined e^{i \theta} to be the point on the unit circle cos(\theta) + i sin(\theta), discarding once and forever the notation cis(\theta) (we justified this definition in last night’s problem set). We showed we could recover useful trigonometric identities that way (I skipped trigonometry myself and this is the only way I ever knew how to derive those identities) and that we could alternatively write any point on the complex plane in polar coordinates, so as r e^{i \theta}. Finally, we noted that if we multiply anything by the number r e^{i \theta}, we end up stretching it by r and rotating it by \theta.

We heard a funny story Kelly told us about taking a test to get his pilot’s license. He was given 30 minutes and lots of suggestions once to compute a heading which involved a calculation in polar coordinates. Since he was a mathematician he was too proud to accept the props they offered him, and finished with 29 minutes to spare. Once aloft though he quickly realized his calculation simply couldn’t be correct, but fudged the test by eyeballing it and following a highway. Turns out that pilots use due north as the axis along which the angle is zero, and then they go clockwise from there. I’m not sure what the moral of the story is, but it’s something like, “don’t be arrogant unless it’s a clear day and you have a backup plan.”

Categories: math education

Nim

July 5, 2012 4 comments

Yesterday I gave a “Prime Time” talk here at HCSSiM, which is an hour long talk to the entire program. I talked about the game of Nim.

Nim is an old game (that’s the kind of in-depth historical information you’re gonna get from me) where you have a certain number of piles and each pile has a certain number of stones in it. There are two players and you take turns removing as many stones from any one pile as you want. The last person to remove a stone wins. Or, to anticipate my confusion later on, the person who gives back an empty game to their opponent wins.

You can play Nim online here with 3 or more piles and where the stones are matchsticks.

A bunch of the kids had never played so I got them to come to the board to play 2- and 3-pile Nim. Eventually it was  discovered that, as long as you start out with uneven piles with 2-pile Nim, you have a winning strategy by making them even. But it wasn’t clear how to win with 3-pile Nim, so we put that question in our back pocket for later.

I then changed it up a bit and put a rook on a chessboard, and said the point was to land on the top left corner, and you could only go up and to the left. They quickly realized it was just two-pile Nim again and the winning strategy was to get the rook on the diagonal. Then I switched it up further and made it be a queen, not a rook, and allowed the piece to move up, left, and diagonally up and left. This was harder.

We then decided that, when you have a game like Nim which is two-player, and the players share the same pieces (so not chess) and moves, and when the game gets smaller every time someone makes a move, then every position can be considered either “winning” or “losing”, by growing the game up from smaller games. If you can only get to winning positions, then you’re at a losing position. If there’s an option to get to a losing position, then you’re at a winning position. A consequence of this way of thinking of things is that a “game” can be described by the options you have when given a chance to play (along with the rules that define the options).

We then discussed adding two games A and B, which just means you get to play from either A or B but not both. We decided that 2-pile Nim is already of the form A + A, where A is 1-pile Nim. And furthermore, 1-pile Nim is pretty dumb – the winning strategy is always to just take away all the stones. But in spite of this, 5 stones is not the same as 6 stones for 1-pile Nim, since you can get to 5 stones from 6 but not vice versa.

Then I defined A ~ B if for all other (impartial) games H, A + H always has the same winner as B + H. It’s easy to see ~ is an equivalence relation, and that G + G is always winning (again, by mimicking your opponent’s moves). It’s also pretty easy to see that if A is winning, then A + G ~ G for all G.

But it’s a bad definition of ~ in that it seems to take an infinite amount of work to decide if A ~ B, since you’d have to check something for all possible H. We decided to improve this by proving that G ~ G’ if and only if G + G’ is winning. It is pretty easy to do this.

Then it was time for action, namely to prove the Sprague-Grundy Theorem which states that:

Every impartial game G has G ~ [N] for some N, where [N] denotes 1-pile Nim with N stones.

We prove this by showing recursively on the size of the game that N above (also called the “Nimber” of the position) is just the “mex” function, which is the minimum excluded non-negative integer. In other words, we designate the winning position as having N = 0, and then we grow the game up from there. If a given position can get to a “0” position, then its Nimber is at least 0 – in fact it’s the minimum number that it can’t reach in one move.

In particular, if you are at a position with Nim number non-zero, you can get to a zero position (i.e. a winning position), as well as any smaller Nim position, and if you are at a position with Nim number zero, you can only get to non-zero positions. This is similar to the losing-winning dichotomy except slightly more nuanced.

We then drew a Nimber addition table, which is the same as the chessboard problem with a rook. We used this to reduce 3-pile Nim to 2-pile Nim and worked out a winning strategy for the 3-pile Nim game (2, 5, 3).

Next we drew a Nimber table for the queen on a chessboard problem. We decided we knew how to play that game plus a 3-pile Nim game.

I was running out of time by this time but I ended with showing them a fast way to find the Nimber of the sum of a bunch of games whose Nimbers you already know, namely the bitwise XOR function. I didn’t have time to prove it (it’s not hard to see with induction on the number of games you’re adding up) but it’s easy to see this recovers our “mimicking” strategy with two games.

Categories: math education

HCSSiM Workshop day 3

July 5, 2012 1 comment

A continuation of this, where I take notes on my workshop at HCSSiM.

Equivalence Relations and Partial Orderings

After going over many proofs of the geometry problem from last night’s problem set, I corrected the mistake in the “antisymmetric” property and we went through plenty of examples of equivalence relations and partial orderings. We ended with linear orderings, the real numbers, and the less than or equal relation.

Adding modulo n

Next we went back to the idea of maps f: X \times X \rightarrow X and got the kids to come up with a whole bunch of examples for X = \mathbb{Z}, such as f(a, b) = \lceil \frac{a}{2 \dot b +1} \rceil. We eventually got them to come up with stupider examples like (a, b) \mapsto a and (a, b) \mapsto a+b. Then we switched it up to the finite set [n] = \{1, 2, 3, \dots, n\} and got them to generalize addition. Since n really started to look like an identity element under this operation, we decided to define notation for the set \{0, 1, 2, \dots, n-1\}, which is like [n] but on its side.

Pigs-in-hole Principle

We introduced the pigeonhole principle (but since our camp mascot is a yellow, pig, we call it pigs-in-hole). We actually defined the slightly more general idea that, if you have n holes and k pigs which need to get put into holes, at least one of the n holes to contain at least \lceil k/n \rceil pigs. With that we proved that at least 2 people in New York City have the same number of hairs on their head, that five points in a 1 by 1 square are withing distance \sqrt{2}/2 of each other, that in a group of $n$ people at least two people will have had the same number of handshakes, and others.

Greatest Common Divisor

We asked the kids what the greatest common divisor of a and b is (denoted gcd(a, b)) and how to compute it. We spent a long time chasing down rabbit holes and proving other things that didn’t help us find the greatest common divisor but were true. For example, we showed that if you divide a and b by their greatest common divisor, you end up with numbers that are relatively prime. We even showed there are representations of a and b as products of primes, but since we couldn’t yet prove those were unique representations, we could use that to come up with a way to find the “common primes.”

Eventually we thought of a trick to reduce the problem, namely the division algorithm. Actually Edwin thought of the trick, and it eventually became the Edwinian Algorithm (not like it’s usually called, namely the Euclidean Algorithm). Edwin observed that gcd(a, b) = gcd(a - bq, b) when you write a = bq + r for 0 \leq r <b.

Once we had the Edwinian Algorithm, we realized we could go backwards and express gcd(a, b) as a linear combination of a and b, and we used that to prove a very important property of primes, namely that if p is a prime and p | ab then either p|a or p|b or both. This allowed us to show that the prime factorizations we’d found before for a and b were in fact unique up to relabeling, which we left for homework.

So it turns out I’m not going to be able to make the homeworks public, but we had an awesome problem set with lots of pigeon hole problems and Edwinian Algorithm problems. We asked them to decide which approach to calculating gcd(a,b) is faster, through the Edwinian Algorithm or via prime factorizations.

Categories: math education