Below is an approach I've been exploring for connecting the prime counting function with the logarithmic integral and expressing the error term between the two. I find it beguiling, but I've largely run out of ideas for further developing this approach.

Hence this question. What I'd really, really appreciate is either 1) references to papers or research covering the general space of ideas I'm exploring here, 2) an explanation for why this approach is going to be a dead end, or especially 3) ideas for manipulating or further exploring my equation (4) below that I might have overlooked. [Edit]I'm specifically interested in techniques I might be unfamiliar with from the study of the divisor summatory function $D_k$, which is at the heart of (4). [End Edit]


Start by summing Linnik's identity from 2 to n.

$\displaystyle\sum_{j=2}^n 1 - \frac{1}{2}\sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor} 1 + \frac{1}{3}\sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}\sum_{l=2}^{\lfloor\frac{n}{j k}\rfloor} 1 - \frac{1}{4}...=$ $\pi(n) + {\frac{1}{2}}\pi(n^{\frac{1}{2}}) + {\frac{1}{3}}\pi(n^\frac{1}{3})+...$

where $\pi(n)$ is the prime counting function. The nested sums on the left only need to be computed up to a depth of $\log_2 n$ before they start equalling 0.

Next, approximate the left hand side by replacing sums with integrals, starting integration at 1 rather than 2, and removing floor functions from upper bounds. This immediately gives the logarithmic integral.

$\displaystyle\int_{1}^n dx - \frac{1}{2}\int_{1}^n \int_{1}^{\frac{n}{x}} dy dx + \frac{1}{3}\int_{1}^n \int_{1}^{\frac{n}{j}}\int_{1}^{\frac{n}{x y}} dz dy dx - \frac{1}{4}... = li(n) - \log\log n - \gamma$

where $li(n)$ is the logarithmic integral and $\gamma$ is the Euler-Mascheroni constant. (You can find a fairly straightforward sketch of the derivations of both (1) and (2) here)

Now, Riemann's explicit formula for the prime counting function, with a touch of term rearrangement and with $\rho$ the Zeta Zeroes, is of course

$li(n) - \pi(n) - {\frac{1}{2}}\pi(n^{\frac{1}{2}}) - {\frac{1}{3}}\pi(n^\frac{1}{3})-...=\displaystyle\sum_{\rho} li(n^\rho) + \log 2 - \int_x^{\infty}\frac{dt}{t(t^2-1)\log t}$


Define the following $O( \log \log n)$ function

$E(n) = \log 2 - \int_n^{\infty}\frac{dt}{t(t^2-1)\log t} + \log \log n + \gamma$

Then, applying both (1) and (2) to (3) gives

$\displaystyle \sum_{\rho} li(n^\rho) + E(n) =$

$\displaystyle - \frac{1}{2}(\int_{1}^n \int_{1}^{\frac{n}{x}} dy dx - \sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor} 1 )$
$\displaystyle+ \frac{1}{3}(\int_{1}^n \int_{1}^{\frac{n}{j}}\int_{1}^{\frac{n}{x y}} dz dy dx - \sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}\sum_{l=2}^{\lfloor\frac{n}{j k}\rfloor} 1)$
$\displaystyle- \frac{1}{4}(\int_{1}^n \int_{1}^{\frac{n}{j}}\int_{1}^{\frac{n}{x y}}\int_{1}^{\frac{n}{x y z }} dw dz dy dx - \sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}\sum_{l=2}^{\lfloor\frac{n}{j k}\rfloor}\sum_{m=2}^{\lfloor\frac{n}{j k l}\rfloor} 1)$
$\displaystyle +\frac{1}{5}...$

So here is, really, my main question: can anything interesting be done with the right hand side of (4)? I've largely hit a dead-end here.

[Edit] What I'm looking for especially is any smart ideas about different ways of working with, or breaking up, or transforming those various nested sums, particular in ways that might take advantage of symmetries or connections between them.

As Eric Naslund mentions in his equation (2) below, these nested sums are closely related to, and can be expressed in terms of, the divisor summatory function. As a consequence, this opens up the door to the possibility of applying Voronoi summation or the Dirichlet Hyperbola method in connection with these nested sums, for example. I'm curious if there are any other smart techniques from the study of the divisor summatory function that might be brought to bear on (4). [End Edit]


I have explored, a bit, one approach with (4), to inconclusive results.

The following are all equal

$\displaystyle\sum_{j=2}^n \sum_{k=2}^{\lfloor \frac{n}{j} \rfloor} 1 = \sum_{j=2}^n \lfloor \frac{n}{j} \rfloor - 1 = \sum_{j=2}^n \frac{n}{j} - 1 - \sum_{j=2}^n ${$\frac{n}{j}$}

where {n} is the fractional part function. This approach can be generalized to arbitrary depths of nested sums. $\sum_{j=2}^n \frac{n}{j} - 1$ and its generalization appear to be relatively smooth curves, capable of relatively tight approximation, or that's my hunch based on empirical results. Anyway, relying on this, (4) can be rewritten as

$\displaystyle \sum_{\rho} li(n^\rho) + E(n) =$

$\displaystyle - \frac{1}{2}(\int_{1}^n \int_{1}^{\frac{n}{x}} dy dx - (\sum_{j=2}^n \frac{n}{j} - 1) + \sum_{j=2}^n ${$\frac{n}{j}$})
$\displaystyle+ \frac{1}{3}(\int_{1}^n \int_{1}^{\frac{n}{j}}\int_{1}^{\frac{n}{x y}} dz dy dx - (\sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}\frac{n}{j k} - 1) + \sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}${$\frac{n}{j k}$})
$\displaystyle- \frac{1}{4}(\int_{1}^n \int_{1}^{\frac{n}{j}}\int_{1}^{\frac{n}{x y}}\int_{1}^{\frac{n}{x y z }} dw dz dy dx - (\sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}\sum_{l=2}^{\lfloor\frac{n}{j k}\rfloor}\frac{n}{jkl}-1) + \sum_{j=2}^n \sum_{k=2}^{\lfloor\frac{n}{j}\rfloor}\sum_{l=2}^{\lfloor\frac{n}{j k}\rfloor}${$ \frac{n}{jkl} $})
$ \displaystyle +\frac{1}{5}...$

If you sum up just the terms that look like $\sum_{j=2}^n \frac{n}{j} - 1$, you get a smooth curve that bears a strong resemblance to the Logarithmic Integral - you can see part of it here. I'm very curious how to approximate these terms, and what relationship they bear to the logarithmic integral. So that's another question of mine.

Finally, if you sum up just the fractional part sums in (5), you get this function. At least empirically, it appears that all the discontinuities of $\sum_\rho li(n^\rho)$ are confined to just these terms. All of which leads to my final question - are there any interesting tools or approaches that can be applied to these fractional part sums to make any interesting observations?

I hope this question isn't too vague or broad for MO.

  • $\begingroup$ A quick comment: In the $k^{th}$ term, the integral represent the volume under the $k$-dimensional hyperbola $x_1\cdots x_k\leq n$ provided $x_1,\cdots x_n\geq1 $. On the other hand, the sum in the $k^{th}$ term represents the number of integer points under the same $k$-dimensional hyperbola. $\endgroup$ Commented Dec 10, 2011 at 6:53
  • $\begingroup$ That's exactly right, Eric. In fact, each of those terms is clearly related to (though slightly different from) the divisor problem of degree k. On the other hand, the differences on each line are far from being uncorrelated with each other, and any really strong idea about those terms ought to take that into account somehow... or so I remain convinced, anyway. $\endgroup$ Commented Dec 10, 2011 at 8:49

1 Answer 1


Your above identity stems from $$\text{li(x)}-\Pi(x)+\text{small}=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \log \left((s-1)\zeta(s)\right)\frac{x^s}{s}ds,$$ and a Taylor expansion of the logarithm. What follows is not an exact answer to your question, it is not clear what can or cannot be done with a particular identity. Instead, we give an alternate derivation which lives more in the realm of Dirichlet series and contour integrals, but I think it will shed some light upon the problem. The identity you gave above is essentially an expansion of the logarithm in the classical identity above.

Notation: Let $\Pi(x)=\sum_{n\leq x}\frac{\Lambda(n)}{\log n}$ denote Riemann's Pi function, that is $$\Pi(x)=\pi(n)+\frac{1}{2}\pi\left(n^{\frac{1}{2}}\right)+\frac{1}{3}\pi\left(n^{\frac{1}{3}}\right)+\cdots,$$ and define $$H_{k}(x):=\sum_{j_{1}=2}^{x}\sum_{j_{2}=2}^{\lfloor\frac{x}{j_{1}}\rfloor}\cdots\sum_{j_{k}=2}^{\lfloor\frac{x}{j_{1}\cdots j_{k-1}}\rfloor}1$$ to be the number of integer points under hyperbola with entries greater than $2$, and let $$I_{k}(x)=\int_{1}^{x}\int_{1}^{\frac{x}{y_{1}}}\cdots\int_{1}^{\frac{x}{y_{1}\cdots y_{k-1}}}1\text{d}y_{1}\cdots\text{d}y_{k}$$ be the same area when integrated.

Lets begin by looking at the generalized divisor problem. Using Perrons formula, for any $a>1$ we have that $$D_{k}(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\zeta(s)^{k}\frac{x^{s}}{s}ds,\ \ \ \ \ \ \ \ \ \ (1)$$ where $D_{k}(x)$ is the sum of the generalized divisor function. $D_{k}(n)$ is exactly the number of integer points under the $k$-dimensional hyperbola $x_{1}\cdots x_{k}=n,$ but our sums start at $2$ instead of $1$ so we need to modify things slightly. To get the sum of the integer points whose smallest entry is larger than $2,$ we have to subtract away the $k$ different $(k-1)$-dimensional hyperbolas, and look at $D_{k}(n)-kD_{k-1}(n).$ However this overcompensates, and we have to add back in the $\binom{k}{2}$ different $(k-2)$-dimensional hyperbolas. Continuing in this way, we see that

$$\sum_{j=0}^{k}\binom{k}{j}(-1)^{j}D_{k-j}(n)=H_{k}(n) \ \ \ \ \ \ \ \ \ \ (2)$$

and hence equation (1) and (2) together imply that $$H_{k}(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\left(\zeta(s)-1\right)^{k}\frac{x^{s}}{s}ds. \ \ \ \ \ \ \ \ \ \ (3)$$

Similarly, in your note you proved that $$I_k(x)=x\sum_{j=1}^{k}\frac{\left(\log x\right)^{k-j}}{(k-j)!}(-1)^{j},$$ and noticing the similarities in expansions, we may rewrite this as $$I_k(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \frac{x^s}{s} \frac{1}{(s-1)^k}ds.\ \ \ \ \ \ \ \ \ \(4)$$

Using (3) and (4), it follows the individual terms are $$\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \frac{x^s}{s} \left((\zeta(s)-1)^k-\frac{1}{(s-1)^k}\right)ds.$$ Summing over $k$, and using absolute convergence to switch orders, we have that $$\sum_{k=1}^\infty \frac{(-1)^k}{k}\left(H_k(x)-I_k(x)\right)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\sum_{k=1}^\infty \frac{(-1)^k}{k}(\zeta(s)-1)^k \frac{x^s}{s}ds+$$ $$\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\sum_{k=1}^\infty \frac{(-1)^k}{k}(s-1)^{-k} \frac{x^s}{s}ds.$$

Removing the series expansion for the logarithm, this is

$$=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\left(-\log\zeta(s)\right)\frac{x^{s}}{s}ds+\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}-\log\left(\frac{s-1}{s}\right)\frac{x^{s}}{s}ds.$$ And using Perrons formula once again, since $$-\log\zeta(s)=\sum_{k}\frac{\Lambda(n)}{\log n}n^{-s},$$ we have shown that $$\sum_{k=1}^\infty \frac{(-1)^k}{k}H_k(x)=\Pi(x),$$ and on the other hand the integral $$\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \log(s-1)\frac{x^s}{s} ds$$ gives rise to the $\text{li}(x)$ term.

  • $\begingroup$ Eric: Thanks for writing this up - I think it locates what I'm talking about quite nicely. It's also made me realize I likely need to better specify my question. Your equation (2) actually locates the core of my question, regarding techniques I might not be familiar with. I'm curious if there are transformations or re-arrangements to what you label $H_k(n)$ that could say anything novel about the error term. As you say in (2), it can be expressed in terms of the much better studied $D_k(n)$. (cont...) $\endgroup$ Commented Jun 6, 2012 at 7:11
  • $\begingroup$ So, for example, $D_k(n)$ can be expressed as residues, as per books.google.com/books?id=jT9gjGipNDUC&pg=PA352 . (When I tried taking the principal terms for $H_k(n)$ and using them as an approximation in the left side of my (1), I was just left with the logarithmic integral). $D_2(n)$ can also be expressed with the Voronoi summation formula, as per books.google.com/books?id=jT9gjGipNDUC&pg=PA83 . I haven't been able to track down if there are comparable formulas for $D_k(n)$ (which would immediately yields expressions for $H_k(n)$). (cont...) $\endgroup$ Commented Jun 6, 2012 at 7:20
  • $\begingroup$ Obviously my Extra section is another such idea for $H_k(n)$. Additionally, $D_k(n)$ and $H_k(n)$ can be expressed with generalizations of the Dirichlet Hyperbola method. If you look at mathoverflow.net/questions/97694/…, equation (4) from that page one way of writing that generalization. On that page, $D_{2,2}(n)$ is your $H_2(n)$, $D_{3,2}(n)$ is your $H_3(n)$, and so on. I'm still trying to figure out if using those equations in my (4) above leads anywhere interesting. $\endgroup$ Commented Jun 6, 2012 at 7:31
  • $\begingroup$ That exhausts my ideas, I think. So that's the core of my "other techniques" question - 1) are there other ways of expressing $H_k(n)$ (or $D_k(n)$) that lead to any interesting observations in my (4)? And particularly, are there any clever ideas for combining any of those alternative expressions with symmetries between, say, $H_2(n)$ and $H_3(n)$ and $H_4(n)$ and so on, which all jump in ways that share some connections? $\endgroup$ Commented Jun 6, 2012 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.