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 verticies 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
Сайт управляется системой
uCoz