IS THERE any rhyme or reason to magic squares? Most mathematicians would probably say not. Yet these grids of numbers have fascinated people for centuries. Each entry in the grid is different but, miraculously, every row, every column, and every diagonal add up to the same number. To some, the purported mystical significance of magic squares puts them on a par with crystals and gems: Feng shui masters, for instance, use a 3-by-3 magic square called the lo shu to arrange furniture. Hindu mystics carved 4-by-4 magic squares into the walls of the erotic temples at Khajuraho. Artists from Albrecht Dürer to Antonio Gaud’ have incorporated them into their work. Benjamin Franklin, the American polymath, delighted in creating huge magic squares as a kind of mental exercise. So how come professional mathematicians have always remained unenthusiastic about magic squares?
Perhaps magic squares just didn’t have much to do with mainstream mathematical theories. But that has now changed. Like geologists discovering a gold mine from just a few nuggets, mathematicians have begun a systematic exploration of the rich vein of magic squares that lies beneath those found by amateurs. Using powerful tools from algebra and geometry, they can now predict exactly how many magic squares of a given type are out there. Where once the search depended only on your own wits, mathematics can now give you a good idea where to look, and how.
Legend has it that the lo shu (below) was the first magic square, turning up in the markings on the back of a tortoise in the Lo river in China, sometime in the second millennium BC. Add any row, or any column, or any of the two diagonals, and you get the same “magic sum” – 15. Such tables are not easy to find. In fact, there are only eight of them that use each number from 1 to 9 exactly once, and all are simply reflected or rotated versions of the lo shu.
Advertisement
A magic square from the 12th-century temple at Khajuraho in India gives an idea of the extra possibilities offered by a 4-by-4 square:
The rows, columns and diagonals of this square add up to 34, but there’s a new twist. Place the table next to copies of itself, and it creates an infinite “magic carpet”: any four adjacent entries along a straight line – horizontal, vertical or diagonal – sum to 34. But that’s not all. The corners of any 4-by-4 subsquare also sum to 34, as do the four corners of any 3-by-3 subsquare, and likewise those of any 2-by-2 subsquare.
Squares with the magic-carpet property were called pandiagonal. Soon they were joined by antimagic squares – in which all the row, column and diagonal sums were different – and by nested and knight’s-tour magic squares, in which each number from 1 to 64 is a chess knight’s move apart from the next one. There was even a magic square that stays magic when you read the numbers upside down:
Perhaps the most famous inventor of magic squares was the American statesman and scientist Benjamin Franklin, who wrote in his autobiography, “In my younger days, having once some leisure which I still think I might have employed more usefully, I…amused myself in making these kind of magic squares.” One of them was the following 8-by-8 marvel:
Franklin’s square is not magic in the usual sense, because the two diagonals fail to add up to the row and column sum of 260. But it has a plethora of other wonderful properties. Every boomerang-shaped “bent diagonal” adds to 260 (for example, 52 + 3 + 5 + 54 + 10 + 57 + 63 + 16), and this remains true when the square is turned into a carpet. Every half-row and half-column adds to half the magic sum, as does any 2-by-2 subsquare. Franklin also found a 16-by-16 square with similar properties, which, abandoning modesty, he called “the most magically magical of any magic square ever made by any magician”.
Meanwhile, a few mathematicians took up the problem of determining how many magic squares of any given size there are. But after the 3-by-3 squares, of which there are eight, and 4-by-4 squares, of which there are 880 (first listed in 1693 by Bernard Frénicle de Bessy), they were stuck. And there things remained for a couple of centuries.
Then, using a tried-and-trusted trick, mathematicians broke the impasse. And what was this clever trick? They changed the rules to make their lives easier.
In 1915, Percy MacMahon, a British army captain turned mathematician,re-started progress with magic squares by weakening two of the constraints placed on them. First, he allowed the entries to be “non-distinct” and “non-consecutive”: they didn’t have to be composed from an uninterrupted series of integers with no repeats, as the original magic squares had always been. Such a square is now called weak magic; a strong magic square is the original kind, with distinct (but not necessarily consecutive) entries. Second, he tossed out the condition on diagonals, requiring only the row sums and column sums to be the same. Such squares are now called semi-magic.
In 1915, MacMahon published formulae for the number of 3-by-3 weak semi-magic and weak magic squares. Because the entries were no longer required to be distinct or consecutive, the magic sums could be either greater than or less than the lo shu’s 15. In fact, the smallest possible sum is 0, as in this rather Zen-like square:
Because the magic sum was no longer fixed, MacMahon treated it as a variable in his formulae. They came out as a type of mathematical expression called a polynomial – a finite sequence of additions and multiplications of the variable. The number of weak semi-magic squares with magic sum t was (t + 1)(t + 2)(t2 + 3t + 4)/8. Inserting t = 0, for instance, gives 1 x 2 x 4/8 = 1, which confirms that the Zen square is clearly the only such square possible.
The form of MacMahon’s result – a polynomial whose variable is the magic sum – was the start of something big. In 1973, MIT mathematician Richard Stanley and French high-school teacher Eugène Ehrhart independently showed that the number of weak semi-magic squares of any fixed size, with the magic sum t treated as a variable, is a polynomial of t. It became known as an Ehrhart polynomial. Stanley and Ehrhart also vindicated MacMahon’s line of attack by showing that the number of weak magic squares, in contrast, is given by a much more complicated kind of formula called a quasipolynomial. In neither case, though, could they actually work out the formulas.
But, remarkably, Ehrhart did eventually achieve this by converting the problem of counting magic squares to a problem in geometry. Imagine cutting out a piece of fabric whose threads cross vertically and horizontally. Your cuts do not have to be vertical or horizontal, but they do have to be straight. How many “checks” – places where two of the fabric’s threads cross – are there in your piece? Obviously, it depends in some way on the thread count per centimetre.
Ehrhart’s result exactly pins down the nature of this dependence: if you treat the thread count as an unknown quantity, say t, then the number of checks is a polynomial or a quasipolynomial with t as the variable – no matter what shape, or “polytope”, you have cut out. This is also true in higher-dimensional space, which is fortunate because you can think of semi-magic squares as being cut out of a “fabric” that is four-dimensional or more.
It works like this: the conditions that each entry in the semi-magic square must satisfy – being at least zero, and so on – play the role of the cuts in the fabric. The magic sum corresponds to the thread count. Each check corresponds to a different magic square, and the polynomial that counts the number of checks is the same as the Ehrhart polynomial that counts the number of magic squares. Stanley and Ehrhart found, for instance, that the 3-by-3 semi-magic squares with magic sum t all lie inside a four-dimensional polytope whose size depends on t.
Stanley and Ehrhart were not able to work out the exact formulae for 4-by-4 and larger squares, but advances in theory and computing since 1973 have made that possible. In the mid-1990s, Alexander Barvinok of the University of Michigan in Ann Arbor developed an efficient way to compute Ehrhart polynomials. And Jesús De Loera of the University of California at Davis has since coded Barvinok’s method into a computer program called LattE. Using LattE, he and collaborators Maya Ahmed and Raymond Hemmecke have computed the number of magic squares of several different types.
Most spectacular among these computations is Ahmed’s still unpublished work on 8-by-8 “Franklin squares”. It turns out that they are far more common than Franklin would ever have suspected – there are about 228 trillion weak Franklin squares with magic sum 260. How many of them are also strong Franklin squares (that is, with entries from 1 to 64) remains unknown, but she has found three that Franklin didn’t know about.
Meanwhile, Matthias Beck of the Mathematical Sciences Research Institute in Berkeley, California, and Thomas Zaslavsky at the State University of New York at Binghamton have turned their attention to the long-neglected problem of counting strong magic squares – the kind that originally fascinated number enthusiasts. Beck and Zaslavsky have developed their own technique, using “inside-out polytopes”, for performing this count. Thus, for instance, there are eight 3-by-3 strong magic squares with magic sum 15 (the lo shu and its reflections and rotations); there are 24 3-by-3 strong magic squares with magic sum 18, and 32 with magic sum 21.
Benjamin Franklin, lamenting his misspent youth, wrote that magic squares were “incapable of any useful application”. But that’s not exactly true. Problems related to magic squares have abundant applications in tasks such as efficiently assigning personnel to jobs or the statistical analysis of drug trials. Barvinok’s algorithm can be applied to these problems just as readily as to magic squares.
But most people who like messing around with magic squares do it simply for the joy of discovering interesting patterns – and there are still plenty of discoveries waiting to be made (see “Making your own magic”). Happy hunting!
Making your own magic
How can you go about creating your own Franklin-style magic squares? Maya Ahmed has made one remarkable discovery that may help. Start with the 8-by-8 square laid out below:
This is a “pandiagonal” Franklin square, because all rows, columns, diagonals, bent diagonals and broken diagonals – where a diagonal goes out the top (or bottom) of the square, “wraps around” and comes back at the bottom (or top) at the same horizontal position – add up to 4. At the same time all 2-by-2 subsquares, half-rows and half-columns sum to 2. The Ahmed square has 16 variants that can be obtained by swapping any pairs of rows that are separated by one row and lie in the same half. For example, you could swap rows 1 and 3, rows 2 and 4, and rows 6 and 8. And rotating each of these squares by 90 degrees produces a further 16 variants, making a total of 32 variants of the basic Ahmed square.
The coolest thing about Ahmed’s squares is that you can combine them to make new pandiagonal squares. You can add any variant to another simply by laying it directly on top and adding the contents of each of the boxes. The resulting square will still be a pandiagonal Franklin square. In fact, every pandiagonal Franklin square can be built up from Ahmed squares in this way. If you do it 65 times, it’s just possible that every box will contain a different total – each number from 1 to 64 will appear exactly once. If so, congratulations: You have just found the most magically magical square of all time!