15
$\begingroup$

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.

$\endgroup$
4
  • 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$ Commented Apr 12, 2012 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
    Commented Apr 13, 2012 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$ Commented Apr 17, 2012 at 16:03
  • $\begingroup$ In 2019 I added in OEIS A061503 more precise asymptotics and graph. $\endgroup$ Commented Jun 26, 2020 at 9:19

2 Answers 2

29
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Great! Do you know of a way to generate it exactly? $\endgroup$
    – Charles
    Commented Apr 13, 2012 at 1:26
  • $\begingroup$ Use Euler's product. $\endgroup$ Commented Apr 13, 2012 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$ Commented Apr 13, 2012 at 1:54
  • $\begingroup$ @Micah: Thank you for the clarification. $\endgroup$
    – Charles
    Commented Apr 17, 2012 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$ Commented Apr 17, 2012 at 16:18
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .