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.

Read the rest of this entry »

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+),


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

    for all x<y.

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

The new set follows.

Read the rest of this entry »

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.

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 \mbox{Szeg\H o}, Problems and Theorems in Analysis. It is a work in two volumes. Series are studied in the first one.