MathOverflow is a question and answer site for professional mathematicians. 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

For a multiplicative function $f$ and $x>0$ let $$S_f(x)= \sum_{n \leq x} f(n).$$ Studying sums of this type is a favourite pastime of analytic number theorists. I'm trying to understand what kind of behaviour can occur for such sums. In particular, my question is the following.

Does there exist a multiplicative function $f$ and a constant $c_f>0$ such that $$S_f(x) \sim c_f\frac{x}{\log x},$$ as $x \to \infty$?

Here is some motivation for how I came across this problem. Analytic number theorists often study sums of the above type by studying the analytic properties of associated Diriclet series $$L(f,s)=\sum_{n=1}^{\infty}\frac{f(n)}{n^s}.$$

Here, if $L(f,s)$ has a pole of order $r>0$ at $s=1$ and is well-behaved for $\text{Re}( s) >1$, then one can often show (using e.g. a Tauberian theorem such as Perron's formula) that we have an asymptotic formula $$S_f(x) \sim c_f x (\log x)^{r-1}.$$

More generally there is the Selberg-Delange method, here one works with complex powers $\zeta^z(s)$ of the Riemann zeta function. This method, when it works, will give an asymptotic formula of the shape $$S_f(x) \sim c_f x (\log x)^{z-1}.$$ In particular, it does not seem that one can obtain an asymptotic formula like the one I am seeking using this approach.

Note that one cannot use something like the prime number theorem to construct an example of the shape I am looking for, since $\pi(n)$ is not a multiplicative function!

share|cite|improve this question
One possibility for constructing such a function is to find a multiplicatively closed set $A$ (meaning that $m,n\in A$ if and only if $mn\in A$) whose counting function satisfied $\#\{n\le x\colon n\in A\} \sim cx/\log x$. Then you could simply take $f$ to be the indicator function of $A$. – Greg Martin Dec 5 '12 at 4:45
@Greg: Do you know an example of such a set? – Daniel Loughran Dec 5 '12 at 9:47
Not offhand, no.... – Greg Martin Dec 6 '12 at 10:20
Hi Daniel, interesting question. It seems that at least one nice thing that can be said is that the primes in such a multiplicatively closed set must have zero density in the primes. This would be due to Theorem 1 of this paper ( of Moree, and also from this MO question (, Density of a set of integers. Wonder exactly how sparse they have to be, though. – Timothy Foo Dec 6 '12 at 22:33
up vote 8 down vote accepted

I think an explicit multiplicative function that should do the job for you is this one: $f(2^n)=2^n/\big((n+1)\sqrt{\log(n+e)}\big)$, $f(3^n)=3^n/\big((n+1)\sqrt{\log(n+e)}\big)$, $f(p^n)=0$ for $n\ge 1$ and primes $p\ge 5$. The $+1$'s and $+e$'s are just there to make the formula make sense for $n=0$ also.

Here's an outline of why: It suffices to show that for all $\epsilon>0$, for all sufficiently large $N$ one has $$ \sum_{N < 2^k3^l\le (1+\epsilon) N} \frac{1}{(k+1)\sqrt{\log(k+e)}}\cdot \frac{1}{(l+1)\sqrt{\log(l+e)}}\sim c\epsilon /\log N $$ Taking logs, the summation range is essentially $\log N\le k\log 2+l\log 3\le \log N+\epsilon$. For large $N$, there are approximately $\epsilon\log N/(\log 2\log 3)$ pairs $(k,l)$ in the range. These are reasonably uniformly distributed in the band of $\mathbb R^2$, $x\log 2+y\log 3\in [\log N,\log N+\epsilon]$. Hence (with a bit of work making sure the ends of the integral don't dominate), the sum is close to $$ \frac{\epsilon}{\log 2}\int_{0}^{\log N/\log 3} \frac{1}{(y+1)\sqrt{\log (y+e)}}\frac{1}{(x+1)\sqrt{\log(x+e)}}\ dx, $$ where $y=(\log N-x\log 3)/\log 2$.

In the first half of the range, the integral is something like $$ \frac{\epsilon}{\log N\sqrt{\log\log N}} \int_0^{\log N/(2\log 3)} \frac{1}{(x+1)\sqrt{\log(x+e)}}\ dx $$ which is $\sim c\epsilon/\log N$. Similarly for the second half of the range.

If you prefer your multiplicative functions to be integer-valued, of course, you can just take the floor of everything.

share|cite|improve this answer
I think this works. Very nicely conceived. – Greg Martin Dec 7 '12 at 3:27

You can find a many such functions in the book Sándor, J.; Mitrinović, D. S. & Crstici, B. Handbook of number theory. I Springer, 2006 (see for example ch. IV). Some asymptotic formulae have the form $\frac{x^2}{\log x}$ but you can easely transform them in the form $\frac{x}{\log x}$ using summation by parts.

share|cite|improve this answer
Is it possible to construct something from the ground up? Just say, I prescribe $f(p^k) = A_{pk}$ and have the average order come out right? – Will Jagy Dec 5 '12 at 1:55
Alexey: I don't see how you can produce $\frac{x}{\log x}$ from $\frac{x^2}{\log x}$. Summation by parts destroys multiplicativity, I think. – GH from MO Dec 5 '12 at 4:46
If the sum of $a(n)$ grows like $\frac{x^2}{\log x}$ then the sum of $a(n)/n$ grows like $\frac{x}{\log x}$. – Alexey Ustinov 25 mins ago – Alexey Ustinov Dec 5 '12 at 9:02
@Alexey: Thanks for the answer. I will try to find this book in our library and get back to you. Is it possible for you to give a simple example in the mean time? – Daniel Loughran Dec 5 '12 at 21:02
Chapter IV of this book is a compendium of results related to four non-multiplicative functions (the largest prime divisor, the smallest prime divisor, and the sum of the prime divisors, counted with or without multiplicity). Now there may still be a result in this chapter that fits the bill, but maybe a more precise reference could be given? – Anonymous Dec 5 '12 at 21:19

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.