问题

什么是埃尔德什差异问题?

回答
埃尔德什差异问题(Erdős Difference Problem)是一个数论中的著名问题,它涉及到给定一个整数集合,我们能否找到一个子集,使得该子集的所有元素之差都落在另一个预先设定的集合中。这个问题的表述和研究有多种形式,其中最著名和最具有代表性的是由匈牙利数学家保罗·埃尔德什(Paul Erdős)提出的一个版本。

为了详细解释,我们将从几个方面展开:

1. 问题核心的直观理解

想象一下你有一堆数字(一个集合 $A$)。你想要从中挑出一些数字(一个子集 $B subseteq A$),并且你对这些挑出来的数字之间的“距离”(差值)有特定的要求。具体来说,你希望所有差值(例如 $b_i b_j$,其中 $b_i, b_j in B$)都必须落在另一个预先给定的数字集合 $D$ 中。

2. 最经典的埃尔德什差异问题形式

埃尔德什差异问题最经典的表述是关于集合 $A$ 的差集 $AA = {a_i a_j mid a_i, a_j in A}$。

问题可以概括为:

给定一个有限整数集合 $A$,是否可以构造一个子集 $B subseteq A$,使得 $B$ 足够“大”(例如,元素的数量远大于某个阈值),并且 $B$ 的差集 $BB$(通常我们排除零差值,即 $0 otin BB$)只包含一个或少数几个特定的值?

或者更具体地说,埃尔德什本人提出了一个非常具有挑战性的版本:

是否存在一个无限的整数集合 $A$,使得所有非零差值 $a_i a_j$ 都属于某个固定的有限集合 $D$?

(注意:这个无限集合的版本通常被称为 埃尔德什差集问题 或 埃尔德什的差集猜想,而“埃尔德什差异问题”有时也泛指与此相关的有限集合问题。)

3. 问题的背景和重要性

数论中的结构性问题: 这个问题考察的是整数集合的内在结构。如果我们能找到一个子集,其差值非常“受限”,这意味着这个子集具有某种高度的周期性或规律性,即使在更大的集合中这种规律并不明显。
与组合数学和图论的联系: 这个问题可以转化为图论中的问题。例如,将集合 $A$ 的元素视为图的顶点,如果 $a_i a_j in D$ (或 $a_j a_i in D$),则在顶点 $a_i$ 和 $a_j$ 之间画一条边。那么问题就变成寻找一个子图(或导出子图)是否存在,其所有边都属于一个特定的边集,并且顶点数很大。
与解析数论的联系: 为了解决这个问题,研究者们常常使用解析数论的工具,如傅里叶分析、加权和技巧等,来估计集合的大小和差集的性质。

4. 埃尔德什的贡献和相关结果

埃尔德什本人对这个问题进行了深入研究,并提出了许多重要的猜想和研究方向。

有限集合版本(埃尔德什塞迈雷迪定理的背景): 对于一个有限集合 $A$,如果我们要求其差集 $AA$ 的大小 $|Delta(A)|$ 满足 $|Delta(A)| le k$,那么 $|A|$ 的上界是什么?埃尔德什与塞迈雷迪(Endre Szemerédi)合作研究了这个问题,并导致了著名的 埃尔德什塞迈雷迪定理 (Erdős–Szemerédi theorem)。这个定理表明,对于一个包含 $n$ 个整数的集合 $A$,其差集的大小 $|Delta(A)|$ 要么很大,要么非常小。具体来说,如果 $A$ 是一个 $n$ 个整数的集合,那么 $|AA| ge c frac{n^2}{log n}$,其中 $c$ 是一个常数。这个结果表明,一个集合的差集不太可能非常小。换句话说,如果你想要一个子集的差集非常集中,那么这个子集本身相对于原始集合来说是“非常稀疏”的。

无限集合版本(埃尔德什差集猜想): 埃尔德什本人猜想,不存在一个具有自然密度(natural density)的正整数集合 $A$,使得 $AA$ 只包含有限个值。 自然密度是指集合 $A$ 中小于 $N$ 的元素数量除以 $N$,当 $N o infty$ 时的极限。换句话说,埃尔德什认为,任何“足够大”的整数集合(在自然密度意义上),其差集一定会包含“很多”不同的值。

5. 研究的进展和相关定理

莫里斯·博姆(Morris–Bocherer)定理: 这个定理在一定程度上解决了埃尔德什的无限集合猜想。他们证明了,如果一个集合 $A$ 具有正的自然密度,那么其差集 $AA$ 一定包含无限多个素数。这意味着差集不可能只包含一个或有限个值(除非这个集合本身非常平凡,例如只包含一个数)。

有限集版本研究的进展: 对于有限集,研究者们在限制差集大小的条件下寻找最大的子集大小。例如,如果差集 $AA$ 只包含一个非零值 $d$,那么集合 $A$ 的形式必须是 ${a_0, a_0+d, a_0+2d, dots, a_0+(k1)d}$,即一个等差数列。对于差集只包含几个值的情况,也有很多研究。

多项式差集(Polynomial Difference Sets): 埃尔德什也研究过更一般的情况,即差集中的元素是否可以通过某个多项式生成。

6. 困难之处

反证法的运用: 很多研究方法是通过假设一个差集非常小的集合存在,然后通过复杂的论证来导出矛盾。
指数和的估计: 需要精确地估计由集合元素构成的指数和的增长速度,这通常涉及到解析数论的深刻技巧。
对结构的要求极高: 要想让差集很小,集合本身的结构就必须非常特殊,例如形成一个等差数列。但如果集合很大且没有这样强的结构,差集就会变得很大。

7. 举例说明

简单例子(差集非常小): 设 $A = {1, 2, 3, 4}$。
$AA = {11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44}$
$AA = {0, 1, 2, 3, 1, 0, 1, 2, 2, 1, 0, 1, 3, 2, 1, 0}$
去掉零和重复项,非零差集为 ${3, 2, 1, 1, 2, 3}$。这个集合相对较小。

等差数列(差集只有一个非零值): 设 $A = {2, 5, 8, 11}$。这是一个公差为 $3$ 的等差数列。
$AA = {0, pm 3, pm 6, pm 9}$。非零差集为 ${pm 3, pm 6, pm 9}$。
如果 $A = {2, 5, 8, 11, 14}$,公差仍然是 $3$。
$AA = {0, pm 3, pm 6, pm 9, pm 12}$。
如果一个集合是等差数列 ${a, a+d, a+2d, dots, a+(k1)d}$,那么其差集是 ${m cdot d mid (k1) le m le k1}$。这个差集的大小是有限的。

反例(差集很大): 设 $A = {1, 2, 4, 8, 16, dots, 2^{n1}}$ (一个几何数列的前 $n$ 项)。
这个集合的差集会非常大。例如,差值 $2^i 2^j$ 会产生很多不同的值。

总结

埃尔德什差异问题核心在于探究一个整数集合的子集,其元素之差是否能被限制在一个非常小的集合中。这个问题表面看似简单,实则涉及深刻的数论原理。它连接了数论、组合学和分析学,并催生了如埃尔德什塞迈雷迪定理这样的重要结果。虽然埃尔德什本人提出的关于正自然密度集合差集猜想在很大程度上被证明是正确的,但关于有限集合在不同限制下的精确界限,以及其他变种问题,至今仍是活跃的研究领域。

这个问题的重要性在于它揭示了整数集合的结构与它们之间差值分布之间的深刻联系,以及这种联系在数学的许多分支中的普适性。

网友意见

user avatar

这是一个值得科普的好问题。

2015 年 9 月 17 日,陶哲轩 宣布破解 埃尔德什差异问题(the Erdős Discrepancy Problem)(论文地址:

arxiv.org/abs/1509.0536

),实在是可喜可贺。

埃尔德什差异问题 当然是一个很难的问题。从提出者和破解者的履历便可见一斑:

  • Terence Tao 有多厉害,相信大家都知道:12 岁获得 IMO 金牌,31 岁获得菲尔兹奖等,都是极其厉害的成就。当然,让我印象深刻的,还有这么一段描述:“陶哲轩的数学生涯 也并非一帆风顺。9岁多时,他未能入选澳大利亚队,去参加国际数学奥林匹克竞赛。”
  • 但我们更应该知道,Paul Erdős 也是一个很厉害的人,至少,从成就上来说,他可能比现在的 Tao 更厉害: 他发表论文高达 1475 篇,为现时发表论文数最多的数学家(第二位为 欧拉);曾和 511 人合写论文。如果你看过《我的大脑敞开了》或《数字情种》,你一定会对这个神奇的数学家留下深刻的印象。

然而,与两人的光辉履历形成鲜明对比的是,“埃尔德什差异问题” 从 问题描述 来说,却是相当简洁且便于理解的——通过适当的解释,只要是小学毕业了的人,都可以理解这个问题在说什么。

埃尔德什差异问题 的描述是这样的:

  • 对于任意无穷数列,

接下来,我尝试用 小学生可以理解的方式 来解释这个问题:

(1) 首先,有一个无限长的数列 ,数列中的每个数,都是由 1 和 -1 组成的。

  • 比如数列 A:1,-1,-1,-1,1,-1……就是一个满足条件的数列。

(2) 接下来,我们要取数列的某些项,这些项在数列中的位置都是某个自然数 N 的倍数,并且是从头开始的连续几个倍数(即第 N 、2N、3N……项)。

  • 比如,我们可以取数列的第 1、2、3、4 项(在 A 中分别为 1,-1,-1,-1),因为它们都是 1 的倍数,且为前 4 项;或者取数列的第 2、4、6 项(在 A 中分别为 -1,-1,-1),因为‘它们都是 2 的倍数,且为前 3 项。但我们不能取数列的第 1、2、4 项 或者 第 4、6、8 项,因为它们不是【从头开始】的【连续几个倍数】。

(3)对于(2)中的每种取法构成的新的数列,我们可以求该数列所有项的和。我们要证明的命题是:无论原来的无穷数列长什么样,我们都可以找到一种取法,使得新数列的和的绝对值大于任意给定的自然数 C

——————————

遇到这样的问题,一个很自然的思路是:试试 C 比较小的时候,我们是否可以给出证明。

  • 当 C=0 时,结论是显然的。

我们只要取数列的第 1 项就可以,它的绝对值肯定大于0。

  • 当 C=1 时,结论就不那么显然了。

我们要证明的是,对任意满足要求的数列,

我思考了这个问题,给出了自己的解法,并认为这可以成为一道中学数学竞赛题。为了便于理解,解答过程不使用超过初中的数学。

**********

证明:

用反证法。假设存在一个数列,满足

于是我们有两个简单的推论:

  1. 对任意正整数 d,数列的第 d 项和第 2d 项的和为 0——反之,它们的和必为 2 或-2,矛盾;
  2. 对任意正整数 d,数列的第 2d-1 项和第 2d 项的和为 0——反之,设 k 为最小的不满足该条件的数,即第 2k-1 项和 第 2k 项的和为 2 或 -2,则数列的前 2k 项的和为 2 或 -2,矛盾;

不失一般性,设数列第 1 项为 1。

  • 由推论2 => 第 2 项为 -1;
  • 由推论1 => 第 4 项为 1;
  • 由推论2 => 第 3 项为 -1;
  • 由推论1 => 第 6 项为 1;
  • 由推论2 => 第 5 项为 -1;
  • 由推论1 => 第 10 项为 1;
  • 由推论2 => 第 9 项为 -1;

考虑数列的第 12 项:

由于数列的第 6 项为 1,由推论1 => 第 12 项为 -1;

但此时数列的第 3、6、9、12 项分别为 -1,1,-1,-1,其和为 -2,与题设矛盾!

故假设不成立,结论成立。

**********

好了,通过一阵折腾,我们证明了 C=1 的情况是成立的。

那么,C=2 的时候,会是什么情况呢?

  • 2014 年 2 月,英国利物浦大学的 Alexei Lisitsa Boris Konev,利用计算机,几近于暴力验证的办法,验证了 C=2 的特殊情况。但是,计算机验证过程产生数据达到 13G,甚至超过整个Wikipedia 网站的总数据量。

C=3 呢?

  • 相同的计算机算法,没有给出结果……

——————————

然后,陶哲轩登场了!

他证明了一个更强的命题:

  • 对于任意无穷数列,

这段话是什么意思呢?

首先,数列不再局限于由 1 和 -1 组成了,只要满足 即可,

其中 H 代表

希尔伯特空间

当然,对于非数学系的同学来说,要理解希尔伯特空间可能有些困难。

为了让高中生也能有一个概念,我们取一个该空间的子集:复数集

即,对于数列的每一项,只要满足模等于 1 即可。

比如,数列可以长成这样: ……

在这种情况下,Tao 证明了:

  • 我们总可以找到满足要求的子数列,使得它们的和的模大于任意一个自然数

现在,你是不是感觉到,这个结论好像真的很强?

然而我们可不能忘记,希尔伯特空间比复数集还要大得多得多。

对了,刚才忘了说,陶哲轩从接触这个问题,到最终发表论文,只用了不到两周:

他并没有专门去攻克埃尔德什差异问题,只是在研究其他问题时,发现恰好和这个问题有关,于是“顺手”证明了一下而已。

(注:这其实是一个略带夸张的说法,评论区

@chen ke

指出,Tao自己在这篇paper里就说明了这个结果是基于polymath project的成果,而他本人就参加了这个项目)

所以,如果陶哲轩的证明最终被认为是正确的,

那么对于我们而言,除了默默围观和赞叹,

还能做什么呢?

【完】

********************

【如需转载,请联系作者】

类似的话题

  • 回答
    埃尔德什差异问题(Erdős Difference Problem)是一个数论中的著名问题,它涉及到给定一个整数集合,我们能否找到一个子集,使得该子集的所有元素之差都落在另一个预先设定的集合中。这个问题的表述和研究有多种形式,其中最著名和最具有代表性的是由匈牙利数学家保罗·埃尔德什(Paul Erd.............
  • 回答
    在奥斯曼帝国的统治下,埃及经历了漫长而复杂的变迁,这种变迁既带来了新的秩序和文化影响,也保留了古老的传统和身份。这段时期,从1517年苏丹塞利姆一世征服埃及,到1798年拿破仑登陆埃及,将近三个世纪的时间里,埃及作为奥斯曼帝国的一个省份,其面貌与之前马穆鲁克王朝时期以及之后的发展都有着显著的不同。政.............
  • 回答
    要理解埃尔多安的“终极目标”,就不能简单地将其视为一个孤立的政治人物,而是要将其置于土耳其复杂的地缘政治、历史遗产以及国内社会经济的宏大图景中去审视。他的目标并非一成不变,而是随着国内外形势的演变而不断调整和深化,但其核心始终围绕着提升土耳其的国际地位、巩固国内的权力基础,以及重塑土耳其的国家认同。.............
  • 回答
    有关日本将引入埃博拉病毒的目的和安全风险的问题,需要澄清的是,目前 没有公开信息或官方公告表明日本计划引入埃博拉病毒,无论是出于研究、治疗还是其他任何目的。埃博拉病毒是一种极其危险的病原体,其感染性强、致死率高,即使是最高级别的生物安全实验室也需要极其严格的防护措施来处理。因此,任何国家引入此类病毒.............
  • 回答
    现代埃及人与古埃及人之间,与其说是一种直接的传承关系,不如说是一种复杂的、多层次的联系,其中既有历史的根基,也有现实的演变,更夹杂着文化、身份认同的交织与碰撞。如果非要用一个词来形容,那或许是“根与枝”的关系——现代埃及人是这片土地上生长的枝叶,而古埃及人则是那深埋地下的根系,虽然形态迥异,却一同汲.............
  • 回答
    要说埃及人肥胖的“根本原因”,这事儿可复杂了,不是一两句话就能说清的。要真想弄明白,得从好几个方面掰开了揉碎了看。首先,咱们得聊聊饮食习惯的巨变。以前的埃及,大家吃什么?主要是接地气的、自己种的、相对健康的食物,比如蔬菜、豆类、全麦面包、还有一些鱼和肉。这些食物营养均衡,而且制作过程也比较简单。但是.............
  • 回答
    你好!能从埃及带回项链,这真是太棒了!埃及历史悠久,文化底蕴深厚,很多首饰都非常有故事和象征意义。你想让我帮你看看这条项链,我非常乐意!不过,我毕竟是AI,没办法亲眼看到你的项链,所以为了能给你更详细的解答,你能否尽量多地描述一下它呢?哪怕是一些你觉得无关紧要的小细节,也可能对我判断有很大帮助。请你.............
  • 回答
    华纳兄弟公司(Warner Bros.)确实暂停了与演员埃兹拉·米勒(Ezra Miller)的未来合作,这一决定并非空穴来风,背后牵涉到米勒近年来一系列备受争议的行为和法律问题。 简单来说,是由于米勒频繁的法律麻烦和扰乱公众秩序的行为,导致华纳方面对其的信任度急剧下降,为了保护公司声誉和品牌形象,.............
  • 回答
    关于埃尔克森(埃神)和高拉特(高指导)的归化问题,确实在当时引起了不小的争议,反对的声音也并非空穴来风。要理解这些反对意见,咱们得从几个层面来分析,不能光看表面,得挖深一点。首先,是“血统论”和民族认同的根深蒂固。这是最容易被提及,也最触动一部分国人情绪的理由。在中国文化中,尤其是传统观念里,“国籍.............
  • 回答
    在《刺客信条》系列探寻古老文明的脚步从未停歇,继埃及的宏伟金字塔和希腊的辉煌神话之后,下一站的风景会是哪里,这个问题无疑牵动着无数玩家的心弦。如果让我来猜想,我个人非常倾向于将目光投向那个同样拥有辉煌历史、神秘传说和独特魅力的文明——古罗马的鼎盛时期。为什么是古罗马?让我来细细道来。首先,历史的连续.............
  • 回答
    关于为什么像埃博拉和拉沙这样的致命病毒会频繁地在非洲出现,这是一个复杂的问题,涉及到地理、生态、社会以及历史等多个层面的因素。与其说“起源于非洲”,不如更准确地说,非洲大陆由于其独特的环境和人类活动模式,为某些病毒的传播和爆发提供了“温床”或者说“更容易暴露”的条件。下面我将从几个关键方面来详细阐述.............
  • 回答
    要理解埃及阿拉伯语、黎凡特阿拉伯语和标准阿拉伯语之间的区别,以及它们与古埃及语、阿拉米语的联系,我们得从头说起,就像讲一个悠久的故事。想象一下,阿拉伯语就像一片广袤的土地,而标准阿拉伯语(MSA)是这片土地上最宏伟、最庄重、最被尊崇的那部分。它如同古老的都城,拥有优雅的建筑、精深的学识,是文学、宗教.............
  • 回答
    咱们得聊聊《JOJO的奇妙冒险》里的几位巨头——迪奥、承太郎、二乔(乔瑟夫·乔斯达)、阿布德尔和波鲁那雷夫。要说他们凑一块儿聊天,用的啥语言,这事儿可得掰开了揉碎了说,因为这背后牵扯到角色设定、故事背景,甚至还有点漫画本身的“默契”在里头。首先,咱们得明确一个基本点:他们说的不是同一种语言,但交流起.............
  • 回答
    雷杰普·塔伊普·埃尔多安,土耳其政坛一位极具影响力的人物,他的名字与土耳其近二十年的政治走向紧密相连。从一个草根出身的政治家,一步步攀登至土耳其最高权力巅峰,埃尔多安的崛起本身就是一部充满戏剧性的史诗。他的过往与崛起埃尔多安的早年生活并不算显赫。他出生于土耳其最大城市伊斯坦布尔的一个普通家庭,年轻时.............
  • 回答
    埃及与英国在1821年至1881年间对苏丹长达半个世纪的殖民统治,给这片广袤的土地留下了深刻且至今仍在影响苏丹发展的复杂印记。这段时期并非简单的统治与被统治,而是一系列旨在巩固自身利益的政策和实践,这些做法的累积效应塑造了苏丹的政治、经济、社会以及文化格局,其影响之深远,甚至可以说决定了苏丹日后许多.............
  • 回答
    在谈论与埃博拉病毒“同级”或“更强大”的病原体时,我们首先需要明确“强大”的定义。这个词可以从多个维度来解读: 致病性(Virulence): 指的是病原体引起疾病的严重程度,包括症状的凶险性、并发症的发生率以及最终的死亡率。 传染性(Transmissibility): 指的是病原体在人群.............
  • 回答
    埃及,一个充满古老神秘与灿烂文明的国度,吸引着无数旅人前往探索。但要在这片土地上拥有一段美好的旅程,确实需要一些细致的准备和周全的考量。下面就为你细细道来,去埃及旅游,你需要注意些什么。行前准备:打好基础,事半功倍 签证: 这是第一步,也是至关重要的一步。大部分国籍的游客需要提前办理埃及签证。你.............
  • 回答
    “埃及伪史考”这个标题本身就带有强烈的指向性,暗示作者认为埃及的历史是虚假的、被伪造的。这样的出发点已经预设了结论,而非客观的探究。在一篇严谨的学术探讨中,这样的标题容易引起读者反感,并被视为缺乏学术中立性。潜在的问题可以从以下几个方面来剖析:1. 标题的预设性与目的性: “伪史”的定义模糊且主.............
  • 回答
    克里斯·埃文斯,这个名字,相信很多朋友都不会陌生。从那个意气风发的“美国队长”到如今沉稳中带着一丝不羁的“斯科特·普利斯”,他的银幕形象早已深入人心。而围绕着他的,除了那些深入骨髓的角色,还有一个永恒的话题——他的长相到底属于什么类型?要给克里斯·埃文斯的长相下一个绝对的定义,其实挺难的。他身上糅合.............
  • 回答
    去埃及留学一年,说实话,准备行李确实是个挺费心思的事儿,毕竟你将在一个完全不同的文化和生活环境下度过一年。我想跟你分享一些我总结的经验,希望能帮你更实在地准备:衣物类: 轻便透气的夏装为主,但也要备几件长袖。 埃及大部分地区常年炎热,尤其是夏天,白天温度很高。所以T恤、短裤、薄长裤、裙子是你衣柜.............

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有