FOM: On twin primes and surreal numbers; reply to Forster

[Joe Shipman]

Forster:
>I am in the market for examples of
>fast-growing functions that the average 4th year
>mathmo might find soothingly familiar, and i
>started wondering about prime pairs.  Does anybody
>know whether there is a lower bound on the growth
>rate of the function that enumerates the lower
>members of prime pairs?  I take it it's still open
>that there are infinitely many?

The sum of the reciprocals of the twin primes converges.  It's still
open that there are infinitely many, but this gives you a lower bound.
In fact the frequency of twin primes is believed to be quadratic in
1/log(n), with good numerical evidence.  If you want something that
grows faster, try "odd-sided polygons constructible with straightedge
and compass"; it's not known if there are infinitely many (it is
believed there are only finitely many because it is believed there are
only finitely many Fermat primes of the form 1+2^n, and any
constructible odd-sided polygon is a product of distinct Fermat primes),
but if there are they grow at least double exponentially (since 1+2^n
can only be prime if n is itself a power of 2).

A better example of double exponential growth comes from Conway: the
finite ordinals which form a field under nim-addition and
nim-multiplication are those of the form 2^(2^n) for n=0,1,2,3,... (2,
4, 16, 256, 65536, etc., where each term is the square of the previous
one).

If you want natural sequences growing faster than that the best place to
look is Friedman's work.

Postscript for those who don't have "On Numbers and Games":

Nim-addition = adding base 2 without carrying; the Nim-product # of x
and y is most simply defined by the following rules:
  i) if x<y and y is 2^(2^n), x#y=xy
 ii) if y=2^(2^n), y#y=(3y/2)
iii) use associative and distributive laws to derive the rest

The infinite ordinals which are fields under the Nim operations are much
more interesting.  omega^(omega^omega) is the first algebraically closed
field under the Nim-operations (that is, the ordinal omega^(omega^omega)
is the first ordinal transcendental over the earlier ones); the next
transcendental is very large, and Conway leaves as an open question what
its relationship is to the first impredicative ordinal Gamma_0.

-- Joe Shipman