塞迈雷迪定理
此条目需要精通或熟悉数学的编者参与及协助编辑。 (2019年6月17日) |
在算术组合学中,塞迈雷迪定理是个关于自然数集子集中的等差数列的结论。1936年,艾狄胥和图兰·帕尔猜想[1]:若整数集 A 具有正的自然密度,则对任意的正整数 k, 都可以在 A 中找出一个 k 项的等差数列。塞迈雷迪·安德烈于 1975 年证明了此结论。
定理叙述
编辑若自然数集的子集 A 满足
则称 A 具有正的上密度。塞迈雷迪定理断言,若自然数集的一个子集具有正的上密度,则对任意的正整数 k, 该子集都包含无穷多个长为 k 的(公差不为 0) 的等差数列。
定理另有一个等价的有限性叙述(即不牵涉“无穷”的):对任意的正整数 k 和实数 都存在正整数
使得 {1, 2, ..., N} 的每个至少 δN 元的子集,都包含长为 k 的等差数列。
定义 rk(N) 为 {1, 2, ..., N} 的子集当中,不包含长为 k 的等差数列的最大子集的大小。塞迈雷迪定理给出渐近上界
换言之,rk(N) 随 N 的增长慢于线性。
历史
编辑范德瓦尔登定理是塞迈雷迪定理的先驱,其于 1927 年获证。
塞迈雷迪定理中, k = 1 和 k = 2 的情况显然成立。 k = 3 的结论关乎萨莱姆-斯宾塞集(不包含 3 项等差数列的整数子集)的大小。1953 年,克劳斯·罗特[2] 利用类似哈代-李特尔伍德圆法的方法,证明了 k = 3 的结论。1969 年,塞迈雷迪·安德烈[3]利用组合学方法证明了 k = 4 的情况。在 1972 年,罗特[4]利用类似自己证明 k = 3 的情况的方法,给出了 k = 4 的情况的另证。
塞迈雷迪于 1975 年给出了适用于所有 k 的证明。[5] 他巧妙地扩展了自己先前对 k = 4 的情况的组合论证,艾狄胥称该证明为“组合学推理的杰作”("a masterpiece of combinatorial reasoning")[6]. 定理亦有若干其他证明,较重要的有:1977 年希勒尔·菲尔斯滕贝格利用遍历理论给出的证明[7][8],以及 2001 年高尔斯结合傅里叶分析和组合数学给出的证明[9]。陶哲轩称塞迈雷迪定理的众多证明为“罗塞塔石碑”,因为它们连结了几个乍看之下迥异的数学分支。[10]
rk(N) 的具体大小
编辑rk(N) 的确切增长速度仍然未知。目前所知的上下界为
其中 欧布莱恩(Kevin O'Bryant) 证出了上述的下界[11] ,其证明建基于贝哈连德(Felix Behrend)[12]、罗伯特·蓝钦[13],以及埃尔金(Michael Elkin) [14][15]先前的成果。上界由高尔斯证出。[9]
对于较小的 k, 可以找到比起一般情况更紧的上下界。当 k = 3 时,布尔甘[16][17]、希思-布朗 (Roger Heath-Brown)[18]、塞迈雷迪[19],以及汤·桑德斯[20]依次给出了愈来愈好的下界。目前所知的上下界为
两边的界限分别由欧布莱恩[11] 和布鲁姆(Thomas Bloom) [21] 给出。
当 k = 4 时,本·格林和陶哲轩[22][23] 证明了存在 c > 0 使得
推广
编辑希勒尔·菲尔斯滕贝格和伊扎克·卡茨内勒松利用遍历理论整明了塞迈雷迪定理的高维推广。[24] 高尔斯[25]、沃伊杰赫·勒德尔和约泽夫·斯科肯 (Jozef Skokan) [26][27] ,以及布兰登·纳格 (Brendan Nagle)、 勒德尔和马蒂亚斯·沙赫特[28] ,和陶哲轩[29]给出了各自的组合学证明。
亚历山大·莱布门 (Alexander Leibman) 和维塔利·别尔格尔松[30] 给出定理对多项式列的推广:若 的上密度为正,且 为满足 的整值多项式,则存在无穷多组 使得对 都有 莱布门和别尔格尔松的结果同样适用于高维的情况。
塞迈雷迪定理的有限性版本可推广至有限的加法群上,例如有限域上的向量空间。[31] 定理在有限域上的类比,是有助理解原定理(在正整数集上)的模型。[32] 所谓封顶集问题,就是要找出向量空间 所包含的无 3 项等差数列的最大子集的大小,即塞迈雷迪定理当 k = 3 时的界限。
格林-陶定理断言,存在任意长的质数等差数列。此结论不能由塞迈雷迪定理推出,因为质数集的密度为 0. 本·格林和陶哲轩在其证明中引入了“相对性”(英语:relative) 的塞迈雷迪定理,该定理适用于任意具特定伪随机性的整数子集(允许密度为 0)。大卫·康伦,雅各布·福克斯和赵宇飞[33] (Yufei Zhao)其后亦给出了适用于更一般情况的相对性塞迈雷迪定理。[34][35]
埃尔德什等差数列猜想(断言倒数和发散的集合,必有任意长的等差数列)可以推出塞迈雷迪定理和格林-陶定理。
参见
编辑参考资料
编辑- ^ Erdős, Paul; Turán, Paul. On some sequences of integers (PDF). Journal of the London Mathematical Society. 1936, 11 (4): 261–264 [2019-06-17]. MR 1574918. doi:10.1112/jlms/s1-11.4.261. (原始内容存档 (PDF)于2020-07-23).
- ^ Roth, Klaus Friedrich. On certain sets of integers. Journal of the London Mathematical Society. 1953, 28 (1): 104–109. MR 0051853. Zbl 0050.04002. doi:10.1112/jlms/s1-28.1.104.
- ^ Szemerédi, Endre. On sets of integers containing no four elements in arithmetic progression. Acta Math. Acad. Sci. Hung. 1969, 20: 89–104. MR 0245555. Zbl 0175.04301. doi:10.1007/BF01894569.
- ^ Roth, Klaus Friedrich. Irregularities of sequences relative to arithmetic progressions, IV. Periodica Math. Hungar. 1972, 2: 301–326. MR 0369311. doi:10.1007/BF02018670.
- ^ Szemerédi, Endre. On sets of integers containing no k elements in arithmetic progression (PDF). Acta Arithmetica. 1975, 27: 199–245 [2019-06-17]. MR 0369312. Zbl 0303.10056. doi:10.4064/aa-27-1-199-245. (原始内容存档 (PDF)于2020-12-10).
- ^ Erdős, Paul. Graham, Ronald L.; Nešetřil, Jaroslav; Butler, Steve , 编. The Mathematics of Paul Erdős I Second. New York: Springer: 51–70. 2013. ISBN 978-1-4614-7257-5. MR 1425174. doi:10.1007/978-1-4614-7258-2_3.
|chapter=
被忽略 (帮助) - ^ Furstenberg, Hillel. Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. D'Analyse Math. 1977, 31: 204–256. MR 0498471. doi:10.1007/BF02813304..
- ^ Furstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel. The ergodic theoretical proof of Szemerédi’s theorem. Bull. Amer. Math. Soc. 1982, 7 (3): 527–552. MR 0670131. doi:10.1090/S0273-0979-1982-15052-2.
- ^ 9.0 9.1 Gowers, Timothy. A new proof of Szemerédi's theorem. Geom. Funct. Anal. 2001, 11 (3): 465–588 [2019-06-17]. MR 1844079. doi:10.1007/s00039-001-0332-9. (原始内容存档于2020-09-26).
- ^ Tao, Terence. Sanz-Solé, Marta; Soria, Javier; Varona, Juan Luis; Verdera, Joan , 编. International Congress of Mathematicians 1. Zürich: European Mathematical Society: 581–608. 2007. MR 2334204. arXiv:math/0512114 . doi:10.4171/022-1/22.
|chapter=
被忽略 (帮助) - ^ 11.0 11.1 O'Bryant, Kevin. Sets of integers that do not contain long arithmetic progressions. Electronic Journal of Combinatorics. 2011, 18 (1) [2019-06-17]. MR 2788676. (原始内容存档于2018-05-03).
- ^ Behrend, Felix A. On the sets of integers which contain no three terms in arithmetic progression. Proceedings of the National Academy of Sciences. 1946, 23 (12): 331–332. Bibcode:1946PNAS...32..331B. MR 0018694. PMC 1078539 . PMID 16588588. Zbl 0060.10302. doi:10.1073/pnas.32.12.331.
- ^ Rankin, Robert A. Sets of integers containing not more than a given number of terms in arithmetical progression. Proc. Roy. Soc. Edinburgh Sect. A. 1962, 65: 332–344. MR 0142526. Zbl 0104.03705.
- ^ Elkin, Michael. An improved construction of progression-free sets. Israel Journal of Mathematics. 2011, 184 (1): 93–128. MR 2823971. arXiv:0801.4310 . doi:10.1007/s11856-011-0061-1.
- ^ Green, Ben; Wolf, Julia. Chudnovsky, David; Chudnovsky, Gregory , 编. Additive number theory. Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson. New York: Springer: 141–144. 2010. ISBN 978-0-387-37029-3. MR 2744752. arXiv:0810.0732 . doi:10.1007/978-0-387-68361-4_9.
|chapter=
被忽略 (帮助) - ^ Bourgain, Jean. On triples in arithmetic progression. Geom. Funct. Anal. 1999, 9 (5): 968–984. MR 1726234. doi:10.1007/s000390050105.
- ^ Bourgain, Jean. Roth's theorem on progressions revisited. J. Anal. Math. 2008, 104 (1): 155–192. MR 2403433. doi:10.1007/s11854-008-0020-x.
- ^ Heath-Brown, Roger. Integer sets containing no arithmetic progressions. Journal of the London Mathematical Society. 1987, 35 (3): 385–394. MR 0889362. doi:10.1112/jlms/s2-35.3.385.
- ^ Szemerédi, Endre. Integer sets containing no arithmetic progressions. Acta Math. Hungar. 1990, 56 (1–2): 155–158. MR 1100788. doi:10.1007/BF01903717.
- ^ Sanders, Tom. On Roth's theorem on progressions. Annals of Mathematics. 2011, 174 (1): 619–636. MR 2811612. arXiv:1011.0104 . doi:10.4007/annals.2011.174.1.20.
- ^ Bloom, Thomas F. A quantitative improvement for Roth's theorem on arithmetic progressions. Journal of the London Mathematical Society. Second Series. 2016, 93 (3): 643–663. MR 3509957. arXiv:1405.5800 . doi:10.1112/jlms/jdw010.
- ^ Green, Ben; Tao, Terence. Chen, William W. L.; Gowers, Timothy; Halberstam, Heini; Schmidt, Wolfgang; Vaughan, Robert Charles , 编. Analytic number theory. Essays in honour of Klaus Roth on the occasion of his 80th birthday. Cambridge: Cambridge University Press: 180–204. 2009. Bibcode:2006math.....10604G. ISBN 978-0-521-51538-2. MR 2508645. Zbl 1158.11007. arXiv:math/0610604 .
|chapter=
被忽略 (帮助) - ^ Green, Ben; Tao, Terence. New bounds for Szemerédi's theorem, III: A polylogarithmic bound for r4(N). Mathematika. 2017, 63 (3): 944–1040. MR 3731312. arXiv:1705.01703 . doi:10.1112/S0025579317000316.
- ^ Furstenberg, Hillel; Katznelson, Yitzhak. An ergodic Szemerédi theorem for commuting transformations. Journal d'Analyse Mathématique. 1978, 38 (1): 275–291. MR 0531279. doi:10.1007/BF02790016.
- ^ Gowers, Timothy. Hypergraph regularity and the multidimensional Szemerédi theorem. Annals of Mathematics. 2007, 166 (3): 897–946. MR 2373376. arXiv:0710.3032 . doi:10.4007/annals.2007.166.897.
- ^ Rödl, Vojtěch; Skokan, Jozef. Regularity lemma for k-uniform hypergraphs. Random Structures Algorithms. 2004, 25 (1): 1–42. MR 2069663. doi:10.1002/rsa.20017.
- ^ Rödl, Vojtěch; Skokan, Jozef. Applications of the regularity lemma for uniform hypergraphs. Random Structures Algorithms. 2006, 28 (2): 180–194. MR 2198496. doi:10.1002/rsa.20108.
- ^ Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias. The counting lemma for regular k-uniform hypergraphs. Random Structures Algorithms. 2006, 28 (2): 113–179. MR 2198495. doi:10.1002/rsa.20117.
- ^ Tao, Terence. A variant of the hypergraph removal lemma. Journal of Combinatorial Theory, Series A. 2006, 113 (7): 1257–1280. MR 2259060. arXiv:math/0503572 . doi:10.1016/j.jcta.2005.11.006.
- ^ Bergelson, Vitaly; Leibman, Alexander. Polynomial extensions of van der Waerden's and Szemerédi's theorems. Journal of the American Mathematical Society. 1996, 9 (3): 725–753. MR 1325795. doi:10.1090/S0894-0347-96-00194-4.
- ^ Furstenberg, Hillel; Katznelson, Yitzhak. A density version of the Hales–Jewett theorem. Journal d'Analyse Mathématique. 1991, 57 (1): 64–119. MR 1191743. doi:10.1007/BF03041066.
- ^ Wolf, Julia. Finite field models in arithmetic combinatorics—ten years on. Finite Fields and Their Applications. 2015, 32: 233–274. MR 3293412. doi:10.1016/j.ffa.2014.11.003.
- ^ Yufei Zhao. Origin of my name. [2019-06-17]. (原始内容 (html)存档于2019-06-17).
叫宇飞
- ^ Conlon, David; Fox, Jacob; Zhao, Yufei. A relative Szemerédi theorem. Geometric and Functional Analysis. 2015, 25 (3): 733–762. MR 3361771. arXiv:1305.5440 . doi:10.1007/s00039-015-0324-9.
- ^ Zhao, Yufei. An arithmetic transference proof of a relative Szemerédi theorem. Mathematical Proceedings of the Cambridge Philosophical Society. 2014, 156 (2): 255–261. Bibcode:2014MPCPS.156..255Z. MR 3177868. arXiv:1307.4959 . doi:10.1017/S0305004113000662.
延申阅读
编辑- Tao, Terence. Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József , 编. Additive Combinatorics. CRM Proceedings & Lecture Notes 43. Providence, RI: American Mathematical Society: 145–193. 2007. Bibcode:2006math......4456T. ISBN 978-0-8218-4351-2. MR 2359471. Zbl 1159.11005. arXiv:math/0604456 .
|chapter=
被忽略 (帮助)
外部链接
编辑- Announcement by Ben Green and Terence Tao (页面存档备份,存于互联网档案馆) – the preprint is available at math.NT/0404188
- Discussion of Szemerédi's theorem (part 1 of 5) (页面存档备份,存于互联网档案馆)
- Ben Green and Terence Tao: Szemerédi's theorem (页面存档备份,存于互联网档案馆) on Scholarpedia
- 埃里克·韦斯坦因. SzemeredisTheorem. MathWorld.
- Grime, James; Hodge, David. 6,000,000: Endre Szemerédi wins the Abel Prize. Numberphile. 布雷迪·哈兰. 2012 [2019-06-17]. (原始内容存档于2014-01-09).