带大家了解数学的纯粹存在证明

原文标题：《为什么计算高维凸体的体积非常困难？什么是数学的纯粹存在证明？》

从一个简单的方程说起，

显然，这个方程（至少）有一个解。因为，令 f（x）= x^5-x-13，有 f（1）=-13，f（2）=17。所以，在 1 和 2 之间必有一个 x 使 f（x）=0。

这是纯粹存在论证的一个例子，这种论证告诉你有什么东西存在（在此例中，是一个方程的解），但是没有说怎样去求它。如果方程是 x^2-x-13=0，就可以用一种全然不同的论证。二次方程求根的公式告诉我们，恰好有两个解，它甚至告诉我们解是什么它们是

但是对于五次方程就没有类似的公式。

这两种论证表现了数学的基本的两分法。如果要证明一个数学对象的存在，有时可以显式地证明，就是实实在在地描述那个对象；也可以间接地去证明，就是证明如果它不存在就会引起矛盾。

介于其间还有种种可能性，形成一个谱。如所说明过的，上一个论证只是说明，在 1 与 2 之间，方程 x^5-x-13=0 有一个解，但它也建议了一种方法来计算这个解，精确到如你所需。例如，如果需要精确到两位小数，可以取一串数∶1，1.01，1.02，…，1.99，2，然后在每一点估算 f 的值。就会发现，f（1.71）近似为 -0.0889，而 f（1.72）近似为 0.3337，所以其间必有一个解（计算表明，此解更靠近 1.71）。事实上还有更好的方法，例如牛顿方法去逼近一个解。对于许多目的，一个漂亮的解的公式不如计算或逼近这个解的方法更重要。而如果有了一个方法，它是否有用，还要看它运行快不快。

这样，在谱的一端有简单的定义一个熟悉对象的公式，它还可以容易地用来求出这个对象，而在谱的另一端，则有能够确立对象的存在性但不给出进一步的信息的证明，介乎其间的还有能够用以找出对象的算法，这些算法执行起来越快，其用处就越大。

和关于严格性的问题一样，如果一切其他条件都相同，则严格的论证优于不严格的论证。现在，（在直接和间接论证的问题上，也是）即使已经知道有间接存在证明，找到一个显式的有算法的论证仍然是值得的，其理由也是类似的∶寻求显式论证所花的力气时常导致新的数学洞察（不那么明显的是∶寻找间接论证的努力，有时也会带来新的洞察）。

纯粹存在证明的最著名的例子之一是关于超越数的。超越数就是那些不可能是任意整数系数的多项式方程的根的实数。有这种数存在的第一个证明是刘维尔在 1844 年给出的。他证明了有一个条件足以保证一个数是超越的，而且证明了构造出满足这种条件的数也是容易的。后来，各种重要的数如 e，π 都被证明是超越数，但是这些证明都很难。甚至到了现在，仍有许多数几乎肯定是超越数，但是就是证明不出来。

以上所说的证明全都是直接显式的。然后，到了 1873 年康托利用了他的可数性理论给出了超越数存在的完全不同的证明。他证明了代数数成一可数集合，而实数构成一个不可数集合。因为可数集合远小于不可数集合，这表明几乎每一个实数（虽然不一定是几乎每一个你真正见到的实数）都是超越数。

就这个例子而言，两种论证的每一种都告诉了我们另一种论证所没有告诉我们的事。康托的证明告诉了我们确有超越数存在，但却一个例子也没有给我们。

严格说来，这也不是真的∶可以指定一种方法把代数数排成一个单子，然后对这个单子应用康托著名的对角线论证法，就可以找到一个超越数，然而这样找出来的超越数基本上没有任何含义。

刘维尔的证明在一个方面要好得多，因为它给了我们一个方法，用直截了当的定义来构造出几个超越数。然而，如果只知道刘维尔的那种直接论证以及 e，π 为超越数的证明，就可能得到一个印象，即超越数是一种很特殊的数。有一种洞察在这些论证里完全见不到，但在康托的证明里面出现了，即典型的实数是超越数。

在 20 世纪的大部分时间里，高度抽象的间接证明大行其道，但是在最近的年代，特别是因为有计算机的发明，态度起了变化。近来，得到更多注意的是∶一个证明是否为显式的，如果是，又是否能导出有效率的算法。

无需说明，算法本身就是有趣的，这还不尽是由于它们给予数学证明的视角。我们简短地描述一个特别有趣的算法，它给出了一种计算高维凸体体积的方法。

一个图形

称为凸体，是指在 K 内任取两点 z 与 y，则连接 x 与 g 的直线段全在 K 内。例如，正方形和三角形都是凸的，而五角星就不是。这个概念可以直接推广到 n 维情况，n 是任意正整数。面积和体积的概念也能这样推广。

现在设在以下意义上指定了一个 n 维的凸体 K，即设有了一个运行很快的计算机程序，它能告诉我们每一个点（x_1，…，x_n）是否属于 K。怎样来估计 K 的体积呢？对于像这样的问题，最有力的方法之一是统计方法∶随机地取一点，看它是否属于 K，把对 K 的体积的估计建立在这个点落入 K 中的频度上。例如，想估计 π，就取一个半径为 1 的圆，把它放在一个边长为 2 的正方形里面，然后从这个正方形里随机地取许多点。每一个点属于此圆的概率都是 π/4，所以把落入圆内的点占点的总数的比乘以 4，就得到 π 的估计。

这个途径对于很低的维数是很容易起作用的，但是当维数很高时，却会遇到很大的困难。例如设我们想用这个方法估计 n 维球的体积。把这个球放在一个 n 维立方体里面，也去看这个点落入球内的频度。然而，n 维球的体积占 n 维立方体体积的比却是指数的小，这就是说，在球内找到一个点前，先要投的点的数目是指数的大。所以这个方法变得不切实用。

然而，因为还有一个计策可以绕过这个困难。可以定义一个凸体的序列 K_0，K_1，…，K_m，使每一个凸体都包含于下一个凸体内，而从想要计算其体积的凸体开始（即想计算 Ko 的体积），而终于一个立方体（即 K_m 是一个立方体），并且使得 K_i 的体积至少是 K+1 的体积的一半。于是对每一个 i，都要估计一下 K_(i-1) 与 K_i 的体积之比。这些比的乘积就是 K_0 与 K_m 的体积比。但是 K_m（立方体）的体积是知道的，所以就得到 K_0 的体积。

怎样来估计 K_(i-1) 与 K_i 的体积之比呢？只需简单地随机取 K_i 的点，并且看有多少落入 K_(I-1) 中。然而就是在这里，问题的微妙之处出现了∶怎样从知之不多的凸体里随机取点呢？在 n 维立方体里随机取点是容易的，只需要独立地选取 n 个随机数 x_1，…，x_n，而每一个 x_i 都在 -1 和 +1 之间。但是对于一个凸体这就非常不容易了。

有一个奇妙的聪明办法来回避这个问题。这就是小心地设计一个随机游动，从凸体内的一点开始，而在每一步，移动到的点可以从几个不多的可能性中随机选择。随着随机的游动步数越多，对于这点所到达的地方所知就越少。如果这个游动是适当定义的，可以证明，在不多几步以后，点的位置就是纯粹随机的了。然而，证明完非常难。

本文来自微信公众号：老胡说科学 （ID：LaohuSci），作者：我才是老胡