考虑让前后左右上下分别对应四元数 $+\mathrm i, -\mathrm i, +\mathrm j, -\mathrm j, +\mathrm k, -\mathrm k$. 假设前, 左, 上经历某个立方体的旋转变换 $\sigma$, 变成 $x, y, z$, 则 $x, y, z$ 满足右手定向关系: $xy = z$, 换句话说: $xyz = -1$.
所以现在问题是: 计数如下组合对象: 序列 $x, y, z \in \{ \pm \mathrm i, \pm \mathrm j, \pm \mathrm k \}^N$, 满足
- 对 $0 \le i < N$, $x_iy_iz_i = -1$ 恒成立;
- $\pm x, \pm y, \pm z$ 这 $6$ 个序列都是输入允许的.
很显然, 这是一个卷积问题. 也就是说, 如果设 $F(x) = 1 \iff x \in S \operatorname{\text{且}} -x \in S$, 其它项为 $0$, 那么这个问题相当于计算 $(F * F * F)([-1,-1,\dots,-1])$. 其中卷积是这样定义的: $$ (F * G)(x) = \sum_{a_i b_i = x_i} F(a) G(b). $$ 其中我们定义的 $a_i,b_i,x_i$ 在群 $Q_8 = { \pm 1, \pm \mathrm i, \pm \mathrm j, \pm \mathrm k }$ 上取.
显然我们要对 $Q_8$ 做不可约表示的计算.
其不可约表示的数量是 $5$, 因为有五个共轭类, 代表元分别是 $1, -1, \rm i, j, k$. 四个一维的表示可以通过其 Abel 化 $Q_8 / [Q_8, Q_8] \simeq (\mathbb Z / 2 \mathbb Z)^2$ 来计算, 因此不难写出这四个表示; 同时通过一些注意力, 不难发现 $Q_8 \hookrightarrow \mathrm{SL}_2(\mathbb C)$ 是一个不可约表示, 那么我们就确定了 $Q_8$ 的所有不可约表示, 同时附上一张特征标表. $$ \left( \begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & -1 & -1 \\ 1 & 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 & 1 \\ 2 & -2 & 0 & 0 & 0 \\ \end{array} \right). $$
现在我们直接做 Fourier 变换得到了一个 $12^N$ 做法, 看起来过不了.
我们现在具体来写一下答案. 根据群上的 Fourier 反演: $$ [g = h] = \dfrac{1}{|G|} \sum_{\rho \in G^\vee} d_\rho \mathrm{tr}\left(\rho(gh^{-1})\right), $$ 我们只关心 $\rho(\mathrm i), \rho(\mathrm j), \rho(\mathrm k)$ 的线性组合. 那么我们就发现四个 $1$ 维表示不用动; 二维表示考虑到, 纯四元数的 $\mathrm{tr} = 0$, 所以我们只关心 ${ (x,y,z,w) : x+w = 0 }$, 这个空间的一组基是 $\rho(\mathrm i), \rho(\mathrm j), \rho(\mathrm k)$. 缩减考虑范围到一个 $3 \times 3 \times 3$ 张量. 考虑恒等式: 对 $x,y \in {\mathrm i, \mathrm j, \mathrm k}$, 由于表示是表示, $\mathrm{Tr}(\rho (xyz)) = 2 \varepsilon_{xyz}$ (直接计算 $xyz$). 其中 $\varepsilon$ 是 Levi-Civita 张量, 定义为: 在奇排列上取 $-1$, 在偶排列上取 $1$, 在不成排列上取 $0$. 所以 $2 \varepsilon$ 就是所需张量, 其几何意义为行列式.
问题转化为求 $3 \times 3$ 矩阵行列式的 (边界) 秩问题. arXiv 1709.06131 的解答是: 其秩和边界秩都是 $5$. 再加上 $4$ 个一维表示, 时间复杂度为 $\Theta(9^N \mathrm{poly}(N))$, 精细地实现并分析可得这个 $\mathrm{poly}$ 项是常数.
