Tao–Vu · 加性组合学 · 第 3 章 加性几何

3.4　布伦–闵可夫斯基不等式The Brunn–Minkowski inequality

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节目标在前面几节里，我们关心的是有限集合相加后“元素个数”怎么变。本节把舞台换成连续的几何世界：集合 \(A,B\) 是 \(\mathbb{R}^d\)（\(d\) 维空间）里的实心区域，“大小”改用体积（记作 \(\mathrm{mes}\)，即测度 measure）。核心问题是：把 \(A\) 和 \(B\) 做“和集” \(A+B=\{a+b:a\in A,\,b\in B\}\) 之后，体积至少有多大？答案就是布伦–闵可夫斯基不等式——它给出 \(\mathrm{mes}(A+B)\) 的一个干净的下界，是整个加性组合学里几何这一侧的奠基性结果。

本节的目的，是证明关于和集体积 \(\mathrm{mes}(A+B)\) 的如下下界。

定理 3.16（布伦–闵可夫斯基不等式）若 \(A\) 与 \(B\) 是 \(\mathbb{R}^d\) 中非空、有界、开的子集，则 \[\mathrm{mes}(A+B)^{1/d}\ \ge\ \mathrm{mes}(A)^{1/d}+\mathrm{mes}(B)^{1/d}.\]

这条不等式是尖锐的（即不能再改进，见习题 3.4.2）。该定理在 \(A,B\) 仅为可测集（而非有界开集）时也成立，不过那时还须额外假设 \(A+B\) 可测；这一点我们不予证明。一般地，\(\mathrm{mes}(A+B)\) 没有上界：例如取 \(A\) 为 \(\mathbb{R}^2\) 中的 \(x\) 轴、\(B\) 为 \(y\) 轴，则 \(A,B\) 的测度都为零，但 \(A+B\) 却是整个 \(\mathbb{R}^2\)。稍加修改这个例子，就能说明：当 \(A,B\) 为有界开集时，也无法用 \(\mathrm{mes}(A)\) 与 \(\mathrm{mes}(B)\) 给出 \(\mathrm{mes}(A+B)\) 的上界。关于布伦–闵可夫斯基不等式及相关主题的详尽综述，见 [128]。

先把符号读懂：和集 \(A+B\) 是什么 \(A+B\) 是“把 \(A\) 里每个点和 \(B\) 里每个点相加，得到的所有结果”组成的集合。一个等价而直观的看法：把 \(B\) 这个形状的中心放到 \(A\) 里每一点上各盖一份，所有这些副本扫过的总区域就是 \(A+B\)（即 \(A+B=\bigcup_{a\in A}(a+B)\)）。
A（正方形） B（圆盘） + = A+B（正方形被"加厚"）
把圆盘 \(B\) 的中心沿正方形 \(A\) 滑动一圈，扫出的区域就是 \(A+B\)：正方形向外被加厚了一圈（角变圆），面积明显比 \(A\) 大。
为什么是 \(d\) 次根：先验算一个最简单的情形 取 \(B=A\)（且 \(A\) 凸），则 \(A+A=2A\)（把 \(A\) 整体放大到 \(2\) 倍）。在 \(d\) 维里，线度放大 \(2\) 倍，体积变 \(2^d\) 倍，故 \(\mathrm{mes}(2A)=2^d\,\mathrm{mes}(A)\)。代入定理两边：
  1. 左边 \(\mathrm{mes}(A+A)^{1/d}=\big(2^d\,\mathrm{mes}(A)\big)^{1/d}=2\,\mathrm{mes}(A)^{1/d}\)。
  2. 右边 \(\mathrm{mes}(A)^{1/d}+\mathrm{mes}(A)^{1/d}=2\,\mathrm{mes}(A)^{1/d}\)。
  3. 两边恰好相等！这说明：取 \(1/d\) 次根，正是为了让体积这个"\(d\) 次量"变回与线度同级别的"\(1\) 次量"，从而能像长度那样直接相加。这也顺带验证了"等号可达"，呼应了习题 3.4.2。
体会"没有上界"的反例 \(x\) 轴是平面里一条无限长但"无宽度"的线，面积为 \(0\)；\(y\) 轴同理面积为 \(0\)。但 \(x\) 轴上任一点 \((s,0)\) 加上 \(y\) 轴上任一点 \((0,t)\) 得到 \((s,t)\)，而 \(s,t\) 可取任意实数——于是 \(A+B\) 取遍整个平面，面积为无穷。两个"零面积"的集合相加竟得到无穷面积，可见 \(\mathrm{mes}(A+B)\) 不可能被 \(\mathrm{mes}(A),\mathrm{mes}(B)\) 从上方控制住。这也正是布伦–闵可夫斯基只能给下界的原因。

为证明此定理，只需证明下面这个与维数无关的版本即可。

定理 3.17（维数无关版本）若 \(A\) 与 \(B\) 是 \(\mathbb{R}^d\) 中非空、有界、开的子集，且 \(0<\theta<1\)，则 \[\mathrm{mes}\big((1-\theta)\cdot A+\theta\cdot B\big)\ \ge\ \mathrm{mes}(A)^{1-\theta}\,\mathrm{mes}(B)^{\theta}.\]
两个版本的"长相"对比 注意定理 3.17 的右边是 \(\mathrm{mes}(A),\mathrm{mes}(B)\) 的加权几何平均（\(x^{1-\theta}y^\theta\) 型），而且左右两边都不带 \(1/d\) 次根——所以叫"维数无关"：式子的形式里不出现 \(d\)。这种形式在做归纳和积分时更顺手，这正是它被选作证明跳板的原因。

为说明定理 3.17 蕴含布伦–闵可夫斯基不等式，将定理 3.17 中的 \(A,B\) 分别替换为 \(\mathrm{mes}(A)^{-1/d}\cdot A\) 与 \(\mathrm{mes}(B)^{-1/d}\cdot B\)，便得到：对任意 \(0<\theta<1\)， \[\mathrm{mes}\left(\frac{1-\theta}{\mathrm{mes}(A)^{1/d}}\cdot A+\frac{\theta}{\mathrm{mes}(B)^{1/d}}\cdot B\right)\ \ge\ 1.\] 取 \[\theta:=\frac{\mathrm{mes}(B)^{1/d}}{\mathrm{mes}(A)^{1/d}+\mathrm{mes}(B)^{1/d}},\] 即得所求结论。反之，也容易由布伦–闵可夫斯基不等式推出定理 3.17（习题 3.4.1）。

把这段"代换魔术"逐步拆开看 这一步是全节最容易看晕的代数，分步走一遍动机就清楚了。记 \(\alpha=\mathrm{mes}(A)^{1/d}\)，\(\beta=\mathrm{mes}(B)^{1/d}\)。
  1. 归一化：令 \(A'=\mathrm{mes}(A)^{-1/d}\cdot A\)，即把 \(A\) 缩放到体积为 \(1\)（因为线度缩 \(\alpha^{-1}\) 倍，体积缩 \(\alpha^{-d}=1/\mathrm{mes}(A)\) 倍）。同理 \(B'\) 体积也为 \(1\)。于是 \(\mathrm{mes}(A')=\mathrm{mes}(B')=1\)。
  2. 代入定理 3.17：右边变成 \(1^{1-\theta}\cdot 1^{\theta}=1\)，所以 \(\mathrm{mes}\big((1-\theta)A'+\theta B'\big)\ge 1\)。把 \(A',B'\) 写回去就是上面那个带分母的式子。
  3. 选 \(\theta\) 让两个系数相等：我们希望 \((1-\theta)/\alpha\) 与 \(\theta/\beta\) 变成同一个数，这样括号里就是 \(c\cdot(A+B)\) 的形式。解 \((1-\theta)/\alpha=\theta/\beta\) 得 \(\theta=\beta/(\alpha+\beta)\)，正是上面那个取值，此时公共系数为 \(c=1/(\alpha+\beta)\)。
  4. 收尾：于是 \(\mathrm{mes}\big(c\cdot(A+B)\big)\ge 1\)，即 \(c^{d}\,\mathrm{mes}(A+B)\ge 1\)，也就是 \(\mathrm{mes}(A+B)\ge (\alpha+\beta)^{d}\)。两边开 \(d\) 次根：\(\mathrm{mes}(A+B)^{1/d}\ge\alpha+\beta=\mathrm{mes}(A)^{1/d}+\mathrm{mes}(B)^{1/d}\)。证毕。♦

于是剩下的任务就是证明定理 3.17。我们先从一维情形开始。

引理 3.18（一维布伦–闵可夫斯基不等式）若 \(A,B\) 是 \(\mathbb{R}\) 中非空、有界、开的子集，则 \(\mathrm{mes}(A+B)\ge \mathrm{mes}(A)+\mathrm{mes}(B)\)。
证明. 本引理的假设与结论在对 \(A\) 与 \(B\) 各自独立平移时都保持不变，故可设 \(\sup(A)=0\) 且 \(\inf(B)=0\)，于是 \(A,B\) 尤其是不相交的。但这样一来，我们看到 \(A+B\) 同时分别包含 \(A\) 与 \(B\)，证毕。♦
把这条一维证明画出来、补足细节 一维里测度就是"长度"。设想 \(A,B\) 都是若干开区间拼成的。
  1. 平移不改变长度：把 \(A\) 整体左右挪动，长度不变；\(A+B\) 也只是整体平移，长度也不变。所以可以随意"摆位置"。我们把 \(A\) 挪到它的最右端贴着 \(0\)（\(\sup A=0\)，即 \(A\subseteq(-\infty,0)\)），把 \(B\) 挪到它的最左端贴着 \(0\)（\(\inf B=0\)，即 \(B\subseteq(0,+\infty)\)）。这时 \(A\) 全在 \(0\) 左边、\(B\) 全在 \(0\) 右边，二者不相交。
  2. \(A+B\) 装得下 \(A\)：因为 \(B\) 里有靠近 \(0\) 的点（\(\inf B=0\)），\(A+0\approx A\) 都落在 \(A+B\) 里；严格地，\(\sup B=:b>0\)，则 \(A+0^+\) 覆盖 \(A\)，即 \(A\subseteq \overline{A+B}\)。同理 \(B\subseteq A+B\)。
  3. \(A\) 与 \(B\) 又不相交：\(A\) 在负半轴、\(B\) 在正半轴。于是 \(A+B\) 至少包含这两块不重叠的部分，长度相加：\(\mathrm{mes}(A+B)\ge\mathrm{mes}(A)+\mathrm{mes}(B)\)。
0 A（贴在 0 左侧） B（贴在 0 右侧） A+B 至少覆盖 A 与 B 这两段不重叠区间
摆好位置后 \(A\) 全在 \(0\) 左、\(B\) 全在 \(0\) 右，互不重叠；\(A+B\) 同时盖住两段，故长度至少是两段之和。

利用此引理，我们推出

命题 3.19（一维 Prékopa–Leindler 不等式）设 \(0<\theta<1\)，又设 \(f,g,h:\mathbb{R}\to[0,\infty)\) 是 \(\mathbb{R}\) 上下半连续、紧支撑的非负函数，满足 \[h\big((1-\theta)x+\theta y\big)\ \ge\ f(x)^{1-\theta}g(y)^{\theta}\qquad\text{对一切 }x,y\in\mathbb{R}.\] 则有 \[\int_{\mathbb{R}}h\ \ge\ \left(\int_{\mathbb{R}}f\right)^{1-\theta}\left(\int_{\mathbb{R}}g\right)^{\theta}.\]
证明. 用适当的正常数乘 \(f,g,h\)，可将其规范化为 \(\sup_x f(x)=\sup_y g(y)=1\)。 任取 \(1>\lambda>0\)。注意到：若 \(f(x)>\lambda\) 且 \(g(y)>\lambda\)，则由假设 \(h\big((1-\theta)x+\theta y\big)>\lambda\)。于是 \[\{z\in\mathbb{R}:h(z)>\lambda\}\ \supseteq\ (1-\theta)\cdot\{x\in\mathbb{R}:f(x)>\lambda\}+\theta\cdot\{y\in\mathbb{R}:g(y)>\lambda\}.\] 由于 \(f,g,h\) 下半连续且紧支撑，上面所有集合都是开的且有界，故由引理 3.18， \[\mathrm{mes}(\{z:h(z)>\lambda\})\ \ge\ (1-\theta)\,\mathrm{mes}(\{x:f(x)>\lambda\})+\theta\,\mathrm{mes}(\{y:g(y)>\lambda\}).\] 对 \(\lambda\in[0,\infty)\) 积分并使用 Fubini 定理（参见 (1.6)），结论便由算术–几何平均不等式得出。♦
读这条命题前，先建立直觉 Prékopa–Leindler 是"函数版"的布伦–闵可夫斯基：它把"集合的体积"升级成"函数的积分"。三个函数 \(f,g,h\) 的关系 \(h((1-\theta)x+\theta y)\ge f(x)^{1-\theta}g(y)^\theta\) 意思是：\(h\) 在 \(x,y\) 的加权中点处，至少有 \(f(x),g(y)\) 的加权几何平均那么高。结论说：那么 \(h\) 的总积分，至少是 \(f,g\) 积分的加权几何平均。它的威力在于能对维数做归纳——这是直接处理体积难以做到的。
关键技巧：用"水平切片"把积分还原成长度（layer-cake） 证明的灵魂是一个恒等式：任何非负函数的积分，等于它超水平集（即 \(\{z:h(z)>\lambda\}\) 这种"高出 \(\lambda\) 的部分"）长度对 \(\lambda\) 的积分： \[\int_{\mathbb{R}}h(z)\,dz=\int_0^\infty \mathrm{mes}(\{z:h(z)>\lambda\})\,d\lambda.\] 直观上：把函数图像下方的面积，按高度 \(\lambda\) 一层一层水平切开，第 \(\lambda\) 层的"宽度"正是超水平集的长度，把所有层加起来就是总面积。这就是为什么能把"对函数的命题"翻译成"对每个 \(\lambda\) 的集合长度命题"，进而套用一维布伦–闵可夫斯基（引理 3.18）。
高度 h(z) λ {z : h(z) > λ} 的长度
在高度 \(\lambda\) 处水平切一刀，被切到的那段底（红粗线）就是超水平集；把所有高度的切片宽度积起来 \(=\) 函数下面积 \(=\int h\)。
逐步复盘命题 3.19 的证明
  1. 规范化：乘正常数把 \(f,g\) 的最高点都拉到 \(1\)。这只是为了让 \(0<\lambda<1\) 时超水平集非空，使后续引理可用；不影响要证的不等式（两边随常数同步变化）。
  2. 逐层的集合包含：固定 \(\lambda\)。若 \(x\) 让 \(f(x)>\lambda\)、\(y\) 让 \(g(y)>\lambda\)，则 \(f(x)^{1-\theta}g(y)^\theta>\lambda^{1-\theta}\lambda^\theta=\lambda\)，由条件知 \(h((1-\theta)x+\theta y)>\lambda\)。这正说明 \(h\) 的第 \(\lambda\) 层超水平集，包含了 \(f\) 的层与 \(g\) 的层按 \((1-\theta),\theta\) 加权的和集。
  3. 套一维布伦–闵可夫斯基：对这个集合包含关系两边取长度，再用引理 3.18（注意 \((1-\theta)\cdot S\) 把长度缩放 \((1-\theta)\) 倍），得到每一层的长度不等式。
  4. 对 \(\lambda\) 积分（Fubini）：把每层长度的不等式从 \(\lambda=0\) 积到 \(\infty\)，左边变成 \(\int h\)，右边变成 \((1-\theta)\int f+\theta\int g\)。
  5. 算术–几何平均收尾：由 AM–GM，\((1-\theta)\int f+\theta\int g\ge\big(\int f\big)^{1-\theta}\big(\int g\big)^{\theta}\)。串起来即得结论。♦

现在把它迭代到更高维。

命题 3.20（高维 Prékopa–Leindler 不等式）设 \(0<\theta<1\)，\(d\ge 1\)，又设 \(f,g,h:\mathbb{R}^d\to[0,\infty)\) 是 \(\mathbb{R}^d\) 上下半连续、紧支撑的非负函数，满足 \[h\big((1-\theta)x+\theta y\big)\ \ge\ f(x)^{1-\theta}g(y)^{\theta}\qquad\text{对一切 }x,y\in\mathbb{R}^d.\] 则有 \[\int_{\mathbb{R}^d}h\ \ge\ \left(\int_{\mathbb{R}^d}f\right)^{1-\theta}\left(\int_{\mathbb{R}^d}g\right)^{\theta}.\]
证明. 对 \(d\) 作归纳。当 \(d=1\) 时，这正是命题 3.19。现归纳地假设 \(d>1\) 且结论已对所有更小的维数证得。定义一维函数 \(h_d:\mathbb{R}\to[0,\infty)\) 为 \[h_d(x_d):=\int_{\mathbb{R}^{d-1}}h(x_1,\dots,x_d)\,dx_1\cdots dx_{d-1},\] 并类似地定义 \(f_d,g_d\)。容易验证（利用 Fatou 引理）这些函数下半连续且紧支撑。又由在维数 \(d-1\) 应用归纳假设，可见 \[h_d\big((1-\theta)x_d+\theta y_d\big)\ \ge\ f_d(x_d)^{1-\theta}\,g_d(y_d)^{\theta}\qquad\text{对一切 }x_d,y_d\in\mathbb{R}.\] 再对其应用一维 Prékopa–Leindler 不等式，即得所求结论。♦
归纳怎么"降一维"：把空间切成薄片 \(\mathbb{R}^d\) 里一个点写成 \((x_1,\dots,x_{d-1},x_d)\)，把最后一个坐标 \(x_d\) 看成"层高"，前 \(d-1\) 个坐标看成每一层里的位置。
  1. 先沿前 \(d-1\) 维积分：固定层高 \(x_d\)，把 \(h\) 在这一整层（一张 \((d-1)\) 维薄片）上积分，得到一个只依赖 \(x_d\) 的一维函数 \(h_d(x_d)\)——它记录"第 \(x_d\) 层一共有多少质量"。\(f_d,g_d\) 同理。
  2. 每一层用归纳假设：取 \(x_d,y_d\) 两个层高。把这两层各自看成 \((d-1)\) 维问题，对它们用 \(d-1\) 维的 Prékopa–Leindler，就得到层质量之间的关系 \(h_d((1-\theta)x_d+\theta y_d)\ge f_d(x_d)^{1-\theta}g_d(y_d)^\theta\)。
  3. 再沿最后一维用一维结论：现在 \(f_d,g_d,h_d\) 是三个满足同样假设的一维函数，套命题 3.19 得 \(\int h_d\ge(\int f_d)^{1-\theta}(\int g_d)^\theta\)。而 \(\int h_d=\int_{\mathbb{R}^d}h\)（先分层积、再沿层高积，就是全空间积分），\(f,g\) 同理。归纳完成。♦
x_d （层高） 每张薄片：前 d−1 维，先积分得 h_d(x_d)
把 \(d\) 维空间按最后一坐标 \(x_d\) 切成一摞 \((d-1)\) 维薄片：层内用归纳假设，层间用一维结论，维数就从 \(d\) 降到了 \(1\)。

若在命题 3.20 中取 \(f:=1_A\)，\(g:=1_B\)，\(h:=1_{(1-\theta)A+\theta B}\)，便得到定理 3.17，于是布伦–闵可夫斯基不等式随之成立。

最后一步：为何代入指示函数就收工 \(1_A\) 是 \(A\) 的指示函数（在 \(A\) 内取 \(1\)、在外取 \(0\)），它的积分就是 \(A\) 的体积：\(\int 1_A=\mathrm{mes}(A)\)。
  1. 验证条件成立：要保证 \(h((1-\theta)x+\theta y)\ge 1_A(x)^{1-\theta}1_B(y)^\theta\)。右边只在 \(x\in A\) 且 \(y\in B\) 时为 \(1\)（否则为 \(0\)）；而此时 \((1-\theta)x+\theta y\in(1-\theta)A+\theta B\)，正是 \(h\) 取 \(1\) 的地方。所以右边为 \(1\) 时左边也为 \(1\)，条件满足。
  2. 代入结论：命题 3.20 给出 \(\int h\ge(\int 1_A)^{1-\theta}(\int 1_B)^\theta\)，即 \(\mathrm{mes}((1-\theta)A+\theta B)\ge\mathrm{mes}(A)^{1-\theta}\mathrm{mes}(B)^\theta\)——这正是定理 3.17。
  3. 串回主线：再由前面"代换魔术"那一步，定理 3.17 推出定理 3.16。至此布伦–闵可夫斯基不等式完全证毕。♦

习题

习题
  1. 3.4.1　证明定理 3.16 蕴含定理 3.17。
  2. 3.4.2　证明：当 \(A\) 为凸集、且 \(B=\lambda\cdot A+x_0\)（对某 \(\lambda,x_0\in\mathbb{R}^n\)）时，定理 3.17 中可取到等号。反之，若 \(A,B\) 是 \(\mathbb{R}^d\) 中非空、有界、开的子集，证明上述情形实际上是唯一能取到等号的情形。（当 \(A,B\) 仅为可测集时情况略微棘手，且当然只在相差一个零测集的意义下成立；进一步讨论见 [128]。）
  3. 3.4.3　设 \(A\) 为 \(\mathbb{R}^d\) 中的凸体。利用定理 3.17，证明其截面积 \(f(x_d):=\mathrm{mes}(\{x'\in\mathbb{R}^{d-1}:(x',x_d)\in A\})\) 关于 \(x_d\) 构成一个（适当意义下的）凹型函数，即 \(f^{1/(d-1)}\) 是 \(x_d\) 的凹函数。（原文于此页末截断，此处按布伦–闵可夫斯基的标准推论补足结论。）
习题 3.4.3 的思路提示（截面积的凹性） 把凸体 \(A\) 在高度 \(x_d=a\) 与 \(x_d=b\) 处切出两片截面 \(A_a,A_b\)（都是 \(\mathbb{R}^{d-1}\) 里的凸集）。由 \(A\) 凸，中间高度 \(\tfrac{a+b}{2}\) 处的截面包含 \(\tfrac12 A_a+\tfrac12 A_b\)。对这两片 \((d-1)\) 维截面用布伦–闵可夫斯基，就得到 \(f\big(\tfrac{a+b}{2}\big)^{1/(d-1)}\ge\tfrac12 f(a)^{1/(d-1)}+\tfrac12 f(b)^{1/(d-1)}\)，这正是 \(f^{1/(d-1)}\) 凹的中点形式。这说明"凸体的截面积随高度变化得很规整"，是布伦–闵可夫斯基最经典的几何推论之一。

返回 全书目录