See An Inquiry into What It Can Mean That an Infinity of Prime Numbers somehow Can Equal an Infinity of All Numbers (December 12, 2012) with Response by Rick Lightburn
— The number of primes less than P is NOT approximately log(P).
— Rather, it is approximately P / log(P).
This is the Prime Number Theorem.
It was conjectured, on the basis of numerical evidence, by Gauss (1777-1855). It was proved independently, in 1896, by Hadamard and by de la Vallee Poussin.
* * *
More generally, our community faces an exegetical conundrum.
We are adjured that, before we try to understand the great men (sic) of the past better than they understood themselves, we must first try to understand these men as they understood themselves.
The utility and power and simple correctness of this stricture are beyond dispute.
At the same time, if we do not take precautions against getting stuck to the past as if it were a tar baby, we will have difficulty applying that same stricture to the present.
Namely, before we try to understand modern mathematics, or modern science, better than they understand themselves, we must first try to understand them as they understand themselves.
In this regard, it has been standard mathematical practice, for at least a century, to unbundle the issue of how many primes there are, from the issue of the infinities. Although the issues are closely intertwined, they are expositionally distinguishable.
It has been established since antiquity that there are infinitely many primes: that is, that there is no largest prime. The classical proof is in Euclid, although numerous other proofs have since been developed.
But this formulation is simply using the words “infinitely many” — and implicitly their reification, “infinity” — as a synonym for “there is no largest.”
* * *
As to the infinities, it is possible, but it is not necessary, to drag in anything as exotic as the prime numbers, and the Prime Number Theorem.
Instead, consider merely the odd integers, as a subset of the integers:
— Obviously there are only “half” as many odd integers as integers (the other “half” being the even integers).
— Yet, almost as obviously, the set of odd integers can be put into a one-to-one correspondence with the set of all the integers. So there are the “same” number of elements in each of these two sets.
Over the centuries, this oddity was noted by many, including Galileo.
Today it is the second of these two definitions that is taught, not just in universities, but in high schools.
(Here we are tippy-toeing toward our understanding modern mathematics first as it understands itself.)
Two sets are defined as having the same cardinal number if there exists a one-to-one correspondence between the elements of the two sets. (Not every correspondence has to be one-to-one. Instead, there merely has to exist a one-to-one correspondence.)
Any set that can be put into a one-to-one correspondence with the integers is called countable, or denumerable.
On this definition, the odd integers, and the even integers, and the totality of integers, have the “same” cardinal number. Each set is countable.
Indeed, this definitional structure can be pushed further. A set can be defined as infinite if there exists a one-to-one correspondence between the set and a “proper” subset of the set. (The “improper” subset of a set would be the set itself.)
“But, but, but… there are still only half as many odd integers as integers.”
“Fine. But if you cannot cannot unstick yourself from that tar baby, at least provisionally, you will not understand modern mathematics as it understands itself. You will therefore be violating your own exegetical stricture.”
* * *
Now moving on as to infinities, still without any reference to prime numbers —
As just noted, the sets of odd integers, and even integers, and integers are all countable sets.
Interestingly, although there appear to be more “rational” numbers (numbers that can be expressed as a “ratio” or fraction) than integers, nevertheless the set of rational numbers is also countable.
That is, there exists an ordering of the rational numbers that has a first and second and third (etc.) rational number, and takes in all of the rational numbers. Here it is:
1/1 2/1 3/1 4/1 5/1 …
1/2 2/2 3/2 4/2 5/2 …
1/3 2/3 3/3 4/3 5/3 …
1/4 2/4 3/4 4/4 5/4 …
1/5 2/5 3/5 4/5 5/5 …
… … … … …
Start at the top left. Then drop southeast, counting each diagonal as you go.
This array of fractions is an instance of the important general theorem that a countable union of countable sets is countable.
* * *
So much for the sets of odd integers, and even integers, and integers, and rational numbers: each of these four sets is countable.
Now what about the “irrational” numbers (the numbers that cannot be expressed as a “ratio” or fraction)?
We must be careful. Our paradigm for an “irrational” number is probably the square root of two: the Pythagorean diagonal of the unit square
It is proved in early high school algebra that this diagonal is incommensurable with the side. That is, the diagonal is not a “rational” multiple of the unitary side.
The vast gulf between the rational numbers and the irrational numbers appears to be:
— The decimal expression of a rational number either terminates ( 1/4 = .25 ) or repeats ( 1/7 = .142857142857… )
— The decimal expression of an irrational number does not repeat: no matter to how many decimal places one carries the expansion, no repeated pattern emerges.
However, despite this vast gulf, there is a hidden kinship between the rational numbers and at least some of the irrational numbers.
All of the rational numbers, and at least some of the irrational numbers, are the roots of polynomials with rational coefficients:
— The rational number 1-2/3, or 5/3, is the root of the polynomial 3x – 5 = 0.
— The irrational number sqrt(2) is the (positive) root of the polynomial x^2 – 2 = 0.
Numbers, whether rational or irrational, that are the roots of polynomials with rational coefficients are called algebraic numbers.
We already noted that the set of rational numbers is countable.
Amazingly, so is the set of “irrational algebraic” numbers.
That is because the set of polynomials with rational coefficients contains only countably many polynomials. (Use the “countable union” theorem: There are countably many exponents of the leading term, and finitely many lower exponents of remaining terms, and countably many rational coefficients of each term.)
This definition immediately raises the question:
Given that there exist “rational algebraic” numbers ( e.g. 1-2/3 ), and “irrational algebraic” numbers ( e.g. sqrt(2) ), are there also irrational numbers that are not algebraic? — i.e. irrational numbers that are transcendental?
— In 1844 Liouville exhibited the first known transcendental number.
— In 1873 Hermite proved that e = 2.718281828459045… (the base of natural logarithms) is transcendental.
— In 1882 Lindemann proved that pi = 3.1415926535… is transcendental. He thereby proved, after roughly 2-1/2 millennia, that it is impossible to “square the circle” (with a compass and an unmarked straight-edge) — the problem exhibited by Dante, on the last page of the Divine Comedy, as impossibly hard.
— In 1874, and then sensationally in 1891, Cantor proved that the real numbers are not countable.
There is, somehow, a “larger” infinity than the infinity of the (countable) integers.
This larger “uncountable” infinity turns out to be the set of all subsets of the “countable” integers.
Now the real numbers consist of the rational, and the irrational, numbers.
Alternately, the real numbers consist of the algebraic, and the transcendental, numbers.
But we have already noted that the rational numbers, and the algebraic irrational numbers, are countable.
So, by process of elimination, it must be the transcendental irrational numbers that are uncountable.
Infinities therefore have different “sizes” — different cardinal numbers:
— The “smallest” infinity — that of the integers, a countable set — is denoted aleph-null.
— The “larger” uncountable infinity of the real numbers — the set of all subsets of the countable integers — is denoted aleph-one.
— Still “larger” infinities — aleph-two, aleph-three, etc. — result from repeatedly taking the set of all subsets of a given infinity.
* * *
In closing, let’s turn to a correct articulation of the Prime Number Theorem.
We were able to get through all that we did, just now, as to infinities, without uttering Word One about either the Prime Number Theorem, or primes in general.
It is true that the primes are a countable subset of the countable integers. (The other countable subset in this split is, of course, the composite numbers.)
But there was no need, in examining countability, to invoke special properties of the primes, beyond the fact that the primes are countably infinite (as are many other subsets of the integers).
However, we are obligated to clean up that dreadful typo in the statement of the Prime Number Theorem.
This theorem is ordinarily stated in terms of the prime counting function, pi(x):
— This expression, pi(x), is defined to mean the number of primes less than or equal to x.
— Note that this “pi” is not the “pi” of (say) “pi * r^2,” or “3.14…”
— Instead, this “pi” is a letter of the alphabet, and denotes a function, just as would f, or g, or h.
— So this “pi” is a homonym: it sounds the same, but it means something different.
The Prime Number Theorem of 1896 states:
pi(x) ~ x / log(x)
— The twiddle ( ~ ) is read “is approximately,” a concept that is made rigorous.
— And log(x) denotes the natural (base e) logarithm, not the common (base 10), logarithm.
* * *
What follows is my own pedagogical attempt to make sense of the Prime Number Theorem.
I haven’t seen this articulation anywhere else, but it has helped me.
Start with a sequence of four rhetorical questions about the positive integers. (The set of positive integers is commonly denoted Z: German “Zahl.”)
We begin at the shallow end of the kiddie pool.
Q-1-Z How many positive integers are there, less than or equal to 10?
Q-2-Z What is the tenth positive integer?
Q-3-Z How many positive integers are there, less than or equal to N?
Q-4-Z What is the N-th positive integer?
We now pose the same sequence of four rhetorical questions about the primes.
(The number 1 is considered neither prime nor composite, but rather is the unit. That is because, if 1 is considered prime, then it is also composite: 1 (composite) = 1 (prime) times 1 (prime). Unfortunately, there are also infinitely many other factorizations of 1 (composite) into as many 1’s (prime) as we please. This efflorescence, unique to the number 1, destroys the important principle of “unique factorization into primes,” and is therefore to be avoided.)
Q-1-p How many primes are there, less than or equal to 10?
A-1-p 4 primes. They are 2, 3, 5, and 7. Symbolically, pi(10) = 4.
Q-2-p What is the tenth prime?
A-2-p 29. To get to it, we must first wade through its nine predecessors: 2, 3, 5, 7, 11, 13, 17, 19, 23.
Q-3-p How many primes are there, less than or equal to N?
A-3-p Abruptly, we are plunged into the deepest end of the pool.
This is the Prime Number Theorem: pi(N) ~ ______ ?
Gauss himself, although he actively conjectured it, could not prove it.
However, there is one thing we can say about this answer, with absolute certainty. Over at A-3-Z, the answer was N.
Here at A-3-p, the answer must be strictly less than N. That is because we seek only a subset of those N positive integers, namely the primes.
Put another way, if we need a smaller number than N, then N has to be deflated to a smaller value. N has to be divided by something.
And we “know” the answer: N has to be divided by log(N):
pi(N) ~ N / log(N)
Q-4-p What is the N-th prime?
A-4-p Same deepest water. Same drill.
Once again, there is one thing we can say about this answer, with absolute certainty. Over at A-4-Z, the answer was N.
Here at A-4-p, the answer must be strictly greater than N. That is because we must overshoot N to find enough primes.
Put another way, if we need a larger number than N, then N has to be inflated to a larger value. N has to be multiplied by something.
The answer here is, “of course,” N * log(N).
I seriously doubt that the statement of the Prime Number Theorem can be made appreciably clearer than this.
Brian A. Kennedy