Ronald Graham's other large number. Well---- it was large in 1964 anyway.
Computational Complexity 2019-08-20
Graham's number (see here) was at one time the largest number to appear in a math proof.
a) GN was an upper bound on a problem in Ramsey theory. There are now better upper bounds, see here. These better upper bounds are still large- Hales-Jewitt-Large, but that's already much smaller than the original GN.
b) Other proofs now have numbers even larger than GN. For example Harvey Friedman's work on the finite versions of Kruskal's Tree Theorem. (There may be other cases- if you know some then let me know in the comments.)
Since my dept recently moved buildings I found old papers that I had not looked at in years. One of them was
Old and New Problems and Results in Combinatorial Number Theory
by Erdos and Graham
(see here)
So I began reading it and came across a result of Graham from 1964 that used large numbers. No where near as large as GN, but I found it interesting that Graham was involved with large numbers way back then.
Here is the problem:
A Lucas Sequence is a sequence that obeys
a(n) = a(n-1) + a(n-2).
Clearly such a sequence is determined by a(0) and a(1).
QUESTION: Does there exists a(0) and a(1) that are rel prime such that the sequence has only composite numbers?
By ingenuity and some computing power Graham found YES. For how the got the numbers see here. The numbers are of course in the paper, and how they got them is interesting, but I present them anyway. Hope I don't make a typo:
a(0) = 1786772701928802632268715130455793
a(1) = 1059683225053915111058164141686995
The paper Old and New... says its open if there is a smaller pair of numbers, I do not know if it is still open. If you know, let us all know in the comments!
These numbers seem small today since we have modern computers that can store and manipulate them easily. Were the considered large numbers in 1964? They were never called Graham Numbers which is probably just as well since that honor lay ahead.