American Institute of Mathematical Sciences

Advanced
  2010, 17: 57-67. doi: 10.3934/era.2010.17.57

Linear approximate groups

Emmanuel Breuillard 1, , Ben Green 2, and  Terence Tao 3,

1. 

Laboratoire de Mathématiques, Bâtiment 425, Université Paris Sud 11, 91405 Orsay, France
2. 

Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WA, United Kingdom
3. 

Department of Mathematics, UCLA, 405 Hilgard Ave, Los Angeles, CA 90095

Received  January 2010 Published  September 2010

This is an informal announcement of results to be described and proved in detail in [3]. We give various results on the structure of approximate subgroups in linear groups such as ${\rm{S}}{{\rm{L}}_n}(k)$. For example, generalizing a result of Helfgott (who handled the cases $n = 2$ and $3$), we show that any approximate subgroup of ${\rm{S}}{{\rm{L}}_n}({\mathbb{F}_q})$ which generates the group must be either very small or else nearly all of ${\rm{S}}{{\rm{L}}_n}({\mathbb{F}_q})$. The argument is valid for all Chevalley groups $G(\mathbb{F}_q)$. Extending work of Bourgain-Gamburd we also announce some applications to expanders, which will be proven in detail in [4].
Keywords: expander graphs., Approximate groups, growth.
Mathematics Subject Classification: 20G40, 20N9.
Citation: Emmanuel Breuillard, Ben Green, Terence Tao. Linear approximate groups. Electronic Research Announcements, 2010, 17: 57-67. doi: 10.3934/era.2010.17.57
References:
[1]

L. Babai and A. Seress, On the diameter of permutation groups, European J. Combin., 13 (1992), 231–-243. doi: doi:10.1016/S0195-6698(05)80029-0.  Google Scholar

[2]

E. Breuillard and B. J. Green, Approximate groups II : The solvable linear case,, preprint, ().   Google Scholar

[3]

E. Breuillard, B. J. Green and T. C. Tao, Approximate subgroups of linear groups,, preprint. \arXiv{1005.1881}, ().   Google Scholar

[4]

E. Breuillard, B. J. Green and T. C. Tao, Expansion in simple groups of Lie type,, preprint., ().   Google Scholar

[5]

J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of $SL_2(F_p)$, Ann. of Math. (2), 167 (2008), 625-642. doi: doi:10.4007/annals.2008.167.625.  Google Scholar

[6]

J. Bourgain and A. Gamburd,, Expansion and random walks in $\SL_d(\Z/p^n\Z)$ I, J. Eur. Math. Soc. (JEMS), 10 (2008), 987-1011.  Google Scholar

[7]

J. Bourgain and A. Gamburd,, Expansion and random walks in $\SL_d(\Z/p^n\Z)$ II, With an appendix by Bourgain, J. Eur. Math. Soc. (JEMS), 11 (2009), 1057-1103.  Google Scholar

[8]

J. Bourgain, A. Gamburd and P. Sarnak, Affine linear sieve, expanders, and sum-product, Invent. Math, Springeronline (2009).  Google Scholar

[9]

J. Bourgain, A. Glibichuk and S. Konyagin, Estimates for the number of sums and products and for exponential sums in fields of prime order, J. London Math. Soc. (2), 73 (2006), 380-398. doi: doi:10.1112/S0024610706022721.  Google Scholar

[10]

M.-C. Chang, Convolution of discrete measures on linear groups, J. Funct. Anal., 253 (2007), 303-323. doi: doi:10.1016/j.jfa.2007.03.008.  Google Scholar

[11]

M.-C. Chang, Product theorems in $\SL_2$ and $\SL_3$, J. Math. Jussieu, 7 (2008), 1-–25.  Google Scholar

[12]

M.-C. Chang, On product sets in $\SL_2$ and $\SL_3$,, preprint., ().   Google Scholar

[13]

M.-C. Chang, Some consequences of the polynomial Freiman-Ruzsa conjecture, C. R. Math. Acad. Sci. Paris, 347 (2009), 583-588.  Google Scholar

[14]

L. E. Dickson, "Linear groups with an exposition of Galois Field Theory," Chapter XII, Cosimo classics, New York, 2007. Google Scholar

[15]

O. Dinai, Expansion properties of finite simple groups,, preprint. \arXiv{1001.5069}, ().   Google Scholar

[16]

A. Eskin, S. Mozes and H. Oh, On uniform exponential growth for linear groups, Invent. Math., 160 (2005), 1-30. doi: doi:10.1007/s00222-004-0378-z.  Google Scholar

[17]

A. Gamburd, S. Hoory, M. Shahshahani, A. Shalev and B. Virag, On the girth of random Cayley graphs, Random Structures Algorithms, 35 (2009), 100-117. doi: doi:10.1002/rsa.20266.  Google Scholar

[18]

N. Gill and H. Helfgott, Growth of small generating sets in $\SL_n(\Z/p\Z)$,, preprint. \arXiv{1002.1605}, ().   Google Scholar

[19]

W. T. Gowers, Quasirandom groups, Combin. Probab. Comput., 17 (2008), 363-387. doi: doi:10.1017/S0963548307008826.  Google Scholar

[20]

B. J. Green, Approximate groups and their applications: Work of Bourgain, Gamburd, Helfgott and Sarnak,, preprint. \arXiv{0911.3354}, ().   Google Scholar

[21]

M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. No., 53 (1981), 53-73.  Google Scholar

[22]

H. Helfgott, Growth and generation in $SL_2(Z/pZ)$, Ann. of Math. (2), 167 (2008), 601-623. doi: doi:10.4007/annals.2008.167.601.  Google Scholar

[23]

H. Helfgott, Growth in $\SL_3(\Z/p\Z)$, preprint (2008). arXiv:0807.2027 Google Scholar

[24]

J. E. Humphreys, "Linear Algebraic Groups," Springer-Verlag GTM 21, 1975.  Google Scholar

[25]

E. Hrushovski, Stable group theory and approximate subgroups, preprint (2009). arXiv:0909.2190 Google Scholar

[26]

M. Larsen and R. Pink, Finite subgroups of algebraic groups, preprint (1995). Google Scholar

[27]

C. Matthews, L. Vaserstein and B. Weisfeiler, Congruence properties of Zariski-dense subgroups, Proc. London Math. Soc, 48 (1984), 514-532. doi: doi:10.1112/plms/s3-48.3.514.  Google Scholar

[28]

M. V. Nori, On subgroups of $\GL_n(\F_p)$, Invent. Math., 88 (1987), 257-275. doi: doi:10.1007/BF01388909.  Google Scholar

[29]

L. Pyber and E. Szabó, Growth in finite simple groups of Lie type, preprint (2010). arXiv:1001.4556 Google Scholar

[30]

I. Z .Ruzsa, Generalized arithmetical progressions and sumsets, Acta. Math. Hungar., 65 (1994), 379-388. doi: doi:10.1007/BF01876039.  Google Scholar

[31]

T. C. Tao, Product set estimates in noncommutative groups, Combinatorica, 28 (2008), 547-594.  Google Scholar

[32]

T. C. Tao, Freiman's theorem for solvable groups,, preprint., ().   Google Scholar

[33]

T. C. Tao and V. H. Vu, "Additive Combinatorics," Cambridge University Press, 2006. doi: doi:10.1017/CBO9780511755149.  Google Scholar

[34]

J. Tits, Free subgroups in linear groups, Journal of Algebra, 20 (1972), 250-270. doi: doi:10.1016/0021-8693(72)90058-0.  Google Scholar

[35]

P. Varjú, Expansion in $\SL_d(\mathcalO_K/I)$, $I$ squarefree,, preprint., ().   Google Scholar

[36]

V. H. Vu, M. Wood and P. Wood, Mapping incidences,, preprint., ().   Google Scholar

show all references

References:
[1]

L. Babai and A. Seress, On the diameter of permutation groups, European J. Combin., 13 (1992), 231–-243. doi: doi:10.1016/S0195-6698(05)80029-0.  Google Scholar

[2]

E. Breuillard and B. J. Green, Approximate groups II : The solvable linear case,, preprint, ().   Google Scholar

[3]

E. Breuillard, B. J. Green and T. C. Tao, Approximate subgroups of linear groups,, preprint. \arXiv{1005.1881}, ().   Google Scholar

[4]

E. Breuillard, B. J. Green and T. C. Tao, Expansion in simple groups of Lie type,, preprint., ().   Google Scholar

[5]

J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of $SL_2(F_p)$, Ann. of Math. (2), 167 (2008), 625-642. doi: doi:10.4007/annals.2008.167.625.  Google Scholar

[6]

J. Bourgain and A. Gamburd,, Expansion and random walks in $\SL_d(\Z/p^n\Z)$ I, J. Eur. Math. Soc. (JEMS), 10 (2008), 987-1011.  Google Scholar

[7]

J. Bourgain and A. Gamburd,, Expansion and random walks in $\SL_d(\Z/p^n\Z)$ II, With an appendix by Bourgain, J. Eur. Math. Soc. (JEMS), 11 (2009), 1057-1103.  Google Scholar

[8]

J. Bourgain, A. Gamburd and P. Sarnak, Affine linear sieve, expanders, and sum-product, Invent. Math, Springeronline (2009).  Google Scholar

[9]

J. Bourgain, A. Glibichuk and S. Konyagin, Estimates for the number of sums and products and for exponential sums in fields of prime order, J. London Math. Soc. (2), 73 (2006), 380-398. doi: doi:10.1112/S0024610706022721.  Google Scholar

[10]

M.-C. Chang, Convolution of discrete measures on linear groups, J. Funct. Anal., 253 (2007), 303-323. doi: doi:10.1016/j.jfa.2007.03.008.  Google Scholar

[11]

M.-C. Chang, Product theorems in $\SL_2$ and $\SL_3$, J. Math. Jussieu, 7 (2008), 1-–25.  Google Scholar

[12]

M.-C. Chang, On product sets in $\SL_2$ and $\SL_3$,, preprint., ().   Google Scholar

[13]

M.-C. Chang, Some consequences of the polynomial Freiman-Ruzsa conjecture, C. R. Math. Acad. Sci. Paris, 347 (2009), 583-588.  Google Scholar

[14]

L. E. Dickson, "Linear groups with an exposition of Galois Field Theory," Chapter XII, Cosimo classics, New York, 2007. Google Scholar

[15]

O. Dinai, Expansion properties of finite simple groups,, preprint. \arXiv{1001.5069}, ().   Google Scholar

[16]

A. Eskin, S. Mozes and H. Oh, On uniform exponential growth for linear groups, Invent. Math., 160 (2005), 1-30. doi: doi:10.1007/s00222-004-0378-z.  Google Scholar

[17]

A. Gamburd, S. Hoory, M. Shahshahani, A. Shalev and B. Virag, On the girth of random Cayley graphs, Random Structures Algorithms, 35 (2009), 100-117. doi: doi:10.1002/rsa.20266.  Google Scholar

[18]

N. Gill and H. Helfgott, Growth of small generating sets in $\SL_n(\Z/p\Z)$,, preprint. \arXiv{1002.1605}, ().   Google Scholar

[19]

W. T. Gowers, Quasirandom groups, Combin. Probab. Comput., 17 (2008), 363-387. doi: doi:10.1017/S0963548307008826.  Google Scholar

[20]

B. J. Green, Approximate groups and their applications: Work of Bourgain, Gamburd, Helfgott and Sarnak,, preprint. \arXiv{0911.3354}, ().   Google Scholar

[21]

M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. No., 53 (1981), 53-73.  Google Scholar

[22]

H. Helfgott, Growth and generation in $SL_2(Z/pZ)$, Ann. of Math. (2), 167 (2008), 601-623. doi: doi:10.4007/annals.2008.167.601.  Google Scholar

[23]

H. Helfgott, Growth in $\SL_3(\Z/p\Z)$, preprint (2008). arXiv:0807.2027 Google Scholar

[24]

J. E. Humphreys, "Linear Algebraic Groups," Springer-Verlag GTM 21, 1975.  Google Scholar

[25]

E. Hrushovski, Stable group theory and approximate subgroups, preprint (2009). arXiv:0909.2190 Google Scholar

[26]

M. Larsen and R. Pink, Finite subgroups of algebraic groups, preprint (1995). Google Scholar

[27]

C. Matthews, L. Vaserstein and B. Weisfeiler, Congruence properties of Zariski-dense subgroups, Proc. London Math. Soc, 48 (1984), 514-532. doi: doi:10.1112/plms/s3-48.3.514.  Google Scholar

[28]

M. V. Nori, On subgroups of $\GL_n(\F_p)$, Invent. Math., 88 (1987), 257-275. doi: doi:10.1007/BF01388909.  Google Scholar

[29]

L. Pyber and E. Szabó, Growth in finite simple groups of Lie type, preprint (2010). arXiv:1001.4556 Google Scholar

[30]

I. Z .Ruzsa, Generalized arithmetical progressions and sumsets, Acta. Math. Hungar., 65 (1994), 379-388. doi: doi:10.1007/BF01876039.  Google Scholar

[31]

T. C. Tao, Product set estimates in noncommutative groups, Combinatorica, 28 (2008), 547-594.  Google Scholar

[32]

T. C. Tao, Freiman's theorem for solvable groups,, preprint., ().   Google Scholar

[33]

T. C. Tao and V. H. Vu, "Additive Combinatorics," Cambridge University Press, 2006. doi: doi:10.1017/CBO9780511755149.  Google Scholar

[34]

J. Tits, Free subgroups in linear groups, Journal of Algebra, 20 (1972), 250-270. doi: doi:10.1016/0021-8693(72)90058-0.  Google Scholar

[35]

P. Varjú, Expansion in $\SL_d(\mathcalO_K/I)$, $I$ squarefree,, preprint., ().   Google Scholar

[36]

V. H. Vu, M. Wood and P. Wood, Mapping incidences,, preprint., ().   Google Scholar

[1]

Cristóbal Camarero, Carmen Martínez, Ramón Beivide. Identifying codes of degree 4 Cayley graphs over Abelian groups. Advances in Mathematics of Communications, 2015, 9 (2) : 129-148. doi: 10.3934/amc.2015.9.129
[2]

Fabio Augusto Milner. How Do Nonreproductive Groups Affect Population Growth?. Mathematical Biosciences & Engineering, 2005, 2 (3) : 579-590. doi: 10.3934/mbe.2005.2.579
[3]

Jan Hladký, Diana Piguet, Miklós Simonovits, Maya Stein, Endre Szemerédi. The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs. Electronic Research Announcements, 2015, 22: 1-11. doi: 10.3934/era.2015.22.1
[4]

Stéphane Sabourau. Growth of quotients of groups acting by isometries on Gromov-hyperbolic spaces. Journal of Modern Dynamics, 2013, 7 (2) : 269-290. doi: 10.3934/jmd.2013.7.269
[5]

Nicolás Matte Bon. Topological full groups of minimal subshifts with subgroups of intermediate growth. Journal of Modern Dynamics, 2015, 9: 67-80. doi: 10.3934/jmd.2015.9.67
[6]

Christine A. Kelley, Deepak Sridhara. Eigenvalue bounds on the pseudocodeword weight of expander codes. Advances in Mathematics of Communications, 2007, 1 (3) : 287-306. doi: 10.3934/amc.2007.1.287
[7]

Paweł G. Walczak. Expansion growth, entropy and invariant measures of distal groups and pseudogroups of homeo- and diffeomorphisms. Discrete & Continuous Dynamical Systems, 2013, 33 (10) : 4731-4742. doi: 10.3934/dcds.2013.33.4731
[8]

Litao Guo, Bernard L. S. Lin. Vulnerability of super connected split graphs and bisplit graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1179-1185. doi: 10.3934/dcdss.2019081
[9]

Lianwen Wang. Approximate controllability and approximate null controllability of semilinear systems. Communications on Pure & Applied Analysis, 2006, 5 (4) : 953-962. doi: 10.3934/cpaa.2006.5.953
[10]

Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131
[11]

Cristina M. Ballantine. Ramanujan type graphs and bigraphs. Conference Publications, 2003, 2003 (Special) : 78-82. doi: 10.3934/proc.2003.2003.78
[12]

Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. Nodal geometry of graphs on surfaces. Discrete & Continuous Dynamical Systems, 2010, 28 (3) : 1291-1298. doi: 10.3934/dcds.2010.28.1291
[13]

Daniele D'angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda. Schreier graphs of the Basilica group. Journal of Modern Dynamics, 2010, 4 (1) : 167-205. doi: 10.3934/jmd.2010.4.167
[14]

Yassine El Gantouh, Said Hadd, Abdelaziz Rhandi. Approximate controllability of network systems. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020091
[15]

Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93
[16]

Wooyeon Kim, Seonhee Lim. Notes on the values of volume entropy of graphs. Discrete & Continuous Dynamical Systems, 2020, 40 (9) : 5117-5129. doi: 10.3934/dcds.2020221
[17]

Renato Iturriaga, Héctor Sánchez Morgado. The Lax-Oleinik semigroup on graphs. Networks & Heterogeneous Media, 2017, 12 (4) : 643-662. doi: 10.3934/nhm.2017026
[18]

Thomas Zaslavsky. Quasigroup associativity and biased expansion graphs. Electronic Research Announcements, 2006, 12: 13-18.

[19]

Deng Lu, Maria De Iorio, Ajay Jasra, Gary L. Rosner. Bayesian inference for latent chain graphs. Foundations of Data Science, 2020, 2 (1) : 35-54. doi: 10.3934/fods.2020003
[20]

Alexander Bibov, Heikki Haario, Antti Solonen. Stabilized BFGS approximate Kalman filter. Inverse Problems & Imaging, 2015, 9 (4) : 1003-1024. doi: 10.3934/ipi.2015.9.1003

2019 Impact Factor: 0.5

Tools

Metrics

  • PDF downloads (86)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences