Functions that link to divisor function

Question

I am interested in the following problem:

Do there exist a function $f:\mathbb{N}\to\mathbb{N}$ such that $$f(f(n))=\sigma_0(n)$$

My progress was the following (for sake of simplicity, we denote $\sigma_0(n)$ by $d(n)$):

• I proved $f(1)=1, f(2)=2$
• $f(d(n))=d(f(n))$
• $f$ is surjective
• $f(f(ab))=f(f(a))\cdot f(f(b))$ whenever $\gcd(a,b)=1$

However, I am not able to get any good idea to solve the main problem. Any help will be highly appreciated.

EDIT: To prove $f(2)=2,$ we note that $$f(f(2))=d(2)=2\implies f(f(f(2)))=f(2)\implies d(f(2))=f(2)$$Now we know that $d(N)=N\iff N=1,2$...Its easy to check that $f(2)\neq 1\implies f(2)=2$.

Answer 1

A more intuitive solution

To construct the function $f$, we basically use the fact that there are infinitely many prime numbers. Its easy to see that $f(x)=1\iff x=1$ and $f(2)=2$ and so, now we further think how do we construct the function for higher entries.

Suppose we want to determine the value of $f(n)$ for some $n\geq 3$. To do so, we move inductively and assume that we have found out the value of $f(i)$ for all $i\leq n-1$. Okay, so we know the value of $f$ at $1$ and $2$ and thus, we can say $d(N)<N$ for all $n\geq 3$. This is actually a very beneficial statement because according to our inductive approach, we know the value of $f(d(n))$ and so, we know what is the value of $f(f(f(n)))$. But $f(f(f(n)))=d(f(n))$ and so, we know the value of $d(f(n))=k$ (say). Clearly, if we define $f(n):=p^{k-1}$, and $f(p^{k-1}):=d(n)$ then this satisfies all conditions where $p$ is some sufficiently large prime. Thus the functional square root of divisor function exists.

Example

We know $f(1)=1,f(2)=2$ and now, we find $f(3)$. As discussed earlier, we first find $d(3)$ which indeed is $2<3$. Thus, we know $f(2)=2=k$. Thus, $f(3)=p^{2-1}=p$ for some random large $p$. So, lets say $f(3)=5$ and thus, $f(5^{2-1})=f(5)=d(3)=2$. So till now, we defined:

• $f(1)=1$
• $f(2)=2$
• $f(3)=5$
• $f(5)=2$

Now, lets find $f(4)$. Applying the similar algorithm, we get $d(4)=3\implies f(3)=5=k$. Thus, $f(4)=p^{5-1}=p^4$. Lets take $p=7$ in this case. So, $f(7^{5-1})=d(4)=3$. So we get,

• $f(1)=1$
• $f(2)=2$
• $f(3)=5$
• $f(4)=2401$
• $f(5)=2$
• $f(2401)=3$

Now, we find $f(6)$ as we already know the value of $f$ for all $n\leq 5$. Going that way again, we note that $f(d(6))=f(4)=2401=k$. Thus, $f(6)=p^{2400}$. Lets take $p=23$ this time (we may also take $p=11$). Thus, $f(23^{2400})=d(6)=4$. So, we get,

• $f(1)=1$
• $f(2)=2$
• $f(3)=5$
• $f(4)=2401$
• $f(5)=2$
• $f(6)=23^{2400}$
• $f(2401)=3$
• $f(23^{2400})=4$

and we keep on continuing like that.

Answer 2

Such a function does exist; here’s an explicit construction.

Take each $n\in\mathbb N$ in ascending order, assigning a function value $f(n)$ (and possibly further function values), starting with $f(1):=1$ and $f(2):=2$, which you’ve already shown to be required. If we haven’t assigned a function value for $n$ yet, check whether we have already assigned $\sigma_0(n)$ as a function value $f(m)$ for some $m$. If so, assign $f(n):=m$. (This step isn’t actually necessary, it just prevents an even more rapid growth of the function values.) If there is no such $m$ yet, find the least prime $p$ such that $r=p^{f(\sigma_0(n))-1}$ has not been assigned a function value yet. (Since $\sigma_0(n)\lt n$ for $n\ge3$, we have already assigned a function value for $\sigma_0(n)$ when we reach $n$.) Assign $f(n):=r$ and $f(r):=\sigma_0(n)$. (This ensures $f(f(n))=f(r)=\sigma_0(n)$ and $f(f(r))=f(\sigma_0(n))=\sigma_0(r)$.) The least such prime $p$ is used just to keep the numbers small (and to avoid having to use the axiom of choice); any such prime $p$ would do.

Here are the function values assigned by this construction to the integers up to $59$, each line showing $n\to f(n)\to f(f(n))$:

1 -> 1 -> 1
2 -> 2 -> 2
3 -> 2 -> 2
5 -> 3 -> 2
4 -> 5 -> 3
16 -> 4 -> 5
6 -> 16 -> 4
7 -> 3 -> 2
8 -> 16 -> 4
9 -> 7 -> 3
10 -> 16 -> 4
11 -> 3 -> 2
32768 -> 6 -> 16
12 -> 32768 -> 6
13 -> 3 -> 2
14 -> 16 -> 4
15 -> 16 -> 4
17 -> 3 -> 2
18 -> 32768 -> 6
19 -> 3 -> 2
20 -> 32768 -> 6
21 -> 16 -> 4
22 -> 16 -> 4
23 -> 3 -> 2
14348907 -> 8 -> 16
24 -> 14348907 -> 8
25 -> 23 -> 3
26 -> 16 -> 4
27 -> 16 -> 4
28 -> 32768 -> 6
29 -> 3 -> 2
30 -> 14348907 -> 8
31 -> 3 -> 2
32 -> 32768 -> 6
33 -> 16 -> 4
34 -> 16 -> 4
35 -> 16 -> 4
64 -> 9 -> 7
36 -> 64 -> 9
37 -> 3 -> 2
38 -> 16 -> 4
39 -> 16 -> 4
40 -> 14348907 -> 8
41 -> 3 -> 2
42 -> 14348907 -> 8
43 -> 3 -> 2
44 -> 32768 -> 6
45 -> 32768 -> 6
46 -> 16 -> 4
47 -> 3 -> 2
30517578125 -> 10 -> 16
48 -> 30517578125 -> 10
49 -> 47 -> 3
50 -> 32768 -> 6
51 -> 16 -> 4
52 -> 32768 -> 6
53 -> 3 -> 2
54 -> 14348907 -> 8
55 -> 16 -> 4
56 -> 14348907 -> 8
57 -> 16 -> 4
58 -> 16 -> 4
59 -> 3 -> 2

The reason I’m including the list only up to $59$ is that with $\sigma_0(60)=12$ and $f(12)=2^{15}$ already assigned, the next assignment is $f(60)=2^{2^{15}-1}$, a number with about $10^4$ digits.

Here’s Java code that implements the construction.