טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentKarelin Ariel
SubjectBounded Generation in SLn(Fq{X})
DepartmentDepartment of Mathematics
Supervisor Dr. Chen Meiri


Abstract

 

Gaussian elimination works over fields. This fact, taught in any first year linear algebra course, states that over any field F, every square matrix of order n and determinant 1 over F is a product of O(n2) elementary matrices, i.e. matrices having 1’s on the diagonal, one nonzero off-diagonal entry and 0’s elsewhere.


When moving to matrices of determinant 1 over Euclidean domains, there is still an algorithm resembling Gaussian elimination, transforming every matrix of determinant 1 to the identity after a finite number of steps. However, this method makes a repeated use of Euclid's algorithm, and hence the number of elementary operations needed for the elimination may be unbounded. We say that elementary matrices generate SLn over Euclidean domains, yet perhaps unboundedly. When generalizing to more general commutative rings, even generation itself cannot be guaranteed.


Given a ring R (which is not a field) and a nonzero ideal J, a J-elementary matrix is an elementary matrix whose nonzero off-diagonal entry belongs to J. A sensible generalization of the field case asks whether J-elementary matrices boundedly generate the subgroup they generate. We answer this question affirmatively for R=Fq[x], where Fq is the field with q elements. This is our main result. Moreover, our bound depends only on n and q, but not on J. This fact is very important to our applications. The bound is not obtained in a constructive way, as we only prove its existence using the Compactness theorem of first order logic. The proof is also heavily based on the theory of Mennicke symbols, and the similar work by Carter, Keller, Paige and Morris for rings of algebraic integers.


We also present two applications of our result on bounded generation:


Word width in SLn(Fq[x]): Let G be a group, and w be a nontrivial word in the free group. Any word w defines a map from Gk to G by substitution. We denote by w(G) the set containing all element lying in the image of this map, together with their inverses. If w(G) boundedly generates the subgroup of G generated by it, we say that the word w has finite width in G. Word width has been the subject of extensive research. We prove several uniform results, considering word width in the group SLn(Fq[x]) as a function of w and n.


Ulam Stability of SLn(Fq[x]): A group G is said to be Ulam stable, if - roughly speaking - the following holds: Any almost multiplicative map from G to any group of unitary matrices can be approximated by a homomorphism between the two groups. The notion was first introduced by Ulam in 1940. We prove, using our result on bounded elementary generation, that SLn(Fq[x]) is Ulam stable.