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.

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