有两个数学家 Busemann 和 Petty 在 1956 年提出了这样的一个猜想： 如果有两个关于原点对称的凸体，其中第一个和任意一个过原点的（余维为 1 的）超平面的交集的大小都比第二个和同一超平面的交集大，能不能说明第一个凸体比第二个大？ 在二维这是显然的，所以这个猜想主要是关于高维情形的。 大部分数学家都会直觉地猜测说这个猜想是对的，但是到了 1975 年，另外两个数学家 Larman 和 Rogers 给出了当维度大于 12 时的一个非常复杂的反例，大出人们意料之外。 又过了十年，1986 年，Ball 证明了一个简单而漂亮的定理： 任何中心放在原点的单位立方体，无论维度为何，和过原点的超平面的交集都不大于 √2。 这个定理立刻导出了 Busemann – Petty 猜想的简单反例，因为当维度大于 10 的时候，中心放在原点的体积为 1 的球和超平面交集是大于 √2 的，所以 Busemann – Petty 猜想在 10 维以上都是错的。 这个结果过了一段时间被 Giannopoulos 和 Bourgain 独立地改进为 7 维以上都是错的，后来 Papadimitrakis 和 Gardner 又独立地把它改进为 5 维以上都是错的，这样只剩下 […]
Author: 木遥
我们都是谁的子孙？
刚刚看到一篇微博，说加州一名小姑娘在做家庭作业时发现美国除了第八任总统范布伦之外所有的总统都有一个共同的祖先：1215 年签署大宪章的英王约翰。这条消息迅速激起了各种惊讶和感叹的声音，从权力在民主社会的隐秘世袭到共济会的阴谋论，不一而足。 但是只要稍微多想一想，就会发现「美国的所有总统都有共同的祖先」这件事，不但不应该令人惊叹，反而应当是显然的事。事实上，随便从美国选取几十个人，他们在若干年前都几乎一定会有一位相同的祖先，这是很容易计算出来的。 让我们简单估算一下，不考虑跨种族通婚的因素：一个人的父母辈有两人，祖父母辈有四人，依此追溯，第 n 代祖先会有 2^n 个人。以平均 20 年一代人来计算，一个现代美国人在 1215 年的祖先共有 2^40 个人，也就是一万亿人！很显然，当时全体白人的总数也远远小于这个数字，所以事实上当时的每个人只要后来没有绝嗣，都几乎一定是这个人的祖先，而且在他的家谱的不同位置重复出现过很多次。——这听起来很荒谬，但是是真的。 既然如此，每个现代美国人在 13 世纪的白人祖先都几乎构成了当时白人的全体，那他们的交集非空，一点也不值得奇怪。 上面的计算当然过于粗略，更准确量化的数学结论要用到不太初等的概率论计算。1998 年，耶鲁大学统计系的 Chang 在一篇论文里精细地估算了这个问题：在一个人数为 N 的族群里，假定交配关系是随机的，大约会在多少代人以前出现一个人是今天所有人的共同祖先？答案是 log_2 N 代，并且这个估计的方差很小。具体的证明相当困难，但是结论却是简单而符合数学直觉的：这个数字恰好是每个人的全体祖先回溯而上扩散到全体人群的时间。 但是这当然是个不太现实的答案。如果把它直接套用在今天人类的总数上，会算出今天全体人类大概在 32 代人之前就有一个共同的祖先，即大约六七百年之前。我们很难想象在宋元时期会有一个人既是今天所有中国人的祖先，也是所有美国人的祖先。（如果是真的话，他大概一定就是传说中把精子洒遍欧亚大陆的成吉思汗了吧。） 很显然，这里的问题在于那个交配关系完全随机的假设。即使在近代，一个人也不可能真的和世界上随机某处的人结为伴侣，更不用说古代了。跨地域的婚配在人类历史上相当罕见，跨大洲就更困难。但是这在数学模型上并不难修正。2004 年 MIT 的 Rohde 和他的合作者们在一篇论文里考虑了区域限定的因素，发现即使加以苛刻的移民限制，比如每一代人里只有极少比率的人会移民到别的区域，共同祖先事实上也还是离我们并不遥远。经过他们的估算和计算机的辅助验证，全人类的最近的共同祖先即使按照非常保守的估计，也大约出现在不早于公元前 1500 年左右，即商朝初期的时代。 有趣的是一个进一步的推论。很显然，这位「人类共同祖先」的父母和祖父母等祖先们当然也还是我们的共同祖先。从此人开始越向上追溯，共同祖先就会越来越多，直到上溯到某一时刻，共同祖先会塞满当时的全体人类。这个时间点被称为「恒同始祖点」。按照上面那篇论文的估计，这个时间大约在公元前五千年左右。在那时，地球上的每个后来没有彻底绝嗣的人类都是我们今天每个人的祖先。——这句话很拗口，而且非常违反直觉。 需要说明的是，这里所有关于祖先的讨论都是把父系母系均计算在内的。如果我们只定义父系先祖为祖先（就像大多数父系社会的家谱那样），情况就大为不同。因为一个人的父母混合祖先在上溯时人数会爆炸性增长，而纯粹的父系祖先始终只有一个人，所以父系树的交汇比父母祖先树的交汇要困难得多。在这种设定下，我们仍然可以考虑同样的问题：什么时候开始存在一个最近的全人类的共同的父系祖先？ 有趣的是这个问题所对应的数学模型反而比上一个要简单，结论也要弱上许多。数学家很早就知道，如果一个种群的人口为 N，那它们的共同的父系祖先平均而言大约会在 2N 代以前出现（和上一条结论相比，这是一个早得多的时间）。但是这个变量的方差相当大，以至于很难精确估计。在这种情况下，基因生物学而非数学才是更有效的工具。因为每个人都会只从父亲那里得到 Y 染色体，通过对今天人类的 Y 染色体的抽样分析，基因学家可以估计出这个人的时代。最近的研究结果是他大约存在于十四万年之前。 他在文献中一般被称为「Y 染色体亚当」。很显然，这是借用了圣经的典故。但是这个典故容易带来某种误解，仿佛他是人类历史上的「第一个男人」。事实上，他只是当时人类中普通的一员，只不过除了他之外同时代所有别的男人都在后来的漫长历史中的某一刻断绝男性后代了而已。 同样的分析也可以用来估计人类的最近的共同母系祖先，这时需要采用的遗传学工具不再是染色体，而是线粒体 DNA。这位母系始祖被估计出现在公元前十五到二十五万年之间。她被称为「线粒体夏娃」。令人遗憾的是，她和「Y 染色体亚当」素不相识，而且两人隔了几万年。（不过他们至少大概都生活在同一片非洲大陆上。） （一个有趣的问题是为什么夏娃比亚当早出现这么久。这是由于原始社会中男女的生育特点不同，在父系社会，一个健康女性的女性后代的数目基本上是恒定的，而一个健康男性的男性后代数目却有巨大的起伏。粗略地说，这意味着不同的人的母系树比父系树更难交汇在一起。） 当然，所有这些讨论要么是基于概率论的数学推导，要么是尚不完全成熟的基于基因理论的假说。并且很显然它们都不能排除某些极小概率的极端情况的存在，比如这世界上存在着一小群人有史以来就与世隔绝，那他们当然无法被计算在内。不过，仅仅是抽象地想象一下「全人类的共同始祖」的面貌，也已经是颇为有趣和超现实的事了。
J-L 定理，以及为什么一个立方体相当于一个球壳
Johnson–Lindenstrauss 定理是我在今晚的一个学术报告里听说的一个非常令人惊讶的定理。简单说来，它的结论是这样的：一个一百万维空间里的随便一万个点，一定可以几乎被装进一个几十维的子空间里！ 严格说来是这样：在 M 维空间中的 N 个点，几乎总是被包含在一个 D 维子空间里的。这里的 D 按照直觉应当等于 N 的阶，可是实际上我们只需要让 D 是 log(N) 的阶就可以了。这里「几乎被包含在」的确切含义是它在这个子空间上的投影几乎是等距的（允许有一个 ε 的误差，而常数 D/log(N) 就依赖于 ε）。很显然，这件事情在高维数据降维时有极重要的意义。 这个定理的证明很初等。它依赖于这样的一个基本概率事实：一个随机的 M 维单位向量到一个随机的 D 维子空间上的投影的长度几乎一定约等于 D/M。这件事情本身也有点不同寻常，虽然它可以通过简单的计算来证实。这是概率论计算中常常出现的由于高维度而导致的反直觉现象的一例。 这让我想起另一个高维度导致的悖论，是我在学大数定律时了解到的。在 M 维单位立方体中随机取一个点，当 M 充分大时根据大数定理容易算出这个点到立方体中心的距离几乎一定等于 √(M/3)/2。于是这就说明 M 维实心单位立方体几乎就完全位于一个半径为 √(M/3)/2 的球壳上。这里没有任何捣鬼之处，事实上就是如此。