Magic square of cubes of prime numbers, order 42
Magic square of fourth powers, order 44

In 2007, Jaroslaw Wroblewski (University of Wroclaw, Poland) and Hugo Pfoertner (MTU Aero Engines, Germany) solved two interesting and very difficult problems:

1. first known magic square of cubes of prime numbers
2. first known magic square of fourth powers having an order smaller than 243

Their magic square #1 solves one of my open problems published in The Mathematical Intelligencer in 2005. And their magic square #2 greatly improves the previous record, their order 44 being far smaller than 243. Here is the story of their discoveries, five parts in this page:

The first problem and its context

In 2005, I gave these first known 4x4 and 5x5 magic squares of squares of prime numbers in the Supplement of my paper on magic squares of squares published in The Mathematical Intelligencer:

 29² 191² 673² 137² 71² 647² 139² 257² 277² 211² 163² 601² 653² 97² 101² 251²

 11² 23² 53² 139² 107² 13² 103² 149² 31² 17² 71² 137² 47² 67² 61² 113² 59² 41² 97² 83² 127² 29² 73² 7² 109²

What is more difficult than magic squares of squares? Magic squares of cubes! That's why, among the 10 open problems published in my paper, I asked this one:

Open problem 6 - Construct a magic square of cubes of prime numbers

Two years after its publication, Wroblewski and Pfoertner will be the first to solve this problem!

The second problem and its context

Started by Leonhard Euler in 1770 with his 4x4 magic squares of squares, and later by Edouard Lucas in 1876 with his unsuccessful search of 3x3 magic squares of squares, the smallest possible magic square of any power is an extremely difficult problem: ON ANY POWER > 1, WE DO NOT KNOW WHAT THE SMALLEST POSSIBLE MAGIC SQUARE IS! We don't know if a 3x3 magic square of squares is possible. We don't know if 4x4 or 5x5 or 6x6 or 7x7 or 8x8 magic squares of cubes are possible, and so on...

Before the Wroblewski-Pfoertner square, the smallest known magic square of 4th powers was coming from the 243x243 tetramagic square of Pan Fengchu (see the Multimagic records): when the numbers of a tetramagic square are squared, or are cubed, or are raised to the 4th power, the magic square is still magic.

 Magic square Smallest possible Smallest known of squares Unknown! Maybe 3x3? 4x4 (L. Euler, 1770) of cubes Unknown! Maybe 4x4? 9x9 (C. Boyer, 2006) of 4th powers Unknown! 243x243 (from the tetramagic squareof Pan Fengchu, 2004) of 5th powers Unknown! 729x729 (from the pentamagic squareof Li Wen, 2003)

If we don't take care of the diagonals (meaning searching semi-magic squares instead of magic squares), then we know some answers on the smallest possible question. For example we know 3x3 semi-magic squares of squares, and 4x4 semi-magic square of cubes. On our problem here with 4th powers, we know 4x4, 8x8, 9x9 semi-magic squares.

 141014 9384 9314 377624 358664 208814 210384 133934 248064 301914 304184 92634 4134 320264 317874 11064

The gap between the smallest known semi-magic and magic squares of 4th powers was incredibly large: 4x4 versus 243x243. My question asked in this website was:

Who will construct a magic square of 4th powers smaller than 243x243?

Wroblewski and Pfoertner will be the first to solve this problem!

The Wroblewski's work on semi-magic solutions

Jaroslaw Wroblewski (Wroclaw 1962 -)
playing during the "LVII Olimpiada Matematyczna" of Poland, in 2006. Click on the image to enlarge it.

Jaroslaw Wroblewski & Jean-Charles Meyrignac was the winning team of the Al Zimmermann's programming contest of March-May 2007 called "searching Kurchan pandiagonal multiplicative squares". They won the three parts of the contest: look at http://www.recmath.org/contest/Kurchan/index.php. Previously, in February 2006, Jaroslaw Wroblewski was the first person able to construct a bimagic square smaller than 8x8: a long-awaited result, since 1890! Look at his 6x6 bimagic square.

Reusing his winning code of the Zimmermann's contest, but modified for the two above problems, he succeeded to produce two semi-magic squares, June 6th 2007. As he said, it is a "byproduct of the contest".

• S42.TXT, a 42x42 semi-magic square of cubes of consecutive prime numbers (from 11^3 to 1537^3, S3 = 33151363766492)
• S44.TXT, a 44x44 semi-magic square of consecutive fourth powers (from 1^4 to 1936^4, S4 = 123784061778806)

Here are some of his comments on the used method for S42.TXT:

1) Pick the primes so that the magic sum = (sum_of_primes)/(matrix_size) is integer and of the same parity as the square size (primes are odd).
2) Place the entries at random and keep optimizing.
My optimizing routine takes 2 rows and swaps some of the entries in those rows so that no entry changes it's column and one of the rows gets as close to magic sum as possible. Alternately it takes 2 columns and does a similar optimization on them. Apparently it converges to a semi-magic square when the terms are well below 2^(matrix_size). Currently I can work on sizes up to 51, perhaps I could get a bit higher, but it would require writing another routine.
I strongly believe that it is possible to permute rows and columns to get both diagonals magic, but at the moment I have no program that could do that.

These semi-magic squares are not magic squares. Who would be able to find two magic diagonals? This difficult problem will be solved by Hugo Pfoertner.

The Pfoertner's final work on the diagonals

Hugo Pfoertner (Rosenheim 1950 -)
Photo of a conference of the NATO Research and Technology Organization, Budapest, 2005. Click on the image to enlarge it.

As Jaroslaw Wroblewski, Hugo Pfoertner was also an excellent competitor on the three parts of the same Al Zimmermann's contest: his final placings are 13th (maximal part), 5th (minimal part), and 4th (Kurchan part). Hugo is employed in the research and development of MTU Aero Engines, Germany. In his leasure time, he enjoys solving mathematical problems using computers: look at www.pfoertner.org.

Finding two magic diagonals in a semi-magic square is a very difficult task. Imagine that there are 44! = 2.66*10^54 possible diagonals in a 44x44 semi-magic square, and that the probability to discover two crossing diagonals having the correct sum, as big as 123784061778806 for the 44x44, is extremely low.

Hugo Pfoertner started on the smaller square, 42x42, and one month later succeeded to find two good diagonals, July 9th: the first problem was solved! For this first found square, the total CPU time was four weeks on up to ten CPUs (Itanium-2 or 3.4GHz Pentium).

And October 8th, 2007, I received this message from Hugo:

The 44X44 4th-power square problem is now solved. It took a rather massive computational effort to find the required permutations. Searching for the correct diagonal by row permutations started on June 11 and produced a matching matrix on August 27. Using this matrix as a starting point, simulaneous row/column permutations produced a matching anti-diagonal on October 7.
Most of the time the permutation program was running on 57 Processors of a 5 years-old SGI machine
http://www.sgi.com/products/remarketed/origin3000. This computer, which was scheduled for retirement, used to be one of the workhorses in MTU's R&D department. Due to its planned disassembly only a minor regular workload had remained on the machine. Additionally the idle time on 14 Processors of SGI Altix machines was used http://www.sgi.com/products/remarketed/altix350. The accumulated CPU times to find a matrix with matching diagonal were 148 CPU months on Origin 3000 processors and 22.4 CPU month on the Itanium-2 processors of the Altix machines. Finding the correct antidiagonal took 80 CPU months on the Origin 3000 and 17.5 CPU months on the Altix 350.
In total 18.8 CPU years were spent on the Origin 3000 and 3.3 CPU years on the Altix 350. The resulting magic square is probably one of the more expensive members of this species ;-)

Hugo Pfoertner thanks his employer, MTU Aero Engines, for giving him access to these significant computational resources.

The solutions with the two magic squares

Here are these two excellent and impressive Wroblewski-Pfoertner's squares:

With their first square, my Open problem 6 is now solved. And with their second square, the table of the records seen above can now be updated:

 Magic square Smallest possible Smallest known of squares Unknown! Maybe 3x3? 4x4 (L. Euler, 1770) of cubes Unknown! Maybe 4x4? 9x9 (C. Boyer, 2006) of 4th powers Unknown! 44x44 (J. Wroblewski - H. Pfoertner, 2007) of 5th powers Unknown! 729x729 (from the pentamagic square of Li Wen, 2003)

But maybe other people will try to improve their results, with squares smaller than 44x44 or 42x42? If yes, send me a message!

As a (temporary?) conclusion, some remarks from Jaroslaw:

It is known that there exist 12x12 magic-square-of-cubes-of-primes, but the proof is not constructive (take the known trimagic 12x12; take 144 primes in arithmetic progression that exist by Green-Tao theorem; then replace each number 'n' in trimagic with 'n'-th term of the progression).
At the moment I do not see how one could significantly decrease 42x42 size of known example with the approach I used.

IMPORTANT! The above status of 2007 has now changed, with new smaller magic squares of cubes, 4th powers and 5th powers! Look here.