Four Cubed (Complete Projection Cubes)

For any positive integer N we can arrange the integers 0 to N^2 - 1
in a square array of size NxN.  However, the case N = 4 is unique
because 2^4 = 4^2 is the only solution of  x^y = y^x  for distinct
naturals x,y.  As a result, we can expand each of the numbers 0-15
into four binary bits and place them on four separate levels to give 
a 4x4x4 cube.

For example, consider the array

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

The four binary levels of this array are

     1's place      2's place     4's place     8's place

      0 1 1 0        1 1 1 0       1 0 0 1       1 0 1 0
      0 1 1 1        1 0 1 1       0 0 1 1       1 1 0 1
      0 0 0 1        1 0 0 0       0 0 0 0       0 1 0 0
      0 1 0 1        0 0 1 0       1 1 1 1       1 1 0 0

Notice that the rows of these bit-planes also give the integers 
0-15:
                      6 14  9 10
                      7 11  3 13
                      1  8  0  4
                      5  2 15 12

However, the COLUMNS do not give all 16 distinct integers 0-15.
Instead they give
                      0 13 12  7
                     14  8 13  4
                      9  1  5 13
                     13  7  8  4

which has four 13's, two 8's, two 7's, and two 4's.

Do there exist 4x4x4 cubes of binary bits such that the "projection"
onto each face of the cube gives all the integers from 0 to 15?  The
above example satisfies this condition for only two of the three
orthogonal directions.  (Obviously if the condition is satisfied in 
a given direction, it is also satisfied in the opposite direction, 
so the above cube satisfies the condition for four of its six faces.)

I received several replies advising me that the answer to my question 
was probably "No", although no one could prove it.  It turns out there 
was a good reason no one could prove it.  Dan Cass found the following
cube with the desired property:

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

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

Andrei Ivanov then noted that the desired property is conserved under 
any permutations of the orthogonal bit-planes, any spatial rotations, 
and interchanging the '0' and '1' symbols.  He also found that there 
could be no more than two distinct cubes up to these transformations.

Examining these two possibilities I showed that they could in fact
be transformed into each other using the stated transformations,
so there is really just one "complete bit-cube".  Also, I showed
that the operation of exchanging the '0' and '1' symbols was
superfluous because that transformation can always be accomplished
by rotations and plane swaps.

For example, consider the two complete bit-cubes shown below:

      0 11 13  3                             15  4  2 12
     14 10  6  2    exchange 0's and 1's      1  5  9 13
      7  9  5  4   ---------------------->    8  6 10 11
     12  8  1 15                              3  7 14  0
       cube A                                   cube B

The question is, can we get from cube A to cube B by means of spatial 
rotations and plane permutations?  Assigning directions to cube A as 
shown below

         ^
       y |
         |    0 11 13  3
         |   14 10  6  2
         |    7  9  5  4
         |   12  8  1 15
         |
         / -------------->  x
        /
       z

we can apply the following permutations to the bit-planes normal to
the three axes:

              z:  (1234) --> (2143)
              x:  (1234) --> (4231)
              y:  (1234) --> (4231)

The result is cube B.  Surprisingly, this same transformation applied 
to the simply ordered cube 

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

also yields its 1's complement!  This raises the question: What is
the set of cubes for which this (or any particular) transformation
yields its 1's-complement?

In any case, here's a nice "constructive" way of deriving the
(essentially unique) complete bit-cube, and for counting the number
of distinct such cubes up to plane swaps alone, and up to spatial
rotations alone.  If each number in the range 0-15 is to appear 
in each orthogonal view, then looking down on the cube from any 
direction we must see exactly eight 1's in each row and each 
column.  This means there are only 7 possible rows (columns)
of bitcounts
                     4 3 1 0
                     4 2 1 1
                     4 2 2 0
                     3 3 2 0
                     3 3 1 1
                     3 2 2 1
                     2 2 2 2

(These are the seven ways of partitioning eight into four non-
negative integers not exceeding 4.)  It's easy to see that there 
are only six distinct ways (up to row and column swaps) of combining 
four such rows into a 4x4 square so that each row and column sums 
to 8 and there are exactly 1,4,6,4,1 (respectively) occurrances of 
0,1,2,3,4.  These six ways are shown below, where I've adopted the 
convention of showing a square with the numbers in descending 
lexicographic order, both for columns and for rows.  (This uniquely 
fixes the row and column swaps).

       A:         B:         C:
       4 3 1 0    4 3 1 0    4 2 2 0
       2 1 3 2    2 1 2 3    2 2 2 2
       1 2 2 3    1 2 3 2    1 3 1 3
       1 2 2 3    1 2 2 3    1 1 3 3

       D:         E:         F:
       4 2 2 0    4 2 2 0    4 2 1 1
       2 2 1 3    2 3 1 2    2 0 3 3
       1 3 2 2    1 2 2 3    1 3 2 2
       1 1 3 3    1 1 3 3    1 3 2 2

For each of these "bitsum maps" the number of ways of placing the 
integers 0-15 is exactly

             (1!)(4!)(6!)(4!)(1!) = 414720

so it's not hard to check each of these to see how many (if any) 
give the full set of numbers 0-15 in the other two views.  It turns 
out that NONE of the arrangements for types A, B, C, or E give a 
complete bit cube.

However, 96 arrangements based on F give complete bit cubes, and 24
arrangements based on D give complete bit cubes.  In addition, it's 
easy to check that every one of the 96 complete F arrangements when 
viewed from either of the other two directions is a D arrangement.  
Therefore, each of the 96 F arrangements represents a unique cube 
(i.e., we don't have to worry that two of those F arrangements may 
be two perpindicular views of the same cube).  Also, every one of 
the complete bit-cubes with a D arrangement looks like an F from 
exactly one other direction (so there are no complete bit-cubes 
that look like D in all three directions).  Thus, every complete 
bit-cube is an FDD.

Clearly for a fixed row/column permutation of the F bitsum map the 
96 possible arrangements of the numbers 0-15 give distinct cubes 
(counting rotational differences).  Also, this set of 96 is mutually 
exclusive with the set for any other permutation of the rows/columns 
of the F bitsum map, provided that the permutations give a distinct 
bitmap.  However, F has two identical rows and two identical columns, 
so the number of row permutations is 4!/2, as is the number of column 
permutations, for a combined total of (4!/2)^2 = 144.

For each of those there are 96 distinct complete bit-cubes, for a 
total of (144)(96) = 13824, which happens to equal (4!)^3.  Then, 
since can we orient each cube with the FF axis parallel to any of 
the three axes x, y, or z, this gives another factor of 3, for a 
grand total of

          3(96)(4!/2)^2  =  3(4!)^3  =  41472

(in agreement Andrei Ivanov's computations).  This also shows 
that there are exactly three distinct cubes up to plane swaps, 
corresponding to the three possible directions for the FF axis.

By the way, the fact that spatial rotations contribute only a
factor of 3 to the number of solutions given by plane swaps,
whereas there are actually 24 distinct rotational positions of
a cube, implies that the (4!)^3 plane swaps contain a sub-group
of the cube's rotational group (S_4).  This sub-group applies
the following permutations to the vertices of the cube:

    basic    I    a    aa  aaa   cc  cca   bb  bba

     000    000  100  110  010  101  001  011  111
     001    001  101  111  011  100  000  010  110
     010    010  000  100  110  111  101  001  011
     011    011  001  101  111  110  100  000  010
     100    100  110  010  000  001  011  111  101
     101    101  111  011  001  000  010  110  100
     110    110  010  000  100  011  111  101  001
     111    111  011  001  101  010  110  100  000

where a,b,c are rotations about the x,y,z axes respectively.
Interpreting the vertex positions as binary numbers and placing
the rotations in ascending order, this table can be written as

                  0 1 2 3 4 5 6 7
                  1 0 3 2 5 4 7 6
                  2 5 6 1 0 7 4 3
                  3 4 7 0 1 6 5 2
                  4 3 0 7 6 1 2 5
                  5 2 1 6 7 0 3 4
                  6 7 4 5 2 3 0 1
                  7 6 5 4 3 2 1 0

Notice that the vertex pairs (0,1), (2,3), (4,5) and (6,7) are
always adjascent.  These rotations apply the following subgroup
of permutations to the four "main diagonals" of the cube

                    0123
                    3201
                    1032
                    2310
                    2301
                    1023
                    3210
                    0132

which makes it clear that the group has the transposition structure
denoted by [01][23].


Now let's determine the number of distinct complete bit-cubes up to
spatial rotations only.  First let's summarize what we know:

(1) The total number of distinct orthogonally positioned cubes, not 
    allowing any rotations or plane swaps, is (3)(4!)^3.

(2) Every cube is of type F in one projection and type D in the other
    two projections.  (This means that the numbers '0' and '15' appear
    in different columns and rows in one projection, but they appear 
    in the same column or row in the other two projections.)

(2) The total number of cubes can be de-composed like this

                (3)(4!)^3   =   (3)(96)(4!/2)^2
    where 
            3 = the three possible orientations of the F projection
           96 = the number of distinct solutions for each distinct 
                F-projection bitsum map
     (4!/2)^2 = the number of distinct F-projection bitsum maps

(3) To determine the number of cubes up to space rotations we can
    immediately divide out the factor of 3.  Also, we can divide the
    number of distinct type-F bitsum maps by a factor of 4, because
    the number (4!/2)^2 counts the four rotated versions of each 
    F-view separately (and there is clearly no symmetry in these
    rotated views because the bitsum 4 must appear in four different
    places as you rotate the view).  This gets us down to just 
    (1/4)(4!/2)^2  =  36  distinct F-projections up to rotation, 
    and there are 96 distinct solutions per F-projection.

(4) If none of the cubes had any rotational symmetry (i.e., if each 
    cube looked different in each of its 24 orthogonal orientations)
    then we would conclude there were exactly (96)(36)=3456 distinct
    cubes up to space rotations.

    However, some of the cubes DO have one rotational symmetry, i.e.,
    if you flip it over to the opposite F-view and spin it 90 degrees,
    you sometimes find the same cube.  The key question is, how many
    of the 3456 cubes have this symmetry?

    The F-projection bitsum map up to row and column swaps is

                         4 2 1 1
                         2 0 3 3
                         1 3 2 2
                         1 3 2 2

    For this particular permutation of the rows and columns it turns
    out that 16 of the 96 solutions possess rotational symmetry, 
    meaning that if you view them from the opposite side you see (a 
    rotated version of) the same solution.  Thus the other 80 
    solutions are comprised of 40 matched pairs of F-projections,
    i.e., there are two distinct F-projections for each of these
    cubes.  Thus, we really only need 40 cubes to represent the 
    complete set (because they each give two of the 96 solutions, 
    depending on which end you view).  As a result, there are only 
    40 + 16 = 56 distinct cubes (up to space rotation) with the 
    above F-projection bitsum map.

    Here we might be tempted to jump to the conclusion that this 
    same analysis applies to each of the 36 bitsum maps, giving a 
    total of (56)(36)=2016 distinct cubes.  However, that's not the 
    case, because some of the permutations of the F bitsum map don't 
    allow any of the 96 solutions to have rotational symmetry.  For 
    example, in any permutations where the bitsums 4 and/or 0 are 
    off the diagonal, we can't possibly have any symmetrical 
    solutions.

    We could explicitly enumerate all 96 solutions for each of the 
    36 bitsum maps, and check to see how many are symmetrical, but 
    there is a simpler way.  Of the 36 maps only 4 have the symmetry 
    to allow symmetrical solutions, because 0 and 4 must be on the 
    diagonal, with '4' in a fixed quadrant, and the other two 
    row/columns are interchangeable.  In all four of those cases 
    there are exactly 16 symmetrical solutions.  For the remaining 
    32 bitsum maps there are no symmetrical solutions, so the 96
    solutions in each case are comprised of 48 matched pairs.  Thus 
    the total number of distinct cubes up to space rotations is (as 
    Dan Cass had determined by a slightly different method)

                4*56 + 32*48  =  1776


By the way, it's interesting that Dan Cass's original solution
has the form

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

which is anti-symmetric in the 2's-complement sense.  If we write 
the square elements (mod 15) we have

                 -3 -7  1 -0
                  7 -6  5  4
                 -1 -5  6  2
                  0 -4 -2  3

Therefore, we have A[i,j] = -A[j,i]  for all i <> j.  We also have 
the relation on the main diagonal A[i,i] = -A[3-i,3-i] for i=0,1,2,3.
Any complete bit-cube is equivalent (up to rotations and plane swaps)
to a cube with these symmetries.  Up to plane rotations there are
48 distinct cubes of this form.  If we also allow reflection about
the 0-15 axis, then there are only 24.  Of those 24, twelve have 
the additional symmetry that they are identical when viewed from 
the opposite face of the cube.  For example, the cube

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

has this extra symmetry, as can be seen from the fact that flipping
the cube about the 0-15 axis applies the transpositions (1,8),
(2,4), (10,5), (3,12), (14,7), and (13,11), which are just the
same binary numbers read from opposite ends.

Another way of classifying these bit-cubes is by applying the 
"descending order" arrangement to the rows and columns of the F 
faces.  The result is that there are only 12 possibilities.  In 
other words, taking any complete bit-cube, look at one of the F 
faces and swap columns and rows as needed to place the numbers in 
descending order.  If the first row is lexicographically less than 
the first column, stop.  If not, turn the cube over and repeat the 
process on the opposite F face (which is then guaranteed to be in 
the right order).  The result will be that you are looking at one 
of the following 12 cubes:

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

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

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


Return to MathPages Main Menu