Uniform Squares

An NxN array of numbers is said to be "uniform" if the numbers are 
arranged such that the sum of any N numbers, no two from the same 
row or column, is always the same.  A *standard* uniform square is 
a uniform square consisting of the integers 0 to N^2-1.

The most obvious example of a standard uniform square of size NxN is
a simple monotonic arrangement of the numbers 0 to N^2-1 listed in 
order from left to right and top to bottom.  This arrangement is 
clearly uniform because the value in the ith row and jth column is 
Ni+j, and each row and column index (0,1,..,N-1) occurs exactly once 
among all the N selected locations.  Thus the sum of the N numbers is

   Sum  =  (0+1+..+N-1)(N+1)   =   N (N^2 - 1) / 2

Obviously every sub-square and every co-factor of a uniform square 
is uniform.  Also, uniformity is preserved under rotations and 
reflections of the square, and under any permutations of rows and 
columns.  

This raises the question of whether every standard uniform square of 
a given order can be transformed into the simple monotonic array by 
rotations, reflections, and row/column permutations.  The answer is 
no; if N is composite we can easily construct uniform squares that 
cannot be transformed into the simple monotonic square.  

For example, with N=4 we have the following three distinct standard 
uniform squares

  0  1  2  3       0  1  4  5        0  2  4  6
  4  5  6  7       2  3  6  7        1  3  5  7
  8  9 10 11       8  9 12 13        8 10 12 14
 12 13 14 15      10 11 14 15        9 11 13 15

The first one is the simple 4x4 monotonic square.  The other two are 
both, in a sense, 2x2 monotonic arrays of 2x2 monotonic squares.  
They are distinct because of the "polarity" of the sub-squares.  Any 
monotonic array has two polarities, related by flipping them over in 
the plane, so that one lists the numbers left-to-right first and 
then top-to-bottom, whereas the other lists the numbers top-to-bottom 
first and then left-to-right.  The middle and right-hand arrays above 
differ because in one case the 2nd level polarity is the same as the 
1st level, while in the other case the 1st and 2nd level have opposite 
polarities.

For the case N=6 it starts to get interesting.  In addition to the 
simple 6x6 monotonic square we have 3x3 arrays of 2x2 squares, and 
2x2 arrays of 3x3 squares, and in each case the 2nd-level polarity 
can be the same as or opposite to the 1st level polarity.  Thus we 
have five fundamentally distinct uniform squares of order 6.

In general, I suspect that if N is a prime then there is only one 
standard uniform NxN square up to rotations, reflections, and row/
column swaps.  If N is composite, then I think each distinct ordered 
factorization of N into k factors represents 2^(k-1) distinct uniform
squares.  This is because the polarity at each level can either agree
or disagree with the top level polarity (but the polarity on any 
given level must be the same throughout the square).

To illustrate, consider the case N=8.  I think there are exactly 9 
distinct standard uniform squares of sixe 8x8, corresponding to the 
factorizations

       one-part    (8)
       two-part    (2)(4)      (4)(2)
       three-part  (2)(2)(2)

Thus the number of distinct 8x8 uniform squares is

            (1)2^0 + (2)2^1 + (1)2^2  =  9

One of the 4 squares corresponding to the factorization (2)(2)(2)
has the 2nd level polarity reversed relative to the 1st and 3rd
levels, so it looks like this

      0  2   4  6     32 34  36 38
      1  3   5  7     33 35  37 39

      8 10  12 14     40 42  44 46
      9 11  13 15     41 43  45 47


     16 18  20 22     48 50  52 54
     17 19  21 23     49 51  53 55

     24 26  28 30     56 58  60 62
     25 27  29 31     57 59  61 63

Any 8 numbers selected from this array such that no two are in the 
same row or column will sum to 252.

If my supposition about prime-order squares being unique is correct, 
and if polarity on a given level has to be constant, then it would 
seem that the number of distinct standard uniform squares of size 
NxN depends only on the *formal* prime decomposition of N, without 
regard to the actual primes.  For example, if we let u(N) denote 
the number of distinct standard uniform squares of size N (up to 
rotations, relfections, and row/col permutations), then I think 
u(N) = SUM 2^(k-1)  where the sum is taken over every distinct 
ordered factorization of N into k parts.  Thus for any primes 
p, q, and r we have

    u(p) = 1           u(pq) = 5
  u(p^2) = 3        u(p^2 q) = 21
  u(p^3) = 9      u(p^2 q r) = 217
  u(p^4) = 27
  u(p^5) = 145

and so on.  Thus, the number of distinct 60x60 standard uniform 
squares is 217 (because 60 is of the form p^2 q r).

Does the function u(N) as defined above actually give the number of 
distinct standard uniform NxN squares up to rotations, reflections, 
and row/column permutations?  Also, what is the simplest way of 
computing the function u(N) as defined above for arbitrary values 
of N = (p1^a1)(p2^a2)...(pk^ak)?

One possible approach would be to note that all of the NxN arrays 
correspond to factorizations of (x^(N^2) - 1)/(x - 1).   When N is 
prime, we don't have too many factors.  If we can show that *every* 
standard uniform square corresponds to a factorization, this might
lead to a good method.  At the very least it seems to encode the 
problem in a convenient form.  

However, I've been thinking about it a little differently, and I 
think now that u(N), the number of distinct standard uniform NxN 
arrangements (up to rotations, reflections, and row/column 
permutations) is

             u(N) = [tau(N)-1][tau(N)-2] + 1                (1)

where tau(N) is the number of divisors of N.  Of course if N has the 
prime factorization (p1^a1)(p2^a2)...(pk^ak) then tau(N) is equal to 
the product (1+a1)(1+a2)...(1+ak), so if this is the correct formula 
for u(N) it confirms that u(N) is only dependent on the formal 
factorization of N.  (The cyclotomic polynomial factorizations would 
perhaps lead to the same result, but I haven't worked it out.)

Equation (1) rests on the idea that a standard square is uniform if 
(and only if?) the elements of the square are given by an equation 
of the form

    Q(x,y) = A1 x%d1 + A2 x%d2 + ... + Ak x%dk
                                                              (2)
                + B1 y%d1 + B2 y%d2 + ... + Bk y%dk

where x%d signifies the positive reduced value of x modulo d, and 
the moduli d1,d2,..,dk are divisors of N.  The "if" part is immediate, 
because the indicies x and y each take on each value from 0 to N-1 
exactly once, and these values are uniformly distributed among the 
equivalence classes modulo d iff N is divisible by d.  Thus, any 
standard square whose elements are generated by an equation of the 
form (2) is uniform.

The "only if" part seems less easy to prove, although it would be 
amazing if it weren't true, i.e., if there was a uniform square of 
prime order that was not equivalent (up to rotations, reflections, 
and row/column permutations) to the simple monotonic arrangement.  
I've checked the case N=5 and found no exceptional uniform 
arrangements (and of course there are none for N = 2 or 3).  
Maybe the cyclotomic factors approach would provide a handle to 
prove this "only if" part.

I haven't exhaustively checked the case N=6 to see if there are any 
exceptional uniform squares, but I've checked all the squares given 
by (2) with d1=2, d2=3, and d3=6 and all possible combinations of 
coeffcients in the range -6 to +6.  This reveals 46 sets of 
coefficients that give standard uniform squares.  By symmetry between
x and y (flipping the squares) this reduces to 23 sets, but the 
majority of those are row/column permutations.  Focusing on just 
the monotonic solutions we find there are 7 distinct standard 
uniform squares of order 6, given by the formula

           S(x,y) = A1 x%6 + A2 x%3 + A3 x%2

                        + B1 y%6 + B2 y%3 + B3 y%2

with the coefficients shown below.

            A1 A2 A3  B1 B2 B3
            -- -- --  -- -- --
            1  0  0   6  0  0
            2 -1  0   6  0 -3
            2  0 -1   6  0 -4
            2  0  0   6  0 -5
            3 -2  0   6 -3  0
            3  0 -2   6 -4  0
            3  0  0   6 -5  0

These results indicate that it suffices to consider only a single 
polarity for the entire square, so we can say without loss of 
generality that ordering of the elements is always left-to-right 
first and then top-to-bottom.  They also show that a square can be 
divided into rectangles, not just squares.

To illustrate, consider the 6x6 squares.  Clearly sub-dividing 
the overall square with just horizontal lines doesn't produce a 
new square, because the monotonically ordered sequence of numbers 
would remain unchanged.  We need to first divide the square with 
one or more equally-spaced vertical lines, and then for each such 
partition we can produce a distinct square with 0, 1, or 2 equally 
spaced horizontal dividing lines.  (Notice that we don't divide 
by 6 itslef because then the square reduces again to the simple 
monotonic square.)  The seven fundamental 6x6 standard uniform
squares are illustrated schematically below.  Within each 
rectangle the numbers are listed monotonically, and the rectangles 
themselves are taken monotonically.

   ___________
  |           |
  |           |
  |           |
  |           |
  |           |
  |___________|

   ___________        ___________        ___________
  |     |     |      |     |     |      |     |     |
  |     |     |      |     |     |      |_____|_____|
  |     |     |      |_____|_____|      |     |     |
  |     |     |      |     |     |      |_____|_____|
  |     |     |      |     |     |      |     |     |
  |_____|_____|      |_____|_____|      |_____|_____|

   ___________        ___________        ___________
  |   |   |   |      |   |   |   |      |   |   |   |
  |   |   |   |      |   |   |   |      |___|___|___|
  |   |   |   |      |___|___|___|      |   |   |   |
  |   |   |   |      |   |   |   |      |___|___|___|
  |   |   |   |      |   |   |   |      |   |   |   |
  |___|___|___|      |___|___|___|      |___|___|___|


The number of ways of evenly dividing the square with one or 
more vertical lines is tau(N)-2, and the number of ways of evenly 
dividing the square with 0 or more horizontal lines is tau(N)-1.  
Therefore, in addition to the simple monotonic square we have 
[tau(N)-2][tau(N)-1] distinct arrangements, which leads to 
equation (1) for u(N).

There are several interesting aspects of uniform squares.  
First, notice that in an NxN square there are N! distinct sets 
of N elements such that no two are in the same row or column.  
This seems to be a very large number of conditions to satisfy 
simulataneously, but it can be shown that a necessary and 
sufficient condition for uniformity is that in every 2x2 sub-cell 
is uniform, i.e., for every

              a b
              c d

we have a+b = c+d.  There are only (N-1)^2 such sub-squares in an NxN 
square, so this is a more accurate indication of the constraints.  It 
is, however, still far more constrained than, for example, a magic 
square, which must satisfy only 2N+2 conditions.

It's also interesting to consider the "trace" of an array, which
is defined as the sum of the diagonal elements.  The trace has lots 
of nice properties, such as 

     trace(AB) = trace(BA)          trace(AB-BA) = 0

and so on.  Anyway, notice that an array is *uniform* if and only if 
its trace is invariant under all permutations of its rows and columns 
(and reflections).

I mentioned above that the "only if" part seems less easy to prove, 
although it would be amazing if it weren't true, i.e., if there was 
a uniform square of prime order that was not equivalent (up to 
rotations, reflections, and row/column permutations) to the simple 
monotonic arrangement.  I think a rough and inelegant proof that 
there's essentially only one standard uniform square of any given 
prime order can be pieced together from a direct review of the 
process of constructing uniform squares.  We know that uniformity 
is preserved under permutations of the rows and columns, so without 
loss of generality we can focus on squares with [0] in the upper-left
corner and with strictly increasing numbers along the top row and 
down the lefthand column.

Also, from the local property that each 2x2 sub-square

          a b
          c d

is uniform, we know that a+d=b+c, from which it follows immediately 
that the value in the location (i,j) is simply the sum of the value 
in location (i,0) and the value in location (0,j).  Thus, every 
uniform square can be transformed into one of the form
         __________________________________________
        |  0     y1     y2     y3   ...   y(N-1)   |
        | x1   x1+y1  x1+y2  x1+y3  ...  x1+y(N-1) |
        | x2   x2+y1  x2+y2  x2+y3  ...  x2+y(N-1) |
        | x3   x3+y1  x3+y2  x3+y3  ...  x3+y(N-1) |
        |                                          |
        \           etc.                           \
        |                                          |
        | xN   xN+y1  xN+y2  xN+y3  ...  xN+y(N-1) |
        |__________________________________________|
        
where 0 < y1 < y2 < ... < y(N-1)  and  0 < x1 < x2 < x3 ... < x(N-1).  
For this to be a standard square each integer from 0 to N^2-1 must 
appear exactly once.  This implies that either x1 or y1 must equal 
1, so without loss of generality can assume y1 = 1.  In fact,
we can assume the first k positive integers are assigned to the
locations y1,y2,..,yk.  If k = N-1  then the rest of the square is 
entirely determined, and we have the simple monotonic square.

If k is less than N-1, so the value of y(k+1) is NOT k+1, then we 
must have x1 = k+1 because otherwise k+1 will not appear in the 
square at all.  To illustrate, here's what we have so far if k=3:

           0  1   2   3  ...
           4 [5] [6] [7]

The numbers in brackets are implied as soon as we set x1=4.  The next 
smallest unused number is now 8.  Notice that at each stage the next
available number must appear in the top row or the lefthand column,
because otherwise it can't appear in the square at all.  So we have
two choices; we can place 8 in x2 or in y4.  If we place it in x2
the result is

           0  1    2    3  ...
           4 [5]  [6]  [7]
           8 [9] [10] [11]

and so the next smallest number is 12.  We could then continue to 
place the sequence of next smallest numbers down the lefthand column, 
until eventually we either reach the bottom of the square (in which 
case we haven't divided the square by rows) or we decide to place a 
number on the top row.  Whenever we decide to do this the result is 
the same, so we can just consider the case when we immediately decide 
to place 8 in y4 (instead of x2 as we did above).  The result is

           0   1   2   3   8 ...
           4  [5] [6] [7] [12]

Now the next smallest number is 9, but we can't place it in the 
lefthand column because the would give us another [12] (in the 
column under [3]).  Thus we have no choice but to place the number
9 in the top row, which gives

           0   1   2   3   8    9 ...
           4  [5] [6] [7] [12] [13]

Now the next smallest number is 10, and by the same reasoning we MUST 
place this in the top row (because otherwise we'd have two 13's).  The 
same applies to 11, so we are forced to

           0   1   2   3   8    9    10   11 ...
           4  [5] [6] [7] [12] [13] [14] [15] 

Now the next available number is 16, and we have our choice of placing 
it on the top or the lefthand edge.  The point here is that once we 
interrupt an arithmetic sequence on either the top or the left, that 
"block size" must repeat thereafter, and the only way to add more rows 
is to complete a block of the columns.  Similarly, the only way to add
more columns (once they've been interrupted) is by completing a block
of the rows.  Consequently, in order to produce a complete NxN square, 
the periods of the rows and columns must both be divisors of N.

This implies that if N is a prime there is essentially only one standard 
uniform square of size NxN, and it also confirms the general formula 
u(N) = [tau(N)-2][tau(N)-1] + 1 for the number of distinct standard 
uniform squares of order N.

Another interesting aspect of uniformity is the fact that the local 
condition for uniformity (a+d=b+c) shows that a uniform square is 
entirely determined by just it's boundary conditions, i.e., the 
values along two adjacent edges, together with the stipulation of 
uniformity, completely determine the array.

What is the continuous analog of uniformity?  In other words, if we
have a continuous scalar field q(x,y) defined on the continuous 
variables x and y, what would it mean for this surface to be "uniform" 
in the sense discussed here?  For each incremental square region on
the surface we have the four values

                    q(x,y)      q(x,y+dy)

                  q(x+dx,y)   q(x+dx,y+dy)

The uniformity condition implies

          q(x+dx,y) - q(x,y)  =  q(x+dx,y+dy) - q(x,y+dy)
  and
          q(x,y+dy) - q(x,y)  =  q(x+dx,y+dy) - q(x+dx,y)

so this implies that

                       d^2 q     d^2 q
                       -----  =  -----  =  0
                       dx dy     dy dx

where the "d's" denote partial derivatives.  The equality of those 
two partials is a characteristic of the real and imaginary components 
of an analytic function.  More importantly, the vanishing of this
mixed partial is equivalent to the one-dimensional wave equation,
written in "diagonal" coordinates.  In terms of the coordinates
u=(x+y) and v=(x-y) this partial differential equation becomes

                       d^2 q     d^2 q
                       -----  =  -----
                        du^2      dv^2

Given a "uniform" continuous scalar field Q(x,y) defined on the 
continuous variables x and y, it's clear that if the scalar has 
values along the left-hand edge given by a function f(x) and along 
the top edge given by g(y) then the uniform scalar field is simply
the sum
               Q(x,y)  =  f(x) + g(y)  -  C

where C is the value at (0,0).  (In other words, f(0) = g(0) = C.)