There is a literature dealing with $$ \sum_{k\le x}d(f(k)) $$ where $f$ is an irreducible polynomial and $d(n)$ is the number of divisors of $n$. Erdos 1952 shows that the sum $\asymp x\log x,$ which was improved to $Ax\log x+O(x\log\log x)$ by Bellman-Shapiro (cited in Scourfield). But these results only apply to irreducible polynomials.

  1. What asymptotics are known for $\sum_{k\le x}d(k^2)$?
  2. Are there good methods for calculating this sum quickly?

The literature includes: Dirichlet 1850, Voronoi 1903 and van der Corput 1922, Kolesnik 1969, Huxley 1993, Nowak 2001 (linear); Scourfield 1961, Hooley 1963, McKee 1995, McKee 1997, McKee 1999, Broughan 2002 (quadratic). The sequence is in the OEIS as A061503 but there is no real information there.

  • 4
    $\begingroup$ Doesn't Theorem 5.2 (with $\alpha$ set equal to $x$) in the paper by Broughan, linked to by the OEIS sequence you referenced, provide the answer? $\endgroup$ – Barry Cipra Apr 12 '12 at 23:29
  • $\begingroup$ @Barry: You're right! I saw the paper but was discouraged by the use of the restricted divisor function rather than d(n). The first few theorems didn't apply and I sort of skimmed the rest without checking carefully. $\endgroup$ – Charles Apr 13 '12 at 1:30
  • 4
    $\begingroup$ @Barry Cipra: Careful, it doesn't provide the answer. You would need to set $\alpha=x^2$, not $\alpha=x$. By definition, $$d_\alpha (n)=|\{d|n:\ d\leq \alpha\}|,$$ so to be sure to get all of the divisors of $n^2$ for $n\leq x$, we must have $\alpha =x^2$. There is a way to modify Broughan's proof by using the hyperbola method so that the error depends on $\sqrt{\alpha}$. $\endgroup$ – Eric Naslund Apr 17 '12 at 16:03

In the case you are interested in there is a simple generating (Dirichlet) series: $$ \sum_{n=1}^\infty \frac{d(n^2)}{n^s} = \frac{\zeta^3(s)}{\zeta(2s)}.$$ From this you can either use a convolution argument or a Perron formula type argument to get an asymptotic formula. In particular, I believe it follows that $$\sum_{n\leq x} d(n^2) = \frac{3}{\pi^2}x \log^2 x +O(x \log x). $$ With more work, you can get lower-order terms of size $\asymp x \log x$ and $\asymp x.$

Edit: There seems to some disagreement on whether the coefficient of the leading order term is $\frac{3}{\pi^2}$ or $\frac{3}{2\pi^2}$. I believe that $\frac{3}{\pi^2}$ is correct. Here are three bits of reasoning: From the generating series, we have $$ \sum_{n\leq x}d(n^2) = \sum_{n\leq x} \sum_{k\ell^2=n} d_3(k)\mu(\ell) = \sum_{\ell\leq \sqrt{x}} \mu(\ell) \sum_{k\leq x/\ell^2} d_3(k) $$ where $d_3(n)$ denotes the number of ways to write $n$ as a product of three positive divisors and $\mu(\ell)$ is the Moebius function. By a standard estimate $$ \sum_{k\leq x/\ell^2} d_3(k) = \frac{x}{2\ell^2}\log^2(x/\ell^2) + O\left(\frac{x\log x}{\ell^2} \right)$$ from which it follows that $$ \sum_{n\leq x}d(n^2) = \frac{x \log^2 x}{2} \sum_{\ell \leq \sqrt{x}} \frac{\mu(\ell)}{\ell^2} +O(x\log x) = \frac{3 x}{\pi^2}\log^2 x +O(x\log x).$$ Alternatively, a Perron formula (e.g. Prime Number Theorem) type argument can be used to show that $$ \sum_{n\leq x}d(n^2) = \text{Res}_{s=1} \frac{\zeta^3(s)}{\zeta(2s)} \frac{x^s}{s} +o(x) = \frac{3x}{\pi^2}\log^2 x + O(x\log x).$$ Moreover, in Mathematica, you can use DivisorSigma[0, n^2] to calculate $d(n^2)$. For $x=1,000,000$ I get that $$ \frac{\pi^2}{3x\log^2x}\sum_{n\leq x} d(n^2) \approx 1.27305392....$$ The slow convergence to 1 is from the influence of lower-order terms. Notice, however, that the value it is not anywhere near $1/2$. However, if I define $F(x)$ to be the residue of$\frac{\zeta^3(s)}{\zeta(2s)}\frac{x^s}{s}$ at $s=1$, I get that $$ \frac{1}{F(x)}\sum_{n\leq x} d(n^2) \approx 1.0000073....$$

  • $\begingroup$ Great! Do you know of a way to generate it exactly? $\endgroup$ – Charles Apr 13 '12 at 1:26
  • $\begingroup$ Use Euler's product. $\endgroup$ – Sungjin Kim Apr 13 '12 at 1:32
  • 1
    $\begingroup$ According to the Broughan paper (see my comment to the OP), the factor in front of the $x\log^2x$ is $3/2\pi^2$. $\endgroup$ – Barry Cipra Apr 13 '12 at 1:54
  • $\begingroup$ @Micah: Thank you for the clarification. $\endgroup$ – Charles Apr 17 '12 at 15:59
  • $\begingroup$ And in a correction to my comment to the OP, Eric Naslund has explained why there's no conflict with the Broughan paper. Thanks, Eric!! $\endgroup$ – Barry Cipra Apr 17 '12 at 16:18

It is interesting that $d(n^2)$ problem admits square root cancelation in the error term: $$\sum_{n\leq x} d(n^2) = x P_2(\log x) +O\left(x^{1/2}\exp\left(-c\frac{\log^{3/5}x}{\log^{1/5}\log x}\right)\right).$$ (See section 4.12 from Postnikov A. G. Introduction to analytic number theory. He reissues result from the article Stronina M. I. Integral points on circular cones. (Russian) Izv. Vysš. Učebn. Zaved. Matematika 1969.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.