← Combinatorics 主索引 · Template 2 v2 模板 · decision_log
Template 2 v2 流水线 · L1 sentinel 在数值层 1 小时内击毁 · $k=2$ 显式反例 + 多角度 case 分析失败诊断
原命题陈述:对任意 $\mathcal F\subseteq\binom{[n]}{k}$ sunflower-free 与任意 $i 结论:否。最小反例出现于 $n=4, k=2$,共 24 例;$n=5$ 共 660 例;$n=6$ 共 4680 例。本文档保留作为反面教材,并在 §5 给出可救的修订版本。
设 $[n]=\{1,2,\dots,n\}$,$\mathcal F\subseteq\binom{[n]}{k}$ 是 $k$-uniform 集族。
Sunflower($\Delta$-system,参数 $r$):$r$ 个集合 $A_1,\dots,A_r\in\mathcal F$ 称为一朵 $r$-sunflower,若存在公共核 $Y$ 使得
$$A_a\cap A_b = Y \quad\text{对所有 }a\neq b,\qquad A_a\setminus Y \text{ 两两不交(即"花瓣"互斥)}.$$
族 $\mathcal F$ 称为 $r$-sunflower-free 若不含任何 $r$-sunflower。本文统一取 $r=3$。
Frankl shift $S_{ij}$($i
$$S_{ij}(F)=\begin{cases}(F\setminus\{j\})\cup\{i\}, & j\in F,\ i\notin F,\ (F\setminus\{j\})\cup\{i\}\notin\mathcal F,\\ F, & \text{otherwise}.\end{cases}$$
$S_{ij}\mathcal F=\{S_{ij}(F):F\in\mathcal F\}$。这是组合极值学的标准工具:保 size $|S_{ij}\mathcal F|=|\mathcal F|$、保 uniformity,且迭代收敛到 shifted family(即 $j\in F\Rightarrow (F\setminus\{j\})\cup\{i\}\in\mathcal F$ 当 $i\notin F$)的不动点。
Sunflower 主问题(Erdős–Ko–Rado 1960 / Erdős–Rado 1960):找 $k$-uniform 不含 $r$-sunflower 的最大族 size $f(k,r)$。Erdős–Rado 给出 $f(k,r)\le (r-1)^k k!$;ALWZ 2020(Alweiss–Lovett–Wu–Zhang,arXiv:1908.08483)将上界推进到 $(\log k)^k(r\log\log k)^{O(k)}$,是 50 年最大跃迁。
P1 的设想:若能证 "Frankl shift 保 sunflower-free",则求 $f(k,r)$ 时只需在 shifted family 内搜索 — shifted family 有强结构(lex-initial-like),可能给出新 case-bash 上界,甚至链接到 ALWZ 的 entropy 框架。换言之 P1 是 lemma 候选:证之则 §13.6 / §13.7 的 main attack 全部依赖它。
Frankl shift 在文献中被反复证保 intersecting (Frankl 1995 Lemma 2.1)、$t$-intersecting、antichain (Engel 1997 Thm 8.1.4)、shadow size (Kruskal–Katona shifted 版本)、no-two-disjoint 等性质。Sunflower-free 是另一个"看起来局部"的性质,folklore 认为该保。本笔记将证明这种 folklore 在 $r=3$ 下错误。
L1 阶段并行启动 5 个 angle agents(详见 /tmp/sunflower_brainstorm/prop1/L1P1_*.md)。简评如下:
| 角度 | 路线 | L1 ranker 总分 / verdict | 实际命运 |
|---|---|---|---|
| A | 直接组合归纳 case-bash($|T|\in\{0,1,2,3\}$ 拆分) | 15 / strong(top-1) | 致命:Case 1 自称"闭合"实则漏掉 $A_1^*\notin\mathcal F$ 的子情形(见 §4.3) |
| B | SAT / 暴力枚举小 $n,k$ sunflower-free 族 + 跑 shift | 14 / promising | 救星:sentinel 直接调用,30 秒找出反例 |
| C | 归约到已知 shifting 不变量(intersecting / antichain / shadow) | 11 / weak | 预先认识到 sunflower 是 $r\ge 3$ 元谓词,不在 Frankl–Pach 模板内;自我判 fail,但无法独立给出反例 |
| D | 序理论 / Johnson scheme Bose–Mesner 代数 | 10 / risky | 自我识破:lex-initial 反而富含 sunflower(如 $\{A:1\in A\}$),策略破产 |
| E | 概率 / mod-2 配对 / Janson 单调性 | 9 / weak | 提出 64-case 双 counting,未跑通;与 A 实质等价 |
反证:设 $\mathcal F$ sunflower-free 而 $S_{ij}\mathcal F$ 含 sunflower $\{A_1,A_2,A_3\}$ 核 $Y$。对每个 $A_t$ 看是否被 shift 改动:被改动的 $A_t$ 满足 $i\in A_t,\,j\notin A_t$,原像为 $A_t^*=(A_t\setminus\{i\})\cup\{j\}$;未改动者 $A_t^*=A_t$。设 $T\subseteq\{1,2,3\}$ 为被改动下标。
L1 ranker 给 A 高分(15/20)正是因为 Case 0 / Case 3 闭合得漂亮,Case 1 看起来"几乎闭合"。这种乐观正是 v1 流水线(无 sentinel)会陷入的陷阱。
v2 流水线在 L1 发散后强制运行 sentinel:一个独立 agent,目标 = 在小参数上做完整数值 / 暴力检验,与 advocate(角度 A–E)的乐观平衡。sentinel 不 care 证明优雅,只 care "能不能跑出反例"。
sentinel 调用 system python3,对 $n=4,5,6$ 与 $k=2$ 全枚举:
| $n$ | sunflower-free $k=2$ 族数 | 测试 $(\mathcal F, i| 反例数 | 反例比例 | |
|---|---|---|---|---|
| 4 | 41 | 246 | 24 | 9.8% |
| 5 | 253 | 2530 | 660 | 26.1% |
| 6 | 1198 | 17970 | 4680 | 26.0% |
反例比例稳定在 1/4 量级,并随 $n$ 增长保持;这绝非边缘事件,而是 shifting 在 $k=2$ 下的结构性特征。
$k=2$ 已击毁。$k\ge 3$ 反例只会更多(自由度更大),无需进一步搜索。命题 1 在标准定义下 false。建议 propogate KILL 到 L2,跳过 search / lit-integrator / executor / reviewer,进入 §5 修订建议层。
取
$$\mathcal F = \big\{\{1,2\},\ \{1,4\},\ \{2,3\}\big\} \subseteq \binom{[4]}{2}.$$
Step 1:验证 $\mathcal F$ sunflower-free。三对交:
三对交两两不等($\{1\},\{2\},\emptyset$),故 $\mathcal F$ 不构成 3-sunflower。又 $|\mathcal F|=3$,唯一 3 元组就是 $\mathcal F$ 自身,故 $\mathcal F$ sunflower-free。✓
Step 2:作用 $S_{1,2}$($i=1, j=2$)。逐个看:
结果:
$$S_{1,2}\mathcal F = \big\{\{1,2\},\ \{1,4\},\ \{1,3\}\big\}.$$
Step 3:验证 $S_{1,2}\mathcal F$ 含 3-sunflower。三对交:
三对交全等于 $\{1\}$。花瓣:$\{2\},\{4\},\{3\}$ 两两不交且非空。故 $S_{1,2}\mathcal F$ 是正宗 3-sunflower,核 $Y=\{1\}$。 $\blacksquare$
把 $\mathcal F$ 看作 $K_4$ 上的 3 边图:两条边过顶点 1(即 $\{1,2\},\{1,4\}$ 形成"V"),第三条边 $\{2,3\}$ 不过 1。这不是 star,故非 sunflower。
shift $S_{1,2}$ 把"不过 1 的边" $\{2,3\}$ 强行拉过 1,变 $\{1,3\}$ — 三条边一起形成 1 为中心的 3-星 = 3-sunflower。
本质:shift 是"压缩元素 $j\to i$",它把分散的核 $\{2\}$ 与空核合并到 $\{1\}$。这正是 sunflower-free 性质所禁止的"核同步"。intersecting / shadow 这类二元谓词在 shift 下安全,因为它们只看 pairwise 信息;sunflower-free 是 3 元谓词,三个集合的交需同步,shift 反而促进同步。
给出小尺度全谱(sentinel 数据):
| $n$ | $\binom{n}{2}$ 边数 | 子族总数 | sunflower-free 数 | 反例数 | 反例 / sf-free 比 |
|---|---|---|---|---|---|
| 3 | 3 | 8 | 8 | 0 | 0% |
| 4 | 6 | 64 | 41 | 24 | 0.585 / pair-tested |
| 5 | 10 | 1024 | 253 | 660 | 2.61 / sf-free |
| 6 | 15 | 32768 | 1198 | 4680 | 3.91 / sf-free |
注:$n=3$ 不存在 3-sunflower($\binom{3}{2}=3$ 边 $K_3$ 三对交分别为 3 个不同顶点,不能全相等),故所有 8 子族 vacuously sunflower-free,shift 也保持。$n\ge 4$ 起反例每量级出现。
角度 A 的 Case 1 草稿声称:"$T=\{1\}$,$i\in P_1$,$j\notin A_2\cup A_3$ ⇒ $\{A_1^*,A_2,A_3\}$ 是 $\mathcal F$ 中 sunflower — 矛盾。"
用上面反例对照(这里 shift 的方向取 $i=1, j=2$,但 sentinel 的反例对应"被 shift 进来"的集合是 $\{1,3\}$ — 它在 $S_{1,2}\mathcal F$ 中,原像是 $\{2,3\}\in\mathcal F$):
A 草稿对 $i\in Y$ 子情形写:"若 $i\in Y$ 且 $j\notin A_2,A_3$..."后面没继续展开,直接跳到"若 $i\in P_1$"那一支声称闭合。
真正漏洞:当 $i\in Y$(即 shift 的"目标元素"恰好落在 sunflower 的核中),原像 $A_3^*=(A_3\setminus\{i\})\cup\{j\}$ 把 $i$ 替成 $j$。但
草稿在 Case 1 偷偷假设:「若 $A_1$ 被 shift,则 $A_1^*$ 与未动的 $A_2,A_3$ 仍构成 sunflower(核同步、花瓣不交)」。这一步在 $i\in Y$ 时成立的前提是所有 $A_t$ 的核必须同时包含 $i$ 或同时不包含 $i$。可是 Case 1 的定义是"$T=\{1\}$ 仅一个被改",即 $A_2,A_3\in\mathcal F$ 没动,$A_2$ 是否含 $i$ 与 shift 无关 — shift 不能强制 $A_2,A_3$ 在 $i$ 上的状态。
反例正好踩中:$A_2=\{1,2\},A_3'=\{1,4\}$ 都含 $i=1$(这是构造 sunflower 必需的),但原像 $A_3^*=\{2,3\}$ 不含 $i=1$ 也不含 $j=2$ 之外的 $A_2,A_3'$ 元素与之同步的结构。"反推"破产。
更深层:A 草稿的结构论证未把 "$A_t^*\in\mathcal F$" 与 "$A_t^*$ 在 sunflower 配置中"两件事拆开。前者由 shift 定义保证;后者需要额外验证 — 而本反例恰好提供了"$A_t^*\in\mathcal F$ 但不构成 sunflower"的清晰例子。
| 性质 | 谓词元数 | shift 保? | 关键差异 |
|---|---|---|---|
| intersecting($|F\cap F'|\ge 1$) | 2 元 | 是 (Frankl 1995 Lemma 2.1) | shift 把 $j\to i$ 只能减少不交对,不能增加 |
| $t$-intersecting | 2 元 | 是 | 同上 |
| antichain | 2 元 | 是 (Engel 1997) | shift 保 size 与 $\subseteq$ 关系 |
| shadow size $|\partial\mathcal F|\le M$ | 1 元 + global | 是 (Kruskal–Katona) | shift 是 shadow 的弱化 |
| sunflower-free($r=3$) | 3 元 | 否(本反例) | shift 促进核同步,制造新 sunflower |
归纳:shift 保性质的判据似乎是"谓词 $\le 2$ 元 + 单调($\mathcal F'\supseteq\mathcal F$ 则性质保)"。sunflower-free 既不是单调(去除元素可能制造新 sunflower 反过来不可能 — 但同 size shift 可),也不是 2 元,失败是结构必然,不是技术细节。
原命题死,但下列修订形式仍值得 L2/L3 攻关。每条都附"为何这样改可能可行"。
$$\mathcal F\subseteq\binom{[n]}{k},\quad \forall F,F'\in\mathcal F:\ F\cap F'\neq\emptyset.$$
EKR 极值族($n\ge 2k$,$|\mathcal F|\le\binom{n-1}{k-1}$)已知是 star-like 的,shift 在 EKR 内部移动是 well-studied。修订陈述:若 $\mathcal F$ intersecting + sunflower-free + $n\ge 2k$,则 $S_{ij}\mathcal F$ 也 intersecting + sunflower-free。
动机:intersecting 强制所有对交非空;shift 在此约束下"核已经同步",反而无法制造新核。本笔记反例 $\{\{1,2\},\{1,4\},\{2,3\}\}$ 不是 intersecting($\{1,4\}\cap\{2,3\}=\emptyset$),故不在此修订形式范围内。值得在 $k=3, n=7,8$ 上跑 sentinel 验证。
设 $\mathcal F^* = \lim_{m\to\infty} S_{i_m j_m}\cdots S_{i_1 j_1}\mathcal F$ 为 shift 不动点,即 shifted family:$\forall F\in\mathcal F^*, j\in F, i 修订陈述:若 $\mathcal F^*$ 已 shifted 且 sunflower-free,则任何 $S_{ij}\mathcal F^*=\mathcal F^*$(恒等),故 trivially 保。这个版本平凡为真,但有意义的是反方向: 修订 (b'):若 $\mathcal F$ sunflower-free,是否存在 shift 序列使 $\lim$ 仍 sunflower-free?sentinel 数据显示 $n=4$ 时 41 个 sf-free 族中只有 17 个在某个 shift 下保持,其余 24 都立即坏掉 — 故修订 (b') 也大概率假,需进一步实验。 定义对称压缩 $C_{ij}$:若 $F\bigtriangleup\{i,j\}\notin\mathcal F$,则把"$j\in F, i\notin F$"或"$i\in F, j\notin F$"中较 lex-小者保留,另一对应的集合替为对称伴侣。即 真正 的 swap,不是单方向 push。 这是 Kleitman 1966 monotone compression 的变体。修订陈述:sunflower-freeness 在 $C_{ij}$ 下保持。 动机:$C_{ij}$ 不 break 对称性 — 对核 $Y$ 关于 $\{i,j\}$ 的归属不会单方向激活。本笔记的反例 $\{2,3\}\to\{1,3\}$ 是单方向 push(仅当 $\{1,3\}\notin\mathcal F$ 时触发),$C_{ij}$ 会同时检验对称伴侣 $\{1,3\}\to\{2,3\}$ 而把"哪边留下"按 lex 选 — 在反例配置里 lex 小的是 $\{1,3\}$,但保留 $\{2,3\}$ 也合规,等价于不动。需 sentinel 重跑。 原命题取 $r=3$。改 $r\ge k+1$(核空时即 $r$ 个两两不交集)。 修订陈述:若 $\mathcal F$ 不含 $r$-sunflower 且 $r\ge k+1$,则 $S_{ij}\mathcal F$ 同。 动机:$r$ 越大,sunflower 越稀有;$r\ge k+1$ 把 sunflower 推到接近"两两不交"(matching)领域,shift 保 matching size 是经典结果(Frankl 1980)。本反例 $r=3, k=2$,对应 $r=k+1$ 临界 — 故此修订也未必能救。需在 $r=4, k=2$ 与 $r=4, k=3$ 上跑 sentinel。 $S_{\{i,j\}}^{\mathrm{sym}}(F) = F\bigtriangleup\{i,j\}$ 当 $|F\cap\{i,j\}|=1$ 且对称伴侣不在 $\mathcal F$ 中。这与 (c) 在算子层等价。 用 ALWZ 2020 的"spread"度量:$\mathcal F$ 是 $r$-spread 若 $\forall S, |\{F\in\mathcal F:S\subseteq F\}|\le r^{-|S|}|\mathcal F|$。修订陈述:若 $\mathcal F$ $r$-spread + sunflower-free,则某种 entropy 单调算子(不同于 Frankl shift)保两性质。 动机:ALWZ 的核心是"非 spread 族必含 sunflower"。spread 是真正的"sunflower-free 替代品",且 entropy 视角下是单调的 — 比 Frankl shift 更适配。但需重新定义算子,不再是单点 $i\to j$ push。 建议:放弃 P1 原形,把 (a) 与 (f) 提升为独立命题 P1.a 与 P1.f,分别走自己的 Template 2 v2 流程。其余 (b)–(e) 作为反面文献注记保留。 命题 1(标准定义):KILL。 反例数据:$n=4$ 24 例 / $n=5$ 660 例 / $n=6$ 4680 例 — 不是边缘事件而是 1/4 量级的结构性失败。最小反例 $\mathcal F=\{\{1,2\},\{1,4\},\{2,3\}\}$ 在 $S_{1,2}$ 下变 sunflower 核 $\{1\}$。 角度 A 的 Case 1 草稿"闭合"假设错误:未把 "$A_t^*\in\mathcal F$" 与 "$A_t^*$ 仍参与 sunflower 配置"拆开,导致反推到 $\mathcal F$ 中的步骤在 $i\in Y$ + 某 $A_t$ 不含 $i$ 时崩溃。 本命题是 v2 流水线设计目标的标本:folklore "shift 保 X" 类陈述对人类组合学家有强先验偏置(intersecting / antichain / shadow / no-disjoint 全保过),故传统攻关会反复试 case-bash 直到几周后从数值层意外 catch 反例。 v2 把数值 sentinel 放在 L1 与 advocate 平级,无视 ranker 给出的 strong verdict,独立跑暴力枚举 — 1 小时识别出 6 个月攻关都可能漏掉的反例。这正是"多 agent 并行 + 强制对抗 sentinel"相对于"线性论证 pipeline"的不对称收益。(c) compressed-by-symmetric-pair 算子
(d) $r\ge k+1$ 大花瓣 sunflower-free
5.2 改算子
(e) symmetric two-point shift
(f) entropy-monotone compression(ALWZ-style)
5.3 总修订矩阵
修订形式 救活性 对 P1 原 ambition 的支持 下一步 (a) intersecting + sf-free 中(待 sentinel) 部分(限到 EKR 极值领域) $k=3,n=7,8$ 全枚举 (b) shifted 不动点 trivial 无(同义反复) 跳过 (b') shift 序列 lim 低(sentinel 已暗示反例) 无 记录否定 (c)/(e) symmetric compression 中 较强(替代 Frankl shift) 定义算子 + 枚举 (d) $r\ge k+1$ 低($r=k+1$ 临界已破) 较弱 $r=4$ sentinel (f) ALWZ spread + 新算子 未知 非常强(接 §13.6 主线) 独立命题(命题 1.f) 6. KILL verdict + 价值告示
6.1 Template 2 v2 流水线的价值
阶段 v1(无 sentinel)会发生什么 v2 实际发生
L1 发散
5 角度并行;A 拿 strong verdict;进入 L2
5 角度并行;A 拿 strong verdict;但 sentinel 同时跑数值
L1 sentinel
—
30 秒发现 $n=4$ 反例 → propagate KILL
L2 search / lit-integrator
查 Frankl 1995, ALWZ 2020;可能误把 folklore 当定理引
跳过
L3 executor
试图证 Case 1 / Case 2;卡 case 2 数日;可能补 case 但仍漏掉 $i\in Y$ 子情形
跳过
L4 reviewer
解析 + 数值 reviewer 才数值化检验,发现反例
跳过(已在 L1 发现)
L5 总结
记 KILL,但已花 $20-50
记 KILL + 修订建议;总成本 $1-2
预期人工攻关时间(无 v2)
folklore 直觉 + Frankl shifting 模板 → 数周到 6 个月反复试 case 拆分
1 小时
6.2 给后续命题的教训
6.3 文件位置
work/sunflower-proposition1_shifting_preserves.html/tmp/sunflower_brainstorm/prop1/L1P1_{A,B,C,D,E}_*.md/tmp/sunflower_brainstorm/prop1/L1_ranker.md/tmp/sunflower_brainstorm/prop1/L1_sentinel.mdwork/reference_sunflower_research/prop1/decision_log.md