POLYA009:  3 by 3 magic square with distinct square entries (proposed by Lev Emelyanov, 11/14/01).

Does there exist a 3 by 3 magic square whose entries are distinct integer squares?

Remark: Here is one whose entries are squares but not all distinct:

1   49  25
49  25    1
25   1   49

Discussion. [SCL, 11/15/01]: Ball and Coxeter [1, p.212] gives an order 8 magic square with the property that squaring each entry also gives a magic square. They also refer to a paper in which a magic square of order 32 is constructed, with the property that squaring the entries gives a magic square and cubing the entries also gives a magic square.

[SCL, 11/16/01]: There are three examples of double squares from the web-page
http://www.pse.che.tohoku.ac.jp/~msuzuki/MagicSquare.8x8.complete.html
_______________________________________

a.. Frolow's double square (1892)
Sum of the squared numbers are also constant.
45 23 1 59 26 36 54 16
40 30 12 50 19 41 63 5
22 48 58 4 33 27 13 55
31 37 51 9 44 18 8 62
3 57 47 21 56 14 28 34
10 52 38 32 61 7 17 43
60 2 24 46 15 53 35 25
49 11 29 39 6 64 42 20

b.. Cocoz's double square (1897)
5 31 35 60 57 34 8 30
19 9 53 46 47 56 18 12
16 22 42 39 52 61 27 1
63 37 25 24 3 14 44 50
26 4 64 49 38 43 13 23
41 51 15 2 21 28 62 40
54 48 20 11 10 17 55 45
36 58 6 29 32 7 33 59

c.. Fitting's double squares (1941)
He analyzed the properties of the square by using binary numbers.
Sum of the squared numbers in the pan-diagonals are constant.
1   2  60 59   7    8  62  61
15 40 32  49   9  34  26  55
18 42 45  21 24  48  43  19
54 27 35 12  52  29  37  14
64 63   5   6  58  57    3    4
50 25 33 16  56  31  39  10
47 23 20 44  41  17  22  46
11 38 30 53  13  36  28  51

1 17 63 47   4 20 62 46
8 28 56 41   5 25 53 44
49 29 14 34 52 32 15 35
58 39 11 23 59 38 10 22
64 48   2 18 61 45   3 19
57 37   9 24 60 40 12 21
16 36 51 31 13 33 50 30
7 26 54 42   6 27 55 43

[SCL, 11/16/01]: I can show that all of the entries must be odd in a smallest example. If

a^2 b^2 c^2
d^2 e^2 f^2
g^2 h^2 i^2

is a magic square, then there is a number m such that a^2 + b^2 + c^2 = d^2 + e^2 + f^2 = g^2 + h^2 + i^2 = a^2 + d^2 + g^2 = b^2 + e^2 + h^2 = c^2 + f^2 + i^2 = a^2 + e^2 + i^2 = c^2 + e^2 + g^2 = m.  (These are somewhat redundant, but no matter.) Now,
3e^2 = (a^2 + e^2 +i^2) + (d^2 + e^2 + f^2) + (c^2 + e^2 + g^2) - (a^2 + d^2 + g^2) -(c^2 + f^2 + i^2) = m.
Let us write m=3k, for convenience.Also, d^2 + f^2= 2k = 2e^2b^2 + h^2 = 2k = 2e^2a^2 + i^2 = 2k = 2e^2c^2 + g^2 = 2k =2e^2.
Suppose that e is even. Now, d^2 + f^2 is a multiple of 4, and thus d and f are even. Similarly, all of the entries are even, and we can divide
the magic square by 4. If we assume that we are looking for a smallest magic square with square entries, it follows that e must be odd. But now, all of the other entries must be odd, since each is in a two-term sum of squares congruent to 2 mod 4.Also, since we would like all of the entries distinct, we need to choose e so that 2e^2can be written at least 4 distinct ways as the sum of squares. [Not sufficient, but necessary.]

[SCL, 11/17/01]:  I  note that once one has decided what e, a, b are in the square

a^2   b^2   c^2
d^2   e^2   f^2
g^2   h^2   i^2

then one knows what all the entries are.

Another thought: Can one use one or more of those like what LE gives in the background remark above  to patch together a solution?

[SCL: 11/22/01]: 1. In the square

a^2 b^2 c^2
d^2 e^2 f^2
g^2 h^2 i^2

we can make the assumptions that a<e and g<e, since we can rotate the square if this is not the case. We can also make the assumption that b<e, since reflecting about the middle row will achieve this if it is not already true.

This might help very slightly in a computer search for solutions. So, we need only look for possible values of a,b,e, with a,b<e and all of the other values are determined.

2. Still thinking of a possible computational solution, I would like to limit the number of cases that need to be considered for any given e.

I am now going to use some complex numbers, so "I" will stand for the square root of negative 1. With luck, there won't be a confusion between "i" and "I".

Since a^2+i^2=2e^2, we have (a+iI)(a-iI)=2e^2. We may assume that e has no prime factor p of the form 4k+3, since then a and i (and b,h and c,g and d,f) would all be divisible by p. Thus, 2e^2 is a product of factors of the form x+yI, where x,y are relatively prime. Thus 2e^2=prod(x_q+y_qI,q=1..m), for some m. But, the gaussian integers are a unique factorization domain (up to multiplication by units). Thus, a+bI is also a product of factors of the form x+yI, where x,y are relatively prime, not both of the same parity, except for the possibilities 1+I and 1-I. Note, that since a-bI is the product of the complements of the factors in a+bI, any factors of the form x+yI and x-yI for fixed x,y must be distributed evenly amongst a+bI and a-bI. Thus, since factors of the form x+yI and x-yI for fixed x,y (except for 1+I and 1-I) occur with combined exponent a multiple of 4, they must be distributed evenly amongst a+bI and a-bI, and thus must show up an even number of times in each product.

Thus, one way to attack the problem computationally is

(1) generate a list L of gaussian integers of the form x+yI, where x,y are relatively prime, not both of the same parity, with the exception that (1+I) and (1-I) are in L. We can keep the list a little smaller by requiring that x be no more than y.

(2) Select some multiset S from L, such that the combined multiplicity of x+yI and x-yI is even for each x,y.

(3) Let (a+iI)=(1+I)*prod(q in S)

(4) Add (a,i,e) to list of possible solutions of the equation a^2+i^2=2e^2. (We can also dictate that a<i here, by simply reversing their roles.

In the above way, one can enumerate solutions of the equation a^2+i^2=2e^2, where e contains only factors from L, and where |S| is not more than some preset limit. This list of solutions can be sorted so that given e, it is easy to retrieve all possible pairs (a,i). Thus, for this e, we have our choices for a and for b from a short list, rather than searching all pairs of integers (a,b) with a<e and b<e.

I have tried this approach, with |S| at most 4, and with the factors on L fairly small. I used factors of primes under 100, and truncated that list in order to keep the run-time to a level I was willing to wait for. If anybody wants to try a more extensive run, be my guest.

[SCL: 11/26/01]: I found this web-page with a search made for the 3 by 3 square of squares.

<http://www.pse.che.tohoku.ac.jp/~msuzuki/Randall.html>

Randall L. Rathbun claims to have found squares of squares which satisfy 7 of the eight constraints. (I didn't check the ones shown, but have no reason to believe they don't have the stated property.) Maybe somebody could find out if he was eventually successful, or perhaps now that machines are a little faster, maybe somebody could expand the search by his methods.

[SCL, 12/4/01]: The same type of argument I gave to show that all of the entries are odd can also be modified to show that all of the entries are relatively prime to 6 in a smallest example.
I looked again at Randall Rathbun's page where he lists the results of his "triad" search. However, none of his triad triples even satisfies the all
entries odd condition. This indicates to me that the search may go a lot higher than he might have anticipated: up to common difference 8,848,224 he still didn't have an all odd triple.

Here is a synopsis of an attack one can take, cribbing from his page: Every 3-by-3 magic square is of the form

x+a x-a-b x+b
x-a+b x x-b+a
x-b x+a+b x-a

We need triples (x-a+mb,x+mb,x+a+mb) with m=0,1,-1. Thus, he looks for triads (u^2,v^2,w^2) with common difference t. That is, u^2+t=v^2, v^2+t=w^2.

Now, from what we know, u^2, v^2, w^2 must be odd, and thus t is a multiple of 8. (Actually t is also a multiple of 8 if we allow even cases.) Also, if t is not a multiple of 3 then {u^2,v^2,w^2} is a complete set of residues mod 3, and this is impossible. Thus, 24 divides t.

Now, one can run a program, increasing t by 24, and listing the factors of each t. If i is a factor of t, then one choice for u is (t/i-i)/2, with
v=(t/i+i)/2. Thus, each t is tested fairly quickly after the factorization. We need u to be odd, and we need w=\sqrt{v^2+t} to be an integer. If this
happens, we have an acceptable triad. If we get three or more for the same t, we have an acceptable triple of triads. It remains to check that they
will form a magic square, and 7 of the 8 conditions will be satisfied (if you place the entries where he does). What is needed is that the squares of
the middle elements of the three triads be in arithmetric progression.

So, one question to everyone: can we put even more conditions on t in order to further speed up a computer search?

[FvL, 4/19/02]:  I found the following page from "Math Pages": http://www.mathpages.com/home/kmath417.htm
It derives that if we have a Magic Square of  Squares

a^2 b^2 c^2
d^2 e^2 f^2
g^2 h^2 i^2

It is not only necessary that 2e^2 can be written as sum of squares in four ways, but more (so, at least five?) is necessary.

Bibliography. [1]: W.W. Ball and H.S.M. Coxeter, Essays in the Recreations of Mathematics, 12th edition, Dover reprint.
[2]: J.P.Robertson, Magic squares of squares, Math. Magazine, 69 (1996) 289--293.
[3]: R.K.Guy and R.J.Nowakowski, Unsolved problems, 1969--1995, Amer. Math. Monthly, 102 (1995) 925.
[4]: R.K.Guy, Problem D15, Unsolved Problems in Number Theory, 2nd edition, Springer, 1994.