Well, wait, I have a question.
What's that?
So far, we keep looking at variations of functions that provide a weighted count of prime powers. But it seems like it would make more sense to use a function that just counted the primes themselves, wouldn't it?
Well, as a matter of fact, you can count raw primes with a similar identity, if you really put your mind to it. And it is interesting in its own right. But it turns out it's much less straightforward. I'll turn to it now.
Okay.
By the end of this, I bet you'll see why we use the weighted prime power function, though.
So, as usual, I'll return to the baseline function, $f_k(n,j):$
And so, of course, $f_1(n, 2)$ is
Right.
I imagine you'll introduce yet another helper function now.
I will. The helper function, which I'll arbitrarily call $h(n)$, is not at all a standard function.
So start by decomposing $n$ into its prime factorization as $ n = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdot \dots {p_k}^{a_k} $.
Okay..
Do that, and we can define $h(n)$ in terms of the prime powers of the factorization of $n$. It looks like this:
$h(n)$ is entirely determined by the powers in the prime factorization of $n$. This definition is enough to show that it is a multiplicative function.
And you say it's not a standard function?
As far as I know, no. If you graph it, it looks like this:
Once again, it looks pretty unpredictable. So the value of the function is bounded by 0 and 1, right?
Yeah, you should be able to see that from the definition, really. Anyway, now I can use $h(n)$ as a helper function inside a new recursive prime counting function like so:
If I compare this new function $g_1(n, 2)$ to the original function $f_1(n, 2)$, I will see this:
So $g_1(n,2)$ does indeed count just primes.
Right. We can in fact say
$$ g_1(n,2)= \sum_{p \le n} 1 = \pi(n) $$I think, as usual, that an animation might help here. You can see the recursive structure stays the same. But now we rely on difficult-to-compute coefficients along the way.
Looking back at that graph, I can see that these two functions end up being quite close to each other. By the time $n$ is around a million, they just differ by a bit less than $100$.
Right. In fact, it's also straightforward to express $f$ in terms of $g$, as
$$ f_1(n,2) = \sum_{k = 1} \frac{1}{k} \cdot g_1(n^\frac{1}{k},2) $$That makes sense.
And then, using a basic combinatorial technique, Möbius inversion, we can express $g$ in terms of $f$ as
$$ g_1(n,2) = f_1(n,2) \rr{- \frac{1}{2} \cdot f_1(n^\frac{1}{2},2)- \frac{1}{3} \cdot f_1(n^\frac{1}{3},2)- \frac{1}{5} \cdot f_1(n^\frac{1}{5},2) + \frac{1}{6} \cdot f_1(n^\frac{1}{6},2)-...} $$or, more generally by using the Möbius function $\mu(n)$, as
$$ g_1(n,2) = f_1(n,2) \rr{+ \sum_{k = 2} \frac{1}{k} \cdot \mu(k) \cdot f_1(n^\frac{1}{k},2)} $$It's this last form, which is very easy to calculate, that means working with $f$, the weighted prime power counting function, is essentially equivalent to working with $g$, the count of primes.
I see. And obviously computing $h(n)$, because it requires factoring $n$, is not easy or convenient. So at least from that perspective, $g$ is much harder to work with than $f$.
Precisely.
In a previous discussion, we worked through a specific connection between the generalized divisor function $d_z(n)$ and our weighted count of prime powers function $\frac{\Lambda(n)}{\log n}$.
Right.
Well, we can use the same mathematical plumbing here to similar results. Suppose we define this other generalized number theory function $h_z(n)$ as
Okay.
If we take the derivative of $h_z(n)$ with respect to $z$ and then examine $z=0$, we will find that
$$$$I won't dwell on this, but if you experiment with these functions, you'll notice that $d_1(n)=1$ for any $n$. That's a really useful property. Whereas $h_z(n)$, at least to appearances, never behaves in easy-to-predict ways.
And that difference suggests why the weighted prime function might be more natural to work with, I guess.
So I guess I follow all this, or I do enough. But I have to say, the origin of the function $h(n)$ seems pretty obscure.
I can see that. But there's actually a straight-forward way to find such functions, at least there is from a computational perspective.
So what is that?
Well, the approach works like this.
Suppose you have some arbitrary function $\theta(n)$, and you want to find a second function $h(n)$ so that, for $$g_k(n,j)=\rec{h(j)\cdot(\frac{1}{k}-g_{k+1}(\frac{n}{j},2)) + g_k (n, j+1)}$$ $$ g_1(n,2) = \sum_{j = 2}^n \theta(j) $$
That's basically the situation we found ourselves in above, right?
Maybe making this more concrete might help.
Okay. In the case we started with, before, $\theta(n)$ is a function equal to $1$ if $n$ is prime, and $0$ otherwise.
To find $h(n)$, we can simply use $\theta(n)$ in the following, related recursive formula, like so:
And viola - we get $h(n)$ out the other side mechanically. This relationship is quite general.
That works? Huh. Well, there's definitely a distinct visual symmetry between the two functions, anyway.
So can you connect all this to the Riemann zeta function in the usual way?
Well, yes... but in this case it's mildly trickier than in previous cases.
Why is that?
Well, we can indeed take our definition above, introduce a scaling factor $j^{-s}$ to the recursive definition, and arrive at
And for a suitable value of $s$, you can take the limit as $n$ goes to infinity, and you will get a convergent limit.
And in fact, that limit will be equal to the Prime zeta function, $P(s)$.
Okay. So what exactly is tricky about that?
Well, the resulting limit, in that form, doesn't actually have an immediate connection to the Riemann zeta function, that's all.
Oh.
But it really is only mildly tricky. Particularly, the Möbius inversion relationship still works. And in fact,
$$\log \zeta(s) = \sum_{k=1}^\infty \frac{1}{k} P(s k)$$And
$$P(s) = \sum_{k=1}^\infty \frac{\mu(k)}{k} \log \zeta(s k)$$So the connection is still somewhat straightforward.
Okay.
Let's move on, then.