Number of Elements in a Topology.

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

 

Question: Given , can we construct a topology such that has exactly 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 we can simply take and to be our sets, but for we need to be a bit more clever.  But not much more.  Consider:

 

This is a topology on with exactly 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 , there are two open sets in the particular point topology (empty set and the whole set).

If our universe is , then we have three open sets in the particular point topology.

If our universe is , then we have five open sets in the particular point topology.

If our universe is , then we have nine open sets in the particular point topology.

If our universe is , then we have seventeen open sets in the particular point topology.

 

If we exclude the empty set, it seems like we will have 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?

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

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:

were mapped to

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 means the number 400 in base 5; in decimal this is the number 100.  So .  We drop the in our base 10 numbers and note the following:

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 and some some mods to figure out the digits.  The first digit will be easy: it’s just .  But then what’s the carry?  After a bit, I worked out that it will just be .  This did not seem to be going anywhere, since this number might be somewhat large too; we would need to add this number 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 terms in the original, then it is equal to with terms plus with terms.  Note, then, that if we define the term to be the sum of terms that look like , then we have .  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? 

 

 

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
+

1

2

3

4

5

6

7

9

0

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

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

An Elementary Continued Fractions Problem.

To celebrate the 15k people who have, for whatever reason, happened upon this blog, I thought I’d post about something kind of fun.  I was going through some of my older books to try to see what I could give away, and I happened upon the sequence

 

 

which should look familiar to you.  Something kind of fun and mean to do is to tell someone who doesn’t know much math to evaluate this.  After they’ve had some time to get frustrated, you note that if we let

 

 

then then the original fraction is just .  Of course, this has an easy solution; , or which is known as the golden ratio.  Similar looking "regular" continued fractions can be computed similarly.

For ease of notation, I will say when I mean

 

 

which is standard notation.  Note the semi-colon.  This means the golden ratio is . 

It’s kind of neat to see what kinds of things you get with things of the form where I have purposely used here to hint that even complex values may be used.  Try out a few values.  Here’s a list of things to try:

 

1. Try to get a rational number.
2. Try to get a purely imaginary number.  Is it possible?
3. What kinds of numbers will give you rational numbers?  (There is actually a theorem about this!)
4. Can you ever obtain 0?  Why not?  Is it obvious from how we construct ?  It it obvious from the solution to the quadratic?
5. (Something I haven’t tried yet!) Do any complex numbers give you real numbers?  Do any complex numbers give you rational numbers?  (After reading below, is analytic?  What does it look like in the complex plane?)

 

The nice thing about this problem is that it is actually accessible for a student in high school who has seen the quadratic formula! 

A little edit below, WITH PICTURES!

Sequence which has countably many convergent subsequences.

This post is about a question I just thought about that I thought had a pretty neat solution.  The values we consider below are all in the Reals.

 

So, we’re all familiar with sequences which have subsequences which converge to two different values; for example, take which has a subsequence converging to 1 and a subsequence converging to -1.  Similarly, we can construct a sequence containing subsequences converging to three different values in a similar way; for example: .  Indeed, for any finite number, we can make a sequence containing subsequences converging to that number of different values.

 

The obvious next question is: can a sequence have subsequences which converge to a countable number of different values?  What about an uncountable number of different values?

 

For the former question, I thought of this solution.  First, enumerate your countable list of distinct values (think of the integers or the rationals, for example) as .  To construct the sequence, we do the following:

• Let .
• Let if is not some positive power of a prime (for example, if is 15, 21, 35, 100, etc.)
• For where is a positive power of a prime, we do the following: If for and is the -th prime (so , , , and so on) then set where is the -th element from your list above.

 

How does this actually work?  Let’s take a simple example.  Let’s let our countable set be the set of natural numbers.  This is easily ordered as and so, for this example, , , , and so forth.  Our sequence is now:

and if we kept going like this,

 

You kinda see the pattern going on here.  The 1 will appear infinitely many times, but the spaces between it grow exponentially.  Same for 2, 3, 4, and so on.  Thus, this sequence has the subsequence for any which obviously will converge to .

 

Do you have another neat way to do this?  Encoding this in the primes was my first thought, but you never know!

 

As for uncountable, my guess is no.  Of course, thinking of the sequence as a SET, we would get the reals from the rationals which is uncountable, but as a SEQUENCE it is not so trivial I feel.  I don’t want to spend too much time thinking about this (as analysis is calling me!) but I’m sure the proof isn’t too crazy.

 

Edit: Of course, a nice example exists where a sequence has subsequences converging to an uncountable number of distinct point.  In fact, two nice examples exist, and both were provided to me by Brooke (as usual!).

 

Uncountable Example 1:

It was a bit difficult for me to see the first one, but after doing a nice little thought experiment everything became much clearer.  Here it is:

Let be an enumeration of the rationals.  The claim is that there is actually a subsequence which converges to any real number.  Think about it for a minute.

Here’s a sketch for the proof.  Take your favorite real number.  Let’s start easy and just say we want a subsequence which converges to .  Let be the first element in our enumeration of the rationals above which is a distance less than 1 away from ; let’s say it’s .  Now let be the first element in our enumeration which is after and which is a distance less than away from . 

After that, you just keep picking the "next" element from the list that’s away from .  There must be one due to the density of the rationals in the reals (or, assume not and see what happens!).  We end up with as a subsequence of our enumeration of the rationals which converges to .  Obviously, replacing with any other real number works exactly the same.

 

Uncountable example 2:

This was one that Brooke presented to me that I liked quite a bit since it’s really easy to state.  Here’s the sequence (broken up by lines for clarity):

 

 

This converges to any real number in .  To see this is easy: decimal expand your chosen real number and pick the element "from each line" (as I’ve written it above) which is closest to it.  They’ll be at most away (for some suitable depending on the line you’re on) and thus a subsequence exists which converges to whatever element you picked.

Lim Sup: Life Lessons.

I’ve always felt a little uneasy with Lim Sup and Lim Inf’s.  Today while reading Rudin’s Complex book, I finally "got" it.

 

To find the lim sup of your sequence: take every convergent subsequence’s limit and find the sup of those limits.

 

This is, of course, exactly what the definition is, but it wasn’t "visual" to me until I thought about it this way.  Is there something you learned early on that you weren’t quite clear with until much, much later?

A Quick Note on Fatou’s Lemma.

Above is a sweet picture of this French mathematician Pierre Fatou.  Of course he had a nice mustache, but a few math things that are kind of neat about him: he was the first person to study the Mandelbrot set (though there is some controversy regarding the word "first" here…) and he also enjoyed iterative and recursive processes before they became really cool, making him a computer science hipster.  Also, he has a lemma in measure theory named after him.  That’s what this post is about.

 

Lemma (Fatou’s):  Let be a sequence of non-negative measurable functions on with the Lebesgue measure ,  and let for all .  Then, is measurable and we have the inequality

.

Nested Sequences of Measurable Sets.

On nearly every practice qualifying exam that I’ve been studying from, the following question (in some guise) comes up:

 

Question: Let be a sequence of Lebesgue measurable sets in .  Denote the Lebesgue measure by . 

1. If for every , then is it true that ?  If not, add a criteria to make it true.
2. If for every , then is it true that ? If not, add a criteria to make it true.

 

I’ll write up the solutions, since they are available elsewhere, but take a little bit of time to think about the second one if you haven’t.  I’ll put the remainder of the post under a cut so that I don’t spoil it right away. 

Jordan’s Lemma.

[This post is for those of you who are already comfy with doing some basic contour integrals in complex analysis.]

 

So you’re sitting around, evaluating contour integrals, and everything is fine.  Then something weird comes up.  You’re asked to evaluate an integral that looks like

for is continuous.  Eek.  Don’t panic though, because Camille Jordan’s gonna help you out.

 

Real Analysis Primer, Part 8: Lebesgue Integration.

Brief "Where are we going?" Motivation.

So far we’ve been talking about measure theory, which is nice to study just for the sake of measuring things, but when we talk about functions and measurements, we generally want to know the integral.  The Riemann integral was wonderful because of its simplicity in defining it: you have a big sheet of wavy paper (the total area under a function) and you keep slicing the pieces until they look like rectangles — once they look sufficiently close to a rectangle, just use length-times-width, and add up all the rectangles.  This is one interpretation of the Riemann integral, and, for the most part, it works wonderfully.  But there are many functions where it fails miserably.  This is where Lebesgue takes over.

So what’s different about Lebesgue?  While Riemann cuts apart the domain, Lebesgue says, "Okay, how large is the set of x-values that have the range value ?"  Specifically, we cut up the function into sets which have the same range value, then multiply that range value with the measure of the set. 

As an example, take the step function defined on, say, such that for and for and elsewhere.  The Lebesgue integral will say, "Where does take on the value 0?  Well, which has measure of 18.  Since the value is 0, we have , so this contributes nothing to the integral.  Where does take on the value 1?  On , which has a measure 1.  So this contributes to the integral.  Similarly, the function takes on a value 2 onn , this has measure 1, so this contributes to the integral.  No other values are taken on, so this integral is 0 + 1 + 2 = 3."

This extremely simple example shows the difference between Riemann and Lebesgue at the most fundamental level.  To do Riemann would be much easier in this case: it’s just adding up the rectangles.

 

There is a slight hitch at this point. Suppose we naively tried to apply what we’ve just said to a more complex function like defined, say, on .  We know (because this forms a triangle) that the area should be 2.  At every number between in the range, though, the function only takes on the value at a single point which has measure 0.  Thus, every one of these contributes 0 to the integral; and the sum of 0′s will be 0.  So the integral is 0?  That’s not right!

The problem here is that we must define the Lebesgue integral for functions which take on simple functions (which take on a countable number of values) and somehow approximate more general functions.  As we know, a function is measurable if and only if there is a sequence of simple functions which converge uniformly to it; and this will give us the means to integrate general (measurable) functions: we will take the integrals of each element of the sequence, and then define that limit to be the integral of the measurable function.  A number of questions will arise instantly, like, "Does this work?  Does this make sense?  Is this well-defined?", all of which can easily be put down with the elegant slashing of our proof-swords. 

So, let’s get down to it.

 

The Lebesgue Integral and Simple Functions.

We’ve already gone over simple functions (ones with a countable number of values, the pre-image of each of these being measurable making simple functions, themselves, measurable) so we might as well dive right in.  We will begin by defining, after long last, the Lebesgue Integral for these simple functions.  It will be defined exactly as we have motivated it above.

 

Definition.  Let be a measurable simple function on a (measurable) set taking the values .  Let be defined as the set of all such that ; that is, is the pre-image of .  Then we define

to be exactly the sum

provided that the sum converges absolutely (that is, the sum converges with replacing ).

We call this the Lebesgue integral of over the set .

 

Note that we have explicitly noted that must be measurable, though this is not specifically stated in the texts I am using.  I don’t feel I am losing much in assuming this (expect, perhaps, for more pathological examples such as being able to integrate some function which is non-zero only on a measurable subset of the non-measurable set).  Notice that we have also assumed that our sum must converge absolutely, and not just conditionally. 

[Note: At this point, it is not entirely clear to me why this should be necessary; in finite cases, we will generally not worry about it, but perhaps there is some reasoning as to why in infinite measured sets, we need this absolute qualification.  Feel free to weigh in here.]

It is reasonable to want to check the well-defined-ness of this, but I will not do this here since it is available where ever Lebesgue integrals are gone over.  I will also not define the integral of or for , because these should be relatively obvious.

 

TO BE CONTINUED.

Applying the Maximum Modulus Principle and Cauchy: A Common Question.

I’ve been a bit busy moving and packing my things, but I’ve tried to keep my problem-doing up to practice for my analysis qual.  One problem that seems to come up quite a bit in the complex analysis part of the exam is something like the following:

 

Question.  Suppose that is entire which satisfies for every and every .  Prove that is a polynomial of degree at most .