Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I don't know how precise I can make this question. I want to know whether there is a theorem that says that a certain phenomenon always happens, but I think the best I can do in order to pin down the phenomenon is describe it rather vaguely and then give some examples.

In connection with the Erdős discrepancy problem I'm finding that it would be quite nice to have some coefficients λ(d) such that $f(n)=\sum_{d|n}λ(d)$ is a small perturbation of a smooth function. Here are two examples. If we take λ to be the von Mangoldt function Λ then $f(n)=\log n$, which is monotonic and slowly increasing. That would count as very nice for me because it is approximately constant on long intervals. Another example is if we take λ to be the Möbius function μ. Then we get the function that's 1 at 1 and 0 everywhere else.

Now for reasons I won't go into, I'm not too keen on either of these examples. The trouble with Λ is that it is rather sparsely supported, and the trouble with μ is that it works only because there is a huge amount of cancellation. What I want to know is whether there is a general principle that says that something like this is necessary. A heuristic argument would be this: if λ is predominantly positive and is spread out over many integers d, then we would expect f(n) to be significantly bigger when n has many factors. This would make f oscillate a lot, which is roughly what I mean by not being smooth.

Thus, my question is whether there is some sort of known "uncertainty principle" that tells us, in a quantitative form, that there is a trade-off: if λ is mainly positive and is reasonably densely supported, then we have to pay the price with a lot of oscillation for f.

Thinking about it a bit further, I think that the right measure of oscillation for my purposes would be the rate of growth of $\sum_{m\leq n}|f(m)-f(m-1)|$. I'd like that not to be too much bigger than $f(n).$ At this stage, I'm not sure what I should mean by "not too much bigger than".

Just to give a tiny bit more intuition about the question, if we take λ to be 1 at all primes and 0 otherwise, then we get the number of distinct prime divisors of n, which is known to be near to $\log\log n$ with fairly high probability. So this is a reasonably smooth example. For any k we could take all products of k distinct primes. This would give us $f(n)=\binom mk$, where m is the number of distinct prime divisors of n. For smallish k this is still reasonably concentrated, by the Erdős-Kac theorem (which concerns the number of prime divisors rather than the number of distinct prime divisors, but I think a similar conclusion holds in the distinct-divisors case). So a special case of my question would be to ask how far we can push k before we lose the smoothness of f.

share|improve this question
You have probably seen this, but this reminds me of the results started by Erdos and collected in Hildebrand's "A characterization of the logarithm as an additive arithmetic function", that any reasonably smooth additive function has to be the logarithm, even if one just imposes $\sum_{n\le x}|f(n+1)-f(n)|=o(x)$. –  Gjergji Zaimi Sep 11 '10 at 17:15
I think I'm missing part of the question. You want $\lambda$ to produce a $f:=1*\lambda$ with variation controlled by $f$, but is there anything else you want on $\lambda$? Otherwise, as the title suggests, why don't you choose your favourite $f$ and just define $\lambda$ by Moebius inversion? –  Pietro Majer Sep 11 '10 at 17:20
As I said, I want λ to be reasonably spread out and mainly positive. –  gowers Sep 11 '10 at 23:34
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.