Non-commutative super approximation and the product replacement algorithm

Non-commutative super approximation and the product replacement algorithm Abstract: Let A be the free abelian group on n generators and C a finite simple abelian group. The action of Aut(A) on E = Epi(A, C) ( = the set of epimorphisms from A to C) satisfies super-approximation (i.e., the induced graph is an expander). We will discuss the situation when A is replaced the non-abelian free group F and C a non-abelian finite simple group S. This question is of interest in presentation theory of finite groups as well as for analyzing the product replacement algorithm which is an important and useful algorithm in computational group theory. If time permits we will also discuss the situation when M(g) (= the mapping class group) replaces Aut(F).

Date

Speakers

Alex Lubotzky

Affiliation

The Hebrew University of Jerusalem