For this entire series of discussions, we've relied on one specific form of recursive function.
That's been true, yes.
I foregrounded it in the hopes its simplicity would keep the variations we explored front and center. I like that they're so easy to implement and tweak in most programming languages. And purely at the level of notation, these definitions barely introduce any extraneous symbols to distract from our main focus.
I think that's fair to say, sure.
So that's been useful. Despite that, though, the recursive form we've worked with presents an issue that I want to acknowledge.
What is that?
Well, the core ideas we've been exploring have some key symmetries that are ever present, and those symmetries can be really significant. But the specific recursive style of identity we've explored, convenient though it may be, stomps all over those symmetries.
Oh.
With that in mind, I do want to introduce a few other recursive forms, ones that capture some of that symmetrical structure, and in way that aren't too much more complicated.
Expressing Certain Symmetries
What are these new forms? How do they compare to the original form we've been using so much, $$\displaystyle f_k(n,j) = \begin{cases} \frac{1}{k} - f_{k+1}(\frac{n}{j}, 2) + f_k(n,j+1) & n \ge j \\ 0 & \textrm{ otherwise } \end{cases}$$
Well, the first alternative works like so. Introduce the following helper function.
$$\displaystyle \theta(m,k) = \begin{cases} 0 & m = 0, k = 0 \\ \frac{(-1)^{k+1}}{k} & m = 0, k \ne 0 \\ \binom{m}{k} & \textrm{otherwise} \end{cases}$$With that, we can now define a new function that looks like this:
$$f_m(n,j)=\begin{cases} \displaystyle\sum_{k=0}^{\lfloor \log_j n \rfloor} \theta(m,k) \cdot f_{m-k}(\frac{n}{j^k}, j+1) & n \ge j \\ \mathbb{1}_{m \ne 0} & \textrm{ otherwise } \end{cases}$$And now we can express our weighted prime counting function as $$\Pi(n) = f_0(n,2)$$ That's it.
And now's probably a good time to remind that all the JavaScript code here is live in the web browser; if you tap F12 to bring up your debugging console, you can run this code like so:
This might be especially useful for the following examples, where implementations of new approaches will be paired with implementations of their original approaches. Definitely feel free to experiment with it, to see if working.
How This Form Differs
Okay, fine. But why should we pay attention to this new way of writing our ideas?
Well, conceptually here we are rearranging what we count to emphasize certain symmetries.
So what does that mean?
In our original recursive form, we had two references to the function we were working with, right?
Right. We had one reference to $f_{k}(n, \rr{j+1})$, and we also have a reference to $f_{k+1}(\frac{n}{j}, \rr{2})$
Exactly right. So what do we have here, by contrast?
Well here, in our new function, we apparently have a $f_{m-k}(\frac{n}{j^k}, \rr{j+1})$ term, which almost seems like a combination of the two. But that's it. And we specifically don't have a function reference that starts over counting with $2$. What does this all mean?
Here's the conceptual difference. In our original style of counting, if we were counting solutions of the form $a \cdot b \cdot c \cdot ...$, say, we were essentially enumerating all possible values of $a$, then $b$, then $c$, and so on, without paying any attention to how they related to one another.
And that's what the $2$ meant, then. We were moving on to the next term.
Exactly. Here, by contrast, we are dealing, all at once, with every case where any of the terms equal $2$. And then we move on to any case where any terms equal $3$, and so on, constantly incrementing. And we take advantage of combinatorial properties along the way to do this, to capture the fact that there is a great deal of repetition.
Which must be why binomial coefficients show up in our helper function, I take it. It's expressing some combinatorial symmetries. I follow that, I suppose, but that $\theta(m,k)$ coefficient still sticks out as an odd function...
Well, let me try to clarify that and describe this all from a slightly different angle, because the following idea will be more broadly useful anyway.
Revisiting $D_z(n)$
Do you recall, back in this discussion, I defined the generalized divisor summatory function $D_z(n)$?
Right; we worked through an aside showing $\displaystyle \lim_{z \to 0} \frac{\partial}{\partial z} D_z = \Pi(n)$. So there is a deeply natural relationship between $D_z(n)$ and $\Pi(n)$.
And as a matter of fact, you can also express that as $\displaystyle \lim_{z \to 0} \frac{D_z(n)-1}{z} = \Pi(n)$ as well, which amounts to the same thing.
Fine. So what do we gain by looking at $D_z(n)$ instead?
Well, in many cases, definitions for $D_z(n)$ are slightly more straightforward, that's all. And then we can produce related, slightly messier definitions for $\Pi(n)$ from them.
In our original approach, $D_z(n)$ could be rewritten explicitly as: $$D_z(n) = 1+\binom{z}{1}\sum_{\substack{ j \le n \\ j \ge 2}} 1 + \binom{z}{2} \sum_{\substack{ j_1 \cdot j_2 \le n \\ j \ge 2}} 1 + \binom{z}{3} \sum_{\substack{ j_1 \cdot j_2 \cdot j_3 \le n \\ j \ge 2}} 1 + ...$$
Or, in the recursive style of function used since the beginning of these dialogues, as
$$f_k(n,j)=\begin{cases} \displaystyle \frac{z+1-k}{k} \cdot (1+f_{k+1}(\frac{n}{j},2)) + f_k(n,j+1) & n \ge j \\ 0 & \textrm{otherwise} \end{cases}$$And so here, $D_z(n) = 1+f(n)$.
Okay. And so if we take the derivative with respect to $z$ of that idea at $z=0$, we do get our weighted count of prime powers identity.
Right. But that approach certainly isn't the only way to express $D_z(n)$. $D_z(n)$ is all about counting, and there are lots and lots of ideas we might turn to in the service of counting.
In fact, here's an alternate identity that is likewise really important and isn't, I think, any less natural than that previous identity: $$D_z(n) = \sum_{2^{k_2} \cdot 3^{k_3} \cdot 4^{k_4} \cdot 5^{k_5} \cdot ... \le n } \binom{z}{k_2} \cdot \binom{z-k_2}{k_3} \cdot \binom{z-k_2-k_3}{k_4} \cdot \binom{z-k_2-k_3-k_4}{k_5} \cdot ...$$ And here, any $k$ is a whole number $ \ge 0$.
We can rewrite this idea slightly using the notation of multinomial coefficients, perhaps stressing even more clearly how natural this idea is. If we define $k_a=k_2+k_3+k_4+k_5+...$, then this definition can be rewritten as $$D_z(n) = \sum_{2^{k_2} \cdot 3^{k_3} \cdot 4^{k_4} \cdot 5^{k_5} \cdot ... \le n } \binom{z}{z-k_a, k_2, k_3, k_4, k_5, ...}$$ For the sake of easy computation, this core idea can be rewritten recursively, and tidily I think, as
$$f_m(n,j)=\begin{cases} \displaystyle\sum_{k=0}^{\lfloor \log_j n \rfloor} \binom{m}{k} \cdot f_{m-k}(\frac{n}{j^k}, j+1) & n \ge j \\ 1 & \textrm{otherwise} \end{cases}$$And then here, we can thus say that $D_z(n) = f_z(n,2)$.
Okay, that does seem interesting, and it doesn't strike me as obviously unnatural or anything. The presence of the multinomial coefficient highlights that we're now expressing certain combinatorial properties, which does seem interesting. And so if we take the derivative of that idea with respect to $z$ of that at $z=0$, we also get our weighted count of prime powers $\Pi(n)$?
Exactly. And you can indeed extract our new recursive definition, the one we started with, from this identity. But the process of applying the derivative with respect to $z$ at $z=0$ does tend to muddy up the recursive definition a bit more, hence the awkwardness of that $\theta(m,k)$ definition.
As a small aside before I introduce the other major form, there is yet another related identity for $D_z(n)$ that I want to draw attention to here, $$D_z(n) = \sum_{2^{k_2} \cdot 3^{k_3} \cdot 5^{k_5} \cdot 7^{k_7} \cdot ... \le n } \binom{z+k_2-1}{k_2} \cdot \binom{z+k_3-1}{k_3} \cdot \binom{z+k_5-1}{k_5} \cdot \binom{z+k_7-1}{k_7} \cdot ...$$ which can be rewritten for easier computation as
$$f(n,j)=\begin{cases} \displaystyle\sum_{k=0}^{\lfloor \log_{p_j} n \rfloor} \binom{z+k-1}{k} \cdot f(\frac{n}{(p_j)^k}, j+1) & n \ge p_j \\ 1 & \textrm{otherwise} \end{cases}$$And so here, $D_z(n) = f(n,0)$.
That is interesting... It actually looks really quite similar, except the definition relies on primes rather than whole numbers $ \ge 2$.
That's true.
So why the interest in drawing attention to this last definition?
This last definition is, in fact, a discrete convolution variant of a really core number theory concept, Euler products, that's all. So that warrants making the connection, I think. It's actually something like a restatement of the fundamental theorem of arithmetic, relying on the fact that all numbers have unique prime factorizations. So its conceptual, and even visual, similarity to the previous definition we just started working with is perhaps satisfying and intriguing in its own right. But I'm already biting off more than I can chew here, so enough about that aside, I suppose.
The Point of All This, and the Other Form
Okay, fine. This is all quite the digression. But let's return to this new recursive definition, the one that works with whole numbers, that we started this section with. What is the value of expressing these symmetries explicitly in this way, then? Why are we putting in this extra effort?
Well, if you are rather clever about it, these symmetries can be useful for more efficient computation, with some work. And likewise, it's possible these symmetries might also be harnessed for questions of approximating the count of primes in interesting ways as well. I know I'm not doing a great job in making the connection clear here, but the broad idea is essentially a generalization of the same one employed by the Dirichlet hyperbola method, only here in this context of weighted prime counting functions.
Okay.
So that's the value of noting this approach. Along those lines, though, I said that I had more than one general form that deals with this symmetry that I was interested in here.
You did, yes.
Good. Well, there's actually a few variants of this idea, but here's the other main one I want to note. And it starts with a different conceptual idea.
If you really think about it, when trying to compute $D_z(n)$ or $\Pi(n)$, we've often been faced with the task of counting solutions to questions like $ j_1 \cdot j_2 \cdot j_3 \cdot ... \le n$, where any $j$ is $>1$ or $>0$, depending on the context, right?
That sounds right, yes.
Well, we want to think harder about what that it is we're actually doing here, because there is a huge amount of redundancy in that style of counting. To take advantage of that, now we'll change how we count just a bit. We'll add the extra constraint that any value $j_{k} \ge j_{k+1}$ to reduce the solutions we manually count over. And then we'll turn to combinatorics to recover the actual, correct count.
I guess I get the concept, but can you be more specific?
Sure. Putting this idea into practice, our new way of computing $D_z(n)$ will be as $$D_z(n) = \sum_{\substack{ j_1 \cdot j_2 \cdot j_3 \cdot j_4 \cdot ... \le n \\ j_1 \ge j_2 \ge j_3 \ge ... \\ j > 0 } } f(j_1, j_2, j_3, ...)$$ where $f(j)$ is a combinatorial helper function I'll describe in a second. The bounds of the sum is really the core idea here, though. We really narrowed down the solutions we are counting over.
...Okay. Right, I think I see that. But what is that helper function, $f(j)$?
Well, this might sound a little confusing, but bear with me. Suppose $j$ is some array of integer values sorted from highest to lowest, and the array discards any elements that equal $1$. Then if $k$ is the length of the array $j$, and $k_i$ is the multiplicity (number of occurrences) of the $i$-th distinct value in $j$, then $$f(j) = \binom{z}{k} \cdot \binom{k}{k_1, k_2, k_3, ...} $$
Ah - so once again, we encounter the multinomial coefficient in this context.
Exactly so. In fact, this approach is closely related to the other form we started with, above. Still, if the above definition seems daunting and perhaps wordy, the actual recursive implementation of the idea here, as code, is surprisingly tidy, and it quite resembles the very original recursive definition we've already spent so much time working with. So we can implement this as
$$f_k(n, j, c, r) = \begin{cases} \frac{z+1-k}{1+(r-1) \cdot \mathbb{1}_{j=c}} \cdot \left(1 + f_{k+1}\left(\frac{n}{j}, 2, j, 2+(r-1) \cdot \mathbb{1}_{j=c} \right)\right) + f_k(n, j+1, c, r) & n \geq j \textrm{ and } c \geq j \\ 0 & \text{ otherwise } \end{cases}$$And with this definition, we can say $D_z(n) = 1 + f_1( n,2,n,1 )$.
Okay. That takes care of computing $D_z(n)$. What about the weighted count of primes, though?
Well, if we take the derivative of that with respect to $z$ at $z=0$, we will finally be left with
$$f_k(n, j, c, r) = \begin{cases}\frac{1-k+\mathbb{1}_{k=1}}{1+(r-1) \cdot \mathbb{1}_{j=c}} \cdot \left(1 + f_{k+1}\left(\frac{n}{j}, 2, j, 2+(r-1) \cdot \mathbb{1}_{j=c}\right)\right) + f_k(n, j+1, c, r) & n \geq j \textrm{ and } c \geq j \\ 0 & \text{ otherwise } \end{cases}$$And with this definition, our weighted count of prime powers is $\Pi(n) = f_1( n,2,n,1 )$.
As usual, we can animate this. So if we do, it will look like so.
For a sense of how much redundancies are pruned here, each of these nodes is quite literally displaying how many corresponding nodes they would have taken up in our original method of counting. The more composite a number is, the more redundancies are eliminated, so this gets much more significant as the numbers grows larger. I hope that's clear enough to follow.
Well... it is enough, I think. Certainly the code seems to produce expected results at any rate.
Good. For the rest of this discussion, I mostly just want to show how these ideas can be applied to some of our more interesting prime counting variations.