[FOM] 273:Sigma01/optimal/size

[Timothy Y. Chow]

Harvey Friedman <friedman at math.ohio-state.edu> wrote:
> Graham's number is upper bounded by the value of the 4th (I may be off 
> by 1) function in the Ackermann hierarchy at a fairly small argument.

I don't think this is correct.  I think Graham's number is something like 
A_(A_(A_(...A_4(3)...)(3))(3))(3), with 64 levels of subscripting.

> Of course, Graham's number has some special mathematical significance of 
> a different kind than my numbers. So Graham's number of course REMAINS 
> quite important, despite its PUNY size.

Graham's number doesn't have any direct relation to proof-theoretic 
issues, but in one sense it is similar to the numbers in your "long finite 
sequences" paper, in that it is a *bound* for an innocuous-looking 
combinatorial problem.  In fact, it is an *upper* bound for a certain 
Euclidean-type Ramsey number whose true value is conjectured by some 
people to be 6.  So its intrinsic significance is doubtful; it's really 
just a measure of how inadequate our proof techniques are for such a 
problem.

The problem in question, by the way, is to take a hypercube in R^n, join 
every pair of vertices with an edge, and two-color the edges so as to 
avoid a monochromatic *planar* K_4.  Graham's number is bound on the 
critical dimension n.

Tim