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)…
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 where the functions are continuous, and we can find bounds with and . By the Weierstrass -test, is continuous. Also, the strategy for nowhere differentiability is typical: We associate with each point a pair of sequences and with strictly decreasing to and strictly increasing to . The key lemma (shown, for example, in Johan Thim’s Master thesis available here) is that, if a continuous function is differentiable at , then we have
In the case of the Faber functions, the functions add `peaks’ in the neighborhood of any point, and the locations of these peaks can be used as the points and ; 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 or .
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.
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 and some continuous transformations . This provides us with a sequence of compact sets, where we set and . 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 , and satisfies , i.e., 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.
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 »
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:
To be explicit: You need to prove all the assertions in the paragraph above.
The new set follows.
Read the rest of this entry »
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 Problems and Theorems in Analysis. It is a work in two volumes. Series are studied in the first one.