Counting Magic Squares

Our first example deals with counting magic $4\times 4$ squares. We call a $4\times 4$ array of nonnegative numbers a magic square if the sums of the $4$ entries along each row, along each column and along the two main diagonals equals the same number $s$ , the magic constant. Let us start with counting magic $4\times 4$ squares that have the magic constant $1$ . Associating variables $x_1,\ldots,x_{16}$ with the $16$ entries, the conditions of a magic $4\times 4$ square of magic sum $1$ can be encoded into the following input file ``EXAMPLES/magic4x4'' for LattE.

10 17
1 -1 -1 -1 -1  0  0  0  0  0  0  0  0  0  0  0  0
1  0  0  0  0 -1 -1 -1 -1  0  0  0  0  0  0  0  0
1  0  0  0  0  0  0  0  0 -1 -1 -1 -1  0  0  0  0
1  0  0  0  0  0  0  0  0  0  0  0  0 -1 -1 -1 -1
1 -1  0  0  0 -1  0  0  0 -1  0  0  0 -1  0  0  0
1  0 -1  0  0  0 -1  0  0  0 -1  0  0  0 -1  0  0
1  0  0 -1  0  0  0 -1  0  0  0 -1  0  0  0 -1  0
1  0  0  0 -1  0  0  0 -1  0  0  0 -1  0  0  0 -1
1 -1  0  0  0  0 -1  0  0  0  0 -1  0  0  0  0 -1
1  0  0  0 -1  0  0 -1  0  0 -1  0  0 -1  0  0  0
linearity 10 1 2 3 4 5 6 7 8 9 10
nonnegative 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Now we simply invoke the counting function of LattE by typing:

    ./count EXAMPLES/magic4x4

The last couple of lines that LattE prints to the screen look as follows:

Total Unimodular Cones: 418
Maximum number of simplicial cones in memory at once: 27

*****  Total number of lattice points: 8  ****

Computation done.
Time: 1.24219 sec

Therefore, there are exactly $8$ magic $4\times 4$ squares that have the magic constant $1$ . This is not yet impressive, as we could have done that by hand. Therefore, let us try and find the corresponding number for the magic constant $12$ . Since this problem is a dilation (by factor $12$ ) of the original problem, we do not have to create a new file. Instead, we use the option ``dil'' to indicate that we want to count the number of lattice points of a dilation of the given polytope:

    ./count dil 12 EXAMPLES/magic4x4

The last couple of lines that LattE prints to the screen look as follows:

Total Unimodular Cones: 418
Maximum number of simplicial cones in memory at once: 27

*****  Total number of lattice points: 225351  ****

Computation done.
Time: 1.22656 sec

Therefore, there are exactly $225351$ magic $4\times 4$ squares that have the magic constant $12$ . (We would NOT want to do THAT one by hand, would we?!)

Here is some amazing observation: the running time of LattE is roughly the same for counting magic squares of sum $1$ and of sum $12$ . This phenomenon is due to the fact that the main part of the computation, the creation of the generating function that encodes all lattice points in the polytope, is nearly identical in both cases.

Although we may be already happy with these simple counting results, let us be a bit more ambitious and and let us find a counting formula that, for given magic sum $s$ , returns the number of magic $4\times 4$ squares that have the magic constant $s$ .

For this, simply type (note that LattE invokes Maple to simplify intermediate expressions):

    ./ehrhart simplify EXAMPLES/magic4x4

The last couple of lines that LattE prints to the screen looks as follows:

Rational function written to EXAMPLES/magic4x4.rat

Computation done. 
Time: 0.724609 sec

We are informed that this call created a file ``EXAMPLES/magic4x4.rat'' containing the Ehrhart series as a rational function:

(t^8+4*t^7+18*t^6+36*t^5+50*t^4+36*t^3+18*t^2+4*t+1)/(-1+t)^4/(-1+t^2)^4

Now we could use Maple (or your favorite computer algebra software) to find a series expansion of this expression.

$$\frac{t^8+4*t^7+18*t^6+36*t^5+50*t^4+36*t^3+18*t^2+4*t+1}{(-1+t)^4(-1+t^2)^4}$$

$$= 1+8t^1+48t^2+200t^3+675t^4+1904t^5+4736t^6+10608t^7+21925t^8+$$

$$42328t^9+77328t^{10}+134680t^{11}+225351t^{12}+364000t^{13}+570368t^{14}+$$

$$869856t^{15}+{O}(t^{16})$$

The summands $8t$ and $225351t^{12}$ reconfirm our previous counts.

Although this rational function encodes the full Ehrhart series, it is not always as easy to compute as for magic $4\times 4$ squares. As it turns out, adding and simplifying rational functions, although in just one variable $t$ , can be extremely costly due to the high powers in $t$ and due to long integer coefficients that appear.

However, even if we cannot compute the full Ehrhart series, we can at least try and find the first couple of terms of it.

    ./ehrhart 15 EXAMPLES/magic4x4

The last couple of lines that LattE prints to the screen look as follows:

Memory Save Mode: Taylor Expansion:
1
8t^1
48t^2
200t^3
675t^4
1904t^5
4736t^6
10608t^7
21925t^8
42328t^9
77328t^10
134680t^11
225351t^12
364000t^13
570368t^14
869856t^15
Computation done.
Time: 1.83789 sec

Again, our previous counts are reconfirmed.

Nice, but the more terms we want to compute the more time-consuming this task becomes. Clearly, if we could find sufficiently many terms, we could compute the full Ehrhart series expansion in terms of a rational function by interpolation.