Fourier analysis in combinatorial number theory

I. D. Shkredov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 65 (2010) no. 3, pp. 513-567

Résumé

In this survey applications of harmonic analysis to combinatorial number theory are considered. Discussion topics include classical problems of additive combinatorics, colouring problems, higher-order Fourier analysis, theorems about sets of large trigonometric sums, results on estimates for trigonometric sums over subgroups, and the connection between combinatorial and analytic number theory. Bibliography: 162 titles.

Détail

Keywords: Fourier analysis, combinatorial number theory, additive combinatorics.

Bibliographie

[1] M. B. Nathanson, “Additive number theory. Inverse problems and the geometry of sumsets”, Grad. Texts in Math., 165, Springer-Verlag, New York, 1996, 293 pp. | MR | Zbl

[2] T. Tao, Van Vu, Additive combinatorics, Cambridge Stud. Adv. Math., 105, Cambridge Univ. Press, Cambridge, 2006, 512 pp. | MR | Zbl

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

[4] I. D. Shkredov, “Szemerédi's theorem and problems on arithmetic progressions”, Russian Math. Surveys, 61:6 (2006), 1101–1166 | DOI | MR | Zbl

[5] A. L. Cauchy, “Recherches sur les nombres”, J. École Polytech., 9 (1813), 99–116

[6] L. G. Shnirel'mann, “Über additive Eigenschaften von Zahlen”, Math. Ann., 107:1 (1933), 649–690 | DOI | MR

[7] 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

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

[9] B. Green, T. Tao, “An inverse theorem for the Gowers $U^3(G)$ norm, with applications”, Proc. Edinb. Math. Soc. (2), 51:1 (2008), 73–153 | DOI | MR | Zbl

[10] J. Bourgain, N. Katz, T. Tao, “A sum-product estimate in finite fields and their applications”, Geom. Funct. Anal., 14:1 (2004), 27–57 | DOI | MR | Zbl

[11] J. Solymosi, “On the number of sums and products”, Bull. London Math. Soc., 37:4 (2005), 491–494 | DOI | MR | Zbl

[12] A. A. Glibichuk, S. V. Konyagin, “Additive properties of product sets in fields of prime order”, Additive combinatorics, CRM Proc. Lecture Notes, 43, Amer. Math. Soc., Providence, RI, 2007, 279–286, arXiv: math/0702729 | MR | Zbl

[13] A. A. Glibichuk, “Combinational properties of sets of residues modulo a prime and the Erdös–Graham problem”, Math. Notes, 79:3–4 (2006), 356–365 | DOI | MR | Zbl

[14] J. Bourgain, The sum-product theorem in $\mathbb Z_q$ with $q$ arbitrary, Preprint

[15] J. Bourgain, A. Glibichuk, S. Konyagin, “Estimate 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

[16] J. Bourgain, S. V. Konyagin, “Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order”, C. R. Math. Acad. Sci. Paris, 337:2 (2003), 75–80 | DOI | MR | Zbl

[17] J. Bourgain, “Estimates on exponential sums related to the Diffie–Hellman distributions”, Geom. Funct. Anal., 15:1 (2005), 1–34 | DOI | MR | Zbl

[18] J. Bourgain, “Mordell's exponential sum estimate revisited”, J. Amer. Math. Soc., 18:2 (2005), 477–499 | DOI | MR | Zbl

[19] J. Bourgain, “Exponential sum estimates over subgroups of ${\mathbb Z}^*_q$, $q$ arbitrary”, J. Anal. Math., 97 (2005), 317–355 | DOI | MR | Zbl

[20] J. Bourgain, Multilinear exponential sums in prime fields, Preprint

[21] J. Bourgain, “Multilinear exponential sums in prime fields under optimal entropy condition on the sources”, Geom. Funct. Anal., 18:5 (2009), 1477–1502 | DOI | MR | Zbl

[22] J. Bourgain, “Some arithmetical applications of the sum-product theorems in the finite fields”, Geometric aspects of functional analysis, Lecture Notes in Math., 1910, Springer, Berlin, 2007, 99–116 | DOI | MR | Zbl

[23] J. Bourgain, M.-C. Chang, “Exponential sums 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

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

[25] T. Tao, “Norm convergence of multiple ergodic averages for commuting transformations”, Ergodic Theory Dynam. Systems, 28:2 (2008), 657–688 | DOI | MR | Zbl

[26] 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

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

[28] A. Leibman, “Pointwise convergence of ergodic averages for polynomial sequences of translations on a nilmanifold”, Ergodic Theory Dynam. Systems, 25:1 (2005), 201–213 | DOI | MR | Zbl

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

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

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

[32] B. Host, B. Kra, “Convergence of polynomial ergodic averages. Probability in mathematics”, Israel J. Math., 149:1 (2005), 1–19 | DOI | MR | Zbl

[33] T. Ziegler, “A non-conventional ergodic theorem for a nilsystem”, Ergodic Theory Dynam. Systems, 25:4 (2005), 1357–1370 | DOI | MR | Zbl

[34] T. Ziegler, “Universal characteristic factors and Furstenberg averages”, J. Amer. Math. Soc., 20:1 (2007), 53–97 | DOI | MR | Zbl

[35] T. Austin, “On the norm convergence of nonconventional ergodic averages”, Ergodic Theory Dynam. Systems, 30:2 (2010), 321–338 | DOI | Zbl

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

[37] 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

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

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

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

[41] J. Bourgain, “Roth's theorem on progressions revisited”, J. Anal. Math., 104 (2008), 155–192 | DOI | MR | Zbl

[42] B. Green, T. Tao, “The primes contain arbitrarily long arithmetic progressions”, Ann. of Math. (2), 167:2 (2008), 481–547 | DOI | MR | Zbl

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

[44] I. D. Shkredov, “On a problem of Gowers”, Izv. Math., 70:2 (2006), 385–425 | DOI | MR | Zbl

[45] I. D. Shkredov, “On a generalization of Szemerédi's theorem”, Proc. London Math. Soc. (3), 93:3 (2006), 723–760 | DOI | MR | Zbl

[46] B. Green, T. Tao, “New bounds for Szemerédi's theorem. I. Progressions of length 4 in finite field geometries”, Proc. London Math. Soc. (3), 98:2 (2009), 365–392, arXiv: math/0509560 | DOI | MR | Zbl

[47] S. V. Konyagin, I. E. Shparlinski, Character sums with exponential functions and their applications, Cambridge Tracts in Math., 136, Cambridge Univ. Press, Cambridge, 1999, 163 pp. | MR | Zbl

[48] S. V. Konyagin, “Estimates for trigonometric sums and for Gaussian sums”, IV Mezhdunarodnaya konferentsiya “Sovremennye problemy teorii chisel i ee prilozheniya” (Tula, 2001), Ch. III, MGU, 2002, 86–114 | MR | Zbl

[49] J. Bourgain, “More on the sum-product phenomenon in prime fields and its applications”, Int. J. Number Theory, 1:1 (2005), 1–32 | DOI | MR | Zbl

[50] N. Hegyváry, F. Hennecart, “Explicit constructions of extractors and expanders”, Acta Arith., 140:3 (2009), 233–249 | DOI | MR | Zbl

[51] M. Z. Garaev, “The sum-product estimate for large subsets of prime fields”, Proc. Amer. Math. Soc., 136:8 (2008), 2735–2739 | DOI | MR | Zbl

[52] D. Hart, A. Iosevich, J. Solymosi, “Sums and products in finite fields via Kloosterman sums”, Int. Math. Res. Not. (IMRN), 2007, no. 5, rnm007, 14 pp. | DOI | MR | Zbl

[53] I. Shparlinski, “On the solvability of bilinear equations in finite fields”, Glasg. Math. J., 50:3 (2008), 523–529, arXiv: 0708.2130v2 | DOI | MR | Zbl

[54] A. Sárközy, “On sums and products of residues modulo $p$”, Acta Arith., 118 (2005), 403–409 | DOI | MR | Zbl

[55] D. Hart, A. Iosevich, “Sums and products in finite fields: an integral geometric viewpoint”, Radon transforms, geometry, and wavelets, Contemp. Math., 464, Amer. Math. Soc., Providence, RI, 2008, 129–135, arXiv: 0705.4256 | MR

[56] M. Z. Garaev, V. Garcia, “The equation $x_1x_2=x_3x_4+\lambda $ in fields of prime order and applications”, J. Number Theory, 128:9 (2008), 2520–2537 | DOI | MR | Zbl

[57] B. Green, “A Szemerédi-type regularity lemma in abelian groups, with applications”, Geom. Funct. Anal., 15:2 (2005), 340–376 | DOI | MR | Zbl

[58] B. Green, “Montréal lecture notes on quadratic Fourier analysis”, Additive combinatorics, CRM Proc. Lecture Notes, 43, Amer. Math. Soc., Providence, RI, 2007, 69–102, arXiv: math/0604089 | MR | Zbl

[59] I. Schur, “Über die Kongruenz $x^m+y^m\equiv z^m \pmod p$”, Deutsch. Math. Ver., 25 (1916), 114–117 | Zbl

[60] W. T. Gowers, “Rough structure and classification”, GAFA'2000 (Tel Aviv, 1999), Geom. Funct. Anal., Special Volume, Part I, 2000, 79–117 | MR | Zbl

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

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

[63] B. Green, I. Ruzsa, “An analog of Freiman's theorem in an arbitrary abelian group”, J. London Math. Soc. (to appear)

[64] T. Sanders, An application of a local version of Chang's theorem, arXiv: math.CA/0607668

[65] T. Sanders, “Appendix to ‘Roth’s theorem on progressions revisited,' by J. Bourgain”, J. Anal. Math., 104 (2008), 193–206, arXiv: 0710.0642v2 | DOI | MR | Zbl

[66] I. D. Shkredov, “On sets of large trigonometric sums”, Izv. Math., 72:1 (2008), 149–168 | DOI | MR | Zbl

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

[68] N. H. Katz and T. Tao, “Recent progress on the Kakeya conjecture”, Proceedings of the 6th International Conference on Harmonic Analysis and Partial Differential Equations (El Escorial, 2000), Publ. Mat., Vol. Extra, 2002, 161–179 | MR | Zbl

[69] T. Tao, “From rotating needles to stability of waves: emerging connections between combinatorics, analysis, and PDE”, Notices Amer. Math. Soc., 48:3 (2001), 294–303 | MR | Zbl

[70] G. Mockenhaupt, T. Tao, “Restriction and Kakeya phenomena in finite fields”, Duke Math. J., 121:1 (2004), 35–74 | DOI | MR | Zbl

[71] B. Green, T. Tao, The quantitative behaviour of polynomial orbits on nilmanifolds, arXiv: 0709.3562v1

[72] B. Green, T. Tao, The equivalence between inverse sumset theorems and inverse conjectures for the $U^3$-norm, arXiv: 0906.3100v1

[73] B. Green, T. Tao, “Quadratic uniformity for the Möbius function”, Ann. Inst. Fourier (Grenoble), 58:6 (2008), 1863–1935, arXiv: math/0606087 | MR | Zbl

[74] T. Tao, T. Ziegler, The inverse conjecture for the Gowers norm over finite fields via the correspondence principle, arXiv: 0810.5527

[75] A. Samorodnitsky, L. Trevisan, “Gowers uniformity, influence of variables, and PCPs”, SIAM J. Comput., 39:1 (2009), 323–360, arXiv: math/0510264 | DOI | MR | Zbl

[76] S. Lovett, R. Meshulam, A. Samorodnitsky, “Inverse conjecture for the Gowers norm is false”, STOC' 08. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (Victoria, Canada, 2008), 2008, 547–556, arXiv: 0711.3388v1 | Zbl

[77] W. Rudin, Fourier analysis on groups, Wiley, New York, 1990 (Reprint of the 1962 original) | MR | Zbl

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

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

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

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

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

[83] 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

[84] 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

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

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

[87] H. Furstenberg, B. Weiss, “A mean ergodic theorem for $N^{-1}\sum_{n=1}^N f(T^n x)g(T^{n^2} x)$”, Convergence in ergodic theory and probability (Columbus, OH, 1993), Ohio State Univ. Math. Res. Inst. Publ., 5, de Gruyter, Berlin, 1996, 193–227 | MR | Zbl

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

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

[90] 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

[91] B. Elkin, An improved construction of progression-free sets, arXiv: 0801.4310v1

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

[93] P. Frankl, G. L. Graham, V. Rödl, “On subsets of abelian groups with no 3-term arithmetic progression”, J. Combin. Theory Ser. A, 45:1 (1987), 157–161 | DOI | MR | Zbl

[94] R. Meshulam, “On subsets of finite abelian groups with no 3-term arithmetic progressions”, J. Combin. Theory Ser. A, 71:1 (1995), 168–172 | DOI | MR | Zbl

[95] T. Sanders, “Roth's theorem in $\mathbb Z^n_4$”, Anal. PDE, 2:2 (2009), 211–234, arXiv: 0807.5101v1 | MR | Zbl

[96] B. Green, Notes on the polynomial Frieman–Ruzsa conjecture, Preprint, 2005

[97] N. G. Chudakov, “O plotnosti sovokupnosti chetnykh chisel, nepredstavimykh kak summa dvukh nechetnykh prostykh”, Izv. AN SSSR. Ser. matem., 2:1 (1938), 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] B. Green, “Roth's theorem in the primes”, Ann. Math. (2), 161:3 (2005), 1609–1636 | DOI | MR | Zbl

[101] R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey theory, Wiley-Intersci. Ser. Discrete Math. Optim., 2d ed., Wiley, New York, 1990, 196 pp. | MR | Zbl

[102] B. M. Landman, A. Robertson, Ramsey theory on the integers, Stud. Math. Libr., 24, Providence, RI, Amer. Math. Soc., 2004, 317 pp. | MR | Zbl

[103] Handbook of combinatorics, v. 1, 2, eds. R. L. Graham, M. Grötschel, L. Lovász, Elsevier, Amsterdam; MIT Press, Cambridge, MA, 1995 | MR | Zbl

[104] R. Rado, “Verallgemeinerung eines Satzes von van der Waerden mit Anwendungen auf ein problem der Zahlentheorie”, Sitzungsber. Preuß. Akad. Wiss., Phys.-Math. Kl., 17 (1933), 16–17 | Zbl

[105] R. Rado, “Some recent results in combinatorial analysis”, C. R. Congr. Internat. Math., 2 (1936), 20–21, Oslo | Zbl

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

[107] R. L. Graham, Rudiments of Ramsey theory, CBMS Reg. Conf. Ser. Math., 45, Amer. Math. Soc., Providence, RI, 1981, v+65 pp. | MR | MR | Zbl | Zbl

[108] 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

[109] N. Hindman, I. Leader, D. Strauss, “Open problems in partition regularity”, Combin. Probab. Comput., 12 (2003), 5–6 | DOI | MR | Zbl

[110] M. Beiglböck, V. Bergelson, N. Hindman, D. Strauss, “Multiplicative structures in additively large sets”, J. Combin. Theory Ser. A, 113:7 (2006), 1219–1242 | DOI | MR | Zbl

[111] V. Bergelson, N. Hindman, I. Leader, “Additive and multiplicative Ramsey theory in the reals and the rationals”, J. Combin. Theory Ser. A, 85:1 (1999), 41–68 | DOI | MR | Zbl

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

[113] N. Hindman, D. Strauss, “Algebra in the Stone–Čech compactification”, Theory and applications, de Gruyter Exp. Math., 27, de Gruyter, Berlin, 1998, xiv+485 pp. | MR | Zbl

[114] V. Bergelson, “Ergodic Ramsey theory – an update”, Ergodic theory of $\mathbb Z^d$-actions (Warwick, 1993–1994), London Math. Soc. Lecture Note Ser., 228, Cambridge Univ. Press, Cambridge, 1996, 1–61 | MR | Zbl

[115] T. Sanders, Analytic approaches to Schur's theorem, Preprint

[116] I. D. Shkredov, On monochromatic solutions of some nonlinear equations in $\mathbb Z/p\mathbb Z$, arXiv: 0909.3269v1

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

[118] I. Z. Ruzsa, “An analog of Freiman's theorem in groups”, Structure theory of set addition, Astérisque, 258, 1999, 323–326 | MR | Zbl

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

[120] G. A. Freiman, Foundations of a structural theory of set addition, Transl. Math. Monogr., 37, Amer. Math. Soc., Providence, RI, 1973 | MR | MR | Zbl

[121] I. D. Shkredov, “On sumsets of dissociated sets”, Online J. Anal. Comb., 4 (2009), Art. 4, 26 pp. | MR

[122] F. L. Nazarov, “The Bang solution of the coefficient problem”, St. Petersburg Math. J., 9:2 (1998), 407–419 | MR | Zbl

[123] K. Ball, “Convex geometry and functional analysis”, Handbook of the geometry of Banach spaces, v. 1, Elsevier, Amsterdam, 2001, 161–194 | MR | Zbl

[124] B. Green, “Spectral structure of sets of integers”, Fourier analysis and convexity, Appl. Numer. Harmon. Anal., Birkhäuser, Boston, MA, 2004, 83–96 | MR | Zbl

[125] W. Rudin, “Trigonometric series with gaps”, J. Math. Mech., 9 (1960), 203–227 | DOI | MR | Zbl

[126] B. Green, Structure theory of set addition, ICMS Instructional Conference in Combinatorial Aspects of Mathematical Analysis, Edinburgh, 2002 http://www.dpmms.cam.ac.uk/~bjg23/papers/icmsnotes.pdf

[127] B. Green, “Some constructions in the inverse spectral theory of cyclic groups”, Combin. Probab. Comput., 12:2 (2003), 127–138 | DOI | MR | Zbl

[128] I. D. Shkredov, “Examples of sets with large trigonometric sums”, 198, no. 12, 2007, 1805–1838 | DOI | MR | Zbl

[129] A. A. Yudin, “O mere bolshikh znachenii trigonometricheskikh summ”, Teoriya chisel, eds. G. A. Freiman, A. M. Rubinov, E. V. Novoselov, Kalininskii gos. un-t, Kalinin, 1973, 163–174 | MR | Zbl

[130] S. V. Konyagin and V. F. Lev, “On the distribution of exponential sums”, Integers, 2000, A1, 11 pp. (electronic only) | MR | Zbl

[131] V. F. Lev, “Linear equations over ${\mathbb F}_p$ and moments of exponential sums”, Duke Math. J., 107 (2001), 239–263 | DOI | MR | Zbl

[132] G. Myerson, “How small can a sum of roots of unity be?”, Amer. Math. Monthly, 93:6 (1986), 457–459 | DOI | MR | Zbl

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

[134] 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

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

[136] E. Szemerédi, V. 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

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

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

[139] T. Sanders, “Additive structures in sumsets”, Math. Proc. Cambridge Philos. Soc., 144:2 (2008), 289–316, arXiv: math/0605520 | DOI | MR | Zbl

[140] T. Sanders, “A note on Freiman's theorem in vector spaces”, Combin. Probab. Comput., 17:2 (2008), 297–305 | DOI | MR | Zbl

[141] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1992, xvi+254 pp. | MR | Zbl

[142] E. Croot, I. Ruzsa, T. Schoen, “Arithmetic progressions in sparse sumsets”, Combinatorial number theory, de Gruyter, Berlin, 2007, 157–164 | MR | Zbl

[143] K. T. Smith, “The uncertainty principle on groups”, SIAM J. Appl. Math., 50:3 (1990), 876–882 | DOI | MR | Zbl

[144] T. Tao, “An uncertainty principle for cyclic groups of prime order”, Math. Res. Lett., 12:1 (2005), 121–127 | MR | Zbl

[145] S. Guo, Zh.-W. Sun, “A variant of Tao's method with application to restricted sumsets”, J. Number Theory, 129:2 (2009), 434–438, arXiv: 0808.0243v1 | DOI | MR | Zbl

[146] P. Stevenhagen, H. W. Lenstra, “Chebotarëv and his density theorem”, Math. Intelligencer, 18:2 (1996), 26–37 | DOI | MR | Zbl

[147] N. M. Korobov, Exponential sums and their applications, Math. Appl. (Soviet Ser.), 80, Kluwer, Dordrecht, 1992, xvi+209 pp. | MR | MR | Zbl | Zbl

[148] I. E. Shparlinskii, “Estimates of Gaussian sums”, Math. Notes, 50:1 (1991), 740–746 | DOI | MR | Zbl

[149] D. R. Heath-Brown, S. V. Konyagin, “New bounds for Gauss sums derived from $k$th powers, and for Heilbronn's exponential sum”, Q. J. Math., 51:2 (2000), 221–235 | DOI | MR | Zbl

[150] L. J. Mordell, “On a sum analogous to a Gauss' sum”, Quart. J. Math., 3 (1932), 161–167 | DOI | Zbl

[151] T. Cochrane, C. Pinner, “An improved Mordell type bound for exponential sums”, Proc. Amer. Math. Soc., 133:2 (2004), 313–320 | DOI | MR | Zbl

[152] E. Bombieri, J. Bourgain, S. V. Konyagin, “Roots of polynomials in subgroups of $\mathbb{F}^*_p$ and applications to congruences”, Int. Math. Res. Not. IMRN, 2009, no. 5, 802–834 | DOI | MR | Zbl

[153] I. M. Vinogradov, Elements of number theory, Dover, New York, viii+227 pp. | MR | MR | Zbl | Zbl

[154] S. V. Konyagin, “Good distribution of values of sparse polynomials modulo a prime”, Analytic number theory, Cambridge Univ. Press, Cambridge, 2009, 289–296 | MR | Zbl

[155] B. Green, Sum-product phenomena in $\mathbf{F}_p$: a brief introduction, arXiv: 0904.2075v1

[156] P. Erdös, E. Szemerédi, “On sums and products of integers”, Studies in pure mathematics, Birkhäuser, Basel, 1983, 213–218 | MR | Zbl

[157] K. Ford, “Sums and products from a finite set of real numbers”, Ramanujan J., 2:1-2 (1998), 59–66 | DOI | MR | Zbl

[158] M. B. Nathanson, “On sums and products of integers”, Proc. Amer. Math. Soc., 125:1 (1997), 9–16 | DOI | MR | Zbl

[159] G. Elekes, “On the number of sums and products”, Acta Arith., 81:4 (1997), 365–367 | MR | Zbl

[160] B. Barak, R. Impagliazzo, A. Wigderson, “Extracting randomness using few independent sources”, SIAM J. Comput., 36:4 (2006), 1095–1118 | DOI | MR | Zbl

[161] M.-Ch. Chang, “On a question of Davenport and Lewis and new character sum bounds in finite fields”, Duke Math. J., 145:3 (2008), 409–442 | DOI | MR | Zbl

[162] M. Z. Garaev, “An explicit sum-product estimate in $\mathbb F_p$”, Int. Math. Res. Not. IMRN, 2007, no. 11, rnm035, 11 pp., arXiv: math/0702780v1 | DOI | MR | Zbl