A Prime Counting Gallery

With a Function Applied

I don't want to dwell on these techniques too long. So as I say, let me just show how they could be employed by some of the functions we already covered, and then we can move on to the next topic.

Sure.

A lot of the prime counting variations were just our basic form, altered by the introduction of a helper function.

That's right. We explored quite a few examples of that form. Given some arbitrary helper function $\rr{\nu(j)}$, they all took the form $$\displaystyle f_k(n,j) = \begin{cases} \rr{\nu(j)} \cdot( \frac{1}{k} - f_{k+1}(\frac{n}{j}, 2) ) + f_k(n,j+1) & n \ge j \\ 0 & \textrm{ otherwise } \end{cases}$$

Right. Well, here, we can rewrite these generalizations as

And then the value of the function will be computed by $f_0(n,2)$

Or alternatively, we could use our second form and write this as

And in that case, the value of the function is computed by $f_1(n,2,n,1)$

Got it. That's pretty straightforward.

With Varying Sample Sizes

We also experimented with changing the sample size of the recursive formula as a way to connect the logarithmic integral to our weighed prime power counting function.

Right. We expressed that as $$\displaystyle f_k(n,j) = \begin{cases} \rr{d} \cdot( \frac{1}{k} - f_{k+1}(\frac{n}{j}, \rr{1+d}) ) + f_k(n,j+\rr{d}) & n \ge j \\ 0 & \textrm{ otherwise } \end{cases}$$

Exactly so. Well here, we can also express that idea this way, too.

If we do that, then we can express our weighted count of prime powers as $$\lim_{d \to 1} f_0(n,1+d) = \Pi(n)$$ and the logarithmic integral $\mathrm{li}(n)$ as $$\lim_{d \to 0} f_0(n,1+d) = \mathrm{li}(n) - \log \log n - \gamma$$

Okay.

And again, if we turn to our second form, we can write this general idea as

Do that, and we can express the weighted count of prime powers as $$\lim_{d \to 1} f_1(n,1+d,n,1) = \Pi(n)$$ and the logarithmic integral $\mathrm{li}(n)$ as $$\lim_{d \to 0} f_1(n,1+d,n,1) = \mathrm{li}(n) - \log \log n - \gamma$$

Pretty fascinating, right?

Wait... wait.

Yes?

You've mentioned before that the difference between $\Pi(n)$ and $\mathrm{li}(n)$ is, let's say, of interest.

Indeed, that is certainly true.

So these forms here apparently express certain symmetries inside both functions. Can they be used somehow to say anything interesting about the size of the difference between $\Pi(n)$ and $\mathrm{li}(n)$, of bounding that difference somehow?

That sounds like an interesting question! You might even be tempted to wonder so, given that the original Dirichlet hyperbola method is used to give exactly that kind of information for the much simpler $D(n)=\sum_{a \cdot b \le n} 1$.

Exactly!

Unfortunately, if I am good at anything at all in the realm of math, it's the sort of thing that is currently going on in these articles. I am decidedly lousy at analysis, and that won't be changing. So let me just register that I find this an interesting question myself...

...but I do want to note one last observation before moving on. I mentioned before that there are a number of roughly equivalent forms that rely on the symmetry we are exploring here.

Right.

I have yet another variant to mention in passing that, I think, might be interesting for this specific context...

So what is that?

Well, let me define a combinatorial helper function first. Suppose $j$ is some array of integer values sorted from lowest to highest (previously, we've worked highest to lowest). And suppose $k_i$ is the multiplicity (number of occurrences) of the $i$-th distinct value in $j$. Then, relying on multinomial coefficients once again, our helper function this time is $$f(j) = \binom{1}{k_1, k_2, k_3, ...}$$

And note especially that if $k_1$, $k_2$, $k_3$, and so on are all totally distinct, which is a very common case, then $f(j) = 1$.

Okay, duly noted. But what is the role for this function?

Well, with that helper function, we can express the following quite striking parallel identities between the weighted count of prime powers and the logarithmic integral...

$$\begin{aligned} \Pi( n ) &= \sum_{\substack{t_1=2}}^n f(t_1) - \frac{2!}{2} \cdot \sum_{\substack{t_1=2}}^{\lfloor n^\frac{1}{2} \rfloor} \sum_{\substack{t_2=t_1}}^{\lfloor \frac{n}{t_1} \rfloor} f(t_1,t_2) +\frac{3!}{3} \cdot \sum_{\substack{t_1=2}}^{\lfloor n^\frac{1}{3} \rfloor} \sum_{\substack{t_2=t_1}}^{\lfloor (\frac{n}{t_1})^\frac{1}{2} \rfloor} \sum_{\substack{t_3=t_2}}^{\lfloor \frac{n}{t_1 \cdot t_2} \rfloor} f(t_1,t_2,t_3)-\frac{4!}{4} \cdot ... \\ \mathrm{li}( n ) - \log \log n - \gamma &= \int_{\substack{1}}^n \, d t_1 - \frac{2!}{2} \cdot \int_{\substack{1}}^{n^\frac{1}{2} } \int_{\substack{t_1}}^{\frac{n}{t_1} } \, d t_2 \, d t_1 +\frac{3!}{3} \cdot \int_{\substack{1}}^{n^\frac{1}{3} } \int_{\substack{t_1}}^{(\frac{n}{t_1})^\frac{1}{2} } \int_{\substack{t_2}}^{ \frac{n}{t_1 \cdot t_2} } \, d t_3 \, d t_2 \, d t_1-\frac{4!}{4} \cdot ... \end{aligned}$$

Pretty fascinating, right? Well, I find it compelling, anyway. If you're curious about this form of the weighted count of prime powers function, I discuss it more here in my discussion about prime counting, where it plays a central role. Okay, let me round things out with one more example.