Magic N-Cubes Form a Free Monoid Allan Adler P.O. Box 20276, Cherokee Station, New York, NY 10021 Abstract In this paper we prove a conjecture stated in an earlier paper [ A-L]]. The conjecture states that withrespecttoarathernaturaloperation,thesetofN-dimensionalmagiccubesformsafreemonoid for every integer N > 1. A consequence of this conjecture is a certain identity of formal Dirichlet series. These series and the associated power series are shown to diverge. Generalizations of the underlying ideas are presented. We also prove variants of the main results for magic cubes with remarkable power sum properties. (1980)AMSClassi(cid:12)cations: 05A15,05A17,05A19,05B15,08A02,08A05,08B20,10A05,10A25, 10A50, 10H40, 10M20, 15A30, 15A33, 15A51, 20M05 Key Words: array, estimate, free monoid, generating function, inescapable submonoid, in(cid:12)nite dimensionalvariety,irreducible,leftprime,magicN-cube,monoid,persuasivesubmonoid,semidirect product x0 Introduction AccordingtothebookofW.S.Andrews [An],thestudyofmagicsquaresisquiteoldanddates back to ancient Tibet, to 12th century China, to 9th century Arab astrologers and perhaps much further. Indeed, Andrews speculates that magic squares might even be prehistoric. Despite their antiquity, they have often been regarded by serious mathematicians as a waste of time, although many of the great mathematicians of the past, such as Euler [ E1], [ E2], Ramanujan [ R1],(cf. [ R2]) and Fermat [ F], found it to their liking to waste quite a lot of time on them. One possible reason for this double standard is that although magic squares are a lot of fun, no one believes that itispossibletoprovegeneraltheoremsaboutthem. Indeed,untilrecentlyallworkonmagicsquares consisted in presenting methods of constructing magic N-cubes or of examining the properties of particular magic N-cubes, with most attention being devoted to the case N = 2. Since no explicit method has ever been given for constructing all magic N-cubes, the work of past researchers has necessarily been limited to special classes of magic N-cubes. Even so, their work has in some cases also drawn on interesting mathematics such as the related studies of Latin squares and (cid:12)nite geometries. One can also mention the paper [ A-L], which used Prouhet sequences* *ProuhetsequenceshaveasaspecialcaseasequenceusedbyMorse[Mo1](cf. [Mo2],[M-H1]togive a counterexample to the Poincar(cid:19)e-Bendixson theorem in higher genus and by Morse and Hedlund [M-H 2] to give an example of unending chess. 1 the electronic journal of combinatorics 4 (1997), #R15 2 to construct an in(cid:12)nite class of magic cubes with remarkable power sum properties, and the recent papers [ A1], [ A-W], in which p-adic L-functions [ Iw] are used to construct an in(cid:12)nite class of magic p-dimensional cubes.1 In recent times, mathematicians concerned with areas quite di(cid:11)erent from magic squares have been pleased and amused when they could report that their researches have led them to objects which, if not actually magic squares, at any rate exhibit some of the properties of magic squares. ThusitwasthatAx [Ax1],inhisstudiesofquantummechanics [Ax2],enjoyedreferringtodoubly stochastic matrices as \magic squares"; that Andr(cid:19)e Weil [ W1] was able to point out properties of the period matrices of Fermat curves [ W2] which made them like \magic squares"; and that I.M.Gelfandinhislecturesongeneralizedhypergeometricfunctions [Ge]washappytoreportthat someoftheobjectsofhistheoryaredescribedby\magicsquares". Somesuch\magicsquares"then become legitimate objects of study in their own right. For example, in his work on magic graphs, Richard Stanley [ S1], [ S2] used the Hilbert syzygy theorem to study the growth as k ! 1 of the number of arrays of positive integers with entries less than k and having many of the properties of magic squares. Nevertheless, the study of magic N-cubes themselves remains disreputable and probably always will. It is not the purpose of this article, however, to survey the subject of magic N-cubes nor to create enthusiasm for the topic where it does not already exist. It is instead to report on a theoretical development in the subject of magic N-cubes, and here I mean genuine magic N-cubes, not the imitations which were mentioned in the previous paragraph. The simple fact is that until the paper [ A-L] appeared in 1977, no theorem had ever been published concerning the set of all magicN-cubesasawhole. Whatwasnewin [A-L],apartfromanewconstructionofaremarkable classofmagicN-cubes,wastheintroduction([A-L],p. 624)ofanoperationonthesetofallmagic squares. This operation is associative and has an identity element and therefore makes the set of magic squares into a monoid. Furthermore, it was conjectured that with respect to this operation, thesetofmagicsquaresisafreemonoid. Itwasalsoremarkedin [A-L],butnotexplicitlyproved, thattheoperationmakessenseformagicN-cubesforallN andtheconjecturewasexpectedtohold forallN >1. Inthispaper,weshowthattheconjectureistrue.2 Byadaptingthetechniquesofthe proof, we show that magic N-cubes satisfying certain remarkable power sum properties also form a free monoid. We then consider various generating functions for the number of magic N-cubes and show that they diverge. Although pleasant to know, the real signi(cid:12)cance of their divergence lies in the estimates that one uses. For, what one really wants to know, either exactly or approximately, is how many magic N-cubes there are of a given size. We therefore summarize the estimates we obtain at the end of the article. Undoubtedly one can get much better estimates even from the constructions we have used. Whether one can get accurate asymptotic estimates for the number of magic N-cubes is another question. It is conceivable that the \sporadic" magic squares which do not arise from general constructions form an in(cid:12)nite set larger in the sense of its growth than the set of magic squares that do arise from such constructions. If this is the case, then the approach we have taken to obtaining estimates cannot, even in principle, be made accurate through more careful study of general constructions. In order to test for this possibility, it seems reasonable to suggest thatinadditiontousingcomputerstoenumeratethemagicsquaresofvarioussizes,asmanypeople are doing, one should also be trying to see whether the magic squares produced by these searches have natural generalizations to new in(cid:12)nite families. The contents of the paper are as follows. In x1, we prove (Theorem 1.26) that magic squares form a free monoid. These ideas apply as well in the case of magic N-cubes, but since they only involve trivial modi(cid:12)cations of the proof for magic squares, the details are left to the reader. In x2, which is devoted to generalizations, we note that the frames of the magic N-cubes form a monoid, 1 One can view this result as saying that one can use the Riemann zeta function and certain Dirichlet L-functions to construct magic p-cubes. 2 For N = 1, every permutation of the interval [1;r] is a magic 1-cube, since there is only one \side" and that side is also the only \diagonal". In this case, the monoid is de(cid:12)nitely not free, since for example, the magic 1-cubes 1 2 3 and 1 2 are irreducible and commute with each other under the monoid operation, the product being 1 2 3 4 5 6 . The generators of the monoid are the irreducible elements of the monoid, but I don’t know the relations among them. 2 the electronic journal of combinatorics 4 (1997), #R15 3 as do the summation conditions to which they are subjected, and we formulate these observations in a very general setting, motivated by the desire to understand the monoids S (t;g) (see x3) from N an abstract point of view. In earlier draft of this article [ A2], these generalizations were worked out in considerable detail including some discussion of in(cid:12)nite dimensional varieties. In the present article, for reasons of space, the discussion is reduced to a brief sketch. In x3, we consider classes of magic N-cubes that have certain remarkable power sum properties for their entries. We denote these monoids S (t;g) and prove in Theorem 3.1 that they are free on in(cid:12)nitely many generators. N Inx4,wetakeupthequestionoftheconvergenceofthegeneratingfunctionsand,aftershowingthat they diverge, conclude the article with a summary of the estimates we obtained. These estimates can undoubtedly be greatly improved by a more careful application of the methods we are using. However they are all based on the observation that certain methods of constructing magic N-cubes arecompatiblewithmanypermutations. Moredesirablethanmerelyhavingbetterestimateswould be to have another observation of an essentially di(cid:11)erent nature. Throughout this article, N will denote an integer greater than 1 and Z will denote the ring of integers. We will often regard Z as a monoid either under addition or under multiplication, as the situation requires. If a and b are integers, we will denote by [a;b] the set of integers which are (cid:21)a and (cid:20)b. If S is a monoid, we will denote the identity element of S by 1 . S TheauthorwishestothankC.CowsikforhishelpinprovingthecrucialLemma1.25andP.Szu¨sz for his help in proving the divergence of the generating functions. The author is also grateful to Roger Howe and Walter Feit for making it possible for him to use facilities at Yale University. Finally, theauthorisgratefultoMichelBrou(cid:19)eformakingitpossibletouseacomputeratthe E(cid:19)cole Normale Sup(cid:19)erieure in Paris, where (cid:12)nal changes were made in the manuscript. x1 Magic Squares De(cid:12)nition (1.1): Byamagic square of order n,alsocalledann(cid:2)n magic square,wemean an n(cid:2)n square array A=(a ), 0(cid:20)i;j (cid:20)n−1, of positive integers such that ij (i) each of the integers from 1 to n2 inclusive occurs exactly once among the entries of A; nP−1 (ii) for 0(cid:20)i(cid:20)n−1, the sum a is independent of i; ij j=0 nP−1 (iii) for 0(cid:20)j (cid:20)n−1, the sum a is independent of j; ij i=0 nP−1 nP−1 (iv) thesums a and a areequaltothesumsgivenin(ii)(andthereforetothose ii i;n−i−1 i=0 i=0 in (iii) as well). For example, 1 15 14 4 8 1 6 12 6 7 9 3 5 7 8 10 11 5 4 9 2 , 1 and 13 3 2 16 Figure 1 are magic squares. We let let M denote the set of all magic squares. We will de(cid:12)ne an operation on M . The 2 2 operation will be denoted by (cid:3) and will be referred to as multiplication. Before de(cid:12)ning our operation on M formally, let us illustrate it with an example. Let A be the 3(cid:2)3 magic square in 2 Figure 1 above and let B be the 4(cid:2)4 magic square in Figure 1. To form the magic square A(cid:3)B, note that B is 4(cid:2)4 in this case and make a big, empty 4(cid:2)4 frame, as in Fig.2 below. 3 the electronic journal of combinatorics 4 (1997), #R15 4 8 1 6 3 5 7 4 9 2 Fig. 2 Fig. 3 Now locate the square in B which contains the number 1 and place a copy of A in the corre- sponding square of the frame we have just constructed, as in Fig.3 above. We can view this as a way of counting out 9 consecutive numbers. Now locate the square in B containing 2 and in the corresponding square of Fig. 3, count out the next 9 numbers in the same pattern. It is the same to say that one adds 9 to all of the entries of A and places the result in the box corresponding to the position of the 2 in B, as in Fig.4 below. 8 1 6 134 127 132 125 118 123 35 28 33 8 1 6 3 5 7 129 131 133 120 122 124 30 32 34 3 5 7 4 9 2 130 135 128 121 126 119 31 36 29 4 9 2 107 100 105 53 46 51 62 55 60 80 73 78 102 104 106 48 50 52 57 59 61 75 77 79 103 108 101 49 54 47 58 63 56 76 81 74 71 64 69 89 82 87 98 91 96 44 37 42 66 68 70 84 86 88 93 95 97 39 41 43 67 72 65 85 90 83 94 99 92 40 45 38 17 10 15 116 109 114 26 19 24 17 10 15 143 136 141 12 14 16 111 113 115 21 23 25 12 14 16 138 140 142 13 18 11 112 117 110 22 27 20 13 18 11 139 144 137 Fig. 4 Fig. 5 Next one (cid:12)nds the 3 of B and counts out the next 9 numbers in the corresponding place in the frame. Continuing in this way, we eventually get the magic square in Fig.5 above. The product square A(cid:3)B has order 12, the product of the orders of A and B. It is convenient to have an analytic expression for this operation and for that purpose we can work in somewhat greater generality. Let G be an abelian group and choose an element u of G once and for all. Denote by A(G) the set of all square arrays of elements of G, the size of the arrays being arbitrary. If A = (a ), ij 0 (cid:20) i;j (cid:20) m−1, and B = (b ), 0 (cid:20) k;l (cid:20) n−1 are elements of A(G) of sizes m(cid:2)m and n(cid:2)n kl respectively, their product A(cid:3)B will be the mn(cid:2)mn matrix E = (e ) whose ((cid:11);(cid:12))-th entry is (cid:11)(cid:12) given by (1:2) e =m2(cid:1)(b +u)+a (cid:11)(cid:12) kl ij where (1:3) ((cid:11);(cid:12))=m(cid:1)(k;l)+(i;j): Here one should note that as i;j run over the integers from 0 to m−1 and k;l run over the integers from 0 to n−1, the numbers (cid:11);(cid:12) will run over the integers from from 0 to mn−1. So we have 4 the electronic journal of combinatorics 4 (1997), #R15 5 de(cid:12)ned all the entries of E. A moment’s thought will show that if we take G to be the group Z of rationalintegersandu=−1andifweletAandB bemagicsquares, thenwerecovertheoperation wehavede(cid:12)nedformagicsquares. Itisalsoeasytoseethatingeneralthe1(cid:2)1array u isa2-sided identity element for the operation (cid:3). Furthermore, the reader will easily verify that the operation (cid:3) is associative (see for example [ A-L]). A set S closed under an associative operation is called a semigroup. A semigroup with an identity element is called a monoid. We therefore have the following result. Lemma (1.4): Let G be an abelian group. The set A(G) of all square arrays with entries in G is a monoid with identity element u with respect to the operation (cid:3) de(cid:12)ned by equations (1.2) and (1.3). IfS isamonoidwithidentityelementswithrespecttoanassociativeoperation(cid:14)thenasubset T of S is called a submonoid of S if T contains the identity element s of S and is closed under the operation (cid:14). Returning to the original construction involving magic squares, we have the following result, whose straightforward proof is left to the reader (cf. [ A-L]). Proposition (1.5): Let M denote the set of all magic squares. Let A(Z) denote the monoid 2 obtained by taking G to be the additive group of integers and u = −1 in Lemma (1.4). Then M 2 is a submonoid of A(Z). If we modify condition (i) of De(cid:12)nition 1.1 so that the entries of a magic square of ordern run from 0 to n2−1 instead of from 1 to n2 and modify the product (cid:3), as given in Figures 2-6, accordingly, thentheanalyticexpressionfortheproductbecomessimpler. ItistheproductinheritedfromA(Z) when we take u=0 instead of u=−1. ThenotationM andA(Z)introducedinProposition(1.5)willberetainedthroughoutthissection. 2 De(cid:12)nition (1.6): Let S be a monoid with identity element s with respect to an operation (cid:14). We say that S is is left cancellative if for any elements a;b;c of S, the identity (1:7) a(cid:14)b=a(cid:14)c implies b = c. Similarly we say that S is right cancellative if for any elements a;b;c of S, the identity (1:8) a(cid:14)c=b(cid:14)c implies a=b. Lemma (1.9): Let G be an abelian group and let u be an element of G. Then the monoid (A(G);(cid:3);u) is right cancellative. Proof: Let A, B and C be elements of A(G). Suppose that A is m(cid:2)m, B is n(cid:2)n and C is p(cid:2)p. If A(cid:3)C =B(cid:3)C then we must have mp=np and therefore m=n. We therefore have (1:10) m2(cid:1)(c −1)+a =m2(cid:1)(c −1)+b kl ij kl ij for 0 (cid:20) i;j (cid:20) m−1 and 0 (cid:20) k;l (cid:20) n−1, which implies that a = b for all i;j. Therefore ij ij A(cid:3)C =B(cid:3)C implies A=B and we are done. Lemma (1.11): Let G be an abelian group and let u be an element of G. Then the monoid (A(G);(cid:3);u) is left cancellative if and only if the group G is torsion-free. Proof: Let A;B;C be elements of A(G) and suppose that A is m(cid:2)m, B is n(cid:2)n and C is p(cid:2)p. If A(cid:3)B =A(cid:3)C then we must have mn=mp and therefore n=p. It follows that (1:12) m2(cid:1)(b −1)+a =m2(cid:1)(c −1)+a kl ij kl ij for 0(cid:20)i;j (cid:20)m−1 and 0(cid:20)k;l(cid:20)n−1, which implies that m2(cid:1)(b −c )=0 for allk;l. Since the kl kl group G is torsion free, it follows that b = c for all k;l. Therefore, the equation A(cid:3)B = A(cid:3)C kl kl implies B =C and we are done. 5 the electronic journal of combinatorics 4 (1997), #R15 6 De(cid:12)nition (1.13): Let S be a monoid with identity element s with respect to the law of compo- sition (cid:14). Let T be a submonoid of S. We say that T is persuasive in S if the following condition is satis(cid:12)ed: for any elements a;b;c of S such that a(cid:14)b = c, if two of the elements a;b;c belong to T then so does the third. We say that T is inescapable in S if whenever the identity a(cid:14)b = c holds in S with c in T, the elements a;b must also belong to T. It is easy to see that an inescapable submonoid is persuasive. Lemma (1.14): The submonoid M of A(Z) is persuasive. The arrays which satisfy conditions 2 (ii),(iii) of De(cid:12)nition 1.1 form an inescapable submonoid of A(Z) Proof: Let A;B;C be elements of A(Z), where A is m(cid:2)m, B is n(cid:2)n and C is mn(cid:2)mn, and suppose that A(cid:3)B =C. Then we have mPn−1 mP−1nP−1(cid:0) (cid:1) c = m2(cid:1)(b −1)+a rs kl ij r=0 i=0 k=0 (1:15) (cid:18) (cid:19) (cid:18) (cid:19) nP−1 mP−1 = m3 b −m3n+ n a ; kl ij k=0 i=0 where (r;s) = m(cid:1)(k;l)+(i;j). If in the above equations, we replace the row or column of A we are using by another and keep the row or column of B (cid:12)xed, we do not change the value of the expression. That is because C belongs to M (Z) and all we are doing is choosing another row or 2 column of C. Since we have kept the row or column of B (cid:12)xed, its contribution is also unchanged. It follows that the sum over the row or column of A is likewise unchanged, which proves that A satis(cid:12)es conditions (ii) and (iii) of De(cid:12)nition 1.1. Similarly, if one (cid:12)xes the row or column of A and varies the row or column of B, one proves that B satis(cid:12)es conditions (ii) and (iii) of De(cid:12)nition 1.1. This proves that arrays satisfying conditions (ii) and (iii) form an inescapable submonoid. As P P P for condition (iv), the sum c over the main diagonal of C is m2 (b −1) plus a . If we ii jj kk change to the other diagonal, the sum for C doesn’t change and therefore it doesn’t change for A if and only if it doesn’t change for B. This shows that condition (iv) is persuasive. It remains to verify condition (i) of De(cid:12)nition (1.1). If A and B are magic squares then by Proposition (1.5) so is C. Therefore if two of A;B;C are magic squares then C is a magic square and therefore satis(cid:12)es condition (i) of De(cid:12)nition (1.1). We can write (1:16) c =m2(cid:1)(b −1)+a rs kl ij where (1:17) (r;s)=m(cid:1)(k;l)+(i;j) and 0 (cid:20) i;j (cid:20) m−1 and 0 (cid:20) k;l (cid:20) n−1. If A satis(cid:12)es condition (i) of De(cid:12)nition (1.1) then in equation (1.16) the elements a are determined by the condition that c −a must be divisible by ij rs ij m2 and therefore we have (cid:20) (cid:21) c +m2−1 (1:18) b = rs kl m2 which implies that (1:19) 1(cid:20)b (cid:20)n2: kl Since the (mn)2 numbers c in equation (1.16) must be distinct, the same must be true of the n2 rs numbers b . Therefore, B satis(cid:12)es condition (i) of De(cid:12)nition (1.1). Conversely, suppose that B kl satis(cid:12)es condition (i) of De(cid:12)nition (1.1). By equation (1.16), the m2 elements a must be a full set ij of representatives for the residue classes modulo m2 and for each c there is a unique a such that rs ij 6 the electronic journal of combinatorics 4 (1997), #R15 7 c −a is divisible by m2. If some a is less than 1, choose (r;s) such that c −a is divisible by rs ij ij rs ij m2 and such that c is as large as possible. Then we have rs (1:20) c −a (cid:21)c (cid:21)(mn)2 rs ij rs which by equation (1.16) implies that (1:21) b (cid:21)n2+1; kl contradicting the fact that B satis(cid:12)es condition (i) of De(cid:12)nition (1.1). Therefore we must have a (cid:21)1foralli;j. Asimilarargument,whichweleavetothereader,showsthata (cid:20)m2 foralli;j. ij ij Since the a represent all of the m2 residue classes modulo m2, it follows that A satis(cid:12)es condition ij (i) of De(cid:12)nition (1.1). This proves the lemma. Remark (1.22): I don’t know whether M is an inescapable submonoid of A(Z). 2 The following de(cid:12)nition is motivated by the corresponding notions from elementary number theory. De(cid:12)nition (1.23): Let S be a monoid with identity element s with respect to an operation (cid:14). We will say that element t of S is irreducible if t 6= s and if for any elements u;v of S such that t=u(cid:14)v wehaveeitheru=sorv =s. AnelementtofS issaidtobeleft primeifforanyelements u;v;w of S such that t(cid:14)u = v(cid:14)w, there is an element x of S such that v = t(cid:14)x. This de(cid:12)nition of irreducibility is more restrictive than the one generally accepted. However since the monoids in which we wish to study irreducible elements have no units other than the identity element, our de(cid:12)nition will in practice coincide with the usual one. The following lemma follows by an obvious induction on the order of the order of the magic square. Lemma (1.24): The set of all irreducible magic squares generates the monoid M of all magic 2 squares. Inotherwords,everymagicsquarecanbewrittenasaproductofirreduciblemagicsquares. In order to prove that the monoid M is free, we only have to prove that every magic square is 2 uniquely a product of magic squares. Indeed, a monoid is free if and only if it is freely generated by its irreducible elements. That this is the case for M follows, in analogy with the proof of 2 the fundamental theorem of arithmetic, by a simple induction as soon as one has proved that an irreduciblemagicsquareisleftprime. Therefore,thefreenessofM isaconsequenceofthefollowing 2 simple lemma. Lemma(1.25): (IrreducibleImpliesPrime)LetA;B;C;DbemagicsquaressuchthatA(cid:3)B = C(cid:3)D. Suppose A is m(cid:2)m, B is n(cid:2)n, C is p(cid:2)p where m(cid:20)p. If A is irreducible then there is a magic square E such that C =A(cid:3)E. Proof: We will (cid:12)rst show that m must divide p. Here we prefer to give a geometric argument since the key insight is geometrical and is lost in analytic formulations of the proof. We will therefore refer to the geometric description of the operation on magic squares, as illustrated in Figures 2-6. Let F =A(cid:3)B =C(cid:3)D. If we view F is the product C(cid:3)D then F is partitioned into p(cid:2)p squares. Let C denote the p(cid:2)p square which contains the number 1 in F. Then C is an exact replica of 1 1 the magic square C and in particular contains all of the entries of F which are (cid:21) 1 and (cid:20) p2 and none of the entries of F which are >p2. If we now view F as the product A(cid:3)B then F is instead partitioned into m(cid:2)m squares. The (cid:12)rst such square contains the numbers from 1 to m2 and is denoted A . The second such square contains the numbers from m2+1 to 2m2 and is denoted A 1 2 and so on. If m does not divide p then in particular m < p and m2 does not divide p2. Let h be the smallest integer such that h(cid:1)m2 (cid:21) p2. Then the square A lies partly in the square C and h 1 partly outside of it. Let g >0 be an integer. If g <h then the square A lies entirely inside C and g 1 if g > h then A lies entirely outside of C . Since A is m(cid:2)n and C is p(cid:2)p with m < p, there g 1 h 1 must be a column of C which does not meet the square A . Since that column must be covered by 1 h disjoint squares A lying entirely inside of C , it follows that m does divide p after all. Retaining g 1 7 the electronic journal of combinatorics 4 (1997), #R15 8 the de(cid:12)nition of h, we see that h(cid:1)m2 = p2 and therefore h = t2 for some positive integer t. The square C is therefore covered by squares A and is therefore of the form A(cid:3)E where E is a t(cid:2)t 1 g array of nonnegative integers. Since A and C are magic squares, it now follows from Lemma (1.14) that E is a magic square and we are done. Theorem (1.26): The monoid M of all magic squares is freely generated by the set of all 2 irreducible magic squares. Proof: In view of the Irreducibility Implies Prime Lemma and the remarks preceding it, the proof may safely be entrusted to the reader. x2 Generalizations In the preceding section, we have stated our result in the case of magic squares because of the highly geometric and visual nature of the operation and proof and the comparatively simple notation in that case. One can also de(cid:12)ne magic N-dimensional cubes (also known as magic N-cubes) in a similar way to that given in De(cid:12)nition 1.1 and the reader is invited to provide the de(cid:12)nition herself, the only caution being that the condition (iv) on the sum over the diagonals is generalizedinN dimensionstothesumoverthelongestdiagonals,theonesjoiningoppositecorners of the N-cube. Similarly one can, with only minor changes, de(cid:12)ne the operation (cid:3) on the set M N of all magic N-cubes. The same arguments then apply with only minor modi(cid:12)cations to prove that the set M of all magic N-cubes forms a free monoid. We omit the details of this generalization, N whose only complications are notational. One can in fact generalize much further with no essential di(cid:14)culty. Since some of these gener- alizations might be of independent interest, and since to some extent they facilitate the discussion of x3, we will indicate some of them briefly, leaving the veri(cid:12)cation of the elementary details to the reader. (1) Let S;H be monoids and suppose that H is an S-module, i.e. we have a homomorphism from S into the monoid of endomorphisms of the monoid S. Denote by F(S;H) the set of all pairs (F;(cid:27)) consisting of a (cid:12)nite subset F of H and an element (cid:27) of S. The pair (F;(cid:27)) is called a frame,F iscalledtheturfoftheframeand(cid:27) iscalledthenominal orderoftheframe. Then F(S;H) forms a monoid in which the product of (F ;(cid:27) ) and (F ;(cid:27) ) is the frame (F ;(cid:27) (cid:27) ), 1 1 2 2 3 1 2 where F is the set of all elements of the form (cid:27) (f )f with f 2 F and f 2 F . If we view 3 1 2 1 1 1 2 2 a magic N-cube as an array, hence a function de(cid:12)ned on a certain cubical subset of ZN, this de(cid:12)nitionallowsustoconsiderdomainswhichinsteadare(cid:12)nitesubsetsF ofarbitrarymonoids H. It should be clear that the monoid F(S;H) is simply the semidirect product of S and the monoid P(H) of (cid:12)nite subsets of H. (2) Let S;H be as in (1) and let G be a commutative S-module. Let u be an element of G which will be (cid:12)xed throughout the discussion. If (F;(cid:27))2F(S;H), then by an array of type (F;(cid:27)) with entries in G, we mean a triple (F;(cid:27);(cid:21)) where (cid:21) is a function from F to G. If we do not wish to specify the type (F;(cid:27)) of the array, we will refer to it as an array framed in F(S;H). Wecall(cid:27) theorderofthearray(F;(cid:27);(cid:21)). WedenotebyA(S;H;G)thesetofallarraysframed in F(S;H). Then A(S;H;G) is naturally a semigroup in which the product of (F ;(cid:27) ;(cid:21) ) and 1 1 1 (F ;(cid:27) ;(cid:21) ) is the array (F ;(cid:27) ;(cid:21) ), where (F ;(cid:27) ) is the product of (F ;(cid:27) ) and (F ;(cid:27) ) in 2 2 2 3 3 3 3 3 1 1 2 2 F(S;H) and where the function (cid:21) is de(cid:12)ned by 3 X 0 (cid:21) (h )= ((cid:27) ((cid:21) (h )+u)+(cid:21) (h )) 3 3 1 2 2 1 1 where the summation runs over all elements (h ;h ) 2 F (cid:2)F such that h = (cid:27) (h )h . If g 1 2 1 2 3 1 2 1 is an element of G, we will denote by g the framed array g =(feg;s;(cid:21):feg!G) de(cid:12)ned by (cid:21)(e) = g, where e is the identity element of H. This notation generalizes and supersedes the notation u introduced in x1. If g is taken to be an element of G such that g+u = 1 , where G 1 is the identity element of G, then A(S;H;G) is actually a monoid whose identity element G is g. Assume that such an element g exists. The monoid A(S;H;G) may then be described as the semidirect product of S with the monoid P(H;G) of all (cid:12)nite partial functions from H to G, this being the kernel of the homomophism (F;(cid:27);(cid:21))7!(cid:27) of A(S;H;G) onto S. 8 the electronic journal of combinatorics 4 (1997), #R15 9 (3) In order to introduce the notion of a magic frame, we have to be able to specify the summation conditions. To do so in our present generality, we observe that the summation conditions traditionallyconsideredinthestudyofmagicN-cubesalsoformamonoidandusethatinsight in order to formulate our generalization. More precisely, let S;H;G be as in (1) and let n be a positive integer. We introduce the following monoids. Qn M(1) = F(S;H) M(n) = M(1) 1 1 1 i=1 Qn M(1) = F(S;P(H)) M(n) = M(1): 2 2 2 i=1 In the de(cid:12)nition of M(n) and M(n) we use the product notation to denote the (cid:12)bre product 1 2 over S, not the cartesian product. In practice, an element of M(1) will be a subset of H over 1 whichwewishtosumtheentriesofanarray. InthecaseofmagicN-cubes,suchasubsetmight be an orthogonal or a great diagonal of the N-cubes, but one considers other subsets as well. In general, we will want to sum over various subsets and we wish to handle all such subsets simultaneously. For example, if N is (cid:12)xed and H =ZN, we can let n=2N−1 and view the set of n great diagonals of the N-cube as an element of M(n). In that case, if (F ;(cid:27) ) is an N-cube 1 i i for i = 1;2 and if A is the element of M(n) corresponding to the set of great diagonals of i 1 (F ;(cid:27) ),thentheproductinM(n) ofA andA willbethesetofgreatdiagonalsoftheproduct i i 1 1 2 of(F ;(cid:27) )and(F ;(cid:27) ). Thisisquitesatisfyingbutdoesnotsu(cid:14)cetodescribetheorthogonals. 1 1 2 2 The reason is that the number of orthogonals of an N-cube depends on the size of the N-cube and not just on N. For this reason we introduced the monoid M(1). The orthogonals parallel 2 to a particular axis of an N-cube form an element of M(1). If for i=1;2, B is the element of 2 i M(1) corresponding to the orthogonals of an N-cube (F ;(cid:27) ) parallel to a particular axis (the 2 i i same axis for i = 1;2), then the product in M(1) of B and B is the element corresponding 2 1 2 to the set of orthogonals in that same direction in the product of (F ;(cid:27) ) and (F ;(cid:27) ). This is 1 1 2 2 also satisfying, but since there are N directions in which to choose the orthogonals, the system of all orthogonals is described by an element of M(N). Thus, the set of summation conditions 2 which a magic N-cube is expected to satisfy is an element of the monoid M(n)(cid:2)M(N); 1 2 where n = 2N−1. In order to simplify the notation, we observe that the monoid M(1) may be 1 embedded in the monoid M(1) by associating to a subset F of H the singleton fFg. Therefore, 2 we may regard the set of summation conditions as an element of M(d) where d = N +2N−1. 2 Theseconsiderationsmotivatethefollowingde(cid:12)nition: let(F;(cid:27);(cid:21))beanelementofA(S;H;G), letdbeapositiveintegerandletC =(C ;:::;C )beanelementofM(d)suchthatfor1(cid:20)i(cid:20)d, 1 d 2 every element of C is a subset of F. We say that the array (F;(cid:27);(cid:21)) is C-stochastic if for i P 1(cid:20)i(cid:20)d and for E in C , the summation (cid:21)(h) is independent of i and E. Suppose that i h2E (cid:30) is a homomorphism from a submonoid F of the monoid F(S;H) to the monoid M(d) such 2 that for every (F;(cid:27);(cid:21)) in F the order of (cid:30)(F;(cid:27);(cid:21)) is (cid:27). We will say that an array (F;(cid:27);(cid:21)) is phi-stochasticif(F;(cid:27))belongstoF andif(F;(cid:27);(cid:21))is(cid:30)(F;(cid:27))-stochastic. IfF and(cid:30)aresuch, we denote by M((cid:30)) the subset of A(S;H;G) consisting of all (cid:30)-stochastic arrays. Then M((cid:30)) is a submonoid of A(S;H;G). Now suppose that the only pair ((cid:27);g) 2 S(cid:2)G with (cid:27)(g) = 1 G is (1 ;1 ), where 1 is the identity element of S. Then then the monoid M((cid:30)) is a persuasive S G S submonoid of A(S;H;G). ByplacingsomerestrictionsonthemonoidG,onecangeneralizefurtherthenotionsofstochas- ticityintroducedin(3). Moreprecisely,oneassumesthatGistheadditivegroupofanalgebraically closed(cid:12)eldk. Inthatcase, onecanintroducemonoidsofsummationconditionsbymeansofcertain classes of in(cid:12)nite dimensional varieties over k and prove that they are free. Space does not permit the detailed description of this general construction and we presently know only one interesting 9 the electronic journal of combinatorics 4 (1997), #R15 10 example of it, namely in connection with the monoids S (t;g) de(cid:12)ned in the next section. So we N will con(cid:12)ne our attention to that example, which we describe in the next section without reference to in(cid:12)nite dimensional varieties. x3 Magic N-cubes with remarkable power sum properties Let n2[1;N]. An n-cube contained in an N-dimensional cubical array f of order d is then the intersectionofthatarraywithacertainnumberofhyperplanesparalleltothefacesofthearray. As such it is completely described by selecting a subset J of cardinality N−n of [1;N] and prescribing a function h:J ![0;d−1]. Two n-cubes having the same set J are said to be conjugate. Let g : [1;N] ! Z be any nonnegative function and let t > 1 be an integer. We denote by S (t;g) the set of all magic N-cubes A satisfying the following two conditions: N (a) The order of A is a power of t, say ts. (b) For 1(cid:20)n(cid:20)N, conjugate n-dimensional subcubes have equal sums of the r-th powers of their entries, for 0(cid:20)r (cid:20)g(n). WealsodenotebyM (t)themonoidofallmagicN-cubessatisfyingonlycondition(a)above. N In the proof, we will use notation introduced in (1) and (2) of x2. Theorem (3.1): Let t;g be as above. Then S (t;g) is an inescapable submonoid of the monoid N M of all magic N-cubes. Furthermore, S (t;g) is a free monoid on in(cid:12)nitely many generators. N N Proof: Let A;B be elements of S (t;g) and let C be their product. Any n-dimensional subcube N K of C is the product in F(Z;ZN) of the corresponding subcubes K0;K00 of A and B respectively. Normally we think of the n-subcubes as subsets of A;B and C but we can view them as elements of F(Z;ZN) by replacing, e.g. K0 by the pair (K0;ts), where t is the order of C. Here the action of s Z on ZN is the usual Z-module structure on ZN. Since we care about the entries of these n-cubes, we are concerned with the elements of A(S;ZN;G), where S;G are Z under multiplication and addition respectively and where G is viewed as an S-module via (s;g) 7! sNg. Denote by f;f0;f00 the functions that give the entries of the subcubes K;K0;K00 respectively. We then have X X X f(v)r = (tsNf00(v00)+f0(v0))r (3:2) v2K v02K(cid:18)0v00(cid:19)2K 00 ! ! Xr r X X = f0(v0)r−j (cid:1) tjsNf00(v00)j j j=0 v02K0 v002K00 Since the sums over K0 and K00 are independent of the choices of the n-cubes K0;K00 within their conjugacyclasses,thesumoverK isindependentofthechoiceofthen-cubeK withinitsconjugacy class. This proves that S (t;g) is a submonoid of M . Furthermore, the submonoid S (t;g) is an N N N inescapable submonoid of M . Indeed, suppose A;B;C are magic N-cubes such that A(cid:3)B = C N and suppose that C belongs to S (t;g). Choose K;K0;K00 as before and use the above identity for N the sum of the r-th powers of the entries of K, which we know is independent of the choice of the n-cube K within its conjugacy class. If we (cid:12)x the n-cube K00 and allow the n-cube K0 to vary in its conjugacy class, it follows by an easy induction on r that, for 1(cid:20)r (cid:20)g(n), the sum of the r-th powers of the entries of the entries of K0 are independent of the choice of K0 within its conjugacy class. Similarly, by (cid:12)xing K0 and letting K00 vary in its conjugacy class we see that the sum of the r-th powers of the entries of K00 is independent of the choice of the n-cube K00 within its conjugacy class. This proves that S (t;g) is an inescapable submonoid of M . It follows that an irreducible N N elementofS (t;g)isalsoirreduciblewhenviewedasanelementofM . ToseethatS (t;g)isfree, N N N it su(cid:14)ces to prove the analogue of the Irreducibility Implies Prime Lemma for this situation. So suppose that A;B;C;D are elements of S (t;g) of orders m;n;p;q where m(cid:20)p, and suppose that N A(cid:3)B =C(cid:3)D with A irreducible. In the proof of the freeness of M , which we left to the reader, N oneprovesalongthewaythatM satis(cid:12)estheanalogueoftheIrreducibilityImpliesPrimeLemma. N Since A is also irreducible as a magic N-cube, it follows that we can write C as the product A(cid:3)E of A and another magic N-cube E. It then follows that E belongs to S (t;g). Therefore, S (t;g) N N is free. Finally, to see that S (t;g) has in(cid:12)nitely many generators, we will show that it contains N in(cid:12)nitely many irreducible magic N-cubes. In Theorem 1 on p.620 of [ A-L], it is shown how to 10