12
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why must $f(1)$ be $0$ or $1$? $\endgroup$ – copper.hat Oct 4 '17 at 4:52
  • 1
    $\begingroup$ $f(0)=f(0^2+0^2)=f(0)^2+f(0)^2$ so $f(0)=0$. Next check $f(1)=f(1^2+0^2)=f(1)^2+f(0)^2=f(1)^2$. $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '17 at 5:00
  • $\begingroup$ @JorgeFernández: Thanks. A bit slow tonight :-(. $\endgroup$ – copper.hat Oct 4 '17 at 5:00
  • $\begingroup$ how did you see $f(6)=6$? $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '17 at 5:54
  • $\begingroup$ Very simple. $3^2+4^2=5^2$ which gives $6^2+8^2=10^2$. $f(10)=10$ and $f(8)=8$ so $f(6)=6$ :) $\endgroup$ – crskhr Oct 4 '17 at 5:56
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Very Very clever indeed :) $\endgroup$ – crskhr Oct 4 '17 at 8:46
  • $\begingroup$ 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. $\endgroup$ – Alon Amit Oct 4 '17 at 8:55
  • $\begingroup$ this is basically the same thing I did but two hours later! $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '17 at 15:30
  • $\begingroup$ @jorge I didn’t see your answer when I started writing mine, but you’re right. I don’t know why someone downvoted it. $\endgroup$ – Alon Amit Oct 4 '17 at 15:39
  • $\begingroup$ 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. $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '17 at 15:41
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If anyone needs help with a specific part of the post I'd be happy to help. $\endgroup$ – Jorge Fernández Hidalgo Oct 4 '17 at 6:56
  • 1
    $\begingroup$ The downvote is certainly ridiculous and stupid. +1 $\endgroup$ – Jack Oct 8 '17 at 22:21

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.