Built on Facts

Sunday Function

We’re doing two functions today. If I’m not mistaken we’ve done each of them separately, but there’s a famous and interesting relationship between the two that’s always interesting to look at. Like very many interesting mathematical facts, it has to do with the prime numbers.

As such the first function is the log integral Li(x), usually defined in the following way:

i-d4bb9fe09d6b78eb832985821d8a307f-1.png

We’ll plot it in a minute, but if you’re interested in a rough idea of it’s behavior it so happens that Li(x) ~ ln(x)/x. That is, those two functions have a smaller and smaller percentage difference as x becomes larger.

Now the second function is π(x), which is the prime counting function. The notation is traditional; the pi has nothing to do with the number 3.14159…, rather the p in pi is supposed to suggest the word “prime”. π(x) is defined as the number of prime numbers less than or equal to x. For instance, π(10) = 4, because there’s 4 primes less than 10 (1 is not a prime, if you’re curious.).

Now if we plot these two functions on the same graph we may get the accurate impression that the two are related.

i-a00d2ad65a221c80717ba30b258614fe-graph1.jpg

The log integral and the prime counting function get closer and closer to each other in percentage terms as x gets large. This is the prime number theorem, and it is tremendously important in understanding the properties of the prime numbers.

You may also notice that while the log integral is a very good approximation, it is an approximation and over the interval of the graph it’s always a little higher than the actual number of primes. This is true if you plot the first million primes or the first billion primes or the first trillion primes. For a while it was thought that this property of Li(x) > π(x) held for all x. There was some theoretical support for the idea that this was universal, but in math theoretical support isn’t worth a whole lot. You want a rigorous mathematical proof. And it turns out that you wouldn’t be able to prove that property because it’s not true. In 1914 the great mathematician John Littlewood proved that in fact the property was not universal. At some large x, the prime counting function would pass up the log integral function (though of course their percentage difference would continue to decrease). Then it would in turn be passed up, and they would go on trading off an infinite number of times. But his proof of this fact was not a so-called “constructive” proof, which means that though he proved that some x existed where one passed the other, his proof did not in fact tell you what that x might be. Could be relatively small, could be unimaginably huge.

In 1933 another mathematician named Stanley Skewes was able to shed some light on the issue. He wasn’t able to find the specific number for the first crossover, but he was able to show that whatever it was, it was mathematically certain to be less than a number that’s usually now called Skewes’ number. That number was really unimaginably huge. If you packed the universe shoulder to shoulder with tiny print zeros you wouldn’t even be able to write the number, much less the quantity that number represents. You have to use a tower of exponents to write the number. The number is approximately equal to 10^10^10^34.

Isaac Asimov tacked the subject of explaining such a huge number in simple terms in his classic essay “Skewered!” I don’t think it’s online but it’s in his excellent essay collection “Of Matters Great and Small“.

For a while it was the largest number to naturally appear in a mathematical proof. It’s since been passed up by others which are much larger. On the other hand, since Skewes’ number is an upper bound subsequent work has been able to show that the first crossing actually occurs at a vastly smaller number. The number is still huge, but not nearly so huge as Skewes’ number – around 10^316, to be specific.

By physics standards this is a gargantuan number. But by mathematics standards it’s not so much. After all, there’s an infinite number that are larger.

Comments

  1. #1 Rob
    November 16, 2009

    Very well done little essay. I’ve read an interesting essay called Who Can Name the Bigger Number? It discusses computability, Ackerman functions, and the “Busy Beaver Function” and is quite fascinating. And yet, after all that, the mind boggling thing to me is that nearly every integer is larger than any integer one can define, computable or not!

  2. #2 Uncle Al
    November 16, 2009

    10^316? “ACK! THBBFT!” String theory’s acceptable vacua leave that in the exponential dust.

  3. #3 Ed
    November 18, 2009

    I’m confused. If Li(x) ~ ln(x)/x, shouldn’t Li(x) be less than 1 for all x?

    Or should the right hand side be flipped over?

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.