Notes on The Magic Squares of Squares Problem (Nov. 2020)


1. Problem Introduction

A Magic Square is an \(n \times n\) matrix where the sums of the elements along the rows, columns, and diagonals are the same. Here is an example of a classic \(3 \times 3\) Magic Square using the natural numbers \(1\) through \(9\).

\(6\)\(1\)\(8\)
\(7\)\(5\)\(3\)
\(2\)\(9\)\(4\)

In the square above it is easy to verify that all rows, columns, and diagonals sum to \(15\).

People have been studying Magic Squares for at least the past \(4000\) years; however, there are a few open problems related to Magic Squares with a few additional constraints on the values of their entries. A good survey of these open problems (and the rewards for solving them) is found here. These recreational mathematics problems are easy to state, yet deceptively difficult to answer.

The problem in particular that has captured my interest for well over a year now is the Magic Squares of Squares problem which asks if a \(3 \times 3\) Magic Square exists with \(9\) distinct positive square integers.

For a good survey of what is known so far about this problem, I recommend taking a look here and here. This is a well studied problem in number theory, yet no one has been able to produce either a \(3 \times 3\) Magic Square of Squares or a proof that it doesn't exist.

While, I have not solved the problem, I believe that I have some interesting results, and I see no reason not to share them with others while I continue to think about the problem.


2. My Results

If a \(3 \times 3\) Magic Square of Squares exists, it must be a square integer multiple of a rational \(3 \times 3\) Magic Square of Squares of the following form (up to rotation and reflection)

\(\left(\frac{u^2-2u-1}{u^2+1}\right)^2\)\(1+\frac{4u(u^2-1)}{(u^2+1)^2}+\frac{4v(v^2-1)}{(v^2+1)^2}\)\(\left(\frac{v^2-2v-1}{v^2+1}\right)^2\)
\(1+\frac{4u(u^2-1)}{(u^2+1)^2}-\frac{4v(v^2-1)}{(v^2+1)^2}\)\(1\)\(1-\frac{4u(u^2-1)}{(u^2+1)^2}+\frac{4v(v^2-1)}{(v^2+1)^2}\)
\(\left(\frac{v^2+2v-1}{v^2+1}\right)^2\)\(1-\frac{4u(u^2-1)}{(u^2+1)^2}-\frac{4v(v^2-1)}{(v^2+1)^2}\)\(\left(\frac{u^2+2u-1}{u^2+1}\right)^2\)

Also, if there does not exist \(u,w_0,w_1 \in \mathbb{Q}\) that is a non-trivial solution to \(\frac{2u(u^2-1)}{(u^2+1)^2}=\frac{w_0(w_0^2-1)}{(w_0^2+1)^2}+\frac{w_1(w_1^2-1)}{(w_1^2+1)^2}\), then there does not exist a non-trivial Magic Square of Squares.

Also, if there does not exist \(u,v,w_0 \in \mathbb{Q}\) that is a non-trivial solution to \(\frac{u(u^2-1)}{(u^2+1)^2}+\frac{v(v^2-1)}{(v^2+1)^2}=\frac{w_0(w_0^2-1)}{(w_0^2+1)^2}\), then there does not exist a non-trivial Magic Square of Squares.


3. Proof of Results

a. Searching Over Rationals Instead of Integers For Solutions

To make the problem easier we are going to search for a \(3 \times 3\) Magic Square with 9 distinct positive square rationals.

If a \(3 \times 3\) Magic Square exists 9 distinct positive square rationals, then a \(3 \times 3\) Magic Square exists with 9 distinct positive square integers and vice-versa

The integers to rationals case is trivial, and the rationals to integers case just involves multiplying all of the entries by the gcd of the denominators.

b. Parameterizing Solutions

It is well known that all Rational \(3 \times 3\) Magic Squares can parameterized by the following:

\(x-y\)\(x+y+z\)\(x-z\)
\(x+y-z\)\(x\)\(x-y+z\)
\(x+z\)\(x-y-z\)\(x+y\)

Dividing through by \(x\) we get the following (Note \(x\) is never \(0\)):

\(\frac{x-y}{x}\)\(\frac{x+y+z}{x}\)\(\frac{x-z}{x}\)
\(\frac{x+y-z}{x}\)\(\frac{x}{x}\)\(\frac{x-y+z}{x}\)
\(\frac{x+z}{x}\)\(\frac{x-y-z}{x}\)\(\frac{x+y}{x}\)

Which simplifies to the following with \(Y:=\frac{y}{x}\) and \(Z:=\frac{z}{x}\)

\(1-Y\)\(1+Y+Z\)\(1-Z\)
\(1+Y-Z\)\(1\)\(1-Y+Z\)
\(1+Z\)\(1-Y-Z\)\(1+Y\)

All that we have done so far is scale the initial parameterization. This new Magic Square now parameterizes all \(3 \times 3\) Magic Squares with Magic sums of \(3\).

For a Magic Square of Squares to exist, the following radicals (ignoring signs) must all be rational (and unique):

\[\sqrt{1-Y},\sqrt{1+Y},\sqrt{1-Z},\sqrt{1+Z},\sqrt{1-Y-Z},\sqrt{1+Y-Z},\sqrt{1-Y+Z},\sqrt{1+Y+Z}\]

We will return to these once we prove something about the rational parameterization of \(\sqrt{1-p},\sqrt{1+p}\)

c. A Rational Parameterization of \(\sqrt{1-p},\sqrt{1+p}\)

We can find a rational parameterization of \(\sqrt{1-p}\) in terms of \(t\) easily by the following algebraic manipulation:

\[t=\sqrt{1-p}\]

\[t^2=1-p\]

\[p=1-t^2\]

Then we will substitute \(1-t^2\) for \(p\) in \(\sqrt{1+p}\) and generate a new rational parameterization of both expressions

\[s=\sqrt{1+p}\]

\[s=\sqrt{1+(1-t^2)}\]

\[s=\sqrt{2-t^2}\]

\[s^2=2-t^2\]

\[s^2+t^2=2\]

This is the equation for a circle with radius 2. All circles have rational parameterizations in 1 variable, and we can find this circle's rational parameterization by the following steps:

\(s=1,t=1\) is a rational point on this circle, so all rational points (ignoring the point \((1,-1))\) can be expressed as the intersection between the line \(s=u(t-1)+1\) with rational slope \(u\) and the circle \(s^2+t^2=2\)

Next we will plug \(s=u(t-1)+1\) into \(s^2+t^2=2\) to get the intersection. Simplifying and solving for \(t\) is messy, but we get the following simple result:

\[(u(t-1)+1)^2+t^2=2\]

Expand:

\[t^2u^2-2tu^2+2tu+u^2-2u+1+t^2=2\]

Move all terms to the left side of the equation

\[t^2u^2+t^2+2tu-2tu^2+u^2-2u-1=0\]

Collect powers of \(t\):

\[t^2(u^2+1)+t(2u-2u^2)+(u^2-2u-1)=0\]

Quadratic formula:

\[t=\frac{-(2u-2u^2) \pm \sqrt{(2u-2u^2)^2-4(u^2+1)(u^2-2u-1)}}{2(u^2+1)}\]

Simplify:

\[t=\frac{u^2-u \pm (u+1)}{u^2+1}\]

\[t=\frac{u^2-u+(u+1)}{u^2+1},t=\frac{u^2-u-(u+1)}{u^2+1}\]

\[t=\frac{u^2+1}{u^2+1},t=\frac{u^2-2u-1}{u^2+1}\]

\[t=1,t=\frac{u^2-2u-1}{u^2+1}\]

Plugging \(t\) back into our original equation \(p=1-t^2\) and solving for \(p\) we get two solutions:

The first is trivial (and it is a trivial solution to the larger Magic Squares problem): \(t=1\)

\[p=1-1^2=0\]

The second is more interesting: \(t=\frac{u^2-2u-1}{u^2+1}\)

\[p=1-(\frac{u^2-2u-1}{u^2+1})^2\]

\[p=\frac{(u^2+1)^2}{(u^2+1)^2}-\frac{(u^2-2u-1)^2}{(u^2+1)^2}\]

\[p=\frac{(u^2+1)^2-(u^2-2u-1)^2}{(u^2+1)^2}\]

\[p=\frac{4u(u^2-1)}{(u^2+1)^2}\]

d. A final Parameterization of \(3 \times 3\) Magic Squares of Squares

Using this parameterization (above), we define the following:

\[Y:=\frac{4u(u^2-1)}{(u^2+1)^2},Z:=\frac{4v(v^2-1)}{(v^2+1)^2}\]

\(\sqrt{1-Y},\sqrt{1+Y},\sqrt{1-Z},\sqrt{1+Z}\) are always rational with this parameterization, so all that remains is to find a pair \((u,v) \in \mathbb{Q}^2\) such that the following are rational: \(\sqrt{1-Y-Z},\sqrt{1+Y-Z},\sqrt{1-Y+Z},\sqrt{1+Y+Z}\)

For \(\sqrt{1-Y-Z}\) and \(\sqrt{1+Y+Z}\) to be rational, there must exist \(w_0\in\mathbb{Q}\) such that \(Y+Z=\frac{4w_0(w_0^2-1)}{(w_0^2+1)^2}\)

For \(\sqrt{1+Y-Z}\) and \(\sqrt{1-Y+Z}\) to be rational, there must exist \(w_1\in\mathbb{Q}\) such that \(Y-Z=\frac{4w_1(w_1^2-1)}{(w_1^2+1)^2}\)

Substituting what we know about \(Y\) and \(Z\), we get the following two equations:

\[\frac{4u(u^2-1)}{(u^2+1)^2}+\frac{4v(v^2-1)}{(v^2+1)^2}=\frac{4w_0(w_0^2-1)}{(w_0^2+1)^2} \;\;\; , \;\;\; \frac{4u(u^2-1)}{(u^2+1)^2}-\frac{4v(v^2-1)}{(v^2+1)^2}=\frac{4w_1(w_1^2-1)}{(w_1^2+1)^2}\]

We can divide through by 4:

\[\frac{u(u^2-1)}{(u^2+1)^2}+\frac{v(v^2-1)}{(v^2+1)^2}=\frac{w_0(w_0^2-1)}{(w_0^2+1)^2} \;\;\; , \;\;\; \frac{u(u^2-1)}{(u^2+1)^2}-\frac{v(v^2-1)}{(v^2+1)^2}=\frac{w_1(w_1^2-1)}{(w_1^2+1)^2}\]

And add the two equations together to get \(1\) equation in \(3\) variables:

\[\frac{2u(u^2-1)}{(u^2+1)^2}=\frac{w_0(w_0^2-1)}{(w_0^2+1)^2}+\frac{w_1(w_1^2-1)}{(w_1^2+1)^2}\]

Proving that no non-trivial rational triple of \((u,w_0,w_1)\) that satisfies the above relation, suffices to prove that no Magic Square of Squares exist.

(Trivial solutions to this relation are all cases where \(\frac{2u(u^2-1)}{(u^2+1)^2}\), \(\frac{w_0(w_0^2-1)}{(w_0^2+1)^2}\), and \(\frac{w_1(w_1^2-1)}{(w_1^2+1)^2}\) are not distinct.)


4. Additional Notes

Proving that there is no non-trivial rational solution to \(\frac{u(u^2-1)}{(u^2+1)^2}+\frac{v(v^2-1)}{(v^2+1)^2}=\frac{w_0(w_0^2-1)}{(w_0^2+1)^2}\) proves that there are no non-trivial Magic Squares of Squares but does not prove that no non-trivial Magic Hourglasses of Squares exist. Similarly, a non-trivial triple would prove that a Magic Hourglass of Squares exists, but would not prove that a Magic Square of Squares exists.

The general function \(f(u)=\frac{u(u^2-1)}{(u^2+1)^2}\) has an interesting structure. All of the following are equal!

\[f(u)=-f(-u)=-f\left(\frac{1}{u}\right)=f\left(\frac{u+1}{u-1}\right)=f\left(\frac{1-u}{1+u}\right)\]

This means that we can confine our search to a rational triple \((u,w_0,w_1)\) in the open interval \((0,1)^3\)


5. Computational Results

In C++, using GMP and Farey Sequences, I conducted a search over all possible positive rational pairs \((u,v)\) with denominators less than or equal to \(3000\) where \(Y=-\frac{4u(u^2-1)}{(u^2+1)^2}\) and \(Z=-\frac{4v(v^2-1)}{(v^2+1)^2}\) such that both \(\sqrt{1-Y-Z}\) and \(\sqrt{1+Y+Z}\) exist and \(0\le v\le u\le \sqrt{2}-1\) for nontrivial solutions.

My program ran for ~\(132\) hours, checked \(155,228,794,012\) pairs, and found the following:

\(\sqrt{1-Y-Z}\) is a nontrivial rational \(445\) times.

\(\sqrt{1-Y+Z}\) is a nontrivial rational \(435\) times.

\(\sqrt{1+Y+Z}\) is a nontrivial rational \(1933\) times.

\(\sqrt{1+Y-Z}\) is a nontrivial rational \(802\) times.

There are no pairs in this search such that \(2\) or more of these expressions are nontrivial rationals at the same time.

While this is not a proof, it certainly lends some experimental evidence to the conjecture that no \(3 \times 3\) Magic Square of Squares exists.

A full dataset of these pairs can be downloaded here as a text file: magic_pairs_3000.txt


Email: zachdestefano@gmail (dot) com

Back to My Recreational Math, Puzzles, and Ideas