组合设计中的 50 个公开问题

给定参数 (v,k,λ)（t 设计），除整除性等显然必要条件外，何时精确存在？——Wilson 与 Keevash 给出「充分大 v」的渐近答案，有限情形的完整判据呢？

现状对 2-(v,3,1)（Steiner 三元系）等已完全刻画（柯克曼条件）；一般 (t,k,λ) 的有限判据仍靠计算机逐族攻坚。Keevash 定理的「充分大」阈值大到无法显式，把判据变成算法是当前工程。

Keevash 2014 证明「满足整除条件且 v 充分大则 t 设计存在」——能否给出有效的 v 阈值与多项式时间的构造算法？

现状原证明是「随机化+吸收」的存在性论证；Glock–Kühn–Lo–Osthus 的「迭代吸收」给出更好的阈值但仍是纯存在性。显式构造（哪怕对 t=4,5）都是大新闻。

除 Teirlinck 1987 的突破性存在证明外，能否给出参数尽可能小的显式非平凡 6-设计（乃至更高 t）？

现状Teirlinck 的构造参数巨大且高度非显式；最大的「漂亮」设计仍是 5-(12,6,1) 大 Witt 设计与 5-(24,8,1) 大 Witt 设计。6-设计的「Witt 型明珠」是否还有人间的版本，是设计理论的浪漫悬案。

强度 t、正交阵列 OA(λs^t, n, s, t) 何时达到 Rao 界？达到界的阵列的分类？

现状Rao 界与编码的 LP 界同源；达到界情形与纠错码（MDS 码、紧框架）等价的部分已知，一般情形的谱未完成。「Rao 界的紧性」是正交阵列理论的脊柱问题。

球面上存在 t-设计（对次数 ≤t 的多项式精确求积）所需的最少点数是多少？渐近常数能否锁定？

现状Corens–McLaren 型下界与 Bondarenko–Radchenko–Viazovska（2010 年代的突破：点数 ~ t² 级）之间存在常数鸿沟；「最优球面设计的显式小构造」也开（与 29 号 SIC 问题呼应）。

用 k 元组盖住所有 t 元组，最少需要多少块？对给定剩余类（如 n mod 6 时的 C(n,4,3)）精确值？

现状渐近已由 Rödl 定理（爱尔德什–哈纳尼猜想）解决；精确值只在部分同余类确定（Schönheim 下界与构造之间的缺口）。《覆盖设计手册》厚达千页仍填不满。

把 5 元组的最小集合使每个 4 元组被盖住——T(n,5,4) 的精确渐近常数？

现状与 Turán (3,4) 问题（见《图论》分册 07 号）同为「超图图兰」的圣杯；图兰本人给出的构造至今未被击败，其最优性五十年未证。

阶 12 的射影平面是否存在？

现状Bruck–Ryser–Chowla 定理只排除 n≡1,2 (mod 4) 且非平方和的情形——12 恰好躲开。10 阶平面的不存在曾靠 Cray 巨型机 + Lam 团队多年计算（1989）；12 阶的搜索空间比 10 阶大数十个量级，是「计算数学的下一个登月」。

是否存在阶非素数幂的有限射影平面？

现状所有已知平面（包括全部四个 9 阶平面）阶为素数幂；Bruck–Ryser 只给部分否定。若答案为「否」，则需要全新的构造思想（有限几何之外的非坐标手法）。

每个素数幂阶 pⁿ 的射影平面个数是多少？9 阶恰有 4 个（1 笛沙格 + 3 非笛沙格）；16 阶已知 22 个；一般阶的完整清单？

现状16 阶的完整分类（22 个）是计算机时代的里程碑；25 阶已知 193 个？未完成。一般阶连「数量是否为 pⁿ 的多项式」都不知道。

有限极空间的卵形集（每条线至多交 2 点）何时存在、何时是椭圆二次曲面？

现状Barlotti–Panella 分类定理覆盖多数情形，特征 2 的例外（超卵形、Segre–Tallini）仍在攻；「极空间的卵形完全分类」是有限几何的持续工程。

哪些参数的 t-设计可分解为平行类（如柯克曼三元系之于 STS）？t≥3 的可解性判据？

现状t=2 已由 Ray-Chaudhuri–Wilson（1971，可解 BIBD）与 Keevash 解决渐近；t≥3 的可解版连渐近都只有部分（Keevash 的方法对可解情形需额外假设）。「柯克曼的 15 女儿」之后五十年，推广仍在路上。

t-(n,k,λ)_q 子空间设计（向量空间的子空间版设计）在满足整除条件时是否存在？

现状q-模拟的存在理论远落后于经典：零星构造（Suzuki 群给出的 2-设计等）之外没有一般存在定理；「Keevash 的 q-版本」是当前活跃的攻坚方向（Kühn–Ley–Osthus 等）。

每个 4n 阶 Hadamard 矩阵（±1 矩阵行两两正交）都存在。

现状1893 年提出。已知最小未定阶是 668（此前 428 于 2005 年解决）。构造手段（Paley 型、Williamson 型、合痕法）各有覆盖域，但「每 4 的倍数」仍遥不可及——它是组合设计里最古老的总攻目标。

循环 Hadamard 矩阵只有 4 阶一种。

现状Ryser 1963 年提出。已知阶必为 4u² 型（Schmidt 的谱方法大幅排除）；对巨大范围已用计算机排除，但一般证明需要新的谱/数论工具。循环差集与其等价。

循环差集 (v,k,λ)（k(k−1)=λ(v−1) 的「完美分度」子集）何时存在？乘子定理之外还有什么必要条件？

现状Bruck–Ryser–Chowla 与乘子定理给出两翼；两翼之间大量参数组既无构造也无排除。「差集地图」至今是设计理论最密集的未定区域。

满足整除条件的哪些 n 允许循环（平移不变）的四元系？

现状循环 STS(2,3,n) 已完全刻画（Pelteson）；3 元以上循环系的判据残缺，大量整除可行的 n 既无构造也无否定。循环性把设计钉在群论（正规循环自同构）上，两侧的工具都未合流。

完全图 K_2n 的完美 1-因子分解（任何两个因子的并是哈密顿圈）对每个 n 都存在。

现状Kotzig 1964 年提出；已证到数百阶（含全部素数幂 ±1 的部分构造）。它是「把组合设计翻译成群论陪集分解」的样板问题，与 Room 方、扫描设计交织。

每个奇数阶拉丁方都有一条完整横截（每行每列每符号各取一次）。

现状Ryser 1967 年提出。偶数阶有反例（如某 4 阶方）；奇数阶连「有 n−O(log n) 长的部分横截」都已是重量级结果（Keevash 等），最后一步未跨。它与偶数阶的 n−1 猜想（Brualdi–Stein，同样未证）构成拉丁方理论的双子星。

每个拉丁方都有一条长度 n−1 的部分横截。

现状最好下界是 n−O((log n)²/log log n) 型（多次改进），与 n−1 之间还剩一个「缓慢项」；19 号与 20 号若同时获证将统一为「拉丁方横截定理」。Polymath 曾组织攻坚未果。

偶数阶拉丁方中，偶标号与奇标号（行列置换的符号）的个数不等（差非零）。

现状1990 年提出。它蕴含「列表染色版本的 Galvin 定理推广」与组合零点定理的一族推论；目前只对部分阶（素数、某些合数）与少数函数类验证。整数流与组合代数的方法都在尝试。

ℂ⁶ 中最多有几组两两不正交基（MUB）？素数幂维数必有 d+1 组；6=2×3 非素数幂，已知至少 2 组、至多 3 组——是 2 还是 3？

现状这是「合数维数 MUB 谱」的旗舰：d=6 争议二十余年，数值与结构证据双向拉锯。它同时是量子信息（量子态层析）的实用问题——「到底 2 还是 3」至今无裁决。

每个维数 d 都存在 SIC-POVM：d² 个等长向量两两内积模长恰为 1/√(d+1)（最对称的量子态设计）。

现状Zauner 1999 年博士论文提出。已数值验证到 d≈100+，严格证明到 d≤21 及若干无穷族（Scott–Grassl 谱系）。SIC 与球面设计、数论（Hecke 特征形式）出人意料的联系是近年最大惊喜之一。

哪些正交阵列等价于「量子态设计」或「纠缠态的完备测量」？OA 的强度与量子不可区分度的精确对应？

现状量子 t-设计（态设计）与经典 OA 的对应部分建立（Gross–Audenaert–Eisert）；「量子 t-设计所需最小态数」的显式谱（与 5 号球面设计、23 号 SIC 三线合围）未完成。

双色 [1,W] 中必含长 7 等差数列的最小 W？已知 W(2,6)=1132。

现状W(2,6)=1132（Kouril 2008，SAT+对称性剪枝的壮举）之后，W(2,7) 的下界 ~3703 与上界数十万之间是纯算力鸿沟；一般 W(2,k) 增长的指数常数（Graham 型：2^k 对 2^k²？）同样是百年之争。

三色情形的长 5 等差数列阈值？已知 W(3,4)=293。

现状W(3,5) 下界 ~1700、上界 ~万级；多色范德瓦尔登数整个谱系（除极小值）都未确定。「可计算但算不动」是这一族的共同命运。

最小 N 使 [1,N] 的 6-染色必含单色 x+y=z？已知 S(5)=160。

现状S(5)=160（Heule 2017，SAT 求解器万核月余）后 S(6) 下界 536 与指数上界之间；「舒尔数与拉姆齐数的指数关系」同样开。SAT 工具链是这一族的当代引擎。

R(4,4,4) 已知在 51 与 62 之间（与图论分册 04 号 R₄(3) 同区间——纯巧合的数值对望）。

现状下界 51（1974）、上界 62（Radziszowski–Xu）四十余年未动。多色拉姆齐数谱系（R(3,3,4)、R(3,4,4) 等部分确定）中 R(4,4,4) 是下一位主角。

最小 N 使 [3]^N（3 字母、N 维网格）的任意 3-染色必含单色组合线？

现状Hales–Jewett 定理（1963）保证存在；HJ(2,n) 与 HJ(3,2) 等小值已算，HJ(3,3) 及以上完全开。Polymath 曾攻 tic-tac-toe 型相关数（HJ(2,6) 等）；「HJ 数的增长」与 Graham 数比肩。

𝔽₃ⁿ 中无 3-项等差数列的子集最大多大？Ellenberg–Gijswijt 给出 (2.756)ⁿ 上界、构造给出约 2.2ⁿ——精确底数？

现状2016 年的多项式方法突破是十年来加法组合最大的单点进展；「2.756 是否可再压」「下界能否抬到 2.756 附近」都开。cap set 猜想（原「多项式级」）已被否定，剩下的常数之战刚开场。

有限的并闭集族（族中任两集之并仍在族中）必有一元素出现在至少一半的集合里。

现状1979 年提出、Polymath1 攻坚未果。最好下界约 0.613（熵+递归法），距 1/2 的对面还差 0.11+；若真，最简证明也许藏在交换代数（Stanley 深度方法）里。

存在 c>1 使任何多于 c^k 个 k 元集合的族必含太阳花（两两交相同的 k 元「花芯」结构）。Erdős–Rado 的 k⁵˙ᵏ 上界能否压到指数？

现状Polymath10（2016）把 c 压到约 3.6（对足够大的 k），距猜想要求的「常数 >1 即可」仍差关键一步；c 若真存在将瞬间改进复杂性理论的 many lower bounds（AC⁰ 等）。

对每个有限域 𝔽_q，不可在 𝔽_q 上表示的拟阵只有有限多个极小禁例。

现状Geelen–Gerards–Whittle 的「拟阵极小结构理论」（对应图子式理论的拟阵版）在推进中，二域 GF(2) 情形已基本解决（Bixby–Cunningham 时代起）；一般素数幂的特征谱仍未合龙。「图子式定理的拟阵版」是本世纪结构图论最大的工程。

相对距离 δ 固定时，二元码的最大码率 R(δ) 的精确值？Gilbert–Varshamov 下界与 Hamming/LP 上界之间的「缺口」能否合龙？

现状这是编码理论六十年的「天际线问题」：MRRW（LP）上界与 GV 下界在 δ≈0.3 附近的 gap 尚无一流形工具能合上；2010 年代 Jiang–Vardy 型改进只是微雕。极性码（Arikan）的成功反而突显了 R(δ) 本体的未知。

除平凡与少数已知（Golay 的 Lee 版）外，是否存在其他 Lee 度量完美码？

现状Tietäväinen–van Lint 完成了汉明度量的分类（Hamming/Golay 之外无）；Lee 度量的对应分类残缺，「非线性的 Lee 完美码」是否存在是码论的持久缺口。

非平凡 MDS 码的长度 ≤ q+1（除偶 q 的 k=3/q−1 例外）——Segre 时代起的部分结果之外，一般 q（合数、非素数幂）的完全证明？

现状Simeon Ball 等对素数 q 与多数偶 q 已证（2010 年代）；合数域与非素数幂 q 的残余情形未合龙。MDS 猜想等价于「有限几何中弧（arc）的极大谱」，与 11 号卵形问题互锁。

2-(n,3,1) 的大集合（不相交铺满全部三元组）已由陆家羲–Teirlinck 解决；3-(n,4,1)（Steiner 四元系）的大集合存在吗？

现状陆家羲 1980 年代解决大集合 LS(2,3,n) 是中国组合数学的世纪成就；t≥3 的「大集合谱」几乎空白（只有零星 n）。这是以中国人命名的问题谱系的延续。

哪些「结合方案」（Bose–Mesner 代数）存在？Bannai–Ito 猜想：本质非平凡方案只有有限多个（固定秩 2 矩阵代数维数）？

现状「Bannai–Ito 纲领」（用结合方案的否定性替换存在性证明）在 Hamming/Johnson 等方案上成功；一般分类远未完成。它与代数图论的 Lovász–Spectra 工具箱共享地基。

除小 Witt（5-(12,6,1)）、大 Witt（5-(24,8,1)）及其子系外，是否还存在其他「参数漂亮、自同构群巨大」的零星 t-设计？

现状零星单群（魔群月光）与设计的纠缠是 20 世纪数学的高光；「零星设计是否已穷尽」没有理论答案。每次新的大设计（如 2000 年代的 5-(48,12,λ) 探索）都牵动群论。

Keevash 2018 证明固定 (t,k,λ) 下设计个数的主项渐近；次项、误差项与「随机设计的分布性质」（如自同构群几乎平凡）能否精确？

现状主项公式（熵型）已立；「典型设计是什么样」（如规范型、局部结构）的统计力学视角刚起步。「计数之后」的分布理论是设计理论的新大陆。

对有限集 A，|A+A|+|A·A| ≥ |A|^2−ε(n)（ε→0）——Erdős–Szemerédi 1983 的猜想。

现状Solymosi 的 n^4/3 与后续多项式方法（Shkredov 等）逐步抬升指数；实数情形最好约 n^4/3+o(1)，距 2 仍远。素域情形与 cap set（30 号）共享多项式工具箱。

若 A 是 ℤ 的渐进加法基（每个大整数可写成 a+a′），则表示函数不可有界。

现状1941 年提出，加法数论最著名的老题之一；所有已知「薄基」构造的表示函数都无界增长，但「无界是必然」五十年未证。Sárközy–Szemerédi 证明「平均意义下无界」的弱版。

k 种面额、每信封至多 h 张邮票时，可连续覆盖的最大整数 n(h,k) 的渐近常数？

现状固定 k、h→∞ 的主项（Frobenius 型）已知，渐近常数（Stöhr 型 c_k 的存在性与显式值）只有 k≤3 确定并可加推广；一般 k 的「邮票常数」是数值半群理论的门面问题（与《半群》分册联动）。

ℤ/nℤ（或 [1,n]）中最大的「无 3-项等差」子集、最大的「无平方和」子集等的精确常数（弱版：渐近公式）。

现状Cap set 的突破（30 号）示范了多项式方法的威力；整数情形（Roth 定理的定量常数）的最优界仍是未定战场。Behrend 型下界 70 余年未被实质超越，是加法组合最著名的「上下界夹心」。

Wilson 的「基本构造」（从已知设计拼出新设计）能否升级为「按群作用分类所有设计」的系统理论（类似有限单群的分类哲学）？

现状Wilson 纲领、乘子定理、群构造（1-因子、差集）各自为政；「设计理论的 CFSG」——按自同构群把设计世界切分——只有零星（高对称设计普查）。

可解（柯克曼型）设计的显式构造与计数：给定的 (v,k,λ) 可解设计的个数有公式吗？

现状存在性渐近已入 Keevash 框架；显式构造与计数（Kirkman 系统的个数公式）远未完成。「从柯克曼到 Keevash」的这条线是设计教育与现代理论的最佳桥梁。

Room 方（对偶 1-因子分解）与 Howell 设计的参数谱何时存在？

现状存在性判据覆盖多数同余类，剩余类与「极小 Room 方」未合流。它是「将球赛循环赛表数学化」的实用理论，工程意义大而理论缺口清晰。

给定可满足的参数，构造一个设计需要多少时间？「设计构造 ∈ P 吗」（一般 (t,k,λ)）？

现状STS 有多项式构造；一般 t-设计的显式构造算法（吸收法能否算效化）未证——与 02 号互为表里。「存在性定理的算法化」是组合学对计算复杂性理论的输出接口。

大设计 ↔ 大单群（Witt ↔ Mathieu、魔 ↔ 月光）的对应是「冰山一角」还是「全部」？设计-群对应的系统性理论？

现状零星对应表（Mathieu 群、Higman–Sims、Conway 群等）四十年来零星增加；「为什么大设计总牵着大群」没有理论解释。这是设计理论最浪漫的开放前沿。

理想终点：给任何 (t,k,λ) 一张「存在 ⇔ 整除条件」的完整判据表（渐近已由 Keevash 保证，有限情形 01 号）——然后对每个可解变体（46 号）、循环变体（17 号）、q-变体（13 号）重复。这张总表可能在本世纪画出吗？

现状2-(v,3,1) 已完成；其余空白。整除条件远不充分的反例（如某些 (v,k,λ) 整除可解但无设计）显示「判据=整除」不会平凡成立——总表若有，将标志组合设计理论的成年。