Back to Riemann, Part 5


So far, I’ve covered exponents, i, e, ln() and series expansions.

n^x is a continuous line from minus to plus infinity if n is not 0 or 1, and x is a real number.

If n = e, when x = a + bi, then e^x = e^(a+bi) = (e^a) * (cos(b) + i*sin(b))

And, if a=0 and b = pi (3.14159),
e^i*pi = -1

making e^bi the function for drawing the unit circle.

Then, ln(), the natural logarithm, is just the inverse function for e^x.

I kind of jumped from n^x, for any value of n, to e^x. We can convert between them if we want to. If j = n – e, then n^x = (j + e)^x.

And, logb(x) for any base “b” is = ln(x) / ln(b).

Again, why use “e” and ln()? Because they’re easy to work with, they have special properties that other numbers don’t have, such as e^i*pi being on the unit circle, and we can always convert between them and base 10 numbers if we have to.

Why use series expansions? Well, that’s what the zeta function is (1 + 1/2^s + 1/3^s + 1/4^s + 1/5^s…), and some functions that are harder to work with in one form (e^(a+bi)) can be easier to work with in another (e^x = 1 + x + x^2/2! + x^3/3! + x^4/4! + x^5/5!…)

Ok, what’s the point?
So far, I’ve just wanted to lay down the groundwork. It’s now time to look at how everything started, to lead up to the Riemann Hypothesis.

We begin by trying to count the number of prime numbers below a particular limit.

A number is prime if its only factors are itself, and 1. Because 1 is a factor of all other numbers, it is not included in the list of primes. That means that 2, 3, 5 and 7 are the only primes less than or equal to 10. 4 is not prime because its factors are 1, 2 and 4. 6 is not prime because its factors are 1, 2, 3 and 6. 8 is not prime because its factors are 1, 2, 4 and 8. 9 is not prime because its factors are 1, 3 and 9.

We can define a counting function, usually given as:

pronounced “pi”, but is not to be confused with the constant 3.14159. This function counts the number of primes from 2 to x.

pi(10)  = 4
pi(100) = 25
pi(1000) = 168

pi() as a function doesn’t have an equation to it, per se. At least, not just yet. It’s just a matter of sitting down and checking whether every number between 2 and 1000 is prime or non-prime, and then counting up all the ones that are prime.


(Plots here obtained from Wolfram Alpha. Above plot is for pi(10,000).)

What’s important here is to note that the plot of pi() from 2 to 10,000 is not linear. If we want to find some way of getting close at guessing the correct answers for how many primes there are between 100,000 and 199,999, we can’t use an expression in the form of y = n * x, or y = x^n, because they’re going to deviate too much from the real answer given by pi().

We could try using x * 0.125, or x^0.773, which look like they might be getting close to pi() in the range 0 to 10,000:

But, if we expand the range (referred to as changing the domain of the function) to 0 to 10,000,000, both approximations obviously fail.

Instead, it turns out that x/ln(x) works a lot better over the larger domains, and

pi(x) ~ x/ln(x)

is known as the Prime Number Theorem, where the squiggly means that the error between pi(x) and x/ln(x) goes to zero as x goes to infinity.

Remember, pi(x) actually does count the number of primes less than or equal to x, so that’s the truly correct value. But, hand-counting the primes is time consuming, so we want to find an equation that gives us a close approximate answer, and we use x/ln(x) for that.

How do we get the error between reality and the approximation?

error = pi(x) – x/ln(x)

And, we can introduce the idea of “a relative error”, which is (pi(x) – x/ln(x)) / x.

Or, the difference between the counting function pi() and the approximation x/ln(x), divided by x. If the relative error goes to 0 as x goes to infinity, then the number of primes below x is about x/ln(x), for large x.

What this means is that one of the closest methods we have, at the moment, for predicting the distribution of prime numbers is the formula x/ln(x). We’re going to try to find something better.


(Relative error for pi(x) and x/ln(x) from 0 to 1 million.)

Very quickly, one reason people care about prime numbers is that they’re used extensively in securing computer communications and data encryption. If you pick a very large number (150 digits) that is the product of 2 prime numbers, then you can make that number public, and it will be very difficult to determine which two prime numbers make up its factors. That is, it’s easy to test whether a random number is prime, but it’s much, much harder computationally to find the factors of that number. There can be billions of prime numbers that are 100 digits long, and the odds of randomly giving two people the exact same key are very near zero. So, for the moment, public key encryption is considered pretty secure, if you use long enough numbers. However, if there were some way of predicting the distribution of prime numbers exactly, it would become much easier to crack public key systems.

Advertisements
Leave a comment

1 Comment

  1. Back to Riemann, Part 8 | threestepsoverjapan

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: