Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-26T09:56:13.707Z Has data issue: false hasContentIssue false

Mixing, Communication Complexity and Conjectures of Gowers and Viola

Published online by Cambridge University Press:  07 June 2016

ANER SHALEV*
Affiliation:
Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel (e-mail: [email protected])

Abstract

We study the distribution of products of conjugacy classes in finite simple groups, obtaining effective two-step mixing results, which give rise to an approximation to a conjecture of Thompson.

Our results, combined with work of Gowers and Viola, also lead to the solution of recent conjectures they posed on interleaved products and related complexity lower bounds, extending their work on the groups SL(2, q) to all (non-abelian) finite simple groups.

In particular it follows that, if G is a finite simple group, and A, BGt for t ⩾ 2 are subsets of fixed positive densities, then, as a = (a1, . . ., at) ∈ A and b = (b1, . . ., bt) ∈ B are chosen uniformly, the interleaved product ab:=a1b1 . . . atbt is almost uniform on G (with quantitative estimates) with respect to the ℓ-norm.

It also follows that the communication complexity of an old decision problem related to interleaved products of a, bGt is at least Ω(t log |G|) when G is a finite simple group of Lie type of bounded rank, and at least Ω(t log log |G|) when G is any finite simple group. Both these bounds are best possible.

Type
Paper
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Arad, Z. and Herzog, M. eds (1985) Products of Conjugacy Classes in Groups, Vol. 1112 of Lecture Notes in Mathematics, Springer.CrossRefGoogle Scholar
[2] Babai, L., Nikolov, N. and Pyber, L. (2008) Product growth and mixing in finite groups. In Proc. 19th Annual ACM–SIAM Symposium on Discrete Algorithms: SODA, pp. 248–257.Google Scholar
[3] Curtis, C. and Reiner, I. (1981) Methods of Representation Theory, Wiley Interscience.Google Scholar
[4] Ellers, E. W. and Gordeev, N. (1998) On the conjectures of J. Thompson and O. Ore. Trans. Amer. Math. Soc. 350 36573671.CrossRefGoogle Scholar
[5] Even, S., Selman, A. L. and Yacobi, Y. (1984) The complexity of promise problems with applications to public-key cryptography. Inform. Control 61 159173.CrossRefGoogle Scholar
[6] Fulman, J. and Guralnick, R. (2012) Bounds on the number and sizes of conjugacy classes in finite Chevalley groups with applications to derangements. Trans. Amer. Math. Soc. 364 30233070.CrossRefGoogle Scholar
[7] Gowers, W. T. (2008) Quasirandom groups. Combin. Probab. Comput. 17 363387.CrossRefGoogle Scholar
[8] Gowers, W. T. and Viola, E. (2015) The communication complexity of interleaved group products. In Proc. 47th Annual ACM Symposium on the Theory of Computing: STOC, pp. 351–360.CrossRefGoogle Scholar
[9] Gowers, W. T. and Viola, E. (2015) The communication complexity of interleaved group products. Electronic Colloquium on Computational Complexity, report 44, revision 1.CrossRefGoogle Scholar
[10] Guralnick, R. M. and Lübeck, F. (2001) On p-singular elements in Chevalley groups in characteristic p. In Groups and Computation III: Proc. International Conference at the Ohio State University, 1999, Vol. 8 of Ohio State Univ. Math. Res. Inst. Publ., de Gruyter, pp. 169–182.CrossRefGoogle Scholar
[11] Guralnick, R. M. and Malle, G. (2012) Products of conjugacy classes and fixed point spaces. J. Amer. Math. Soc. 25 77121.CrossRefGoogle Scholar
[12] Landazuri, V. and Seitz, G. M. (1974) On the minimal degrees of projective representations of the finite Chevalley groups. J. Algebra 32 418443.CrossRefGoogle Scholar
[13] Larsen, M. J., Shalev, A. and Tiep, P. (2011) The Waring problem for finite simple groups. Ann. of Math. 174 18851950.CrossRefGoogle Scholar
[14] Liebeck, M. W. and Shalev, A. (2004) Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks. J. Algebra 276 552601.CrossRefGoogle Scholar
[15] Liebeck, M. W. and Shalev, A. (2005) Fuchsian groups, finite simple groups and representation varieties. Invent. Math. 159 317367.CrossRefGoogle Scholar
[16] Liebeck, M. W. and Shalev, A. (2005) Character degrees and random walks in finite groups of Lie type. Proc. London Math. Soc. 90 6186.CrossRefGoogle Scholar
[17] Miles, E. and Viola, E. (2013) Shielding circuits with groups. In Proc. 45th Annual ACM Symposium on the Theory of Computing: STOC, pp. 251–260.CrossRefGoogle Scholar
[18] Shalev, A. (2008) Mixing and generation in simple groups. J. Algebra 319 30753086.CrossRefGoogle Scholar
[19] Shalev, A. (2009) Word maps, conjugacy classes, and a noncommutative Waring type theorem. Ann. of Math. 170 13831416.CrossRefGoogle Scholar