Things that shouldn’t work, but do

There are several mathematical heuristics (it’s difficult to call them proofs), which are non-rigorous in the best of cases and sometimes seemingly insane. For example, Euler’s ‘proof’ that the sum of the reciprocals of the primes diverges at an asymptotic rate of O(\log{\log{n}}) manipulates divergent series as though they were convergent, and does other dubious steps such as taking the logarithm of infinity.

He proceeded to conclude the rate of divergence of the series. It transpires that whilst the proof was non-rigorous, one can easily repair it, in this case by replacing the infinite summations with partial sums and taking the limit. It’s very messy, though, but still possible (I recall doing this for an earlier cp4space post).

Seven trees in one

Whilst the Euler proof cheats slightly, it may appear to the untrained eye to be completely legitimate. We’ll now take a look at a more extreme example, which appears more like a mathematical joke than a proof, but again reaches a correct conclusion. Later, a rigorous general proof was published, stating ‘whenever this silly approach is employed, and certain constraints are obeyed, the result of this process is a true statement’.

The subject is Andreas Blass’ Seven Trees in One, which I would probably rank among my favourite mathematical papers. Essentially, the heuristic argument runs like this:

  • Consider binary trees (with ordered leaves), and let each leaf be coloured with one of k colours. Here are a few examples of trees:

seventrees

  • There are C_{n-1} trees with n leaves, thus C_{n-1} k^n if we colour the leaves. Hence, the total number of trees with coloured leaves is given by the series k + k^2 + 2k^3 + 5k^4 + 14k^5 + ..., where the coefficients are Catalan numbers. This generating function has the closed form \dfrac{1-\sqrt{1-4k}}{2k}.
  • Evaluating this at k = 1 gives us the number of unlabelled trees, T = \dfrac{1-\sqrt{-3}}{2}. The astute observer will notice that this is a sixth root of unity, so T^7 = T.
  • Hence, there is an elegant bijection between trees and 7-tuples of trees.

Blass then provides such an elegant bijection in the paper. Here is a diagrammatic representation of the bijection, where the letters a, b, c, … represent arbitrary trees (including the ’empty tree’ consisting of a single leaf). To use this diagram, apply the first rule that applies to your 7-tuple.

bijection

Why does this work?

It is obvious that there were many non-sequiturs in the above derivation. Nevertheless, Blass provided a rigorous justification of this argument.

  • A tree is either a leaf or an ordered pair of trees (the children of the root node). Hence, it makes sense to write T = 1 + T² (where T is the set of trees, multiplication corresponds to Cartesian product, ‘+’ gives the disjoint union of two sets, and ‘=’ means ‘there exists a natural bijection’).
  • Now, if we were in a ring, we could rearrange to give T^2 - T + 1 = 0 and multiply by T^5 + T^4 - T^2 - T to give the desired equality, T^7 = T. However, this argument would also give clearly erroneous statements such as T^6 = 1. The reason this fails is that we’re not in a ring, but a semiring (ring without negatives).
  • Nevertheless, in a semiring we can still apply the formula T = 1 + T² to ultimately derive the desired statement. Dan Piponi created a video, where a penny can bifurcate into two pennies in adjacent locations (corresponding to bijecting from the set of trees to the disjoint union of the singleton set and the set of ordered pairs of trees). The reverse process can also happen (since bijections are, by their very nature, invertible):

If we replace each of these steps with the elementary bijection, the whole thing gives the bijection from trees to 7-tuples of trees.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Things that shouldn’t work, but do

  1. wojowu says:

    In pseudoproof of this bijection you probably forgot to put imaginary unit in value of T

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s