If an arithmetic function $f$ is such that $\sum\limits_{n=1}^Nf(n)=\Theta(N)$ then $f(n)=o(n^\epsilon)$

92 Views Asked by At

Consider a positive-valued, arithmetic function $f$ with $f(n)\geq 2$. Suppose that $f$ satisfies the inequality

$$c_1N\leq\sum_{n=1}^Nf(n)\leq c_2N$$

where $0<c_1<c_2$ are real constants.

The aim is to show that $$f(n)=o(n^{\epsilon}) \text{, } n\to\infty$$

It is straightforward to show that $\forall \epsilon >0$, $$\liminf_{n\to\infty}\frac{f(n)}{n^{\epsilon}}=0$$ Otherwise, for $n$ larger than some sufficiently large $N_{\epsilon}$ and $c_{\epsilon}=\liminf_{n\to\infty}\frac{f(n)}{n^{\epsilon}}>0$, $$f(n)\geq (1-\epsilon)c_{\epsilon}n^{\epsilon}$$ and hence $$\sum_{n=N_{\epsilon}}^Nf(n)>(1-\epsilon)c_{\epsilon}\sum_{n=N_{\epsilon}}^{N}n^{\epsilon}=O(N^{1+\epsilon}) \text{, } N\to\infty$$. This contradicts the right hand side bound in our inequality.

The $\forall \epsilon>0$ $$\limsup_{n\to\infty}\frac{f(n)}{n^{\epsilon}}=0$$ case has proved more difficult:

If these $\limsup$s are finite for each $\epsilon>0$, then of course by picking $\epsilon'<\epsilon$ we have that $$\limsup_{n\to\infty}\frac{f(n)}{n^{\epsilon'}}=0$$.

On the other hand I cannot obtain a contradiction, assuming that there is a fixed $\delta>0$ such that $$\limsup_{n\to\infty}\frac{f(n)}{n^{\delta}}=\infty $$

For $x>0$ and $\phi(x)$ a strictly increasing function, such that $$\lim_{x\to\infty}\phi(x)\to\infty$$ we may construct a sequence of integers $n_k$ such that $$f(n_k)>\phi(k)n_k^{\delta}$$

From here it is not clear what choice to make for our auxiliary function $\phi$. Any input would be greatly appreciated!

1

There are 1 best solutions below

3
On BEST ANSWER

What you want to show need not hold. If for example $f(n) = 2n$ if $n$ is a power of $2$ and $f(n) = 2$ otherwise, then we have

$$2N \leqslant \sum_{n = 1}^N f(n) \leqslant 2N + 2\sum_{k = 0}^{\bigl\lfloor \frac{\log N}{\log 2}\bigr\rfloor} 2^k < 2N + 4\cdot 2^{\bigl\lfloor \frac{\log N}{\log 2}\bigr\rfloor} \leqslant 6N\,,$$

so $f$ satisfies the assumption, but not the desired conclusion.

A multiplicative function $f$ with $f(n) \geqslant 2$ for $n \geqslant 2$ (we always have $f(1) = 1$ for a multiplicative function that isn't identically $0$) satisfies $f(n) \geqslant 2^{\omega(n)}$, where $\omega(n)$ is the number of distinct prime factors of $n$, and thus

$$\sum_{n = 1}^N f(n) \geqslant \sum_{n = 1}^N 2^{\omega(n)} \sim \frac{6}{\pi^2}N\log N\,.$$

So a multiplicative function cannot satisfy the full assumption. If the conditions are relaxed to $f(n) \geqslant 0$ and $\sum_{n = 1}^N f(n) \in \Theta(N)$, then $f(2^k) = 2^k$ and $f(n) = 0$ if $n$ is not a power of $2$ is (completely) multiplicative and satisfies

$$\frac{1}{2}N \leqslant \sum_{n = 1}^N f(n) \leqslant 2N$$

but not $f(n) \in o(n^{\epsilon})$ for any $\epsilon \leqslant 1$.