The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

Question

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.

Preliminary: Mertens function and the Prime Counting function

Start by generalizing the Divisor summatory function as

$D_{k,s}(n) = \displaystyle\sum_{j=s}^n D_{k-1,s}(\lfloor \frac{n}{j} \rfloor )$
$D_{0,s}(n) = 1$
(1)

(the normal Divisor summatory function can be recovered by setting s to 1).

Using a variation on Linnik's Identity and a related identity, we can express Mertens function as

$M(n) = \displaystyle\sum_{j=0}^{\log_2{n}} (-1)^j D_{j,2}(n)$
(2)

and the prime counting function as

$\pi(n) = \displaystyle\sum_{k=1}^{\log_2{n}}\sum_{j=1}^{\log_2{n^\frac{1}{k}}} \frac{(-1)^{j+1} \mu(k)}{j k} D_{j,2}(n^{\frac{1}{k}})$
(3)

Preliminary: Generalizing the Dirichlet Hyperbola Method

There are symmetries in (1), which can be expressed by generalizing the Dirichlet Hyperbola Method into the following recursive identity

$D_{k,s}(n) = \displaystyle\sum_{m=s}^{n^\frac{1}{k}}\sum_{j=0}^{k-1} \binom{k}{j} D_{j,m+1}( \lfloor \frac{n}{m^{k-j}} \rfloor )$
(4)

If we specify s as 2 and various whole number values for k, as required in (2) and (3) above, we'll find

$D_{1,2}(n) = \lfloor n \rfloor - 1$
$D_{2,2}(n) = - (\lfloor n^{\frac{1}{2}} \rfloor ^ 2) + 1 +2 \displaystyle\sum_{m=2}^{\lfloor n^\frac{1}{2} \rfloor} \lfloor \frac{n}{m} \rfloor $
$D_{3,2}(n) = \lfloor n^{\frac{1}{3}} \rfloor ^ 3 - 1 +3 \displaystyle\sum_{m=2}^{\lfloor n^\frac{1}{3} \rfloor} \lfloor \frac{n}{m^2} \rfloor - \lfloor (\frac{n}{m}^\frac{1}{2}) \rfloor^2 + 2 \sum_{j=m+1}^{\lfloor (\frac{n}{m})^\frac{1}{2} \rfloor} \lfloor \frac{\frac{n}{m}}{j} \rfloor $
...and so on with ever larger expansions.

---

THE ACTUAL QUESTION

My question is two-fold, concerning the intersection of (4) with (2) and (3).

1) Has there been any work done on using this kind of approach as a basis for prime counting algorithms? Or, alternatively, does anyone have any smart ideas for improving or evolving such an approach?

I've actually turned this approach around in my head for quite some time, but without much luck - hence my question. Using a suitably large wheel with (4) (say, only letting m take on values that are not divisible by primes <= 19) generates a surprisingly fast (in constant time) prime counting algorithm, particularly for using $O(n^\epsilon)$ memory. It seems to run in something like $O(n^\frac{4}{5})$ time or a bit worse (empirically).

But like I say, that's roughly the ceiling on what I've figured out to do with it. Has any other work been done on approaches like this?

2) Is there any way to make use of approximations of (4) to say anything interesting about the asymptotic behavior of Mertens function or the prime counting function? I know the error term of the generalized divisor problem is known to be no worse than $\Delta_k(n) = O(x^{1-\frac{1}{k}} \log^{k-2} x )$, but that doesn't seem enormously useful, and there are definitely deeper structural connections between the various Divisor summatory function values employed in (2) and (3).

---

Addendum: Mathematica code

This is the Mathematica code for (4), as NumDivisors, (3), as PrimeCount, and (2), as Mertens.

NumDivisors[k_, s_, n_] := 
 Sum[ Binomial[k, j] NumDivisors[j, m + 1, n/(m^(k - j))], {m, s, 
   n^(1/k)}, {j, 0, k - 1}]  
NumDivisors[0, s_, n_] := 1  
PrimeCount[n_] := 
 Sum[(-1)^(j + 1)/(j k) MoebiusMu[k] NumDivisors[j, 2, n^(1/k)], {k, 
   1, Log[2, n]}, {j, 1, Log[2, (n^(1/k))]}]  
Mertens[n_] := 1 + Sum[(-1)^k NumDivisors[k, 2, n], {k, 1, Log[2, n]}]  

These can be tested against the following reference definitions.

ReferenceNumDivisors[k_, s_, n_] := 
 Sum[ReferenceNumDivisors[k - 1, s, n/j ], {j, s, n}]  
ReferenceNumDivisors[0, s_, n_] := 1  
ReferenceCountPrimes[n_] := PrimePi[n]  
ReferenceMertens[n_] := Sum[ MoebiusMu[j], {j, 1, n}]  

Answer 1

It is useful to classify arithmetic functions $f(n)$ involving the primes into two classes: those whose Dirichlet series involves the zeta function (or something similar, such as a Dirichlet L-function) in the numerator, and those that involve zeta functions in the denominator. Examples of the former type include the constant function 1 and the various divisor sum functions. Examples of the latter type include the Mobius and von Mangoldt functions. The functions of the latter type are much harder to control, because by their nature they are very sensitive to the location of zeroes of the zeta function, and in particular are sensitive to the truth of statements such as the Riemann hypothesis. Functions of the former type, by contrast, pay almost no attention to the location of these zeroes.

Because of this difference in sensitivity to zeta zeroes, it is highly unlikely that one can rely solely on asymptotics for sums of functions of the first type to conclude useful asymptotics on functions of the second type, and the series expansions which connect the two are likely to have very poor convergence properties (much as Taylor series such as $\log(1-x) = -x - x^2/2 - x^3/3 - \ldots$ must necessarily have poor convergence properties near the singularity x=1).

On the other hand, there are certainly useful hyperbola-type identities for sums involving functions of the second type, such as Vaughan's identity. The catch is that the sums that come out of such identities, if they are to be useful, must still involve at least one function of the second type, since one cannot hope for the influence of zeta zeroes to magically disappear (unless the identity is so badly convergent that one can hide this influence inside the accumulated error terms in the asymptotics; but in such cases, the identity is likely to be useless for the purpose of producing asymptotics).

It is also possible to use methods of sieve theory to upper bound functions of the second type, such as $\Lambda$, by divisor sums which are basically of the first type, and indeed such upper bound sieves can be very useful in analytic number theory. However, they do not seem capable, by themselves, of producing asymptotics for functions of the second type (although with the addition of non-trivial ingredients outside of sieve theory, this is occasionally possible, e.g. with the Friedlander-Iwaniec theorem).

Answer 2

related work http://dl.dropbox.com/u/13155084/Given%20a%20divisor%20k.pdf