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