原创近60年的“向日葵猜想”获得重大进展,完整的解决方案已经在望

时间:2019-10-28 10:55:23   热度:37.1℃   作者:网络

原标题:近60年的“向日葵猜想”获得重大进展,完整的解决方案已经在望

一个看似简单的数学问题困扰了研究人员近60年,它就是“向日葵猜想”。这个问题最早是由匈牙利数学家保罗·埃尔德斯和英国数学家理查德·拉东于1960年提出的,被称为“向日葵引理”。引理这个术语本质上是指“迷你定理”,它是指已经被证明是正确的,但还不足以将其完全称为定理的程度。

向日葵猜想并不涉及任何植物生物学,但它却是关于物体集合的数学问题。取一些数字集,看看它们之间的共同点。如果每一对集合有相同的公共点,我们就认为这些是向日葵的中央圆盘。每一组剩下的部分叫做向日葵的花瓣,所以集合的数目就是花瓣的数目。从数学上讲,向日葵的中央圆盘最少可以包含0个点,数学向日葵可以全是花瓣,没有盘,不像真正的向日葵。

如果你考虑平面xy上的点的集合,也很容易形象化这个猜想。首先要确定你计划包含在每个集合中的固定数量的点,然后随机绘制圆环,以便每个圆环或集合包含该数量的点。如果循环重叠也没关系,所以有些点可能会在不止一个集合中出现,就像文氏图中的交点。

如果你绘制了许多包含大量点的圆环,大多数环就会像一团乱麻一样重叠并纠缠在一起,但是数学家保罗·埃尔德斯和理查德·拉东却做出了一个预测,其中必然会出现一个微妙的结构: 三个或三个以上的集合会在完全相同的点的子集上部分重叠,并且没有一个集合会与其他集合重叠。

如果你要删除这些点的公共子集,这三个集合就会围绕着一个空隙排列,彼此完全分离,就像向日葵黑暗中心周围的花瓣一样。基于此数学问题的研究,最简单的向日葵被认为具有这样的特性:三个集合彼此互不重叠或者说不和任何其他集合重叠,这些岛状物被称为“不相交”集。

他们推测,随着更多环的绘制,向日葵不可避免地出现:要么是不相交集,要么是以正确的方式重叠的集合。向日葵猜想是称为拉姆齐理论的更广泛数学领域的一部分,该理论研究随着随机系统变大,秩序是如何开始出现的,而完全的无序是不太可能的。

两位数学家希望确切地知道需要多少个集合,每个集合里有多少个点才能确保数学向日葵的形成。他们在解决这个问题上迈出了一小步,建立了一个参数w,代表每个集合中的点的数量。然后两人证明了需要大约w的w次方的集合,才能够确保向日葵特性的出现。因此如果您希望每个集合包含100个点,那么他们证明您需要100的100次方个集合才能保证向日葵的出现。

同时他们猜想向日葵出现的集合所需的实际数量要比W的W次方小得多,它更像是一个常数的w次方,然而他们却找不到一种方法来证明他们的直觉是正确的。事实上他们并不是唯一试图验证猜想的人,在他们首次提出猜想之后和60年后找到新的证据前,只有两位数学家在该问题上取得了一点渐增性进展,一次是在1997年,一次是在今年年初。只是虽然他们简化了这项结果背后的方法,却无法完善两位数学家证明的基本界限。

相比之下,新的证明是一个重大的进展。由数学家和计算机科学家组成的四名研究人员小组,通过将问题分解成两种不同的场景来实现这一进步。这四名研究人员分别来自加州大学圣迭戈分校的沙查·洛维特、普林斯顿大学的瑞安·阿尔维斯、北京大学的吴克文和哈佛大学的张家鹏共同撰写了该研究报告。

在第一个更简单的场景中,他们考虑了当集合有大量重叠时会发生什么,这使得理解向日葵何时必须出现相对容易。当一个元素集合中的所有元素都属于一个大集合时,你就可以利用这个结构来找到向日葵。研究人员首先要问的是,在这个系统中,是否有一组点在很大一部分集合中是公共的。一旦他们确定了这样的一组点,他们就会把对向日葵的搜索限制在所有集合中包含这组点的的一部分。他们以这种方式继续,改进他们的搜索,使得系统搜索限制在总集合中越来越少的部分,这些集合会有越来越多的共同点,这种修剪一直持续到他们找到向日葵。

在第二种情况下,也就是更困难的情况下,他们分析当数据集没有太多重叠时会发生什么。在这种情况下,生成向日葵的最可能的方法是使用三个不相交的集合。但是,要证明三个完全独立的集合隐藏在大量轻度重叠的集合中并不容易。这就是与计算机科学的联系。几年来,两位合著者洛维特和张家鹏一直试图使用计算机科学家用来研究一种叫做布尔函数的程序的工具来分析向日葵问题。这些函数对一系列的位1和0进行运算,并在最后输出单个位,对应计算语句是否真(1)和假(0)。例如,如果布尔函数的至少一个输入位为1,则可将其编程为输出1;如果输入的任何一个都不为1,则可将布尔函数输出为0。

三年前洛维特和张家鹏意识到,可以用相同的方式来考虑在一组轻度重叠的集合中是否存在三个不相交的集合。首先为特定集合中的每个点分配一个标签: 如果它仅包含在一个集合中,则为1;如果不包含则为0。如果每个输入点都是1,那么布尔函数将输出1 (真),这意味着集合中的每个点都只在那个集合中,使得集合不相交。因此,一个“真”的输出结果表明,您找到向日葵的条件是正确的。

通过严格地证明这种对应关系,研究人员应用了有关布尔函数的广泛知识,来解决向日葵资源不足的问题。他们证明了(log w)的w次方集足以产生向日葵。他们的新结果并没有完全证明集合的猜想数(常数的W次幂)足以保证有向日葵的产生。但相比59年前两位数学家的研究,他们的最新结果要好一个数量级别, 大约是两人预测的产生向日葵所需要的集合的数量。

在经历了半个世纪的失败后,这项新研究表明,一个完整的解决方案已经在望。它还进一步解释了特殊形状在随机数学领域扎根的必然性。

上一篇: 这几个家居旺财风水的小秘诀,你一定要知道...

下一篇: 巡察微故事|社区虚报冒领77岁老人劳务费...


 本站广告