题解：P17230 [Math×Girl²] 染色³

· · 题解

声明: 写作过程中多次使用 AI 检验并修改病句、斟酌用词与行文, 论证的展开亦有 AI 参与; 思路均出自魔女の理团队的各出题人、验题人及我的个人理解.

约定. 根据个人习惯, 所有数组下标从 0 开始. 这可能影响你对奇数位置等术语的理解.

总结. 每个 k\times k\times k 网格块中的唯一黑点, 可由三个相位函数表示. 窗口条件可改写为相位条件; 合法方案要么存在常值相位, 要么由三组投影两两不交的支撑集确定. 最后的计数用两次二维 NTT 卷积完成, 复杂度为 O\bigl(bc(\log b+\log c)\bigr).

题目描述. 设 a, b, c, k 是正整数, A = ak, B = bk, C = ck. 将

要求每个形如 $[i, i+k) \times [j, j+k) \times [\ell, \ell+k)

的区域内有且仅有一个黑点. 求方案数对某个可 NTT 模数 p_{\rm NTT} 取模的结果.

算法

记 [r]=\{0,1,\ldots,r-1\}, 将原网格划分为 abc 个 k\times k\times k 网格块, 编号为 (u,v,w)\in[a]\times[b]\times[c]. 每个网格块本身就是一个窗口, 因而恰有一个黑点; 把它写成

\bigl(ku+X_{u,v,w},\ kv+Y_{u,v,w},\ kw+Z_{u,v,w}\bigr),

其中三个余数都属于 [k].

固定 v,w, 考察沿 x 方向相邻的两个网格块 u,u+1. 对任意 1\le s<k, 从 ku+s 开始的长度 k 区间包含前一个网格块的黑点当且仅当

窗口内恰有一个黑点, 故这两个条件恰有一个成立. 这对所有 $s$ 成立, 便推出 $X_{u,v,w}=X_{u+1,v,w}$. 沿另两个方向同样推导, 可得三个函数 $$X:[b]\times[c]\to[k],\qquad Y:[a]\times[c]\to[k],\qquad Z:[a]\times[b]\to[k],$$ 使网格块 $(u,v,w)$ 中黑点的相位恰为 $(X(v,w),Y(u,w),Z(u,v))$. **引理 G.1 (相位条件).** 上述染色方案与满足下述条件的三元组 $(X,Y,Z)$ 一一对应: 任取不同的 $(u,v,w),(u',v',w')$, 以下三项至少一项成立: $u\ne u'$ 且 $X(v,w)=X(v',w')$; $v\ne v'$ 且 $Y(u,w)=Y(u',w')$; $w\ne w'$ 且 $Z(u,v)=Z(u',v')$. **证明.** 前面的论证已说明每个染色方案对应三个相位函数. 任取一个窗口, 每条被窗口跨越的网格块边界都产生一个阈值 $s\in\{1,\ldots,k-1\}$. 对窗口接触到的每个网格块, 记录其黑点在各个跨越坐标上是否落入窗口, 得到一个 $0$-$1$ 向量. 若两个网格块的向量相同, 它们在每个编号不同的坐标上的相位都不同, 与条件矛盾; 故这个映射单射. 定义域和值域大小相同, 恰有一个网格块的黑点落入窗口. 反过来, 若有一对网格块不满足该条件, 就在每个编号不同的坐标选一个分开两个相位的阈值. 它们在相应窗口中得到同一 $0$-$1$ 向量, 映射不单射; 有限集上的非单射映射不满射, 故某个同类窗口中黑点数不是一. $\blacksquare

引理 G.2 (二维计数). 设 U:[s]\to[k] 与 V:[r]\to[k] 满足: 对任意

这样的函数对恰有 $P_k(r,s)=k^{r+1}+k^{s+1}-k^2$ 个. **证明.** 若 $U$ 非常值, 取两个取值不同的位置 $j,j'$, 便知 $V$ 必为常值; 反之亦然. $U$ 为常值时有 $k\cdot k^r$ 种, $V$ 为常值时有 $k^s\cdot k$ 种, 两者同时为常值的 $k^2$ 种被重复计算一次, 故 $$P_k(r,s)=k^{r+1}+k^{s+1}-k^2.$$ $\blacksquare

若 X 全局为常值, 有 k 种选择; 对每个固定的 u, 函数对

因此这类方案数为 $kP_k(b,c)^a$. 三个相位函数轮换后, 再作容斥, 得到至少一个相位函数全局为常值的方案数 $$\begin{aligned} L_k(a,b,c)={}&kP_k(b,c)^a+kP_k(a,c)^b+kP_k(a,b)^c\\ &-k^2\bigl(k^{ab}+k^{ac}+k^{bc}\bigr)+k^3. \end{aligned}$$ 以下设 $X,Y,Z$ 都不是常值. 固定 $w$, 对只在 $u,v

两个坐标不同的网格块使用相位条件, 可知 X(\cdot,w) 与 Y(\cdot,w) 至少一个为常值; 循环置换坐标后也同理. 因而每个相位函数的取值表沿两个方向都存在非常值的行或列.

以 X 为例, 令 B_X 为 X(v,\cdot) 非常值的行指标集, C_X 为

$B_X\times C_X$ 内的位置都取同一个基准值 $x_0$. 令 $S_X$ 为 $X$ 偏离 $x_0$ 的位置集, 并同样定义基准值 $y_0,z_0$ 与支撑集 $S_Y,S_Z$. 于是三个支撑集都非空, 并满足 $$\pi_C(S_X)\cap\pi_C(S_Y)=\varnothing,\qquad \pi_B(S_X)\cap\pi_B(S_Z)=\varnothing,\qquad \pi_A(S_Y)\cap\pi_A(S_Z)=\varnothing.$$ 这三个投影两两不交的条件也是充分的. 若一对网格块不满足相位条件, 则每个相位函数恰有一个端点落在相应支撑集中. 三组支撑各自选出的端点只有两个, 因而至少两组会落在同一端点; 这正被对应的投影不交条件排除, 矛盾. 令 $q=k-1$. 每个支撑位置有 $q$ 个非基准取值. 设 $H_k(a,b,c)

为三组非空支撑及其非基准取值的方案数, 设 T_k(a,b,c) 为允许支撑为空时的方案数. 对空支撑作容斥可得 \begin{aligned} H_k(a,b,c)={}&T_k(a,b,c)-(k^b+k^c-1)^a-(k^a+k^c-1)^b\\ &-(k^a+k^b-1)^c+k^{bc}+k^{ac}+k^{ab}-1. \end{aligned} 故总答案为 F(k;a,b,c)=L_k(a,b,c)+k^3H_k(a,b,c).

现计算 T_k. 对 A 中每个顶点, 标记它只连接 S_Y、只连接 S_Z 或不连接的状态, 权重依次取 1,1,-1; B,C 中的顶点同理. 若一个顶点同时连接两种支撑, 则所有状态均不合法; 若它孤立, 三种权重之和为

将 $A$ 中三个状态的顶点数记为 $r,s,a-r-s$, $B$ 中记为 $u,v,b-u-v$, $C

中记为 p,t,c-p-t. 可选支撑位置数为 rt+sv+up, 每个位置可空或取 k-1 个颜色, 故固定状态的贡献为 k^{rt+sv+up}. 直接六重求和可以计算答案, 但并不够快.

定义

S_k(m,n)=\sum_{r=0}^{m}\sum_{s=0}^{n}(-1)^{m-r+n-s}\binom mr\binom ns k^{rs}.

它正是元素取自 [k]、且没有空行和空列的 m\times n 矩阵数. 先对 A 方向求和, 可把六重式化为二维卷积形式:

T_k(a,b,c)=\sum_{u=0}^{b}\sum_{v=0}^{c}\binom bu\binom cv\bigl(k^u+k^v-1\bigr)^aS_k(b-u,c-v).

在模数 p_{\rm NTT} 下预处理阶乘与逆阶乘. 令 K_{u,v}=k^{uv}/(u!v!),

E_{u,v}=(-1)^{u+v}/(u!v!)$. 则 $S_k(m,n)/(m!n!)$ 是 $K$ 与 $E

的二维卷积系数. 令 A_{u,v}=(k^u+k^v-1)^a/(u!v!), 把 A 与归一化后的

的时间复杂度为 $O\bigl(bc(\log b+\log c)\bigr)$, 空间复杂度为 $O(bc)$; 卷积后只保留 $0\le m\le b,0\le n\le c$ 的系数即可. ## 附录: Keller 命题 本题若推广到 $D\ge8$, 将遇到本质的数学障碍, 因为 Keller 命题在这一维数起不再成立. Keller 命题 $\mathbf K(n)$ 表述如下: 若 $\mathbb R^n$ 是若干与 $U=[0,1)^n$ 全等的超立方体的不交并, 则其中必有两个超立方体共享一个 $n-1

维侧面. 这一命题目前的情况是:

定理 G.3. 对于 D \le 7, \mathbf K(D) 成立; 对于 D \ge 8, \mathbf K(D) 不成立.

下文证明 D\le5 时 \mathbf K(D) 成立 (D=6,7 亦成立, 见附录末注). 本题所需的结论比一般情形弱得多, 仍附于此以备参考.

沿用前文的记号 e(x) = \mathrm e^{2 \pi \mathrm i x}.

设 T\subseteq\mathbb R^D 满足: 对任意 x\in\mathbb R^D, 唯一存在

**引理 G.4 (相位引理).** 对于任意两个不同的 $s, t \in T$, 存在某个坐标 $i$, 使得 $s_i - t_i \in \mathbb Z \setminus \{0\}$. **证明.** 取一条平行于第 $i$ 个坐标轴的直线 $\ell$. 它与所经过的每个正方体 $s+U

相交成一个长度为 1 的区间; 这些区间无重无漏地覆盖整条实轴, 故端点的小数部分相同, 记作 p(\ell)\in\mathbb R/\mathbb Z. 固定

$\Lambda=\{t\in T:t_i\equiv\alpha\pmod1\}+U$. 它沿 $e_i$ 方向平移不变, 即 $\Lambda+u\cdot e_i=\Lambda$. 因此, 将 $\Lambda$ 中所有正方体沿 $e_i

同时平移, 其余正方体不动, 仍得到一个密铺.

以下反证. 假设对任意 i 都有 s_i-t_i\notin\mathbb Z\setminus\{0\}. 依次处理坐标 i=0,1,\ldots,D-1: 若 s_i=t_i, 便略过; 否则 s_i-t_i 不是整数. 取 \alpha=t_i, 则 t+U\subseteq\Lambda 而

$t$ 的第 $i$ 个坐标变为 $s_i$. 全部处理完后, 两个正方体重合, 与密铺矛盾. $\blacksquare

由此, Keller 命题化为一个组合问题. 设字符集 \Sigma, 定义

若存在 $i$ 使 $s_i=t_i^\vee$, 就说两个字符串 $s,t\in\Xi^D$ **呼应**. 若它们恰好在一个坐标不同, 即 $\sum_{i=0}^{D-1}[s_i=t_i]=D-1$, 且呼应, 则称它们构成**孪生对**. **多盒码**是 $\Xi^D$ 的子集, 其中任意两个字符串都呼应. **定理 G.5.** 若 $\mathbf K(D)$ **不成立**, 则存在一个不含孪生对的多盒码 $S \subseteq \Xi^D$, 满足 $|S| = 2^D$. **证明.** 设有 $\mathbf K(D)$ 的反例密铺. 对几乎所有点 $P$, $P + \{0, 1\}^D

都位于某个正方体内部 (边界的测度为零), 取这样的一个点 P. 对

$P + \varepsilon$ 所在正方体的角点, 即 $P + \varepsilon \in t(\varepsilon) + U$. 取 $\Sigma=[0,1)$. 用 $(y\bmod1,\lfloor y\rfloor\bmod2)\in\Xi$ 表示 $y\bmod2$. 这 $2^D$ 个字符串 $t(\varepsilon)\bmod2\in\Xi^D

构成一个不含孪生对的多盒码.

对不同的 \varepsilon,\varepsilon', 相位引理说明

$t(\varepsilon)$ 的第 $i$ 个坐标落在 $[P_i+\varepsilon_i-1,P_i+\varepsilon_i+1)$, 所以前述整数只能是 $-1$ 或 $1$. 两个字符串遂在该坐标呼应, 因而构成多盒码. 若其中有一对孪生, 相应的两个正方体便相差 $\pm e_i$, 从而共享一个面, 这与反例密铺矛盾. $\blacksquare

为了继续证明, 先给每个字符串定义一个盒. 设维数为 n (即 D), 取样本空间 \Omega=\{0,1\}^{\Sigma\times[n]}, 并赋以均匀乘积测度 \mu. 对 v=((\sigma_0,b_0),\ldots,(\sigma_{n-1},b_{n-1}))\in\Xi^n, 令

$\mu(B(v))=2^{-n}$. 多盒码中不同字符串在某个坐标呼应, 所以相应的盒两两不交. 称两个多盒码 $S,T$ **等价**, 若 $\bigcup_{v\in S}B(v)=\bigcup_{w\in T}B(w)$. 对 $v,w\in\Xi^n$, 定义 $$g(v,w)=\prod_{i=0}^{n-1}g_i(v_i,w_i),\qquad g_i(s,t)= \begin{cases} 2,&s=t,\\ 0,&s=t^\vee,\\ 1,&t\notin\{s,s^\vee\}. \end{cases}$$ 逐坐标计算可得 $$\mu(B(v)\cap B(w))=2^{-2n}g(v,w).

事实上, 第 i 个坐标上字符相同时交集的相对测度为 1, 互补时为空集, 其余情形为 1/2; 这正是 2^{-1}g_i(v_i,w_i).

若 V 是多盒码, 则其中的盒两两不交, 因而

=2^{-2n}\sum_{v\in V}g(v,w).$$ 左侧等于 $\mu(B(w))=2^{-n}$ 当且仅当 $B(w)\subseteq\bigcup_{v\in V}B(v)$. 所以 $$B(w)\subseteq\bigcup_{v\in V}B(v) \quad\Longleftrightarrow\quad \sum_{v\in V}g(v,w)=2^n.

记 w\preceq V 表示这个包含关系. 若 S,T 等价且 S\cap T=\varnothing, 则对 b\in T 有 b\preceq S, 对 a\in S 有 a\preceq T. 又两边的盒并相等, 而每个盒测度都为 2^{-n}, 故 |S|=|T|=:m. 注意: 多盒码内任意两个字符串都呼应, 因而其中的孪生对恰好是只在一个坐标不同的字符串对.

引理 G.6 (五盒). 设 V\subset\Xi^n 是不含孪生对的多盒码, w\notin V, w\preceq V, 且 B(w)\cap B(v)\ne\varnothing 对所有 v\in V 成立. 则 |V|\ge5. 若

|V|=5$, 则存在坐标 $0,1,2$ 和字符 $a_i\notin\{w_i,w_i^\vee\}$, 使 $V

在这些坐标上的限制为

a_0a_1a_2,\quad a_0^\vee a_1^\vee a_2^\vee,\quad w_0a_1a_2^\vee,\quad a_0^\vee w_1a_2,\quad a_0a_1^\vee w_2 \end{gathered}

(其余坐标处均取 w), 且这个由 5 个字符串构成的码是刚性的: 它覆盖的完整字符串中, 除这 5 个字符串外只有 w 本身. 若 |V|=6, 则某个 v\in V 与 w 只在一个坐标不同.

证明. 在 B(w) 内, 将 v_i=w_i 的坐标替换为通配符, 其余字符不变, 得广义字符串 \bar v. 因 B(v)\cap B(w)\ne\varnothing, 不会出现

通配化不改变两个字符串不同的坐标集合, 故所得广义字符串码仍无孪生对. 若广义字符串 $\bar v$ 有 $r(\bar v)$ 个非通配坐标, 则它在 $B(w)

内的相对测度为 2^{-r(\bar v)}, 从而 \sum_{v\in V}2^{-r(\bar v)}=1.

将上式按二进制权重分解后枚举可知: |V|\le4 时分布只能为 \{2,2,2,2\} 或 \{1,2,3,3\}; |V|=5 时只能为 \{1,3,3,3,3\} 或 \{2,2,2,3,3\}. 以下逐类检验, 并反复使用任意两个字符串至少在两个坐标不同且彼此呼应:

故 |V|\ge5. 当 |V|=5 时, 分布只能为 \{2,2,2,3,3\}: 两个 r=3 字符串在三个活动坐标上彼此互补, 三个 r=2 字符串再由覆盖关系唯一确定为上述由 5 个字符串构成的构型.

刚性: 设完整字符串 u 被这 5 个盒覆盖. 若活动坐标外有 u_j\ne w_j, 在 B(u) 中取一个避开这 5 个盒的切片, 便能找到未被覆盖的点; 在三个活动坐标内, 除非 u_0u_1u_2=w_0w_1w_2, 上述构型的并同样留有空隙. 故 u=w.

最后设 |V|=6. 若没有字符串满足 r(\bar v)=1, 则所有 r(\bar v)\ge2; 由上式, 六项和为 1 时权重只能为 1/4,1/4,1/8,1/8,1/8,1/8.

对划分中的每个真柱面应用五盒分类, 可知两个 1/4-盒和四个

另一侧是上述由 $5$ 个字符串构成的构型. 因而某个字符串满足 $r(\bar v)=1$; 还原通配符便知它与 $w$ 只在一个坐标不同. $\blacksquare

引理 G.7 (推论). 设 V, W 是不交的等价无孪生对多盒码, m = |V| = |W| \le 11. 则:

  1. 不存在 v \in V, w \in W 恰在一个坐标处不同;

  2. 若对某坐标 i 与字符 l, V_{i,l} 与 V_{i,l^\vee} 都至少含 5 个字符串, 则 m\ge12;

其中 V_{i,l} = \{v \in V : v_i = l\}.

证明. (1) 设 v_{i^c}=w_{i^c}, v_i=a\ne b=w_i. 由 v\preceq W, B(v) 在坐标 i 上背向 w 的一侧须由 W 中第 i 坐标取 b 的互补字符的字符串覆盖. 投影掉坐标 i 后, 五盒引理给出至少 5 个这样的字符串. 对称地, B(w) 背向 v 的一侧至少需要 5 个 V 中第

i$ 坐标取 $a$ 的互补字符的字符串. 这两组字符串连同 $v,w

所在切片互不重合, 因为任一由 5 个字符串构成的覆盖都不能坍缩到 v 或

\(2\) 分别对与 $V_{i,l}$ 相交的 $w\in W$ 和与 $V_{i,l^\vee}$ 相交的 $w'\in W$ 应用五盒引理. 若一侧恰为刚性的 $5$ 字符串构型, 等价性将迫使 $V,W$ 出现只在一个坐标不同的字符串, 与 (1) 矛盾. 因此至少一侧需要 $6

个字符串, 从而 m\ge5+6+1=12.

(3) 设坐标 i 出现三个互补字符对

\{a,a^\vee\},\{b,b^\vee\},\{c,c^\vee\}$. 同时取 $a,b,c

的切片投影掉坐标 i 后给出低维等价码; 对 a^\vee,b^\vee,c^\vee 也一样. 五盒引理给每侧至少 5 个盒, 第三个字符对的其余出现再给两个相对切片各至少 1 个字符串, 故

$\blacksquare

引理 G.8 (等价码引理). 设 S, T 都是不含孪生对的多盒码, 若

**证明.** 反设 $m \le 11$, 取 $n$ 最小的反例. **归约.** 由推论 (3), 每个坐标至多有两个互补字符对. 若某个坐标只用一对 $\{a,a^\vee\}$, 将该坐标两侧切片并投影掉它, 得到 $n-1$ 维等价码. 由 $n

的最小性和无孪生条件, 两个投影码必重合; 还原到 n 维便会得到 S,T 的公共字符串或孪生对, 均不可能. 因此逐坐标重命名后, 每个坐标恰含四个字符

若 $S_{i,a}=\{u\}$, 等价性迫使 $a^\vee$ 一侧 (直接或经 $b,b^\vee

两个切片) 至少有 5 个字符串; 另一互补侧也至少有 5 个. 连同 u 与第四侧必要的字符串, 有 m\ge12, 矛盾.

同理, 任意两个非互补切片的并至多含 7 个字符串; 否则另两个互补切片各至少含两个字符串, 从而 m\ge8+2+2=12.

孪生对. 称 u, v \in S 为 i-孪生对, 若

(即存在 $j \ne i$ 使 $u_j = v_j^\vee$, 其余坐标相同). **断言** 对每个坐标 $i$ 与非互补字符 $l,s\in\{a,a^\vee,b,b^\vee\}$, 存在 $i$-孪生对 $u,v\in S$ 满足 $u_i=l$, $v_i=s$. 若不然, 删去坐标 $i$ 后 $C=(S_{i,l}\cup S_{i,s})_{i^c}$ 不含孪生对, 且任意两个非互补切片合计至多有 $7$ 个字符串, 故 $|C|\le7$. 先证一个辅助结论: 对维数归纳可知, 至多有 $7

个字符串且不含孪生对的多盒码是刚性的, 即没有其他等价码. 维数 \le3 时, 另一等价表示若覆盖其中一个字符串而不包含它, 便由五盒引理得到唯一的刚性

删去公共字符串后, 剩下两个不交等价码, 总数至多为 $7$. 取其中一个码的字符串, 五盒引理给另一个码至少 $5$ 个覆盖字符串: 恰为 $5

个时构成刚性构型, 不可能; 有 6 或 7 个时, 沿与它只差一个坐标的字符串切片后归入归纳假设. 故 C 刚性.

将 \bigcup S=\bigcup T 沿坐标 i 取值为 l 或 s 的部分切开, 再投影掉坐标 i, 得 C 与 (T_{i,l}\cup T_{i,s})_{i^c} 等价. 由刚性知两者重合. 因 S\cap T=\varnothing, S 的 l 部分须与 T 的

$(S_{i,l})_{i^c}\preceq(S_{i,l^\vee})_{i^c}$ 且 $(S_{i,s})_{i^c}\preceq(S_{i,s^\vee})_{i^c}$. 两个覆盖码不交, 五盒引理各给至少 $5$ 个字符串, 连同两个非互补切片各至少两个字符串, 有 $m\ge5+5+2>11$, 矛盾. 断言得证. 在 $S$ 上定义图 $G$: $u,v$ 相邻当且仅当它们构成某个坐标的 $i$-孪生对, 边的颜色记为 $i$. 由断言, 每个坐标 $i$ 给出四条互不相同的边 (字符对 $\{a,b\},\{a,b^\vee\},\{a^\vee,b\},\{a^\vee,b^\vee\}$ 各一条), 故 $|E(G)|\ge4n$. 下面使用两个图论事实. 其一: 若 $u,v$ 相邻, 则存在坐标 $j$ 与互补字符对 $\{c,c^\vee\}$, 使 $|S_{j,c}\cup S_{j,c^\vee}|\ge\deg u+\deg v-1$. 事实上规范化后 $u,v$ 的孪生关系发生在坐标 $0,1$; $u$ 或 $v

的每个额外邻点都在一个额外孪生坐标上不同于其中一员. 在 \deg u+\deg v-2 次额外关联中, 除至多一个外, 都必须在某列保留一个固定的互补对, 否则两个邻点将不再呼应, 即得该不等式.

其二: 对任何图,

设 $M$ 为右端. 度数 $>M/2$ 的顶点构成独立集 (相邻则度数和超过 $M$); 由 Hall 定理它们可被匹配到度数 $<M/2$ 的顶点, 成对的顶点度数和不超过 $M$, 其余度数不超过 $M/2$, 即得该平均度数上界. **$n\ge6$.** 任一非互补切片合计至多有 $7$ 个字符串, 故每个互补字符对的出现次数也不超过 $7$; 上述度数不等式给出相邻 $u,v

满足 \deg u+\deg v\le8, 平均度数上界遂得 \bar d(G)\le4. 又

**$n=5$.** 同上 $\deg u+\deg v\le8$. 若每条边都有 $\deg u+\deg v\le7$, 则 $\bar d(G)\le7/2$, 与 $|E(G)|\ge20$ 合起来迫使 $m>11$, 矛盾. 故存在边 $uv$ 使 $\deg u+\deg v=8$. 度数不等式取等迫使两个坐标 $j,k

中各有 7 个 N(u)\cup N(v) 中的字符串使用某个固定互补字符对; 另一互补字符对在 j,k 各至少出现 4 次. 因 m\le11, N(u)\cup N(v) 之外至少有 3 个字符串同时在 j,k 使用另一对. 若这两组字符串不同, 已至少有 12 个顶点, 故 m=11 时它们只能是同样的 3 个字符串. 这 3 个字符串在 j,k 都使用字符对 \{b,b^\vee\}. 直接检验孪生对的定义可知, 连接它们与 N(u)\cup N(v) 的孪生边必经 u 或 v; 因而 b^\vee 与

**$n=4$.** 这是唯一需要有限分类的情形. 每个坐标的四个字符各至少出现在两个字符串中. 取 $w\in T$, 记 $S(w)=\{v\in S:B(v)\cap B(w)\ne\varnothing\}$. 由 $w\preceq S(w)$, 五盒引理给出 $|S(w)|\ge5$; $|S(w)|=6$ 时, 五盒引理断言存在与 $w

只在一个坐标不同的字符串, 与推论 (1) 矛盾; |S(w)|\ge10 时, S(w) 中没有第 i 列为 w_i^\vee 的字符串, 而每个切片至少含两个字符串, 故

下面只用一个有限情形下的奇偶性结论. 设 $u\notin V$ 且 $u\preceq V$, 其中 $V$ 为多盒码. 将 $B(u)$ 与所有 $B(v)$ 的交依次按坐标切开; 每次切开都把尚未切开的块分成一对互补半块. 对每个终块记录覆盖它的字符串中与 $u$ 互补的坐标数的奇偶性. 内部切面两侧的记录成对抵消, 而 $B(u)$ 的两个端面各留下一个记录, 故必有两个覆盖字符串的互补坐标数为奇数. 将此结论用于 $S\cap T=\varnothing$ 与任意 $s\in S\preceq T$, 得 $T

中两个字符串的互补坐标数为奇数. 无孪生对排除 1, 四维中只余 3. 重命名坐标与字符后可设 w^{(1)}=bbbb, w^{(2)}=b^\vee b^\vee b^\vee b.

对 v\in S(w^{(1)}), 记 r(v) 为 v 中 b 的个数; 因

$S(w^{(1)})$ 中有 $x$ 个字符串含两个 $b$, $y$ 个含一个 $b$, $z$ 个不含 $b$; 由 $\sum_{v\in S(w^{(1)})}g(v,w^{(1)})=16$, 有 $4x+2y+z=16$ 及 $x+y+z=k\in\{5,7,8,9\}$. 解出该计数关系后逐一检查 (两个被选字符串须在不含 $b$ 的位置取互补的 $a/a^\vee$ 字符, 出现孪生对立即排除). 至多交换各坐标的 $a,a^\vee$ 后, 剩下六种类型 ($(2,3,2)$ 有两个非同构型): $$\begin{array}{c|cccccc} k & 5 & 7 & 7 & 8 & 8 & 9\\ (x,y,z) & (3,2,0) & (2,3,2) & (2,3,2) & (1,5,2) & (0,8,0) & (1,4,4) \end{array}$$ 其代表码为 $$\begin{gathered} P_5 = \{aaab,\ a^\vee a^\vee a^\vee b,\ baa^\vee b,\ a^\vee bab,\ aa^\vee bb\},\\ C_7 = \{aaaa,\ aaa^\vee b,\ aa^\vee a^\vee a^\vee,\ a^\vee aba,\ a^\vee ba^\vee a^\vee,\ ba^\vee ba,\ bbaa^\vee\},\\ P_7 = \{aaab,\ aa^\vee ba,\ a^\vee baa^\vee,\ aaa^\vee a,\ aa^\vee aa^\vee,\ a^\vee bba,\ bba^\vee a^\vee\},\\ P_8^{(1)} = \{aaab,\ aba^\vee a^\vee,\ a^\vee aaa,\ a^\vee aba^\vee,\ a^\vee a^\vee a^\vee a^\vee,\ baa^\vee a,\ ba^\vee aa^\vee,\ ba^\vee ba\},\\ P_8^{(2)} = \{aaab,\ aa^\vee ba^\vee,\ aba^\vee a,\ a^\vee aba,\ a^\vee a^\vee a^\vee b,\ a^\vee baa^\vee,\ baa^\vee a^\vee,\ ba^\vee aa\},\\ P_9 = \{aaa^\vee a,\ aaba^\vee,\ aa^\vee a^\vee a^\vee,\ aa^\vee ba,\ a^\vee aaa^\vee,\ a^\vee a^\vee aa,\ a^\vee ba^\vee b,\ baaa,\ ba^\vee aa^\vee\}. \end{gathered}$$ 再看 $w^{(2)}$: 它只在坐标 $0,1,2$ 交换 $b\leftrightarrow b^\vee$. 分三种情形: - 两个覆盖都含 $5$ 个字符串: 该构型迫使 $S(w^{(1)})$ 的 $5

个字符串在某个非活动坐标都取 b. 若该坐标属于 0,1,2, 则这些字符串都不属于 S(w^{(2)}), 两个覆盖不交, 共得 10 个字符串, 且并集不含坐标 3 上取 b^\vee 的字符串; 该切片再补两个字符串,

若该坐标是 $3$, 则 $S(w^{(1)})\subset S_{3,b}$. 对 $S(w^{(2)})

同样论证: 其公共坐标属于 0,1,2 时回到上一种情形; 否则其 5 个字符串也在坐标 3 取 b. 此时 S(w^{(2)}) 中恰有 3 个字符串在坐标 0,1,2 取 b^\vee, 它们与 S(w^{(1)}) 都在坐标 3 的切片中, |S_{3,b}|\ge5+3=8; 其余三个字符切片各至少含两个字符串, 仍超过 12.

矛盾.

n\le3. 由五盒引理, 任何非平凡等价表示都会给出对某个字符串的不含孪生对的覆盖, 至少需要 5 个盒; 唯一的 5 字符串构型使用三个活动坐标且刚性. 故 n\le3 被排除.

综上, 反例不存在: m \ge 12.

\blacksquare

若 \mathbf K(D) 不成立, 由前述构造可得一个含 2^D 个字符串且不含孪生对的多盒码 S\subseteq\Xi^D.

因而对任意字符串 $w\in\Xi^D$, 盒 $B(w)$ 几乎处处被这些盒划分, 且 $$\sum_{v\in S}g(v,w)=2^D.$$ 以下称满足这一等式、含 $2^D

个字符串的码为分区码.

引理 G.9 (切片). 设 W\subseteq\Xi^D 是分区码, 第 i 列同时出现互补字符

$\sum_{a\in(W_{i,l})_{i^c}}g(a,u)=\sum_{b\in(W_{i,l^\vee})_{i^c}}g(b,u)$. 因而两个切片码 $(W_{i,l})_{i^c}$ 与 $(W_{i,l^\vee})_{i^c}$ 等价, 且 $|W_{i,l}|=|W_{i,l^\vee}|$. **证明.** 分别将分区等式用于字符串 $u\cdot l$ 与 $u\cdot l^\vee$, 即第 $i

坐标分别取 l,l^\vee, 其余坐标取 u. 第 i 个字符为 l 的字符串在前式中贡献 2g(v_{i^c},u), 在后式中贡献 0; 取 l^\vee 时则相反; 其余字符的贡献在两式中相同. 两式相减即得所述等式. 左码覆盖 u 当且仅当左和为 2^{D-1}, 因而所述等式也说明右码恰在此时覆盖 u, 故两码等价. 两侧都是若干两两不交、测度均为 2^{-(D-1)} 的盒之并, 所以大小也相等.

\blacksquare

引理 G.10 (互补封闭). 分区码 W 的任一列中, 每个出现的字符的互补字符也出现.

证明. 固定列 i 与其中出现的字符 l=(\sigma,b), 取 v\in W_{i,l} 及

$X'\in B(w)$ 对某个 $w\in W$ 成立; 又 $X'\notin B(v)$, 故 $w\ne v$. 因为 $W$ 是多盒码, $v,w$ 在某列 $j$ 呼应. 若 $j\ne i$, 则 $X'$ 在第 $j

列仍满足 v_j 的条件, 不能同时满足互补的 w_j 条件, 矛盾. 故 j=i, 从而 w_i=l^\vee.

\blacksquare

引理 G.11 (孪生判据). 设 W\subseteq\Xi^D 是含 2^D 个字符串的分区码. 若存在坐标

**证明.** 记这些互补字符对为 $\{l_j,l_j^\vee\}$. 由切片引理, 每对两侧大小相等, 故 $\sum_j|W_{i,l_j}|\le2^{D-1}$. 又 $k>2^{D-3}/3$, 有 $2^{D-1}/k<12$, 故存在 $j$ 使 $|W_{i,l_j}|\le11$. 若切片码 $(W_{i,l_j})_{i^c}$ 含孪生对 $u,v$, 则 $u\cdot l_j,v\cdot l_j\in W$ 仍只在同一个坐标不同, 是 $W$ 的孪生对. 否则两个切片码都不含孪生对, 它们等价且各至多有 $11$ 个字符串. 若它们不交, 等价码引理给出其大小至少为 $12$, 矛盾; 故有公共字符串 $u$. 于是 $u\cdot l_j,u\cdot l_j^\vee\in W$ 只在第 $i$ 坐标不同, 也是孪生对. $\blacksquare

定理 G.12. 对于 D\le5, \mathbf K(D) 成立.

证明. 反设 \mathbf K(D) 不成立. 由前述构造, 存在不含孪生对的 D 维分区码

由孪生判据的逆否命题, $k_i\le2^{D-3}/3\le4/3$, 故 $k_i\le1$. 互补封闭引理说明每列至少有一对互补字符, 因而每列恰有一对, 记作 $\{l_i,l_i^\vee\}$; 第 $i$ 列没有其他字符. 于是 $S\subseteq\{l_1,l_1^\vee\}\times\cdots\times\{l_D,l_D^\vee\}$. 右端恰有 $2^D$ 个字符串, 而 $|S|=2^D$, 故两者相等. 这个全集码含有 $l_1l_2\cdots l_D$ 与 $l_1^\vee l_2\cdots l_D$ 这一对孪生, 和 $S

不含孪生对矛盾.

\blacksquare

下面给出 Mackey 构造的 Keller 命题八维反例. 记 K_D 的顶点集为

$x_i-y_i\equiv2\pmod4$, 且 $x,y$ 至少在两个坐标不同. 因此, 只要 $K_8

中有一个大小为 2^8 的团, 就能构造八维 Keller 反例.

下表列出每个 x\in\mathbb Z_4^2 对应的四元素集合

$$\begin{array}{c|cccc} x&00&02&21&23\\ \hline F_x&\{0211,1132,2303,3020\}&\{2211,1130,0303,3022\}&\{1011,1331,3103,3223\}&\{1113,1323,3001,3231\} \end{array}$$ $$\begin{array}{c|cccc} x&12&10&33&31\\ \hline F_x&\{0000,0230,2112,2322\}&\{0102,0222,2010,2330\}&\{1210,3302,0023,2131\}&\{3210,1302,0021,2133\} \end{array}$$ $$\begin{array}{c|cccc} x&20&22&01&03\\ \hline F_x&\{0213,3132,2301,1020\}&\{2213,3130,0301,1022\}&\{3111,3321,1003,1233\}&\{3013,3333,1101,1221\} \end{array}$$ $$\begin{array}{c|cccc} x&32&30&13&11\\ \hline F_x&\{0012,0332,2100,2220\}&\{0110,0320,2002,2232\}&\{0131,2023,1212,3300\}&\{0133,2021,3212,1300\} \end{array}$$ 逐项核对这 $16$ 组长度为 $4$ 的字符串, 可得: 1. $x\ne y$ 时 $F_x\cap F_y=\varnothing$; 2. 每个 $F_x$ 是 $K_4$ 的团; 3. 若 $x,y$ 恰好只有一个坐标之差为 $2\pmod4$, 则任取 $u\in F_x$, $v\in F_y$, 总有某个坐标 $j$ 满足 $u_j-v_j\equiv2\pmod4$; 4. 对不同的 $x,y$, 任取 $u\in F_x$, $v\in F_y$, 除非 $$\begin{gathered} \{x,y\}\in E=\{\{00,02\},\{00,20\},\{02,22\},\{20,22\},\\ \{33,31\},\{33,13\},\{31,11\},\{13,11\}\}, \end{gathered}$$ 否则 $u,v$ 至少在两个坐标不同. 再取下面 $16$ 个长度为 $4$ 的字符串: $$W=\left\{ \begin{array}{cccc} 1032&1300&2320&3301\\ 1012&1120&0320&3303\\ 1212&3102&0100&3121\\ 1232&3322&2100&3123 \end{array} \right\}.$$ 将 $w\in W$ 写作 $w=xy$, 其中 $x=w_0w_1$, $y=w_2w_3$. 再核对这个 $4\times4$ 表可知: 对不同的 $w=xy,w'=x'y'$, $x,x'$ 或 $y,y'

中至少有一对恰好只有一个坐标之差为 2\pmod4. 此外, 若 x=x' 而

对 $w=xy$ 定义 $$C_w=F_x\times F_y=\{uv:u\in F_x,\ v\in F_y\}\subseteq\mathbb Z_4^8, \qquad C=\bigcup_{w\in W}C_w.$$ 每个 $C_w$ 有 $16$ 个元素, 且由 $F_x

两两不交知各 C_w 两两不交, 因而 |C|=16\cdot16=256.

任取不同的 p=uv,q=u'v'\in C. 若它们来自同一个 C_w, 只要一个长度为

4$ 的部分不同, 便可由相应 $F_x$ 或 $F_y$ 是团得到一个相差 $2\pmod4

的坐标. 若 p\in C_w,q\in C_{w'} 且 w\ne w', 上段中 x,x' 或 y,y' 的性质配合表的第三条, 同样给出一个相差 2\pmod4 的坐标.

再验证不同坐标数. 若 p,q\in C_w, 一个长度为 4 的部分不同则该部分至少有两个坐标不同; 两个部分都不同则各自至少贡献一个不同坐标. 若 w\ne w' 且

x\ne x',y\ne y'$, 两个部分分别至少贡献一个不同坐标. 剩下 $x=x',y\ne y'

的情形: 若 u\ne u', u,u' 同属 F_x 且至少在两个坐标不同; 若 u=u', 则 \{y,y'\}\notin E, 表的第四条给出 v,v' 至少在两个坐标不同. 交换

上述团可用来构造实际铺砌. 对 $c\in C,z\in\mathbb Z^8$, 令 $$Q_{c,z}=c+4z+[0,2)^8.$$ 任取两个不同的立方体. 若标签不同, 它们在某个坐标相差 $2\pmod4$, 故对应平移量在该坐标相差至少 $2$; 若标签相同, 则周期向量 $z$ 不同, 也有一个坐标的平移量相差至少 $4$. 两种情形下内部都不交. 在 $(\mathbb R/4\mathbb Z)^8$ 上, 这些立方体共有 $256$ 个, 总体积为 $256\cdot2^8=4^8$, 恰等于整个环面的体积, 故它们铺满环面; 周期延拓后得到 $\mathbb R^8$ 的铺砌. 若两个立方体共享一个完整七维面, 其平移量模 $4$ 后恰在一个坐标相差 $2$. 这与 $C$ 中任意两个字符串至少在两个坐标不同矛盾. 因而 $\mathbf K(8)

不成立.

注: 上述证明在码论框架下完成. D=6 时还需 David Applegate 给出的六维 Keller 图 60 团上界处理余下情形; D=7 时 \mathbf K(7) 仍成立, 若七维反例存在, 其中两个相关参数只能取 3,4,5. 四维中 Corrádi--Szabó 的

12$ 码字构造给出了最优下界; 八维反例是 Mackey 于 $2002

年给出的上述替换构造.