九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

非平凡 6-设计的小参数显式构造

《组合设计中的 50 个公开问题》 · 问题 03 专题综述

题面除 Teirlinck 1987 的突破性存在证明外,能否给出参数尽可能小的显式非平凡 6-设计(乃至更高 t)?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

非平凡的 t-设计指 λ>0 且块不是全部 k-子集的设计。1987 年 Teirlinck 证明:对每个 t 都存在非平凡 t-设计——结束了 «t≥6 是否存在» 的悬案。但他的构造参数巨大且高度非显式。本问题问:能否给出参数尽可能小的显式 6-设计?对标对象是设计理论的两颗明珠:小 Witt 设计 5-(12,6,1) 与大 Witt 设计 5-(24,8,1)——它们是 «最漂亮的参数+最大对称群» 的 5-设计,6-设计是否还有 «Witt 型» 的人间版本,是设计理论的浪漫悬案。

主要概念

整除算术为何在 t=6 变苛刻

01 号的计数恒等式在 t=6 要求六个整除条件同时成立,其中 i=5 的一条是 C(k−5,1) ∣ λ·C(v−5,1),即 k−5 ∣ λ(v−5)。想压小参数就得同时满足六条整除式而块数 b = λ·C(v,6)/C(k,6) 又不爆炸——Witt 设计恰是 «小参数+λ=1» 的唯一解族:5-(12,6,1) 有 b=132 块,5-(24,8,1) 有 b=759 块。λ=1 时六条整除同时成立对 6-设计几乎无解(已知的 6-(v,k,1) 只在 v 巨大时才有候选),故构造都从 λ>1 入手。

Teirlinck 递归的机制

Teirlinck 的构造是 «升阶»:从 t-设计造 (t+1)-设计。核心工具是 t-齐次、t-可逆的加权结构:在已知 t-设计上装备 «点权» 与 «块权»,使加权计数满足 (t+1) 阶整除,再用 «权分割» 把加权块拆成等权的普通块。整条链从平凡设计出发逐级抬升,参数随之指数膨胀——这就是 «存在但巨大» 的来源。

主要命题与证明

命题 1(大 Witt 设计与扩展 Golay 码,陈述+构造线索) 存在 5-(24,8,1) 设计:取扩展二元 Golay 码 [24,12,8] 的 759 个重量 8 码字作为块。其自同构群为魔群之外最大的散在群之一 M₂₄(阶约 2.4×10¹⁸),且每对块交于 0、2 或 4 点。

梗概 Golay 码可由 «横切» 十六元组 ⟨Ω∖{∞} 的循环结构⟩ 生成:生成矩阵的行由 {∞}∪F₂⁴ 的二次型结构给出;重量 8 码字共 759 = C(24,5)/C(8,5)·(1/1) 个,逐一验证五个定点能唯一延拓为码字(Golay 码的 «3-传递修补» 性质),即得 5-(24,8,1)。块对相交数的验证用码的对偶性与重量枚举多项式。□

命题 2(Teirlinck 定理,1987;陈述) 对每个 t ≥ 1 存在非平凡 t-(v,k,λ) 设计,其中 v,k,λ 均为 t 的(巨大的)显式函数。证明用 «权升阶» 归纳;构造的显式性在原则上成立、在实践上不可展开。

梗概 归纳步:给定加权 t-设计 (𝒟,w),构造 «t+1 可逆» 的加权结构——把点集复制成多个拷贝、用 t-设计的块作 «导轨» 分配权,使新结构对任何 (t+1)-子集的加权覆盖数恒等。随后 «去权»:把权 w 写成互不相同的 0-1 权之和(需 w 的值域受控),每个 «权层» 拆成普通块。整除条件由恒等式逐阶核验。□

命题 3(小参数的算术排除) 6-(v,k,1) 的六条整除条件在小参数强约束:例如 k≥7、λ=1 时 i=5 条给 k−5 ∣ v−5,i=4 条给 C(k−4,2) ∣ C(v−4,2),联立后 v 至少是 k−5 的倍数加 5 且远大于 k;已知 λ=1 的候选参数从 v≥某大界才开始,这解释了 «λ=1 的 6-设计为何无处可寻»。

说明 这不是存在性定理而是算术排除:它把 «小 Witt 型 6-设计» 的搜索空间压到几个参数窗口,正是显式构造攻坚的战场。□

进展与文献

Witt 1938 的两大设计;Teirlinck《Non-trivial t-designs without repeated blocks exist for all t》(1987);Magliveras–Leavitt 的 t=6 小型化尝试;Huber 对 t-设计与码、群关联的综述。开放核心:λ>1 的 «小» 6-设计(v 数千级)显式构造;6-设计的对称性普查(自同构群是否必然 «小»);Teirlinck 构造的参数改进——任何一档都是设计理论的一等成果。

← 返回问题 03