13

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

C.S.
  • 5,528

2 Answers2

8

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.

Alon Amit
  • 15,591
  • 2
    Very Very clever indeed :) – C.S. Oct 04 '17 at 08:46
  • I'm afraid I may have made it look cleverer than it is, to keep it brief. There are many useful parametrizations for quadratic diophantine equations, and here we just need one solution with the added proviso that it contains a given number $N$ that is larger than the others. Some playing around with parity and factorizations quickly yield this parametric solution, and I'm sure there are others. – Alon Amit Oct 04 '17 at 08:55
  • this is basically the same thing I did but two hours later! – Asinomás Oct 04 '17 at 15:30
  • @jorge I didn’t see your answer when I started writing mine, but you’re right. I don’t know why someone downvoted it. – Alon Amit Oct 04 '17 at 15:39
  • It's okay, it just made me a bit angry that this question had +8 when I solved it and my answer managed to get a negative score somehow. Have a nice day. – Asinomás Oct 04 '17 at 15:41
4

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

Asinomás
  • 105,651