``Six Little Squares and How their Numbers Grow''
Maple Worksheets and Supporting Documentation

by Matthias Beck and Thomas Zaslavsky

Best Viewed With Any Browser

This page provides access to the principal Maple computations on which our article was based, and some supplementary material.

There are three kinds of computations: the geometrical ones based on inside-out Ehrhart theory with generating functions and quasipolynomial counting functions, those which enumerate and count the squares individually, and one oddball in which we calculate the number of squares by a complicated (but effective) formula.

We include two more Maple computations. One is for weak 3x3 squares, and the other is for a 2x3 Latin rectangle (not in the "Six little squares" paper).

  1. Geometrical solutions

    LattE input files and results.

    These files may be posted at a later time.

    Maple files of computations based on the LattE output.

    Each set begins with the same "front end" that sets up the generating function as a rational function, but then takes the computations in a different direction.


    1. The first set computes the quasipolynomial constituents via inside-out Ehrhart theory, and lists and analyzes their coefficients (except in the magic cases, which are simple).
      1. Magic squares by magic sum and by upper bound.
      2. Semimagic squares counted by magic sum.
      3. Semimagic squares counted by upper bound.
      4. Magilatin squares counted by magic sum.
      5. Magilatin squares counted by upper bound.

    2. The second set computes the generating functions out to a large number of terms, in fact up to termenddegree . Up to 10000 terms can be done quickly by the Maple program. The user can set the value of "enddegree". This set does not compute the quasipolynomials; instead, its output (which may be very long) lists the values of the sequence, which it obtains by series expansion of the rational generating function.
      The programs with their output for "enddegree:=500" are also available as guides to correct use.
      1. Magic squares by magic sum and by upper bound.
      2. Semimagic squares counted by magic sum.
      3. Semimagic squares counted by upper bound.
      4. Magilatin squares counted by magic sum.
      5. Magilatin squares counted by upper bound.

    3. These files contain tables of values in the form "t, termt", one per line, for t from the initial positive term to t=10000. They are in the Online Encyclopedia of Integer Sequences (OEIS).
      1. Magic squares by magic sum.
      2. Magic squares by upper bound.
        • The total number of squares with upper bound t, Mc(t), for t up to 10000. Sequence A108576 in the OEIS.
        • The number of symmetry types of squares with upper bound t, mc(t), for t up to 10000. Sequence A108577 in the OEIS.
        • The number of reduced squares with upper bound t=2n, Rmc(2n), for n up to 10000. Sequence A174256 in the OEIS. (The same as reduced magic squares by magic sum 3n.)
        • The number of symmetry types of reduced squares with upper bound t=2n, rmc(2n), for n up to 10000. Sequence A174257 in the OEIS. (The same as reduced symmetry types by magic sum 3n.)
      3. Semimagic squares counted by magic sum.
      4. Semimagic squares counted by upper bound.
      5. Magilatin squares counted by magic sum.
      6. Magilatin squares counted by upper bound.

    4. The third set computes the constituents and checks that they're correctly evaluated by using them to generate more than two full periods of values, which are compared with the coefficients of the generating series. These programs are written only for the magilatin computation, since that contains the semimagic computation as a sub-computation, so validating the former gives confidence also in the latter. The affine program computes the truncated constituents (period 120) and the correction constituents (period 21), whose difference gives the actual values (period gcd(21,120) = 840) of the affine magilatin count.
      1. Magilatin squares counted by magic sum.
      2. Magilatin squares counted by upper bound.

  2. Direct enumeration


    Maple files of computations and results.

    The Maple programs compute the numbers by individually generating and counting all squares. This is slow but the programs are simple and therefore trustworthy. The programs contain the generating functions found by the geometrical method and compare them with the direct counts, thereby confirming the correctness of the generating functions.

    1. Magic squares counted by magic sum or upper bound. Maple programs count.ma.mws (by magic sum) and count.mc.mws (by upper bound). They count magic squares in a completely elementary and dependable way (generating one square of each symmetry type), up to high enough values of the magic sum to completely confirm the results of the Ehrhart method.
    2. Semimagic squares counted by magic sum:
      • Maple program count.sa100.mws. It counts semimagic squares in a completely elementary and dependable way (generating one square of each symmetry type), up to high enough values of the magic sum to give considerable confidence in the Ehrhart results, but it is a long way from a complete confirmation (which we estimate would take many millenia).
      • Another Maple program count.sa3.sn.mws. It counts semimagic squares by magic sum, by direct enumeration of supernormalized squares and combining these numbers (by a simple formula) to get the number of all squares. (This program also prints the number of symmetry types, thus giving a long list of numbers.) The count is slow, though faster than the preceding program, so the results stop before 100.
    3. Semimagic squares counted by upper bound: Maple program count.sc100.mws. It counts semimagic squares in a completely elementary and dependable way (generating one square of each symmetry type), up to high enough values of the bound (more than one full period of 60) to give considerable confidence in the Ehrhart results, but it is not a complete confirmation.
    4. Magilatin squares counted by magic sum: Maple program count.mla100.mws. It counts semimagic squares in a completely elementary and dependable way (generating every square), up to high enough values of the magic sum (sum 100) to give considerable confidence in the Ehrhart results, but it is far from perfect confirmation, which we estimate would take a million years, more or less, by this method.
    5. Magilatin squares counted by upper bound: Maple program count.mlc91.mws. It counts semimagic squares in a completely elementary and dependable way (generating every square), up to bound 91 (more than one full period of 60), giving additional confidence in the Ehrhart results; but it is not perfect confirmation, which we estimate might take a hundred thousand years by this method.

  3. Indirect counting

      This method is complicated (and the formula took weeks to compute and verify) but we are confident it is correct because we have cross-checked small values and the principal constituent against the other methods.

    1. Semimagic squares counted by magic sum: Maple program count.sa3.formula.mw calculates the numbers of semimagic squares by magic sum, using a complicated formula, and finds all 840 constituent polynomials within a reasonable time.
    2. A similar program, Maple program count.sa3.formula-detailed.mw, is the same; but it also evaluates the period, finding that the period of the constituents with index not a multiple of 4 is a divisor of 420 (half the overall period).
    3. Explanation of the complicated formula implemented in that Maple program. (Download PostScript file, 270 KB; PDF file, 110 KB.)

  4. Weak semimagic

    1. We used a Maple program to find the number of weakly semimagic squares, i.e., without any distinctness requirement. This is easy to do by direct enumeration.

  5. Other magical counting problems

    1. Here is the Maple program for the number of 2x3 magilatin rectangles with an upper bound on the entries. This example appears in the main paper, [MML].

Up to the publication list

Return to my home page.