Projet de note soumis aux Comptes Rendus de l’Academie de Sciences

Sur l’énumeration des cubes magiques

Note de Miklós Bóna Présentée par Henri Cartan

Résumé - Dans cette note nous montrons quelques différences intéressantes entre les carrés magiques et les cubes magiques . L’introduction est consacrée à l’exposé des principaux résultats concernant le nombre H_{n}(r) des carrés magiques n × n (où n est fixe) en fonction de la somme de ligne r. Puis nous examinons la même question pour les cubes magiques n × n × n, et on obtient le résultat surprenant que la fonction correspondante de r n’est pas un polynôme , alors que H_{n}(r) est un polynôme . On en montre la raison principale et on décrit cette fonction.

On the number of the magic cubes

Abstract - In this note we point out some interesting differences between magic squares and magic cubes. In our Introduction we present the main results about the number H_{n}(r) of n × n magic squares (for fixed n) as a function of their line sums r. Then we shall examine the same question for magic cubes n × n × n and we shall prove that the correspondent function of r is not a polynomial. It is somewhat surprising because H_{n}(r) is a polynomial. We shall give an explanation of this fact and we shall describe that function.

1 Introduction

Dans ce chapitre nous nous sommes appuyé notamment sur les travaux de Richard P. Stanley dans [1].

Soit B une matrice de taille p × q et de rang p dont les éléments sont des entiers naturels. Soit E_{B} = {b ∈ N^{q} | Bb = 0}. Notons R_{B} l’algèbre du monoïde E_{B} sur un corps infini k. (Si t = t_{1}, …, t_{q}, alors nous écrivons t^{b} pour t_{1}^{b_{1}}t_{2}^{b_{2}} … t_{q}^{b_{q}}). Alors R_{B} est une k-algèbre de type fini, de plus, si on prend la forme irréductible de son polynôme de Hilbert F (R_{B}, t), on a :

F (R_{B}, t) = ∑_{b∈E_{B}} t^{b} = \frac{P (R_{B}, t)}{Π_{b∈CF (B)}(1 − t^{b})}

où P (R_{B}, t) est un polynôme , et b ∈ CF (B) si b ∈ E_{B} et mb = c+d , c, d ∈ E_{B}, m ∈ N impliquent c = ib, d = jb.

Soit H_{n}(r) le nombre des carrés magiques n × n à somme de ligne r. Il n’est pas difficile de voir que qu’il existe une matrice B de taille (2n−2)×n^{2} telle que E_{B} soit égal à l’ensemble des carrés magiques n × n. Le théorème Birkhoff-von Neumann nous dit qu’en ce cas CF (B) est égal à l’ensemble des matrices de permutation. Choisissons une telle matrice B et spécialisons la N^{n^{2}}-graduation de F (R_{B}, t) de la façon suivante: soit t = (t_{ij}) où 1 ≤ i, j ≤ n et remplaçons t_{ij} par x si i = 1 et par 0 si i ≠ 1. On obtient:

∑_{r≥0} H_{n}(r)x^{r} = \frac{P_{1}(x)}{(1 − x)^{n!}}

(où P_{1} ∈ Z[x]). Il est possible de prouver que le degré de P_{1} est inférieur à n!. Donc H_{n}(r) est un polynôme ; de plus, son degré est égal à (dimR_{B}) − 1 = (dim_{Q}E_{B}) − 1 = (n − 1)^{2}.

2 Les cubes magiques

Soit maintenant T_{n}(r) le nombre des cubes magiques n × n × n à somme de ligne r. On voit immédiatement que T_{n}(r) ≤ (r + 1)^{(n−1)^{3}} car les éléments d’un sous-cube (n − 1) × (n − 1) × (n − 1) déterminent tous les autres éléments de notre cube n × n × n.

Donc si T_{n}(r) était un polynôme , alors son degré ne pourrait être supérieur à (n − 1)^{3}. On a calculé les valeurs de T_{n}(r) pour n = 3, r = 0, 1, …, 9 et on a obtenu qu’il n’existait aucun polynôme P de degré ≤ 8 qui prenait ces valeurs à 0,1,…,9. Donc nous n’obtenons pas le même résultat que celui en dimension deux, c’est-à-dire, que T_{n}(r) n’est pas un polynôme .

Essayons de reproduire la démonstration qu’on a montrée en dimension deux. On voit facilement qu’il existe une matrice B de taille 3(n^{2} − n) × n^{3} pour laquelle E_{B} est égal à l’ensemble des cubes magiques. Le premier pas de cette ”démonstration” qui ne sera pas valide, c’est la description de l’ensmble CF (B).

Soit maintenant n = 3, nous voyons que le cube magique suivant n’est pas décomposable en somme de deux cubes magiques à somme de ligne 1 :

( \begin{matrix}2 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix} )

( \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} )

( \begin{matrix}0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix} )

Donc la situation est plus compliquée qu’en dimension deux; il n’est pas vrai que CF(B) est égal à l’ensemble des cubes magiques à somme de ligne 1. Un calcul fastidieux mais sans difficulté montre que le théorème suivant est vrai:

Théorème 1 Tout cube magique 3 × 3 × 3 est décomposable en somme de certains cubes magiques à somme de ligne 1 et de certains cubes magiques à somme de ligne 2.

Il est clair que cette décomposition n’est pas unique. On peut formuler ce résultat aussi de la façon suivante : la somme de ligne des éléments de CF (B) est ≤ 2. Ce résultat a déjà un point commun avec celui en dimension deux, puisqu’il démontre l’existence d’une certaine décomposition. Cela nous a encouragés à formuler le résultat suivant :

Théorème 2 Soient U(r) = T_{3}(2r) et V (r) = T_{3}(2r + 1). Alors U(r), V (r) ∈ Q[x], et degU(r) = degV (r) = 8.

Nous donnons l’esquisse de la démonstration pour U(r); elle est identique pour V (r). On sait du théorème 1 que tout cube magique à somme de ligne 2r est décomposable en somme de certains cubes magiques à somme de ligne 2. Soit s = T_{3}(2) = 132, et notons les cubes magiques à somme de ligne 2 par a_{1}, a_{2}, …, a_{132}. Cette décomposition n’est pas unique; il existe des équations

∑_{I} a_{i}x_{i} = ∑_{J} a_{j}y_{j}

où I et J sont des sous-ensembles de l’ensemble {1,2,3 …,132}, et x_{i}, y_{j} sont des entiers positifs. Une telle équation est dite minimale s’il n’y a pas d’autre équation telle dont les coefficients x̄ et ȳ sont tels que pour tout i ∈ I et pour tout j ∈ J on a x̄_{i} ≤ x_{i} et ȳ_{j} ≤ y_{j}. (En ce cas on dit que x̄ ≤ x et ȳ ≤ y). Nous allons prouver que le nombre d’équations minimales est fini, il est évident qu’il suffit de le prouver pour les équations minimales relatives à des ensembles I et J fixés et disjoints. Soit | I + J |= m. Alors chacune de ces équations minimales peut être representée par un point de N^{m}. Grâce à leur minimalité, l’ensemble de ces points forme une antichaîne de N. Or, toute antichaîne de N^{m} est finie, donc le nombre des équations minimales est fini.

Démontrons maintenant que U(r) est un polynôme , par récurrence sur le

nombre e des équations minimales. Si e=0, alors on sait que U(r) = ( \begin{matrix}s + r + 1 \\ r \end{matrix} ).

Donc U(r) est un polynôme . Supposons qu’on l’ait déjà prouvé pour e, et qu’on ait ainsi obtenu un polynôme P (r). Prenons maintenant une nouvelle équation minimale (elle peut avoir plus de deux membres), et notons-la par:

∑_{I_{1}} a_{i1}b_{i1} = … = ∑_{I_{f}} a_{if}b_{if} = X

où nécessairement : ∑_{i∈I_{j}} b_{ij} = z pour tout 1 ≤ j ≤ f, car les membres des équations minimales doivent avoir la même somme de ligne z. Tous les cubes magiques qui contiennent le cube magique X sont comptés f fois dans P (r).

Ceux, qui contiennent 2X sont comptés ( \begin{matrix}f + 1 \\ 2 \end{matrix} ) fois; ceux qui contiennent

iX sont comptés ( \begin{matrix}f + i − 1 \\ i \end{matrix} ) fois. Donc on a pour tout entier naturel r:

U(r) = P (r)−U(r−z)(f−1)−U(r−2z) ( \begin{matrix}f \\ 2 \end{matrix} )−… = P (r)−∑_{i=1}^{[r/z]} U(r−iz) ( \begin{matrix}f + i − 2 \\ f − 2 \end{matrix} )

Si on remlace maintenant r par r − z et on soustrait l’équation obtenue de l’équation précédente, puis ajoute U(r − z) à chaque membre, on a :

U(r) = U(r − z) + P (r) − P (r − z) − ∑_{i=1}^{[r/z]−1} U(r − iz) ( \begin{matrix}f + i − 3 \\ f − 3 \end{matrix} )

Si on remplace de nouveau r par r − z, et si l’on fait le même processus, on obtient encore une formule pour U(r), etc. Nous voyons qu’après le (f −1)-ième pas, tous les coefficients binominaux du membre de droite deviennent 0. On a donc une formule pour U(r) qui ne contient qu’une combinaison linéaire des P (r − iz). Cela prouve que U(r) est un polynôme . En calculant les 9 premières valeurs de T_{3}(r), on voit qu’il est de degré 8.

Si on considère T_{n}(r) pour un n quelconque, on a un résultat identique:

Théorème 3 Pour tout entier naturel n il existe un h entier naturel tel que T_{n}(r) est un quasi-polynôme de quasi-période h.

(On dit que la fonction F : N → C est une quasi-polynôme s’il existe un entier naturel k tel que pour tout entier naturel i ≤ k les fonctions F_{i}(n) = F (nk + i) sont des polynômes).

Il suffit de trouver un entier naturel h tel que tout cube magique à somme de ligne jh se décompose en somme des cubes magiques à somme de ligne h. Soit h_{1} = 1, et soit h_{2} le plus petit entier naturel tel qu’il existe un cube magique à somme de ligne h_{2} qui ne se décompose pas en somme des cubes magiques à somme de ligne h_{1} = 1. De la même façon, soit h_{3} le plus petit entier naturel tel qu’il existe un cube magique à somme de ligne h_{3} qui ne se décompose pas en somme des cubes magiques à somme de ligne h_{2}, etc. Ce processus s’arrête au bout d’un nombre fini des pas: supposons par absurde que la suite h_{1} < h_{2} < … soit infinie. Soit I_{s} = {x^{d} | d ∈ G_{i}, i ≤ s}△ R_{B} , où G_{i} est l’ensemble des cubes magiques à somme de ligne h_{i}. On voit que: I_{1} < I_{2} < .. < I_{j} <, ce qui est une contradiction car R_{B} est une k-algèbre de type fini. Donc la suite des h_{i} est finie. Soit alorsh son plus grand élément, et on a prouvé que T_{n}(r) est un quasi-polynôme de quasi-période h. Comme on l’a fait en dimension deux, on peut démontrer qu’il est de degré (n − 1)^{3}.

Bibliographie

[1] R.P.Stanley : Combinatorics and Commutative Algebra, Progress in Mathematics (41), Birkhauser, 1983

Université Paris 7 , UFR de Mathématiques 2 Place Jussieu, 75221 Paris, France