Two Turtles Playing with a Hammer: A Game.

January 16, 2012

While I’m finishing up the Baire Category post, let’s have a little fun. Here’s a game I like to play when I’m in my office hours and have literally nothing else to do. I call it, “Two Turtles Playing With A Hammer.”

The game is simple.

Pick a number (or, have a friend pick one for you!). It’s more fun if you pick a number that’s a well-known irrational or transcendental number. Let’s call this number $\alpha$ .
Pick a natural number (for example, 4 or 12). Usually, 2, 3, 4, or 6 give the nicest looking results. Let’s call your number $n$ .
The point of the game is to approximate $\alpha$ using a sequence that looks like this:

$\displaystyle\frac{\pi^{n}}{b_{1}} + \frac{\pi^{n}}{b_{2}^{2}} + \frac{\pi^{n}}{b_{3}^{3}} + \dots$

where all the $b_{i}$ ’s are natural numbers. If this is not possible to do, you lose. Else, you win! [Of course, you can feel free to make your own game where this is an alternating sequence.]

An example. Let’s just do one that I played around with a bit:

$(\pi^4)/57 + (\pi^4)/67^2 + (\pi^4)/37^3 \approx \sqrt{3}$ .

Of course, the game is rather pointless, but you can say to your friends, “Look at this! This crazy sum of stuff is pretty dang close to $\frac{\sqrt{2}}{2}$ .” They’ll be impressed.

[Note: It may be a good (undergraduate-level) exercise to think about the following: given that we only add terms, and given that the denominators must be elements of the naturals, then (given some $n$ ) what numbers can we make from these sequences? What if we also set one of the $b_{i}$ ’s in the assumption (for example, making $b_{3} = 5$ )?]

Edited: I fixed the note above. Another good undergraduate-level question is: what if we allow only one term to be subtracted; can we make any real number? If they’re particularly good at programming, you could ask them to write a program that approximates any number to some number of places with such a sequence (either from the game or using a single subtracted term).

Posted by James

Filed in fun, game

2 Comments »

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):

The interior of the closure of $Y$ in $X$ has empty interior.
$\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 R}$ 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.

Posted by James

Filed in examples, functional analysis, point-set topology, undergrad problems

2 Comments »

Teaching the Baire Category Theorem in an Intro Point-set Course: a mini-rant.

January 5, 2012

Whenever I talk to students who have had basic point-set topology, I’m not surprised if they haven’t seen the BCT; it’s near the end of the point-set part of Munkres, and one natural stopping point for a semester-long point-set class is Urysohn’s lemma which is done before BCT. I don’t remember learning the BCT in point-set when I took it and it wasn’t until Functional Analysis that I had to study it again. This is a shame for a few reasons, but I wanted to point out just two.

This theorem is able to be proved (or at least stated) after complete metric spaces are defined and would take only around one lecture to do with applications. Depending on the speed of the professor and the way one works through the book, one probably gets to metric spaces around the middle of the semester. The students have had analysis, and are, therefore, familiar with completeness (or, at worst, they’re comfortable with Cauchy sequences!) so it is not difficult to define complete metric spaces. What else would we need? Nowhere-dense sets. That’s all.
This can be a great “visual” theorem in some spaces. One common problem point-set topology students seem to have is that they will work through definitions without developing any kind of intuition behind what something is (eg, limit points). Therefore, it’s nice to learn properties of spaces we know and love. The BCT is easily applied to the reals, the irrationals, the rationals, and the cantor set. It also is a great brain-stretching exercise to think about how “close” points can be in a nowhere dense set on the real line.

This may be a non-issue for those of you whose point-set class included this, but I wanted to point is out nonetheless. I would go as far as saying that this is “more important” to cover in a first course in point-set than the proof of Urysohn’s lemma [which is the first “deep” result in Munkres]. Of course, the proof is important, but in an introductory course I feel that proving Urysohn’s lemma for metric spaces and stating it for general spaces is a better way to go. Feel free to disagree and yell at me!

Edit: This rant used to be part of the BCT post I made recently, but because it’s not really mathematics and more about teaching I decided to post it on its own so I don’t have to subject everyone to reading my rants.

Posted by James

Filed in point-set topology, rants

Uncountable Subset A of [0,1] with A – A empty.

December 20, 2011

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 »

Posted by James

Filed in cute problems, cute proofs, point-set topology, undergrad problems

2 Comments »

11, 111, 1111, … Not a Square.

December 18, 2011

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 »

Posted by James

Filed in cute proofs, exercises, fun, undergrad problems

3 Comments »

Urysohn’s Lemma for Metric Spaces.

November 20, 2011

After proving this "Deep Result" [cf. Munkres] a professor will (hopefully) say something like: "Yes, the proof is important, but what does this theorem mean? And what does it mean for spaces which are sufficiently nice, like metric spaces?"

Let’s state the result just so we’re all on the same page.

Theorem. The topological space $X$ is normal (that is, every pair of disjoint closed subsets $A, B$ can separated by disjoint neighborhoods) if and only if any two disjoint closed sets can be separated by a function.

The proof of this is not obvious. In fact, it is quite involved. But if $X$ happens to be a metric space, we can make the proof significantly easier by using a function that is similar to a distance function with a few minor modifications. I call this function the standard Urysohn function for metric spaces for lack of a better (or shorter) name. The function is as follows:

$\displaystyle f(x) = \frac{d(x,A)}{d(x,A) + d(x,B)}$

but before proving this theorem in the metric space setting, let’s look at this function. If $A,B$ are disjoint, then it is clear that the denominator is non-zero (why?) so this is defined everywhere. If $x\in A$ we have that this function evaluates to 0. If $x\in B$ then we have that this function evaluates to 1. And the function (since the distance is always non-negative) achieves values in $(0,1)$ for every point not in $A$ or $B$ (convince yourself that this function is continuous and only achieves the values 0 and 1 if the point is in either $A$ or $B$ respectively). This function, therefore, separates $A$ and $B$ .

The next thing you should think about is: what do the preimages of $f$ look like? Draw some pictures! Here’s some pictures to start you off to get the idea. The first is just in ${\mathbb R}$ and the second is in the real plane. Both have the standard topology.

This one is potentially not to scale, but you’ll see that we essentially have a linear relation (since the sum in the denominator will always be 1 in this case) except when we start looking at points that are less than all the points in $A$ or greater than all the points in $B$ . What happens in those cases?

I’ve left this "face" as an exercise because when I did it I was kind of excited about the result. What do the preimages look like? Does this look like something you’ve seen before; maybe in physics? Could you modify the Urysohn equation above to make it seem MORE like something in physics?

So now that you’ve seen these pre-images, it should be relatively clear how to create neighborhoods around each of the open sets. It still takes a bit of proof, but it’s nowhere near the difficulty of the standard Urysohn’s.

I encourage you, further, to draw some pictures. My rule of thumb is: draw at least five different pictures; four easy ones and a hard one. Find out where the preimages are in each of these. Remember, too, that not every metric space looks the same; what would this look like, for example, in the taxi-cab space? Or in some product space? Or in the discrete space…?

Posted by James

Filed in exercises, fun, point-set topology

Factorials and Exponentials.

November 6, 2011

I’ve been working on a problem (here is a partial paper with some ideas) that’s really easy for any calculus student to understand but quite difficult for even wolfram alpha to work out some cases. Here’s the idea:

We know that $\lim_{n\to\infty}\dfrac{e^n}{n!} = 0$ . It’s not hard to reason this out (there are some relatively obvious inequalities, etc.), but I wanted to know what happened if we considered something like:

$\lim_{n\to\infty}\dfrac{e^{e^n}}{n!}$ .

It turns out, this goes to infinity. Maybe this is not so surprising. But, to balance this out, I thought maybe I could add another factorial on the bottom. What about

$\lim_{n\to\infty}\dfrac{e^{e^n}}{(n!)!}$

where this double factorial is just $n!$ with another factorial at the end. It turns out, this one goes to 0.

The problem here is that after $((n!)!)!$ , Mathematica doesn’t seem to be able to handle the sheer size of these numbers. Consequently, I only have a few values for this. I’ve included everything I have in a google-doc PDF (the only way I can think to share this PDF), and I’m looking for suggestions. Here’s some things I thought of:

Stirling’s formula. Unfortunately, this starts to get very complicated very quickly, and if you consider subbing it in for even $((n!)!)!$ it can take up a good page of notes. It also doesn’t reduce as nicely as I’d like.
Considering the Gamma function. It may be easier to work with compositions of the gamma function since it is not discrete and we may be able to use some sort of calculus-type things on it.
Number Crunching. For each of these cases, it seems like there is a point where either the numerator or the denominator "clearly" trumps over the other; this is not the "best" method to use, but it will give me some idea of which values potentially go to infinity and which go to zero.
Asymptotics. I’m not so good at discrete math or asymptotics, so there may be some nice theorems (using convexity, maybe?) in that field that I’ve just never seen before. Especially things like: if $f\sim g$ then $f\circ f \sim g\circ g$ under such-and-such a condition.

Feel free to comment below if you think of anything.

Posted by James

Filed in discrete math, pdf, problems

8 Comments »

Nested Kind of Topology.

October 16, 2011

In the last post, I posted a topology on $\{1,2,3,\dots, k-1\}$ where the open sets were

$\{\emptyset , \{1\}, \{1,2\}, \{1,2,3\},\dots, \{1,2,3,\dots, k-1\}\}$

You can check that this is, in fact, a topology and it, in fact, has exactly $k$ elements. But this is also a really nice topology for intro-topology students. Why? Because it has some strange properties which are easy to get your hands on and prove! Let’s show some of these. For the sake of brevity, let’s call this topology $P$ .

$P$ is not Hausdorff.

This is easy to see. Pick the elements 1 and 2. The only set which contains 1 but not 2 is $\{1\}$ , but there is no set which contains 2 but not 1.

$P$ is $T_{0}$ .

Two points are topologically indistinguishable if they have exactly the same neighborhoods; a $T_{0}$ space is one where each point is topologically distinguishable. It is trivial to check that this holds.

$P$ is connected. (!)

This is somewhat surprising to me (especially because of how disjoint it "seems"!) but if we attempt to find a separation we find that it is impossible: every open set contains 1 except the empty set, so, in particular, no two open sets have trivial intersection unless one is empty.

A function $f:{\mathbb R}\rightarrow P$ is continuous if and only if the sets of all $x$ which map to $n\in \{1,2,3,\dots, k-1\}$ are open (in the standard topology on ${\mathbb R}$ .

This is simply taking preimages. I mention it because actually DRAWING the function on the "plane" (where the "x-axis" is ${\mathbb R}$ and the "y-axis" is $\{1,2,3,\dots, k-1\}$ we get something which does not at all look continuous (unless it is constant —). This is perhaps a good exercise for intro topology students to work out so that they can see that not all continuous maps "look" continuous. Of course, there are many other ways to see this using other spaces.

Limits? What about the sequences in this set? Let’s remind ourselves what convergence is: $\{x_{n}\}\rightarrow x$ if for every open set $U$ containing $x$ there is some $N$ such that for all $n\geq N$ we have $x_{n} \in U$ . Note then that:

$\{1,1,1,1,1,\dots\}$ converges to $1$ .

$\{2,2,2,2,2,\dots\}$ converges to $2$ .

and so on. But then we have

$\{1,2,1,2,1,\dots\}$ which converges to 2, but not to 1 (why?).

$\{1,2,3,1,2,3,\dots\}$ which converges to 3, but not to 2 or 1 (why?).

and so forth. In fact, if we have an infinite number of the numbers $n_{1}, n_{2}, \dots, n_{r}\in \{1,2,\dots, k-1\}$ then this sequence will only converge to $\max(n_{1}, n_{2}, \dots, n_{r})$ which is kind of a neat characterization. In fact, this takes care of most (all?) of the sequences.

Limit Points? A limit point $p$ of a subset $A$ is a point such that for every open $U$ containing $p$ we have $A \cap (U-\{p\}) \neq \emptyset$ .

Consider the subset $A = \{1\}$ and let’s see if there are any limit points. What about 2? Well, we have that $\{1,2\} - \{2\} = \{1\}$ so the intersection of this with $A$ is nontrivial. Similarly, the other open sets containing 2 have nontrivial intersection with $A$ which includes more than the element 2. What about 3? Same deal. And 4? Yes. So we can now ask: what’s the closure of $\{1\}$ ?

Consider $A = \{1,2\}$ and we will start looking at the element 3. Is 3 a limit point? For the same reasons above, it is. So what is the closure of this set?

Let’s be a little adventurous and ask what about $A = \{1, 3\}$ . For the same reasons as above, $4,5,6\dots, k-1$ are all limit points, but what about 2? In fact, it is.

Last, (and this will complete our "characterization" of the closures of our subsets) what about $A = \{2,3\}$ . Clearly we will have $4, 5, 6, \dots, k-1$ as limit points, but the odd one out is 1. And 1 is not a limit point (why not?). That’s a bit sad. So, taking the least element in the subset allows us to describe the closure: it’s the set of every element greater than or equal to it.

Closed sets. It’s a bit interesting to think up what sets we got from taking the closures of each subset, and then to just start with our open sets and take compliments. Do we get the same thing? Neato.

Compactness? A bit trivial in this case. Why? (Maybe extending to infinite things would make this cooler…)

Here’s something weird, too: what is a path in this space? What is a loop? How could we construct something like the fundamental group for this? Homology groups? To those with more experience, these questions might be easy; but it is not obvious to me (at least at this point!) how these constructions should go.

Posted by James

Filed in examples, fun, point-set topology, undergrad problems

1 Comment »

Number of Elements in a Topology.

October 14, 2011

The following question came up today after a brief and somewhat unsatisfying talk I gave on the intuition behind topologies:

Question: Given $n\in {\mathbb N}$ , can we construct a topology $\tau$ such that $\tau$ has exactly $n$ elements?

The solution wasn’t obvious to me until I looked at the pattern of numbers on the back of a thing of Dried Papaya Chunks. For $n = 1, 2$ we can simply take $\emptyset$ and $\{1\}$ to be our sets, but for $n = k$ we need to be a bit more clever. But not much more. Consider:

$\{\emptyset ,\{1\},\{1,2\},\{1,2,3\},\dots \{1,2,3,\dots, k-1\}\}.$

This is a topology on $\{1,2,\dots, k-1\}$ with exactly $k$ elements.

In these examples, the elements which are nested inside each other and is somewhat reminiscent of the "particular point" topology — the topology in which a set is open if and only if it contains some predetermined point (or is empty). In the finite case, how many elements are in the particular point topology? Let’s do a few examples.

If our universe is $\{1\}$ , there are two open sets in the particular point topology (empty set and the whole set).

If our universe is $\{1,2\}$ , then we have three open sets in the particular point topology.

If our universe is $\{1,2, 3\}$ , then we have five open sets in the particular point topology.

If our universe is $\{1,2,3,4\}$ , then we have nine open sets in the particular point topology.

If our universe is $\{1,2,3,4,5\}$ , then we have seventeen open sets in the particular point topology.

If we exclude the empty set, it seems like we will have $2^{k-1}$ elements in our particular point topology. Why is this?

(Hint: Take the last example above with seventeen open sets and suppose the element 5 is your particular point. Write down all the open sets containing 5. Now take your pen and scribble out the 5′s in each of those open sets — do the resulting sets look familiar? Hm.)

Neat. If you take other finite topologies, are there any neat patterns that arise when you increase the number of digits? Is it possible to associate some sort of polynomial or invariant with finite topologies? With infinite topologies? Would this even be useful?

Posted by James

Filed in examples, fun, point-set topology

Summing 1 + 11 + 111 + … and My Problem Solving Technique.

September 17, 2011

This post was inspired by a question on the comment second of my last post about the prime-ness of 111…111. The question is: what’s the sum of 1 + 11 + 111 + … + 111…111? This seemed kind of silly to me (especially if the sum has less than 10 terms) but I quickly realized that I couldn’t figure out a "closed form" without appealing to weird "carry" tricks. So I tried to figure something else out.

Because my final solution to this question was somewhat unsatisfying, I’ve made this a special kind of post! This post will have two main purposes: to try to answer this question and to show what kinds of things I do when I don’t know the answer to a problem. So let’s begin.

First, I scribbled out lots of examples to see if there were patterns in the numbers. Indeed, there are, but there was no nice way to describe them in general without creating a whole lot of variables and expanding the number of terms out into a base-ten sum. This was frustrating. Especially because I knew there might be an easy answer looming out there that I wasn’t clever enough to see.

Second, I noted that 11 and 111 and 1111 are kind of weird numbers; written in base 10 they look pretty, but they don’t have much else in common. As we saw in the last post, a few are prime but many are not, and many have very strange prime factorizations — these factorizations do group together, but that seemed to be too far away from this problem to use. So, maybe another base would make them better formed? I plugged away in wolfram alpha. The first two bases I tried were base 2 and base 11. Neither one worked nicely. When I tried base 5, I found that the numbers followed an interesting pattern:

$1, 11, 111, 1111, 11111, 111111, \dots$

were mapped to

$1, 21, 421, 13421, 323421, 12023421, \dots$

Note that the last few digital always stay the same here. Because the decimal form of these numbers is 1 + 10 + 100 + 10000 + … this is not all that surprising. We’re essentially adding the base-5 versions of these together. Note that $400_{5}$ means the number 400 in base 5; in decimal this is the number 100. So $400_{5} = 100_{10}$ . We drop the $_{10}$ in our base 10 numbers and note the following:

$1 = 1_{5}$

$10 = 20_{5}$

$100 = 400_{5}$

$1000 = 13000_{5}$

$10000 = 310000_{5}$

$100000 = 11200000_{5}$

and while this seems to have a bit of a pattern, it grows too fast to be of use for adding. On the other hand, I found that base 5 can be fairly neat when you input numbers that have "nice forms" in base 10. Try it out!

Third, I was a bit upset, so I went back to thinking that I could write the number of terms as $n = a_{0} + a_{1}10 + a_{2}10^{2} + \dots + a_{k}10^{k}$ and some some mods to figure out the digits. The first digit will be easy: it’s just $a_{0}$ . But then what’s the carry? After a bit, I worked out that it will just be $\frac{n - a_{0}}{10}$ . This did not seem to be going anywhere, since this number might be somewhat large too; we would need to add this number $n - 1$ times, and then there’s another carry that will look significantly more complex than the one I just wrote. After trying this for five carries, I started to lose track of what I was doing; the formula was getting much more difficult than just doing "normal" addition. This clearly wasn’t going to go anywhere. At this point, a flash of insight hit me. Of course. This is just like adding 1 + 10 + 100 + 1000 + …, but only a little bit off. But how much off?

Fourth, I thought that, okay, 1 + 11 + 111 + 1111 +… is the same sum as 1 + 10 + 100 + 1000 + … with a difference of exactly 1 + 11 + 111 + … with one less term. If there are $n$ terms in the original, then it is equal to $1 + 10 + 100 + 1000 + \dots$ with $n$ terms plus $1 + 11 + 111 + \dots$ with $n -1$ terms. Note, then, that if we define the term $ONE_{k}$ to be the sum of $k$ terms that look like $1 + 11 + 111 + 1111\dots$ , then we have $ONE_{k} = 111\dots 111 + ONE_{k-1}$ . At this point, I began kicking myself, because this tells me nothing new about the problem; in fact, it is essentially a restatement of the problem! But because of this, I thought about what happens when we do addition in 10′s. I realized that it is exactly the same sort of thing we are doing when we add 11′s, but each successive digit will raise by 1. So for example, while

1 + 10 + 100 + 1000 + 10000 = 11111

we have

1 + 11 + 111 + 1111 + 11111 = 12345

Each digit, starting at the left, is one plus the one before it. Of course, this suggests a pattern. But then what happens when you get far enough along?

$1 + 11 + 111 + 11111 + \dots + 111111111111 = 123456790122$

which does not look as pretty. But look; if we add in the following way, this becomes easy! (I’ve attempted to use a chart to display place values.)

1	2	3	4	5	6	7	8	9
								1	0
									1	1
										1	2
+

Which is exactly what we got above! Note here that I’ve made a "10" that sits inside the tenth decimal place (and so is implicitly a carry of 1 in the ninth place) and a "11" that sits in the tenth place (and so is a carry of 1 in the tenth place and 1 in the eleventh place) and so on. I’ve found that this method of computing is slightly faster than computing the original sum by hand and much less space consuming. Unfortunately, the clever (and even not-so-clever) reader will notice that this is still the sum of $n - 8$ terms. Though I find it faster because you are only adding at most three things in each column (carries included). I tried to speed-test myself by adding together 20 terms this way and by doing 1 + 11 + 111 + … etc. straight out. My times are as follows:

Original Way (Adding 1 + 11 + 111…): 1 minute.

New Way (Described above): 40 seconds.

I also was much less confident doing this the original way (try it; you’ll have to keep track of the carry and the number of ones you need to add up and that gets confusing). The most time consuming part about the "new way" was writing out the problem; I did not count this in the "original way" because it’s just as easy to visualize the problem as it is to write it out — it would take significantly longer. If I were to only time the "calculation" part, the new way took me about 15 seconds. Pretty good for a human.

But, this solution was the best I could do. I do not have a closed form. If anyone has a different or more interesting solution, let me know. I didn’t want to resort to asking google, but maybe there’s a cute trick that makes this into a nice closed form. I’m not sure.

Edit: Of course, there is an easier solution which was provided to me by Josh "The Widowmaker" Silverman over at his blog. The key was to represent this as a geometric series (something that I seem to have completely missed out on). It turns out that the closed form expression is

$\frac{1}{81}(10^{n+1} - 10 - 9n)$

for the sum of the first $n$ numbers of this form. To see the derivation, go to his blog and read it over.

Posted by James

Filed in arithmetic, fun, number theory, tricks

1 Comment »

the dying love grape

Two Turtles Playing with a Hammer: A Game.

January 16, 2012

Baire Category Theorem.

January 5, 2012

Leading up to the Theorem.

The Theorem.

Why is it called the “Category” theorem?

Other Formulations of the BCT.

A Surprising Result.

BCT in Functional Analysis.

Teaching the Baire Category Theorem in an Intro Point-set Course: a mini-rant.

January 5, 2012

Uncountable Subset A of [0,1] with A – A empty.

December 20, 2011

11, 111, 1111, … Not a Square.

December 18, 2011

Urysohn’s Lemma for Metric Spaces.

November 20, 2011

Factorials and Exponentials.

November 6, 2011

Nested Kind of Topology.

October 16, 2011

Number of Elements in a Topology.

October 14, 2011

Summing 1 + 11 + 111 + … and My Problem Solving Technique.

September 17, 2011

Recent Posts

Categories

Meta

Archives

Blogroll

Follow “the dying love grape”