If $f(1)=1$, then is it true that $f(n)=n$ for all $n \in \mathbb{N}\cup\{0\}$.

Question

Let $f:\mathbb{N}\cup\{0\}\to\mathbb{N}\cup\{0\}$ be a function which satisfies $f(x^2+y^2)=f(x)^2+f(y)^2$ for all $x,y \in\mathbb{N}\cup\{0\}$. It' easy to see that $f(0)=0$ and $f(1)=0$ or $f(1)=1$. Suppose let's assume that $f(1)=1$. Then it's very easy to see that $f(2)=2$ and since $f(2)=2$, we can see that $f(4)=4$ and $f(5)=5$ because $5=2^2+1^2$. To see $f(3)=3$, note that $$25=f(5^2)=f(3)^2+f(4)^2 \implies f(3)=3$$ One can even see that $f(6)=6$, $f(7)=7$ and so on. Is it generally true that $f(n)=n$ for all $n$?

Edit. If anyone wondering how $f(7)=7$ here is the way. Note that $f$ satisfies $f(n^2)=f(n)^2$. One can see that $$25^{2}=24^2+7^2 \implies 25^{2}=f(24)^{2}+f(7)^{2}$$ We have to show $f(24)=24$. For this note that $$26^2 = 24^2+10^2 \implies f(26)^{2} = f(24)^{2}+f(10)^{2}$$ But $f(26)=26$ because $26=5^2+1^2$ and $f(10)=10$ since $10=3^{2}+1^{2}$. In short if $n=x^2+y^2$ for some $x,y$ and $f(1)=1$, then we can see that $f(n)=n$.

Answer 1

Yes.

Suppose you already know that $f(n)=n$ for all $n < N$. You want to find $a,b,c$, all smaller than $N$, such that $N^2+a^2=b^2+c^2$. If you find such a triplet, you immediately conclude that $f(N)=N$, and you have the necessary inductive step.

For odd $N>6$, use

$N^2+\left(\frac{N-5}{2}\right)^2 = (N-2)^2+\left(\frac{N+3}{2}\right)^2$

For even $N>6$, use

$N^2+\left(\frac{N}{2}-5\right)^2 = (N-4)^2 + \left(\frac{N}{2}+3\right)^2$

Since the question details already prove that $f(n)=n$ for small values of $n$, this inductive step finishes the argument.

Answer 2

Let $N$ be the smallest number with $f(N)\neq N$.

Notice that $f(N^2+a^2)=f(N)^2 + a^2 \neq N^2 + a^2$ for all $a<N$.

On the other hand if we can write $N^2+a^2$ as $b^2 + c^2$ with $b,c<N$ then $f(b^2+c^2)=f(b)^2+f(c)^2=b^2+c^2$.

---

We now prove that for large $N$ we can always find $0\leq a,b,c < N$ such that $N^2+a^2=b^2+c^2$ or $N^2-c^2=(a+b)(a-b)$.

Letting $c=(N-k)$ we get $k(2N-k)=(a+b)(a-b)$.

Checking with $k=1,2,3$ we'll find a value such that $2N-k$ that is a multiple of $3$, this will give rise to a factorization $(\frac{2N-K}{3})(3k)$ which can be realized in the way $(a+b)(a-b)$ with $0\leq a,b<N$.

The first value that makes $N$ large enough is the first value such that $3\times 3 \leq (2N-3)$ which is $6$.

---

So we just need to prove $f(n)=n$ holds for $n\in \{0,1,2,\dots,6\}$, we prove them in this order:

$0$ (clearly)

$1$ (clearly)

$2$ (sum of two squares)

$4$ (a square)

$5$ (sum of $1^2+2^2$)

$3$ ($3^2+4^2=5^2$)

$8$ ($2^2+2^2$)

$10$ ($1^2+3^2$)

$6$ ($6^2+8^2=10^2$)