I've been working on the following prime number related stuff over the
last year and a half. I've been unable to find reference to ANY of it
in any of the number theory books / papers I've read through. So my
question is, is any of the following known (and if so, where should I
look to read more about it), and is any of it noteworthy?
Section 1: Prime Power Function
-------------------------------
For any positive constant integer N, where n1, n2, ... nx are natural
number variables greater than or equal to 2,
#{ n1 = N : nx >= 2 }
- 1/2 * #{ n1 * n2 = N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 = N : nx >= 2 }
- 1/4 * #{ n1 * n2 * n3 * n4 = N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 = N : nx >= 2 }
- ...
which is to say, the count of ways that N can be expressed as an
integer greater than 1, minus half the count of ways that N can be
expressed as two integers multiplied together, each greater than 1,
plus a third of the count of ways N can be expressed as three integers
each greater than 1 multiplied together, and so on is equal to the
following:
0 if N is composite
1 if N is prime
1 / power if N is a prime power
So, for example,
245
---
+ 1 / 1 * #{ (245) } = +1
- 1 / 2 * #{ (5*49), (7*35), (35*7), (49*5) } = -2
+ 1 / 3 * #{ (5*7*7), (7*5*7), (7*7*5) } = +1
--
0
Thus, 245 is composite.
81
--
+ 1 / 1 * #{ (81) } = +1
- 1 / 2 * #{ (3*27), (9*9), (27*3) } = -3/2
+ 1 / 3 * #{ (3*3*9), (3*9*3), (9*3*3) } = +1
- 1 / 4 * #{ (3*3*3*3) } = -1/4
----
1/4
Thus, 81 factors to a prime to the 4th power.
Section 2: Prime Powers Counting Function
-----------------------------------------
The identity from Section 1 requires, generally, factoring N before we
can find the number of solutions for each count. If, however, we sum
this identity for all values from 2 to N, we find that
#{ n1 <= N : nx >= 2 }
- 1/2 * #{ n1 * n2 <= N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 <= N : nx >= 2 }
- 1/4 * #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
- ...
is equal to the count of primes <= N plus one half the count of primes
less than or equal to N^(1/2) plus one third the count of primes less
than or equal to N^(1/3) and so on, or, in other words,
#{ n1 <= N : n1 prime }
+ 1/2 * #{ n1 <= N^(1/2): n1 prime }
+ 1/3 * #{ n1 <= N^(1/3): n1 prime }
+ 1/4 * #{ n1 <= N^(1/4): n1 prime }
+ 1/5 * #{ n1 <= N^(1/5): n1 prime }
+ ...
Counting these lattice volumes is not trivial, but it can be done
without resorting to factoring.
Section 3: Prime Counting Function
----------------------------------
The prime powers coutning function from Section 2 yields precisely the
same values as Riemann's similar function. Thus, we can use the same
techniques, employing a mobius inversion to yield the exact count of
primes less than or equal to N.
Section 4: Lattice Counting
---------------------------
For an expression like
#{ n1 * n2 * ... nx <= N: n1, n2, ... nx >= 2 }
any given set of numbers will show up at most x! times. Additionally,
the smallest value in the set will be at most floor( N^( 1 / x ) ).
If we count the number of values in the lattice from smallest value to
largest, our process can look, very roughly, something like this:
for( a_1 = 2 to N^(1/x) )
for( a_2 = a_1 to ( N^(1/(x-1) )/a_1 )
for( a_3 = a_2 to ( N^(1/(x-2))/(a_1*a_2) )
...
for( a_(x-1) = a_(x-2) to ( N^(1/2)/( a_1*a_2*...*a_(x-2) ) )
total += b1 + ( N / ( a_1*a_2*...*a_(x-1) ) - 1 ) * b2
where b2 is calculated based on how many times values in the set( a_1,
a_2, ..., a_(x-1) ) are equal to each other. This technique can be
vastly sped up by using a wheel.
With my current implementation of lattice counting, which is an area
of research I don't know much about, this yields a prime counting
algorithm that works, at least empirically, in O( N ^ 4/5 + epsilon )
time and O( epsilon ) space. I have this coded and working right now.
Section 5: Continuous Volumes Bounding Lattices
-----------------------------------------------
As before, with n1, n2, ... nx integers >= 2 and N a constant value,
#{ n1 * n2 <= N } is bounded by the continuous (real-variable) curve
x1*x2 = N, x1 >= 1, x2 >= 1. All valid integer pair solutions to the
first equation are contained entirely by this volume, and only integer
pair solutions from this first equation are contained entirely by this
volume. The integral for this volume is N log N - N + 1.
#{ n1 * n2 * n3 <= N } is bounded by the continuous curve x1*x2*x3 =
N, where, x1, x2, and x3 are all >= 1. The integral for this volume
is N/2 * ( log N )^2 - N log N + N - 1. It has similar properties to
the first equation in terms of the specific lattice points it bounds.
#{ n1 * n2 * n3 * n4 <= N } is bounded by a volume that is, when
integrated, equal to N/6 * ( log N )^3 - N/2 * ( log N )^2 + N log N -
N + 1.
And so on. All of these volumes have similar properties regarding the
lattice points that they bound.
Section 6: Relationship to the Prime Number Theory
--------------------------------------------------
If we replace the prime power counting function from section 2,
#{ n1 <= N : nx >= 2 }
- 1/2 * #{ n1 * n2 <= N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 <= N : nx >= 2 }
- 1/4 * #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
+ ...
with the continuous variable volumes bounding each of these lattices
as approximations, we arrive at the following equation:
( - 1 + N )
- 1/2 * ( 1 - N + N log N )
+ 1/3 * ( - 1 + N - N log N + N/2 ( log N )^2 )
- 1/4 * ( 1 - N + N log N - N/2 ( log N )^2 + N/6 ( log N )^3 )
+ 1/5 * ( - 1 + N - N log N + N/2 ( log N )^2 - N/6 ( log N )^3 + N/24( log N )^4 )
-...
This value is equal the Logarithmic Integral, Li( N ).
It might be possible one could construct an elementary proof of the
prime number theory based off of these relationships, assuming that
all the steps to this point were proven.
Section 7: Relationship to the Zeroes of the Riemann Zeta Function
------------------------------------------------------------------
The equation from Section 2,
#{ n1 <= N : nx >= 2 }
- 1/2 * #{ n1 * n2 <= N : nx >= 2 }
+ 1/3 * #{ n1 * n2 * n3 <= N : nx >= 2 }
- 1/4 * #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
+ 1/5 * #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
- ...
is precisely equal to
#{ n1 <= N : n1 prime }
+ 1/2 * #{ n1 <= N^(1/2): n1 prime }
+ 1/3 * #{ n1 <= N^(1/3): n1 prime }
+ 1/4 * #{ n1 <= N^(1/4): n1 prime }
+ 1/5 * #{ n1 <= N^(1/5): n1 prime }
+ ...
which, by Riemann's work, is equal to
Li( N ) - Li( N^( each non-trivial zeta zero ) ) - ln 2 + tiny integral
Given that the formula involving the bounding continuous volumes from
the preceding section equals Li( N ), we can see that
( - 1 + N
- #{ n1 <= N : nx >= 2 } )
- 1/2 * ( 1 - N + N log N
- #{ n1 * n2 <= N : nx >= 2 } )
+ 1/3 * ( - 1 + N - N log N + N/2 ( log N )^2
- #{ n1 * n2 * n3 <= N : nx >= 2 } )
- 1/4 * ( 1 - N + N log N - N/2 ( log N )^2 + N/6 ( log N )^3
- #{ n1 * n2 * n3 * n4 <= N : nx >= 2 } )
+ 1/5 * ( - 1 + N - N log N + N/2 ( log N )^2 - N/6 ( log N )^3 + N/24( log N )^4
- #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 })
- ...
which represents volumes of the various bounding curves that aren't
contained by lattice squares/cubes/etc underneath them (and which,
when totaled, is the amount that Li( N ) deviates from pi( N ) +
1/2pi( N^1/2) + 1/3pi( N^1/3) + ... ) is thus equal to
- Li( N^( each non-trivial zeta zero ) ) - ln 2 + tiny integral
What repurcussions, if any, this has is unclear to me.
Section 8: Mu Function
----------------------
For any positive constant integer N, where n1, n2, ... nx are natural
number variables greater than or equal to 2, and where the syntax #{ a
* b <= c } denotes the count of solutions to a * b <= constant c, the
sum
- #{ n1 = N : nx >= 2 }
+ #{ n1 * n2 = N : nx >= 2 }
- #{ n1 * n2 * n3 = N : nx >= 2 }
+ #{ n1 * n2 * n3 * n4 = N : nx >= 2 }
- #{ n1 * n2 * n3 * n4 * n5 = N : nx >= 2 }
+ ...
(which is to say, the negative value of the count of ways that N can
be expressed as 1 integer greater than 1, plus the count of ways that
N can be expressed as 2 integers multiplied together, each greater
than 1, minus the count of ways N can be expressed as three integers
each greater than 1 multiplied together, and so on)
is equal to the mobius mu function, where
mu( N ) = 0 if N is not squarefree
1 if N is squarefree and has an even number of factors
-1 if N is squarefree and has an odd number of factors
Section 9: Mertens Function
---------------------------
The identity for mu above requires, generally, factoring N to find the
number of solutions for each equation. If, however, we sum this
identity for all values from 2 to N, we find the following:
- #{ n1 <= N : nx >= 2 }
+ #{ n1 * n2 <= N : nx >= 2 }
- #{ n1 * n2 * n3 <= N : nx >= 2 }
+ #{ n1 * n2 * n3 * n4 <= N : nx >= 2 }
- #{ n1 * n2 * n3 * n4 * n5 <= N : nx >= 2 }
+ ...
Calculating the number of solutions for each of these values, while
not simple, can be done without resorting to any factoring. These
values are essentially the number of integer lattice values under
various regular rectangular hyperbola volumes.
This identity is a way of expressing the Mertens Function, the sum of
the mobius mu.
Section 10: d_k
---------------
The count of ways a number N can be represented by k integers >= 1
multiplied together, if N in its canonical prime decomposition is
represented by p1^a1 * p2^a2 * ... * px^ax, is equal to
( a1 + k - 1 )! / ( a1! * ( k - 1 )! )
* ( a2 + k - 1 )! / ( a2! * ( k - 1 )! )
* ( ... )
* ( ax + k - 1 )! / ( ax! * ( k - 1 )! )
Section 11: d_k_2
-----------------
The count of ways a number N can be represented by k integers >= 2
multiplied together, if N in its canonical prime decomposition is
represented by p1^a1 * p2^a2 * ... * px^ax, is equal to
binomial( k, 0 ) * d_k ( N )
- binomial( k, 1 ) * d_(k-1)( N )
+ binomial( k, 2 ) * d_(k-2)( N )
- ...
and so on until the series terminates.
Section 12: Using d_k_x to calculate Mertens and Pi*
----------------------------------------------------
Using the family of d_k_x functions, we can rewrite the previous results as
Mu( N ) = - d_1_2( N ) + d_2_2( N ) - d_3_2( N )
+ d_4_2( N ) - ...
Prime Power( N ) = d_1_2( N ) - 1/2 * d_2_2( N ) + 1/3 * d_3_2( N )
- 1/4 * d_4_2( N ) + ...
Thus
Mertens( N ) =
- d_1_2( 1 ) + d_2_2( 1 ) - d_3_2( 1 ) + d_4_2( 1 ) - ...
- d_1_2( 2 ) + d_2_2( 2 ) - d_3_2( 2 ) + d_4_2( 2 ) - ...
- d_1_2( 3 ) + d_2_2( 3 ) - d_3_2( 3 ) + d_4_2( 3 ) - ...
- ...
- d_1_2( N ) + d_2_2( N ) - d_3_2( N ) + d_4_2( N ) - ...
and
pi*( N ) =
d_1_2( 1 ) - 1/2 * d_2_2( 1 ) + 1/3 * d_3_2( 1 ) - 1/4 * d_4_2( 1 ) + ...
+ d_1_2( 2 ) - 1/2 * d_2_2( 2 ) + 1/3 * d_3_2( 2 ) - 1/4 * d_4_2( 2 ) + ...
+ d_1_2( 3 ) - 1/2 * d_2_2( 3 ) + 1/3 * d_3_2( 3 ) - 1/4 * d_4_2( 3 ) + ...
...
+ d_1_2( N ) - 1/2 * d_2_2( N ) + 1/3 * d_3_2( N ) - 1/4 * d_4_2( N ) + ...
In general, though, while this appears to be true, it is an extremely
slow way to evaluate these functions. |
