Functions that link to divisor function

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$$.

• This is called the functional square root and here's an MO convo about this. Commented Apr 24, 2020 at 3:21
• @Mason But in this case we have a step function Commented Apr 24, 2020 at 3:34

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.

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) 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.