IBM Ponder This #041 · 2001 年 9 月

Thomas Schwentick 提出了这个研究型问题。

给定 N，考虑集合 {0,1,…,N-1} 上的置换群 G，要求 G 中每个置换 g 与固定的 N-循环 (0,1,2,…,N-1) 复合以后，仍然是一个 N-循环。求满足条件的最大群的阶的上界与下界。

这里，置换群对置换复合封闭；循环 (a,b,c) 表示 a 映到 b、b 映到 c、c 映到 a。N-循环会遍历全部 N 个元素后才返回起点。

当 N 是 2 的幂时，已知可构造阶为 2^N/(2N) 的群。以下 N=8 的例子有 2^8/(2×8)=16 个元素，每行先列出 g(0),…,g(7)，再给出循环表示：

0	1	2	3	4	5	6	7		(0)(1)(2)(3)(4)(5)(6)(7)
0	1	6	7	4	5	2	3		(0)(1)(2,6)(3,7)(4)(5)
0	5	2	7	4	1	6	3		(0)(1,5)(2)(3,7)(4)(6)
0	5	6	3	4	1	2	7		(0)(1,5)(2,6)(3)(4)(7)
2	3	0	1	6	7	4	5		(0,2)(1,3)(4,6)(5,7)
2	3	4	5	6	7	0	1		(0,2,4,6)(1,3,5,7)
2	7	0	5	6	3	4	1		(0,2)(1,7)(3,5)(4,6)
2	7	4	1	6	3	0	5		(0,2,4,6)(1,7,5,3)
4	1	2	7	0	5	6	3		(0,4)(1)(2)(3,7)(5)(6)
4	1	6	3	0	5	2	7		(0,4)(1)(2,6)(3)(5)(7)
4	5	2	3	0	1	6	7		(0,4)(1,5)(2)(3)(6)(7)
4	5	6	7	0	1	2	3		(0,4)(1,5)(2,6)(3,7)
6	3	0	5	2	7	4	1		(0,6,4,2)(1,3,5,7)
6	3	4	1	2	7	0	5		(0,6)(2,4)(1,3)(5,7)
6	7	0	1	2	3	4	5		(0,6,4,2)(1,7,5,3)
6	7	4	5	2	3	0	1		(0,6)(2,4)(1,7)(3,5)

例如，把第四个置换 (0)(1,5)(2,6)(3)(4)(7) 与第五个置换 (0,2)(1,3)(4,6)(5,7) 依次作用，得到 (0,2,4,6)(1,7,5,3)。各元素的两步映射为 0→0→2、1→5→7、2→6→4、3→3→1、4→4→6、5→1→3、6→2→0、7→7→5。

最后一个置换 (0,6)(2,4)(1,7)(3,5) 与 (0,1,2,3,4,5,6,7) 复合，得到 (0,7,2,5,4,3,6,1)，说明它满足题目要求。

这种构造可以推广为“吊灯群”：取二叉树，叶子代表 0 至 N-1。顶层区分最低二进制位，因此左子树为偶数、右子树为奇数，以下各层依此类推。N=8 时叶子顺序为 [0,4,2,6,1,5,3,7]，即二进制位反序。允许的树变换在每一层都进行偶数次左右子树交换；这里共有 log₂N=3 层。

出题人当时知道的最好上界约为 sqrt(N!)。官方鼓励改进从 2^N/(2N) 起的下界，或给出明显优于 N! 的上界，并特别认可每次首先实现的改进。

解答

认真尝试后再打开

待补充。