# The function $g(n)=\sum_{\substack {1\lt k\leq n \\ \gcd(k,n)=1}}d(k-1)$

In 1965 Puliyakot Keshava Menon proved that $${\displaystyle \sum _{\substack {1\leq k\leq n \\ \gcd(k,n)=1}}\gcd(k-1,n)=\varphi (n)d(n)}$$ being $$\varphi(n)$$ the totient function of $$n$$. If we move under summation the function $$d(n)$$ (the function that counts the divisors of $$n$$), that is if we consider the function $${\displaystyle g(n)=\sum _{\substack {1\lt k\leq n \\ \gcd(k,n)=1}}d(k-1)}$$ and analyze its behavior up to $$n=10^6$$, we find that (for $$n\gt35$$) $${\displaystyle 1 \lt \frac {g(n)} {\varphi (n)log(n)} \lt 2}$$ Is there a way to prove the above bounds?

Many thanks.

• What is the value of $d(0)$? Commented Jun 7, 2021 at 20:08
• @saulspatz Thanks. I have corrected the question. Commented Jun 7, 2021 at 20:17
• You may be interested to know (apart from the asymptotics) that there are multi-dimensional generalizations of this identity. I remember proving it using Burnside's lemma somewhere on this site, but the generalizations are equally magnificent to look at, and may pique your interest. Commented Jun 8, 2021 at 23:46

We can actually deduce an asymptotic expression for the sum $$g(n)$$ using some known estimates. I'll present a sketch of the calculation.
First remove the coprimality condition using Mobius inversion: $$g(n) = \sum_{2\leq k\leq n} d(k-1) \sum_{a\mid (k,n)} \mu(a).$$ Inverting the order of summation gives $$g(n) = \sum_{a\mid n} \mu(a) \sum_{\substack{2\leq k\leq n\\ a\mid k}} d(k-1).$$ After a change of variables, the inner sum is $$\sum_{\substack{2\leq k\leq n\\ a\mid k}} d(k-1) = \sum_{\substack{m\leq n\\ m\equiv-1 (\text{mod}\ a)}} d(m).$$ Using a result of Pongsriiam and Vaughn (see this paper, for instance), we have $$\sum_{\substack{m\leq n\\ m\equiv-1 (\text{mod}\ a)}} d(m) = \frac{1}{\phi(a)} \sum_{\substack{1\leq m\leq n\\(n,a)=1}} d(m) + O\left(n^{1/2+\epsilon}\right).$$ The Dirichlet series assosiated to the sum on the right is $$\zeta(s)^2 \prod_{p\mid a} \left(1-\frac{1}{p^s}\right)^2.$$ A calculation involving Perron's Formula gives $$\sum_{\substack{1\leq m\leq n\\(m,a)=1}} d(m) = n \left(\frac{\phi(a)}{a}\right)^2\left(\log n + 2\gamma-1+2\sum_{p\mid a} \frac{\log p}{p-1}\right) + O\left(d(a)n^{3/4}(\log n)^2\right).$$ (This is not the sharpest error term one can get, but it suffices here.)
Combining things, we have $$g(n) = n\sum_{a\mid n} \frac{\mu(a)\phi(a)}{a^2} \left(\log n + 2\gamma-1+2\sum_{p\mid a} \frac{\log p}{p-1}\right) + O\left(n^{3/4+\epsilon}\right).$$ Returning to your actual question, the leading order term is $$n\log n \sum_{a\mid n} \frac{\mu(a)\phi(a)}{a^2} = n\log n \prod_{p\mid n} \left(1-\frac{1}{p}\right)\prod_{p\mid n}\left(1+\frac{1}{p^2-p}\right) = \phi(n)\log n \prod_{p\mid n}\left(1+\frac{1}{p^2-p}\right)$$ A numerical computation shows that $$1 < \prod_{p\mid n}\left(1+\frac{1}{p^2-p}\right) < \prod_{p}\left(1+\frac{1}{p^2-p}\right)< 2$$ for all $$n$$ (since the product can be extended to infinity absolutely). I'm not sure if your estimate holds for all $$n$$, but it at least holds for all sufficiently large $$n$$.