14
$\begingroup$

I have seen several questions here on MO regarding large numbers, (uparrow notation, etc.), and different way to construct and compare such numbers.

I am curious what the applications are for the study of such numbers, what is the motivation behind such constructs? There are plenty of constructs that produce large numbers, but the results seems to be of the form this quantity is finite, but large, which, surely, is mindboggeling and nice, but it does not reach outside the world of large numbers.

Are there any famous results that use these incredibly large numbers? In particularly, where the result itself is not just of the form this number is large.

I only know some places where such large numbers appear, (Ramsey theory and computability, such as the busy beaver function), but is this motivation enough for study of really large numbers in general?

Clearly, there cannot be many real-world applications, since these numbers vastly exceed the number of particles in the universe. They are so large that we cannot gasp how large they are, so using them in some application will be fruitless.

EDIT: I would really appreciate examples where the actual number (or big estimate) plays an essential role, not just finiteness of said numbers.

A hypothetical result I am looking for could be of the following form: $f,g$ are special functions defined on positive reals, such that $f(x)$ has its first zero for some $x$ satisfying $N_f < x $ and $g(x)$ has its first zero for some $x<N_g$. Some cool non-trivial result follows only if $g$ is zero before $f$, so this would be implied by proving $N_g < N_f$, where $N_f$ and $N_G$ are explicit, and very large bounds.

Thus, I am particularly interested in where working with large numbers is essential for the proof, but the result is not of the form "this number is really large". There are a lot of results of the form If we do this, then this certain number is really large, but theorems that involve explicit large numbers where the consequence other than this is finite, but very large, seems rare.

$\endgroup$
2
  • 1
    $\begingroup$ Are you primarily interested in applications of individual large numbers (such as the Skewes number, which by now is just an artifact, or Graham's number which has a curious provenance), or in fast-growing sequences? I'd think it is the latter that has greater theoretical significance. $\endgroup$
    – Todd Trimble
    Apr 10, 2014 at 13:17
  • $\begingroup$ In my opinion, the interesting part here is essentially the existence and finiteness of Grahams bound, not so much the size. If the proof in some sense relies on Grahams number in an essential way, then this is an application, but if there is a lot of extra effort to find a bound of the number, then it does not add so much extra value, I think. Similarly, the recent progress of the twin prime conjecture is not really about the size of the gap between primes, but its finiteness, even though the initial number was a quite large number (70 millions). $\endgroup$ Apr 10, 2014 at 14:15

2 Answers 2

10
$\begingroup$

For the conceptual picture that you seem to be looking for, you probably want to think in terms of fast-growing functions as the primary object of interest, and very large numbers as evaluations of these functions at specific values of interest. One major reason for the interest in fast-growing functions is that they provide a way to calibrate the logical strength of a system of axioms; the stronger the axioms, the more functions they can prove total.

In Ramsey theory, often the only known way to construct something is via some complicated iteration, and so fast-growing functions arise naturally as measuring the rate of growth of the iteration. Sometimes, one can prove a lower-bound result that shows that the objects in question really do have to grow very quickly, so the large numbers are not just being introduced to give a loose upper bound but are telling you how fast the objects really are growing. One example that Harvey Friedman likes to give is the following.

Block Subsequence Theorem. Let $k\ge 1$. Then there is a longest finite sequence $x_1, \ldots, x_n$ from $\{1,\ldots,k\}$ such that for no $i < j \le n/2$ is $x_i,\ldots,x_{2i}$ a subsequence of $x_j,\ldots,x_{2j}$.

For $k\ge1$, let $n(k)$ denote the length of this longest finite sequence. One can show without much difficulty that $n(1)=3$ and $n(2)=11$. It turns out that $n(3)>A(7198,158386)$, where $A$ is (a version of) the Ackermann function. Now I suppose you could argue that the specific value of $n(3)$ is of limited interest—it's just some big finite number—but the point is that the function used to express it isn't arbitrary; its appearance tells you something about the structure of the combinatorial object in question, and it's also a hint that a moderately strong induction axiom will be needed to prove the result.

$\endgroup$
5
$\begingroup$

The classical (in true historical sense) application is the sand reckoner and the cattle problem (it might be that Archimedes used problems with practically incalculable numbers to discover who among the mathematicians in Alexandria claimed as their own results that Archimedes sent to Alexandria without proof). These numbers were as big for the time as the numbers you cite are today. Note also that very rapidly increasing integer sequences are related to undecidability results, see the work of Harvey Friedmann and others https://u.osu.edu/friedman.8/files/2014/01/EnormousInt.12pt.6_1_00-23kmig3.pdf http://oeis.org/A014221 (Provocative side note: for what we known, it might be that the "separation" that we experiment between NP complete problems and P problems might due to the fact that P might be equal to NP but with polynomials with incredibly large degree and coefficients)

Edit: I agree with @Per Alexandersson that it would be better to give examples where the specific number (and not only its vague hugeness) matters. In fact we can say that "vague hugeness" examples are uninteresting precisely because the sand reckoner for the first time showed how easy it is, in principle, to give such examples (before that someone even doubted that big numbers can be specified, or even that the existing sand was finite in number; limit case: some primitive languages count "one, two, many").

In my opinion the cattle problem is a case where the specific number matters: [1] it asks the specific number; [2] it was not obvious (at the time, well before the Indian algorithm) that a solution exists at all (it is not a problem of "finite vs infinite"); [3] it is not obvious that if a solution exists it must be quite big. The function that associates to a squarefree $N$ the least natural $x$ such that $Nx^2$ has distance 1 from a square might have looked almost completely random at the time; it is not a isotone function (Vardi specifies smaller data that would give much bigger numbers) which in a way makes it even more interesting, despite its relative smallness (but not for its time), in comparison with the rapidly increasing sequences that also Timothy Chow and Todd Trimble consider logically interesting and with specific combinatorial meanings for the specific values.

As @Pietro Majer spotted, the parenthetical remark about Archimedes is only speculation (that I found on the net about a month ago, and that now I cannot trace back. The source did not give real substance to the claim, and so i did not bookmark the url). However, I cited that since in any case it is a plausible application of "too-big" numbers. After all, in the same way as Archimeds could have done with plagiarizing mathematicians ("specify the number please"), Pietro Majer invited me to sustantiate a probably unsustantiable claim.

The following might be a reasoning behind this speculation (for a amusing possibility, in the same way as I cite a possibility concerning P and NP).

From http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Archimedes.html

In the preface to On spirals Archimedes relates an amusing story regarding his friends in Alexandria. He tells us that he was in the habit of sending them statements of his latest theorems, but without giving proofs. Apparently some of the mathematicians there had claimed the results as their own so Archimedes says that on the last occasion when he sent them theorems he included two which were false:

... so that those who claim to discover everything, but produce no proofs of the same, may be confuted as having pretended to discover the impossible.

However, "false" is not the only translation: from pag. 20 in http://www.ifi.unicamp.br/~assis/Archimedes-2nd-edition.pdf

there are two included among them which are impossible of realisation [and which may serve as a warning] how those who claim to discover everything but produce no proofs of the same may be confuted as having actually pretended to discover the impossible.

A footnote by Heath on "impossible of realisation" notes a corruption of the Greek text and concludes

The meaning appears to be simply "wrong".

But if one takes "impossible of realisation" also the cattle problem (and not only false propositions) would fit.

However, this is not a proof, and even if it were a proof one can cite what a historian said to Kolmogorov

You have supplied one proof of your thesis, and in the mathematics that you study this would perhaps suffice, but we historians prefer to have at least ten proofs.

So you are justified in reacting to the speculation I cited with (the much more classicaly supposed last words) "Noli turbare circulos meos" (or their equivalent in vernacular contemporary italian, increasing by 1 the dimension).

$\endgroup$
2
  • $\begingroup$ Thank you! I am aware of all the sources you linked to, but they do not really satisfy me as much as I'd like (see my post edit). Surely, the numbers that appear are truly large, but the result in the end is just "this is a large number", If you asked a person in complex analysis what theory of analytic functions is good for, then she would not say "Oh, we use this to construct cool analytic functions", but rather "These particular analytic functions are used to show this other result in other area", which a priori do not really look like they need analytic functions. $\endgroup$ Apr 10, 2014 at 14:36
  • $\begingroup$ "it might be that Archimedes used problems with practically incalculable numbers to discover who(…)" Sounds interesting, could you elaborate on this? Is there any source that suggests that? $\endgroup$ Apr 11, 2014 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.