414/514 – The triangle inequality

February 3, 2012

On Google+, Willie Wong posted a link to this interesting example, by Brian Gawalt: BART fares and the triangle inequality.

There is a natural way of measuring distance in a subway or train system, the “price between stations” metric. It turns out that when applied to BART, the  Bay Area Rapid Transit system, this fails to be a metric, with the consequence that sometimes it is cheaper to take a detour, exiting and reentering an intermediate station, than going directly to one’s destination. As Gawalt points out:

It’s probably important to recognize the 15 cents you save by jumping out costs about 15 to 20 minutes of your life waiting for the next train to come pick you up.

Willie adds an interesting comment, that I reproduce here:

Heh, while BART fails to be a metric space (with the price between stations metric), it is interesting to note that the single-fare systems form ultrametric spaces.

The British Rail / PostOffice metrics, of course, reflect systems with concentric zones in rings for which to get from one place to another almost certainly require passing through the centre. Like London Underground for example.

The public transport in Lausanne does not form a metric space using the price-between-stations metric for another (somewhat strange) reason: the price-between-stations function is set valued: the same two stations can have different prices depending on which route the bus/train takes, even without you getting off. (This is the problem with a zone based system. For certain places there are two more or less identical routes but one goes through two or three more zones than the other: some of the zones looks like they are slightly gerrymandered.) Of course, in this case most sensible people would just buy the cheapest available fare and take the cheapest available route, showing that a zone-based system is much more like a Riemannian manifold (and commuters try to travel in geodesics)…

414/514 – The Schoenberg functions

January 23, 2012

Here is Jeremy Ryder’s project from last term, on the Schoenberg functions. Here we have a space-filling continuous map $f:x\mapsto(\phi_s(x),\psi_s(x))$ whose coordinate functions $\phi_s$ and $\psi_s$ are nowhere differentiable.

The proof that $\phi_s,\psi_s$ are continuous uses the usual strategy, as the functions are given by a series to which Weierstrass $M$-test applies.

The proof that $f$ is space filling is nice and short. The original argument can be downloaded here. A nice graph of the first few stages of the infinite fractal-like process that leads to the graph of $f$ can be seen in page 49 of Thim’s master thesis.

414/514 – Faber functions

January 17, 2012

Here is Shehzad Ahmed’s project from last term, on the Faber functions, a family of examples of continuous nowhere differentiable functions. Ahmed’s project centers on one of them, but the argument can be easily adapted to all the functions in the family.

As usual, the function is given as a series $F=\sum_n f_n$ where the functions $f_n$ are continuous, and we can find bounds $M_n$ with $\|f_n\|\le M_n$ and $\sum_n M_n<+\infty$. By the Weierstrass $M$-test, $F$ is continuous. Also, the strategy for nowhere differentiability is typical: We associate with each point $x$ a pair of sequences $(a_n)_{n\ge0}$ and $(b_n)_{n\ge0}$ with $a_n$ strictly decreasing to $x$ and $b_n$ strictly increasing to $x$. The key lemma (shown, for example, in Johan Thim’s Master thesis available here) is that, if a continuous function $f$ is differentiable at $x$, then we have

$\displaystyle f'(x)=\lim_{n\to\infty}\frac{f(a_n)-f(b_n)}{a_n-b_n}.$

In the case of the Faber functions, the functions $f_n$ add `peaks’ in the neighborhood of any point, and the locations of these peaks can be used as the points $a_n$ and $b_n$; moreover, the slopes accumulate at these peaks, and so the limit on the right hand side of the displayed equation above does not converge and, in fact, diverges to $+\infty$ or $-\infty$.

Faber’s original paper, Einfaches Beispiel einer stetigen nirgends differentiierbaren Funktion, Jahresbericht der Deutschen Mathematiker-Vereinigung, (1892) 538-540, is nice to read as well. It is available through the wonderful GDZ, the Göttinger Digitalisierungszentrum.

414/514 – Katsuura function

January 17, 2012

Here is Erron Kearns’s project from last term, on the Katsuura function, an example of a continuous nowhere differentiable function.

The presentation is nice: As usual with these functions, this one is defined as the limit of an iterative process, but the presentation makes it very clear the function is a uniform limit of continuous (piecewise linear) functions, and also provides us with a clear strategy to establish nowhere differentiability.

Actually, the function is presented in a similar spirit to many fractal constructions, where we start with a compact set $K$ and some continuous transformations $T_1,\dots,T_n$. This provides us with a sequence of compact sets, where we set $K_0=K$ and $K_{m+1}=\bigcup_{i=1}^n T_i(K_m)$. Under reasonable conditions, there are several natural ways of making sense of the limit of this sequence, which is again a compact set, call it $C$, and satisfies $C=\bigcup_{i=1}^n T_i(C)$, i.e., $C$ is a fixed point of a natural “continuous” operation on compact sets.

This same idea is used here, to define the Katsuura function, and its fractal-like properties can then be seen as the reason why it is nowhere differentiable.

414/514 – Convexity

November 16, 2011

This is the last homework set of the term. It is optional. If you decide to turn it in, it is due Wednesday, December 14 at noon.

414/514 – Series

November 8, 2011

This is homework 5, due Friday November 18 at the beginning of lecture.

First of all, some of you did not realize that the first question in the previous homework set was indeed a question, and skipped it. If that was the case, please solve it now and turn it in. The sooner you do so, the sooner I’ll be able to grade it and return it with the rest of your homework 4. The question was as follows:

• Suppose that $f$ is monotonically increasing. Then $f(x-)$ and $f(x+)$ exist for all $x\in{\mathbb R}$. Moreover,

$f(x-)\le f(x)\le f(x+)$,

and

$f(x+)\le f(y-)$

for all $x.

To be explicit: You need to prove all the assertions in the paragraph above.

The new set follows.

414/514 – Partitions

October 31, 2011

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.

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

414/514 – Limit points

October 28, 2011

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

Suppose that $A$ is an uncountable subset of ${\mathbb R}.$ Then $A$ admits a limit point. In fact, if $A\subseteq(-r,r)$, then $A$ admits a limit point $x_0$ with ${}|x_0|

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 $A$ is unbounded, or else it has a limit point. But even if we know that $A\subseteq(-r,r)$, so it certainly is bounded, we are not quite done yet because the limit point could be $r$ or $-r.$

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

First, we may assume $A$ is bounded. This is because

$\displaystyle A=\bigcup_n A\cap(-n,n)$,

so for some $n$ we must have $A\cap(-n,n)$ is uncountable so, even if $A$ is unbounded, we can replace it with the uncountable bounded set $A\cap(-n,n).$

Let $I_0=(-n,n)$ or, if we are given that $A\subseteq(-r,r)$ to begin with, let $I_0=(-r,r).$ So we can assume $A\subseteq I_0$. Write $I_0=(-a,a)$ so we do not have to distinguish between both cases. For $n\ge1$, let

$\displaystyle I_n=\left(-a+\frac1n,a-\frac1n\right).$

Then $A=\bigcup_{n\ge1} A\cap I_n$, and it follows that for some $n\ge1$ we must have $A\cap I_n$ is uncountable.

Now, we know that any infinite bounded subset of the reals has a limit point, so $A\cap I_n$ has a limit point. This point in absolute value has size at most $\displaystyle a-\frac1n, 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

October 25, 2011

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 $\displaystyle A(x)=\sum_{j=0}^\infty a_j x^j$ and $\displaystyle B(x)=\sum_{j=0}^\infty b_j x^j$. Suppose that both $A$ and $B$ converge absolutely and uniformly in the interval ${}[-r,r]$. We want to prove that for $x\in[-r,r]$, we also have

$\displaystyle A(x)B(x)=\sum_{j=0}^\infty\left(\sum_{i=0}^j a_i b_{j-i}\right)x^j,$

and this latter series converges absolutely and uniformly in ${}[-r,r]$.

To see this, let $\displaystyle A_N(x)=\sum_{j=0}^N a_j x^j$ and $\displaystyle B_N(x)=\sum_{j=0}^N b_j x^j$ denote the partial sums of $A$ and $B$, and denote by $\displaystyle P_N(x)=\sum_{m=0}^N\left(\sum_{j+k=m}a_j b_k\right)x^m$ the partial sums of the “formal product” series.

We want to show that $\displaystyle\lim_{N\to\infty}P_N(x)=A(x)B(x).$

Let us call $R_N(x)$ the “remainder” or “tail” series of $B(x)$, i.e., $\displaystyle R_N(x)=B(x)-B_N(x)=\sum_{j=N+1}^\infty b_j x^j.$

We have that $P_N(x)=a_0B_N(x)+a_1xB_{N-1}(x)+\dots+a_N x^N B_0(x)$ $=a_0(B(x)-R_N(x))+a_1 x (B(x)-R_{N-1}(x))+\dots$ $+a_N x^N (B(x)-R_0(x)).$ Expanding this last expression, we find that it equals $B(x)\sum_{j=0}^Na_j x^j-[a_0R_N(x)+a_1 xR_{N-1}(x)+\dots$ $+a_N x^N R_0(x)].$

Now, $B(x)\sum_{j=0}^Na_j x^j=B(x)A_N(x)$ clearly converges to $B(x)A(x)$ as $N\to\infty$, and the convergence is uniform in the interval ${}[-r,r].$

We want to show that the remaining term $a_0R_N(x)+a_1 xR_{N-1}(x)+\dots+a_N x^N R_0(x)$ converges to 0 and does so uniformly in the interval ${}[-r,r].$

First, since $B_n(x)\to B(x)$ uniformly as $n\to\infty$, then for any $\epsilon>0$ there is an $N_0$ such that if $n\ge N_0$ then ${}|R_n(x)|<\epsilon$ for all $x\in[-r,r]$.  If $N>N_0$, we can split the sum above as $S_1(x)+S_2(x)$, where

$\displaystyle S_1(x)=a_0 R_N(x)+a_1 x R_{N-1}(x) + \dots + a_{N-N_0}x^{N-N_0} R_{N_0}(x)$

and

$\displaystyle S_2(x)=\sum_{j=N-N_0+1}^N a_j x^j R_{N-j}(x).$

Note that $|S_1(x)|\le\epsilon\sum_{j=0}^{N-N_0}|a_j x^j|\le K\epsilon$, where $K$ is the constant $\sum_j |a_j|r ^j.$ This shows that $S_1(x)\to0$ uniformly for $x\in{}[-r,r].$

To bound $S_2$, note that it is a sum of a constant number of terms, namely $N_0$. The functions $R_{N_0-1},R_{N_0-2},\dots,R_0$ are continuous and bounded in the interval ${}[-r,r]$, so there is a constant $L$ that bounds all of them (and, of course, $L$ does not depend on $N$). Hence

$\displaystyle |S_2(x)|\le L\sum_{j=N-N_0+1}^N |a_jx^j|\le L\sum_{j\ge N-N_0+1} |a_j|r^j.$

Since $\sum_j|a_j|r^j$ converges, there is an $N_1$ such that if $n\ge N_1$, then $\sum_{j\ge n}|a_j|r^j<\epsilon.$

Pick $N$ so that $N-N_0>N_1$. Then $|S_2(x)|. We have now shown that $|S_1(x)+S_2(x)|\to0$ uniformly for $x\in{}[-r,r]$, and this completes the proof.

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

414/514 – Continuity

October 24, 2011

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

Suppose that $f: {\mathbb R}\to{\mathbb R}$ and that $a\in{\mathbb R}$. We write

$\displaystyle \lim_{x\to a^-}f(x)=L$

iff for all $\epsilon>0$ there is a $\delta>0$ such that whenever $0 then $|f(x)-L|<\epsilon$. In this case, we say that $f$ converges to $L$ as $x$ approaches $a$ from the left.

Similarly, we define convergence from the right:

$\displaystyle \lim_{x\to a^+}f(x)=R$

iff for all $\epsilon>0$ there is a $\delta>0$ such that whenever $0 then $|f(x)-R|<\epsilon$. In this case, we say that $f$ converges to $R$ as $x$ approaches $a$ from the right.

In terms of these notions, we see that $\lim_{x\to a}f(x)$ exists iff both $\lim_{x\to a^-}f(x)$ and $\lim_{x\to a^+}f(x)$ exist, and are equal, in which case $\lim_{x\to a}f(x)$ equals their common value.

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

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

Recall that $f$ is monotone iff it is either monotonically increasing or monotonically decreasing. The first alternative means that $f(a)\le f(b)$ whenever $a\le b$. The second means that $f(a)\ge f(b)$ whenever $a\le b$.