Non-commutative methods in additive combinatorics and number theory
- Authors: Shkredov I.D.1
-
Affiliations:
- Steklov Mathematical Institute of Russian Academy of Sciences
- Issue: Vol 76, No 6 (2021)
- Pages: 119-180
- Section: Articles
- URL: https://journals.rcsi.science/0042-1316/article/view/142315
- DOI: https://doi.org/10.4213/rm10029
- ID: 142315
Cite item
Abstract
About the authors
Ilya Dmitrievich Shkredov
Steklov Mathematical Institute of Russian Academy of Sciences
Email: ilya.shkredov@gmail.com
Doctor of physico-mathematical sciences, Professor
References
- T. Austin, “Quantitative equidistribution for certain quadruples in quasi-random groups”, Combin. Probab. Comput., 24:2 (2015), 376–381
- T. Austin, “Ajtai–Szemeredi theorems over quasirandom groups”, Recent trends in combinatorics, IMA Vol. Math. Appl., 159, Springer, Cham, 2016, 453–484
- L. Babai, A. Seress, “On the diameter of permutation groups”, European J. Combin., 13:4 (1992), 231–243
- A. Balog, E. Szemeredi, “A statistical theorem of set addition”, Combinatorica, 14:3 (1994), 263–268
- V. Blomer, E. Fouvry, E. Kowalski, P. Michel, D. Milicevic, “On moments of twisted $L$-functions”, Amer. J. Math., 139:3 (2017), 707–768
- D. Borthwick, Spectral theory of infinite-area hyperbolic surfaces, Progr. Math., 256, Birkhäuser Boston, Inc., Boston, MA, 2007, xii+355 pp.
- J. Bourgain, “A modular Szemeredi–Trotter theorem for hyperbolas”, C. R. Math. Acad. Sci. Paris, 350:17-18 (2012), 793–796
- J. Bourgain, “Some Diophantine applications of the theory of group expansion”, Thin groups and superstrong approximation, Math. Sci. Res. Inst. Publ., 61, Cambridge Univ. Press, Cambridge, 2014, 1–22
- J. Bourgain, A. Gamburd, “Uniform expansion bounds for Cayley graphs of $operatorname{SL}_2(mathbb{F}_p)$”, Ann. of Math. (2), 167:2 (2008), 625–642
- J. Bourgain, A. Gamburd, P. Sarnak, “Affine linear sieve, expanders, and sum-product”, Invent. Math., 179:3 (2010), 559–644
- 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
- J. Bourgain, A. Kontorovich, “On Zaremba's conjecture”, C. R. Math. Acad. Sci. Paris, 349:9-10 (2011), 493–495
- J. Bourgain, A. Kontorovich, “On Zaremba's conjecture”, Ann. of Math. (2), 180:1 (2014), 137–196
- J. Bourgain, A. Kontorovich, “On the local–global conjecture for integral Apollonian gaskets”, Invent. Math., 196:3 (2014), 589–650
- E. Breuillard, “A brief introduction to approximate groups”, Thin groups and superstrong approximation, Math. Sci. Res. Inst. Publ., 61, Cambridge Univ. Press, Cambridge, 2014, 23–50
- E. Breuillard, B. Green, “Approximate groups. II. The solvable linear case”, Q. J. Math., 62:3 (2011), 513–521
- E. Breuillard, B. Green, T. Tao, “Approximate subgroups of linear groups”, Geom. Funct. Anal., 21:4 (2011), 774–819
- E. Breuillard, B. Green, T. Tao, “The structure of approximate groups”, Publ. Math. Inst. Hautes Etudes Sci., 116 (2012), 115–221
- V. Brun, Le crible d'Eratosthène et le theorème de Goldbach, Skr. Nor. Vidensk. Akad. Kristiania I, 3, En Commission chez J. Dybwad, Kristiania, 1920, 36 pp.
- J. Button, C. M. Roney-Dougal, “An explicit upper bound for the Helfgott delta in $operatorname{SL}(2,p)$”, J. Algebra, 421 (2015), 493–511
- F. R. K. Chung, R. L. Graham, R. M. Wilson, “Quasi-random graphs”, Combinatorica, 9:4 (1989), 345–362
- M. DeVos, The structure of critical product sets, 2013, 147 pp.
- G. Elekes, “On linear combinatorics. I. Concurrency – an algebraic approach”, Combinatorica, 17:4 (1997), 447–458
- G. Elekes, “On the number of sums and products”, Acta Arith., 81:4 (1997), 365–367
- G. Elekes, “On linear combinatorics. II. Structure theorems via additive number theory”, Combinatorica, 18:1 (1998), 13–25
- G. Elekes, “SUMS versus PRODUCTS in number theory, algebra and Erdős geometry”, Paul Erdős and his mathematics (Budapest, 1999), v. II, Bolyai Soc. Math. Stud., 11, Janos Bolyai Math. Soc., Budapest, 2002, 241–290
- A. Eskin, S. Mozes, Hee Oh, “On uniform exponential growth for linear groups”, Invent. Math., 160:1 (2005), 1–30
- E. Fouvry, E. Kowalski, P. Michel, “Algebraic trace functions over the primes”, Duke Math. J., 163:9 (2014), 1683–1736
- Г. А. Фрейман, “Группы и обратные задачи аддитивной теории чисел”, Теоретико-числовые исследования по спектру Маркова и структурной теории сложения множеств, Калинин. гос. ун-т, М., 1973, 175–183
- Г. А. Фрейман, Начала структурной теории сложения множеств, Казан. гос. пед. ин-т, Казань, 1966, 140 с.
- G. A. Freiman, “On finite subsets of nonabelian groups with small doubling”, Proc. Amer. Math. Soc., 140:9 (2012), 2997–3002
- G. Frobenius, “Über Gruppencharaktere”, Sitzungber. Preuss. Akad. Wiss. Berlin, 1896, 985–1021
- D. A. Frolenkov, I. D. Kan, “A strengthening of a theorem of Bourgain–Kontorovich. II”, Mosc. J. Comb. Number Theory, 4:1 (2014), 78–117
- A. Gamburd, “On the spectral gap for infinite index ‘congruence’ subgroups of $operatorname{SL}_2(mathbb Z)$”, Israel J. Math., 127 (2002), 157–200
- N. Gill, “Quasirandom group actions”, Forum Math. Sigma, 4 (2016), e24, 35 pp.
- N. Gill, L. Pyber, I. Short, E. Szabo, “On the product decomposition conjecture for finite simple groups”, Groups Geom. Dyn., 7:4 (2013), 867–882
- A. S. Golsefidy, P. P. Varju, “Expansion in perfect groups”, Geom. Funct. Anal., 22:6 (2012), 1832–1891
- T. Gowers, “A new proof of Szemeredi's theorem for arithmetic progressions of length four”, Geom. Funct. Anal., 8:3 (1998), 529–551
- W. T. Gowers, “Quasirandom groups”, Combin. Probab. Comput., 17:3 (2008), 363–387
- B. Green, I. Z. Ruzsa, “Freiman's theorem in an arbitrary abelian group”, J. Lond. Math. Soc. (2), 75:1 (2007), 163–175
- B. Green, T. Tao, “Linear equations in primes”, Ann. of Math. (2), 171:3 (2010), 1753–1850
- M. Gromov, “Groups of polynomial growth and expanding maps”, Inst. Hautes Etudes Sci. Publ. Math., 53 (1981), 53–78
- L. Guth, N. H. Katz, “On the Erdős distinct distances problem in the plane”, Ann. of Math. (2), 181:1 (2015), 155–190
- Y. O. Hamidoune, “Some additive applications of the isoperimetric approach”, Ann. Inst. Fourier (Grenoble), 58:6 (2008), 2007–2036
- Y. O. Hamidoune, “Two inverse results”, Combinatorica, 33:2 (2013), 217–230
- G. H. Hardy, J. E. Littlewood, “Some problems of ‘Partitio Numerorum’. III. On the expression of a number as a sum of primes”, Acta Math., 44:1 (1923), 1–70
- Р. Хартсхорн, Алгебраическая геометрия, Мир, М., 1981, 600 с.
- H. A. Helfgott, “Growth and generation in $operatorname{SL}_2(mathbb{Z}/pmathbb{Z})$”, Ann. of Math. (2), 167:2 (2008), 601–623
- H. A. Helfgott, “Growth in $operatorname{SL}_3(mathbb{Z}/pmathbb{Z})$”, J. Eur. Math. Soc. (JEMS), 13:3 (2011), 761–851
- H. A. Helfgott, “Growth in groups: ideas and perspectives”, Bull. Amer. Math. Soc. (N. S.), 52:3 (2015), 357–413
- D. Hensley, “The distribution of badly approximable numbers and continuants with bounded digits”, Theorie des nombres (Quebec, QC, 1987), de Gruyter, Berlin, 1989, 371–385
- D. Hensley, “The distribution of badly approximable rationals and continuants with bounded digits. II”, J. Number Theory, 34:3 (1990), 293–334
- D. Hensley, “Continued fraction Cantor sets, Hausdorff dimension, and functional analysis”, J. Number Theory, 40:3 (1992), 336–358
- D. Hensley, “The distribution mod $n$ of fractions with bounded partial quotients”, Pacific J. Math., 166:1 (1994), 43–54
- D. Hensley, “A polynomial time algorithm for the Hausdorff dimension of continued fraction Cantor sets”, J. Number Theory, 58:1 (1996), 9–45
- E. Hlawka, “Funktionen von beschränkter Variation in der Theorie der Gleichverteilung”, Ann. Mat. Pura Appl. (4), 54 (1961), 325–333
- E. Hrushovski, “Stable group theory and approximate subgroups”, J. Amer. Math. Soc., 25:1 (2012), 189–243
- E. Hrushovski, F. Wagner, “Counting and dimensions”, Model theory with applications to algebra and analysis, v. II, London Math. Soc. Lecture Note Ser., 350, Cambridge Univ. Press, Cambridge, 2008, 161–176
- M. N. Huxley, “Exceptional eigenvalues and congruence subgroups”, The Selberg trace formula and related topics (Brunswick, Maine, 1984), Contemp. Math., 53, Amer. Math. Soc., Providence, RI, 1986, 341–349
- И. Д. Кан, “Усиление теоремы Бургейна–Конторовича. IV”, Изв. РАН. Сер. матем., 80:6 (2016), 103–126
- А. А. Карацуба, Основы аналитической теории чисел, 2-е изд., Наука, М., 1983, 240 с.
- J. H. B. Kempermann, “On complexes in a semigroup”, Nederl. Akad. Wetensch. Proc. Ser. A, 59, = Indag. Math., 18 (1956), 247–254
- B. Kerr, I. E. Shparlinski, “Bilinear sums of Kloosterman sums, multiplicative congruences and average values of the divisor function over families of arithmetic progression”, Res. Number Theory, 6:1 (2020), 16, 21 pp.
- А. Я. Хинчин, Цепные дроби, 3-е изд., Физматгиз, М., 1961, 112 с.
- J. F. Koksma, “A general theorem from the theory of uniform distribution modulo $1$”, Mathematica, Zutphen. B, 11 (1942), 7–11 (Dutch)
- A. Kontorovich, The hyperbolic lattice point count in infinite volume with applications to sieves, Ph.D. thesis, Columbia Univ., 2007, 79 pp.
- A. Kontorovich, “From Apollonius to Zaremba: local–global phenomena in thin orbits”, Bull. Amer. Math. Soc. (N. S.), 50:2 (2013), 187–228
- A. Kontorovich, “The orbital circle method”, Thin groups and superstrong approximation, Math. Sci. Res. Inst. Publ., 61, Cambridge Univ. Press, Cambridge, 2014, 93–106
- A. Kontorovich, “Levels of distribution and the affine sieve”, Ann. Fac. Sci. Toulouse Math. (6), 23:5 (2014), 933–966
- A. Kontorovich, D. D. Long, A. Lubotzky, A. W. Reid, “What is… a thin group?”, Notices Amer. Math. Soc., 66:6 (2019), 905–910
- Н. М. Коробов, Теоретико-числовые методы в приближенном анализе, Физматгиз, М., 1963, 224 с.
- E. Kowalski, “Explicit growth and expansion for $operatorname{SL}_2$”, Int. Math. Res. Not. IMRN, 2013:24 (2013), 5645–5708
- E. Kowalski, An introduction to expander graphs, Cours Spec., 26, Soc. Math. France, Paris, 2019, x+276 pp.
- E. Kowalski, P. Michel, W. Sawin, “Bilinear forms with Kloosterman sums and applications”, Ann. of Math. (2), 186:2 (2017), 413–500
- E. Kowalski, Ph. Michel, W. Sawin, Bilinear forms with Kloosterman sums. II, Ver. 1, 2018 (v4 – 2020), 44 pp.
- E. Kowalski, Ph. Michel, W. Sawin, Bilinear forms with generalized Kloosterman sums, Ver. 2, 2018 (v1 – 2018, v4 – 2020), 56 pp.
- Л. Кейперс, Г. Нидеррейтер, Равномерное распределение последовательностей, Наука, М., 1985, 408 с.
- V. Landazuri, G. M. Seitz, “On the minimal degrees of projective representations of the finite Chevalley groups”, J. Algebra, 32:2 (1974), 418–443
- S. Lang, A. Weil, “Number of points of varieties in finite fields”, Amer. J. Math., 76:4 (1954), 819–827
- M. Larsen, R. Pink, “Finite subgroups of algebraic groups”, J. Amer. Math. Soc., 24:4 (2011), 1105–1158
- Ю. В. Линник, Эргодические свойства алгебраических полей, Изд-во Ленингр. ун-та, Л., 1967, 208 с.
- A. Lubotzky, “Cayley graphs: eigenvalues, expanders and random walks”, Surveys in combinatorics, London Math. Soc. Lecture Note Ser., 218, Cambridge Univ. Press, Cambridge, 1995, 155–189
- S. Macourt, I. E. Shparlinski, “Double sums of Kloosterman sums in finite fields”, Finite Fields Appl., 60 (2019), 101575, 7 pp.
- M. Magee, Hee Oh, D. Winter, Expanding maps and continued fractions, 2015 (v1 – 2014), 46 pp.
- M. Magee, Hee Oh, D. Winter, “Uniform congruence counting for Schottky semigroups in $operatorname{SL}_2 (mathbb{Z})$”, J. Reine Angew. Math., 2019:753 (2019), 89–135
- G. A. Margulis, “Explicit constructions of graphs without short cycles and low density codes”, Combinatorica, 2:1 (1982), 71–78
- T. Miyake, Modular forms, Springer Monogr. Math., Corr. reprint of the 1st ed., Springer-Verlag, Berlin, 2006, x+335 pp.
- Н. Г. Мощевитин, “О множествах вида $mathscr A+mathscr B$ и конечных цепных дробях”, Матем. сб., 198:4 (2007), 95–116
- N. G. Moshchevitin, On some open problems in Diophantine approximation, 2012, 42 pp.
- N. Moshchevitin, B. Murphy, I. Shkredov, “Popular products and continued fractions”, Israel J. Math., 238:2 (2020), 807–835
- N. G. Moshchevitin, I. D. Shkredov, “On a modular form of Zaremba's conjecture”, Pacific J. Math., 309:1 (2020), 195–211
- B. Murphy, Group action combinatorics, 2019, 33 pp.
- B. Murphy, “Upper and lower bounds for rich lines in grids”, Amer. J. Math., 143:2 (2021), 577–611
- B. Murphy, O. Roche-Newton, I. Shkredov, “Variations on the sum-product problem”, SIAM J. Discrete Math., 29:1 (2015), 514–540
- B. Murphy, M. Rudnev, S. Stevens, Bisector energy and pinned distances in positive characteristic, 2019, 17 pp.
- B. Murphy, J. Wheeler, “Growth in some finite three-dimensional matrix groups”, SIAM J. Discrete Math., 34:3 (2020), 1984–1998
- М. А. Наймарк, Теория представлений групп, 2-е изд., Физматлит, М., 2010, 576 с.
- H. Niederreiter, “Dyadic fractions with small partial quotients”, Monatsh. Math., 101:4 (1986), 309–315
- N. Nikolov, L. Pyber, “Product decompositions of quasirandom groups and a Jordan type theorem”, J. Eur. Math. Soc. (JEMS), 13:4 (2011), 1063–1077
- E. Noether, “Ein algebraisches Kriterium für absolute Irreduzibilität”, Math. Ann., 85:1 (1922), 26–40
- К. И. Ольмезов, “Элементарный аналог операторного метода в аддитивной комбинаторике”, Матем. заметки, 109:1 (2021), 117–128
- J. E. Olson, “On the sum of two sets in a group”, J. Number Theory, 18:1 (1984), 110–120
- J. Pach, M. Sharir, “Geometric incidences”, Towards a theory of geometric graphs, Contemp. Math., 342, Amer. Math. Soc., Providence, RI, 2004, 185–224
- G. Petridis, “New proofs of Plünnecke-type estimates for product sets in groups”, Combinatorica, 32:6 (2012), 721–733
- G. Petridis, Ol. Roche-Newton, M. Rudnev, A. Warren, “An energy bound in the affine group”, Int. Math. Res. Not. IMRN, 2020, rnaa130, 19 pp., Publ. online
- M. Pollicott, P. Vytnova, Hausdorff dimension estimates applied to Lagrange and Markov spectra, Zaremba theory, and limit sets of Fuchsian groups, 2020, 53 pp.
- L. Pyber, E. Szabo, “Growth in linear groups”, Thin groups and superstrong approximation, Math. Sci. Res. Inst. Publ., 61, Cambridge Univ. Press, Cambridge, 2014, 253–268
- L. Pyber, E. Szabo, “Growth in finite simple groups of Lie type”, J. Amer. Math. Soc., 29:1 (2016), 95–146
- A. S. Rapinchuk, “Strong approximation for algebraic groups”, Thin groups and superstrong approximation, Math. Sci. Res. Inst. Publ., 61, Cambridge Univ. Press, Cambridge, 2014, 269–298
- A. A. Razborov, “A product theorem in free groups”, Ann. of Math. (2), 179:2 (2014), 405–429
- Ol. Roche-Newton, I. Z. Ruzsa, Chun-Yen Shen, I. D. Shkredov, “On the size of the set $AA+A$”, J. Lond. Math. Soc. (2), 99:2 (2019), 477–494
- Ol. Roche-Newton, A. Warren, “New expander bounds from affine group energy”, Discrete Comput. Geom., 66:2 (2021), 552–574
- M. Rudnev, “On the number of incidences between points and planes in three dimensions”, Combinatorica, 38:1 (2018), 219–254
- M. Rudnev, I. D. Shkredov, On growth rate in $operatorname{SL}_2(mathbb{F}_p)$, the affine group and sum-product type implications, 2019 (v1 – 2018), 43 pp.
- М. Г. Рукавишникова, “Вероятностная оценка суммы неполных частных дробей с фиксированным знаменателем”, Чебышевский сб., 7:4 (2006), 113–121
- I. Z. Ruzsa, “Sums of finite sets”, Number theory: New York seminar 1991–1995, Springer, New York, 281–293
- T. Sanders, “A quantitative version of the non-Abelian idempotent theorem”, Geom. Funct. Anal., 21:1 (2011), 141–221
- T. Sanders, “Approximate groups and doubling metrics”, Math. Proc. Cambridge Philos. Soc., 152:3 (2012), 385–404
- T. Sanders, An analytic approach to a weak non-Abelian Kneser-type theorem, 2012, 6 pp.
- T. Sanders, “The structure theory of sets addition revisited”, Bull. Amer. Math. Soc. (N. S.), 50:1 (2013), 93–127
- P. Sarnak, Xiaoxi Xue, “Bounds for multiplicities of automorphic representations”, Duke Math. J., 64:1 (1991), 207–227
- A. Schinzel, W. Sierpinksi, “Sur certaines hypothèses concernant les nombres premiers”, Acta Arith., 4 (1958), 185–208
- W. M. Schmidt, “Irregularities of distribution. VII”, Acta Arith., 21 (1972), 45–50
- T. Schoen, I. D. Shkredov, “Higher moments of convolutions”, J. Number Theory, 133:5 (2013), 1693–1737
- Ж.-П. Серр, Линейные представления конечных групп, Мир, М., 1970, 132 с.
- И. Д. Шкредов, “Несколько новых результатов о старших энергиях”, Тр. ММО, 74, № 1, МЦНМО, М., 2013, 35–73
- И. Д. Шкредов, “Структурные теоремы в аддитивной комбинаторике”, УМН, 70:1(421) (2015), 123–178
- И. Д. Шкредов, “Несколько замечаний к теореме о разложимости Балога–Вули и величинах $D^+$, $D^times$”, Теория чисел и приложения, 2, К 80-летию со дня рождения профессора Анатолия Алексеевича Карацубы, Совр. пробл. матем., 24, МИАН, М., 2017, 85–103
- И. Д. Шкредов, “Об асимптотических формулах в некоторых вопросах теории сумм произведений”, Тр. ММО, 79, № 2, МЦНМО, М., 2018, 271–334
- I. D. Shkredov, “Some remarks on products of sets in the Heisenberg group and in the affine group”, Forum Math., 32:1 (2020), 189–199
- I. D. Shkredov, Growth in Chevalley groups relatively to parabolic subgroups and some applications, 2020, 25 pp.
- И. Д. Шкредов, “О спектральном зазоре и диаметре графа Кэли”, Труды МИАН, 314 (2021), 318–337
- I. D. Shkredov, “Modular hyperbolas and bilinear forms of Kloosterman sums”, J. Number Theory, 220 (2021), 182–211
- I. E. Shparlinski, “Distribution of modular inverses and multiples of small integers and the Sato–Tate conjecture on average”, Michigan Math. J., 56:1 (2008), 99–111
- I. E. Shparlinski, “Modular hyperbolas”, Jpn. J. Math., 7:2 (2012), 235–294
- I. E. Shparlinski, “On sums of Kloosterman and Gauss sums”, Trans. Amer. Math. Soc., 371:12 (2019), 8679–8697
- I. E. Shparlinski, Tianping Zhang, “Cancellations amongst Kloosterman sums”, Acta Arith., 176:3 (2016), 201–210
- Р. Стейнберг, Лекции о группах Шевалле, Мир, М., 1975, 262 с.
- S. Stevens, F. de Zeeuw, “An improved point-line incidence bound over arbitrary fields”, Bull. Lond. Math. Soc., 49:5 (2017), 842–858
- M. Suzuki, Group theory. I, Grundlehren Math. Wiss., 247, Springer-Verlag, Berlin–New York, 1982, xiv+434 pp.
- E. Szemeredi, W. T. Trotter, Jr., “Extremal problems in discrete geometry”, Combinatorica, 3:3-4 (1983), 381–392
- T. Szőnyi, “Around Redei's theorem”, Discrete Math., 208/209 (1999), 557–575
- T. Tao, “Product set estimates for non-commutative groups”, Combinatorica, 28:5 (2008), 547–594
- T. Tao, Expansion in finite simple groups of Lie type, Grad. Stud. Math., 164, Amer. Math. Soc., Providence, RI, 2015, xiv+303 pp.
- T. Tao, Van H. Vu, Additive combinatorics, Cambridge Stud. Adv. Math., 105, Cambridge Univ. Press, Cambridge, 2006, xviii+512 pp.
- M. C. H. Tointon, “Freiman's theorem in an arbitrary nilpotent group”, Proc. Lond. Math. Soc. (3), 109:2 (2014), 318–352
- M. C. H. Tointon, Introduction to approximate groups, London Math. Soc. Stud. Texts, 94, Cambridge Univ. Press, Cambridge, 2019, xiii+205 pp.
- И. М. Виноградов, Основы теории чисел, 10-е изд., стер., Лань, СПб., 2004, 176 с.
- S. K. Zaremba, “Good lattice points, discrepancy, and numerical integration”, Ann. Mat. Pura Appl. (4), 73 (1966), 293–317
- S. K. Zaremba, “La methode des ‘bons treillis’ pour le calcul des integrales multiples”, Applications of number theory to numerical analysis (Univ. Montreal, Montreal, QC, 1971), Academic Press, New York, 1972, 39–119
Supplementary files
