|
Complete Projection Cubes |
|
|
|
For any positive integer N we can arrange the integers 0 to N2 – 1 in a square array of size NxN. However, the case N = 4 is unique because 24 = 42 is the only solution of xy = yx 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: |
|
|
|
|
|
|
|
The array given by stacking these and viewing in the vertical direction is: |
|
|
|
|
|
|
|
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 side 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) occurrences 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 perpendicular 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 (S4). 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 adjacent. 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.) |
|
|
|
(3) 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 = number of distinct solutions for each distinct F-projection bitsum map |
|
(4!/2)2 = the number of distinct F-projection bitsum maps |
|
|
|
(4) 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 we 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. |
|
|
|
(5) 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 we flip it over to the opposite F-view and spin it 90 degrees, we 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 we view them from the opposite side we 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 we 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 we 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 14 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 |
|
|
|
Incidentally, although the block of size N=4 is the only possibility in D=3 dimensions for complete blocks in the base b=2, the basic requirement bN = ND−1 has other solutions in higher dimensions. For example, in D=5 dimensions we could have a block with edge length N=16 filled with binary (b=2) bits. Each of the 16 “faces” of this 5-dimensional block consists of a 4-dimensional block of size 164, which has 65536 cells, each of which can be associated with the projected 16-bit integers (in the remaining dimension) from 0 to 65535. The task would be to find an arrangement of the bits in the 165 cells of the overall block that gives a complete projection of the numbers 0 to 65535 on each of the 16 four-dimensional “faces” (or 32 faces, counting the opposite directions). |
|
|
