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.)
```