Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-23T15:09:27.275Z Has data issue: false hasContentIssue false
  • English
  • Français

Mixing, Communication Complexity and Conjectures of Gowers and Viola

Published online by Cambridge University Press:  07 June 2016

ANER SHALEV
ANER SHALEV*
Affiliation:
Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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, B ⊆ Gt 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 a • b:=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, b ∈ Gt 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.

Keywords

Primary 20D06Secondary 03D1520P05
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 4 , July 2017 , pp. 628 - 640
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 3657–3671.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 159–173.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 3023–3070.CrossRefGoogle Scholar
[7] Gowers, W. T. (2008) Quasirandom groups. Combin. Probab. Comput. 17 363–387.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 77–121.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 418–443.CrossRefGoogle Scholar
[13] Larsen, M. J., Shalev, A. and Tiep, P. (2011) The Waring problem for finite simple groups. Ann. of Math. 174 1885–1950.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 552–601.CrossRefGoogle Scholar
[15] Liebeck, M. W. and Shalev, A. (2005) Fuchsian groups, finite simple groups and representation varieties. Invent. Math. 159 317–367.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 61–86.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 3075–3086.CrossRefGoogle Scholar
[19] Shalev, A. (2009) Word maps, conjugacy classes, and a noncommutative Waring type theorem. Ann. of Math. 170 1383–1416.CrossRefGoogle Scholar