Let $B_n$ be the hyperoctahedral group (the isometries of the $n$-dimensional hypercube). Let $k <n$ and consider the action of $B_n$ on the $k$-dimensional faces of the hypercube.

What can you say about cycles in this permutation representation of $B_n$? What is the longest cycle you can find?

Thank you.


I think this quickly leads to difficult questions.

Thinking of $B_n$ as the semidirect product $H \rtimes S_n$ where $H \cong C_2 \times \cdots \times C_2$, we can factorize each element of $B_n$ as $h t$ where $h \in H$ and $t \in S_n$. If $t$ has order $r$ then $(ht)^r = h'$ for some $h' \in H$, of order at most $2$. Choosing $h$ suitably, we can assume $h'$ is not the identity. Hence the maximum order of an element of $B_n$ is twice the maximum order in $S_n$, say $m_n$. Landau proved that

$$\log m_n \sim \sqrt{n \log n} \quad\text{as $n \rightarrow \infty$.}$$

For $k$ reasonably large (but less than $n$), my guess is that this means there is an element of $B_n$ having a cycle of length $2m_n$ in the action of $B_n$ on $k$-faces.

If we position the hypercube so that its $(n-1)$-faces are determined by the equations $x_i = 1$ or $x_i = -1$ for $i \in \{1,\ldots, n\}$ then the $k$-faces correspond to equations $x_{i_1} = \pm 1, \ldots, x_{i_{n-k}} = \pm 1$, with $n-k$ chosen signs. Hence the stabiliser of a $k$-face is a conjugate of $B_k \times S_{n-k}$. Therefore, restricting the action of $B_n$ on $k$-faces to the chosen top group $S_n$, we get $S_n$ acting on the cosets of $S_k \times S_{n-k}$, i.e. $S_n$ acting on $k$-subsets of $\{1,\ldots, n\}$. For this action, I would guess that for 'most' $k$, the maximum cycle length is $m_n$. As far as I know, no result of this form has been proved.

Edit Let $c_n$ be the number of distinct prime factors of $m_n$. In Proposition 7 in Ordre maximal d'un élément du groupe symmétrique, Bull. Soc. Math. France. 97 (1969) 129–191, Nicolas proved that

$$ c_n \sim 2 \sqrt{\frac{n}{\log n}}.$$

Note that $c_n$ is the number of disjoint cycles (ignoring fixed points) in a permutation $\sigma_n \in S_n$ of maximum order $m_n$. If $k= c_n$ then there is a $k$-subset of $\{1,\ldots, n\}$ containing exactly one element from each cycle of $\sigma_n$. In the action of $\sigma_n$ on $k$-subsets, this subset is in a cycle of length $m_n$, the maximum possible. Multiplying $\sigma_n$ by a suitable element of the bottom group $H$ will give a cycle of length $2m_n$.

I still think it is a tricky problem to say much for general $k$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.