



















m = a_{1}n + r_{1}









1337944608 = 317(4216212) + 1405404.

Next, we note that

4216212 = 3(1405404) + 0









r_{1} = n\mod m

r_{2} = 2n\mod m





in \mod m = jn \mod m

which implies

(i-j)n\mod m = 0


cn \mod m = 1.



Pretty slick, no?






















Road to the Proof.




First, note that









Putting this all together, we have



We clean it up a bit, and state the following:






Next time, we’ll talk about applications!

Pick’s Theorem.

November 22, 2012












Motivating Pick’s Theorem.




Easy Polygons.









































The Theorem.









Given all of this, let’s jump into the proof.

























The associated polynomials in this case are given by Faulhaber’s formula:













































[Note: It’s been a while!  I’ve now completed most of my pre-research stuff for my degree, so now I can relax a bit and write up some topics.  This post will be relatively short just to “get back in the swing of things.”]


In Group Theory, the big question used to be, “Given such-and-such is a group, how can we tell which group it is?”


The Sylow Theorems (proved by Ludwig Sylow, above) provide a really nice way to do this for finite groups using prime decomposition.  In most cases, the process is quite easy.  We’ll state the theorems here in a slightly shortened form, but you can read about them here.  Note that subgroup which is of order p^{\beta} for some \beta is unsurprisingly called a p-subgroup. A p-subgroup of maximal order in G is called a Sylow p-subgroup.


Theorem (Sylow).  Let G be a group such that |G| = p^{\alpha}m for p\not| m.  Then,

  1. There exists at least one subgroup of order p^{\alpha}.
  2. The Sylow p-subgroups are conjugate to one-another; that is, if P,Q are Sylow p-subgroups, then there is some g\in G such that gPg^{-1} = Q.  Moreover, for all g\in G, we have that gPg^{-1} is a Sylow p-subgroup.
  3. The number of Sylow p-subgroups of G, denoted by n_{p}, is of the form n_{p} \equiv 1\mbox{ mod } p.  In other words, n_{p} divides m.


This first part says that the group of Sylow p-subgroups of G is not empty if p divides the order of G.  Note that this is slightly abbreviated (the second part is actually more general, and the third part has a few extra parts) but this will give us enough to work with.


Problem: Given a group  |G| = pq for p,q prime and p < q, is G ever simple (does it have any nontrivial normal subgroups)?  Can we say explicitly what G is?


We use the third part of the Sylow theorems above.  We note that n_{q} | p and n_{q} \equiv 1\mbox{ mod } q, but p < q so this immediately implies that n_{q} = 1 (why?).  So we have one Sylow q-subgroup; let’s call it Q.  Once we have this, we can use the second part of the Sylow theorem: since for each g\in G we have gQg^{-1} is a Sylow q-subgroup, but we’ve shown that Q is the only one there is!  That means that gQg^{-1} = Q; this says Q is normal in G.  We have, then, that G isn’t simple.  Bummer.

On the other hand, we can actually say what this group is.  So let’s try that.  We know the Sylow Q-subgroup, but we don’t know anything about the Sylow P-subgroups.  We know that n_{p} \equiv 1\mbox{ mod }p and n_{p} | q, but that’s about it.  There are two possibilities: either n_{p} = 1 or n_{p} = q.

For the first case, by using the modular relation, if p does not divide q-1 then this forces n_{p} = 1; this gives us a unique normal Sylow p-subgroup P.  Note that since the orders of our normal subgroups multiply up to the order of the group, we have PQ \cong P\times Q \cong G; in other words, G \cong {\mathbb Z}_{p}\times {\mathbb Z}_{q}.

For the second case, n_{p} = q.  We will have a total of q subgroups of order p and none of these are normal.   This part is a bit more involved (for example, see this post on it), but the punch line is that it will be the cyclic group {\mathbb Z}_{pq}.


I’ll admit that the last part is a bit hand-wavy, but this should at least show you the relative power of the Sylow theorems.  They also come in handy when trying to show something either does or does not have a normal subgroup.  Recall that a simple group has no nontrivial normal subgroups.


Question.  Is there any simple group with |G| = 165?


I just picked this number randomly, but it works pretty well for this example.  We note that |G| = 165 = 3\cdot 5\cdot 11.  Let’s consider, for kicks, n_{11}.  We know n_{11} must divide 3\cdot 5 = 15 and it must be the case that n_{11} \equiv 1\mbox{ mod } 11; putting these two facts together, we get n_{11} = 1.  This immediately gives us a normal subgroup of order 11, which implies there are no simple groups of order 165.


Question.  Is there any simple group with |G| = 777?


Alas, alack, you may say that 777 is too big of a number to do, but you’d be dead wrong.  Of course, 777 = 3\cdot 7\cdot 37.  Use the same argument as above to show there are no simple groups of this order.


Question.  Is there any simple group with |G| = 28?


Note that 28 = 2^{2}\cdot 7 so we need to do a little work, but not much.  Just for fun, let’s look at n_{7}.  We must have that it is 1 modulo 7 and it must divide 2^{2} = 4.  Hm.  A bit of thinking will give you that n_{7} = 1, which gives us the same conclusion as above.


Of course, there are examples where this doesn’t work nicely.  Think about the group of order 56, for example.  In order to work with these kinds of groups, one must do a bit more digging.  We will look into more of this later.

[Note: It’s been too long, mathblog!  I’ve been busy at school, but I have no plans to discontinue writing in this thing.  For longer posts, you’ll have to wait until I have some free time!]


You’ve probably seen a graph before: they’re collections of vertices and edges pieced together in some nice way.  Here’s some nice examples from wikipedia:

File:McGee graph.svg

File:Moser spindle.svg



One theorem that I constantly run into (mainly because it’s relevant to homology) is the following:


Theorem.  Given some connected finite graph G, there exists a spanning tree of G.


Note that such a tree is not generally unique.  You might want to find one or two in the graphs above to prove this to yourself!  Nonetheless, even though this proof seems like it would be a bit intimidating (or, at least, by some sort of tedious construction), it’s actually quite nice.  Let’s go through it.


Proof. We’ll prove this by the number of cycles in G.  If G has no cycles then it is, itself, a tree; hence, G is its own spanning tree.  Suppose now that any graph with n cycles has a maximum spanning tree.  Given some graph with n+1 cycles, take any one of these cycles and delete any edge (but not deleting the vertices!).  This reduces the number of cycles by (at least) one, so there is a spanning tree by induction.  In fact, since we have not deleted any vertices, we may replace the edge we removed and this tree will still span the graph.  \Box


A couple of questions about this for the eager reader.  Where did we use connectedness?  Where did we use finite-ness?  What if we were given an infinite graph?  Is there a nice notion of cycles for this kind of graph?  Draw some pictures and think about it!

Baire Category Theorem.

January 5, 2012

During one of my previous qualifying exams, one of the questions looked, at first, to be a basic Fourier Analysis question.  The hint, though, was to use the Baire Category Theorem.  The problem and hint looked so unrelated that the phrase has become somewhat of a running joke for some of us in the department (“How are we going to prove this is a cofibration?”  “Oh, easy, just use the Baire Category theorem.”).

The more I read about it, the more I realized that the Baire Category theorem pops up much more than I realized and in a number of surprising and diverse topics.  This post is just to introduce you to the BCT and to show off some of its raw power.  One of the results below is one that I genuinely don’t believe — that is, I know it has to be true (it was proved!) but it just seems so outrageous that I can’t being myself to believe it!  But, we’ll get to that.


Leading up to the Theorem.

There are a few different formulations of the theorem, so I’ll pick the one that turns out to be most common in what I’ve read.  First, let’s quickly define some terms.


Definition.  A complete metric space is a metric space where each Cauchy sequence converges to a point in the space.


For example, {\mathbb R} is complete, but {\mathbb Q} is not complete since in the latter space we can take a sequence like: 1, 1.4, 1.41, 1.414, … which are all rational numbers that converge to \sqrt{2}, but \sqrt{2} isn’t in the rational numbers.


Definition.  A subset of a space is dense if the closure of the subset is the entire space.


For example, {\mathbb Q} is dense in {\mathbb R} since the closure of {\mathbb Q} is {\mathbb R}.  The irrationals are also dense in {\mathbb R}.  The integers, {\mathbb Z}, are not dense in {\mathbb R} because the closure of the integers in {\mathbb R} is just {\mathbb Z} (why?).


Q: What are the dense subsets of a non-empty discrete space?  Does this make sense “visually”?


Definition.  The interior of a subset Y is the largest open set contained in Y.  In metric spaces, it’s the union of all the balls contained in Y.


The next definition might be a little strange if you haven’t seen it before and, in fact, there are two nice (equivalent) ways of thinking about this concept.  I’ll list both.


Definition.  A set Y is nowhere dense in some space X if either (and hence both):

  1. The interior of the closure of Y in X has empty interior.
  2. \overline{Y^{C}} = X; that is, the closure of the compliment of Y is dense in X.


This last definition might seem a bit strange to you, but the “image” of this is the following: a nowhere dense set is literally a set which is not dense anywhere — but what does that mean?  Density isn’t usually considered a local property.  How do we usually check density, though?  We take the closure of the set and if it’s the whole space then we say the set is dense.  If we wanted to make this more “local”, what we could say is that we don’t get any neighborhoods of the whole space.  This is the same as saying the closure of our subset has no open neighborhoods inside of it or that it has empty interior.  This givers us the first definition.  The second is a direct consequence which is sometimes more useful to think about depending on your original subset.


Example.  We have {\mathbb Z}\subseteq {\mathbb R} with the standard topology.  Is {\mathbb Z} nowhere dense in {\mathbb R}?  Note that \bar{{\mathbb Z}} = {\mathbb Z} and this has empty interior.  By the first definition, {\mathbb Z} must be nowhere dense in {\mathbb R}.  If we wanted to use the second definition, we could say that the compliment of {\mathbb Z} in {\mathbb R} is just everything but the integers; but the closure of this is {\mathbb R} which means the compliment of {\mathbb Z} is dense in {\mathbb R} giving us the same conclusion.  This is not surprising, since the elements of {\mathbb Z} are “pretty far apart” in {\mathbb R}.


Example.  Our favorite limit-point example, Y = \{\frac{1}{k}\,|\, k\in {\mathbb N}\} is a subset of {\mathbb R}.  Is it nowhere dense?  Using the first definition, the closure is just Y\cup \{0\} which has empty interior (why?).  With the second definition, the compliment of Y has closure equal to {\mathbb R} and so it is dense.  In either case, this proves that Y is nowhere dense in the reals.


Example.  The ball (0,1)\subseteq {\mathbb R}.  The closure of this set is [0,1] which has interior equal to (0,1).  Therefore, this set is not nowhere dense.  That’s a bit sad.  But you can see that this set really is “somewhere dense” visually.


Example.  The Cantor set is closed (there are a number of cute ways to prove this) so to show it is nowhere dense in [0,1] it suffices to show that it has empty interior by the first definition.  Prove it!


You may have been surprised with the last example, or even the \frac{1}{k} example.  For the latter one, it seems like the points are really “getting close” to 0, so maybe some density should occur; it’s not the case, though!  For the Cantor set, many points in this set can be “very close” to one-another so it is a bit surprising that this set is not dense anywhere.  If one goes through the construction slowly, you’ll see why the points are “just far enough apart” to reasonably be considered (that is, intuitively considered) nowhere dense.


The Theorem.

Why would we ever care about nowhere dense sets?  Well, they’re kind of crappy in the following sense: even if we unioned a countable number of nowhere dense subsets together, we could never recover the original set.  An analogy from anthropology would go like this: we might be able to find tons of copies of some ancient book, but if each of them are missing a whole lot (nowhere dense) then even combining them all together we can’t recover the original manuscript.


Oh.  And why do jigsaw puzzle makers make each of the puzzle pieces look like that?

Because if they made them nowhere dense, we would never be able to finish the puzzle.  Buh-dum-tsh.


Theorem (Baire Category Theorem).  A non-empty complete metric space is not the countable union of nowhere dense sets.


This shouldn’t be too scary to you at this point.  Let’s do some immediate consequence examples.


Example.  Do you think we could union a countable number of things that look like {\mathbb Z} together and get something like the real numbers?  That is, maybe we could take

{\mathbb Z} = \{\dots, -1,0,1,2,\dots\}

{\mathbb Z} + \frac{1}{2} = \{\dots, -\frac{1}{2}, \frac{1}{2}, \frac{3}{2}, \frac{5}{2},\dots\}

{\mathbb Z} + \frac{1}{3} = \{\dots, -\frac{2}{3}, \frac{1}{3}, \frac{4}{3}, \frac{7}{3},\dots\}

and so on, and union them all together to make {\mathbb R}.

Nope.  The BCT says to not even try.  Each of these translates of {\mathbb Z} is nowhere dense, so a countable union of them would not get you {\mathbb R}.


Non-Example.  What if we did the same thing as above, but we wanted to union them all together to get {\mathbb Q}, the rationals.  What would Baire say about that?  Probably, “Don’t use my theorem with this, because {\mathbb Q} isn’t a complete metric space.”


Non-Example.  What if we tried the same thing with the {\mathbb Z} translates above as subsets of {\mathbb R}, but we union them all and then union that with the irrational numbers.  In this case, too, we can’t use Baire, because the irrational numbers are actually dense in the reals; the BCT doesn’t say anything about unions with dense subsets.


Example.  What if we have a complete metric space with no isolated points?  Can it be countable?

(Recall, an isolated point is one which has a neighborhood not containing any other point of the space.  For example, if we took \{0\}\cup [1,2] in the subspace topology of the reals, then \{0\} is an isolated point of this subspace since it, itself, is open and it contains no other point of the subspace.)

In this case, we can cleverly use the BCT to show that every complete metric space with no isolated points is uncountable.  Suppose it were countable.  Then every point of the space is nowhere dense (!  Why is this the case?  What is the closure of a point?  What is its interior?  Does this argument show why we cannot have isolated points?).  But since our space is countable, it is the countable union of its points, each of which is nowhere dense.  Baire would have a real problem with that.  This contradicts BCT, so such a space must be uncountable.


Why is it called the “Category” theorem?

This “category” isn’t the same category as in category theory.  The term comes from the original language that the theorem was stated in.  It’s a bit ugly, so I’ve yet to mention it, but I might as well spell it out for you now:

  • We call a set of First Category if it can be written as a countable union of nowhere dense sets.  This is also called a meagre set.  (Amusingly, the meagre is also the name of a fish.)  Sometimes this is Americanized (that is, bastardized) and pronounced as “meager set” which would mean something like, “thin set” or “set having little substance” which is, intuitively, what this set should “look” like.
  • We call a set of Second Category if it is not of first category.


We also have what’s called a Baire Space, which is just a space where every non-empty open set is of second category.  This means, intuitively, that an open set needs to have some “density” to it.  The original Baire Category theorem stated that every complete metric space is a Baire Space.  This is “almost” equivalent to what we have above; see below.


Other Formulations of the BCT.

There are three distinct formulations of the BCT that are generally given (the texts  I have in my office give at most two, but the third is a consequence of the first so this is perhaps why).  Right above this, we give one of them.


BCT (1).  Every complete metric space is a Baire space; that is, every open subset in a complete metric space is not the countable union of nowhere dense sets.

BCT (3).  Every complete metric space is not the union of nowhere dense sets.


I list these together because it’s clear that the third is a consequence of the first.  (These numbers are because the second BCT is actually called “the second BCT” in a few places.)


BCT (2).  Every locally compact Hausdorff space is a Baire space.  Recall that locally compact means that every point of our space has a compact neighborhood.


Note that it’s not the case that the first BCT implies the second, and it’s not the case that the second implies the first.  It would be nice if there were some meta-BCT that implied both of them, but when we write down exactly what we need for something to be a Baire space, we’re left with a couple of choices; if you’re interested in this, you should check out the proofs for both of these theorems and see where we’re using locally compact verses where we’re using complete.

A Surprising Result.

One of the coolest results I’ve seen using the BCT (and, indeed, one of the coolest results I’ve seen perhaps in general) is the following.


Maybe, first, it’s nice to ask the following question (that you can even ask to your friends!): what’s your idea of a “general” continuous function?  That is, just think of the most generic continuous function you can.  Visualize it.  Maybe draw it.  What do you have?  Probably some sort of polynomial.  (When I do this, I actually draw fifth degree polynomials most of the time.)  Is this really so generic?


First, let’s just define exactly what we mean by “generic.”


Definition.  If A is a subset of some space X, the compliment of A is nowhere dense, and all points in A share some property, then we call this property generic of X.


This should be reasonable: something genertic should be representative of the whole.  That is, if something is not generic, then it should not happen very often; in our language, the set of non-generic things should be nowhere dense.


Theorem (Banach, Mazurkiewicz, 1931).  The generic (in the sense of the above definition) continuous function on a compact interval (that is, f\in C^{0}([a,b],{\mathbb R})) is nowhere differentiable, and not monotone on any subinterval of [a,b].


Just think about that for a second.  Let it sink in.  Nowhere differentiable is strange enough; we can (and will) use the BCT to talk about a nowhere differentiable function.  But, what’s more, it’s not monotone on any subinterval, no matter how small.  And, yes, this function is generic.  What.


As a note, somewhat strangely, because of the above definition of “generic” it is entirely possible to have two different kinds of “generic” things representing some space.  The definition doesn’t say anything about the generic property being unique and, in general, it isn’t.



BCT in Functional Analysis.

to do.

I’m going through a few books so that I can start doing lots and lots of problems to prepare for my quals.  I’ll be posting some of the “cuter” problems.


Here’s one that, on the surface, looks strange.  But ultimately, the solution is straightforward.


Problem.  Find an uncountable subset A\subseteq [0,1] such that A - A = \{a - b\,\mid\,\,a,b\in A\} has empty interior.


Read the rest of this entry »

I just saw this problem in a book of algebra problems, and I thought it was nice given one of the previous posts I had up here.


Problem.  Show that 11, 111, 1111, 11111, … are not squares.


You ought to think about this for a bit.  I started by supposing they were squares and attempting to work it out like that; unfortunately, there are some strange things that happen when we get bigger numbers.  But.  You should see a nice pattern with the last two digits.  Click below for the solution, but only after you’ve tried it!

Read the rest of this entry »