8
$\begingroup$

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.

  • 0
    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.2012-05-17
  • 0
    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.2012-05-17
  • 3
    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$$2012-05-17

1 Answers 1

5

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.