# The Discrete Hairy-Ball Theorem

This question was inspired by Math puzzles for dinner.

The arrow compatibility conditions in that problem can be considered an attempt to discretize the notion of a continuous vector field.

The Hairy-Ball Theorem states that there is no continuous nowhere-vanishing vector field on an even-dimensional sphere.

We are led to the following formulation of a discrete Hairy-Ball Theorem for two dimensions:

Instead of a $2$-sphere, we consider unit squares on the surface of a $(3 \times 3 \times 3)$-Rubik’s cube. Instead of searching for a continuous nowhere-vanishing vector field, we ask if there exists a ‘legal configuration’ of arrows on the squares of the cube.

A ‘legal configuration’ of arrows consists of the following:

1. For any non-corner square, an arrow pointing in one of the eight cardinal directions is placed.
2. For any corner square, there is one cardinal direction that does not point to an adjacent square. For these squares, the placed arrow should point in one of the other seven directions.

The following conditions are modified from the original formulation:

1. Orthogonally-adjacent non-corner squares should be compatible in the sense that if they are flattened to lie in a plane, then the arrows should be at most $45^{\circ}$ apart.
2. Orthogonally-adjacent corner squares should be compatible in the sense that if they are flattened to lie in a plane, the arrows are one rotation away from each other within the seven allowed directions. For example, if northeast is a prohibited direction on a corner square, then a northward pointing arrow on the square and an eastward pointing arrow on an adjacent square are compatible.

So, can you comb a hairy Rubik's cube discretely? Does a legal configuration of arrows exist? What about an $(n \times n \times n)$-cube?

• might be obvious, but by just brute force experimentation you can't comb a 1x1x1 cube. – Otis Chodosh Aug 7 '10 at 6:41

By interpolating "legal configuration" if it were to exist, I think you can obtain a nowhere vanishing, continuous vector field on $S^2$. Suppose that for some $n$ there is a legal configuration on the $n\times n \times n$ cube. For each 1x1 face, put a vertex at the center. Then connect vertexes whose 1x1 face's touch. (basically something like a dual graph, but I don't know what the real terminology is).

Doing this, you get $(n-1)^2$ squares on each face of the Rubik's cube, $n-1$ squares on each edge of the Rubik's cube, and one triangle for each vertex of the cube. Now, put the arrow from the 1x1 face at the associated vertex. For each square or triangle we can now linearly interpolate to get a vector field over the whole thing. These will patch back together to form a continuous vector field on $S^2$ because on the lines they are glued along, the value on each piece is linear interpolation between the same two vectors. Thus, basically it remains to check that given a "legal configuration" you cannot interpolate to a zero vector.

The squares are not too bad, because the most that two of the vectors being interpolated can be off by is $90^\circ$, so you can't get a zero vector.

The triangles are a little trickier because things get twisted around, but if you try to write down the possible cases, you can see that there is basically only one type of "legal" corner configuration, and it doesn't interpolate to a zero vector.

This seems to show that you don't even need to assume anything special about corner squares, you can allow them to point in the 8th illegal position, and there are still no "legal configurations."

• This does the trick! However, it would be nice to have a proof which does not depend on the continuous case... – Yakov Shlapentokh-Rothman Aug 7 '10 at 22:57
• Yeah.. It seems like you could the discrete version to imply the continuous case by taking $n$ large enough you could choose a grid with arbitrarily small distance between adjacent points so that if you let each point have the cardinal direction closest value of the vector field at that point you would still have at most $45^\circ$ difference between adjacent arrows.. – Otis Chodosh Aug 8 '10 at 2:51

I am not sure I fully understand the question, but you should know the following classical discrete version of the hairy ball theorem:

Let $P \subset \Bbb R^3$ be a convex polytope. We say that an orientation of edges of $P$ is balanced if every vertex has at least one ingoing and one outgoing edge (i.e., the oriented graph has no sinks and no sources). Then the edges of at least two faces of $P$ form oriented cycles.

The proof is completely straightforward and goes exactly the way you think it should go (follow the arrows!). This result has been rediscovered a number of times. The earliest place where I found this result is here: L. Glass, A combinatorial analog of the Poincaré index theorem, J. Combin. Theory Ser. B 15 (1973), 264–268. See also Ex. 25.15 in my book for the context, and connections with other related results (sorry for the self-promotion).

• That does indeed seem extremely relevant! I will have to think about it a bit, but my hunch is that non-existence of a "legal configuration" follows without much work from this theorem. – Yakov Shlapentokh-Rothman Aug 7 '10 at 5:48
• @Pak. Can we deduce the continuous version of the Hairy ball theorem from the discrete version, by some limiting process ? – coudy Aug 7 '10 at 14:18
• @coudy: check out Thurston's "Three-dimensional geometry and topology", pages 19--25. It's not a limiting process, but rather showing that any vector field can be taken "transverse" to the edges of some triangulation (=convex polytope). – Tom Church Aug 7 '10 at 16:32

This is in response to Yakov’s request to see a proof that does not rely on the continuous Hairy Ball Theorem.

A ‘legal’ configuration has to satisfy the compatibility requirement appearing in the original problem, i.e., that the arrows in two adjacent squares are no more than $45^{\circ}$ apart in direction. If not, it is very easy to construct a ‘legal’ configuration.

Now, suppose that we have a graph on the surface of the cube that yields an $(n \times n)$-square grid on each face. Let $S$ denote the set of all square regions and $V$ the set of all vertices of this graph. For the sake of contradiction, assume that this graph admits a ‘legal’ configuration of arrows. This means that each element of $S$ is assigned an arrow pointing in one of the eight cardinal directions, subject to the compatibility requirement. We even allow the arrow in a corner square to point in the eighth forbidden direction.

Define a function $N$, from the set of all pairs of adjacent elements of $S$ to the set $\{ - 45^{\circ},0^{\circ},45^{\circ} \}$, as follows. If $A,B \in S$ are adjacent, define $N(A,B)$ as the angle $\theta \in \{ \pm 45^{\circ},0^{\circ} \}$ that we must turn the arrow in $A$ to obtain the arrow in $B$. (Counterclockwise rotations are considered positive.) Clearly, $N(B,A) = - N(A,B)$ for any pair $(A,B)$ of adjacent elements of $S$.

Next, define a function $W: V \to \mathbb{R}$, which we call the winding-number function, as follows:

• For any vertex $v$ that is not a corner of the cube, let $$W(v) \stackrel{\text{df}}{=} N(A,B) + N(B,C) + N(C,D) + N(D,A),$$ where $(A,B,C,D)$ is any counterclockwise ordering of the four squares surrounding $v$; from the compatibility requirement, we have $W(v) = 0^{\circ}$.
• For any vertex $v$ that is a corner of the cube, let $$W(v) \stackrel{\text{df}}{=} N(A,B) + N(B,C) + N(C,A),$$ where $(A,B,C)$ is any counterclockwise ordering of the three squares surrounding $v$; it is not difficult to check that $W(v) = - 90^{\circ}$.

Now, $\displaystyle \sum_{v \in V} W(v) = 0^{\circ}$ as any two adjacent elements of $S$ appear exactly twice, in opposite orders, when summing up all the winding numbers. On the other hand, we have $$\sum_{v \in V} W(v) = - 90^{\circ} \times 8 = - 720^{\circ},$$ as each vertex that is a corner of the cube contributes $- 90^{\circ}$, while any other vertex contributes $0^{\circ}$. This contradiction implies that there cannot be a ‘legal’ configuration.

To prove the continuous Hairy Ball Theorem, take $n$ large enough and then argue by contradiction.

• I must add that my argument requires $n \in \mathbb{N}_{\geq 2}$. – Transcendental Jul 31 '16 at 4:45