Thursday, July 2, 2015

Numbers that go on forever, and numbers that don’t

The number $\pi$ is not only the ratio of the circumference to the diameter in any circle, but it also pops up in probability, number theory, combinatorics and so on. For instance, look at the talk Why Pi?  by Don Knuth. By the way, around 11 minutes into the talk, Knuth gets nervous. Yes I was watching in the middle of the night, and laughing.

It seems though that what this number is most famous for is the fact that it never ends. It just goes on forever. Vi Hart can explain what this means. It’s not that it’s infinite, because it’s actually smaller than 4. But still...

We mathematicians are amazed. Not because pi has infinitely many digits, but because this seems to be such a big deal. Well, proving it is a big deal. But what it shows is that in this respect, pi is like most other numbers.

Pi is like a prince or princess of mathematics. It lives an absolutely weird life, yet what people seem to find most interesting about it is that it gets married, has children, and makes gingerbread at christmas.

By the way, pi is also wrong. Well, not wrong really. But it's wrong that this number should receive the status of being $\pi$, when the number $2\pi$, also known as $\tau$ (tau), is a much better candidate for the title of “circle constant”.

Anyway, it's more of a surprise when numbers turn out not to go on forever. A few years ago, I found out that if one chooses uniformly (that is, with equal probability for all possibilities) a spanning tree on 100 vertices and finds the maximum size matching (set of edges of which no two share a vertex), then the average number of edges is exactly 43.17816555453436639467528498753359880784701479940567711130128858955366138180570639880704988422109251181925421456900270651964884431350257469764694221172317371392058217163932358010086914490396623399.

Ok, this isn’t so surprising to someone who knows a bit about combinatorics and graph theory. According to a famous theorem of Cayley, the number of spanning trees in a complete graph on $n$ vertices is $n^{n-2}$. For $n=100$ this is $100^{98} = 10^{196}$. If we take an average of integers over this many possibilities, we get a rational number with $10^{196}$ in the denominator. Writing this number with decimals just means that we take the numerator and put a decimal point 196 steps from the end. The real surprise was that the numerator could be computed.

Now I have found another number that ends, and that does so for less obvious reasons. Suppose we take again a graph, but this time a complete bipartite graph on 10 by 10 vertices, and put independently a mean 1 exponential weight on each of the 100 edges. Then we look for the minimum total weight of a set of edges that covers all vertices, meaning that each vertex is incident to at least one of them. Then the expected value of the minimum weight is 1.4268901758375519. And there the number ends.

No comments:

Post a Comment