414/514 – Partitions

I while ago I posted a short note on integer partitions and generating functions. I am adding a link here, as it is obviously connected to the combinatorial applications of power series we have been considering.

There are some excellent books on the topic of generating functions. The classic, generatingfunctionology, can be downloaded for free at the website of the author, Herbert Wilf.

Another nice reference is Analytic combinatorics, by Philippe Flajolet and Robert Sedgewick. It can be downloaded for free at Flajolet’s website.

Finally, a classic in analysis that in particular covers this material nicely is the book by Pólya and Problems and Theorems in Analysis. It is a work in two volumes. Series are studied in the first one.

414/514 – Limit points

The argument in today’s lecture depended at the end on the following fact:

Suppose that is an uncountable subset of Then admits a limit point. In fact, if , then admits a limit point with

The proof should be standard by now but, for completeness, here is one way of seeing this:

Before we begin, recall that we already know that a bounded infinite set has a limit point. So, either is unbounded, or else it has a limit point. But even if we know that , so it certainly is bounded, we are not quite done yet because the limit point could be or

Recall as well that the countable union of countable sets is countable.

First, we may assume is bounded. This is because

,

so for some we must have is uncountable so, even if is unbounded, we can replace it with the uncountable bounded set

Let or, if we are given that to begin with, let So we can assume . Write so we do not have to distinguish between both cases. For , let

Then , and it follows that for some we must have is uncountable.

Now, we know that any infinite bounded subset of the reals has a limit point, so has a limit point. This point in absolute value has size at most , but this is what we needed.

In fact, one can extend this argument to see that any uncountable set has an uncountable set of limit points, but we did not need this for today’s argument.

Added: You may find interesting this recent question in MathOverflow.

414/514 – Multiplying power series

In lecture today we argued that under reasonable circumstances, the product of two power series is the series given by their “formal” product. I think I unnecessarily made the argument more complicated than it is, so I am writing it here so we have a clean reference.

Let and . Suppose that both and converge absolutely and uniformly in the interval . We want to prove that for , we also have

and this latter series converges absolutely and uniformly in .

To see this, let and denote the partial sums of and , and denote by the partial sums of the “formal product” series.

We want to show that

Let us call the “remainder” or “tail” series of , i.e.,

We have that Expanding this last expression, we find that it equals

Now, clearly converges to as , and the convergence is uniform in the interval

We want to show that the remaining term converges to 0 and does so uniformly in the interval

First, since uniformly as , then for any there is an such that if then for all .  If , we can split the sum above as , where

and

Note that , where is the constant This shows that uniformly for

To bound , note that it is a sum of a constant number of terms, namely . The functions are continuous and bounded in the interval , so there is a constant that bounds all of them (and, of course, does not depend on ). Hence

Since converges, there is an such that if , then

Pick so that . Then . We have now shown that uniformly for , and this completes the proof.

(We also claimed that the convergence is absolute. To see this, replace all the terms above by their absolute values. The same argument shows convergence of the relevant series, so we indeed have absolute convergence.)

414/514 – Continuity

This is homework 4, due Monday, October 31, at the beginning of lecture.

Suppose that and that . We write

iff for all there is a such that whenever then . In this case, we say that converges to as approaches from the left.

Similarly, we define convergence from the right:

iff for all there is a such that whenever then . In this case, we say that converges to as approaches from the right.

In terms of these notions, we see that exists iff both and exist, and are equal, in which case equals their common value.

The function is said to have a jump discontinuity (or a type I discontinuity, or a simple discontinuity, or a discontinuity of the first kind) at , iff both and exist, but either they are not equal, or they are equal to each other, but not to . Sometimes the notation is used for , provided that it exists and,  similarly, is used to denote , if it exists.

If is discontinuous at , but not through a jump discontinuity, we say that has a type II discontinuity (or a discontinuity of the second kind) at .

Recall that is monotone iff it is either monotonically increasing or monotonically decreasing. The first alternative means that whenever . The second means that whenever .

187 – Mathematics – Stack Exchange

I have mentioned a few times the website http://math.stackexchange.com/ and suggested that you take a look at it and use it as a resource. I believe it is a really useful site when used appropriately. Some of you have asked for additional references, and I think this site may help supply some of them.

Here is a short list of questions posted on the site that may give you an idea of its value:

• Proof by strong induction.
• Proof by induction for inequality.
• Proving a theorem in classical propositional logic.
• Understanding proof by contradiction.

414/514 – Continuous nowhere differentiable functions

There are many excellent sources on the topic of continuous nowhere differentiable functions. Johan Thim’s Master thesis, written under the supervision of  Lech Maligranda, is available online, here, but feel free to use any other sources you find relevant.

As a final project for the course, please choose an example of a continuous nowhere differentiable function, either from Thim’s thesis or elsewhere, and write a note on who it is due to and what the function is, together with complete proofs of continuity and nowhere differentiability. Feel free to add additional information you consider relevant for context.

Contact me (by email) as soon as you have chosen the example you will work on, to avoid repetitions; I will add your name and the chosen example to the list below as I hear from you.

Please take this project very seriously (in particular, do not copy details from books or papers, I want to see your own version of the details as you work through the arguments). Feel free to ask for feedback as you work on it; in fact, asking for feedback is a good idea. Do not wait until the last minute. At the end, it would be nice to make at least some of the notes available online, please let me know when you turn it in whether you grant me permission to host your note on this blog.

The project is due Wednesday, December 14, by noon, but feel free (and encouraged) to turn it in earlier.

List of projects:

• Diana Kruse: Bolzano function.
• Jesse Tillotson: Weierstrass function.
• Erron Kearns: Katsuura function.
• David Sanchez: Peano function.
• Shehzad Ahmed: Faber functions.
• Chip Roth: McCarthy function.
• Jeremy Ryder: Schoenberg functions.

187 – Presentation

Kevin Byrne will give a short presentation on Wednesday, October 26, on Alan Turing and Turing machines. Here is a link to the official page of the Alan Turing Year.

596 – Continued fractions

This term, Summer Hansen is taking a reading course with me on Pell’s equation. Our basic reference is:

• Jacobson and Williams, Solving the Pell equation. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2009. xx+495 pp. ISBN: 978-0-387-84922-5.

We are allowing a rather organic approach to the material, taking as many detours as it seems appropriate. The topic of continued fractions naturally came up. What follows is just a short compendium of results I found interesting while reading on the subject.

187 – Arguing by contradiction

[Edit: I have extended the deadline until the day of the final exam.]

Here are some extra credit problems. They are due at the latest by November 1, the day of the second midterm (just turn them in when you come to take the test), but you can of course turn them earlier. You can turn in as many as you want, this is completely voluntary.

All these problems can be solved arguing by contradiction. They tend to require at least one additional idea. The problems come for Loren C. Larson’s book “Problem-solving through problems.”

1. In a party with 2000 people, among any set of four there is at least one person who knows each of the other three. There are three people who are not mutually acquainted with each other. Prove that the other 1997 people know everyone at the party. (Assume that whenever a person knows a person , then also knows .)
2.  Prove that there are no positive integers , , , and such that .
3. Every pair of communities in a country are linked directly by exactly one mode of transportation: bus, train, or airplane. All three modes of transportation are used in the country; no community is served by all three modes, and no three communities are linked pairwise by the same mode. For example, four communities can be linked according to these stipulations in the following way: bus, , , , ; train, ; airplane, .
   1. Give an argument to show that no community can have a single mode of transportation leading to each of three different communities.
   2. Give a proof to show that five communities cannot be linked in the required manner.
4. Let be a set of rational numbers with the property that whenever and are (not necessarily distinct) elements of , then also and . Moreover, suppose that for any rational number , exactly one of the following is true: , , .
   1. Prove that 0 does not belong to .
   2. Prove that all positive integers belong to .
   3. Prove that is the set of all positive rational numbers.

414/514 – Compactness

Here are some extra credit problems dealing with the notion of compactness. The deadline to turn them in is Wednesday, December 14, at noon. I will not post hints for now, but feel free to stop by my office as you work on the problems, if you want to double check how your approach is going, and we may discuss suggestions then. These results are proved in different sources, try not to look these solutions up.

• (Vitali’s covering lemma)

Suppose that is a metric space and is compact. Let be an open covering of . Show that there is a finite set such that the balls for are pairwise disjoint, and

If , can the constant be improved? (I.e., can it be replaced by a smaller number?) If so, can you find the optimal constant?

The Vitali covering lemma has nice consequences. For example, it allows us to prove Lebesgue’s differentiation theorem.

• (Antisocial coverings)

This is a result of Krantz and Parsons. Again, let be a metric space. A self-centered covering of a non-empty subset is a collection of open balls, with open ball centered at each point of . An antisocial family is a collection of balls with the property that if and are distinct balls in the collection, then and . Prove the following:

Suppose that is a self-centered covering of the compact set , and suppose that the function is continuous on . Then there is an antisocial family that covers .

Also, show that any such family must be finite. Can you find a “reasonable” assumption on the map , not as restrictive as continuity, but sufficient to ensure the result?

(By the way, the topic of covering theorems is very interesting. Let me know if you think you may want to explore this further.)