6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This is called the functional square root and here's an MO convo about this. $\endgroup$ – Mason Apr 24 '20 at 3:21
  • $\begingroup$ @Mason But in this case we have a step function $\endgroup$ – Anand Apr 24 '20 at 3:34
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.