Computing a Number Theoretic Sum

Published Jan 4, 2025

While I was attempting this problem, I misread it after writing it down on paper and instead solved

S = \sum_{xy \leq n} xy \gcd(x, y)

Here the sum is over positive integers $(x, y)$ satisfying $xy \leq n$ , rather than $x, y \leq n$ . In my opinion it turned out more interesting than the original one, so I wanted to share.

Compute $S = \sum_{xy \leq n} xy \gcd(x, y)$ in $\mathcal{O}(\sqrt{n} \log n)$ .

—Source: Accidental misread

Solution

Setting up notation first, let $M$ be set of multiplicative functions, and * be the Dirichlet product, then $(M, *)$ is an abelian group. Let $I$ , $\tau$ , $\phi$ be the identity, divisor count, divisor sum, Mobius, and totient functions respectively. Note that they are all multiplicative.

Write $k = xy$ so that we can iterate over $k$ as follows:

S = \sum_{k \leq n} k \sum_{d \mid k} \gcd(d, k/d)

Key Lemma $\sum_{d^2 \mid k} \tau(k/d^2) \phi(d) = \sum_{d \mid k} \gcd(d, k/d)$
Note here that $d$ does not represent the same iterator, but I kept the variable name anyways.

Proof of Lemma. A cool fact is that any sum of a product of multiplicative functions with the form of the left side is multiplicative. We can define here

f(d^2) = \begin{cases} 0 & \text{$d$ is not a square} \\ \phi(d) & \text{otherwise} \end{cases}

Note that $f$ is multiplicative, and the left side is actually $f * \tau$ , making it multiplicative.

We can verify the right side is multiplicative too, with just the textbook approach. One can notice that if $\gcd(p, q) = 1$ , $d \mid pq \implies d = rs$ , where $r \mid p$ and $s \mid q$ . Also, $\gcd(rs, pq/(rs)) = \gcd(r, p/r) \gcd(s, q/s)$ . Therefore,

\sum_{d \mid pq} \gcd(d, pq/d) = \sum_{r \mid p} \gcd(r, p/r) \sum_{s \mid q} \gcd(s, q/s)

It remains to simply check both sides coincide at prime powers:

\sum_{i \leq \lfloor a/2\rfloor} \tau(p^{a - 2i}) \phi(p^i) = \tau(p^a) + \sum_{1 \leq i \leq \lfloor a/2\rfloor} (a - 2i + 1) p^{i - 1}(p - 1)

= \sum_{i \leq \lfloor a/2\rfloor - 1} 2p^i + (a - 2\lfloor a/2\rfloor + 1) p^{\lfloor a/2\rfloor} = \sum_{i \leq a} p^{\min(i, a - i)}

So we’re done. The sum telescopes in the middle. $\square$

Therefore

S = \sum_{k \leq n} k \sum_{d^2 \mid k} \tau(k/d^2) \phi(d)

The goal here was to turn the sum into one consisting of multiplicative functions, so we can try applying Dirichlet’s Hyperbola Method. We can quickly make the observation $d^2 \leq k \leq n$ , and it looks promising to try iterating over $d \leq \sqrt{n}$ instead:

S = \sum_{d \leq \sqrt{n}} \phi(d) \sum_{d^2 \mid k} k \tau(k/d^2)

Now $k$ has a really simple characterization: it is just $d^2 \alpha$ for $\alpha \leq n/d^2$ . Let’s iterate over $\alpha$ ,

S = \sum_{d \leq \sqrt{n}} \phi(d) d^2 \sum_{\alpha \leq n/d^2} \alpha \tau(\alpha)

So we would be happy if we can compute partial sums of $I \tau$ quickly, luckily it is multiplicative and simple enough, so let’s try to write it as a Dirichlet product:

I\tau = I * I

Using the Hyperbola Method on partial sums of $I \tau$ , choose splitting point $pq = s$ :

\sum^s I\tau = \sum^{p} i \sum^{s/i} j + \sum^{q} i \sum^{s/i} j -\sum^{q} i \sum^{p} j

Of course, partial sums of $I$ is an $\mathcal{O}(1)$ calculation, we can optimally choose $p = q = \sqrt{n}$ , making the $I\tau$ calculation $\mathcal{O}(\sqrt{n})$ .

Now to resolve

S = \sum_{d \leq \sqrt{n}} \phi(d) d^2 \sum_{\alpha \leq n/d^2} \alpha \tau(\alpha)

We can linear sieve the first $\sqrt{n}$ values of $\phi$ in the $S$ sum at no additional symptotic cost. Thus the total time complexity is

\sum_{d \leq \sqrt{n}} \sqrt{\frac{n}{d^2}} = \Theta(\sqrt{n} \log n)

$\blacksquare$