Just to be clear, we are now on our helper function experiment number two of five, right?
Exactly. And once we're done, variants dealing with approximating the weighted count of prime powers will come after that; they're a bit more challenging but I think they're pretty fascinating. But yes, now I want to explore another slight modification to the basic recursive prime counting function and see what the change does.
Fine.
Again, I'll restate the basic definition.
And its graph looks like this.
Now, let me introduce a different, new helper function.
Go ahead.
The one I'll use here is the count of divisors function, $d(n)$.
What does that do?
Well, you can think of $d(n)$ as the count of solutions to $a \cdot b = n$. And here, order matters, and both $a$ and $b$ are positive whole numbers. Which is to say,
That is one jagged, jumpy function. It must be a pain to work with or make predictions about.
That is indeed true.
I have a hard time imagining it can be used for anything particularly predictable.
Yeah, I understand the sentiment. It's probably quite a surprise, then, how simple its impact actually is as a helper function.
Suppose I define a new function using $d(n)$ as, $g_k(n, j)$
If you graph $g_1(n, 2)$ and compare it to the original function, $f_1(n, 2)$, you'll see this:
Huh. It's just doubled, right? Hard to get simpler than that...
Right. As appearances strongly suggest, $g_1(n,2)$ also only changes values at prime powers. Look closely, and you should see that
$$g_1(n,2)= 2 \cdot \sum_{p^k \le n} \frac{1}{k}$$Which is to say, $g_1(n, 2)$ just computes twice the original function $f_1(n, 2)$.
$$g_1(n,2)= \rr{2 \cdot} f_1(n,2)$$That does seem to be about as simple a helper function as you could want. I must admit that's surprising.
As usual, I hope the following animation helps show this in action.
Well, wait, though. The statement $g_1(n,2)= \rr{2 \cdot} f_1(n,2)$ is making me inordinately curious. Is there a way to generalize $d(n)$ to get constants other than $\rr{2}$?
Yeah, that $2$ is one of those details that raises immediate flags, isn't it?
And the answer to that question is, of course!
Interesting. How?
Well, let's start by rewriting $d(n)$ slightly as $d_2(n)$
Okay.
Then this style of counting can be extended for whole number subscripts as $$\displaystyle d_3(n) = \sum_{a \cdot b \cdot c = n} 1$$ $$\displaystyle d_4(n) = \sum_{a \cdot b \cdot c \cdot d = n} 1$$ and so on.
Okay. That pattern seems clear enough.
But we can go much further than that, if we're willing to abandon combinatorial intuition.
How so?
Well, suppose we decompose $n$ into its prime factorization as $ n = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdot \dots {p_k}^{a_k} $.
Okay.
Then using that factorization, $d(n)$ can be generalized to any complex subscript $z$ as
So $d_z(n)$ is entirely determined by the powers in the prime factorization of $n$?
Right. This definition is enough to show that $d_z(n)$ is a multiplicative function. It's an interesting function in its own right; I rarely see it in the wild, but Aleksander Ivic covers it in section 14.6 of his The Riemann Zeta-Function: Theory and Applications.
And I suppose we can just use this as a new helper function?
Indeed. Put $d_z(n)$ to use in the recursive prime counting function as
And then we can immediately explore different values of $z$.
Are there any particularly noteworthy values for $z$?
Well, for example, $d_3(n)$ looks like this
That seems even more jagged and erratic than $d(n)$.
That's true. And yet graph $g_1(n,2)$ when $z=3$ like so
and sure enough, you'll see that it's true that
$$g_1(n,2)= \rr{3 \cdot} f_1(n,2)$$Yeah, so it seems. The scaling constant changed exactly as hoped.
Right. You can watch this idea in action like so:
This style of exploration works as expected for any $z$ we might try, which is nice.
Okay. Are there any other values of $z$ of special note, though?
Well, yes. There is one special value of $z$ that does deserve attention, namely, $z=-1$.
This also looks pretty erratic, but... Is the range of this function limited to values of 1, -1, or 0?
Yes. As a matter of fact, this function proves important enough to warrant its own name and notation in number theory. It's called the Möbius function, denoted $\mu(n)$. It shows up organically in certain important combinatorial contexts.
Anyway, if you use it in $g_1(n,2)$, the following results
And so for this one, it looks like it produces a mirror image.
Right. The count of primes is reflected across the y-axis, so here $$g_1(n,2)= \rr{-1 \cdot} f_1(n,2)$$
And so this approach would look like this:
Anyway, more broadly, with $d_z(n)$,
$$g_1(n,2)= z \cdot \sum_{p^k \le n} \frac{1}{k}$$and
$$g_1(n,2)= \rr{z \cdot} f_1(n,2)$$Got it.
I imagine you can show how these ideas are connected to the Riemann zeta function, next?
Indeed. Introduce a scaling factor $j^{-s}$ to the recursive definition.
Then apply the recursive definition repeatedly until it has been entirely unrolled.
So basically like the previous examples, then.
If you select a suitable value of $s$, you'll find the following limits as $n$ goes to infinity...
$$2 \cdot \log \zeta(s) = \sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} (\zeta(s)^2-1)^k$$ $$z \cdot \log \zeta(s) = \sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} (\zeta(s)^z-1)^k$$Is that actually right?
Well, sort of.
What do you mean?
The above limits can be made to make sense. But the second, more general example does raise some thorny issues.
When raising complex numbers to complex powers - which $\zeta(s)^z$ does - you get a multivalued complex function with infinitely many values.
Oh.
This situation isn't uncommon in complex analysis. But it introduces questions about branch cuts or Riemann surfaces that are definitely beyond the scope of what I want to cover here. So forgive me for hand waving over it.
Fair enough.
At any rate, hopefully this is a suggestive enough demonstration that $d_z(n)$ stretches out this style of weighted prime counting function. So let me move on to another variant.
I have to admit, despite what you just worked through, it's surprising that $d_z(n)$ had such a simple impact on the weighted count of prime powers... It just seems like such a spiky, unpredictable function.
Well, fine. Let me pause the general sweep of our investigations here for a moment, because I think $d_z(n)$ and its connections to primes warrants a bit more attention. So watch this.
Let me rewrite it as $$d_z(n)= \prod_{p^a | n} (\frac{z}{1}) \cdot (\frac{z+1}{2}) ... \cdot (\frac{z+a-1}{a})$$
And what's so interesting about that?
Well, we just generalized the $z$ parameter to complex values, right? Can you think of anything useful about that generalization?
I guess that lets us take limits with $z$, right?
Exactly. I said I would mostly avoid calculus, but here it proves insightful for not too much effort. And doing so will show a really natural relationship between counts of divisors and primes.
Okay. So what is that relationship?
Well, the idea goes like this. For any fixed whole number $n$, $d_z(n)$ will be a straightforward polynomial. Can you list out some of those polynomials for cases where $n$ has only one prime factor? And try expanding the product out.
Sure, that's not too hard. Let's see, we'd have $$d_z(p)=\rr{z}$$ $$d_z(p^2)=\frac{z^2}{2}+\frac{\rr{z}}{2}$$ $$d_z(p^3)=\frac{z^3}{6}+\frac{z^2}{2}+\frac{\rr{z}}{3}$$ $$d_z(p^4)=\frac{z^4}{24}+\frac{z^3}{4}+\frac{11 z^2}{24}+\frac{\rr{z}}{4}$$ and so on.
Good. Now, if you look at the above definition for $d_z(n)$, it is clearly a multiplicative function.
Multiplicative function?
Well, suppose we have some number $n$ whose prime factorization is $p_1^{\alpha_1} \cdot p_1^{\alpha_k} \cdot ... p_k^{\alpha_k}$. Then $$\begin{aligned} \rr{d_z}(n) &= \rr{d_z}(p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot ... p_k^{\alpha_k}) \\ &= \rr{d_z}(p_1^{\alpha_1}) \cdot \rr{d_z}( p_2^{\alpha_2}) \cdot ... \cdot \rr{d_z}( p_k^{\alpha_k} )\end{aligned}$$
Oh, I see. You mean you can split the function up by its prime factors into a product of multiple functions, essentially.
Right. These observations should be enough to see that when $n$ has one prime factor, $d_z(n)$ is a polynomial whose smallest order term will be $z^1$. And if has more than one prime factor, it's smallest order term will be $z$ to some power $>1$.
Okay, I follow that.
That has important implications. Specifically, because of that, if you take the derivative of $d_z(n)$ with respect to $z$, and then examine $z=0$, the result will be equal to the coefficient of $z^1$, which will thus be zero unless $n$ only has one prime base in its prime factorization.
Oh, I see.
Right. In fact, this result is the weighted prime power function we've been working with. Or, put another way, if $n>1$,
Alternatively, while we're here, we can define $d_z(n)$ as $$d_z(n) = \mathbf{1}_{n=1}+\binom{z}{1} \sum_{\substack{ j = n \\ j_1 > 1}} 1 + \binom{z}{2} \sum_{\substack{ j_1 \cdot j_2 = n \\ j > 1}} 1 + \binom{z}{3} \sum_{\substack{ j_1 \cdot j_2 \cdot j_3 = n \\ j > 1}} 1 + ...$$ And then if we take its derivative with respect to $z$ at $z=0$, we also arrive at $$\frac{\Lambda(n)}{\log n} = \sum_{\substack{ j = n \\ j_1 > 1}} 1 - \frac{1}{2} \sum_{\substack{ j_1 \cdot j_2 = n \\ j > 1}} 1 + \frac{1}{3} \sum_{\substack{ j_1 \cdot j_2 \cdot j_3 = n \\ j > 1}} 1 - ...$$
Oh! And isn't that just a variant of the recursive form we've been working with this entire time?
It is indeed. So, as I say, the connection is deeply natural.
Anyway, that's more than enough of this digression, but I do think this connection is quite lovely and makes the connection between $d_z(n)$ and primes very clear.