Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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? –  Barry Cipra Apr 12 '12 at 23:29
@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. –  Charles Apr 13 '12 at 1:30
@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}$. –  Eric Naslund Apr 17 '12 at 16:03
add comment

2 Answers

up vote 28 down vote accepted

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....$$

share|improve this answer
Great! Do you know of a way to generate it exactly? –  Charles Apr 13 '12 at 1:26
Use Euler's product. –  i707107 Apr 13 '12 at 1:32
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$. –  Barry Cipra Apr 13 '12 at 1:54
@Micah: Thank you for the clarification. –  Charles Apr 17 '12 at 15:59
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!! –  Barry Cipra Apr 17 '12 at 16:18
show 1 more comment

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.)

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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