9
$\begingroup$

I am interested in finding out what are the shortest closed walks that touch all $n$ dimensions in an $n$-dimensional hypercube. Because they must be closed and they must touch all $n$ dimensions, the condition of them being shortest implies that they should have length $2n$.

I would like to find out how many "truly distinct" such walks there are, i.e. modulo rotations, reflections, without caring about the starting point, etc.

As far as I can tell, in $n=2$ there are two, and in $n=3$ there are five (see picture below). These are just the ones I have been able to find, I have no proof (in fact, I was about to post that there were four for $n=3$ when I realized that I had missed the fifth case below).

Drawings of the distinct walks for n=2 and n=3.

One can describe these walks as sequences, where $+i$ or $-i$ involve moving up or down coordinate $i$, respectively (with $i=1,...,n$), and where each element appears only once. For example:

3D, 3rd walk in the picture: +1,+2,+3,-1,-3,-2

3D, 4th walk in the picture: +1,+2,+3,-1,-2,-3

I thought maybe one could do combinatorics using these sequences, but I'm finding it hard to then appropriately get rid of all the redundancy coming from rotations and reflections, circular shift permutations, etc.

Is there a known answer to this problem? Or any ideas how to tackle it?

$\endgroup$
0

1 Answer 1

7
$\begingroup$

If you only wanted to quotient by symmetries of the cube, and not by shift (and presumably, reversal) of paths, there would be a very clean answer. The symmetry group of the cube is $S_n \ltimes \{ \pm 1 \}^n$, which acts on $\{ \pm 1, \pm 2, \ldots, \pm n \}$ in the obvious way. We want to consider permutations of the set $\{ \pm 1, \pm 2, \ldots, \pm n \}$, up to the action of the symmetries of the cube. This action is free, so there are $$\frac{(2n)!}{2^n n!} = (2n-1) (2n-3) (2n-5) \cdots 5 \cdot 3 \cdot 1 = (2n-1)!!$$ walks up to symmetries of the cube. (Reference for double factorial notation.)


We can biject these "walks up to symmetries of the cube" with ways to partition $\{ 1,2,3,\ldots, 2n \}$ into $n$ sets of size $2$: We have a block $\{ i,j \}$ in the partition if the $i$-th step and the $j$-th step are edges in opposite directions. For example, your walk $(+1,+2,+3,-1,-3,-2)$ corresponds to the partition $\{ 1,4 \} \sqcup \{ 2,6 \} \sqcup \{ 3,5 \}$. I'll visualize this by drawing $2n$ points around the boundary of a circle, connected by chords.

The figure below, taken from Wikipedia, shows the $15 = 5!!$ chord diagrams in the $n=3$ case, corresponding to the walks in a $3$ dimensional cube.

The fifteen pairings of six points


Now, we want to quotient further by shifting the walk sequences, and I assume also by reversing them. This gives an action of the dihedral group of order $4n$. In terms of our chord diagrams, we want to count these chord diagrams up to rotation and reflections.

I have edited the Wikipedia figure to show how the $15$ walks, above, are grouped into the $5$ classes that you found.

The fifteen pairings of six points, grouped into five symmetry classes


We can do this using Burnside's lemma. Recall: Let $G$ be a finite group acting on a finite set $X$. Then Burnside's lemma says that the number of orbits of $G$ on $X$ is $$\frac{1}{|G|} \sum_{g \in G} |X^g|. $$ So, for each $g$ in the dihedral group, we need to figure out how many chord diagrams are fixed by $g$. (For an easier problem using the same strategy, see how we use Burnside's lemma to count necklaces up to rotation.)

It will be convenient to introduce the notation. $$\tau_m(x) := \sum_{k=0}^{\lfloor m/2 \rfloor} \binom{m}{2k} (2k-1)!! \cdot x^k. $$ For example, $$\tau_4(x) = 1+\binom{4}{2} 1!! x + \binom{4}{4} 3!! x^2 = 1 + 6 x + 3 x^2.$$ In other words, the coefficients of $\tau_m$ are the rows of https://oeis.org/A100861 .

We now carry out the Burnside computation, and break into cases:

Case 1: $g$ is a rotation with period $d$ for $d$ odd.

So $g$ breaks $\{1,2,\ldots, 2n \}$ up into $\tfrac{2n}{d}$ orbits, each of size $d$. A $g$-invariant matching must pair these orbits up with each other. There are $\left( \tfrac{2n}{d} -1 \right)!!$ ways to pair off the orbits and then, for each pair of orbits, there are $d$ $g$-invariant ways to match them. (Match one element arbitrarily, the rest are fixed.) So, in this case, $$|X^g| = \left( \frac{2n}{d} -1 \right)!! d^{n/d}.$$

Case 2: $g$ is a rotation with period $d$ for $d$ even.

Again $g$ breaks $\{1,2,\ldots, 2n \}$ up into $\tfrac{2n}{d}$ orbits, each of size $d$. We can still pair off orbits with each other, but we can also choose one of the orbits and match it within itself. In each orbit $\{ z, gz, g^2 z, \ldots, g^d z \}$, there is a unique $g$-invariant matching, namely, matching $g^i z$ with $g^{i+d/2} z$.

So we must choose $n/2d - 2k$ of the orbits to match with themselves, then pair off the remaining $2k$ orbits in one of $(2k-1)!!$ possible ways and, finally, for each pair of orbits, choose one of the $d$ many possible matchings. In short, in this case, $$|X^g| = \tau_{2n/d}(d).$$

Case 3: $g$ is a reflection with no fixed points.

This is exactly like Case 2 for $d=2$, we have $$|X^g| = \tau_{n}(2).$$

Case 4: $g$ is a reflection with two fixed points.

The two fixed points must be matched to each other. The remaining $2n-2$ points act just like Case $3$, so $$|X^g| = \tau_{n-1}(2).$$

Summing over the whole dihedral group, we get our FINAL ANSWER: $$\frac{1}{4n} \left( \sum_{d|2n,\ d \ \text{odd}} \phi(d) \left( \frac{2n}{d} -1 \right)!! d^{n/d} + \sum_{d|2n,\ d \ \text{even}} \phi(d) \tau_{2n/d}(d) + n \tau_n(2) + n \tau_{n-1}(2) \right).$$ Here $\phi(d)$ is Euler's totient function, which counts the number of order $d$ rotations in the dihedral group.


For example, when $n=3$, we get $$\frac{1}{12} \left( \phi(1) \cdot 5!! + \phi(3) \cdot 1!! \cdot 3 + \phi(2) \tau_{3}(2) + \phi(6) \tau_1(6) + 3 \tau_3(2) + 3 \tau_2(2) \right)=$$ $$\frac{1}{12} (1 \cdot 15 + 2 \cdot 3 + 1 \cdot 7 + 2 \cdot 1 + 3 \cdot 7 + 3 \cdot 3)=5.$$

You can enjoy going through the diagram of fifteen matchings above, considering the various elements in the hexagonal dihedral group, and seeing how they fix $15$, $3$, $7$, $1$, $7$ or $3$ matchings.

$\endgroup$
6
  • $\begingroup$ Hi David, thanks for the awesome answer. There has been in the meantime substantial discussion about this problem on the /r/math subreddit, see reddit.com/r/math/comments/1f7ui06/… I did figure out the connection to chord diagrams and realized that what I am looking for is OEIS A007769 "Number of chord diagrams with n chords; number of pairings on a necklace". Starting from n=2, we get 2, 5, 18, 105... The reason I care about necklaces and not bracelets is because I don't want to quotient by reversal of the paths, paths are oriented. $\endgroup$
    – m3tro
    Commented Sep 4 at 10:07
  • $\begingroup$ I was about to post this as an answer right now, when I came across your answer. You did get to a solution of the problem (can you confirm that your approach would give A007769?) so I am happy accept your answer if you updated it with the additional information. $\endgroup$
    – m3tro
    Commented Sep 4 at 10:15
  • 1
    $\begingroup$ Another neat result of the chord diagram approach is that one can immediately see which paths are "non-returning" (like path number 2 for 2D and paths number 3 and 4 in 3D in the image above) by checking whether the chord diagram is connected. The number of connected diagrams for different n is given in OEIS A018225 and, starting from n=2, is 1, 2, 6, 31... $\endgroup$
    – m3tro
    Commented Sep 4 at 10:19
  • 1
    $\begingroup$ @m3tro, A054499. $\endgroup$ Commented Sep 4 at 10:48
  • 2
    $\begingroup$ Glad to see it worked out! If you don't want to quotient by reflections, you can just use the rotations terms in the Burnside computation, and divide by $2n$ (order of the rotation group) instead of $4n$. $\endgroup$ Commented Sep 4 at 13:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .