Szemerédi's theorem and problems on arithmetic progressions

I. D. Shkredov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 61 (2006) no. 6, pp. 1101-1166

Résumé

Szemerédi's famous theorem on arithmetic progressions asserts that every subset of integers of positive asymptotic density contains arithmetic progressions of arbitrary length. His remarkable theorem has been developed into a major new area of combinatorial number theory. This is the topic of the present survey.

Bibliographie

[1] B. L. Van der Waerden, “Beweis einer Baudetschen Vermutung”, Nieuw Arch. Wisk., 15 (1927), 212–216 | Zbl

[2] A. Ya. Khinchin, Tri zhemchuzhiny teorii chisel, URSS, M., 2004 | MR | Zbl

[3] R. Grekhem, Nachala teorii Ramseya, M., Mir, 1984 | MR | MR | Zbl

[4] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley, New York, 1980 | MR | Zbl

[5] V. A. Uspenskii, Lektsii o vychislimykh funktsiyakh, Fizmatgiz, M., 1960 | MR

[6] S. Shelah, “Primitive recursive bounds for van der Waerden numbers”, J. Amer. Math. Soc., 1:3 (1988), 683–697 | DOI | MR | Zbl

[7] K. F. Roth, “On certain sets of integers”, J. London Math. Soc., 28 (1953), 104–109 | DOI | MR | Zbl

[8] E. Szemerédi, “Integer sets containing no arithmetic progressions”, Acta Math. Hungar., 56:1–2 (1990), 155–158 | DOI | MR | Zbl

[9] D. R. Heath-Brown, “Integer sets containing no arithmetic progressions”, J. London Math. Soc. (2), 35:3 (1987), 385–394 | DOI | MR | Zbl

[10] J. Bourgain, “On triples in arithmetic progression”, Geom. Funct. Anal., 9:5 (1999), 968–984 | DOI | MR | Zbl

[11] J. Bourgain, “A Szemerédi type theorem for sets of positive density in $\mathbb R^k$”, Israel J. Math., 54:3 (1986), 307–316 | DOI | MR | Zbl

[12] I. Z. Ruzsa, E. Szemerédi, “Triple systems with no six points carrying three triangles”, Combinatorics, Proceedings of the Fifth Hungarian colloquium (Keszthely, 1976), Colloq. Math. Soc. János Bolyai, II, North-Holland, Amsterdam, 1978, 939–945 | MR | Zbl

[13] E. Szemerédi, “On sets of integers containing no four elements in arithmetic progression”, Acta Math. Acad. Sci. Hungar., 20:1–2 (1969), 89–104 | DOI | MR | Zbl

[14] E. Szemerédi, “On sets of integers containing no $k$ elements in arithmetic progression”, Acta Arith., 27 (1975), 199–245 | MR | Zbl

[15] H. Furstenberg, “Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions”, J. Anal. Math., 31 (1977), 204–256 | DOI | MR | Zbl

[16] H. Furstenberg, Y. Katznelson, D. Ornstein, “The ergodic theoretical proof of Szemerédi's theorem”, Bull. Amer. Math. Soc. (N.S.), 7:3 (1982), 527–552 | DOI | MR | Zbl

[17] H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, M. B. Porter Lectures, Princeton Univ. Press, Princeton, NJ, 1981 | MR | Zbl

[18] H. Furstenberg, Y. Katznelson, “An ergodic Szemerédi theorem for commuting transformations”, J. Anal. Math., 34 (1978/1979), 275–291 | DOI | MR | Zbl

[19] V. Bergelson, A. Leibman, “Polynomial extentions of van der Waerden's and Szemerédi's theorems”, J. Amer. Math. Soc., 9:3 (1996), 725–753 | DOI | MR | Zbl

[20] H. Furstenberg, Y. Katznelson, “A density version of the Hales–Jewett theorem”, J. Anal. Math., 57 (1991), 64–119 | MR | Zbl

[21] A. Leibman, “Multiple recurrence theorem for measure preserving actions of a nilpotent group”, Geom. Funct. Anal., 8:5 (1998), 853–931 | DOI | MR | Zbl

[22] W. T. Gowers, “A new proof of Szemerédi's theorem”, Geom. Funct. Anal., 11:3 (2001), 465–588 | DOI | MR | Zbl

[23] W. T. Gowers, “A new proof of Szemerédi's theorem for arithmetic progressions of length four”, Geom. Funct. Anal., 8:3 (1998), 529–551 | DOI | MR | Zbl

[24] B. Green, T. Tao, “The primes contain arbitrarily long arithmetic progressions”, Ann. of Math. (to appear)

[25] B. Green, “On arithmetic structures in dense sets of integers”, Duke Math. J., 144:2 (2002), 215–238 | DOI | MR | Zbl

[26] J. Bourgain, M.-C. Chang, “Exponential sum estimates over subgroups and almost subgroups of $\mathbb Z_Q^*$, where $Q$ is composite with few prime factors”, Geom. Funct. Anal., 16:2 (2006), 327–366 | DOI | MR | Zbl

[27] J. Bourgain, A. A. Glibichuk, S. V. Konyagin, “Estimates for the number of sums and products and for exponential sums in fields of prime order”, J. London Math. Soc. (2), 73:2 (2006), 380–398 | DOI | MR | Zbl

[28] I. D. Shkredov, “Ob odnoi zadache Gauersa”, Dokl. RAN, 400:2 (2005), 169–172 | MR

[29] I. D. Shkredov, “Ob odnoi zadache Gauersa”, Izv. RAN. Ser. matem., 70:2 (2006), 179–221 | MR | Zbl

[30] I. D. Shkredov, “Ob odnom obobschenii teoremy Semeredi”, Dokl. RAN, 405:3 (2005), 315–319 | MR | Zbl

[31] I. D. Shkredov, On a generalization of Szemerédi's theorem, arXiv: math.NT/0503639

[32] B. Green, T. Tao, An inverse theorem for the Gowers $U^3$ norm, arXiv: math.NT/0503014

[33] B. Green, T. Tao, New bounds for Szemerédi's Theorem. I: Progressions of length 4 in finite field geometries, arXiv: math.CO/0509560

[34] B. Green, “Roth's theorem in the primes”, Ann. of Math. (2), 161:3 (2005), 1609–1636 | DOI | MR | Zbl

[35] A. A. Bukhshtab, Teoriya chisel, Prosveschenie, M., 1966 | MR | Zbl

[36] I. M. Vinogradov, Osnovy teorii chisel, Lan, SPb., 2004

[37] I. Schur, “Über die Kongruenz $x^m+y^m\equiv z^m\pmod p$”, Jahresber. Deutsch. Math.-Verein., 25:4–6 (1916), 114–117 | Zbl

[38] K. F. Roth, “On certain sets of integers, II”, J. London Math. Soc., 29 (1954), 20–26 | DOI | MR | Zbl

[39] R. Rado, “Verallgemeinerung eines Satzes von van der Waerden mit Anwendungen auf ein Problem der Zahlentheorie”, Sitz. Preuß. Akad. Wiss. Phys.-Math. Kl., 17 (1933), 589–596 | Zbl

[40] R. Rado, “Studien zur Kombinatorik”, Math. Z., 36:1 (1933), 424–470 | DOI | MR | Zbl

[41] R. Rado, “Some recent results in combinatorial analysis”, Comptes Rendus du Congrès International des Mathématiciens, vol. 2 (Oslo, 1936), 1937, 20–21 | Zbl

[42] P. Frankl, R. L. Graham, V. Rödl, “Quantitative theorems for regular systems of equations”, J. Combin. Theory Ser. A, 47:2 (1988), 246–261 | DOI | MR | Zbl

[43] T. Tao, A quantitative ergodic theory proof of Szemerédi's theorem, arXiv: math.CO/0405251 | MR

[44] N. Alon, J. H. Spencer, The probabilistic method, Wiley, New York, 1992 | MR | Zbl

[45] F. A. Behrend, “On sets of integers which contain no three terms in arithmetic progression”, Proc. Natl. Acad. Sci. USA, 32 (1946), 331–332 | DOI | MR | Zbl

[46] R. Salem, D. C. Spencer, “On sets of integers which contain no three terms in arithmetical progression”, Proc. Natl. Acad. Sci. USA, 28 (1942), 561–563 | DOI | MR | Zbl

[47] R. Salem, D. C. Spencer, “On sets which do not contain a given number of terms in arithmetical progression”, Nieuw Arch. Wisk. (2), 23 (1950), 133–143 | MR | Zbl

[48] I. Laba, M. T. Lacey, On sets of integers not containing long arithmetic progressions, arXiv: math.CO/0108155

[49] R. A. Rankin, “Sets of integers containing not more than a given number of terms in arithmetic progression”, Proc. Roy. Soc. Edinburgh Sect. A, 65:4 (1960/1961), 332–344 | MR | Zbl

[50] R. A. Rankin, “Representations of a number af the sum of a large number os squares”, Proc. Roy. Soc. Edinburgh Sect. A, 65:4 (1960/1961), 318–331 | MR | Zbl

[51] P. Erdös, P. Turán, “On some sequences of integers”, J. London Math. Soc., 11 (1936), 261–264 | DOI | Zbl

[52] L. Moser, “On non-averaging sets of integers”, Canadian J. Math., 5 (1953), 245–252 | MR | Zbl

[53] W. T. Gowers, “Lower bounds of tower type for Szemerédi's uniformity lemma”, Geom. Funct. Anal., 7:2 (1997), 322–337 | DOI | MR | Zbl

[54] E. Szemerédi, “Regular partitions of graphs”, Problèmes combinatoires et théorie des graphes (Orsay, 1976), Colloq. Internat. CNRS, 260, CNRS, Paris, 1978, 399–401 | MR | Zbl

[55] J. Komlós, M. Simonovits, “Szemerédi's regularity lemma and its applications in graph theory”, Combinatorics, Paul Erdös is eighty (Keszthely, 1993), Bolyai Soc. Math. Stud., 2, eds. D. Miklós, V. T. Sós, T. Szönyi, János Bolyai Math. Soc., Budapest, 1996, 295–352 | MR | Zbl

[56] Y. Kohayakawa, “Szemerédi's regularity lemma for sparse graphs”, Foundations of computational mathematics (Rio de Janeiro), Springer-Verlag, Berlin, 1997, 216–230 | MR | Zbl

[57] R. L. Graham, V. Rödl, “Numbers in Ramsey theory”, Surveys in combinatorics (New Cross, 1987), London Math. Soc. Lecture Note Ser., 123, Cambridge Univ. Press, Cambridge, 1987, 111–153 | MR | Zbl

[58] B. Nagle, V. Rödl, M. Schacht, “The counting lemma for regular $k$-uniform hypergraphs”, Random Structures Algorithms, 28:2 (2006), 113–179 | DOI | MR | Zbl

[59] W. T. Gowers, “Quasirandomness, counting and regularity for 3-uniform hypergraphs”, Combin. Probab. Comput., 15:1–2 (2006), 143–184 | DOI | MR | Zbl

[60] W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, http://www.dpmms.cam.ac.uk/w̃tg10/papers.html

[61] P. Varnavides, “On certain sets of positive density”, J. London Math. Soc., 34 (1959), 358–360 | DOI | MR | Zbl

[62] E. Croot, A structure theorem for positive density sets having the minimal number of 3-term arithmetic progressions, arXiv: math.NT/0305318

[63] A. Samorodnitsky, L. Trevisan, Gowers uniformity, influence of variables, and PCPs, arXiv: math.CO/0510264 | MR

[64] G. A. Freiman, Nachala strukturnoi teorii slozheniya mnozhestv, Kazan. gos. ped. in-t., Elabuzh. gos. ped. in-t, 1966 | MR | Zbl

[65] Y. Bilu, “Structure of sets with small sumset”, Structure theory of sets addition, Astérisque, 258, 1999, 77–108 | MR | Zbl

[66] I. Ruzsa, “Generalized arithmetic progressions and sumsets”, Acta Math. Hungar., 65:4 (1994), 379–388 | DOI | MR | Zbl

[67] M.-C. Chang, “A polynomial bound in Freiman's theorem”, Duke Math. J., 113:3 (2002), 399–419 | DOI | MR | Zbl

[68] S. L. G. Choi, “On arithmetic progressions in sequences”, J. London Math. Soc. (2), 10:4 (1975), 427–430 | DOI | MR | Zbl

[69] A. Puankare, “Novye metody nebesnoi mekhaniki”, Izbrannye trudy, t. 2, Nauka, M., 1972 | MR | Zbl

[70] A. B. Katok, B. Khasselblat, Vvedenie v sovremennuyu teoriyu dinamicheskikh sistem, Faktorial, M., 1999 | MR | Zbl

[71] V. Bergelson, A. Leibman, “Set-polynomials and polynomial extension of the Hales–Jewett theorem”, Ann. of Math. (2), 150:1 (1999), 33–75 | DOI | MR | Zbl

[72] A. Sárcözy, “On difference sets of sequences of integers, I”, Acta Math. Acad. Sci. Hungar., 31:1–2 (1978), 125–149 | DOI | MR | Zbl

[73] A. Sárközy, “On difference sets of sequences of integers, III”, Acta Math. Acad. Sci. Hungar., 31:3–4 (1978), 355–386 | DOI | MR | Zbl

[74] S. Srinivasan, “On a result of Sárközy and Furstenberg”, Nieuw. Arch. Wisk. (4), 3:3 (1985), 275–280 | MR | Zbl

[75] J. Pintz, W. L. Steiger, E. Szemerédi, “On sets of natural numbers whose difference set contains no squares”, J. London Math. Soc. (2), 37:2 (1988), 219–231 | DOI | MR | Zbl

[76] A. W. Hales, R. I. Jewett, “Regularity and positional games”, Trans. Amer. Math. Soc., 106:2 (1963), 222–229 | DOI | MR | Zbl

[77] R. McCutcheon, Elemental methods in ergodic Ramsey theory, Lecture Notes in Math., 1722, Springer-Verlag, Berlin, 1999 | MR | Zbl

[78] M. D. Boshernitzan, “Quantitative recurrence results”, Invent. Math., 113:3 (1993), 617–631 | DOI | MR | Zbl

[79] N. G. Moschevitin, “Ob odnoi teoreme Puankare”, UMN, 53:1 (1998), 223–224 | MR | Zbl

[80] I. D. Shkredov, “O vozvraschaemosti v srednem”, Matem. zametki, 72:4 (2002), 625–632 | MR | Zbl

[81] I. D. Shkredov, On multiple recurrence, arXiv: math.DS/0406413

[82] V. Afraimovich, J. R. Chazottes, B. Saussol, “Pointwise dimensions for Poincaré recurrence associated with maps and special flows”, Discrete Contin. Dyn. Syst., 9:2 (2003), 263–280 | MR | Zbl

[83] L. Barreira, Y. Pesin, J. Schmeling, “Dimension and product structure of hyperbolic measures”, Ann. of Math. (2), 149:3 (1999), 755–783 | DOI | MR | Zbl

[84] L. Barreira, B. Saussol, “Hausdorff dimension of measures via Poincaré recurrence”, Comm. Math. Phys., 219:2 (2001), 443–463 | DOI | MR | Zbl

[85] L. Barreira, B. Saussol, “Product structure of Poincaré recurrence”, Ergodic Theory Dynam. Systems, 22:1 (2002), 33–61 | DOI | MR | Zbl

[86] B. Saussol, S. Troubetzkoy, S. Vaienti, “Recurrence, dimensions, and Lyapunov exponents”, J. Statist. Phys., 106:3–4 (2002), 623–634 | DOI | MR | Zbl

[87] I. D. Shkredov, “O dinamicheskikh sistemakh s medlennoi skorostyu vozvrascheniya”, Matem. sb., 197:11 (2006), 143–158

[88] M. Ajtai, E. Szemerédi, “Sets of lattice points that form no squares”, Studia Sci. Math. Hungar., 9 (1974/1975), 9–11 | MR | Zbl

[89] V. H. Vu, “On a question of Gowers”, Ann. Combin., 6:2 (2002), 229–233 | DOI | MR | Zbl

[90] J. Solymosi, “Note on a generalization of Roth's theorem”, Discrete and computational geometry, Algorithms Combin., 25, Springer, Berlin, 2003, 825–827 | MR | Zbl

[91] G. N. Sárcözy, S. Selkow, On a question of Gowers concerning isosceles right-angle triangles, , 2003 http://citeseer.ist.psu.edu/569945.html

[92] B. Green, “Finite field models in additive combinatorics”, Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., 327, Cambridge Univ. Press, Cambridge, 2005, 1–27 | MR | Zbl

[93] F. R. K. Chung, R. L. Graham, R. M. Wilson, “Quasi-random graphs”, Combinatorica, 9:4 (1989), 345–362 | DOI | MR | Zbl

[94] F. R. K. Chung, R. L. Graham, “Quasi-random subsets of $Z_n$”, J. Combin. Theory Ser. A, 61:1 (1992), 64–86 | DOI | MR | Zbl

[95] V. I. Bogachev, Osnovy teorii mery, t. 1, 2, NITs “Regulyarnaya i khaoticheskaya dinamika”, M., Izhevsk, 2003

[96] L. E. Dickson, History of the theory of numbers, vol. III, Carnegie Inst. of Washington, Washington, DC, 1919, 1920, 1923 | MR | Zbl

[97] N. G. Chudakov, “O plotnosti sovokupnosti chetnykh chisel, nepredstavimykh kak summa dvukh nechetnykh prostykh”, Izv. AN SSSR. Ser. matem., 1938, no. 1, 25–40 | Zbl

[98] J. G. van der Corput, “Über Summen von Primzahlen und Primzahlquadraten”, Math. Ann., 116:1 (1939), 1–50 | DOI | MR | Zbl

[99] S. Chowla, “There exists an infinity of 3-combinations of primes in A.P.”, Proc. Lahore Philos. Soc., 6:2 (1944), 15–16 | MR | Zbl

[100] P. A. Pritchard, A. Moran, A. Thyssen, “Twenty-two primes in arithmetic progression”, Math. Comp., 64:211 (1995), 1337–1339 | DOI | MR | Zbl

[101] M. Frind, P. Jobling, P. Underwood, 23 primes in arithmetic progression, http://primes.plentyoffish.com

[102] B. Host, B. Kra, “Nonconventional ergodic averages and nilmanifolds”, Ann. of Math. (2), 161:1 (2005), 397–488 | DOI | MR | Zbl

[103] D. A. Goldston, C. Y. Yildirim, “Higher correlations of divisor sums related to primes. I: Triple correlations”, Integers, 3 (2003), paper A5 | MR | Zbl

[104] D. Goldston, C. Y. Yildirim, Higher correlations of divisor sums related to primes, III: $k$-correlations, arXiv: math.NT/0209102

[105] D. A. Goldston, Y. Motohashi, J. Pintz, C. Y. Yildirim, “Small gaps between primes”, Proc. Japan Acad. Ser. A Math. Sci., 82:4 (2006), 61–65 | DOI | MR | Zbl

[106] G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, Clarendon Press, Oxford, 1960 | MR | Zbl

[107] W. Deuber, “Partitions theorems for Abelian groups”, J. Combin. Theory Ser. A, 19:1 (1975), 95–108 | DOI | MR | Zbl

[108] S. D. Adhikari, “A note on a question of Erdös”, Exposition. Math., 15:4 (1997), 367–371 | MR | Zbl

[109] T. C. Brown, V. Rödl, “Monochromatic solutions to equations with unit fractions”, Bull. Austral. Math. Soc., 43:3 (1991), 387–392 | DOI | MR | Zbl

[110] H. Lefmann, “On partition regular systems of equations”, J. Combin. Theory Ser. A, 58:1 (1991), 35–53 | DOI | MR | Zbl

[111] W. Deuber, “Partitionen und lineare Gleichungssysteme”, Math. Z., 133:2 (1973), 109–123 | DOI | MR | Zbl

[112] E. Croot, “Long arithmetic progressions in critical sets”, J. Combin. Theory Ser. A, 113:1 (2006), 53–66 ; arXiv: math.NT/0403082 | DOI | MR | Zbl

[113] R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes, II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562 | DOI | MR | Zbl

[114] J. Bourgain, “On aritmetic progressions in sums of sets of integers”, A Tribute of Paul Erdös, Cambridge Univ. Press, Cambridge, 1990, 105–109 | MR | Zbl

[115] I. Z. Ruzsa, “Arithmetic progressions in sumsets”, Acta Arith., 60:2 (1991), 191–202 | MR | Zbl

[116] B. Green, “Arithmetic progressions in sumsets”, Geom. Funct. Anal., 12:3 (2002), 584–597 | DOI | MR | Zbl

[117] G. A. Freiman, H. Halberstam, I. Z. Ruzsa, “Integer sum sets containing long arithmetic progressions”, J. London Math. Soc. (2), 46:2 (1992), 193–201 | DOI | MR | Zbl

[118] I. Z. Ruzsa, “Arithmetical progressions and the number of sums”, Period. Math. Hungar., 25:1 (1992), 105–111 | DOI | MR | Zbl

[119] A. Sárközy, “Finite addition theorems, I”, J. Number Theory, 32:1 (1989), 114–130 | DOI | MR | Zbl

[120] A. Sárközy, “Finite addition theorems, II”, J. Number Theory, 48:2 (1994), 197–218 | DOI | MR | Zbl

[121] A. Sárközy, “Finite addition theorems, III”, Groupe de travail en théorie analytique et élémentaire des nombres, 1989–1990, Publ. Math. Orsay, 92-01 (1992), 105–122 | MR | Zbl

[122] V. F. Lev, “Optimal representations by sumsets and subset sums”, J. Number Theory, 62:1 (1997), 127–143 | DOI | MR | Zbl

[123] V. F. Lev, “Blocks and progressions in subset sums sets”, Acta Arith., 106:2 (2003), 123–142 | DOI | MR | Zbl

[124] E. Szemerédi, V. H. Vu, “Long arithmetic progressions in sum-sets and the number of $x$-sum-free sets”, Proc. London Math. Soc. (3), 90:2 (2005), 273–296 | DOI | MR | Zbl

[125] E. Szemerédi, V. H. Vu, “Finite and infinite arithmetic progressions in sumsets”, Ann. of Math. (2), 163:1 (2006), 1–35 | DOI | MR | Zbl

[126] J. Solymosi, “Arithmetic progressions in sets with small sumsets”, Combin. Probab. Comput., 15:4 (2006), 597–603 | DOI | MR | Zbl

[127] P. Erdös, P. Turán, “On a problem of Sidon in additive number theory, and on some related problems”, J. London Math. Soc., 16 (1941), 212–215 | DOI | MR | Zbl

[128] T. Jiang, “Anti-Ramsey numbers of subdivided graphs”, J. Combin. Theory Ser. B, 85:2 (2002), 361–366 | DOI | MR | Zbl

[129] V. Jungić, J. Licht, M. Mahdian, J. Nes̆etr̆il, R. Radoic̆ić, “Rainbow arithmetic progressions and anti-Ramsey results”, Combin. Probab. Comput., 12:5–6 (2003), 599–620 | DOI | MR | Zbl

[130] V. Jungić, R. Radoic̆ić, “Rainbow 3-term arithmetic progressions”, Integers, 3 (2003), paper A18 | MR | Zbl

[131] M. Axenovich, D. Fon-Der-Flaass, “On rainbow arithmetic progressions”, Electron. J. Combin., 11:1 (2004), Research paper 1 | MR | Zbl

[132] I. Z. Ruzsa, “Difference sets without squares”, Period. Math. Hungar., 15:3 (1984), 205–209 | DOI | MR | Zbl