MULTIMAGIE.COM - Wroblewski-Pfoertner magic squares, orders 42 and 44

Carré magique de cubes de nombres premiers, ordre 42
Carré magique de puissances 4, ordre 44

En 2007, Jaroslaw Wroblewski (Université de Wroclaw, Pologne) et Hugo Pfoertner (MTU Aero Engines, Allemagne) ont résolu deux intéressants et très difficiles problèmes :

premier carré magique connu de cubes de nombres premiers
premier carré magique connu de puissances 4 ayant un ordre plus petit que 243

Leur carré magique #1 résoud un de mes problèmes ouverts publiés dans The Mathematical Intelligencer en 2005. Et leur carré magique #2 améliore nettement le précédent record, leur ordre 44 étant bien plus petit que 243. Voici l'histoire de leurs découvertes, cinq parties dans cette page :

Le premier problème et son contexte
Le second problème et son contexte
Le travail de Wroblewski sur des solutions semi-magiques
Le travail final de Pfoertner sur les diagonales
Les solutions avec les deux carrés magiques (fichiers Excel téléchargeables)

Le premier problème et son contexte

En 2005, je donnais ces premiers carrés magiques connus 4x4 et 5x5 de nombres premiers dans le supplément de mon article sur les carrés magiques de carrés publié dans The Mathematical Intelligencer :

Le plus petit carré magique 4×4 de carrés de nombres premiers,
S2 = 509 020, par C. Boyer
29²	191²	673²	137²
71²	647²	139²	257²
277²	211²	163²	601²
653²	97²	101²	251²

Le plus petit carré magique 5x5 de carrés de nombres premiers,
S2 = 34 229, par C. Boyer
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²

Qu'est-ce qui est plus difficile que des carrés magiques de carrés ? Des carrés magiques de cubes ! C'est pourquoi, parmi les 10 problèmes ouverts publiés dans mon article, je posais celui-ci :

Problème ouvert 6 - Construire un carré magique de cubes de nombres premiers

Deux années après sa publication, Wroblewski et Pfoertner seront les premiers à résoudre ce problème !

Le second problème et son contexte

Démarré par Leonhard Euler en 1770 avec son carré magique 4x4 de carrés, et plus tard par Edouard Lucas en 1876 avec sa recherche infructueuse de carrés magiques 3x3 de carrés, le plus petit carré magique possible de n'importe quelle puissance est un problème extrêmement difficile : POUR N'IMPORTE QUELLE PUISSANCE > 1, ON NE SAIT PAS QUEL EST LE PLUS CARRE MAGIQUE POSSIBLE ! On ne sait pas si un carré magique 3x3 de carrés est possible. On ne sait pas si des carrés magiques 4x4 ou 5x5 ou 6x6 ou 7x7 ou 8x8 de cubes sont possibles, et ainsi de suite...

Avant le carré Wroblewski-Pfoertner, le plus petit carré magique de puissances 4 provenait du carré tétramagique 243x243 de Pan Fengchu (voir les records multimagiques) : quand les nombres d'un carré tétramagique sont élevés au carré, ou au cube, ou à la puissance 4, le carré magique reste toujours magique.

Plus petit carrés magiques connus de puissances
(avant le carré Wroblewski-Pfoertner de puissances 4)
Carré magique	Plus petit possible	Plus petit connu
de carrés	Inconnu ! Peut-être 3x3?	4x4 (L. Euler, 1770)
de cubes	Inconnu ! Peut-être 4x4?	9x9 (C. Boyer, 2006)
de puissances 4	Inconnu !	243x243 (du carré tétramagique de Pan Fengchu, 2004)
de puissances 5	Inconnu !	729x729 (du carré pentamagique de Li Wen, 2003)

Si l'on ne tient pas compte des diagonales (c'est-à-dire rechercher des carrés semi-magiques au lieu des carrés magiques), alors on connaît quelques réponses à la question des plus petits possibles. Par exemple on connaît des carrés semi-magiques 3x3 de carrés, et des carrés semi-magiques 4x4 de cubes. Concernant notre problème ici avec des puissances 4, on connaît des carrés semi-magiques 4x4, 8x8, 9x9.

Premier et plus petit carré semi-magique connu 4x4 de puissances 4,
S4 = 2 072 924 729 248 210 594,
par L. Morgenstern - C. Boyer
14101⁴	938⁴	931⁴	37762⁴
35866⁴	20881⁴	21038⁴	13393⁴
24806⁴	30191⁴	30418⁴	9263⁴
413⁴	32026⁴	31787⁴	1106⁴

L'écart entre les plus petits carrés semi-magiques et magiques de puissances 4 était incroyablement grand : 4x4 contre 243x243. Ma question posée dans ce site était :

Qui construira un carré magique de puissances 4 plus petit que 243x243 ?

Wroblewski et Pfoertner seront les premiers à résoudre ce problème !

Le travail de Wroblewski sur des solutions semi-magiques

Jaroslaw Wroblewski (Wroclaw 1962 -)
jouant pendant la "LVII Olimpiada Matematyczna" de Pologne, en 2006. Cliquer sur l'image pour l'agrandir.

Jaroslaw Wrobleski & Jean-Charles Meyrignac ont été l'équipe gagnante du concours de programmation de Al Zimmermann de mars-mai 2007 nommé "recherche de carrés multiplicatifs pandiagonaux Kurchan". Ils ont gagné les trois parties du concours : voir http://www.recmath.org/contest/Kurchan/index.php. Précédemment, en février 2006, Jaroslaw Wrobleski avait été la première personne capable de construire un carré bimagique plus petit que 8x8 : un résultat attendu depuis longtemps, depuis 1890 ! Voir son carré bimagique 6x6.

Réutilisant son code gagnant du concours de Zimmermann, mais modifié pour les deux problèmes décrits plus haut, il a réussi à produire deux carrés semi-magiques, le 6 juin 2007. Comme il le dit, c'est une "conséquence du concours".

S42.TXT, un carré semi-magique 42x42 de cubes de nombres premiers consécutifs (de 11^3 à 1537^3, S3 = 33151363766492)
S44.TXT, un carré semi-magique 44x44 de puissances 4 consécutives (de 1^4 à 1936^4, S4 = 123784061778806)

Voici quelques-uns de ses commentaires sur la méthode utilisée pour S42.TXT :

1) Choisir des nombres premiers de façon à ce que la somme magique = (sum_of_primes)/(matrix_size) soit entière et de même parité que la taille du carré (les nombres premiers sont impairs).
2) Placer les nombres au hasard et optimiser.
Ma routine d'optimisation prend deux lignes et échange quelques-uns de leurs nombres de façon à ce qu'aucun nombre ne change de colonne mais qu'une des lignes devienne aussi proche que possible de la somme magique. Alternativement elle prend deux colonnes et fait une optimisation similaire sur elles. Apparemment cela converge vers un carré semi-magique quand les termes sont bien en dessous de 2^(matrix_size). Actuellement je peux travailler sur des tailles jusqu'à 51, peut-être pourrais-je obtenir un peu plus grand, mais cela nécessiterait d'écrire une autre routine.
Je suis persuadé qu'il est possible de permuter les lignes et colonnes pour obtenir deux diagonales magiques, mais je n'ai pour l'instant aucun programme qui pourrait le faire.

Ces carrés semi-magiques ne sont pas des carrés magiques. Qui sera capable de trouver deux diagonales magiques ? Ce difficile problème sera résolu par Hugo Pfoertner.

Le travail final de Pfoertner sur les diagonales

Hugo Pfoertner (Rosenheim 1950 -)
Photo à une conférence conference de la Research and Technology Organization de l'OTAN, Budapest, 2005. Cliquer sur l'image pour l'agrandir.

Comme Jaroslaw Wroblewski, Hugo Pfoertner a aussi été un excellent compétiteur des trois parties du même concours Al Zimmermann : ses classements finaux sont 13ème (partie maximale), 5ème (partie minimale), et 4ème (partie Kurchan). Hugo est employé dans l'équipe de recherche et développement de MTU Aero Engines, Allemagne. Pendant son temps libre, il aime résoudre des problèmes mathématiques à l'aide d'ordinateurs : voir www.pfoertner.org.

Trouver deux diagonales magiques dans un carré semi-magique est un difficile problème. Imaginez qu'il y a 44! = 2.66*10^54 diagonales possibles dans un carré semi-magique 44x44, et que la probabilité de découvrir deux diagonales qui se croisent et qui ont la somme correcte, aussi grosse que 123784061778806 pour le 44x44, est extrêmement faible.

Hugo Pfoertner a démarré sur le plus petit carré, 42x42, et a réussi un mois plus tard à trouver deux bonnes diagonales, le 9 juillet : le premier problème était résolu ! Pour ce premier carré, le temps total de CPU a été de quatre semaines sur jusqu'à dix CPUs (Itanium-2 ou Pentium 3.4GHz).

Et le 8 octobre 2007, je recevais ce message d'Hugo :

Le problème 44x44 de puissances 4 est maintenant résolu. Cela a demandé un effort assez massif de calculs pour obtenir les bonnes permutations. La recherche d'une diagonale correcte par des permutations de lignes a démarré le 11 juin et a produit une bonne matrice le 27 août. En utilisant cette matrice comme point de départ, des permutations simultanées de lignes/colonnes ont produit une bonne antidiagonale le 7 octobre.
La plupart du temps le programme de permutation tournait sur 57 processeurs d'un machine SGI de 5 ans http://www.sgi.com/products/remarketed/origin3000. Cet ordinateur, prévu pour être retiré, était un des fers de lance du département R&D de MTU. Puisque son démantèlement était planifié, seulement une charge mineure de travail restait sur cette machine. Additionnellement le temps inoccupé des 14 processeurs des machines SGI Altix machines était utilisé http://www.sgi.com/products/remarketed/altix350. Le temps accumulé de CPU pour trouver la première diagonale a été de 148 mois de CPU sur les processeurs Origin 3000 et 22,4 mois de CPU sur les processeurs Itanium-2 des machines Altix. Trouver l'antidiagonale correcte a pris 80 mois de CPU months sur l'Origin 3000 et 17,5 mois de CPU sur l'Altix 350.
Au total, 18,8 années de CPU ont été passées sur l'Origin 3000 et 3,3 années de CPU sur l'Altix 350. Le carré magique obtenu est probablement un des membres les plus onéreux de l'espèce ;-)

Hugo Pfoertner remercie son employeur, MTU Aero Engines, pour lui avoir laissé l'accès à ces importantes ressources de calcul.

http://www.mtu.de/en/index.html

Les solutions avec les deux carrés magiques

Voici les deux excellents et impressionnants carrés de Wroblewski-Pfoertner :

Télécharger le carré magique 42x42 de cubes de nombres premiers (fichier Excel zippé, 69Ko)
Télécharger le carré magique 44x44 de puissances 4 (fichier Excel zippé, 34Ko)

Avec leur premier carré, mon Problème ouvert 6 est maintenant résolu. Et avec leur second carré, la table des records vue ci-dessus peut maintenant être mise à jour :

*Etat en octobre 2007 des plus petit carrés magiques connus de puissances*
Carré magique	Plus petit possible	Plus petit connu
de carrés	Inconnu ! Peut-être 3x3?	4x4 (L. Euler, 1770)
de cubes	Inconnu ! Peut-être 4x4?	9x9 (C. Boyer, 2006)
de puissances 4	Inconnu !	44x44 (J. Wroblewski - H. Pfoertner, 2007)
de puissances 5	Inconnu !	729x729 (du carré pentamagique de Li Wen, 2003)

Mais peut-être que d'autres personnes essaieront d'améliorer leurs résultats, avec des carrés plus petits que 44x44 ou 42x42 ? Si oui, envoyez-moi un message !

Comme conclusion (temporaire ?), quelques remarques de Jaroslaw:

Il est connu qu'il existe un carré magique 12x12 de cubes de nombres premiers, mais la preuve n'est pas constructive (prendre le carré trimagique 12x12 connu; prendre 144 nombres premiers en progression arithmétique que l'on sait exister grâce au théorème Green-Tao; puis remplacer chaque nombre 'n' dans le carré trimagique par le 'n'-ème terme de la progression).
Je ne vois actuellement pas comment je peux significativement décroître la taille 42x42 de l'exemple connu, avec l'approche que j'ai utilisé.

IMPORTANT! L'état ci-dessus de 2007 a maintenant changé, avec de nouveaux plus petits carrés magiques de cubes, puissances 4 et puissances 5 ! Voir ici.

Retour à la page d'accueil http://www.multimagie.com