Comptes Rendus
Group Theory/Number Theory
Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order
[Estimes sommes–produits et sur les sommes exponentielles associées à des sous-groupes d'un corps d'ordre premier]
Comptes Rendus. Mathématique, Volume 337 (2003) no. 2, pp. 75-80.

Our first result is a ‘sum–product’ theorem for subsets A of the finite field 𝔽p, p prime, providing a lower bound on max(|A+A|,|A·A|). As corollary, the second and main result provides new bounds on exponential sums associated to subgroups of the multiplicative group 𝔽p*.

Notre premier résultat est un théorème « sommes–produits » pour des sous-ensembles A d'un corps fini 𝔽p, p un nombre premier, donnant une minoration du max(|A+A|,|A·A|). Comme corollaire et résultat principal, on en déduit de nouvelles bornes sur les sommes exponentielles associées à des sous-groupes du groupe multiplicatif 𝔽p*.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(03)00281-4

Jean Bourgain 1, 2 ; S.V. Konyagin 3

1 School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA
2 Department of Mathematics, University of Illinois, Urbana, IL 61801, USA
3 Department of Mechanics and Mathematics, Moscow State University, Moscow 119992, Russia
@article{CRMATH_2003__337_2_75_0,
     author = {Jean Bourgain and S.V. Konyagin},
     title = {Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {75--80},
     publisher = {Elsevier},
     volume = {337},
     number = {2},
     year = {2003},
     doi = {10.1016/S1631-073X(03)00281-4},
     language = {en},
}
TY  - JOUR
AU  - Jean Bourgain
AU  - S.V. Konyagin
TI  - Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 75
EP  - 80
VL  - 337
IS  - 2
PB  - Elsevier
DO  - 10.1016/S1631-073X(03)00281-4
LA  - en
ID  - CRMATH_2003__337_2_75_0
ER  - 
%0 Journal Article
%A Jean Bourgain
%A S.V. Konyagin
%T Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order
%J Comptes Rendus. Mathématique
%D 2003
%P 75-80
%V 337
%N 2
%I Elsevier
%R 10.1016/S1631-073X(03)00281-4
%G en
%F CRMATH_2003__337_2_75_0
Jean Bourgain; S.V. Konyagin. Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order. Comptes Rendus. Mathématique, Volume 337 (2003) no. 2, pp. 75-80. doi : 10.1016/S1631-073X(03)00281-4. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(03)00281-4/

[1] J. Bourgain, N. Katz, T. Tao, A sum–product estimate in finite fields and their applications, ArXiv: v1, January 29, 2003, to appear in GAFA | arXiv

[2] G.A. Edgar; C. Miller Borel subrings of the reals, Proc. Amer. Math. Soc., Volume 131 (2003), pp. 1121-1129

[3] Gy. Elekes On the umber of sums and products, Acta Arith., Volume 81 (1997), pp. 1121-1129

[4] P. Erdős; E. Szemerédi On sums and the products of integers (P. Erdős; L. Alpár; G. Halász, eds.), Studies in Pure Mathematics, Akadémiai Kiadó–Birkhäuser, Budapest–Basel, 1983, pp. 213-218 (To the memory of Paul Turan)

[5] K. Ford Sums and products from a finite set of real numbers, Ramanujan J., Volume 2 (1998), pp. 59-66

[6] D.R. Heath-Brown; S.V. Konyagin New bounds for Gauss sums derived from k-th powers, and for Heilbronn's exponential sums, Quart. J. Math., Volume 51 (2000), pp. 221-235

[7] S.V. Konyagin Estimates of trigonometric sums over subgroups and Gaussian sums, IV International Conference “Modern Problems of Number Theory and its Applications” dedicated to 180th anniversary of P.L. Chebyshev and 110th anniversary of I.M. Vinogradov, Topical Problems, Part 3, Department of Mechanics and Mathematics, Moscow Lomonosov State University, Moscow, 2002, pp. 86-114 ([in Russian])

[8] N.M. Korobov Exponential Sums and their Applications, Kluwer Academic, Dordrecht, 1992

[9] S.V. Konyagin; I.E. Shparlinski Character Sums with Exponential Functions and their Applications, Cambridge Tracts in Math., 136, Cambridge University Press, Cambridge, 1999

[10] M. Nathanson On sums and products of integers, Proc. Amer. Math. Soc., Volume 125 (1997), pp. 9-16

[11] I.E. Shparlinski Estimates for Gauss sums, Math. Notes, Volume 50 (1991), pp. 140-146

[12] J. Solymosi, On a question of Erdős and Szemerédi, Preprint, 2003

  • Rodolphe Richard Manin–Mumford topologique fort, Annales de la Faculté des sciences de Toulouse : Mathématiques, Volume 33 (2024) no. 2, p. 419 | DOI:10.5802/afst.1776
  • Weikun He; Nicolas de Saxcé Linear random walks on the torus, Duke Mathematical Journal, Volume 171 (2022) no. 5 | DOI:10.1215/00127094-2021-0045
  • Todd Cochrane; Misty Ostergaard; Craig Spencer Homogeneous additive congruences, Rocky Mountain Journal of Mathematics, Volume 52 (2022) no. 4 | DOI:10.1216/rmj.2022.52.1295
  • Jiyou Li; Daqing Wan Counting polynomial subset sums, The Ramanujan Journal, Volume 47 (2018) no. 1, p. 67 | DOI:10.1007/s11139-018-0020-0
  • Corentin Perret-Gentil Distribution questions for trace functions with values in cyclotomic integers and their reductions, Transactions of the American Mathematical Society, Volume 371 (2018) no. 7, p. 4585 | DOI:10.1090/tran/7333
  • Matthew Thill; Babak Hassibi Low-Coherence Frames From Group Fourier Matrices, IEEE Transactions on Information Theory, Volume 63 (2017) no. 6, p. 3386 | DOI:10.1109/tit.2017.2686420
  • Yu. N. Shteinikov Estimates of trigonometric sums over subgroups and some of their applications, Mathematical Notes, Volume 98 (2015) no. 3-4, p. 667 | DOI:10.1134/s0001434615090333
  • Юрий Николаевич Штейников; Yurii Nikolaevich Shteinikov Оценки тригонометрических сумм по подгруппам и некоторые их приложения, Математические заметки, Volume 98 (2015) no. 4, p. 606 | DOI:10.4213/mzm10629
  • I.D. Shkredov On exponential sums over multiplicative subgroups of medium size, Finite Fields and Their Applications, Volume 30 (2014), p. 72 | DOI:10.1016/j.ffa.2014.06.002
  • Nick Gill; Harald Andrés Helfgott Growth in solvable subgroups of GLr(Z/pZ) GL r ( Z / p Z ), Mathematische Annalen, Volume 360 (2014) no. 1-2, p. 157 | DOI:10.1007/s00208-014-1008-8
  • Konrad DURNOGA NON-MALLEABLE RANDOMNESS EXTRACTORS, National Security Studies, Volume 6 (2014) no. 2, p. 227 | DOI:10.37055/sbn/135232
  • Jean Bourgain Around the Sum-product Phenomenon, Erdős Centennial, Volume 25 (2013), p. 111 | DOI:10.1007/978-3-642-39286-3_4
  • Jiyou Li On the Odlyzko–Stanley enumeration problem and Waringʼs problem over finite fields, Journal of Number Theory, Volume 133 (2013) no. 7, p. 2267 | DOI:10.1016/j.jnt.2012.11.013
  • Elena Grigorescu; Tali Kaufman; Madhu Sudan Succinct Representation of Codes with Applications to Testing, SIAM Journal on Discrete Mathematics, Volume 26 (2012) no. 4, p. 1618 | DOI:10.1137/100818364
  • Илья Владимирович Вьюгин; Il'ya Vladimirovich Vyugin; Илья Дмитриевич Шкредов; Il'ya Dmitrievich Shkredov; Илья Дмитриевич Шкредов; Il'ya Dmitrievich Shkredov Об аддитивных сдвигах мультипликативных подгрупп, Математический сборник, Volume 203 (2012) no. 6, p. 81 | DOI:10.4213/sm7857
  • Venkatesan Guruswami; James R. Lee; Alexander Razborov Almost Euclidean subspaces of ℓ 1 N VIA expander codes, Combinatorica, Volume 30 (2010) no. 1, p. 47 | DOI:10.1007/s00493-010-2463-9
  • Binbin Zhou A note on exponential sums over subgroups of Zp2∗ and their applications, Journal of Number Theory, Volume 130 (2010) no. 11, p. 2467 | DOI:10.1016/j.jnt.2010.05.004
  • Илья Дмитриевич Шкредов; Il'ya Dmitrievich Shkredov Анализ Фурье в комбинаторной теории чисел, Успехи математических наук, Volume 65 (2010) no. 3, p. 127 | DOI:10.4213/rm9355
  • Elena Grigorescu; Tali Kaufman; Madhu Sudan Succinct Representation of Codes with Applications to Testing, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Volume 5687 (2009), p. 534 | DOI:10.1007/978-3-642-03685-9_40
  • J. BOURGAIN; M. Z. GARAEV On a variant of sum-product estimates and explicit exponential sum bounds in prime fields, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 146 (2009) no. 1, p. 1 | DOI:10.1017/s0305004108001230
  • Terence Tao Product set estimates for non-commutative groups, Combinatorica, Volume 28 (2008) no. 5, p. 547 | DOI:10.1007/s00493-008-2271-7
  • I. D. Shkredov On sets with small doubling property, Mathematical Notes, Volume 84 (2008) no. 5-6, p. 859 | DOI:10.1134/s000143460811028x
  • Илья Дмитриевич Шкредов; Il'ya Dmitrievich Shkredov О множествах с малым удвоением, Математические заметки, Volume 84 (2008) no. 6, p. 927 | DOI:10.4213/mzm3996
  • Igor E. Shparlinski; Arne Winterhof Quantum period reconstruction of approximate sequences, Information Processing Letters, Volume 103 (2007) no. 6, p. 211 | DOI:10.1016/j.ipl.2007.02.019
  • Yu. V. Malykhin Bounds for exponential sums modulo p 2, Journal of Mathematical Sciences, Volume 146 (2007) no. 2, p. 5686 | DOI:10.1007/s10958-007-0385-x
  • Ian F. Blake; Theo Garefalakis; Igor E. Shparlinski On the bit security of the Diffie-Hellman key, Applicable Algebra in Engineering, Communication and Computing, Volume 16 (2006) no. 6, p. 397 | DOI:10.1007/s00200-005-0184-x
  • Pierre-Alain Fouque; David Pointcheval; Jacques Stern; Sébastien Zimmer Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie-Hellman Schemes, Automata, Languages and Programming, Volume 4052 (2006), p. 240 | DOI:10.1007/11787006_21
  • William D. Banks; Igor E. Shparlinski Non-residues and primitive roots in Beatty sequences, Bulletin of the Australian Mathematical Society, Volume 73 (2006) no. 3, p. 433 | DOI:10.1017/s0004972700035449
  • William D. Banks; John B. Friedlander; Moubariz Z. Garaev; Igor E. Shparlinski Character sums with exponential functions over smooth numbers, Indagationes Mathematicae, Volume 17 (2006) no. 2, p. 157 | DOI:10.1016/s0019-3577(06)80013-3
  • Moubariz Z. Garaev; Florian Luca; Igor E. Shparlinski Catalan and Apéry numbers in residue classes, Journal of Combinatorial Theory, Series A, Volume 113 (2006) no. 5, p. 851 | DOI:10.1016/j.jcta.2005.08.003
  • Yu. V. Malykhin Estimates of trigonometric sums modulo p r, Mathematical Notes, Volume 80 (2006) no. 5-6, p. 748 | DOI:10.1007/s11006-006-0197-1
  • Юрий Вячеславович Малыхин; Yuri Viatcheslavovich Malykhin Оценки тригонометрических сумм по модулю pr, Математические заметки, Volume 80 (2006) no. 5, p. 793 | DOI:10.4213/mzm3092
  • J. Bourgain Mordell’s exponential sum estimate revisited, Journal of the American Mathematical Society, Volume 18 (2005) no. 2, p. 477 | DOI:10.1090/s0894-0347-05-00476-5
  • J. Bourgain New Encounters in Combinatorial Number Theory: From the Kakeya Problem to Cryptography, Perspectives in Analysis (2005), p. 17 | DOI:10.1007/3-540-30434-7_2
  • Mei-Chu Chang A sum–product theorem in semi-simple commutative Banach algebras, Journal of Functional Analysis, Volume 212 (2004) no. 2, p. 399 | DOI:10.1016/j.jfa.2003.09.009
  • María Isabel González Vasco; Mats Näslund; Igor E. Shparlinski New Results on the Hardness of Diffie-Hellman Bits, Public Key Cryptography – PKC 2004, Volume 2947 (2004), p. 159 | DOI:10.1007/978-3-540-24632-9_12
  • Igor E. Shparlinski; Arne Winterhof A Nonuniform Algorithm for the Hidden Number Problem in Subgroups, Public Key Cryptography – PKC 2004, Volume 2947 (2004), p. 416 | DOI:10.1007/978-3-540-24632-9_30
  • Richard K. Guy None of the Above, Unsolved Problems in Number Theory, Volume 1 (2004), p. 365 | DOI:10.1007/978-0-387-26677-0_7

Cité par 38 documents. Sources : Crossref

Commentaires - Politique