Erdős #993 — SLOPE 引理

⚠️ 2026-05-31 重要更正。 本页早先把 SLOPE 引理写成一条抽象序列不等式（假设 D 单峰，后改 D 对数凹）—— 这是错的。经穷举 + 实数对抗搜索，所有自然的抽象假设都有反例（D 单峰 ✗、D 对数凹 ✗、A 对数凹 ✗），例如 $D=(6,5,4,3),S=(1,2,4,0),j=1$（D 对数凹，$A=(6,6,6,7)$，却 $e_2-e_1=0<1=d_0-d_1$）。所有反例都有 $\operatorname{mode}(D)=0$，而独立多项式 $I(G\setminus w)$（常数项 $=1$）永不如此。结论：SLOPE 不等式不是干净的抽象序列不等式，真正依赖独立多项式结构。
仍然成立、已证： $S\equiv0$（pure-$D$）情形 —— 见 slope-pureD.pdf（含闭式 Farkas 证书）。一般情形是树/IP-特定的开放问题 —— 见 slope-problem.pdf。下文中标注"假设 (i)/抽象验证"的部分按此更正理解。

0. 从 #993 一路规约到这里（背景）

原问题：对任意树 $T$，独立多项式 $I(T;x)=\sum_k i_k(T)\,x^k$ 单峰。我们走的是空腔归纳（cavity induction）路线：对 $T$ 取一片最深的叶子 $v$，设它的邻居是 $u$。删 $v$ 得 $T'=T-v$。利用独立多项式的空腔恒等式 $I(G)=I(G\setminus x)+x\,I(G\setminus N[x])$，逐层把 $T$ 的单峰性归约到一个关于删点如何移动众数的问题。

核心量是单点 mode-shift $$ g \;=\; \mathrm{mode}\big(I(T')\big)-\mathrm{mode}\big(I(T'\setminus u)\big). $$ 配合已证的"统一空腔单峰定理"，只要 $g\in\{-1,0,1\}$（删一个点，IP 的众数最多移动 1）就能让归纳走下去。 $g\le 1$ 一侧基本已处理；唯一卡住的是 $g\ge -1$——也就是"删点不会把众数往上顶超过 1"。经一系列收窄（详见规约地图），它落在最难的边界情形 $h=3$ 上，并最终化简成下面这条与树无关的不等式。

1. 树如何产生 $D,\,S,\,A,\,E$（化简到单棵子树）

最深叶子 $v$ 的邻居 $u$ 一定是"瘦邻居"（thin）：$u$ 的邻居里除了至多一个非叶顶点 $w'$ 外全是叶子。设 $u$ 带 $j$ 个叶子。删掉 $u$ 后，$T'\setminus u$ 裂成 $j$ 个孤立点和唯一一棵非平凡子树 $G_*$（以 $w'$ 为根）。于是四个多项式全由 $G_*$ 生成：

$$ \begin{aligned} A_0 &:= I(G_*),\qquad S_0 := I(G_*\setminus N[w']),\qquad D_0 := I(G_*\setminus w') \;=\; A_0 - x\,S_0,\\[4pt] E &:= I(T'\setminus u) \;=\; (1+x)^{\,j}\,A_0,\qquad C := I(T') \;=\; E + x\,D_0 . \end{aligned} $$

关键结构（都来自"诱导子图"的初等事实）：

$D_0,\,A_0$ 单峰（归纳假设：它们是更小的树/森林的 IP）；
$S_0\le D_0$ 逐项（$G_*\setminus N[w']$ 是 $G_*\setminus w'$ 的诱导子图）；
那个 $(1+x)^j$ 因子，是 $u$ 上挂的 $j$ 个叶子贡献的——它正是后面"尺度分离"的来源。

把树的语言抽掉，只保留这些系数序列的性质，就得到下面这条干净的引理。

2. SLOPE 引理（精确陈述）

SLOPE 引理　验证 0/1127 万，证明开放

设 $D=(d_k)$、$S=(s_k)$ 是两条非负实数序列，满足

(i) $D$ 对数凹（$d_k^2\ge d_{k-1}d_{k+1}$，特别地单峰）；
(ii) $S\le D$ 逐项（$s_k\le d_k$ 对所有 $k$）；
(iii) $A:=D+xS$ 单峰（即 $a_k=d_k+s_{k-1}$）。

令 $E:=(1+x)^{\,j}A$，$M:=\mathrm{mode}(E)$。若 $\mathrm{mode}(D)\le M-3$，则

$$\boxed{\;e_{M-1}-e_{M-2}\;\ge\; d_{M-3}-d_{M-2}\;}$$

把它放回树：$D=I(G_*\setminus w')$，$S=I(G_*\setminus N[w'])$，$A=I(G_*)=D+xS$，$E=(1+x)^jA_0=I(T'\setminus u)$。所有假设都被树自动满足，而结论 $e_{M-1}-e_{M-2}\ge d_{M-3}-d_{M-2}$ 正是 $g\ge-1$ 在 $h=3$ 情形的等价不等式（下面 §5 会用斜率坐标说清楚）。

术语：$e_k$ 是 $E$ 的第 $k$ 个系数；$\mathrm{mode}$ 取最左的最大值下标。条件 $\mathrm{mode}(D)\le M-3$ 就是我们说的"硬情形"，记 $h:=M-\mathrm{mode}(D)\ge 3$。

3. 为什么它（直觉上）为真：尺度分离

不等式左边 $e_{M-1}-e_{M-2}$ 是 $E$ 在峰下方一格的增量；右边 $d_{M-3}-d_{M-2}$ 是 $D$ 越过自己峰后的第一个跌幅。两边都是"近峰的小量"，看似势均力敌——但其实右边远小于左边，原因有两层：

$h\ge 3$ 强制 $j\ge 4$。（机器验证：硬情形的最小 $j$ 恰为 4。）因为 $(1+x)^j$ 把 $E$ 的众数相对 $A_0$ 往上推约 $j/2$，要把众数推开 $\ge 3$ 必须有足够多的 $(1+x)$ 因子。所以 $E$ 总是被 $(1+x)^{\ge 4}$ 整除。
$(1+x)^j$ 把 $E$ 的系数放大约 $2^j$ 倍，而 $D$ 没有这个因子。所以在共同尺度下，$D$ 的整体量级只有 $E$ 的 $\sim 2^{-j}$；再加上 $d_{M-3}-d_{M-2}$ 本身是个"近峰的差"（D 峰很平），右边是双重地小。

"自我防御"现象：情形越难（众数被顶开的 $h$ 越大），$(1+x)^j$ 需要的 $j$ 越大，于是保护这条不等式的 $2^{-j}$ 幅度差距也越大。难度自己把自己摁住了。机器实测：把裕量按 $h$ 分桶，最坏恰在边界 $h=3$，$h\ge 4$ 几何衰减。

顺带一个被纠正的诱惑：我们一度以为裕量是干净的 $1/6=1/\binom{4}{2}$，但那只是 $j=4$ 的巧合—— 强化版 $e_{M-1}-e_{M-2}\ge\binom{j}{2}(d_{M-3}-d_{M-2})$ 对 $j\ge5$ 失败，实际 sup 比率约按 $2^{-j/2}$ 衰减。

4. 数值证据

真实树 IP：最深叶子空腔，$g\in\{-1,0,1\}$，slope 不等式 0 反例 / 92 万+（含高度数、$n\le 78\text{K}$，缩放 DP）。
抽象序列（一般、非比例 $S$）：在假设 (i)–(iii)（$D$ 对数凹）下 slope 不等式 0 反例 / 3600 万硬情形（所有 $j\ge1$）。对数凹是必需的：若把 (i) 放松为"单峰"则有反例（如 $D=(3,2,2,2),S=(1,1,2,0),j=1$）。
对照：若丢掉 $d_{M-2}$（即想证更强的 $e_{M-1}-e_{M-2}\ge d_{M-3}$），会失败（1127 万里有 1–2 个反例）。说明那个"相减"项是承重的，不能丢。

5. 证明脚手架：斜率坐标

取最难的精确情形 $h=3$（即 $\mathrm{mode}(D)=M-3$），把一切写成 $D$ 的斜率。记 $\delta_k:=d_k-d_{k-1}$（$D$ 的差分，在众数 $M-3$ 处由正变负）。引入

$$ a_l := d_{M-3-l}-d_{M-4-l}\ \ (\ge 0,\ \text{上升斜率},\ l\ge0),\qquad \begin{aligned} b_0&:=d_{M-3}-d_{M-2}\ (=\text{不等式右边 RHS}),\\ b_1&:=d_{M-2}-d_{M-1},\quad b_2:=d_{M-1}-d_{M}\quad(\ge0,\ \text{下降幅度}). \end{aligned} $$ $$ S_r := \sum_{l\ge 0}\binom{j}{r+l}\,a_l \quad(\text{注意：因 }\textstyle\binom{j}{i}=0\ (i>j),\ S_2\ \text{只含 } a_0,\dots,a_{j-2}). $$

把三条众数约束（$E$ 单峰 ⟺ 所有 $\Delta E_k:=e_k-e_{k-1}$ 在 $k\le M$ 处 $\ge0$、$k\ge M+1$ 处 $\le0$）翻译过来，得到以下 逐项等式（机器验证 0 反例 / 520 万）：

记号	等价于	含义
(A) GOAL	$S_2\ \ge\ (j+1)\,b_0+b_1$	要证的目标
(B) $\Delta E_{M-1}\ge0$	$S_2\ \ge\ j\,b_0+b_1$	$E$ 单峰白给的
(C) $\Delta E_{M}\ge0$	$S_3\ \ge\ \binom{j}{2}b_0+j\,b_1+b_2$	$M$ 是众数

对照 (A) 与 (B) 立刻看出问题的本质——"差一格"（off-by-one）： $$\text{GOAL\_slack}\;=\;\Delta E_{M-1}-b_0\;=\;S_2-\big((j+1)b_0+b_1\big).$$ $E$ 单峰免费给了 $S_2\ge j\,b_0+b_1$，而目标要 $S_2\ge (j+1)b_0+b_1$——只差一个 $b_0$（把 $j$ 升成 $j+1$）。这一个 $b_0$ 必须从别的众数约束里"挤"出来。注意 $\binom{j}{2}\ge j+1$（$j\ge4$），所以 (C) 提供的余量是够的，问题只是如何把 $S_3$ 的信息倒给 $S_2$。

一条失败的简单闭合：本想用 $S_2\ge S_3$ 把 (C) 直接搬给 (A)，但 $S_2\ge S_3$ 是假的（验证：520 万里失败 180 万，例如 $j=7$ 时 $S_2=503530在下结论前就测出来了，没再犯 §7 那种错。

6. LP 证书：off-by-one 能由单峰性闭合吗？

既然单条约束不够，自然的客观问法是：把众数约束 $\{\Delta E_k\ \text{的符号}\}$ 全放进去，GOAL 能否被它们线性推出？ 这是一个线性规划（LP）可行性问题。把 $a_l,b_l\ge0$ 当变量、各 $\Delta E_k$ 符号当约束、归一化 $\sum z=1$， 极小化 GOAL_slack：

若 $\min\ge 0$ ⟹ GOAL 在这个锥上恒非负 ⟹ 它确实由（有限窗口的）众数约束线性推出，pure-D 引理就有了有限的 LP 证书。
若 $\min<0$ ⟹ 这些约束不够，需要更大窗口或更多结构。

结果（$j=4$，自写两阶段单纯形，已在玩具 LP 上校验）： $$\min\ \text{GOAL\_slack}\;=\;0\quad(\text{optimal}).$$ 也就是说，对 $j=4$，off-by-one 确实能由有限多条 $\Delta E_k$ 符号约束线性闭合——存在 LP 证书。把对偶乘子读出来，就是一份可写下的证明。$j\ge5$ 目前因求解器 Phase-1 的一个 bug 暂时报错，待修。

意义：这把"证明"从"需要某个灵光一现"降级成了"对每个 $j$ 提取一组有限的线性组合系数"——一件机械、可判定的事。剩下的工作是：修好 $j\ge5$、读出各 $j$ 的乘子、并看它们是否有一个对所有 $j$ 统一的模式（那将给出一劳永逸的人类证明）。

7. 诚实记录：走过的两条弯路（已撤回）

在通往 SLOPE 引理的路上，我两次提出了"更干净"的化简，但都被自己证伪——保留在此，以免重走。

撤回 K1′：丢掉 $S$，用 $\ge a_{M-3}$

曾想把目标弱化成 $e_{M-1}-e_{M-2}\ge a_{M-3}$（不含 $S_0$）。它对真实树 IP 成立，但对一般单峰、甚至对一般对数凹序列都失败。根因是 linkage：树里 $j$ 与 $A_0$ 通过 $h=3\Leftrightarrow\mathrm{mode}(D)=M-3$ 绑定，丢掉 $S_0$ 就丢掉了让不等式为真的树结构。 教训：不要把归约做过头，越过承载真值的那层结构。

撤回 R′：化成 $\mathrm{mode}\big((1+x)^j-x^2)D\big)\ge M-1$

曾"重述"目标为一个两个单峰多项式之间的 mode-shift（$R'_j=(1+x)^j-x^2$ 对数凹、$R'_4=(x^2{+}x{+}1)(x^2{+}3x{+}1)$、$f=R'_jD$ 由 Ibragimov 单峰）。但代数上 $f_{M-1}-f_{M-2}=\Delta E_{M-1}-\Delta d_{M-3}$，而 GOAL$=\Delta E_{M-1}+\Delta d_{M-2}$——两者并不等价（520 万里有 76% 不相等）。它们恰好都恒成立，于是 fail 数都是 0，我误把"都 0-fail"当成了"等价"。 教训：任何"等价重述"都必须做逐项的等式核对，"两者都 0-fail" $\ne$ "等价"。

8. 那么——这究竟是个什么问题？

不是树问题。树只是出处；规约后的 SLOPE 引理是一条关于抽象非负系数序列的陈述，里面没有任何图。

不是 closed-form 公式问题。它不要求算出某个表达式的值，而是一条对所有合法 $(D,S,j)$ 都成立的全称不等式。

它属于：代数组合学里证明单峰性的那一类卷积/对数凹不等式——和 Newton 不等式、Ibragimov 强单峰性、occupancy fraction 是同一族工具的territory。更精确地说，今天我们把它的核心进一步压成了：一条关于 $D$ 的斜率 $(a_l,b_l)$ 的、可由众数约束线性推出的有限不等式（对 $j=4$ 已由 LP 确认 $\min=0$）。

所以现在的形态是最"机械可证"的一种：universal 的初等卷积不等式 → 有限的、LP-可证的线性事实。离一个人类可写下的、对所有 $j$ 统一的证明，只差从 LP 证书里读出乘子并找出 $j$-uniform 的模式这一步。

状态总览：SLOPE 引理 = #993 经此路线的唯一开放核心（验证 0/1127 万，证明开放）。其余环节（统一空腔定理、Levit–Mandrescu 上三分之一递减、瘦邻居存在、Ibragimov、$g\le1$ 一侧）均已证或为标准件。详见规约地图。