305 – A potpurri of groups

Here are a few examples of groups and links illustrating some of them. I will be adding to this list; if you find additional links that may be useful or interesting, please let me know. A nice general place to look at is the page for the book “Visual group theory.”

• , the symmetric and alternating groups in letters.
• Abelian groups, such as .
• Dihedral groups. Here is Erin Carmody‘s page illustrating the symmetries of the square. The Wikipedia page on dihedral groups has additional illustrations and interesting examples.
• Braid groups. Patrick Dehornoy has done extensive research on braid groups, and his page has many useful surveys and papers on the topic. Again, the Wikipedia page is a useful introduction. The applet we saw in class is here.
• Matrix groups. For example, , the group of all invertible matrices with real entries, or , the group of all matrices with real entries and determinant 1.
• The plane symmetry (or Wallpaper) groups.
• Coxeter groups.
• Crystallographic groups.
• Any group is (isomorphic to) a group of permutations, but the groups corresponding to permutation puzzles are naturally described this way. For example, Dana Ernst recently gave a talk on this topic.

305 – The Futurama theorem

Here is a link to Dana Ernst talk on the Futurama theorem of Ken Keeler. In this version, products are just as we treat them (left to right). Also, in this version, there is the “try it yourself” exercise we did not do, but you may want to practice a few examples on your own anyway to make sure you understand the argument.

Another discussion of the Futurama theorem, by Samuel Coskey (who will be joining our math department starting this Fall) can be found here.

Finally, the questions mentioned at the end of Ernst’s talk (see here) are all interesting, and if you figure one or several of them out, please turn them in for extra credit.

(By the way, the same applies to all problems we have been discussing. For example, if through the term you figure a way of producing a really long sequence giving us a better bound for than what you obtained when the homework was due, please turn it in as well.)

305 – Campanology

Campanology, or bell ringing, is an English tradition, where a round of cathedral bells is rung by permuting their order. The book discusses some examples of the possible patterns used in practice (the Plain Lead on four bells, and the Plain Bob Minimus). Additional examples can be found in the Wikipedia link, and links are provided there to a few additional sites, such as bellringing.org.

I strongly recommend that you read Section 3.5 in the book dealing with this topic. It introduces through an example the useful notion of cosets, and also it is quite interesting. For example, it shows how several ideas from group theory were used in practice since the seventeenth century, predating the introduction of the concepts by Galois and his contemporaries, and in a completely different setting.

I did not know about this until I read the book, and of course now I see mentions of bell-ringing everywhere.

The quote above, for example, is from the book Combinatorial Set Theory by Lorenz Halbeisen.

A nice article on the topic (in French) can be found here; coincidentally, the article also talks at the end about juggling. The video of the talk on the mathematics of juggling by Allen Knutson that we saw an excerpt of today is here. A few technical and expository articles on this topic, by renown mathematician (and juggler) Ronald Graham, and his coauthors, can be found in Graham’s page. See for example here, here, here, and here.

305 – Homework III

This homework set is due Wednesday, February 29th, at the beginning of lecture, but feel free to turn it in earlier if possible. Recall that “show” means “prove”.

305 – A lower bound for n(3)

This continues the previous post on Friedman’s theorem.

I want to give a brief idea of the size of Friedman’s , as defined on homework 2. The reference for what follows is

• Harvey Friedman, Long finite sequences,  J. Combin. Theory Ser. A, 95 (1) (2001), 102–144.

Recall that is the largest possible size of a sequence with property , all of whose terms are 1, 2, or 3. Here, to have property means that if , then the sequence is not a subsequence of the sequence .

In lecture we gave an example of such a sequence, of length 216, namely

where we use exponential notation to indicate the number of times a symbol appears consecutively, so the sequence begins

Actually, is much larger than 216. We know it is finite but, as Friedman mentions in his paper, it is an incomprehensibly large number. To explain this, we should mention the Ackermann hierarchy of functions. These are functions , with each a strictly increasing function.

Define . Also, set

,

where there are occurrences of .

This is perhaps best understood by computing a few examples. We have , , and, by an easy induction, .

Now, , , and, in general, is an exponential tower of 2s of height .

The descriptions become more complicated now. For example, is an exponential tower of 2s, but its height is itself an exponential tower of 2s (of height ). For example,

,

where the tower has height .

Let me now quote from Friedman’s paper:

I submit that is a ridiculously large number, but it is not an incomprehensibly large number. One can imagine a tower of 2’s of a large height, where that height is 65,536, and 65,536 is not ridiculously large.

However, if we go much further, then a profound level of incomprehensibility emerges. The definitions are not incomprehensible, but the largeness is incomprehensible. These higher levels of largeness blur, where one is unable to sense one level of largeness from another.

For instance, is an exponential tower of 2’s of height .

It seems safe to assert that, say, is incomprehensibly large. We propose this number as a sort of benchmark. In Section 4 we prove that , which is considerably larger.

Friedman actually goes much further than this. Using computer data provided by Randall Dougherty, Friedman proves in the last section of the paper that

.

For all I know, this could still be very far from the actual value of . And I do not know a reasonable description of an upper bound.

In technical terms, Friedman proves that the function is not primitive recursive, and actually grows much faster than the usual examples of recursive functions that are not primitive recursive. He also describes a function (a member of the so-called Hardy hierarchy) that grows faster than . This means that for all sufficiently large , but the argument does not give a specific bound when .

515 – Homework 2

This set is due Feb. 29 at the beginning of lecture. Let me know if more time is needed or anything like that. Problem 4 was incorrect as stated; I have fixed it now. Thanks to Tara Sheehan for bringing the problem to my attention.

515 – Plotting Féjer’s kernels

Féjer’s kernels are the functions that play the role of “approximations to the Dirac delta” in the computations we will use to obtain Weierstrass approximation theorem. The th approximation is given by

for , .

515 – The fundamental theorem of calculus

Suppose that and has an antiderivative . Then

305 – Friedman’s theorem

I am sketching here a proof of Harvey Friedman‘s result mentioned in lecture. The proof will not be needed for the rest of the course, but it is a nice argument that you may enjoy reading.

Recall that a sequence has property iff there are no integers such that the sequence is a subsequence of .

Here, we are using the notion of subsequence where terms must appear in order but are not required to be consecutive: A sequence is a subsequence of iff there are indices such that

Theorem (H. Friedman, 2001). For any positive integer there is a longest finite sequence in letters with property .

(Of course, once we know that the theorem is true, we can proceed as in lecture and define as the length of this longest sequence.)

414/514 – The triangle inequality

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