← Combinatorics 主索引 · Template 2 v2 模板 · decision_log · P1 (KILL)
Template 2 v2 流水线 · 原 Razborov–Rudich naturalness 路径 KILL · 修订为 Cook–Reckhow + KMOS pseudocalibration + GPW lifting 的 encoding-specific barrier · 4/4 WEAK-GO 票，conditional 接受
核心定理（修订形式 P5'）：在 Cook–Reckhow proof system 框架下，对 特定 encoding $\mathcal A_k$（spread 公理 + sunflower-free 公理 + Boolean 公理），Sherali–Adams refutation degree 为 $\Theta(\log_2 k)$；等价地，star-DISJ 通讯下界经 GPW/CFKMP lifting 给出 spread-refinement query 深度 $\Omega(\log k/\log\log k)$。
关键 caveat：
4 票评审（analytic / algebraic / numerical / adversary）一致 WEAK-GO，无 KILL；adversary 强烈要求降级陈述至 encoding-specific，已采纳。本笔记按 position-paper 级别归档：barrier 框架可形式化、可发表（STOC/FOCS publishable，类比 Razborov natural proofs 自身经典而不解 P vs NP），但绝非 ESS（Erdős sunflower）猜想的最终下界陈述。
把 ALWZ–Rao spread paradigm 套入 Razborov–Rudich (1997) naturalness 三公理：
原企图：把"sunflower-free"作 $\mathcal P$，论 spread 路线本身被 naturalness 阻挡，类比 Razborov–Rudich 对 $\mathsf{P/poly}$ 的 barrier。
精确枚举 $(n,k)=(6,3)$：sunflower-free 族的 density $3.21\times10^{-2}$；$|\mathcal F|\ge 11$ 全军覆没。Janson 阈值给 $|\mathcal F|^\star=O(1)$（$(50,3)$ 阈值仅 $\approx 2.2$），即族大小超过 ~3 个 $k$-set 就几乎必含 3-sunflower。
(L) 公理要求 $\Pr[\mathcal F\in\text{property}]\ge 2^{-\mathrm{poly}(N)}$；这里 $\Pr[\text{sf-free}]=2^{-\Omega(N)}$，指数破裂。且无单向函数对应 — naturalness 不可救。
放弃 naturalness，改走 Cook–Reckhow proof complexity + 通讯复杂度 lifting 的双轨：
定义 encoding $\mathcal A_k$（ALWZ-style）：变量 $x_S\in\{0,1\}$ 表 $S\in\mathcal F\subseteq\binom{[n]}{k}$；公理三组：
定理（修订 P5'）：
$$d_{\mathsf{SA}}(\mathcal A_k)\;=\;\Theta(\log_2 k).$$
等价地：star-DISJ$_{k,n}$ 通讯下界经 GPW/CFKMP lifting 强迫 spread-refinement query 深度 $\ge\Omega(\log k/\log\log k)$。
修订路径核对：
| 层 | 原 RR 形式 | 修订 Cook–Reckhow 形式 |
|---|---|---|
| 下界对象 | 性质 $\mathcal P\subseteq\{0,1\}^{2^N}$ | SA refutation 关于 encoding $\mathcal A_k$ |
| 大小公理 | (L) Largeness $\ge 2^{-\mathrm{poly}(N)}$ | 无（仅需 axiom set，不需 random ensemble） |
| 硬度假设 | 单向函数 / 离散对数 | 无（绕开 cryptographic hardness） |
| barrier 量级 | "naturalness barrier"（语义层） | SA degree $\Theta(\log k)$（语法层，可形式化） |
| 命题精神 | spread paradigm 不可避开 | spread-style refutation 在 ALWZ-encoding 下需 degree $\ge\Omega(\log k)$ |
L1 阶段并行启动 5 个 angle agents（详见 /private/tmp/sunflower_brainstorm/prop5/L1P1_*.md）。L1 ranker 评分（Form / Novel / Evid / Tract / Risk⁻ 各 0–10）：
| # | 角度 | 核心思路 | 合计 | Verdict |
|---|---|---|---|---|
| 1 | E Cook–Reckhow / SoS | spread proof 嵌入 Sherali–Adams / SoS，$\log k$ ↔ degree | 40 | KEEP（barrier 真正可形式化路径） |
| 2 | C Communication | star-DISJ → sunflower-detect, GPW lifting | 37 | KEEP（lifting 工具齐备，独立产 $\log k$ 信号） |
| 3 | A 形式化 Spread 系统 | 三元组证明系统 + 信息税公理 | 29 | SUPPORT（作 E 输入语言） |
| 4 | D Diagonalization | spread-resistant pseudorandom family | 21 | WEAK（与 B 同病：无硬度假设） |
| 5 | B Razborov–Rudich | naturalness 三公理 (C/L/U) | 16 | KILL（(L) 公理直接破，无密码硬度对应） |
整体处置：B + D 共同失败原因 = 无 average-case 硬度假设、sunflower-free 不"large"。E (Cook–Reckhow/SoS) + C (Communication/GPW) 双轨保留；A 作 E 的输入语言（spread 公理的形式语法）。这是修订 P5' 的双工具链根基。
L2 阶段挑出 4 篇必读 paper，每篇对修订 P5' 的接驳点已落实：
Kothari–Mori–O'Donnell–Schoenebeck。通用 pseudocalibration 框架：对随机 $k$-CSP 给出 SoS degree $\ge\tilde\Omega(n^{1-2/k})$ refutation 下界，构造 pseudo-expectation $\widetilde{\mathbb E}$ 对所有 low-degree polynomial 与 planted 分布不可区分。
P5' 用法：spread 假设（每集合 link-size $\le 2^{-r}|\mathcal F|$）天然是 $r$-CSP 形态；KMOS 模板直接给 "SoS degree $<\tfrac14\log k\Rightarrow$ 无 refutation"。这是 E 主线核心机器。
将 randomized decision-tree depth $d$ 用 $O(\log n)$-bit gadget（如 IndexGadget$_n$）lift 为 $\Omega(d\log n)$ randomized cc 下界。证明手法：simulation 论证 + structure-vs-pseudorandomness。
P5' 用法：spread-refinement 谓词 $\Phi_{\text{spread}}(\mathcal F)$ 视为查询 oracle；GPW lift 后任何 BPP-cc 协议 $\ge\Omega(\log k)\cdot\log n$ bits。C 辅线骨架。
Chattopadhyay–Filmus–Koroth–Meir–Pitassi。把 gadget block-size 压到 $O(\log n)$（之前需 $\mathrm{poly}(n)$），证伪"lifting 必须用大 gadget"。
P5' 用法：使 lifting 在 sunflower 自然 scale（每集合 $\log n$-bit 编码）下生效，避免人为 padding 破坏 spread 结构；为 prover_2 的 reduction 提供"小 gadget 即可"的工程许可。
Bar-Yossef–Jayram–Kumar–Sivakumar。信息复杂度 $\mathrm{IC}_\mu(\mathrm{DISJ}_n^k)\ge\Omega(n/k)$，由对 single-coordinate Hellinger distance 加和。
P5' 用法：sunflower 检测 = 找 $k$ 个集合两两交于固定 core，等价于 "$k$-party star pattern of DISJ"；BJKS 给底层 query-级硬度，再经 GPW lift。
L3.lit_1 验：lit_1 提议的代数模板（变量 $x_S$、disjointness 公理 $x_Sx_T=0$ 改为 sunflower-clause $\sum_{\mathcal S}\prod_{S\in\mathcal S}x_S=0$）在 理想结构 上承袭 EKR–PC 框架（同为 multilinear ideal over $\mathbb F$，degree-$k$ axioms）。但 EKR 公理是 degree-2 (pairwise)，sunflower 公理是 degree-$k$，净 gap 仅 $\log k$ — 与 numerical 表对齐。模板 portable，但 "EKR-tight 即 sunflower-tight" 不成立。
定义指示变量 $x_S\in\{0,1\}$，$S\in\binom{[n]}{k}$。spread 公理写成线性约束：
$$\sum_{S\supseteq T}x_S\;\le\;|\mathcal F|\cdot\sigma^{|T|},\quad\forall T,\,|T|\le\log k.$$
sunflower-free 写成 degree-$k$ multilinear axiom：
$$\bigwedge_Y\Bigl[\sum_{\substack{S_1,\dots,S_k\supseteq Y\\\text{petals disjoint}}}x_{S_1}\cdots x_{S_k}\le k-1\Bigr].$$
移植 KMOS 2017 pseudocalibration 模板，构造 pseudo-expectation $\widetilde{\mathbb E}$ 对所有 degree-$d$（$d<\tfrac14\log_2 k$）多项式与 planted sunflower-free, $\sigma$-spread family 不可区分；spread 公理在低度 moment 上自动满足。
Lasserre→PC slack-variable 转换（Laurent 2003）：$\sum_{S\supseteq T}x_S+s_T=2^{-r|T|}\sum x_S$，$s_T\ge 0$。对 Boolean cube 上的 multilinear 理想，SA / SoS / PC 三系统经 Positivstellensatz degree-preserving 等价 up to $O(1)$ factor（Grigoriev–Vorobjov, Schmüdgen archimedean）。spread 公理本身是 degree-$|T|$ 不等式，slack 引入后 PC degree = SA degree + max $|T|$，与 prover_1 的 $\Theta(\log k)$ 匹配。
L3.numerical 表明：
| $k$ | $(1/4)\log_2 k$ (KMOS LB) | $\log_2 k$ (UB) | $\log k/\log\log k$ (GPW lift) | Erdős $(\log k)^k$ |
|---|---|---|---|---|
| 3 | 0.396 | 1.585 | — | 1.33 |
| 5 | 0.580 | 2.322 | 1.911 | 10.8 |
| 8 | 0.750 | 3.000 | 1.893 | 350 |
| 16 | 1.000 | 4.000 | 2.000 | $1.22\times10^7$ |
| 32 | 1.250 | 5.000 | 2.153 | overflow |
| 64 | 1.500 | 6.000 | 2.321 | overflow |
| 128 | 1.750 | 7.000 | 2.493 | overflow |
| 256 | 2.000 | 8.000 | 2.667 | overflow |
| 1024 | 2.500 | 10.000 | 3.010 | overflow |
三条估计在常数倍意义下一致，predicted barrier $d_{\mathsf{SA}}=\Theta(\log_2 k)$，与 spread 论证 entropy step 数同阶。
三机制（SA / GPW / Razborov approximation）看似独立，实则共享 KL chain rule：SA pseudo-distribution、GPW entropy→query、Razborov approximation 都把"每 refinement round 丢 $\log k$ bit"作公理；并非"独立机制 self-confirmation"，而是 paradigm 内同源投影。删去 entropy 假设三条全废。
因此 advocate 的"三机制独立证据"叙事不成立。本笔记按 adversary 要求降级为：三种 view 给 align 数值证据（同一 KL chain rule 的三个投影），而非三个独立证明。
两方 Alice / Bob 各持 $k/2$ 个集合，Carol 持 candidate core $Y$；定义 $f=1$ iff Alice、Bob 集合除 $Y$ 外两两不交（即形成 sunflower with core $Y$）。这是 $k$-party star-DISJ 的实例。
L4.numerical 投票：$\log k/\log\log k$ 量级 严格成立（Göös–Pitassi–Watson 2017 Thm 1）；$k\log k$ bits 需 $N=k\log k$ scale 配合（确实有，是工程层补丁）。CFKMP 2020 RM gadget 在 $b=\Theta(\log k)$ 时正合 sunflower 自然编码 scale，gadget 兼容性已由 lit_2 核查通过。
| L4 评审 | 投票 | 关键理由 |
|---|---|---|
| analytic | WEAK-GO | barrier 框架可行 + STOC/FOCS publishable；KMOS 常数 1/4 迁移到 spread+sunflower-free CNF 需重做 graph matrix norm bound（BHKKMS 模板）；CLRS↔refutation-size 桥需补 Atserias–Lauria–Nordström；size LB 形式 $(\log k)^{\Theta(k)}$ 待重新校准。 |
| algebraic | WEAK-GO | EKR–PC 模板 portable + Positivstellensatz degree-preserving 自洽；瓶颈是 spread + sunflower-free 反例 family 的 pseudo-expectation 未构造（prover_1 §4 待办）。 |
| numerical | WEAK-GO（confidence 0.72） | 三路（KMOS LB / spread UB / GPW lift）量级 $\Theta(\log k)$ 稳；常数 $1/4$ 待 KMOS 模板验证；$N$ scale 需改写为 $k\log k$ 才得 $\Omega(k\log k)$ bits（prover_2 §2 待修）。 |
| adversary | REJECT 当前形式 / CONDITIONAL ACCEPT 修订形式 | 命门：(a) spread proof system 未 Cook–Reckhow well-defined（"spread argument" 仅 风格，无形式语法）；(b) 三机制同源（共享 KL chain rule）；(c) "$\log k$ barrier" 命名过强。要求改 encoding-specific 后可走。 |
4/4 WEAK-GO，但全员要求修订陈述至 encoding-specific。本笔记已采纳此修订（见 §1.2 与 §7）。
命题 5'（修订形式）：position-paper-PASS, encoding-specific.
4 票一致 WEAK-GO，无 KILL。E 主线（KMOS+SA）+ C 辅线（GPW+BJKS）双工具链齐备且量级数值一致。即使 G1+G3+G4 不全闭合，单独证 KMOS pseudocalibration → spread axiom moment matching 已是 publishable barrier 引理（类比 Razborov natural proofs barrier — 不解 ESS，自身经典）；存在副产物 fallback 价值。
L1 已点出此为难点。L3 各文均回避：advocate 只列三条 mechanism；prover_1 给的是 ALWZ argument 翻成 SA 的 degree 下界 — 即对 一个特定 encoding（spread 公理 + sunflower-free 公理 $\mathcal A_k$）的下界，不是对"任意 spread-flavored proof"的下界。
Cook–Reckhow 系统须满足 polynomial-time verifier + completeness/soundness；"spread argument" 仅是论证 风格，无形式语法。因此命题 5 仍未脱"非形式 paradigm 下界"陷阱 — 这正是 Razborov–Rudich 类 barrier 历来要求 hardness 假设的原因。
本笔记的处理（采纳 adversary §3 conditional 条件）：
| # | gap | 提出方 | 紧迫度 |
|---|---|---|---|
| G1 | "Spread-based proof"非 Cook–Reckhow well-defined（仅 风格，无形式语法）；P5' 仅给 特定 encoding 下界 | adversary §1 | CRITICAL（命门，已通过降级陈述处置） |
| G2 | 三机制（SA / GPW / Razborov approx）共享 KL chain rule，非独立证据 | adversary §2 | HIGH（已降级叙事） |
| G3 | KMOS 常数 $1/4$ 迁移到 spread+sunflower-free CNF 需重做 graph matrix norm bound（BHKKMS 模板） | analytic §1 | HIGH |
| G4 | prover_1 size LB 形式化：CLRS extension complexity ↔ propositional refutation size 桥不直接，需补 Atserias–Lauria–Nordström | analytic §2 | HIGH |
| G5 | "$\log k$ barrier" 命名过强，应降为 "$\Theta(\log k)$ SA-degree barrier for ALWZ-encoding" | adversary §3 | HIGH（已采纳） |
| G6 | sunflower-clause axiom degree-$k$ vs EKR axiom degree-2，PC 净 gap 仅 $\log k$；pseudo-expectation 构造（spread 且 sunflower-free reference family）尚未给出 | algebraic §1, prover_1 §4 | MEDIUM |
| G7 | star-DISJ → sunflower-detect 归约的 scale 选择：BJKS $\Omega(N/k)$ 在 $N=k$ 退化到 $\Omega(1)$，需 $N=k\log k$ 配合 RM gadget 才得 $\Omega(k\log k)$ bits | numerical §1, prover_2 §4 | MEDIUM |
立即（本周）：
verdict=position-paper-PASS, encoding_specific=true。短期（1 个月）— 闭合 G3 + G6（核心 prover 任务）：
中期（3 个月）— 闭合 G4 + G7：
长期：
work/sunflower-proposition5_proof_barrier.html/private/tmp/sunflower_brainstorm/prop5/L1P1_{A,B,C,D,E}_*.md/private/tmp/sunflower_brainstorm/prop5/L1_{ranker,sentinel}.md/private/tmp/sunflower_brainstorm/prop5/L2_{search,reader}.md/private/tmp/sunflower_brainstorm/prop5/L3_*.md/private/tmp/sunflower_brainstorm/prop5/L4_*.md/private/tmp/sunflower_brainstorm/prop5/L5_summary.mdwork/reference_sunflower_research/prop5/decision_log.md