My dad has more money than yours.
Saturday 2007 May 26
In this well known children’s game, both player name an integer, and the winner is the one who names the largest integer, or better still the one who utterly humiliates his opponent by naming a vastly larger integer. Integers must be named in a constructive way, say by writing down an explicit Turing machine which halts after a large number of steps (so for example values of the Busy Beaver function are not allowed, as this function cannot be defined constructively).
The problem is to find a good strategy for this game, in other words to give a (constructive) definition of a very large integer.
Any easy way to write down a large integer is to write down a rapidly growing function, and take some value of this function.
If the only functions we use are addition of 1, (or addition of some fixed constant), we get numbers like 1+1+1+1+1+1 or MMMCCXXXVIII.
If we allow addition and multiplication as operations we get numbers such as 18362528394746. This covers essentially all numbers needed in physics (unless one wants to know how long it will take for a large black hole to decay by Hawking radiation, or something like that). A common mistake made at this level is to write a long sequence of nines: since ones are thinner it is better to write a long sequence of ones.
The next step is to allow exponentiation. This allows one to write down numbers such as Skewes number
This covers almost all numbers used in mathematics.
Exponentiation is repeated multiplication, so it does not take much imagination to define an operation of repeated exponentiation, and so on. Repeating this idea gives the class of primitive recursive functions. These are roughly the functions that can be defined by starting with the successor function and allowing functions to be defined by recursion over the integers. A typical example of a number produced with such functions is Graham’s number, which seems to be the largest number that has turned up “naturally” in mathematics (rather than by someone deliberately trying to produce a large number).
The next step is functions such as Ackermann’s function, one of the simplest functions that is not primitive recursive. Primitive functions allow one to define functions by recursion over the first countable ordinal ω, but Ackermann’s function allows one to use recursion over the ordinal ω×ω=ω2. To define bigger functions, one can use larger (countable, constructive) ordinals. Some obvious ways of constructing these are ordinal addition, multiplication, and exponentiation.
The smallest ordinal one cannot form in this way is called ε0, the limit of
which is the ordinal measuring the strength of Peano arithmetic, in the sense that it is the smallest ordinal that Peano arithmetic cannot prove to be well ordered (Gentzen’s theorem). A reasonably natural function at this level, related to Ramsey’s theorem, was found by Paris and Harrington as part of the proof of the Paris-Harrington theorem .
More generally, for any theory extending Peano arithmetic there is a countable ordinal measuring its strength, defined as the smallest (constructive) ordinal that the theory cannot prove is well ordered. There are also some associated rapidly increasing functions, which one can in fact define directly from the theory without mentioning ordinals: take all computable functions fn that the theory can prove are well defined, and “diagonalize” over them. (More precisely, define a new function f(n) = 1+maxi,j≤n fi(j); this new function is increasing and eventually larger than any of the functions fn.)
This produces a function that is well defined (at least if the theory is ω-consistent) but that grows so fast that the theory cannot prove it is well defined.
Incidentally, this gives a proof of one version of Godel’s incompleteness theorem: the theory cannot prove that the function f is well defined, as it is larger than all functions it can prove are well defined, but the ω-consistency of the theory easily implies f is well defined, so the theory cannot prove its own ω-consistency.
So to find large functions we need strong theories. Beyond Peano arithmetic there is second order arithmetic, followed by various set theories, such as Zermelo-Fraenkel set theory. We can go further using the hierarchy of known large cardinal axioms, the largest of which is the axiom for Reinhardt cardinals. (These are so large that they are not consistent with the axiom of choice, so one has to use ZF (Zermelo Fraenkel set theory without the axiom of choice) rather than ZFC.)
So to summarize, we get a really large integer as follows: take Zermelo-Fraenkel set theory with a Reinhardt cardinal. List all computable functions that it can prove are well defined, and diagonalize over them. The value of this function at some reasonably large integer (say a trillion) will be larger than any (constructive) number written down by anyone without training in logic and set theory. It is necessary to take the value at quite a large integer because the function starts off growing quite slowly, since most functions that the theory proves are well defined are quite small.
There is one problem: it is not clear that this function is well defined, and there is no known way of proving that it is. This is inevitable: any function that one can see is well defined must be quite small.
(Added later): if one allows numbers that are just defined, rather than constructively defined,
one can do much better; for example, the busy beaver function at reasonably large values will exceed all the numbers mentioned above. It is easy to define very large numbers from powerful theories with a minor variation of the ideas above as follows: for each theory one can define a function f(n) to be the largest number that the theory can specify and prove is well defined in less than n symbols. For example, one could take the largest number that Zermelo-Frenkel theory with a Reinhardt cardinal can define and prove is well defined in at most a googolplex symbols.
Toroidal black holes?
Tuesday 2007 May 22
A well known theorem about black holes (due to Hawking?) states that their boundary must be a sphere, rather than a higher genus surface. For genus greater than 1 the proof seems fine, but the proof for genus 1 (a torus) seems incomplete :it rules them out physically as being unstable, but this seems to allow the possibility that they exist as unstable mathematical objects.
Consider a very thin torus of dust, rotating at just the right speed for the “centrifugal force” to balance the gravitational attraction. If the torus is thin enough this seems to produce a rotating toroidal black hole.
The obvious way to prove these exist is to write down an explicit formula for the metric, but this seems quite hard. There are many known exact solutions with the right symmetry, but they are mostly rather messy and it is hard to see what is going on (and in any case if they gave toroidal black holes the people who found them would probably have noticed).
The complement of a toroidal black hole is not simply connected, so by taking its universal cover one gets a chain of universes which one can travel between by going though the hole in the torus.
Linked and knotted black holes are left as an exercise for the reader.
Planck units (uselessness of).
Wednesday 2007 May 16
Planck units are determined by setting the speed of light c, Planck’s constant h, and the gravitational constant all equal to 1. The speed of light and Planck’s constant (give or take a factor of two pi) seem fundamental, but it is not clear why the gravitational constant G should be 1.
A minor problem is that it is probably missing a factor of 4π or maybe 8π as this is what appears in the Lagrangian. This is not serious but is a little worrying: no-one would suggest using 2c or c/2 as a fundamental unit of velocity, so an ambiguity of 2 is not a good sign for a supposedly fundamental unit.
A much more serious problem is that G appears as a non-renormalizable term in the Lagrangian of the standard model with gravitation; in fact, the only non-renormalizable term that has been measured to be non-zero. According to Wilson’s view of the renormalization group flow, this Lagrangian should be thought of as a low energy effective Lagrangian of some unknown theory. His theory predicts that there should be lots of non-zero non-renormalizable terms, which should all be extremely small. The constant G by a fluke happens to be detectable, because gravity just happens to be cumulative and is not masked by renormalizable interactions. So this suggests that G is just one of an infinite number of terms in the Lagrangian that could be used to determine a set of units.
Another problem is that according to Wilson’s theory all the coupling constants (presumably including G) change under the renormalization group flow so are not really constant. This suggests that there is nothing particularly significant about the Planck mass, or length, or energy, or whatever: all we know is that classical general relativity breaks down by Planck densities or lengths. By analogy, the Fermi constant for weak interactions could be used to produce a fundamental set of units, where the fundamental energy is about 300 GeV, but nothing special happens at this energy; it is just an order of magnitude estimate for the point where the old Fermi theory of the weak interaction breaks down (and for the masses of the vector bosons of the electroweak interaction).