半群代数中的 50 个公开问题

数值半群 S（自然数的余有限加法子半群）中，设 c 为最大间隙 +1、g 为间隙个数、n 为小于 c 的元素个数——是否总有 n/g ≥ 1/2？

现状Wilf 1977 年提出，是数值半群论的头号猜想。已对对称半群、方次数小的半群等大类验证；Bras-Amorós 等把它化归为「单变量函数的最小化」，但一般情形未证。Wilf 本人的「快乐猜想」至今笑不出来。

亏格为 g 的数值半群个数 n_g 渐近于斐波那契增长（n_g+1/n_g → 黄金比）？

现状2007 年提出。已知 n_g 单调不减（Bras-Amorós）、有指数下界构造；Zhai 证明了「对称半群占总数的比例趋于 0」等结构性结果，但黄金比极限本身未证。它与奇异曲线的模空间计数（Arf 半群与代数几何的接口）相连。

两个生成元的 Frobenius 数有拉马努金式的封闭公式；三个生成元有（算法式）表达式；四个及以上生成元是否存在任何「可用的显式公式」？

现状计算任意个数生成元的 Frobenius 数已知 NP-难（Ramírez Alfonsín），这解释了「没有好公式」的期待方向；但「NP-难 ≠ 没有显式表达式」，是否存在（哪怕超多项式长度但结构清晰的）公式谱仍是开放讨论。固定生成元个数的公式（Curtis 的「无闭式」定理的精确含义）持续争论。

数值半群的哪些间隙是「孤立的」（相邻两侧都是半群元素）？孤立间隙的个数与分布有公式吗？

现状Bras-Amorós–Serrano 系统研究后的基本问题：孤立间隙与半群的两元素生成性、对称性都有耦合；「最多有多少个孤立间隙」这类初等量都没有答案。

type（间隙的极小生成数）为 2 的数值半群（准对称半群）有丰富的对称结构；type 与其它不变量（亏格、跨度、Wilf 函数）的完整关系谱？

现状type 1（对称）与 type 2（准对称）已较成熟；type ≥3 的半群「野性」依旧——连「给定亏格与 type 的半群个数」的公式都没有。type 的极值问题（最大 type）只对部分亏格知道。

哪些数值半群给出完全交的半群环（k[S] 的完全交性）？ Kunz 坐标的判据如何系统化？

现状Herzog 与 Kunz 的经典工作给出对称性 ⇔ Gorenstein 的桥梁；完全交情形有生成元数的递归刻画，但「完全交数值半群按亏格的枚举公式」（及与 02 号计数的耦合）未完成。

Arf 半群（封闭于「对任意元素取商后仍封闭」）按亏格的枚举与树结构刻画。

现状Arf 半群与单变量奇点的代数几何（皮亚泰茨基–夏皮罗奇点）相连；其枚举已知有斐波那契型结构（比 02 号更精确），但「Arf 占全体数值半群的比例」及枚举的封闭公式未得。

随机取 k 个生成元时，Frobenius 数与亏格的期望值和分布？

现状Arnol'd 1989 年的渐近（固定 k、生成元取自大范围）给出期望的 n^1−1/k 型主项；分布的精细形状（方差、极限律）及「固定生成元范围、k→∞」的对偶情形未完成。

原子独异点中，因子分解长度的弹性（最大长/最小长之比的极限）能取哪些值？数值半群情形的显式公式？

现状Geroldinger–Halter-Koch 的因子分解理论给出 C-独异点框架；数值半群的弹性有显式公式（跨度函数），但「一般仿射半群的弹性谱」「长度集合的完整实现问题」未解决。

计算数值半群的 Betti 元素（原子分解关系的极小生成）是 NP-难吗？其个数有没有好的上界？

现状已知部分决策问题 NP-难（覆盖问题归约），但「Betti 元素个数」的上界猜想（如关于生成元数与亏格的多项式界）未证；分解理论（Chapman 等的研究纲领）仍在积累。

由「一个词 = 一个词」定义的独异点是否总能嵌入群（即其消去化自由）？

现状带左循环的情形可嵌入（Adian–Lallement–Preston）；一般情形目前既无证明也无反例。这是半群论与群论之间最著名的桥梁问题（对比：群论侧的「一关系群嵌入群」由 Adian 解决）。

只有一个定义关系的半群，其字问题是否可判定？

现状组合半群论的头号悬案。已知：一关系独异点带左循环可判定（Adian）、一关系群可判定；一般情形自 Markov–Post 时代以来无实质推进。「半群的不可判定性从几个关系开始」是精确的开放谱。

给定一个有限半群，判定其等式理论是否有有限公理基——这个问题本身可判定吗？

现状一般泛代数中不可判定（Murskii 型结果）；对半群这一特类，可判定与否未决。已知存在无有限基的有限半群（事件的六元素反例），但「判定的算法」问题整层开放。

自然数（+,·,^）的全部恒等式能否由中学代数的十一条公理推出？

现状Gurevič 1985 证明中学代数公理不完备（存在真恒等式不可推出），并证明其理论非有限公理化；「完整的（无限）公理化」与「该理论的判定算法」仍开。这是「指运算的野性」给出的深刻结论。

给定一个词模式（如 xx、xyxyx），判定它是否可在某个有限字母表上被无限词避开——这个问题可判定吗？

现状Bean–Ehrenfeucht–McNulty 与 Zimin 的「Zimin 词不可避」定理是基石；一般模式的可避性判定问题（Casazza 型清单）仍是词组合学的头号算法问题。已知大量单族结果，无统一判定。

在 k 字母表上，无限词能避免的最小重复指数的阿贝尔版本（相邻因子在排列意义下相同即算重复）——精确阈值是多少？

现状Dejean 猜想（普通重复阈值）已于 2009 年前后完全解决；其阿贝尔版只对部分字母表数确定或近似，一般情形连「阈值是否为有理数」都未明。它是词组合学在 Dejean 之后的主战场。

每个有限极大码（自由独异点的极大前缀码）都可通过「因子分解」从某个群码导出。

现状Schützenberger 1970 年代提出，是码论的中央猜想；Reutenauer 等给出大量支持结果（对称群码的情形），一般情形与「码的群结构定理」纠缠。连「验证一个码可分解」的算法都难。

Cobham 定理（两个乘法无关基数识别的语言恰为正则语言）能否推广到「非标准数系」（Fibonacci 进制、Pisot 进制等）的统一刻画？

现状Durand 等证明「两个乘法无关的 Pisot 数系」版本（2010 年代的重大推进）；一般「抽象数系」的公理化 Cobham 理论仍在搭建。这是自动机理论与数论的黄金接口。

周期半群（每个元素有幂相等）何时局部有限？「有限生成 + 周期 + 无自由子半群 ⇒ 局部有限？」

现状Shevrin–Volkov 纲领给出周期半群的「理想塔」结构；局部有限性的完整判据（对比群论侧 Zelmanov 的深刻定理）未得。「无自由子半群」类条件的精确力量是半群伯恩赛德问题的残部（与群论分册 40 号呼应）。

一个词的非平凡因子们生成自由独异点时的「亏格」关系（defect 定理）——定量版（多少个独立因子能生成多长的词）的精确界？

现状defect 定理（Lothaire 系）是组合词论的基础工具；其「最优常数」版本（Fine–Wilf 型的精细边值）对特殊词类已知，一般词类的精确常数（如 Fine–Wilf 界的最优性已证，但双变量推广未完）仍在打磨。

任何 n-状态同步化自动机都有长度 ≤ (n−1)² 的同步词。

现状Černý 1964 年提出，自动机理论最著名的猜想。已知界：三次方级（Pin 的 O(n³+n²)）与Černý 自动机本身达到 (n−1)²；「二次界」五十年未证，相关工作延伸到 road coloring（已解）与部分自动机（见 29 号）。

给定一个有限半群，其 Krohn–Rhodes 复杂度（群式分解的层数）可计算吗？

现状Krohn–Rhodes 主定理（1965）保证分解存在；但「给定半群的精确复杂度计算」连可判定性都未证（复杂度 ≤k 的判定问题对每个固定 k 的可判定性亦开）。这是理论计算机科学与代数的接口大题。

阶 n 的半群个数（同构计）的主渐近项是什么？

现状Distler 等已枚举到 n=10（阶 9 有约 5.99 亿个）；群论侧（p-群计数）有 Higman 渐近，半群侧连主导项的形式都无猜想。计算机枚举每进一阶都是工程壮举。

伪簇 V 的「点态集」（V-点态可分性）何时可判定？——Henckell 解决了 J，R、DA 等的完整可判定谱？

现状Henckell 1988 的 J-点态集定理是「有限半群论的深度定理」；后续（Place–Zeitoun 等）解决了若干伪簇，但整个伪簇格上的「可判定地图」远未画完。它与电路复杂度（AC⁰ 的代数刻画）直接挂钩。

星高度层级中，dot-depth 2（二阶多项式星表达式）对应的语言类可判定吗？

现状dot-depth 1 已由 Knast 可判定（1980s）；dot-depth 2 的可判定性是 Eilenberg 纲领四十年未决的头号空白，「Straubing–Thérien 层级」的逐层可判定是正则语言理论的主攻线。

广义正则表达式（补运算自由使用）的星高能否有界？「广义星高 = 1」的语言类刻画？

现状经典星高问题（有限补）已由 Hashiguchi、Kirsten 解决；广义星高问题（Brzozowski 1962 提出）完全开放——连「广义星高超过 1 的语言是否存在」都没人知道。这是「星运算的真实威力」的根本问题。

部分自动机（转移函数可未定义）的同步化问题：正确的二次界常数是什么？

现状完全自动机的 Černý 猜想（21 号）之外，部分自动机已知的指数级界与经验二次现象之间的落差更大；「careful 同步化」的可判定性（对固定 n）与「最短 careful 词」的界都开。

达到同步化长度上界的自动机（Černý 自动机及「准 Černý」族）之外，极端族的完全分类？

现状已知几个达到 (n−1)² 或接近的族（Černý、Kari、Roman 等）；「这些就是全部吗」的枚举式分类未完成——它与 21 号互为表里（若 Černý 猜想真，极端族即「等号族」）。

全变换独异点 T_n 的子半群的秩、生成效率与「万有性」（哪些子半群生成 T_n）的完整刻画？

现状Howie 时代的经典结果给出大量生成对/生成三元组；「极小生成集的谱」「随机生成 T_n 的阈值」等统计问题近年才展开。变换半群是「有限半群的万有容器」，其内部地理远未绘制完。

哪些有限半群可作为「可逆元胞自动机的转移半群」的子半群？（自动机半群的剩余有限性、可判定性谱）

现状自动机群（Mealy 机群）与自动机半群的理论自 2000 年代成型；「每个自动机半群都剩余有限吗」「自动机半群类对取子半群封闭吗」都是 Kourovka 型的开放问题。它与可计算性（元胞自动机的不可判定谱）互锁。

哪些（有限）格可以成为某个（有限）逆半群的合同格？

现状半群方面：每个有限格都是某有限半群的合同格（Freese–Nation 时代的构造）；逆半群侧的对应实现问题未解——模性/分配性的边界在哪里是关键障碍。逆半群（对称逆独异点）是「带部分对称的代数」，其合同理论与群论差异巨大。

阶 11、12 的半群（独异点、群）能否完全枚举？（23 号的实验侧）

现状半群计数枚举依赖 GAP Semigroups 库的等价类剪枝；阶 10 用了数年计算。阶 11 的枚举需要新的对称性利用或 SAT/约束求解技术，是「计算代数的下一座山」。

哪些偏序集可作为半群（独异点）的理想格？

现状合同格问题（31 号）的「理想版」更松：已知每个有限格可实现为某半群的理想格? 部分结果；「带单位的版本」「逆半群版本」以及与格的代数不变量的匹配未完成。

McAlister 的 P-定理（E-单式逆半群 = 群上的半格覆盖）之后，「E-稠密半群」的相应结构定理？

现状P-定理是逆半群论的珠峰；其向 E-稠密半群（更弱的正则性）的推广有多个候选框架（Lawson 的非正则半群理论），统一的结构定理未立。「正则之外」的半群结构论整体处于「局部定理多、全局理论少」的状态。

每个群都可作独异点的单位群；「极小阶」「极小生成关系」的单位群实现谱？

现状平凡构造（群上加零元）给出巨大上界；「阶 n 的群作为阶 m 独异点的单位群，m 最小是多少」这类定量问题对一般群未解。它与「补格」（半群的幺化扩张）的组合问题耦合。

半群扩张的（Lausch 或 Grillet 型）上同调理论能否像群上同调那样给出扩张的分类定理？

现状群上同调（Schreier 定理：扩张 ⇔ 二阶上同调）是教科书内容；半群的对应理论多个版本并存、互相不等价，且「哪个版本给出完整分类」未明。这是「半群比群缺什么」的代数诊断书。

带（幂等半群）的簇格与「格的重构」（由有限成员决定整个簇）问题：哪些簇由有限个有限带公理化？

现状带的簇格结构（Fennemore、Gerhard 定理）是半群论少数「完整地图」；但「公理基的有限性」「格的自同构群」等精细问题仍开。它与 13 号有限基问题共享地平线。

双单（bisimple）逆半群由其「最大群像」与幂等结构决定到什么程度？双单逆半群的分类不变量谱？

现状Rees 矩阵半群给出完全 0-单半群的完整结构（经典）；「无双单正则半群的可分性」由 Rees–Suschkewitsch 的矩阵型结构处理，但「双单 + 逆」的精细分类远未完成。它与 C*-代数的 AFS 理论（逆半群的算子代数实现）共振。

哪些自然数子集可作为某个原子独异点的「因子分解长度集」？

现状Geroldinger 纲领：已知大量「结构定理」（Krull 独异点的长度集是殆算术级数的并），但「实现方向」（给定集合找独异点）与「殆算术结构的必要性」未合流。这是唯一分解失败的「代数病理学」。

原子独异点的 set of distances、catenary degree、ω-不变量之间的完整不等式网络？

现状Chapman–Geroldinger 等定义了若干不变量并证明两两间的部分不等式；「哪些不等式是最优的」「不变量的代数刻画（何时可计算）」未完成。数值半群上这些不变量可显式算出——一般 C-独异点则不可。

有限集 A 的幂集在「并/交/子集幂运算」下生成的独异点的原子结构与 Frobenius 型问题。

现状「Power monoids」（Fan 等近年开辟）连接集合论与因子分解；其原子分解的周期性、弹性与数值半群版本的对应刚起步。这是半群算术的新边疆。

q-rook 独异点、Catalan 独异点等「组合变换独异点」的不可约表示的统一分类？

现状变换独异点的表示论（Solomon、Putcha 系）在「正则独异点」上有完整框架；「非正则组合独异点」（如 Catalan、自由带）的表示分类零星。与 Schur–Weyl 对偶的独异点版（q-rook 对偶）的推广未完成。

正则半群的自然偏序（幂等序的延拓）何时是格？哪些偏序可作为正则半群的自然偏序？

现状Nambooripad 偏序是正则半群论的基础结构；「偏序的格性判据」「逆半群情形（偏序恒为格？否）的精确边界」等基本问题仍开。它与 31 号合同格问题共享「格 vs 半群」的地形。

有限生成半群的增长函数（与群论平行的球面增长率）的分类：多项式、指数与中间增长的完整谱？

现状群论侧有 Wolf–Gromov 定理与 Grigorchuk 构造；半群侧只有零星结果——「多项式增长半群的分类」这一最基本问题都未完成（正则情形已知）。半群的增长理论整体落后群论二十年。

有限半群的全称理论（∀-句子）可判定吗？（与有限群的可判定性对比）

现状有限群的一阶理论可判定；有限半群的理论（即使全称片段）可判定性未明。它与 22、24 号（Krohn–Rhodes、点态集）同属「有限半群的可计算性地图」的空白格。

复杂度 k 与 k+1 的半群都存在（层级严格）——对每个 k 显式给出? 层级的「渐近行为」？

现状Krohn–Rhodes 复杂度的层级严格性已知（构造存在），但「显式小例子」「复杂度与状态数的定量关系」（Henckell–Rhodes 型下界）未完成。它与 22 号（可计算性）共同构成 Krohn–Rhodes 理论的两大残余。

给定独异点的呈现，判定它是否有有限收敛（完备项重写）呈现——可判定吗？

现状项重写理论的「完备化问题」：Knuth–Bendix 补全是半算法；「是否存在可判定判据」「收敛呈现存在 ⇔ 什么代数性质」都开。它与格罗布纳基理论（交换情形完备）的非交换推广直接相关。

哪些（独异点/半群）是自动的（同步双自动结构）？「自动 + 交换? 」「自动半群的子半群自动吗？」

现状群论侧：自动群理论成熟（双曲群皆自动）；半群侧（Campbell–Robertson–Ruškuc 等开创）：「子半群不保持自动性」已证，正则情形有刻画，一般判据未得。「Rees 乘积、自由积的自动性保持谱」等基本问题开。

半群（作为度规空间）的粗几何：哪些粗不变量（端数、边界、增长）可定义且有用？

现状群的粗几何是 21 世纪数学的主干；半群的粗几何（Kilibarda 等的开端）刚起步——连「半群的端数定理」（群的 Freudenthal–Hopf 对应）的类似物都未建立。「半群几何化」是名副其实的新大陆。

终极问题：有限半群论（Eilenberg 纲领）与无限半群论能否像群论那样（有限/无限由线性表示桥接）建立统一框架？——「有限半群的可判定理论」与「无限半群的结构理论」之间的桥在哪？

现状群论有线性表示作为桥梁；半群缺少等价工具（变换表示太弱、矩阵表示不完整）。Krohn–Rhodes 分解、Rees 结构、吸收法等「半成品桥梁」能否拼成统一理论，是本世纪的开放赌注。