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 with respect to a rather natural operation, the set of N-dimensional magic cubes forms a free monoid 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) AMS Classifications: 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, infinite dimensional variety, irreducible, left prime, magic N-cube, monoid, persuasive submonoid, semidirect product

§0 Introduction

According to the book of W.S.Andrews [An], the study of magic squares is quite old and dates 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 it is possible to prove general theorems about them. Indeed, until recently all work on magic squares 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 finite geometries. One can also mention the paper [A-L], which used Prouhet sequences^{1} to construct an infinite class of

1 Prouhet sequences have as a special case a sequence used by Morse [Mo1] (cf. [Mo2], [M-H 1]) to give a counterexample to the Poincaré-Bendixson theorem in higher genus and by Morse and Hedlund [M-H 2] to give an example of unending chess. 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 infinite class of magic p-dimensional cubes.^{2}

In recent times, mathematicians concerned with areas quite different 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. Thus it was that Ax [Ax1], in his studies of quantum mechanics [Ax2], enjoyed referring to doubly stochastic matrices as “magic squares”; that André 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. Gelfand in his lectures on generalized hypergeometric functions [Ge] was happy to report that some of the objects of his theory are described by “magic squares”. Some such “magic squares” 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 → ∞ 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 magic N-cubes as a whole. What was new in [A-L], apart from a new construction of a remarkable class of magic N-cubes, was the introduction ([A-L], p. 624) of an operation on the set of all magic 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, the set of magic squares is a free monoid. It was also remarked in [A-L], but not explicitly proved, that the operation makes sense for magic N-cubes for all N and the conjecture was expected to hold for all N > 1. In this paper, we show that the conjecture is true.^{3} By adapting the techniques of the 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 significance 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 infinite 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 that in addition to using computers to enumerate the magic squares of various sizes, as many people are doing, one should also be trying to see whether the magic squares produced by these searches have natural generalizations to new infinite families.

The contents of the paper are as follows. In §1, 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 modifications of the proof for magic squares, the details are left to the reader. In §2, which is devoted to generalizations, we note that the frames of the magic N-cubes form a monoid, as do the summation conditions to which they are subjected, and we formulate these observations

2 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.

3 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 definitely 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. in a very general setting, motivated by the desire to understand the monoids S_{N}(t, g) (see §3) from an abstract point of view. In earlier draft of this article [A2], these generalizations were worked out in considerable detail including some discussion of infinite dimensional varieties. In the present article, for reasons of space, the discussion is reduced to a brief sketch. In §3, we consider classes of magic N-cubes that have certain remarkable power sum properties for their entries. We denote these monoids S_{N}(t, g) and prove in Theorem 3.1 that they are free on infinitely many generators. In §4, we take up the question of the convergence of the generating functions and, after showing that 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 are compatible with many permutations. More desirable than merely having better estimates would be to have another observation of an essentially different 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 ≥ a and ≤ b. If S is a monoid, we will denote the identity element of S by 1_{S}.

The author wishes to thank C.Cowsik for his help in proving the crucial Lemma 1.25 and P.Szü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, the author is grateful to Michel Broué for making it possible to use a computer at the École Normale Supérieure in Paris, where final changes were made in the manuscript.

§1 Magic Squares

Definition (1.1): By a magic square of order n, also called an n × n magic square, we mean an n × n square array A = (a_{ij}), 0 ≤ i, j ≤ n − 1, of positive integers such that

(i) each of the integers from 1 to n^{2} inclusive occurs exactly once among the entries of A;

(ii) for 0 ≤ i ≤ n − 1, the sum ∑_{j=0}^{n−1} a_{ij} is independent of i;

(iii) for 0 ≤ j ≤ n − 1, the sum ∑_{i=0}^{n−1} a_{ij} is independent of j;

(iv) the sums ∑_{i=0}^{n−1} a_{ii} and ∑_{i=0}^{n−1} a_{i,n−i−1} are equal to the sums given in (ii) (and therefore to those

in (iii) as well).

For example,

8 1 6 3 5 7 4 9 2 , 1 and 1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16

Figure 1

are magic squares.

We let let M_{2} denote the set of all magic squares. We will define an operation on M_{2}. The operation will be denoted by ∗ and will be referred to as multiplication. Before defining our operation on M_{2} formally, let us illustrate it with an example. Let A be the 3 × 3 magic square in Figure 1 above and let B be the 4 × 4 magic square in Figure 1. To form the magic square A ∗ B, note that B is 4 × 4 in this case and make a big, empty 4 × 4 frame, as in Fig.2 below.

Fig. 2  8 1 6 3 5 7 4 9 2 Fig. 3

Now locate the square in B which contains the number 1 and place a copy of A in the corresponding 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 3 5 7 4 9 2 17 10 15 12 14 16 13 18 11 Fig. 4  8 1 6 134 127 132 125 118 123 35 28 33 3 5 7 129 131 133 120 122 124 30 32 34 4 9 2 130 135 128 121 126 119 31 36 29 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 116 109 114 26 19 24 17 10 15 143 136 141 111 113 115 21 23 25 12 14 16 138 140 142 112 117 110 22 27 20 13 18 11 139 144 137 Fig. 5

Next one finds 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 ∗ 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 ≤ i, j ≤ m − 1, and B = (b_{kl}), 0 ≤ k, l ≤ n − 1 are elements of A(G) of sizes m × m and n × n respectively, their product A ∗ B will be the mn × mn matrix E = (e_{αβ}) whose (α, β)-th entry is given by

(1.2)  e_{αβ} = m^{2} · (b_{kl} + u) + a_{ij}

where

(1.3)  (α, β) = m · (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 α, β will run over the integers from from 0 to mn − 1. So we have defined all the entries of E. A moment’s thought will show that if we take G to be the group Z of rational integers and u = −1 and if we let A and B be magic squares, then we recover the operation we have defined for magic squares. It is also easy to see that in general the 1 × 1 array u is a 2-sided identity element for the operation ∗. Furthermore, the reader will easily verify that the operation ∗ 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 ∗ defined by equations (1.2) and (1.3).

If S is a monoid with identity element s with respect to an associative operation ∘ then a subset T of S is called a submonoid of S if T contains the identity element s of S and is closed under the operation ∘. 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_{2} denote the set of all magic squares. Let A(Z) denote the monoid 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 Definition 1.1 so that the entries of a magic square of order n run from 0 to n^{2} − 1 instead of from 1 to n^{2} and modify the product ∗, as given in Figures 2-6, accordingly, then the analytic expression for the product becomes simpler. It is the product inherited from A(Z) when we take u = 0 instead of u = −1. The notation M_{2} and A(Z) introduced in Proposition (1.5) will be retained throughout this section.

Definition (1.6): Let S be a monoid with identity element s with respect to an operation ∘. We say that S is is left cancellative if for any elements a, b, c of S, the identity

(1.7)  a ∘ b = a ∘ 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 ∘ c = b ∘ 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), ∗, u) is right cancellative.

Proof: Let A, B and C be elements of A(G). Suppose that A is m × m, B is n × n and C is p × p. If A ∗ C = B ∗ C then we must have mp = np and therefore m = n. We therefore have

(1.10)  m^{2} · (c_{kl} − 1) + a_{ij} = m^{2} · (c_{kl} − 1) + b_{ij}

for 0 ≤ i, j ≤ m − 1 and 0 ≤ k, l ≤ n − 1, which implies that a_{ij} = b_{ij} for all i, j. Therefore A ∗ C = B ∗ 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), ∗, 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 × m, B is n × n and C is p × p. If A ∗ B = A ∗ C then we must have mn = mp and therefore n = p. It follows that

(1.12)  m^{2} · (b_{kl} − 1) + a_{ij} = m^{2} · (c_{kl} − 1) + a_{ij}

for 0 ≤ i, j ≤ m − 1 and 0 ≤ k, l ≤ n − 1, which implies that m^{2} · (b_{kl} − c_{kl}) = 0 for all k, l. Since the group G is torsion free, it follows that b_{kl} = c_{kl} for all k, l. Therefore, the equation A ∗ B = A ∗ C implies B = C and we are done.

Definition (1.13): Let S be a monoid with identity element s with respect to the law of composition ∘. Let T be a submonoid of S. We say that T is persuasive in S if the following condition is satisfied: for any elements a, b, c of S such that a ∘ 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 ∘ 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_{2} of A(Z) is persuasive. The arrays which satisfy conditions (ii),(iii) of Definition 1.1 form an inescapable submonoid of A(Z)

Proof: Let A, B, C be elements of A(Z), where A is m × m, B is n × n and C is mn × mn, and suppose that A ∗ B = C. Then we have

(1.15)  \begin{aligned}∑_{r=0}^{mn−1} c_{rs} & = & ∑_{i=0}^{m−1} ∑_{k=0}^{n−1} (m^{2} · (b_{kl} − 1) + a_{ij}) \\ & = & (m^{3} ∑_{k=0}^{n−1} b_{kl}) − m^{3}n + (n ∑_{i=0}^{m−1} a_{ij}) , \end{aligned}

where (r, s) = m · (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 fixed, we do not change the value of the expression. That is because C belongs to M_{2}(Z) and all we are doing is choosing another row or column of C. Since we have kept the row or column of B fixed, its contribution is also unchanged. It follows that the sum over the row or column of A is likewise unchanged, which proves that A satisfies conditions (ii) and (iii) of Definition 1.1. Similarly, if one fixes the row or column of A and varies the row or column of B, one proves that B satisfies conditions (ii) and (iii) of Definition 1.1. This proves that arrays satisfying conditions (ii) and (iii) form an inescapable submonoid. As for condition (iv), the sum ∑ c_{ii} over the main diagonal of C is m^{2} ∑(b_{jj} − 1) plus ∑ a_{kk}. If we 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 Definition (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 satisfies condition (i) of Definition (1.1). We can write

(1.16)  c_{rs} = m^{2} · (b_{kl} − 1) + a_{ij}

where

(1.17)  (r, s) = m · (k, l) + (i, j)

and 0 ≤ i, j ≤ m − 1 and 0 ≤ k, l ≤ n − 1. If A satisfies condition (i) of Definition (1.1) then in equation (1.16) the elements a_{ij} are determined by the condition that c_{rs} − a_{ij} must be divisible by m^{2} and therefore we have

(1.18)  b_{kl} = [\frac{c_{rs} + m^{2} − 1}{m^{2}}]

which implies that

(1.19)  1 ≤ b_{kl} ≤ n^{2}.

Since the (mn)^{2} numbers c_{rs} in equation (1.16) must be distinct, the same must be true of the n^{2} numbers b_{kl}. Therefore, B satisfies condition (i) of Definition (1.1). Conversely, suppose that B satisfies condition (i) of Definition (1.1). By equation (1.16), the m^{2} elements a_{ij} must be a full set of representatives for the residue classes modulo m^{2} and for each c_{rs} there is a unique a_{ij} such that c_{rs} − a_{ij} is divisible by m^{2}. If some a_{ij} is less than 1, choose (r, s) such that c_{rs} − a_{ij} is divisible by m^{2} and such that c_{rs} is as large as possible. Then we have

(1.20)  c_{rs} − a_{ij} ≥ c_{rs} ≥ (mn)^{2}

which by equation (1.16) implies that

(1.21)  b_{kl} ≥ n^{2} + 1,

contradicting the fact that B satisfies condition (i) of Definition (1.1). Therefore we must have a_{ij} ≥ 1 for all i, j. A similar argument, which we leave to the reader, shows that a_{ij} ≤ m^{2} for all i, j. Since the a_{ij} represent all of the m^{2} residue classes modulo m^{2}, it follows that A satisfies condition (i) of Definition (1.1). This proves the lemma.

Remark (1.22): I don’t know whether M_{2} is an inescapable submonoid of A(Z).

The following definition is motivated by the corresponding notions from elementary number theory.

Definition (1.23): Let S be a monoid with identity element s with respect to an operation ∘. We will say that element t of S is irreducible if t ≠ s and if for any elements u, v of S such that t = u∘v we have either u = s or v = s. An element t of S is said to be left prime if for any elements u, v, w of S such that t ∘ u = v ∘ w, there is an element x of S such that v = t ∘ x. This definition 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 definition 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_{2} of all magic squares. In other words, every magic square can be written as a product of irreducible magic squares.

In order to prove that the monoid M_{2} is free, we only have to prove that every magic square is 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_{2} follows, in analogy with the proof of the fundamental theorem of arithmetic, by a simple induction as soon as one has proved that an irreducible magic square is left prime. Therefore, the freeness of M_{2} is a consequence of the following simple lemma.

Lemma (1.25): (Irreducible Implies Prime) Let A, B, C, D be magic squares such that A∗B = C ∗ D. Suppose A is m × m, B is n × n, C is p × p where m ≤ p. If A is irreducible then there is a magic square E such that C = A ∗ E.

Proof: We will first 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 ∗ B = C ∗ D. If we view F is the product C ∗ D then F is partitioned into p × p squares. Let C_{1} denote the p × p square which contains the number 1 in F. Then C_{1} is an exact replica of the magic square C and in particular contains all of the entries of F which are ≥ 1 and ≤ p^{2} and none of the entries of F which are > p^{2}. If we now view F as the product A ∗ B then F is instead partitioned into m × m squares. The first such square contains the numbers from 1 to m^{2} and is denoted A_{1}. The second such square contains the numbers from m^{2} + 1 to 2m^{2} and is denoted A_{2} and so on. If m does not divide p then in particular m < p and m^{2} does not divide p^{2}. Let h be the smallest integer such that h · m^{2} ≥ p^{2}. Then the square A_{h} lies partly in the square C_{1} and partly outside of it. Let g > 0 be an integer. If g < h then the square A_{g} lies entirely inside C_{1} and if g > h then A_{g} lies entirely outside of C_{1}. Since A_{h} is m × n and C_{1} is p × p with m < p, there must be a column of C_{1} which does not meet the square A_{h}. Since that column must be covered by disjoint squares A_{g} lying entirely inside of C_{1}, it follows that m does divide p after all. Retaining the definition of h, we see that h · m^{2} = p^{2} and therefore h = t^{2} for some positive integer t. The square C_{1} is therefore covered by squares A_{g} and is therefore of the form A ∗ E where E is a t × t 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_{2} of all magic squares is freely generated by the set of all 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.

§2 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 define magic N-dimensional cubes (also known as magic N-cubes) in a similar way to that given in Definition 1.1 and the reader is invited to provide the definition herself, the only caution being that the condition (iv) on the sum over the diagonals is generalized in N dimensions to the sum over the longest diagonals, the ones joining opposite corners of the N-cube. Similarly one can, with only minor changes, define the operation ∗ on the set M_{N} of all magic N-cubes. The same arguments then apply with only minor modifications to prove that the set M_{N} of all magic N-cubes forms a free monoid. We omit the details of this generalization, whose only complications are notational.

One can in fact generalize much further with no essential difficulty. Since some of these generalizations might be of independent interest, and since to some extent they facilitate the discussion of §3, we will indicate some of them briefly, leaving the verification 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, σ) consisting of a finite subset F of H and an element σ of S. The pair (F, σ) is called a frame, F is called the turf of the frame and σ is called the nominal order of the frame. Then F(S, H) forms a monoid in which the product of (F_{1}, σ_{1}) and (F_{2}, σ_{2}) is the frame (F_{3}, σ_{1}σ_{2}), where F_{3} is the set of all elements of the form σ_{1}(f_{2})f_{1} with f_{1} ∈ F_{1} and f_{2} ∈ F_{2}. If we view a magic N-cube as an array, hence a function defined on a certain cubical subset of Z^{N}, this definition allows us to consider domains which instead are finite subsets F of arbitrary monoids H. It should be clear that the monoid F(S, H) is simply the semidirect product of S and the monoid P(H) of finite 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 fixed throughout the discussion. If (F, σ) ∈ F(S, H), then by an array of type (F, σ) with entries in G, we mean a triple (F, σ, λ) where λ is a function from F to G. If we do not wish to specify the type (F, σ) of the array, we will refer to it as an array framed in F(S, H). We call σ the order of the array (F, σ, λ). We denote by A(S, H, G) the set of all arrays framed in F(S, H). Then A(S, H, G) is naturally a semigroup in which the product of (F_{1}, σ_{1}, λ_{1}) and (F_{2}, σ_{2}, λ_{2}) is the array (F_{3}, σ_{3}, λ_{3}), where (F_{3}, σ_{3}) is the product of (F_{1}, σ_{1}) and (F_{2}, σ_{2}) in F(S, H) and where the function λ_{3} is defined by

λ_{3}(h_{3}) = ∑′(σ_{1}(λ_{2}(h_{2}) + u) + λ_{1}(h_{1}))

where the summation runs over all elements (h_{1}, h_{2}) ∈ F_{1} × F_{2} such that h_{3} = σ_{1}(h_{2})h_{1}. If g is an element of G, we will denote by g the framed array g = ({e}, s, λ : {e} → G) defined by λ(e) = g, where e is the identity element of H. This notation generalizes and supersedes the notation u introduced in §1. If g is taken to be an element of G such that g + u = 1_{G}, where 1_{G} is the identity element of G, then A(S, H, G) is actually a monoid whose identity element 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 finite partial functions from H to G, this being the kernel of the homomophism (F, σ, λ) ↦ σ of A(S, H, G) onto S.

(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 traditionally considered in the study of magic N-cubes also form a monoid and use that insight 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.

\begin{aligned}M_{1}^{(1)} & = & F(S, H) & M_{1}^{(n)} & = & ∏_{i=1}^{n} M_{1}^{(1)} \\ M_{2}^{(1)} & = & F(S, P(H)) & M_{2}^{(n)} & = & ∏_{i=1}^{n} M_{2}^{(1)}. \end{aligned}

In the definition of M_{1}^{(n)} and M_{2}^{(n)} we use the product notation to denote the fibre product over S, not the cartesian product. In practice, an element of M_{1}^{(1)} will be a subset of H over which we wish to sum the entries of an array. In the case of magic N-cubes, such a subset might 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 fixed and H = Z^{N}, we can let n = 2^{N−1} and view the set of n great diagonals of the N-cube as an element of M_{1}^{(n)}. In that case, if (F_{i}, σ_{i}) is an N-cube for i = 1, 2 and if A_{i} is the element of M_{1}^{(n)} corresponding to the set of great diagonals of (F_{i}, σ_{i}), then the product in M_{1}^{(n)} of A_{1} and A_{2} will be the set of great diagonals of the product of (F_{1}, σ_{1}) and (F_{2}, σ_{2}). This is quite satisfying but does not suffice to describe the orthogonals. 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_{2}^{(1)}. The orthogonals parallel to a particular axis of an N-cube form an element of M_{2}^{(1)}. If for i = 1, 2, B_{i} is the element of M_{2}^{(1)} corresponding to the orthogonals of an N-cube (F_{i}, σ_{i}) parallel to a particular axis (the same axis for i = 1, 2), then the product in M_{2}^{(1)} of B_{1} and B_{2} is the element corresponding to the set of orthogonals in that same direction in the product of (F_{1}, σ_{1}) and (F_{2}, σ_{2}). This is 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_{2}^{(N)}. Thus, the set of summation conditions which a magic N-cube is expected to satisfy is an element of the monoid

M_{1}^{(n)} × M_{2}^{(N)},

where n = 2^{N−1}. In order to simplify the notation, we observe that the monoid M_{1}^{(1)} may be embedded in the monoid M_{2}^{(1)} by associating to a subset F of H the singleton {F }. Therefore, we may regard the set of summation conditions as an element of M_{2}^{(d)} where d = N + 2^{N−1}. These considerations motivate the following definition: let (F, σ, λ) be an element of A(S, H, G), let d be a positive integer and let C = (C_{1}, …, C_{d}) be an element of M_{2}^{(d)} such that for 1 ≤ i ≤ d, every element of C_{i} is a subset of F. We say that the array (F, σ, λ) is C-stochastic if for 1 ≤ i ≤ d and for E in C_{i}, the summation ∑_{h∈E} λ(h) is independent of i and E. Suppose that ϕ is a homomorphism from a submonoid F of the monoid F(S, H) to the monoid M_{2}^{(d)} such that for every (F, σ, λ) in F the order of ϕ(F, σ, λ) is σ. We will say that an array (F, σ, λ) is phi-stochastic if (F, σ) belongs to F and if (F, σ, λ) is ϕ(F, σ)-stochastic. If F and ϕ are such, we denote by M(ϕ) the subset of A(S, H, G) consisting of all ϕ-stochastic arrays. Then M(ϕ) is a submonoid of A(S, H, G). Now suppose that the only pair (σ, g) ∈ S × G with σ(g) = 1_{G} is (1_{S}, 1_{G}), where 1_{S} is the identity element of S. Then then the monoid M(ϕ) is a persuasive submonoid of A(S, H, G). By placing some restrictions on the monoid G, one can generalize further the notions of stochas-

ticity introduced in (3). More precisely, one assumes that G is the additive group of an algebraically closed field k. In that case, one can introduce monoids of summation conditions by means of certain classes of infinite 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 example of it, namely in connection with the monoids S_{N}(t, g) defined in the next section. So we will confine our attention to that example, which we describe in the next section without reference to infinite dimensional varieties.

§3 Magic N-cubes with remarkable power sum properties

Let n ∈ [1, N]. An n-cube contained in an N-dimensional cubical array f of order d is then the intersection of that array with a certain number of hyperplanes parallel to the faces of the array. 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_{N}(t, g) the set of all magic N-cubes A satisfying the following two conditions:

(a) The order of A is a power of t, say t^{s}.

(b) For 1 ≤ n ≤ N, conjugate n-dimensional subcubes have equal sums of the r-th powers of their entries, for 0 ≤ r ≤ g(n). We also denote by M_{N}(t) the monoid of all magic N-cubes satisfying only condition (a) above.

In the proof, we will use notation introduced in (1) and (2) of §2.

Theorem (3.1): Let t, g be as above. Then S_{N}(t, g) is an inescapable submonoid of the monoid M_{N} of all magic N-cubes. Furthermore, S_{N}(t, g) is a free monoid on infinitely many generators.

Proof: Let A, B be elements of S_{N}(t, g) and let C be their product. Any n-dimensional subcube K of C is the product in F(Z, Z^{N}) of the corresponding subcubes K′, K′′ 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, Z^{N}) by replacing, e.g. K′ by the pair (K′, t^{s}), where t_{s} is the order of C. Here the action of Z on Z^{N} is the usual Z-module structure on Z^{N}. Since we care about the entries of these n-cubes, we are concerned with the elements of A(S, Z^{N}, G), where S, G are Z under multiplication and addition respectively and where G is viewed as an S-module via (s, g) ↦ s^{N}g. Denote by f, f′, f′′ the functions that give the entries of the subcubes K, K′, K′′ respectively. We then have

(3.2)  \begin{aligned}∑_{v∈K} f(v)^{r} & = ∑_{v′∈K′} ∑_{v′′∈K′′}(t^{sN}f′′(v′′) + f′(v′))^{r} \\ & = ∑_{j=0}^{r} \binom{r}{j} ( ∑_{v′∈K′} f′(v′)^{r−j}) · ( ∑_{v′′∈K′′} t^{jsN}f′′(v′′)^{j}) \end{aligned}

Since the sums over K′ and K′′ are independent of the choices of the n-cubes K′, K′′ within their conjugacy classes, the sum over K is independent of the choice of the n-cube K within its conjugacy class. This proves that S_{N}(t, g) is a submonoid of M_{N}. Furthermore, the submonoid S_{N}(t, g) is an inescapable submonoid of M_{N}. Indeed, suppose A, B, C are magic N-cubes such that A ∗ B = C and suppose that C belongs to S_{N}(t, g). Choose K, K′, K′′ as before and use the above identity for 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 fix the n-cube K′′ and allow the n-cube K′ to vary in its conjugacy class, it follows by an easy induction on r that, for 1 ≤ r ≤ g(n), the sum of the r-th powers of the entries of the entries of K′ are independent of the choice of K′ within its conjugacy class. Similarly, by fixing K′ and letting K′′ vary in its conjugacy class we see that the sum of the r-th powers of the entries of K′′ is independent of the choice of the n-cube K′′ within its conjugacy class. This proves that S_{N}(t, g) is an inescapable submonoid of M_{N}. It follows that an irreducible element of S_{N}(t, g) is also irreducible when viewed as an element of M_{N}. To see that S_{N}(t, g) is free, it suffices to prove the analogue of the Irreducibility Implies Prime Lemma for this situation. So suppose that A, B, C, D are elements of S_{N}(t, g) of orders m, n, p, q where m ≤ p, and suppose that A ∗ B = C ∗ D with A irreducible. In the proof of the freeness of M_{N}, which we left to the reader, one proves along the way that M_{N} satisfies the analogue of the Irreducibility Implies Prime Lemma. Since A is also irreducible as a magic N-cube, it follows that we can write C as the product A ∗ E of A and another magic N-cube E. It then follows that E belongs to S_{N}(t, g). Therefore, S_{N}(t, g) is free. Finally, to see that S_{N}(t, g) has infinitely many generators, we will show that it contains infinitely many irreducible magic N-cubes. In Theorem 1 on p.620 of [A-L], it is shown how to construct a magic N-cube of order t^{M} for every positive integer M such that t divides MN and such that M > 1 when t is even. We will call that construction the method of Prouhet sequences. Hence infinitely many elements of M_{N}(t) are constructed by the method of Prouhet sequences. Furthermore, in Theorem 5 on p.626 of [A-L] it is shown that for 1 ≤ n ≤ N every magic N-cube A constructed in this way has the following property: for all n, conjugate n-dimensional subcubes of A have equal sums of the k-th powers of their entries for k = 0, 1, …, nr − 1. It follows that all but finitely many of the magic N-cubes in M_{N}(t) constructed by the method of Prouhet sequences belong to S(t, g). Therefore we will be done as soon as prove the following lemma.

Lemma (3.3): If M + 1 is divisible by t then the magic N-cube of order t^{M} constructed by the method of Prouhet sequences is irreducible.

Proof: We refer the reader to Theorem 1 of [A-L] or to [A1], pp.16-18, for details of the method of Prouhet sequences. Let A = (a_{i_{1},...,i_{N}}) be a magic N-cube of order t^{M} constructed by the method of Prouhet sequences. Let (i) = (i_{1}, …, i_{N}) and (j) = (j_{1}, …, j_{N}) be the N-tuples such that a_{(i)} = 0, a_{(j)} = 1. Then we have (i) = (0, …, 0) and (j) = (t^{M} − 1, …, t^{M} − 1, 0). It follows that the entries 0 and 1 are on opposite faces of the N-cube and cannot lie in any proper subcube of dimension N. Therefore A is irreducible.

§4 Divergence of generating functions

It is well known that the freeness of these monoids implies identities of formal Dirichlet series of the form

∑_{n=1}^{∞} \frac{a_{n}}{n^{s}} = (1 − ∑_{n=3}^{∞} \frac{b_{n}}{n^{s}} )^{−1}

where a_{n} denotes the number of elements of size n in the monoid and b_{n} denotes the number of irreducible elements of size n of the monoid. We will now consider the convergence properties of these formal Dirichlet series and their associated power series.

Theorem (4.1): Let N, a_{n} (resp. b_{n}) be the number of magic N-cubes (resp. irreducible magic N-cubes) of order n. Then the formal power series

∑_{n=1}^{∞} a_{n}t^{n}, ∑_{n=3}^{∞} b_{n}t^{n}

both have radius of convergence equal to 0. In particular, the formal Dirichlet series introduced above are everywhere divergent for this monoid.

Proof: Let X = (X_{kℓ}), 0 ≤ k, ℓ ≤ N − 1 denote the N × N matrix whose (k, ℓ)-th entry is 1 + Nδ_{kℓ}. If M is a positive integer relatively prime to (2N − 1)! and if we view X as having entries in the ring Z/MZ then X satisfies the following conditions: (1) X is invertible; (2) Every entry of X is a unit of Z/MZ; (3) If e is a vector whose entries are all ±1 then the entries of the vector Xe are units of Z/MZ.

For every such M, we can construct a magic N-cube

MA = (_{M}A_{i_{1},...,i_{N}})

of order M whose entries are defined by

MA_{i_{1},...,i_{N}} = ∑_{k=0}^{N−1} j_{k}M^{k},

where the digits j_{k} are determined by the conditions 0 ≤ j_{k} ≤ M − 1 and

j_{k} ≡ ∑_{k=0}^{N−1} X_{kℓ}i_{ℓ} (mod M).

For a discussion of the ideas behind this construction, see §1 of the author’s paper [A1]. We will merely remark that:

(I) condition (1) guarantees that each of the numbers 0, 1, …, M^{N} − 1 occurs exactly once in

MA; (II) condition (2) guarantees that for any fixed k, the k-th digits of the entries of any orthogonal

of _{M}A are 0, 1, …, M − 1 in some order; (III) condition (3) guarantees that for any fixed k, the k-th digits of the entries of any diagonal

of _{M}A are 0, 1, …, M − 1 in some order. Peter Szüsz pointed out to the author that the observations (I),(II),(III) imply that if σ is any permutation of the numbers 0, 1, 2, … M − 1 then the array _{M}A^{σ} defined by

MA_{i_{1},...,i_{N}}^{σ} = σ(_{M}A_{i_{1},...,i_{N}})

is also a magic N-cube. Therefore a_{M} ≥ M! whenever M is relatively prime to (2N − 1)!, and that already suffices to prove that the summation ∑_{n=1}^{∞} a_{n}t^{n} diverges for t ≠ 0. To show that ∑_{n=3}^{∞} b_{n}t^{n} also diverges, we first prove that the magic N-cube _{M}A is irreducible. Indeed, the number 0 is placed in the center of _{M}A and the number 1 is placed in the box indexed by (i) = (i_{0}, …, i_{N−1}) where (i) satisfies 0 ≤ i_{k} ≤ M − 1 and

(4.2)  ∑_{ℓ=0}^{N−1}(1 + Nδ_{kℓ}) · i_{k} ≡ δ_{0k} (mod M)

for 0 ≤ k ≤ N − 1. It follows that i_{1} = i_{2} = … = i_{N−1} and

\begin{aligned}(N + 1) · i_{0} + (N − 1) · i_{1} & ≡ 1 (mod M) \\ i_{0} + (2N − 1) · i_{1} & ≡ 0 (mod M). \end{aligned}

Solving these equations modulo M we obtain

i_{0} ≡ \frac{2N − 1}{2N^{2}} (mod M) and i_{1} ≡ \frac{−1}{2N^{2}} (mod M).

In particular, since M is relatively prime to (2N − 1)!, both i_{0} and i_{1} are units modulo M. If _{M}A were reducible, we could tile it with subcubes of order R with 0 and 1 lying in a common N-cube B of order R. Here R < M is a factor of M. The N cube B would have to contain all of the nonnegative integers less than R^{N}. For 0 ≤ ν ≤ R − 1, the integer ν occurs at the point ν · (i). Therefore, for 0 ≤ ν ≤ R − 1 the N-cube B would contain the multiple ν · (i) of (i). In particular, for 0 ≤ ν ≤ R − 1, both νi_{0} and νi_{1} must lie among the elements 0, 1, …, R − 1 of Z/MZ. Since i_{0} and i_{1} are units modulo M, they cannot be divisible by R. Therefore the only way all the multiples νi_{0} and νi_{1} with 0 ≤ ν ≤ R − 1 can be < R is if i_{0} = i_{1} = 1. But then 1/N ≡ i_{0} − i_{1} ≡ 0 modulo M, which is impossible. Therefore 0 and (i) cannot lie in a common subcube, which proves that MA is irreducible. Furthermore, the proof that _{M}A is irreducible depends only on the locations of the numbers 0, 1, …, D − 1, where D is the largest divisor of M other than M itself. Therefore any permutation σ that fixes these numbers will map _{M}A to an irreducible magic N-cube _{M}A^{σ}. Since M is relatively prime to (2N − 1), we have D = M/p, where p is the smallest prime dividing M and p ≥ (2N + 1). Therefore, we have

b_{M} ≥ (M − D)! > Γ (\frac{2MN}{2N + 1}) ≥ Γ(4M/5)

which implies that the series ∑_{n=3}^{∞} b_{n}t^{n} diverges for t ≠ 0.

We have a similar result for the monoids S_{N}(t, g), but unfortunately somewhat weaker: we can only prove that the Dirichlet series diverge.

Theorem (4.3): Let N > 1 be an integer and let g : [1, N] → S be any function. For every positive integer n denote by c_{n} (resp. d_{n}) the number of magic N-cubes (resp. irreducible magic N-cubes) of order n belonging to the monoid S_{N}(t, g). Then the Dirichlet series

∑_{n=1}^{∞} \frac{c_{n}}{n^{s}} , ∑_{n=1}^{∞} \frac{d_{n}}{n^{s}}

diverge for every complex number s.

Proof: Let n run over all positive integers M such that t divides MN and such that M > 1 if t is even. If σ is a permutation on the integers 0, 1, …, M − 1 and if x is an integer such that 0 ≤ x ≤ t^{M} − 1, then we write σ(x) to denote the integer obtained by permuting the digits of x in the base t according to the permutation σ. If (i) = (i_{1}, …, i_{N}) is an N-tuple of integers such that 0 ≤ i_{ν} ≤ t^{M} − 1 for 1 ≤ ν ≤ N then we write σ · (i) to denote the N-tuple obtained from (i) by replacing i_{N} by σ(i_{N}). Let A = (a_{i_{1},...,i_{N}}) be the magic N-cube of order t^{M} constructed by the method of Prouhet sequences (cf. [A-L],Theorem 1). As noted in the proof of Theorem 3.1, for all but at most finitely many M such that t divides MN, the magic N-cube lies in S_{N}(t, g). If σ is a permutation on 0, …, M − 1 then we define the array A^{σ} = (a_{i_{1},...,i_{N}}^{σ}) by the rule

a_{(i)}^{σ} = a_{σ·(i)}.

It is easy to see that for 1 ≤ k ≤ N the mapping (i) ↦ σ · (i) maps k-subcubes to k-subcubes and preserves the relation of conjugacy of subcubes. It follows that A^{σ} also belongs to S_{N}(t, g). This shows that for n = t^{M} with M sufficiently large and such that t divides MN, we have c_{n} ≥ M!. Furthermore, since the proof of Lemma 3.3 shows that A^{σ} is also irreducible, we actually have d_{n} ≥ M!. Therefore we have, letting M run over sufficiently large multiples of t,

∑_{n=1}^{∞} \frac{c_{n}}{n^{s}} ≥ ∑_{n=1}^{∞} \frac{d_{n}}{n^{s}} ≥ ∑ \frac{M!}{t^{Ms}}

and the summation on the right diverges by the ratio test.

Since the problem of determining the numbers a_{n}, b_{n}, c_{n}, d_{n}, and others like them, or at least giving good estimates for them, is a matter of independent interest, we summarize in the following theorem the estimates we have obtained. Undoubtedly one can easily do much better.

Theorem (4.4): We have the following inequalities.

(i) a_{M} ≥ M! if M is relatively prime to (2N − 1)!. (ii) b_{M} ≥ (M − D)! if M is relatively prime to (2N − 1)!, where D is the largest proper divisor of

M; (iii) c_{n} ≥ d_{n} ≥ M! if n = t^{M}.

The estimates (i) and (ii) could be improved by studying the question of how many matrices one could have used instead of the matrix X we actually chose for the proof of Theorem 4.1. This would only improve the estimate by at most a factor which is polynomial in M. We haven’t investigated this in any detail since we believe that the actual growth of b_{M} is much larger than any polynomial multiple of M!.

References

[A1] Allan Adler, “Magic Cubes and the 3-adic Zeta Function,” Mathematical Intelligencer 14 (1992) 14-23

[A2] Allan Adler, “Magic N-cubes form a free monoid,” preprint [A-L] Allan Adler and S.-Y. Robert Li, “Magic N-Cubes and Prouhet Sequences,” American Mathe-

matical Monthly 84 (1977) 618-627 [A-W] Allan Adler and Lawrence C. Washington, “p-adic L-functions and p-dimensional magic cubes,”

J.Number Theory 52 (1995) 179-197

[An] W.S.Andrews, Magic Squares and Cubes, Dover, New York, 1960 [Ax1] James Ax, Private Conversation, 1974

[Ax2] James Ax, “Group-theoretic treatment of the axioms of quantum mechanics,” Found. Phys. 6 (1976) 371-399

[E1] Leonhard Euler,“Recherches sur une nouvelle espece de quarres magiques,” Commentationes arithmeticae 2 (1849) 302-361, Opera Omnia, Series I^{a}, Vol. VII, pp.290-392 Leipzig and Berlin, B.G.Teubner 1923 [#530 in Enestrom’s list]

[E2] Leonhard Euler, “De carris magicis,” Commentationes arithmeticae 2 (1849) 593-602, Opera Postuma 1 (1862) 140-151 [#795 in Enestrom’s list]

[F] Pierre de Fermat, Letter to Mersenne, April 1, 1640,Oeuvres de Fermat, Vol.II,p.191

[Ge] I.M. Gelfand, Silliman Lectures, part III, Yale University, Nov.29, 1989

[Iw] Kenkichi Iwasawa, Lectures on p-adic L-functions, Princeton University Press and University of Tokyo Press, Princeton, NJ 1972

[K] Maurice Kraitchik, Traité des Carrées Magiques, Paris, Gauthier-Villars C^{ie}

[Me] Jerome S. Meyer, Fun With Mathematics, World Publishing Company, Cleveland and New York, 1952

[Mo1] Marston Morse, “Recurrent geodesics on a surface of negative curvature,” Transactions of the American Mathematical Society 22 (1921) 84-100 [Collected Papers, vol. 2, pp.24-40]

[Mo2] Marston Morse, Symbolic Dynamics, Lectures by Marston Morse, 1937-1938 Notes by Rufus

Oldenburger, edition with preface, 1966, Institute for Advanced Study, Princeton [M-H 1] Marston Morse and G.A. Hedlund, “Symbolic Dynamics,” American Journal of Mathematics

60 (1938) 815-866 [M-H 2] Marston Morse and G.A. Hedlund, “Unending Chess, Symbolic Dynamics and a Problem in

Semigroups,” Duke Math. Journal 11 (1933) 1-7

[R1] S. Ramanujan, Notebooks of Srinivasa Ramanujan, vol.II, Chapter 2, Facsimile Edition, Tata Institute, Bombay 1957

[R2] S. Ramanujan, Ramanujan’s Notebooks, Part I, edited by Bruce C. Berndt Springer-Verlag, NY 1985

[S1] Richard Stanley, “Linear homogeneous Diophantine equations and magic labelings of graphs,” Duke Math. J. 40 (1973) 607-632

[S2] Richard Stanley, “Magic labelings of graphs, symmetric magic squares, systems of parameters and Cohen-Macaulay rings,” Duke Math. J. 43 (1976) 511-531

[W1] André Weil, Private Conversation, 1976

[W2] André Weil, “Sur les périodes des intégrales abéliennes,” Comm. Pure and Applied Math. XXIX (1976) 813-819, Collected Papers, vol. 3, [1976b], pp.392-397