Expansion properties of finite simple groups 0 1 0 2 n a J 7 2 ] R G . Thesis submitted for the degree of h t a “Doctor of Philosophy” m [ by 1 Oren Dinai v 9 6 0 5 . 1 0 0 1 : v Submitted to the Senate of the Hebrew University i X September 2009 r a 1 This work was carried out under the supervision of Prof. Alex Lubotzky 2 To my mother, who taught me that talent is useless without the ability to carry it out. Tomyfather, whoshowedmethatimaginationhasnoboundaries, andwhom I deeply miss. 3 Acknowledgements Most importantly, I am grateful for working under the supervision of the great mathematical riddle maker, Alex Lubotzky. Other than his broad mathematical perspective, I had the privilege to get to know a real Mensch1. I am thankful to Avi Wigderson and Udi Hrushovski for encouraging me in this work and for many helpful discussions. I thank Elon Lindenstrauss for the fruitful conversations and the ongoing encouragement. These conversations enriched my mathematical thinking. I wish to thank also Michael Larsen who introduced me to the striking application of the Invariant Theory of section 5.2 to my work. I am grateful to Harald Helfgott for his guidance through his remarkable work and for many illuminating discussions. I wish to thank also Peter Sarnak, Laci Babai and Alex Gamburd for many useful conversations. Last but not least, I would like to express my profound thanks to Inna Korchagina for many valuable talks and for good advise. 1a good man in Yiddish 4 Chapter 1 Abstract 1.1 Diameter and Growth of Cayley graphs A family of finite groups G is said to have poly-logarithmic diameter if n n N { } ∈ for some absolute constants C,d > 0, for every G and every subset S G n n n ⊆ generating G , we have n diam(Cay(G ,S )) Clogd( G ), n n n ≤ | | where diam(Cay(G,S)) isthe diameter ofthe Cayley graphofG with respect to S. A well know conjecture of Babai [BS2] asserts that all the non-abelian finite simple groups have poly-logarithmic diameter. In this work we inves- tigate the family of groups SL (and PSL ) over finite fields, and we prove 2 2 the conjecture for this family of groups. In fact, we investigate a stronger Growth property that would imply in particular the poly-logarithmic diameter bounds. By this, we extend the techniques that were developed by Helfgott [He] who dealt with the family 5 of groups SL (and PSL ) over finite fields of prime order. 2 2 1.2 The main results Our main result asserts that the family SL (F ) : p prime;n N 2 pn { ∈ } has poly-log diameter. Note that this result holds uniformly for all finite fields regardless of their charecteristic. This result holds also for the family PSL over finite fields. 2 By using results from Additive Combinatorics, we proved the following stronger Growth property: There exists ε > 0 such that the following holds for any finite field F . q Let G be the group SL (F ) (or PSL (F )) and let A be a generating set of 2 q 2 q G. Then we have, A A A min A 1+ε, G . | · · | ≥ | | | | (cid:8) (cid:9) Our work extends the work of Helfgott [He] who proved similar results for the family SL (F ) : p prime . 2 p { } 6 Contents 1 Abstract 5 1.1 Diameter and Growth of Cayley graphs . . . . . . . . . . . . . 5 1.2 The main results . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Introduction 9 2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Organization of the manuscript . . . . . . . . . . . . . . . . . 11 3 Preliminaries 12 3.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Uniform poly-logarithmic diameter bounds . . . . . . . . . . . 19 4 Tools from Additive combinatorics 22 4.1 The fundamental tools . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Expansion properties in fields . . . . . . . . . . . . . . . . . . 27 4.3 Expansion functions in fields . . . . . . . . . . . . . . . . . . . 30 5 Useful properties of SL (F) 39 2 5.1 Bounded generation of large subsets . . . . . . . . . . . . . . . 39 7 5.2 Symbolic generation of traces . . . . . . . . . . . . . . . . . . 55 5.3 Size of Minimal generating sets of PSL (F ) . . . . . . . . . . 57 2 q 5.4 Avoiding certain traces . . . . . . . . . . . . . . . . . . . . . . 60 6 Growth properties of SL (F ) 69 2 q 6.1 Some useful Growth properties . . . . . . . . . . . . . . . . . 69 6.2 Avoiding subvarieties . . . . . . . . . . . . . . . . . . . . . . . 73 6.3 Reduction from matrices to traces . . . . . . . . . . . . . . . 78 6.4 Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7 Main results 87 7.1 From matrices to traces and back in finite fields . . . . . . . . 87 7.2 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 8 Further conjectures and questions 106 8.1 Trace generation . . . . . . . . . . . . . . . . . . . . . . . . . 106 8.2 Avoiding proper subfields . . . . . . . . . . . . . . . . . . . . . 107 8.3 Growth of trace functions . . . . . . . . . . . . . . . . . . . . 108 8 Chapter 2 Introduction 2.1 Background Let us define the directed diameter of a finite group G with respect to a set of generators S to be the minimal number l for which any element in G can be written as a product of at most l elements in S. We denote this number by diam+(G,S). Define the (undirected) diameter of a finite group G with respect to a set of generators S to be diam(G,S) := diam+(G,S S 1). − ∪ The diameter of groups has many applications. Aside from group theory (see [BKL, La, LS]) and combinatorics(see [Di2, ER, ET1, ET2]) the di- ameter of groups shows up in computer science areas such as communication networks (see [Sto, PV]), generalizations of Rubik’s puzzles (see [DF, McK]), algorithmsandcomplexity (see[EG, Je]). Foradetailedreview see[BHKLS]. Since we are interested in the “worst case generators”, we define diam(G) := max diam(G,S) : G = S . { h i} A family of finite groups G : n N is said to have poly-log diameter n { ∈ } 9 (resp. log diameter) if for any n N we have ∈ diam(G ) Clogd( G ) n n ≤ | | for some constants C,d > 0 (resp. for d = 1). In [Di1], the author shows (with an effective algorithm) that for any fixed p,m N with p a prime and p > m 2, the family ∈ ≥ := SL (Z/pnZ) : n N m,p m G { ∈ } haspoly-logdiameter. AbertandBabai[AB]showed thatforanyfixedprime p , the family C C : p prime; p = p has logarithmic diameter. 0 { p0 ≀ p 6 0} A long standing conjecture of Babai [BS2] asserts that the family of non- abelian finite simple groups has a poly-logarithmic diameter. Very little is known about this conjecture. See [BS1] and [BS2] for some partial results concerning the alternating groups. A breakthrough result of Helfgott [He] proves the conjecture for the fam- ily SL (F ) : p prime . The main goal of this paper is to extend Helfgott 2 p { } work to the family SL (F ) : p prime;n N . We follow the basic strategy 2 pn { ∈ } of Helfgott (with some short cuts following [BG2]) and in particular we also appeal to additive combinatorics and sum-product theorems. The new diffi- culty is that unlike fields of prime order, general finite fields have subfields, and subsets which are “almost” subfields - which are “almost” stable with respect to sum and product. 2.2 Main results Our main results are the following. 10