A product theorem in free groups

Abstract

If $A$ is a finite subset of a free group with at least two noncommuting elements, then $|A\cdot A\cdot A|\geq\frac{|A|^2}{(\log |A|)^{O(1)}}$. More generally, the same conclusion holds in an arbitrary virtually free group, unless $A$ generates a virtually cyclic subgroup. The central part of the proof of this result is carried on by estimating the number of collisions in multiple products $A_1\cdot\ldots\cdot A_k$. We include a few simple observations showing that in this “statistical” context the analogue of the fundamental Plünnecke-Ruzsa theory looks particularly simple and appealing.

  • [BIW] Go to document B. Barak, R. Impagliazzo, and A. Wigderson, "Extracting randomness using few independent sources," SIAM J. Comput., vol. 36, iss. 4, pp. 1095-1118, 2006.
    @article {BIW, MRKEY = {2272272},
      AUTHOR = {Barak, Boaz and Impagliazzo, Russell and Wigderson, Avi},
      TITLE = {Extracting randomness using few independent sources},
      JOURNAL = {SIAM J. Comput.},
      FJOURNAL = {SIAM Journal on Computing},
      VOLUME = {36},
      YEAR = {2006},
      NUMBER = {4},
      PAGES = {1095--1118},
      ISSN = {0097-5397},
      MRCLASS = {68Q10 (05C55 68W20)},
      MRNUMBER = {2272272},
      MRREVIEWER = {Heng Liang},
      DOI = {10.1137/S0097539705447141},
      ZBLNUMBER = {1127.68030},
      }
  • [BRS*] Go to document B. Barak, A. Rao, R. Shaltiel, and A. Wigderson, "2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction," in STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM, 2006, pp. 671-680.
    @incollection {BRS*, MRKEY = {2277192},
      AUTHOR = {Barak, Boaz and Rao, Anup and Shaltiel, Ronen and Wigderson, Avi},
      TITLE = {2-source dispersers for sub-polynomial entropy and {R}amsey graphs beating the {F}rankl-{W}ilson construction},
      BOOKTITLE = {S{TOC}'06: {P}roceedings of the 38th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      PAGES = {671--680},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      YEAR = {2006},
      MRCLASS = {68R10 (05C55 68W20)},
      MRNUMBER = {2277192},
      DOI = {10.1145/1132516.1132611},
      ZBLNUMBER = {1122.68300},
     }
  • [BoGa] Go to document J. Bourgain and A. Gamburd, "Uniform expansion bounds for Cayley graphs of ${ SL}_2(\Bbb F_p)$," Ann. of Math., vol. 167, iss. 2, pp. 625-642, 2008.
    @article {BoGa, MRKEY = {2415383},
      AUTHOR = {Bourgain, Jean and Gamburd, Alex},
      TITLE = {Uniform expansion bounds for {C}ayley graphs of {${\rm SL}\sb 2(\Bbb F\sb p)$}},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {167},
      YEAR = {2008},
      NUMBER = {2},
      PAGES = {625--642},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {20F65 (05C25 05E15 11B30 20G40)},
      MRNUMBER = {2415383},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.4007/annals.2008.167.625},
      ZBLNUMBER = {1216.20042},
      }
  • [BKT] Go to document J. Bourgain, N. Katz, and T. Tao, "A sum-product estimate in finite fields, and applications," Geom. Funct. Anal., vol. 14, iss. 1, pp. 27-57, 2004.
    @article {BKT, MRKEY = {2053599},
      AUTHOR = {Bourgain, Jean and Katz, N. and Tao, T.},
      TITLE = {A sum-product estimate in finite fields, and applications},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {14},
      YEAR = {2004},
      NUMBER = {1},
      PAGES = {27--57},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {11B75 (11T30)},
      MRNUMBER = {2053599},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.1007/s00039-004-0451-1},
      ZBLNUMBER = {1145.11306},
     }
  • [Cha] Go to document M. Chang, "Product theorems in ${ SL}_2$ and ${ SL}_3$," J. Inst. Math. Jussieu, vol. 7, iss. 1, pp. 1-25, 2008.
    @article {Cha, MRKEY = {2398145},
      AUTHOR = {Chang, Mei-Chu},
      TITLE = {Product theorems in {${\rm SL}\sb 2$} and {${\rm SL}\sb 3$}},
      JOURNAL = {J. Inst. Math. Jussieu},
      FJOURNAL = {Journal of the Institute of Mathematics of Jussieu. JIMJ. Journal de l'Institut de Mathématiques de Jussieu},
      VOLUME = {7},
      YEAR = {2008},
      NUMBER = {1},
      PAGES = {1--25},
      ISSN = {1474-7480},
      MRCLASS = {20G30 (11B75 11H56 20G20)},
      MRNUMBER = {2398145},
      MRREVIEWER = {Serge{\u\i} V. Konyagin},
      DOI = {10.1017/S1474748007000126},
      ZBLNUMBER = {1167.20328},
      }
  • [Gow] Go to document W. T. Gowers, "A new proof of Szemerédi’s theorem for arithmetic progressions of length four," Geom. Funct. Anal., vol. 8, iss. 3, pp. 529-551, 1998.
    @article {Gow, MRKEY = {1631259},
      AUTHOR = {Gowers, W. T.},
      TITLE = {A new proof of {S}zemerédi's theorem for arithmetic progressions of length four},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {8},
      YEAR = {1998},
      NUMBER = {3},
      PAGES = {529--551},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {11B25 (11N13)},
      MRNUMBER = {1631259},
      MRREVIEWER = {D. R. Heath-Brown},
      DOI = {10.1007/s000390050065},
      ZBLNUMBER = {0907.11005},
     }
  • [Haa] Go to document U. Haagerup, "An example of a non nuclear $C^{\ast} $-algebra, which has the metric approximation property," Invent. Math., vol. 50, iss. 3, pp. 279-293, 1978/79.
    @article {Haa, MRKEY = {0520930},
      AUTHOR = {Haagerup, Uffe},
      TITLE = {An example of a non nuclear {$C\sp{\ast} $}-algebra, which has the metric approximation property},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {50},
      YEAR = {1978/79},
      NUMBER = {3},
      PAGES = {279--293},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {46L05 (22D35 43A35)},
      MRNUMBER = {0520930},
      MRREVIEWER = {Ole A. Nielsen},
      DOI = {10.1007/BF01410082},
      ZBLNUMBER = {0408.46046},
     }
  • [Hel] Go to document H. A. Helfgott, "Growth and generation in ${ SL}_2(\Bbb Z/p\Bbb Z)$," Ann. of Math., vol. 167, iss. 2, pp. 601-623, 2008.
    @article {Hel, MRKEY = {2415382},
      AUTHOR = {Helfgott, H. A.},
      TITLE = {Growth and generation in {${\rm SL}\sb 2(\Bbb Z/p\Bbb Z)$}},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {167},
      YEAR = {2008},
      NUMBER = {2},
      PAGES = {601--623},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {20G40 (05C25 20F69)},
      MRNUMBER = {2415382},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.4007/annals.2008.167.601},
      ZBLNUMBER = {1213.20045},
     }
  • [Hel2] H. A. Helfgott, Growth in groups: ideas and perspectives, 2013.
    @misc{Hel2,
      author = {Helfgott, H. A.},
      TITLE = {Growth in groups: ideas and perspectives},
      YEAR={2013},
      ARXIV={1303.0239},
     }
  • [Jol] Go to document P. Jolissaint, "Rapidly decreasing functions in reduced $C^*$-algebras of groups," Trans. Amer. Math. Soc., vol. 317, iss. 1, pp. 167-196, 1990.
    @article {Jol, MRKEY = {0943303},
      AUTHOR = {Jolissaint, Paul},
      TITLE = {Rapidly decreasing functions in reduced {$C\sp *$}-algebras of groups},
      JOURNAL = {Trans. Amer. Math. Soc.},
      FJOURNAL = {Transactions of the American Mathematical Society},
      VOLUME = {317},
      YEAR = {1990},
      NUMBER = {1},
      PAGES = {167--196},
      ISSN = {0002-9947},
      CODEN = {TAMTAM},
      MRCLASS = {22D25 (43A15 46L99)},
      MRNUMBER = {0943303},
      MRREVIEWER = {A. Derighetti},
      DOI = {10.2307/2001458},
      ZBLNUMBER = {0711.46054},
      }
  • [KhM] Go to document O. Kharlampovich and A. Myasnikov, "Implicit function theorem over free groups," J. Algebra, vol. 290, iss. 1, pp. 1-203, 2005.
    @article {KhM, MRKEY = {2154989},
      AUTHOR = {Kharlampovich, Olga and Myasnikov, Alexei},
      TITLE = {Implicit function theorem over free groups},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {290},
      YEAR = {2005},
      NUMBER = {1},
      PAGES = {1--203},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20E05 (20F10)},
      MRNUMBER = {2154989},
      MRREVIEWER = {Alina A. Vdovina},
      DOI = {10.1016/j.jalgebra.2005.04.001},
      ZBLNUMBER = {1094.20016},
      }
  • [KhM3] Go to document O. Kharlampovich and A. Myasnikov, "Elementary theory of free non-abelian groups," J. Algebra, vol. 302, iss. 2, pp. 451-552, 2006.
    @article {KhM3, MRKEY = {2293770},
      AUTHOR = {Kharlampovich, Olga and Myasnikov, Alexei},
      TITLE = {Elementary theory of free non-abelian groups},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {302},
      YEAR = {2006},
      NUMBER = {2},
      PAGES = {451--552},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20E05 (03B25 03C60 20F10)},
      MRNUMBER = {2293770},
      MRREVIEWER = {O. V. Belegradek},
      DOI = {10.1016/j.jalgebra.2006.03.033},
      ZBLNUMBER = {1110.03020},
     }
  • [Kow] E. Kowalski, Sieve in expansion.
    @misc{Kow,
      author={Kowalski, E.},
      TITLE={Sieve in expansion},
      NOTE={Technical Report 1028, Séminaire Bourbaki, 63éme année, 2010--2011},
     }
  • [Lub] Go to document A. Lubotzky, "Expander graphs in pure and applied mathematics," Bull. Amer. Math. Soc., vol. 49, iss. 1, pp. 113-162, 2012.
    @article {Lub, MRKEY = {2869010},
      AUTHOR = {Lubotzky, Alexander},
      TITLE = {Expander graphs in pure and applied mathematics},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {49},
      YEAR = {2012},
      NUMBER = {1},
      PAGES = {113--162},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {05-02 (05C40 11N05 11N35 20F65 68R10)},
      MRNUMBER = {2869010},
      MRREVIEWER = {Mikhail Ostrovskii},
      DOI = {10.1090/S0273-0979-2011-01359-3},
      ZBLNUMBER = {1232.05194},
     }
  • [Lyn] Go to document R. C. Lyndon, "Equations in free groups," Trans. Amer. Math. Soc., vol. 96, pp. 445-457, 1960.
    @article {Lyn, MRKEY = {0151503},
      AUTHOR = {Lyndon, Roger C.},
      TITLE = {Equations in free groups},
      JOURNAL = {Trans. Amer. Math. Soc.},
      FJOURNAL = {Transactions of the American Mathematical Society},
      VOLUME = {96},
      YEAR = {1960},
      PAGES = {445--457},
      ISSN = {0002-9947},
      MRCLASS = {20.10},
      MRNUMBER = {0151503},
      MRREVIEWER = {V. K. Belov},
      DOI = {10.2307/1993533},
      ZBLNUMBER = {0108.02301},
     }
  • [LyS] R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, New York: Springer-Verlag, 1977, vol. 89.
    @book {LyS, MRKEY = {0577064},
      AUTHOR = {Lyndon, Roger C. and Schupp, Paul E.},
      TITLE = {Combinatorial Group Theory},
      SERIES = {Ergeb. Math. Grenzgeb.},
      VOLUME={89},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1977},
      PAGES = {xiv+339},
      ISBN = {3-540-07642-5},
      MRCLASS = {20F05 (55A05)},
      MRNUMBER = {0577064},
      MRREVIEWER = {Ian M. Chiswell},
      ZBLNUMBER = {0368.20023},
      }
  • [Nat] M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, New York: Springer-Verlag, 1996, vol. 165.
    @book {Nat, MRKEY = {1477155},
      AUTHOR = {Nathanson, Melvyn B.},
      TITLE = {Additive Number Theory: Inverse Problems and the Geometry of Sumsets},
      SERIES = {Grad. Texts in Math.},
      VOLUME = {165},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1996},
      PAGES = {xiv+293},
      ISBN = {0-387-94655-1},
      MRCLASS = {11Bxx (11-02)},
      MRNUMBER = {1477155},
      MRREVIEWER = {Yuri Bilu},
      ZBLNUMBER = {0859.11003},
      }
  • [Sela] Go to document Z. Sela, "Diophantine geometry over groups. VI. The elementary theory of a free group," Geom. Funct. Anal., vol. 16, iss. 3, pp. 707-730, 2006.
    @article {Sela, MRKEY = {2238945},
      AUTHOR = {Sela, Z.},
      TITLE = {Diophantine geometry over groups. {VI}. {T}he elementary theory of a free group},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {16},
      YEAR = {2006},
      NUMBER = {3},
      PAGES = {707--730},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {20F65 (03C07 03C10 03C65 20E05 20F10)},
      MRNUMBER = {2238945},
      MRREVIEWER = {Daniel P. Groves},
      DOI = {10.1007/s00039-006-0565-8},
      ZBLNUMBER = {1118.20035},
     }
  • [Tao] Go to document T. Tao, "Product set estimates for non-commutative groups," Combinatorica, vol. 28, iss. 5, pp. 547-594, 2008.
    @article{Tao, MRKEY={2501249},
      AUTHOR={Tao, Terence},
      TITLE = {Product set estimates for non-commutative groups},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {28},
      YEAR = {2008},
      NUMBER = {5},
      PAGES = {547--594},
      MRCLASS = {11B30 (11P70)},
      MRNUMBER = {2501249},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.1007/s00493-008-2271-7},
      ZBLNUMBER = {1254.11017},
      }
  • [TaV] Go to document T. Tao and V. H. Vu, Additive Combinatorics, Cambridge: Cambridge Univ. Press, 2006.
    @book {TaV, MRKEY = {2289012},
      AUTHOR = {Tao, Terence and Vu, Van H.},
      TITLE = {Additive Combinatorics},
      SERIES = {Cambridge Stud. Adv. Math.},
      NUMBER = {105},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2006},
      PAGES = {xviii+512},
      ISBN = {978-0-521-85386-6; 0-521-85386-9},
      MRCLASS = {11-02 (05-02 05D10 11B13 11P70 11P82 28D05 37A45)},
      MRNUMBER = {2289012},
      MRREVIEWER = {Serge{\u\i} V. Konyagin},
      DOI = {10.1017/CBO9780511755149},
      ZBLNUMBER = {1127.11002},
     }
  • [Adi] S. I. Adian, The Burnside Problem and Identities in Groups, New York: Springer-Verlag, 1979, vol. 95.
    @book {Adi, MRKEY = {0537580},
      AUTHOR = {Adian, S. I.},
      TITLE = {The {B}urnside Problem and Identities in Groups},
      SERIES = {Ergeb. Math. Grenzgeb.},
      VOLUME = {95},
      NOTE = {translated from the Russian by John Lennox and James Wiegold},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1979},
      PAGES = {xi+311},
      ISBN = {3-540-08728-1},
      MRCLASS = {20F05},
      MRNUMBER = {0537580},
      }
  • [Bul] V. K. Bulitko, "Equations and inequalities in a free group and a free semigroup," Tul. Gos. Ped. Inst. Učen. Zap. Mat. Kaf., iss. 2 Geometr. i Algebra, pp. 242-252, 1970.
    @article {Bul, MRKEY = {0393235},
      AUTHOR = {Bulitko, V. K.},
      TITLE = {Equations and inequalities in a free group and a free semigroup},
      JOURNAL = {Tul. Gos. Ped. Inst. Učen. Zap. Mat. Kaf.},
      NUMBER = {2 Geometr. i Algebra},
      YEAR = {1970},
      PAGES = {242--252},
      MRCLASS = {20E05 (20M05)},
      MRNUMBER = {0393235},
      MRREVIEWER = {V. A. Artamonov},
      }
  • [Mak1] Go to document G. S. Makanin, "Equations in a free group," Izv. Akad. Nauk SSSR Ser. Mat., vol. 46, iss. 6, pp. 1199-1273, 1344, 1982.
    @article {Mak1, MRKEY = {0682490},
      AUTHOR = {Makanin, G. S.},
      TITLE = {Equations in a free group},
      JOURNAL = {Izv. Akad. Nauk SSSR Ser. Mat.},
      FJOURNAL = {Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya},
      VOLUME = {46},
      YEAR = {1982},
      NUMBER = {6},
      PAGES = {1199--1273, 1344},
      ISSN = {0373-2436},
      MRCLASS = {20F05 (20E05 20M05)},
      NOTE = {in Russian; translated in {\it Math. USSR-Izvestiya} {\bf 21} (1983), 483--546},
      MRNUMBER = {0682490},
      ZBLNUMBER = {0527.20018},
      DOI = {10.1070/IM1983v021n03ABEH001803},
     }
  • [equations] Go to document A. A. Razborov, "On systems of equations in a free group," Izv. Akad. Nauk SSSR Ser. Mat., vol. 48, iss. 4, pp. 779-832, 1984.
    @article {equations, MRKEY = {o755958},
      AUTHOR = {Razborov, A. A.},
      TITLE = {On systems of equations in a free group},
      JOURNAL = {Izv. Akad. Nauk SSSR Ser. Mat.},
      FJOURNAL = {Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya},
      VOLUME = {48},
      YEAR = {1984},
      NUMBER = {4},
      PAGES = {779--832},
      ISSN = {0373-2436},
      MRCLASS = {20F10 (03B25 20E05)},
      MRNUMBER = {0755958},
      MRREVIEWER = {R. St{ö}hr},
      NOTE = {in Russian; translated in {\it Math. USSR-Izvestiya} {\bf 25} (1985), 115--162},
      ZBLNUMBER = {0579.20019},
      DOI = {10.1070/IM1985v025n01ABEH001272},
     }
  • [Frei] G. A. Freuiman, Foundations of a Structural Theory of Set Addition, Providence, R. I.: Amer. Math. Soc., 1973.
    @book {Frei, MRKEY = {0360496},
      AUTHOR = {Fre{\u\i}man, G. A.},
      TITLE = {Foundations of a Structural Theory of Set Addition},
      NOTE = {translated from the Russian, \emph{Transl. Math. Monogr.} {\bf 37}},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, R. I.},
      YEAR = {1973},
      PAGES = {vii+108},
      MRCLASS = {10J99 (10AXX)},
      MRNUMBER = {0360496},
      ZBLNUMBER = {0271.10044},
      }

Authors

Alexander A. Razborov

Steklov Mathematical Institute, Moscow, Russia and Institute for Advanced Study, Princeton, NJ

Current address:

University of Chicago, Chicago, IL