The solutions are in! This problem of the week was interesting for me: the usual pattern has been that I pose problems that I’ve solved myself at some point in the past, giving me a kind of “inside edge” on understanding the solutions that come in. But, as I said in POW-12, the difference this time is that the solution I knew of came from someone else (Arin Chaudhuri). What was interesting for me — and given the circumstances, it was probably inevitable — is that some of the solutions we received forced me to make contact with some mathematics I’d only heard about but never studied. Let me get to that in a minute.

Another interesting thing for me — speaking now with my category theorist’s hat on — is how utterly simple and conceptual Arin’s proof was! I was pleased to see that regular problem solver Philipp Lampe also spotted it. Wait for it…

Solution I by Philipp Lampe, University of Bonn: The answer is 8.

Among the eight neighbors of an arbitrary vertex, all colors of an admissible coloring must occur. Thus, 8 is an upper bound for the maximum number of colors one can use. We have to show that there is an admissible coloring with eight colors.

The vertices of the 8-dimensional cube may be represented by vectors (a_1, a_2, \ldots, a_8) with a_i in \{0,1\}, in other words as vectors in \mathbb{F}_{2}^8, the 8-dimensional vector space over the field \mathbb{F}_2 = \{0, 1\} with two elements (i.e., the integers modulo 2). Two such vectors u, v are neighbors iff their coordinate vectors differ in exactly one place, in other words if u = v + e_i considered modulo 2, where e_i is one of the eight standard basis elements (with i-th coordinate 1, and the other coordinates 0).

Now let our “colors” be the 8 elements x_1, x_2, \ldots, x_8 of \mathbb{F}_{2}^3, the 3-dimensional vector space over \mathbb{F}_2. Let the vertex “coloring”

C: \mathbb{F}_{2}^8 \to \mathbb{F}_{2}^3

be the unique \mathbb{F}_2-linear map such that C(e_i) = x_i; that is, define the color of a vertex/vector by

\displaystyle C\left(a_1,\ldots, a_8\right) = \sum_{i=1}^{8} a_i x_i

Now, if v is any vector, the colors of its neighbors are C(v + e_i) = C(v) + C(e_i) = C(v) + x_i. The colors of these neighbors are all distinct since the x_i are distinct. Hence all 8 colors are represented among the colors of the neighbors of any given vertex v, QED.

What I love about this solution it is how natural it is. I’ll say a little more about this in remarks below.

But I also learned a thing or two by studying the next solution. It relies on the theory of Hamming codes, with which I was not conversant. Up to some small edits, here is exactly what Sune Jakobsen submitted:

Solution II by Sune Jakobsen (first-year student), University of Copenhagen: Since each vertex only has 8 neighbors, the answer cannot be greater that 8.

Now we construct such a coloring with 8 colors. An 8-dimensional cube can be represented by the graph with vertices in \{0, 1\}^8, and with an edge between them iff the Hamming distance between them is 1. We color a vertex with color 8 if the seven first bits in the vertex is a “correct” Hamming message (cf. Hamming code (7,4)), and color it in color i if the first seven bits give a correct Hamming message upon changing bit i. This is a well-defined coloring, since each element in \{0, 1\}^7 is either a correct Hamming message, or is Hamming distance 1 away to exactly one correct Hamming message.

It remains to show that no vertex is neighbor to two vertices of the same color. The Hamming distance between these two vertices is 2, thus the Hamming distance between the first 7 bits of two neighbors must be 1 or 2. If two neighbors had the same color i, then by definition one would get two correct Hamming messages by changing bit i in both of them, and the Hamming distance between these messages would be the same as before — either 1 or 2. But the distance between any two correct Hamming messages is at least 3. Contradiction.

Remarks:

1. Let me give a little background to Sune’s solution. Mathematically, the Hamming code called “(7, 4)” is the image of injective linear map

G: \mathbb{F}_{2}^4 \to \mathbb{F}_{2}^7

given by the 7 \times 4 matrix

1101
1011
1000
0111
0100
0010
0001

The Hamming code is what is known as an “error-correcting code”. Imagine that you want to send a 4-bit message (each bit being a 0 or 1) down a transmission line, but that due to noise in the line, there is the possibility of a bit being flipped and the wrong message being received. What can you do to help ensure that the intended message is received?

The answer is to add some “parity check bits” to the message. In the code (7, 4), one adds in three parity checks, so that the transmitted message is 7 bits long. What one does is apply the matrix G to the 4-vector, to get a 7-vector (remember we’re working modulo 2), and this 7-vector is sent down the line. Assuming only a moderate amount of noise in the transmission line, perhaps the 7-bit message will remain intact or perhaps a single bit will be flipped, more rarely two bits will be flipped (and we’ll assume the event that more than two are flipped has negligible probability). Now, the Hamming encoding G is rigged up so that if the 7-bit vector is received as sent, then the parity checks will report 0 errors. If the parity checks report an error, they report precisely where the error occurred if the received vector was off by one bit. (If two flips occurred, then the receiver can still detect from the parity checks that an error occurred. The parity checks can never detect how many bits were flipped, but if the receiver assumes correctly that just one bit got flipped, he can restore the intended message with accuracy. If three or more got flipped, then the receiver got the wrong message, but he would never know it if the parity checks reported back 0 errors.)

How does this work? By having the receiver apply a parity-check matrix H to the received message, given by the 3 \times 7 matrix

1010101
0110011
0001111

In the first place, HG = 0, and so if the message received belongs to the image of G (is a “correct Hamming message” in the terminology of Solution II), which will indeed be the case if there were no errors in the transmission, then H applied to the message will produce the zero vector. In the case where one bit got flipped in the transmission, H applied to the received vector will return a nonzero 3-vector, but the beauty of the Hamming code is that the 3-vector will spell out in binary the bit the error occurred (for example, if the output vector is (0 1 1)^t, then error occurred in the bit with binary number 011, that is bit 3). In that case, the receiver flips that bit to restore the original message. In these two cases, the original 4 bits are then read off as the 3rd, 5th, 6th, and 7th coordinates of the (possibly corrected) 7-vector.

By the way, Sune reminded us that Hamming codes also came up in a post by Greg Muller over at The Everything Seminar, who used the existence of a Hamming code in every dimension 2^k - 1 to solve general hat-guessing puzzles.

2. Within minutes of posting the original problem, we received a message from David Eppstein, who reported that the solution of 8 colors is essentially contained in a paper he coauthored with T. Givaris (page 4); his solution is close in spirit to Sune’s.

Arin Chaudhuri also surmised the connection to Hamming codes, and mentions that the problem (in a slightly different formulation) originally came from a friend of a friend, who blogs about a number of related problems on this page. Presumably the author had things like error-correcting codes in mind.

3. Sune and David noted that their solutions generalize to show that on the 2^k-dimensional cube (for any k), it is possible to color the vertices with 2^k colors (the maximum number possible) so that all of the colors show up as colors of the neighbors of any given vertex.

This is very easy to see by adapting Philipp’s method. Indeed, for each k just take the color set to be the \mathbb{F}_2-vector space S = \mathbb{F}_{2}^k. The set of vertices of the 2^k-dimensional cube may identified with the \mathbb{F}_2-vector space V(S) generated by the set S (as basis), and the desired coloring is then just the \mathbb{F}_2-linear map C: V(S) \to S that extends the identity function on S. As mathematical constructions go, you can’t get much more canonical than that! No fuss, no muss — it’s a purely categorical construction (categorists call it a counit of an adjunction). So then why didn’t I see that myself? 🙂

4. We’re still not sure what the story is in other dimensions. If a_n is the maximum number of admissible colors in dimension n, then about all any one of us knows right now is that a_n = n for n = 2^k, a_n is weakly monotone increasing, and that a_n < n if n is not a power of 2. There’s a conjecture afloat that a_n = 2^{\left[\log_2 n\right]} where \left[x\right] is the floor function, but for now that should be treated as a wild guess. If anyone has further information, please let us know!

Solved by Arin Chaudhuri, David Eppstein, Sune Jakobsen, and Philipp Lampe. Thanks to all those who wrote in!