|
Structure of Magic and Semi-Magic Squares, Methods and Tools for Enumeration |
by Francis Gaspalou |
|
|
 |
 |
|
The two methods described in the two previous pages allow to deduce one square from another square, by transformation or permutation. Here, an intermediate square is deducted from one square, and therefore all a set of squares. It is the intermediate square method: you look at a glance all a set of squares. The intermediate square is a parametric representation of this set of squares. However, the intermediate square method is linked to the permutation method. At the limit, you can consider that the intermediate square method is a special case of the permutation method and you will see that the permutations are those coming from a "basis". But in fact, the intermediate square method is a method in itself. You will see that this method is mainly used to enumerate and represent special sets of squares: regular and semi-regular sets. For order 4, these sets have a very large population (5 760 semi-regular squares, with at least one basis, on the 7 040) in front of irregular squares; for superior orders irregular squares are the most numerous and regular or semi-regular squares are the exception.
The method consists in deducting from one square an intermediate square - sum of two elementary squares built with capital and lower-case letters - , and after in writing magic conditions of these letters, and finally in sweeping the domain of variation of these letters. By such a tabulation of parameters, a set of squares is obtained. Different configurations for the values of the letters are possible (see § 3 hereunder); then you can generate others sets of squares from one intermediate square (as many as the number of different basis: see § 3). The two squares are called the capital letter square and the lower-case letter square. They are the BENSON and JACOBY' notations - main reference I used in the beginning of my research - . These two squares are orthogonal squares, that is to say the sum of the two squares gives a square with all the n˛ possible couples, each one occurring only one time. Note that in other books, the two elementary squares are built with Greek and Latin letters. This notation is rather reserved to Latin squares and Greco-Latin squares (see § 4 hereunder). Note also you can apply the group G of transformations to an intermediate square. I don't apply this group G and by personal convention, I limit enumeration strictly to the set of squares given by an intermediate square without any transformation.
DURER's square:
gives with the basis (a=1, b=2, c=3, d=4; A=0, B=4, C=8, D=12) the intermediate square:
For this intermediate square, the 10 magic conditions on the 4 rows, 4 columns and 2 diagonals give (a, b, c, d; A, B, C, D are now parameters):
A+B+C+D+a+b+c+d=34
A+D=B+C a+d=b+c By tabulation, that is to say when choosing a, b, c, d among the set {1, 2, 3, 4} and when choosing A, B, C, D among the set {0, 4, 8, 12}, and with respect to the above magic conditions, you obtain a set of 64 different squares. In fact, other basis are possible for a, b, c, d, A, B, C, D (see next §) and finally you obtain 6 * 64 = 384 different squares, which are the classical 384 symmetrical squares of order 4. From one square, you can have 384 squares!
3.1 Definition
The n˛ first integers can be obtained by addition from the two arithmetic progressions:
A table of addition (cf. GARDNER) can be built:
But there is not only one decomposition. For example for n=4, it is possible to build other tables of addition, as:
I will call basis a set of n values for lower-case letters a,b,c,d,... and of n values for capital letters A,B,C,D,.... allowing to build such a table of addition, that is to say to generate the n˛ first integers.
In such a table, each letter, capital or lower-case, is occurring n times, therefore: nA+nB+nC+...+na+nb+nc+...= n˛(n˛+1)/2
and then: A+B+C+...+a+b+c+...= S
where S=n(n˛+1)/2 is the magic constant.
The sum of the numbers in the first diagonal of the table of addition is equal to S.
The n values for capital letters are of course different; idem for the n values for lower-case letters. Therefore I can range these values by growing values (for capital as well as for lower-case letters) and call by personal convention capital letters the sets including 0, lower-case letters the sets including 1 (1 is obtained with the sum 0+1): such a basis will be called an orderly basis. Then A=0 and a=1. This convention is only for orderly basis, and otherwise A can take the value 1 in any other basis. Note than in an orderly basis, the sum of the 2 maximum values for capital and lower-case letters is equal to n˛ (D+d=16 for n=4). Taking the successive numbers in the order of the rows of the addition table (from left to right and from top to bottom), you see that a basis is a way to design a special "permutation" on the n˛ first numbers. The intermediate square method is well a special case of the permutation method. 3.2 Enumeration of the different basis
This enumeration is done with a computer. You can only compute the orderly basis. For example, for n=4, you will search the numbers a, b, c, d; A, B, C, D as:
A=0 and A< B< C< D
and allowing to generate by addition the 16 first numbers.
a=1 and a< b< c< d A+B+C+D+a+b+c+d=34 D+d=16 You find 6 orderly basis (classified here by growing values for lower-case letters):
A basis can be defined by the value of the sum of capital letters Σ=A+B+C+D (or of the sum of lower-case letters σ=a+b+c+d, with the property Σ+σ=S where S=n(n˛+1)/2=34 here). The first basis is classical: you have σ=n(n+1)/2, and Σ=n˛(n-1)/2. In fact, 3 elementary basis (the 3 first ones for example) are sufficient to define the set of 6 basis, because the 3 other ones can be deducted by the theorem:
If (a, b, c, d; A, B, C, D) is a solution, then (A+1, B+1, C+1, D+1; a-1, b-1, c-1, d-1) is also solution.
I call this last basis the corresponding basis. The associated square to the corresponding basis is obtained by permutation of capital and lower-case letters (on the associated square to the first basis). The corresponding tables of addition are symmetrical by the first diagonal. You can suppose for example B>b-1 for reducing enumeration to 3 elementary basis. You see a posteriori than the 6 basis are symmetrical for capital and for lower-case letters, that is to say you have for all the basis:
A+D=B+C=M
a+d=b+c=m (and M+m= n˛+1).
Here are the number k of orderly basis for the first values of n:
k is even. I call the k/2 first orderly basis the elementary basis. There are sufficient to describe all the set of k basis. The 7 first orderly basis for n=6 are (always classified according to growing values for lower-case letters):
and the 10 first for n=8:
These results seem original. If n is a prime, then it seems that k=2 (it is not possible to find other solutions than the 2 classical solutions). It seems also that the properties found for n=4 can be generalized: all the basis are symmetrical, for capital letters as well as for lower-case letters.
The notion of basis defined at the previous paragraph is very fruitful for specific sets of magic or semi-magic squares: the squares built from intermediate Greco-Latin squares, therefore made from two elementary orthogonal Latin squares. These squares are also called eulerian squares. Among these squares, the regular squares are a very important set.
I remember that a Latin square is a square where each letter occurs only one time in each row and each column. A Latin square is diagonal if the two diagonals have also the property. A Latin square is magic if the two diagonals are magic. A Latin diagonal square is a specific kind of Latin magic square: in a Latin magic square, the two diagonals are magic, but not necessarily Latin.
A Greco-Latin square is made from two orthogonal Latin squares (each couple of letters occurs only one time). A Greco-Latin square made from two orthogonal Latin diagonal squares is said a diagonal Greco-Latin square. A Greco-Latin square made from two orthogonal Latin magic squares is said a magic Greco-Latin square. The rows and columns of a Latin square (or of a Greco-Latin square) are said regular. A semi-magic square is said regular if it is possible to make a correspondence with an intermediate Greco-Latin square. A magic square is said regular if it is possible to make a correspondence with an intermediate diagonal Greco-Latin square. Caution! The regular squares are a part of magic eulerian squares. For example, you have 1 536 magic eulerian squares of order 4 with the first basis: 1 152 are regular and 384 are magic eulerian but with diagonals only magic and not regular. The following fundamental property can be stated: if a Greco-Latin square of order n can be built, then it is possible to associate k (n!)˛ semi-magic squares to it.
For a given basis, a can take n values, b can take the (n-1) remaining values, c can take (n-2) remaining values, etc., therefore you have n! values for lower-case letters, so much for the capital letters; and you have k different basis giving finally k disjointed sets.
This proposition seems original.
But the k (n!)˛ squares in the associated set are not only semi-magic. Their real properties depend on those of the original Greco-Latin square. For example:
Note that Greco-Latin squares exist for any order different from 2 and 6 (cf. BOUTELOUP, reference given hereafter). In fact, the important thing is the lack of conditions on capital and lower-case letters. The above-mentioned proposition could rather be expressed: if an intermediate square of order n can be built without any condition on capital and lower-case letters, then it is possible to associate k (n!)˛ semi-magic squares to it. Note that the notions of regular lines or Greco-Latin squares are specific to a basis. A line is not regular (or a square is not Greco-Latin) by itself; if you change the basis the property may disappear. The following property can be stated: the 2 (n!)˛ squares given by a Greco-Latin square of order n (with one basis and with its corresponding basis) have a group structure.
I haven't really a demonstration. It is true for order 4 and 5.
This probable property can also be expressed in the following way: you have a group structure on the 2 (n!)˛ squares obtained by association between the (n!)˛ squares given by a Greco-Latin square of order n and the (n!)˛ squares given by the second Greco-Latin square obtained by permutation of capital and lower-case letters.
For order 4, the 1 152 squares have a group structure, but not the k (n!)˛ = 3 456 semi-pandiagonal squares (see Appendix 3, § 3); on the k=6 basis, there are k/2=3 elementary basis. For order 5, the 28 800 squares have also a group structure. There is a large literature on Latin squares and Greco-Latin squares. I think the best book that gives the state of the art on this subject is the book of Jacques BOUTELOUP, Carrés Magiques, Carrés Latins et Eulériens, éditions du Choix, 1991 (sorry, it is in French!). One classical subject in this literature is the regular cyclical squares (see for example the book of BENSON and JACOBY). But curiously, there is very little works on irregular squares (each letter, capital or lower-case, doesn't occur one time and only one time in each row, column or diagonal). CANDY seems the reference in this matter; BENSON and JACOBY deal with some specific pandiagonal 7x7 squares (irregular for lower-case letters, but regular for capital letters). The irregular squares - irregular for capital letters as well for lower-case letters - are the most numerous (see hereafter). Curiously too, I did not find any work in the literature on what I call the Gallic squares (squares with n letters a, n letters b, etc.). It is not compulsory, as in the Latin squares, that each row (or column) has only one a letter; it is sufficient that a occurs n times in the square. Idem for b, etc. The sums of rows, columns and two diagonals are not necessarily equal to σ. I call these squares Gallic by opposition to Latin because Gallic people was known to be less orderly than Latin people! The "interesting" Gallic squares are those that have an orthogonal. These squares constitute an unexplored mine! Their properties have to be studied. I began to do it. The Gallic squares can be used to find magic squares: you build first a Gallic square and you search after the orthogonal squares to this Gallic square. This method is very fruitful when you search specific properties of the magic square or when the general program gives very little solutions because the large number of cases to examine. Therefore, to search an orthogonal to a given lower-case letter square (or capital letter square) is a very powerful method to find magic squares! Ex: you can search "self orthogonal" or "auto-orthogonal" squares (the capital letter square is the lower-case letter square symmetrical by the first diagonal) or most generally a capital letter square which is the lower-case letter square transformed by a transformation of group G. In this way, you generate a magic square from a lower-case letter square only.
You can reduce the enumeration of orthogonal squares to a given lower-case letter square (Latin or Gallic) using the notions of group G (transformation and permutation):
Note: 3 different kinds of squares can be defined:
All these definitions are specific to a basis. A square is not regular or irregular in itself, but by reference to a basis. E.g.: with the classical basis ( 1, 2, 3, 4; 0, 4, 8,12), the 7 040 squares of order 4 can be distributed in
5 248 semi-regular squares (with 1 152 regular squares),
There are 5 760 semi-regular squares with at least one basis among the 7 040 magic squares (and there are 3 456 regular squares with at least one basis among the 7 040).
1 792 irregular squares. See Appendix 3, § 5.
I suppose - but it is only a conjecture - that magic squares and semi-magic squares of order n can be decomposed in elementary sets. With the intermediate square method, the largest set - if it exists - is in relation with a Greco-Latin square and has (n!)2 squares; there is no conditions on capital and lower-case letters (except A+B+C+...+a+b+c+...=S). The other elementary sets are obtained with conditions on capital and lower-case letters; they are sets with q squares, q being a divisor of (n!)2 . As explained in page about The transformation method § 5.1, it is necessary to associate some isomorphic sets (but not all the isomorphic sets) to each elementary set. This conjecture is true for magic squares of order 4 (see Appendix 3, § 6)
The intermediate square method is a powerful tool for enumerating regular squares or semi-regular squares. For order 4, these squares constitute the largest family (cf. § 4 above), but for orders superior to 4, these squares are not the most numerous: irregular squares is the rule, regular or semi-regular squares the exception. For example:
For irregular squares, the intermediate square method can also be applied, but the set of generated squares is very little.
|
