9

I think the answer is that there are only 2 such functions: the zero function and the identity function, but I'm not able to prove it.

A few findings:

  1. $f(0)=0$ and thus $f(a^2)=f(a)^2$.

  2. If $f(1)=0$, then $f(2^n)=0$ for all $n\in \mathbb N_0$; if $f(1)=1$, then $f(2^n)=2^n$ for all $n\in \mathcal N_0$ (can be proven by PMI).

  3. For any functions satisfying the condition, say $f,g$, $f\circ g$ also satisfies the condition.

Source of this problem: https://www2.math.binghamton.edu/p/pow/problem2f20

Yuqiao Huang
  • 728
  • 2
    Notice that having $f(a^2)=f(a)^2$, you get $f(x+y)=f(x)+f(y)$ where $x=a^2, y=b^2$. This is the well-known Cauchy functional equality. Its solution in $\mathbb{N}$ is $f(a)=f(1)\cdot a$ – Dr. Mathva Sep 30 '20 at 18:19
  • 4
    @Dr.Mathva Is this true? We get this for all $x,y$ which are perfect squares, but is it easy to see that it must hold for all the natural numbers? – lulu Sep 30 '20 at 18:21
  • @Dr.Mathva Thank you for this information! I just checked Cauchy functional equation, but I'm not sure how to construct a proof as the case here is only nonnegative integers? – Yuqiao Huang Sep 30 '20 at 18:31
  • 1
    To stress: , given that $f(1)=1$, say, it is easy to show that $f(2)=2$ but not so easy to see that $f(3)=3$. It is still true though: Note that $f(5)=f(2)^2+f(1)^2=5$ so $25=f(25)=f(16+9)=16+f(9)\implies f(9)=9\implies f(3)=3$. And similar arguments work generally. Though I do not see a shortcut (which, of course, doesn't mean that there isn't one). – lulu Sep 30 '20 at 18:35
  • @lulu Yes. During my thinking, I went from 1 through 10 and was not able to show $f(11)=11$ given $f(1)=1$. – Yuqiao Huang Sep 30 '20 at 18:39
  • @YuqiaoHuang Yes, the argument I used for $3$ doesn't work...we could try to look at the Pythagroean triple $(11,60,61)$ but $60$ is not the sum of two squares. – lulu Sep 30 '20 at 18:45
  • @Lulu you are right ... after searching for duplicates, this is the only answer I have found (it's the last and long post). Hope it helps, since this does not look easy – Dr. Mathva Sep 30 '20 at 18:49
  • @Dr.Mathva No worries. I was hoping you had a shortcut! My method seems difficult and I am not sure it gets all the cases. – lulu Sep 30 '20 at 18:52
  • Also, the sixth post looks interesting. – Dr. Mathva Sep 30 '20 at 18:53
  • 3
    @YuqiaoHuang To do $f(11)$: Note that $f(125)=f(10^2+5^2)=125$, but $f(125)=f(11^2+2^2)=f(11)^2+4\implies f(11)^2=121\implies f(11)=11$. – lulu Sep 30 '20 at 18:53
  • @lulu Oh lol. Thank you xD – Yuqiao Huang Sep 30 '20 at 18:54
  • @Dr.Mathva Wow there is a solution. Thanks! – Yuqiao Huang Sep 30 '20 at 18:55
  • @Dr.Mathva That solution is brutal! But, then, I can't manage to show that my method always works, though it seems to work in any case I try. – lulu Sep 30 '20 at 18:56
  • 2
    Does this answer your question? (A lot more here – metamorphy Oct 03 '20 at 08:08

2 Answers2

4

I found a much simpler proof, heavily based on and inspired by the ideas of Hagen von Eitzen's solution. For the sake of completeness, we first note that $f(0) = 2f(0)^2$ and because $1 \neq 2f(0)$, we must have $f(0) = 0$. Next we find $f(1)^2 = f(1)$ and so $f(1) \in \{ 0,1 \}$. For convenience, denote $u = f(1)$. More generally, we have that $f(a^2) = f(a)^2$.

We proceed by noting that $f(2) = 2u^2 = 2u$ and so $f(4) = f(2)^2 = 4u$. Further, observe that $f(5) = f(1)^2 + f(2)^2 = 5u$. Next we note that $f(3)^2 + f(4)^2 = f(25) = f(5)^2.$ We conclude that $f(3) = 3u$ also. Lastly, we note that $f(8) = f(2)^2 + f(2)^2 = 8u$ and $f(10) = f(3)^2 + f(1)^2 = 10u,$ so that from $f(6)^2 + f(8)^2 = f(100) = f(10)^2$ we find that $f(6) = 6u$ too.

We will now prove with induction that $f(n) = nu$ for all non-negative integers $n$. Suppose that for some integer $n > 6$ we have shown that $f(k) = ku$ for all $k < n$. If $n$ is odd, write $n = 2m+1$ for some $m > 2$. Then the equality $$ (2m+1)^2 + (m-2)^2 = (2m-1)^2 + (m+2)^2 $$ implies via the functional equation that $$ f(2m+1)^2 + f(m-2)^2 = f(2m-1)^2 + f(m+2)^2 $$ Since all of $m-2$, $2m-1$ and $m+2$ are smaller than $2m+1$, the result for $n = 2m+1$ follows by induction. Similarly, for even $n$, we write $n = 2m+2$ for some $m > 2$ to find that $$ (2m+2)^2 + (m-4)^2 = (2m-2)^2 + (m+4)^2 $$ implies via the functional equation that $$ f(2m+2)^2 + f(|m-4|)^2 = f(2m-2)^2 + f(m+4)^2. $$ Therefore the induction hypothesis ensures that the result also holds for $n = 2m+2$, as desired.

Mike Daas
  • 1,879
3

With $u=f(1)$, let $$ S=\{\,n\in\Bbb N_0\mid f(n)=nu\,\}.$$ Clearly,

  • $0\in S$,
  • $1\in S$,
  • If two of $a,b,a^2+b^2$ are $\in S$, then so is the third
  • If one of $a,2a^2$ is $\in S$, then so is the other
  • If $a^2+b^2=c^2+d^2$ and three of $a,b,c,d$ are $\in S$, then so is the fourth

From these, we conclude by induction (as you already did), $2^n\in S$ for all $n$, but we also have for example $5=2^2+1^2\in S$ and then from $3^2+4^2=0^2+5^2$, we get $3\in S$ and also $9=3^2\in S$. We also have $7\in S$ from $7^2+1^2=2\cdot 5^2$. Also, $10=3^2+1^2\in S$. Thus the last bullit point applied to $6,8,10,0$ gives us $6\in S$.

Assume $S\ne\Bbb N_0$ and let $a=\min(\Bbb N_0\setminus S)$. From the results so far, we know $a\ge 11$.

Lemma 1. Let $k$ be odd and assume $a\ge M$, where $$M\ge\frac{9k^2+4k}8.$$ Then $2a-k$ is prime.

Proof. Assume $2a-k=rs$ with $1<r\le s$. Then $r,s$ are odd and hence $r\ge 3$ and $$s\ge \sqrt{2M-k}\ge\frac32k.$$ We have $$a^2-(a-k)^2=kr\cdot s=\left(\frac{kr+s}2\right)^2- \left(\frac{|kr-s|}2\right)^2,$$ where $a-k$, $\frac{kr+s}2$, $\frac{|kr-s|}2$ are natural numbers. To see that they are all $<a$, note that $$\frac{kr+s}2=\frac{2a-k}2\left(\frac ks+\frac 1r\right) \le \frac{2a-k}2\left(\frac23+\frac13\right)<a. $$ Thus by minimality of $a$, we conclude $a-k, \frac{kr+s}2, \frac{|kr-s|}2\in S$, and then by the last bullit point above, we conclude $a\in S$, contradiction. $\square$

Corollary. $a\le 24$.

Proof. Otherwise, apply the lemma with $k=1,3,5$ and $M=25$ to find three consecutive primes $2a-5,2a-3,2a-1$ (and they are not $3,5,7$). $\square$

By the same method with $M=11$, we see that $2a-3, 2a-1$ are twin primes. Together with the special cases we have already found above, the only remaining possibility is $a=22$. Using $$ 22^2+4^2=20^2+10^2$$ we finally eliminate this case as well.

But if there is no possible value for $a=\min(\Bbb N_0\setminus S)$, it must be the case that $S=\Bbb N_0$.

Hagen von Eitzen
  • 374,180