Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose $f(n)$ is a positive real-valued arithmetic function such that $$ \frac1n\sum_{k=1}^nf(k)\sim g(n) $$ for $g(x)$ a monotonic increasing function. What can be said about the asymptotic behavior of $$ \sum_{k=1}^n\frac1kf(k) $$ ? The reverse question is also of interest. In both cases it seems that the asymptotics should be fairly simple multiples of each other: $$ \frac1n\sum_{k=1}^nk\sim\frac12n $$ and $$ \sum_{k=1}^n\frac1kk\sim n $$ but I have seen results where this does not seem to hold and I want to know if they are right.

Perhaps the problem cannot be solved without further restrictions on $f$ or $g$. In the case of immediate interest, $f$ and $g$ are essentially linear, in that there exists a constant $k$ such that $x/(\log x)^k\ll h(x)\ll x(\log x)^k$ for $h\in\{f,g\}$ and $x$ in the appropriate domain.

share|cite|improve this question
Let $d(k)$ be the number of divisors of $k$. If my quick calculations are correct, I'm getting $\sum_{k \leq N} \frac{d(k)}{k} \sim (\log N)^2/2$, and it is known that $\frac{1}{N} \sum_{k \leq N} d(k) \sim \log N$. I could certainly be wrong, though. – Antonio Vargas May 17 '12 at 19:09
Of course $d(x) \neq \Omega(x/(\log x)^k)$, so it doesn't fit in your particular case at the bottom of the question. – Antonio Vargas May 17 '12 at 19:16
With Abel summation we can say $$\sum_{k=1}^n\frac{f(k)}{k}=\frac{1}{n}\left(\sum_{k=1}^nf(k)\right)+\int_1^n \frac{1}{x^2}\sum_{k\le x} f(k)~dx$$ – anon May 17 '12 at 19:25
up vote 5 down vote accepted

The asymptotics really do depend on the function $f$ in question.

If $f(x)$ has a power function as its dominant term, with, say, $f(x) = x^p + o(x^p)$, for $p > 0$, then you're right about the two asymptotics being constant multiples of each other: $$\begin{align} \frac{1}{n} \sum_{k=1}^n f(k) &\sim \frac{1}{n}\frac{1}{p+1} n^{p+1} = \frac{1}{p+1} n^p, \\ \sum_{k=1}^n \frac{f(k)}{k} &= \sum_{k=1}^n \left(k^{p-1} + o(k^{p-1})\right) \sim \frac{1}{p}n^p, \end{align}$$ where we use the formula for the sum of $k$th powers (or Euler-Maclaurin summation for $p$ not an integer). This, of course, includes the linear case.

However, if $f(x)$ has $\log x$ as its dominant term, we get the behavior noted by Antonio Vargas: $$\begin{align} \frac{1}{n} \sum_{k=1}^n f(k) &= \frac{1}{n} \sum_{k=1}^n \left(\log k + o(\log k)\right) = \frac{1}{n} \left(\log n! + o(\log n!)\right) \sim \frac{n \log n}{n} = \log n,\\ \sum_{k=1}^n \frac{f(k)}{k} &= \sum_{k=1}^n \left(\frac{\log k + o(\log k)}{k}\right) \sim \frac{1}{2} (\log n)^2, \end{align}$$ where the first asymptotic follows from Stirling's formula and the second is a consequence of Euler-Maclaurin (see, for example, Lemma 2.11 in my paper here).

And, of course, if $f(x)$ has a constant $C$ as its dominant term, we get $$\begin{align} \frac{1}{n} \sum_{k=1}^n f(k) &= \frac{1}{n} \sum_{k=1}^n (C + o(1)) \sim C, \\ \sum_{k=1}^n \frac{f(k)}{k} &= \sum_{k=1}^n \left(\frac{C + o(1)}{k}\right) \sim C \log n. \end{align}$$

Based on this, I would conjecture that there's some cutoff point on the growth rate of $f(x)$ such that if $f(x)$ grows at a sufficiently large rate then $\displaystyle \frac{1}{n} \sum_{k=1}^n f(k)$ and $\displaystyle \sum_{k=1}^n \frac{f(k)}{k}$ have asymptotic growth rates that are constant multiples. Otherwise, $\displaystyle \frac{1}{n} \sum_{k=1}^n f(k)$ is asymptotically smaller than $\displaystyle \sum_{k=1}^n \frac{f(k)}{k}$. Power growth would be above that cutoff point, and logarithmic growth would be below it.

share|cite|improve this answer

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.