13

5

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.

flag
4 
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 2012 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 2012 at 1:30
2 
@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 2012 at 16:03

1 Answer

25

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

link|flag
Great! Do you know of a way to generate it exactly? – Charles Apr 13 2012 at 1:26
Use Euler's product. – i707107 Apr 13 2012 at 1:32
1 
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 2012 at 1:54
@Micah: Thank you for the clarification. – Charles Apr 17 2012 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 2012 at 16:18
show 1 more comment

Your Answer

Get an OpenID
or

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