The solutions to POW-11 are in! Or make that solution, unless you also count your hosts’: only one reader responded. Perhaps everyone has been distracted by the upcoming US presidential election?!

Composite solution by Philipp Lampe, University of Bonn, and Todd and Vishal: We claim there are exactly two functions h: \mathbb{N} \to \mathbb{N} which satisfy the identity h(p^2 + q^2) = h(p)^2 + h(q)^2: the identity function and the function which is identically zero.

Clearly h(0) = h(0^2 + 0^2) = 2h(0)^2 forces h(0) = 0, whence h(1) = h(1^2 + 0^2) = h(1)^2.  Therefore h(1) = 0 or h(1) = 1, and the claim above follows if we show that h(p) = ph(1) for all p \in \mathbb{N}. The first few cases are built up as follows:

h(2) = h(1^2 + 1^2) = 2h(1)^2 = 2h(1)

h(4) = h(2^2) = (2h(1))^2 = 4h(1)

h(5) = h(2^2 + 1^2) = (2h(1))^2 + h(1)^2 = 5h(1)

h(3) = \sqrt{h(3^2 + 4^2) - h(4)^2} = \sqrt{h(5)^2 - h(4)^2} = \sqrt{(25-16)h(1)^2}

= 3h(1)

h(8) = h(2^2 + 2^2) = (2h(1))^2 + (2h(1))^2 = 8h(1)

h(10) = h(3^2 + 1^2) = (3h(1))^2 + h(1)^2 = 10h(1)

h(6) = \sqrt{h(6^2 + 8^2) - h(8)^2} = \sqrt{h(10)^2 - h(8)^2}

= \sqrt{(100-64)h(1)^2} = 6h(1)

where in a few places we have invoked the simple lemma that h(p^2) = h(p)^2 [since h(p^2 + 0^2) = h(p)^2 + 0^2]. The remainder of the argument proceeds by strong induction. For odd p = 2m+1 > 5, we have

(2m+1)^2 + (m-2)^2 = (2m-1)^2 + (m+2)^2 \qquad (1)

Since h preserves sums of two squares,  we derive

h(2m+1)^2 + h(m-2)^2 = h(2m-1)^2 + h(m+2)^2

Therefore, using the inductive hypothesis that h(q) = qh(1) for q < 2m+1, we have

h(2m+1)^2 + (m-2)^2h(1) = (2m-1)^2 h(1) + (m+2)^2 h(1) \qquad (2)

From equation (1) we also have

(2m+1)^2h(1) + (m-2)^2h(1) = (2m-1)^2h(1) + (m+2)^2h(1) \qquad (3)

Comparing equations (2) and (3), we infer h(2m+1) = (2m+1)h(1). In particular, h(q) = qh(1) for q = 7, 9, and we have the case h(8) = 8h(1) from before. This will be used to start the induction for even p, starting from p = 10.

For even p = 2m+2, where m \geq 4, we have

(2m + 2)^2 + (m-4)^2 = (2m-2)^2 + (m+4)^2 \qquad (4)

and by arguing as we did above, we derive the two equations

h(2m+2)^2 + h(m-4)^2 = h(2m-2)^2 + h(m+4)^2

h(2m+2)^2 + (m-4)^2h(1) = (2m-2)^2h(1) + (m+4)^2h(1)

where the second follows from the first by inductive hypothesis. Multiplying (4) through by h(1) and comparing with the last equation, we conclude h(2m+2) = (2m+2)h(1), and this completes the proof.

Remarks:

The underlying idea is to exploit the fact that many numbers can be expressed as a sum of two squares in more than one way, so that one can generate enough relations of the form h(p)^2 + h(q)^2 = h(r)^2 + h(s)^2 to nail down all the h(p) [in terms of h(1)]. A powerful way of generating equations of the form p^2 + q^2 = r^2 + s^2 is to consider prime factorizations in the ring of Gaussian integers \mathbb{Z}\left[i\right]. For example, in the Gaussian integers we have the prime factorizations

5 = (2 + i)(2-i) \qquad 13 = (2 + 3i)(2-3i)

so that there are two ways of writing their product 65 in the form z \cdot \bar{z}:

(2+i)(2+3i) \cdot (2-i)(2-3i), \qquad (2+i)(2-3i) \cdot (2-i)(2+3i)

Here we have, respectively, z = 1 + 8i, z = 7 - 4i, whence 65 = z \cdot \bar{z} = 1^2 + 8^2 = 7^2 + 4^2. Extrapolating from this, if we set

z = (a+bi)(c+di), \qquad z' = (a+bi)(c-di)

then we have |z|^2 = z \cdot \bar{z} = z' \cdot \bar{z'} = |z'|^2, whence we derive

(ac - bd)^2 + (bc + ad)^2 = (ac + bd)^2 + (bc - ad)^2.

This gives a large supply of available relations to work with, and from there it is not too bad to get an inductive argument up and flying, once some base cases have been cleared out of the way with some numerical experimentation.

[Although it’s a little unusual to need such an outlay of base cases (up to at least p = 6) before one can start the induction; it creates a psychological hurdle, I feel. It reminds me of POW-6, where no complete solutions were received: one has to fiddle with a number of base cases before the general argument can be pushed through.]

Incidentally, while researching this problem, I found the wonderful website MathPages, created by an all but anonymous author named Kevin Brown. I really recommend checking out this website, and I hope that it is somehow kept alive: it would be a shame for such a treasure trove to be buried and forgotten in some deep hollow of cyberspace.