Saturday, November 03, 2012

Differential equation and prime counting

A bit over a decade ago in the summer of 2002 I found a difference equation which can be constrained to count prime numbers. The derivation is remarkably simple requiring only very elementary techniques, but weirdly enough leads to this difference equation which in turn leads to a partial differential equation.

My pivotal idea was to count composites at each prime excluding counts from smaller primes. And that seemingly small shift leads to dramatic mathematical consequences.

The count at each composite is given by:

ΔS(x,pj) = [x/pj] - 1 - (j-1) - S(x/pj, pj-1)

That is the count of composites for a particular prime excluding composites that are products of lesser primes.

First it gets a count of integers with a prime as a factor, subtracts 1 for the prime itself, and then subtracts the count of primes less than it. And finally it subtracts the count of composites multiplied times that prime.

Here's an example:

ΔS(16,3) = [16/3] - 1 - 1 - S(16/3,2) = 5 - 1 - 1 - 1 = 2

There are 5 numbers with 3 as a factor below 16, but you subtract 1 for 3, then 1 for 2, to handle 2(3), and then 1 more for the count of composites times 3, where that is for 12.

The S function is just a complete count of composites, so it is a sum of ΔS functions, where of course, if you have the complete count of composites you can count primes.

The form of the ΔS function leads to a very compact prime counting function.

I call the prime counting function P:

P(x,pj) = [x] - S(x,pj) - 1

which allows me to simplify ΔS(x, pj) to

ΔS(x,pj) = P(x/pj,pj-1) - (j-1)

where again pj has to be less than or equal to sqrt(x).

And I can make things a little simpler with the P function by not writing the prime itself but just using its indice, so then P(x,j) is equivalent to P(x,pj).

And the entire thing is:

P(x,n) = [x] - 1 - sum for j=1 to n of {P([x/p_j],j-1) - (j-1)}

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

That is quite compact!

So much from a simple shift in an idea, where excluding counts of composites with smaller primes as factors yields a surprisingly efficient result.

Actually using it to count primes is very straightforward, for instance to count the primes up to 100, you need primes up to sqrt(100) = 10, which is 4 primes. And those primes of course are 2, 3, 5, and 7.

And the prime count is given by:

P(100,4) = 100 - 1 - (P(50, 0) - 0)  - (P(33,1) - 1) - (P(20,2) - 2) - (P(14,3) - 3)

Except P(14,3) needs a correction because the 3rd prime is 5 which squares to 25, so that is going too high as it's bigger than 14 and has to be reset to P(14,2). Then I have:

P(100,4) = 100  - 1 - 49 - 16 - 6 - 3 = 25

So there are 49 even composites, 16 odd composites with 3 as a factor, 6 composites with 5 as a factor but no smaller prime as a factor. And 3 that have 7 as a factor with no smaller prime, and I'll give those as it's just three numbers so easy to do and they are of course: 49, 77 and 91.

(It's fascinating to me that the symbols "S" and "ΔS" disappear at this point though the sum is the S function and the ΔS is what is being summed so they are still there.)

And for a comparison to other techniques you can look up "prime counting function" on the web.

However, we're going to push forward as there is a difference equation yet to be found, which remarkably enough is lurking within that form!

Notice that P(x,pj) is the full count of primes up to and including x, if pj is greater than or equal to the last prime less than sqrt(x), so I can remove all mention of primes with the following

ΔS(x,y) = (P(x/y,y-1) - P(y-1, sqrt(y-1)))(P(y, sqrt(y)) - P(y-1, sqrt(y-1)))

as if y is not prime then

P(y, sqrt(y)) - P(y-1, sqrt(y-1)) = 0

with the constraint that if y>sqrt(x), then P(x,y) = P(x,sqrt(x)) to keep the correct count.

And of course now I finally have my difference equation.

Notice here that sqrt(x) is the integer square root, so it means to find the largest integer less than or equal to sqrt(x), for instance, the integer square root of 10 is 3.

I also now have

P(x,y) = [x] - S(x,y) - 1

as I can remove mention of primes themselves!

Here's the new function then with all mention of primes removed:

P(x,y) = [x] - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

Not as efficient a way to actually count, but in this fully mathematized form we can see a reason for a connection between the count of primes and non-discrete functions that intrigued notables from Euler, to Chebyshev, Gauss, and of course Riemann along with others.

From the difference equation in that summation I can get to a partial differential equation:

P'y(x,y) = -(P(x/y,y) - P(y, sqrt(y))) P'(y, sqrt(y))

And our connection between the count of prime numbers and a differential form is complete.

One of the coolest things to me that jumps out is the x/y within it. With the integration x would be constant, and of course 1/y integrates as the logarithm, but it's still a bit of a reach I think as x/ln x is one of the known approximations to the prime count. And I'm just really out of my area of math comfort at this point.

There is more to guess here though, as notice above I ended up with a reset if y is greater than sqrt(x), which comes in from the original ΔS function and how it counts composites:

ΔS(x,pj) = [x/pj] - 1 - (j-1) - S(x/pj, pj-1)

You only need primes up to or equal to the sqrt(x) or the count is off! For instance, [100/11] = 9 numbers with 11 as a factor, but all composites have already been counted, so it screws everything up if you keep going.

But if you integrate the partial differential that rule is not in sight. That would add more ΔS values. Continuing on with additional ΔS values with the discrete equations decreases the size of P(x,y) as you're subtracting more. So one more guess is that the integration would tend to be below the prime count.

And that is what's seen with what we can assume are approximations, with x/ln x, for instance 100/ln 100 equals approximately 21.71, which lags behind the prime count of 25. And 1000/ln 1000 is approximately 144.76 which lags behind the count of primes up to 1000, which is 168. Guessing then it would never catch it.

But now there is the possibility of a direct answer to one of the more intriguing mathematical questions ever presented. Evaluating that partial differential equation could answer quite a few questions and again I admit it is out of my league to move well there.

While I did take numerical methods for my physics degree it was over two decades ago, and besides there are some serious experts in this area all over the world who could do the best job. I just wish I could get some help here, as I will admit I'm a bit curious!

James Harris

No comments: