Buzz l'éclair

"Vers l'infini et au-delà !"

As I am finally starting my maths blog, I thought it would be fitting for the first post to be on one of the first things that triggered my mathematical curiosity in my younger years: large numbers (and no, I will not be talking about the law of large numbers today, although it will eventually make an appearance on this blog with probability close to 1). More specifically, I want to try to give a somewhat satisfying answer to the following question: how large can numbers get? The following discussion will be mostly elementary and not rely on mathematical concepts beyond the high school level, I therefore hope this will be accessible to most curious (and mathematically-inclined) readers!

1. The Harmonic Series

There are many ways one might be led to think about concepts like infinity and large numbers. For me, one of the most striking such way is the divergence of the Harmonic Series, to which I was introduced as a first-year classe prépa student. Let’s first explain what the Harmonic Series is: consider the (infinite) sequence of inverses of natural numbers, i.e. $1, 1/2, 1/3, 1/4,\ldots$ and so on. Note that these values are decreasing and get closer and closer to zero as we keep going further in the sequence (for instance $1/10 = 0.1 \ge 1/100 = 0.01 \ge 1/10000= 0.0001$ and so on…). Now let $N$ be a large natural number (say, $N= 9999999$ if you like), and denote the partial sum of the Harmonic Series as follows:

\[H_N\equiv \sum_{n=1}^N \frac1n := 1 + \frac12 + \frac 13 + \cdots + \frac1N, \tag1\]

the left-hand side of $(1)$ is a conveniently shorter notation for its right-hand side.

So the partial sum of the Harmonic Series is just the sum of the $N$ first inverse natural numbers. Now, what we call the Harmonic Series is the limit of the sum $(1)$ above, as we let $N$ increase to infinity. That is, it is the sum of all the inverse natural numbers. Mathematically, we denote it as follows:

\[\lim_{N\to\infty} \sum_{n=1}^N \frac1n \equiv\sum_{n=1}^\infty \frac1n \equiv 1 + \frac12 + \frac 13 + \frac 14 \cdots. \tag2\]

Now, what is quite remarkable about the above quantity, is that although it is a sum of tiny numbers which are getting closer and closer to $0$, the sum value is actually infinite. That is, for any number $M$ you can imagine, you can always find a number $N$ of terms such that $H_N$ is larger than your $M$ of choice. This is what we mean when we say that the Harmonic series diverges. This was an absolute shock to me upon learning this for the first time, “how could tiny numbers possibly add up to any arbitrarily large quantity?” was my reaction. Perhaps you don’t find this particularly shocking, since we’re adding up an infinite number of terms after all, but to convince you that it is not such an obvious fact, consider the sequence of inverse powers of two, i.e. $1/2, 1/4, 1/8, 1/16, 1/32 \ldots$ and so on. Now consider the associated geometric series:

\[S := \sum_{n=1}^\infty \frac{1}{2^n} = \frac12 + \frac 14 + \frac18+ \frac{1}{16} + \cdots.\]

Here again, the sequence of inverse powers of two is monotonically decreasing towards zero, and although we’re adding infinitely many terms, we can show that the sum $S$ does not get arbitrarily large as we keep adding more and more terms (in fact, we can show that the sum gets closer and closer to $1$ as we keep adding terms, see this Wikipedia page for details).

So then, how do we make sense of the divergence of the Harmonic Series, and how can we even see that the series diverges? There is actually quite a number of ways one can prove that the series diverges, but a standard proof which achieves both aims at once is obtained by noting that the function $x\mapsto 1/x$ is monotone decreasing on the interval $[1,\infty)$, which gives the lower bound (see here for details)

\[H_N \ge \int_1^{N+1} \frac{dx}{x} \ge \log N, \tag3\]

where $\log$ denotes the natural logarithm. Hence from Equation $(3)$ we can see that $H_N$ grows like the logarithm of $N$, which indeed grows unboundedly with $N$. Better yet, by the same argument used to obtain $(3)$, we can show that $H_N \le \log N + 1$. So now, we know that the Harmonic series diverges, and it does so at a logarithmic speed. We can thus answer the question: for a given number $M$, how many terms $N$ do we need in the sum $H_N$ for it to be larger than $M$? Well, since we’ve shown that $H_N \approx \log N$, it follows that we can take $N$ such that $ \log N \ge M$ to reach our desired target $M$, which after applying the exponential, tells us that roughly $N\approx \exp(M)$ terms are enough to get $H_N \ge M$.

2. From a slowly diverging series to astronomically large numbers

Now that we have some quantitative understanding of why and how the harmonic series diverges to infinity, we can make sense out of why the statement the harmonic series diverges may seem so counter-intuitive (to my younger self, at least).

Mining some “harmonic bitcoin”

Let’s do a thought experiment. Imagine we’re mining a virtual currency, akin to bitcoin, which works as follows: for every unit of computational resource we use, we are able to compute an additional term of the harmonic series, and we get paid in (Hong Kong) dollars the total sum we have been able to compute. In words, if we have $N=10$ units of computational resources, we can compute the harmonic series up to $1 + 1/2 + \ldots + 1/10 $, and we thus get paid $1 + 1/2 + \ldots + 1/10 \approx 3$ HK\$ for this computational work. Now, how much computational resources would we need to earn 200HK\$ this way? Well, as we’ve seen in the previous section, it takes roughly $N\approx\exp(200)$ terms for the first $N$ terms of the harmonic series to be larger than $200$. So we would need approximately $N = 7\times 10^{86}$ (that’s a seven with 86 zeroes after it) units of computational resources to earn 200 dollars! For the record, experts estimate that the number of atoms in the observable universe is around $10^{80}$. Said differently, this means that even if we could magically turn every single atom of the universe into a computational unit solely dedicated to our harmonic bitcoin mining objective, we would still need about a million copies of the universe to earn 200 dollars!

Saving up on a mortgage

Another amusing thought experiment which conveys the same idea is the following: we start a timer at time $T_0=0s$, and every second after that, an amount of $1/j$ HK\$ is deposited to our bank account by a (kind, wealthy, and immortal) stranger, where $j$ is the current second. Said differently, at time $T=1s$, we receive 1\$, at time $T=2s$, we receive 1/2\$, and so on, such that after $N$ seconds, our bank account has received $H_N \approx \log N$ HK\$. How long do we need to wait to have received 10\$, 20\$, or 50\$? Running the same computations as before, we find that it would take respectively $2.2\times 10^4s\approx$ 6 hours to earn 10\$, $4.8\times 10^8s\approx$ 15 years to earn 20\$, and $5.2\times 10^{21}s\approx 1.6 \times 10^{14}$ years to earn 50\$. For the record, this last one is about ten thousand times greater than the age of the universe. So yeah, safe to say we’re not buying a house anytime soon.

Ubiquity of large numbers

Thought experiments like the two above (and many more variants) explain why the divergence of the harmonic series feels like such a counterintuitive fact: the series diverges so slowly that we have no way, within the space and time scales of our universe, to “witness” it reaching those arbitrarily large values. To us, this divergence to infinity, while true in theory, is not physically observable. Slowly (or, viewed conversely, rapidly growing) quantities, such as $\log$ and $\exp$, which lead to the consideration of these incomprehensibly large numbers are however far from being mere curiosities or thought experiments. Indeed, such objects arise naturally to answer deep and important questions in a lot of mathematical subfields. Here are a few examples that I like:

  • The partial sum of reciprocals of prime numbers $\sum_{p \le x, p\text{ prime}} \frac1p $ is known to grow at a rate of $\log\log x$. That is a logarithmic order of magnitude slower than $\log$.
  • The function $x\mapsto\log\log x$ famously appears in the law of the iterated logarithm which quantifies the fluctuations of a scaled random walk.
  • The Moment Generating Function of a Poisson random variable with parameter $\lambda > 0$ is given by the function $f:t\mapsto e^{\lambda(\exp(t) - 1)}$. That is a double exponential growth rate.

These examples do not even remotely scratch the surface of the world fast/slowly growing functions with which researchers in combinatorial graph theory, computability theory and various aspects of theoretical computer science work with daily.

3. So… do large numbers really mean anything?

It appears that we have found ourselves in some kind of paradox: on the one hand, quantities like $\exp\exp(100)$, TREE(3) or Graham’s number are so ridiculously large that there is no realistic way to comprehend them or to make any kind of physical sense out of them, on the other hand the mathematical functions giving rise to such quantities seemingly appear in a number of problems (distribution of primes, deviations of stochastic processes, expected times for rare events, complexity of algorithms, rates of convergence…) and help us understand our world. How do we make sense of this?

One option is to simply reject the very existence of those astronomically large numbers, which are out of reach of our computational abilities. This philosophical stance can be seen as some form of ultrafinitism: reject whatever is not computable from our mathematical system. This means rejecting the infinite set $\mathbb N$ of natural numbers as our foundational number system. Although legitimate and understandable in light of our earlier considerations, this approach comes with the extremely delicate issue;which I do not claim to understand—of having to rebuild from scratch the underlying axioms and set theory of mathematics. This opens up a lot of technical questions, and questions the validity of certain theorems we normally take for granted (akin to how rejecting the axiom of choice has a number of disturbing consequences, though accepting it also does one might argue).

Ray Solomonoff

Ray Solomonoff (1926 - 2009), father of algorithmic information theory. The Solomonoff induction principle, which reshaped our understanding of computation, automation, and knowledge, is named after him.

I will not attempt to take a stance on this delicate philosophical matter (on which my understanding is way too shallow anyway), but rather propose another way to resolve this uncomfortable dilemma, which encompasses the same idea but does not require rebuilding the whole foundations of mathematics. The idea is simply to assume that there exists a probability distribution $P$ on the set $\mathbb N_0$ of natural numbers ${0,1,2,\ldots}$, which to each natural number $n\in \mathbb N$ assigns a probability $P(n) := p_n$, which morally represents the likelihood that a person encounters said number at any point in their life (be it when paying bills, counting the number of clouds in the sky, writing down a phone number, reading the temperatures of the weather forecast…). Surely, such a probability distribution will vary (a lot) from person to person, and through location and time, but the point is to assume that such a probability distribution exists (which of course is nothing but a useful model).

If we are willing to accept this model of reality, then, $P$ being a probability distribution, it has to satisfy the following two properties:

  • $P(n)\ge 0$ for all $n\in \mathbb N_0$, and
  • $\sum_{n\in\mathbb N_0} P(n) = 1 $.

The first bullet point just says that any number must have a probability greater or equal to zero of being observed (but the probability can not be negative), while the second and most crucial point tells us that the sum of the probabilities assigned to each number must be equal to one. That is to say, if we observe any number sampled from this probability distribution, it has to be an element of the set ${0, 1, 2, \ldots}$. From these two bullet points (in fact, just the second bullet point), we can show that the following is true:

\[\lim_{n\to\infty} P(n) = 0,\]

that is to say, larger and larger numbers have probabilities converging to zero. Said in other words, if we accept this “probability distribution model”, then the incomprehensibly huge numbers such as $2^{10^{10}}$, $A(5,5)$, $\Sigma(8)$ and the likes are still allowed to exist, but become statistically insignificant, which matches our idea that those numbers are anomalies outside the realm of “physical reality”.

This probabilistic viewpoint on reality is naturally related (and in fact, inspired by) the Solomonoff induction principle and Occam’s razor. Morally speaking, the idea of these theories is to assign to (scientific) theories $T$ which explain some given observations a probability proportional to $2^{-L(T)}$, where $L(T)$ is the “length” of the theory $T$ (measured, e.g., in bits). This naturally gives higher credence to simpler theories, by virtue of Bayes’ rule, and corresponds to the Occam’s razor principle: “of two competing theories, the simpler explanation of an entity is to be preferred.”. Here in our example with large numbers, we likewise give decreasing probabilities to numbers as their size increases. This gives a simple way to statistically reject gargantuan numbers while keeping the foundations of mathematics untouched.

So, how large do numbers get? Well, not too large, probably.

References and further reading/watching

Articles and books
  • Kifowit, Steven J., and Terra A. Stamps. “The Harmonic Series Diverges Again and Again.” AMATYC Review 27.2 (2006): 31–43.
  • Kifowit, Steven J. “More proofs of divergence of the harmonic series.” Unpublished article available at http://skifowit.prairiestate.edu (2006).
  • Adelman, Omer. “Σ∞: A Micro-Lesson on Probability and Symmetry.” The American Mathematical Monthly 114.9 (2007): 809–810.
  • Lê Nguyên Hoang, El Mahdi EL, et al. La formule du savoir: Une philosophie unifiée du savoir fondée sur le théorème de Bayes. EDP Sciences, 2018. (In French)
Videos (In French)
Blog post