This site is supported by donations to The OEIS Foundation.

Frivolous theorem of arithmetic

From OeisWiki
Jump to: navigation, search

This article needs more work.

Please help by expanding it!

The frivolous theorem of arithmetic reminds us that there are infinitely many integers. Economists and astronomers deal with numbers that seem large to the lay person, but some number theorists and combinatorics experts deal with far larger numbers.

Theorem. (Steinbach)

Almost all [nonnegative] integers are very, very, very large.[1]

Proof. This is really more of a thought experiment than a rigorous, formal proof, but it has been independently thought of by a few different people and presented as a proof. For the purpose of this thought experiment we'll only consider nonnegative integers. Let's say, arbitrarily, that the smallest "large number" is . This number is in fact quite large for most practical purposes, and for most computers these days is the largest unsigned integer they can handle without the need for any clever programming. All numbers from 0 to are considered "small" and all numbers upwards from are considered "large." Let us say, again also arbitrarily, that is "infinite" (i.e. is thus not considered a number and the "large numbers" are to ). The percentage of "small numbers" is then about 0.000000023283%, while the percentage of "large numbers" is about 99.9999999767%.

As it is an understatement that infinity is much larger than our arbitrary setting, the actual percentage of "large numbers" is much greater than given here and the percentage of "small numbers" much smaller. As we let go towards infinity, the percentage of "small numbers" (i.e. 0 to ) among "all numbers" (i.e. 0 to ) goes down to 0%, i.e.

while the percentage of "large numbers" goes up to 100%, i.e.


Since between each pair of consecutive integers there is the same uncountably infinite (the cardinality of the continuum , i.e. the cardinality of the power set of the integers) number of real numbers, this theorem could just as well be extended to all real numbers, while the proof could remain concerned only with integers.

While frivolous, this theorem is not useless. It can be used to show, among other things, that there is no "lossless data compression method that compresses all inputs to smaller bit strings,"[2] or that it is entirely unrealistic to expect to find counterexamples to certain conjectures by testing each progressively larger number until finding the one that disproves the conjecture.

See also


  1. Weisstein, Eric W., Frivolous Theorem of Arithmetic, from MathWorld—A Wolfram Web Resource.
  2. Steven Pigeon, "The Frivolous Theorem of Arithmetic" Harder, Better, Faster, Stronger blog.