I was solving some problems on functional equations especially on multiplicative functions today. I noticed that a strictly increasing completely multiplicative function $f:\mathbb N \to\mathbb N$ depends much on the value of $f(2)$. And there are some values of $f(2)$ (such as $f(2)=3$) for which such functions can not exist. So the following question came to my mind:
Let $f:\mathbb N\to\mathbb N$ be a strictly increasing completely multiplicative function with $f(2)=k$. Find the values of $k$ for which there cannot exist the function $f$ with the given properties.
I tried the problem for small values of $f(2)$ and here are the results (I will skip some of the proofs as they have been proved before in this site):
-
$f(2)=1$: Since $f(1)<f(2)=1$, there cannot exist the function.
-
$f(2)=2$: In this case, $f(n)=n\ \forall n\in\mathbb N$.
(Proof) -
$f(2)=3$: We have $f(3^2)>f(2^3)=27$ or $f(3)>5$ and $f(3^8)<f(2^{13})=3^{13}$ or $f(3)<6$. Since $5<f(3)<6$, the function cannot exist.
-
$f(2)=4$: In this case, $f(n)=n^2\ \forall n\in\mathbb N$.
(Proof)
So we have found two values of $k$. What are the other values? Are they the set of odd numbers or powers of $2$? How to prove in general?
Best Answer
The only completely multiplicative increasing functions $\mathbb{N} \to \mathbb{N}$ are of the form $f(n) = n^j$ for some positive integer $j$.
To prove this, let $f(2) = 2^w$ for some real number $w$. Then consider $f(k)$.
Suppose that $f(k) > k^w$. In this case, we have $\log_2(f(k)) > w \log_2(k)$ and therefore $\log_2(k) < \frac{\log_2(f(k))}{w}$.
The rational numbers are dense, so take some $a \in \mathbb{N}, b \in \mathbb{N}, b > 0$ such that $\log_2(k) < \frac{a}{b} < \frac{\log_2(f(k))}{w}$.
Then we see that $k^b < 2^a$. Therefore, $f(k)^b = f(k^b) < f(2^a) = f(2)^a = 2^{w \cdot a}$. But we also see that $2^{w \cdot a} < f(k)^b$. Contradiction.
Similarly, suppose $f(k) < k^w$. In that case, we have $\log_2(k) > \frac{\log_2(f(k))}{w}$.
By the density of the rational numbers, we take some $a, b \in \mathbb{N}$, $b > 0$ such that $\frac{\log_2(f(k))}{w} < \frac{a}{b} < \log_2(k)$.
From $\frac{a}{b} < \log_2(k)$, we derive that $2^a < k^b$ and hence that $2^{a \cdot w} = f(2)^a = f(2^a) < f(k^b) = f(k)^b$. From $\frac{\log_2(f(k))}{w} < \frac{a}{b}$, we derive that $f(k)^b < 2^{a \cdot w}$. Again, we have a contradiction.
Therefore, we see that $f(k) = k^w$ for all $k$.
Clearly, we must have $w > 0$ to make $f$ increasing. And since $n^w$ is an integer for all $n$, we see that $w$ must be an integer.
So the answer is that the only possible values of $f(2)$ are the even powers of 2.