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 which satisfy the identity : the identity function and the function which is identically zero.

Clearly forces , whence . Therefore or , and the claim above follows if we show that for all . The first few cases are built up as follows:

where in a few places we have invoked the simple lemma that [since ]. The remainder of the argument proceeds by strong induction. For odd , we have

Since preserves sums of two squares, we derive

Therefore, using the inductive hypothesis that for , we have

From equation (1) we also have

Comparing equations (2) and (3), we infer . In particular, for , and we have the case from before. This will be used to start the induction for even , starting from .

For even , where , we have

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

where the second follows from the first by inductive hypothesis. Multiplying (4) through by and comparing with the last equation, we conclude , 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 to nail down all the [in terms of ]. A powerful way of generating equations of the form is to consider prime factorizations in the ring of Gaussian integers . For example, in the Gaussian integers we have the prime factorizations

so that there are two ways of writing their product 65 in the form :

Here we have, respectively, , , whence . Extrapolating from this, if we set

then we have , whence we derive

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

## 8 comments

Comments feed for this article

November 4, 2008 at 12:59 pm

Henry WiltonWell, I can assure you that you didn’t receive only one solution for want of trying! I spent a little while thinking about this, and found that I seemed to be able to do as many cases as I liked, using the identity

. [

edited]For instance,

and one can deduce : , of course, and one gets from :

.

( and are both easy.) In other words, I only used pythagorean triples and sums of squares – I didn’t spot a systematic way of writing sums of squares in two different ways.

I couldn’t push this through to an induction, because as the example of 11 illustrates, you typically have to go much higher before you get lower. (Of course it’s no accident that one could deal with 61, the right hand side of the formula is always a sum of squares.)

Anyway, thanks a lot for this problem! I found it really stimulating, and learned a lot of simple number theory that I’d never known and no doubt should have, such as Fermat/Euler’s theorem that a prime congruent to 1 mod 4 is a sum of two squares.

I wonder if anyone can make my method work, or find an example that one can certainly not do in the way I suggest?

November 4, 2008 at 1:00 pm

Henry WiltonAargh! What’s wrong with my latex?

November 4, 2008 at 2:32 pm

John ArmstrongYou put a space between the “$” and the “latex”.

Either that or you used an oil-based lubricant to get your post into the tubes.

November 4, 2008 at 2:38 pm

Henry WiltonThanks, John.

Also, I notice on re-reading that 24 should have been 20, somewhere.

November 4, 2008 at 2:41 pm

Henry WiltonOh, and the identity should have been

,

of course.

Note to self: don’t try to write latex in wordpress comments before 7am.

November 4, 2008 at 3:02 pm

lukasI’ve been trying to solve this one too, and like Henry, missed the crucial equation (1). In my attempt to solve the problem, I started analyzing the analogous problem for a function . I don’t think there are any solutions besides the obvious ( and the identity), but I have not been able to prove this either. It looks like the proof presented here can be generalized, but there might be some pitfalls, and I’m not in the right state of mind to work it all through right now… but I thought I’d throw it out there. Have fun.

November 6, 2008 at 11:28 pm

Todd TrimbleSorry to be incommunicado; problems with my computer. Henry, thanks for the note of appreciation. Generally what I’ve been trying to do is select problems whose solutions illustrate some general theory or principle, with varying degrees of success however, so it’s always nice to hear when someone has derived some benefit!

(Whenever I set out to solve problems like the ones you see on the Putnam or in the American Mathematical Monthly, my secret hope is that I’ll pick up something that may come in handy some day. I think I can safely say that just about never happens, alas!)

The problems posed by Henry and lukas are intriguing, but I must confess not having much luck with them yet. If anyone has some bright ideas, please let us know here or in mail to our email address (the one given for submitting solutions to POW’s).

December 3, 2008 at 4:09 pm

Funções que preservam somas de quadrado « Morfismo[…] Achou curioso e quer ver uma prova para esse fato, siga até o link (em inglês¹) abaixo: http://topologicalmusings.wordpress.com […]