Almost-magic squares of squares

In the last post we saw that every 3×3 almost-magic square is a rearrangement of three three-term arithmetic progressions that have the same common difference. In other words, if we pick any three numbers x, y and z, and any common difference d, then the nine numbers

xd, x, x+d
yd, y, y+d
zd, z, z+d

can be rearranged to make an almost-magic square

x z+d y-d
z-d y x+d
y+d x-d z

where all the rows and columns, and the leading diagonal, add up to x+y+z.

We’re interested in finding almost-magic squares where all the entries are square numbers, so that means we’re particularly interested in three-term arithmetic progressions of squares. Fortunately there is a well-developed theory of these things, which are closely related to Pythagorean triples.

A useful simplification is that it’s okay to look for almost-magic squares whose entries are the squares of rational numbers, rather than necessarily integers. If we can find such a thing we will just multiply all its entries by their common denominator, and then the entries will be whole numbers.

So we’re looking for rational numbers a, b and c where

c² – b² = b² – a²

or in other words,

a² + c² = 2b²

Now, if we can find rational numbers x, y with

x² + y² = 2

then we can take (abc) = (bxbby) for any arbitrary b. So it will suffice to find the rational points on the circle x² + y² = 2.

There are four obvious such points, namely (±1, ±1). The trick for finding the others is to draw a line through one of the points we know, say (1, 1). This line will intersect the circle in one other point, and then we can parametrise all the rational points on the circle using the slope of the line as a parameter.

circle

If you substitute y = (x-1)t + 1 into x² + y² = 2 then you get a quadratic equation in x. One solution is x=1, of course, and the other turns out to be

\displaystyle x=\frac{t^2-1-2t}{t^2+1}.

Then computing y = 2-x² gives

\displaystyle y=\frac{t^2-1+2t}{t^2+1}.

So the general form for a three-term arithmetic progression of rational squares is the squares of:

\displaystyle q(t^2-1-2t),\quad q(t^2+1),\quad q(t^2-1+2t).

where t and q are arbitrary rational numbers. For example, if we pick q=1 and t=2, we get -1, 5, 7, and indeed (-1)², 5², 7² = 1, 25, 49 is an arithmetic progression. Elementary (but surprisingly tedious) algebra shows that the common difference is 4q²(t³-t).

So, we can use this to generate as many three-term arithmetic progressions of squares as we could possibly want. But we need something more: we need a way to find multiple such progressions that have the same common difference. This is where it starts to get interesting.

We’re going to try to find a way to generate all the three-term arithmetic progressions of squares that have a fixed common difference d. By the characterisation above, this amounts to finding t and q such that

\displaystyle d=4q^2(t^3-t).

Although it may not look like it yet, this equation defines what’s known as an elliptic curve, which turns out to be very useful because elliptic curves are reasonably well-understood mathematical objects. To make it look more like the way elliptic curves are usually written, first we’ll divide by 4q²:

\displaystyle \Bigl(\frac{1}{2q}\Bigr)^2d=t^3-t.

then multiply by d³:

\displaystyle \Bigl(\frac{d^2}{2q}\Bigr)^2=(dt)^3-d^2(dt).

If we now introduce new variables y=\frac{d^2}{2q} and x=dt, we get something that looks very much like the equation of an elliptic curve:

\displaystyle y^2=x^3-d^2x.

The remarkable thing about elliptic curves is that the rational points form an Abelian group. That is, there is a rule for “adding” two rational points to get another one. More than that, this group is finitely generated, which means it’s possible to make any rational point by starting with a finite set of generators and “adding” them together. Even better, there are algorithms that can often (though not always) compute the generators explicitly.

There is something else to notice about this equation. The right-hand side can be factored as

\displaystyle (x-d)x(x+d).

and the equation says that this product is a square. If x is the middle term of a three-term arithmetic progression of squares with common difference d then (x-d), x and x+d are all squares, so their product certainly is. In other words, the middle term of a three-term arithmetic progression of squares with common difference d is always the x coordinate of a rational point on the curve.

On the other hand, the converse isn’t true. If d=6 and x=12 then

\displaystyle (x-d)x(x+d)=6\times12\times18=36^2,

so (12, 36) is a point on the curve; but none of 6, 12, 18 are squares.

So it’s natural to ask which of the curve points have x-coordinates that are in the middle of a three-term arithmetic progression of squares with common difference d. The answer turns out to be expressible very neatly in terms of the “addition” operation in the elliptic curve group. If you look up the formula for “point doubling” on an elliptic curve, and work out what it means for our curve, it turns out that the x-coordinate of (x,y)⊕(x,y) is

\displaystyle \frac{(x^2+d^2)^2}{4y^2}.

Substituting y=\frac{d^2}{2q} and x=dt, this simplifies to

\displaystyle q^2(t^2+1)^2.

which is precisely the middle term of the arithmetic progression we started with! So a curve point has an x-coordinate that is the centre of a three-term arithmetic progression of squares if and only if it is the “double” of another point: and the point it’s the double of is the one that we used to represent this arithmetic progression in the first place.

This gives us a very easy way to extract an arithmetic progression from a curve point: simply double the point and take its x-coordinate.

At this point we’ll turn to the computer algebra system Sage, which has good implementations of the basic elliptic curve algorithms. It’s free, and you can download it from SageMath.org. Its programming language is based on Python, and it uses the Python interpreter internally.

As a first example, let’s take d=6. We’ll define a variable in Sage:

d = 6

then use that to define our elliptic curve:

E = EllipticCurve([-d^2, 0])

If you type E at this point, it should output:

Elliptic Curve defined by y^2 = x^3 - 36*x over Rational Field

which is the elliptic curve we wanted. Now we’ll ask Sage to compute the generators of the curve group, and print them out:

gens = E.gens()
gens

It should say [(-3 : 9 : 1)], meaning that there is one generator, the point (-3, 9). Let’s extract this into a variable g for convenience, and print out the “double point” g+g:

g = gens[0]
g+g

It should print (25/4 : -35/8 : 1). If we’ve got everything right, that should mean that 25/4 is the centre of an arithmetic progression of squares with common difference d. Let’s check:

x = (g+g).xy()[0]
is_square(x - d)
is_square(x + d)
(x-d, x, x+d)

This should print True twice, and then the progression

(1/4, 25/4, 49/4)

Now we can make infinitely many other arithmetic progressions of squares with the same common difference d simply by adding the generator g to itself. Let’s define a simple function to return the arithmetic progression corresponding to a curve point in a nice format:

def progression(curve_point):
    x = (curve_point + curve_point).xy()[0]
    return "(%s)^2, (%s)^2, (%s)^2" % (sqrt(x-d), sqrt(x), sqrt(x+d))

Now we can print the first three arithmetic progressions with common difference d:

for i in range(1, 4):
    print progression(i*g)

This will print:

(1/2)^2, (5/2)^2, (7/2)^2
(1151/140)^2, (1201/140)^2, (1249/140)^2
(4319999/2639802)^2, (7776485/2639802)^2, (10113607/2639802)^2

If we multiply up by the common denominator, which is 184786140, we get three arithmetic progressions of squares that have the same common difference. Let’s code this generically:

def print_progressions(curve_points):
    xs = [ (p + p).xy()[0] for p in curve_points ]
    common_denominator = reduce(lcm, [ x.denominator() for x in xs ])
    for x in xs:
        print "%s^2, %s^2, %s^2" % tuple((
            sqrt(v * common_denominator) for v in [x-d, x, x+d]
        ))

print_progressions([ i*g for i in range(1, 4) ])

It should print:

92393070^2, 461965350^2, 646751490^2
1519206051^2, 1585201101^2, 1648556349^2
302399930^2, 544353950^2, 707952490^2

which makes the almost-magic square:

461965350² 707952490² 1519206051²
302399930² 1585201101² 646751490²
1648556349² 92393070² 544353950²

It would take quite a while to find this by a brute-force search!

Obviously you can repeat this procedure to find as many almost-magic squares of squares as you could possibly want. Some values of d don’t yield any at all, but there are many that do: in fact the values of d that do are known as congruent numbers.

There may also be more than one generator. The first place this happens is d=34:

d = 34
E = EllipticCurve([-d^2, 0])
gens = E.gens()
gens

This is fun, because it allows us to combine them in more interesting ways. Let’s call the two generators g1 and g2:

g1, g2 = gens
print_progressions([g1, g2, g1 + g2])

which gives:

448756^2, 3370444^2, 4745356^2
6062980^2, 6922300^2, 7686140^2
3305605^2, 4699525^2, 5765765^2

Or

print_progressions([g1 - g2, g1 + g2, 2*g1])
7065633890590^2, 13757701009250^2, 18128030556130^2
11681621314215^2, 16607571505575^2, 20375538915495^2
61295378092674^2, 62421747254526^2, 63528148761726^2

The smallest example actually comes from d=210, which also gives a curve with two generators:

d = 210
E = EllipticCurve([-d^2, 0])
g1, g2 = E.gens()
print_progressions([g1, g2, g1+g2])
46^2, 74^2, 94^2
2^2, 58^2, 82^2
97^2, 113^2, 127^2

The next-smallest is print_progressions([g1, g2, g1-g2]) where g1, g2 are the generators of the curve with d=330.

If you’re looking to find a fully magic square of squares, this seems like a sensible place to start. You just need to find three points on one of these elliptic curves whose doubles have their x-coordinates in arithmetic progression. But be warned that several people have looked quite hard, and no one has yet found one!

Further reading

Bremner, Andrew. “On squares of squares.” ACTA ARITHMETICA 88 (1999): 289-297.

Bremner, Andrew. “On squares of squares II.” ACTA ARITHMETICA 99.3 (2001): 289-308.

Bremner, Andrew, Joe H. Silverman, and N. Tzanakis. “Integral points in arithmetic progression on y² = x(x²−n²).” Journal of Number Theory 80.2 (2000): 187-208.

Conrad, Keith. “Arithmetic progressions of three squares.” (2008).

Robertson, John P. “Magic squares of squares.” Mathematics Magazine 69.4 (1996): 289-293.

This entry was posted in chatter, Mathematics. Bookmark the permalink.

2 Responses to Almost-magic squares of squares

  1. Pingback: Magic squares of squares: Part I | Bosker Blog

  2. Pingback: Squares of squares, and the group of rational points on the circle | Bosker Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s