13
$\begingroup$

For a positive integer $k$, let $d(k)$ be the number of divisors of $k$. So $d(1)=1$, $d(p)=2$ if $p$ is a prime, $d(6)=4$, and $d(12)=6$.

What are the precise asymptotics of $\sum_{k=1}^n 1/(k d(k))$?

Background:

1) This came up on the side in the polymath5 project.

2) There, Tim Gowers wrote: If nobody knows the answer, maybe that’s one for MathOverflow, where I imagine a few minutes would be enough.

3) Asked: 14:17 Jerusalem time. (The first accurate answer: 17:44 Jerusalem time.)

4) Looking only at primes or only at integers with a typical number of divisors suggested a $\log\log n$ behavior, but looking at semiprimes indicates the sum is larger. I don't know how much larger.

5) I couldn't find an answer on the web. If there is an easy way searching for an answer that I missed this will be interesting too.

Follow up:

Great answers! Thanks. What about the sum $\sum_{k=1}^n 1/(kd^2(k))$ ?

Improve this question
$\endgroup$
10
  • $\begingroup$ SUM_{k=1}^n 1/kd(k) ... Does that mean $\sum_{k=1}^n 1/(k d(k))$ or $\sum_{k=1}^n d(k)/k$ ? $\endgroup$
    – Gerald Edgar
    Commented Mar 17, 2010 at 12:45
  • $\begingroup$ The former, according to Gil's link. $\endgroup$
    – Steve Huntsman
    Commented Mar 17, 2010 at 12:47
  • $\begingroup$ It's a sum of multiplicative functions so should be amenable to using Dirichlet series. $\endgroup$
    – Victor Miller
    Commented Mar 17, 2010 at 13:01
  • 2
    $\begingroup$ The correct guess is C*(log N)^(1/2). Look-up the Selberg-Delange method. (The point is that sum(z^w(n), n <= X) ~ C*(log X)^(z-1) and (1/2)^w(n) is essentially the same as 1/d(n), so by partial summation we get sum(1/kd(k),k <= X) ~ C*(log X)^(1/2-1+1)) $\endgroup$
    – maks
    Commented Mar 17, 2010 at 15:43
  • 2
    $\begingroup$ Re: the followup. If the hypotheses of the Delange (or Raikov) Tauberian theorem are satisfied, then $\sum_n 1/(n d(n)^2)$ should be $\sim C (\log x)^{1/4}$, since if $p$ is prime, $d(p) = 2$. $\endgroup$
    – Victor Miller
    Commented Mar 18, 2010 at 10:38

3 Answers 3

Reset to default
14
$\begingroup$

The idea (from the Selberg-Delange) method to doing this problem is the following steps:

1) Let $F(s) = \sum_{n\ge 1} \frac{1}{n^s d(n)} = \prod_{p} \left(1 + \sum_{k=1}^{\infty} \frac{1}{(k+1) p^{ks}} \right)$. The latter is by multiplicativity of $d(n)$.

2) If we look, instead at $G(s) = \prod_p \left( 1 + \frac{1}{2 p^s} \right)$ we can see that $F(s)/G(s)$ has a non-zero limit as $s \rightarrow 1$ from above. $G(s)$ corresponds in our original sum to restricting $n$ to be square-free.

3) $G(s)^2$ almost looks like $\zeta(s)$. Show that $G(s)^2/\zeta(s)$ also has a non-zero limit at $s \rightarrow 1$.

4) You then use some Tauberian theorems to show that since $H_n \sim \log n$ (which is the sum associated with $\zeta(s)$ then the corresponding sum for $G(s)$ (i.e. over the square-free $n$) is $\sim to \sqrt{\log n}$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I might be wrong, but I believe this idea predates Selberg and Delange by almost half a century. This was done already in 1908 by Landau to find the number of numbers represented by a sum of two squares. But since Selberg-Delange has been mentioned quite a few times in this post, I am doubting myself. $\endgroup$
    – Dror Speiser
    Commented Mar 17, 2010 at 20:52
  • $\begingroup$ @Dror: Yes, I was reminded of the Landau result you quoted too. I think what Delange did was to give a Tauberian theorem that was strong enough to deduce things like the following: $F(s) = \sum_n \frac{a_n}{n^s}$. and $F(s)^r/\zeta(s)$ has a non-zero limit when $s \rightarrow 1$, for some integer $r$ then $sum_{n \le x} a_n \sim C (\log x)^{1/r}$ for some non-zero $C$. Ramanujan's paper only announces the results. It doesn't have any proofs. $\endgroup$
    – Victor Miller
    Commented Mar 17, 2010 at 21:40
  • 1
    $\begingroup$ The Tauberian theorem you mention was actually proved by Raikov: "Generalisation of a theorem of Ikehara–Landau (in Russian). Mat. Sbornik, 45 (1938)". If I am not mistaken, the Selberg-Delange method is more about getting a better error term (dating 1947?). Of course the particular instance of Landau was also proved and can be found in: "Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindeszahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate." Arch. Math. Phys. 13, 305-312, 1908. $\endgroup$
    – Dror Speiser
    Commented Mar 17, 2010 at 21:52
  • 1
    $\begingroup$ Suppose $D(s)$ is a Dirichlet series with multiplicative coefficients. If $D(s)=\zeta(s)^{a}F(s)$ where $a$ is rational and $F(s)$ is an Euler product which converges without zeros or poles in $\mathrm{Re}(s)> \delta$ for some $\delta < 1$, then you do NOT need a Tauberian theorem to study partial sums of the coefficients of $D(s)$. It is enough to apply a usual contour integration argument, but instead of shifting the whole contour you deform it around the singularity at $s=1$. The partial sums end up being $~c(\alpha)X(\log{X})^{a-1}$ where I forget $c(a)$ (it is simple). $\endgroup$
    – David Hansen
    Commented Mar 18, 2010 at 16:15
  • $\begingroup$ ("\alpha" should be "a") $\endgroup$
    – David Hansen
    Commented Mar 18, 2010 at 16:16
11
$\begingroup$

The correct asymptotic is $C \cdot (\log N)^{1/2}$. (c.f Selberg-Delange method).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nice answer! I wishes I knew more about Selberg Delange method. $\endgroup$
    – Gil Kalai
    Commented Mar 17, 2010 at 18:34
  • $\begingroup$ The main contribution to the sum will come from the integers n <= N, with (1/2)loglog N + O((loglog N)^(1/2 + epsilon)) prime factors. This is again a consequence of... the Selberg-Delange method. $\endgroup$
    – maks
    Commented Mar 17, 2010 at 20:53
10
$\begingroup$

(edited)

The answer can be extracted from a paper of Ramanujan, "Some formulae in the analytic theory of numbers", no. 17 in his collected papers. There he gives, among other things, the formula

$\sum_{n\leq X} \frac{1}{d(n)} \sim \frac{X}{\sqrt{\log{X}}}\pi^{-\frac{1}{2}}\prod_{p}\sqrt{p^2-p}\log{\frac{p}{p-1}}$.

The answer to the original question can be extracted from this by partial summation.

As for the "follow-up", the answer is $\sum_{n \leq X} \frac{1}{n d(n)^2} \sim C (\log{X})^\frac{1}{4}$. Again, Selberg-Delange...

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ That's a nice formula, but Gil asked about the sum of 1/(n d(n)). $\endgroup$
    – Michael Lugo
    Commented Mar 17, 2010 at 15:48
  • 6
    $\begingroup$ Partial summation. $\endgroup$
    – David Hansen
    Commented Mar 17, 2010 at 15:52
  • 3
    $\begingroup$ Even though it is very elementary, I think you should write the above comment in the actual answer. The way it is currently written is just annoying. $\endgroup$
    – Dror Speiser
    Commented Mar 17, 2010 at 18:06
  • 2
    $\begingroup$ Does Ramanujan give a proof or just the formula? $\endgroup$
    – François G. Dorais
    Commented Mar 17, 2010 at 18:25
  • 8
    $\begingroup$ A remark for those who, like me, were confused: $\sqrt{p^2-p} = p (1-1/(2p)+O(1/p^2))$ and $\log (p/(p-1)) = 1/p + 1/(2 p^2) + O(1/p^3)$ so the factors in the product are $1+O(1/p^2)$ and the product converges. $\endgroup$
    – David E Speyer
    Commented Mar 17, 2010 at 18:50

You must log in to answer this question.

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