A result of Erdős on increasing multiplicative functions

Erdős proved that if $f(n)$ is a monotone increasing function from the natural numbers to the positive reals, and $f(n)$ is completely multiplicative, then there exists some constant $C$ such that $f(n)=n^C$ for all $n$.

I have not been able to find a nice proof of this online and was hoping someone could provide a proof.

Solution 1:

Here's a proof I came up with.

Let $C=\log_2 f(2)$, note that $f(2)\geq 1$ and therefore $C\geq 0$. Proceed by induction: Suppose that $f(n)=n^C$, and $n\geq 2$, we will show that $f(n+1)=(n+1)^C$. Write $D=\log_{n+1} f(n+1)$, then $C\leq D$, otherwise for sufficiently large $k$ we will have that $f(n^k)>f((n+1)^k)$, which contradicts the assumption $f$ is increasing. On the other hand, $f(n^2)=f(n)f(n)=n^{2C}=(n^2)^C$, and since $n\geq 2$ we have that $n^2>n+1$. So for the same reason as before $D\leq C$, and therefore $D=C$.

Solution 2:

(rant) This started off being a nice proof that contained the main ideas of what to do. However, because this site demands to be spoon fed answers, I had to fill in all of the nitty gritty details, which take up space. Now, this is not longer a nice proof, which makes me sad. Oh well.(rant over)

Now, suppose that the function is non-decreasing at some point. We have $ f(a) = f(b)$ for $a < b$. Taking $n$ large enough such that $ a^n < 2^k < 2^{k+1} < b^n$, since $ f(a^n) = f(b^n)$, we conclude that $ f( 2^k) = f(2^{k+1} )$, and thus $f(2) = 1 $. Similarly, we can show that $f(x) = 1$ for all $x$. Thus, the only non-decreasing function that is non-decreasing at some point, is $f(x) = 1$. This corresponds to $C = 0 $.

Henceforth, the function is strictly increasing.

Clearly, we must have $f(1) = 1$. Henceforth, we will ignore this value, mainly because I want to divide by $\ln f(a) \neq 0 $.

First, prove by contradiction (it is obvious) that (for $n>1$), $f(n) > 1$.

Second, consider $g(x) = \frac{ \ln f(a) } { \ln a} $. Prove by contradiction that $g(x)$ is a constant.

Suppose not. Then, we have $a , b \neq 1 $ such that $ g(a) < g(b) $, or that $ \frac{ \ln f(a) } { \ln a} < \frac{ \ln f(b) } { \ln b }$.
Since $ f(b) > 1 $, thus $\ln f(b) > 0 $. Also, $\ln a > 0$, so we can divide and multiply respectively to conclude that
$$ 0 < \frac{ \ln f(a) } { \ln f(b) } < \frac{ \ln a} { \ln b} $$
As such, there exist positive integers such that $ \frac{ \ln f(a) } { \ln f(b) } < \frac{ c}{d} < \frac{ \ln a} { \ln b} $.

(For you to do, almost immediate) Show that the function is not increasing on the points $ a^d, b^c$.

The RHS inequality gives us $a^d < b^c$ and the LHS inequality gives us $ f(a ^d) > f(b^c)$. Hence, the function is not increasing.

Third, conclude that $g(x)$ is a constant, and thus $ f(a) = a^C$ for some constant $C$. Furthermore, $C>0$.