## Is there a noncommutative Siegel’s Lemma?

Let f be the smallest function satisfying the following:

Suppose given two matrices A and B in SL_3(Z), with all entries at most N.  If there is a word w(A,B,A^{-1},B^{-1}) which vanishes in SL_3(Z), then there is a word w'(A,B,A^{-1},B^{-1}) of length at most f(N) which vanishes in SL_3(Z).

What are the asymptotics of f(N)?

The reason for the title is that, if SL_3(Z) is replaced by Z^n, this is Siegel’s lemma:  if two (or, for that matter, k) vectors in [-N..N]^n are linearly dependent, then there is a linear dependency whose height is polynomial in N.  (Here k and n are constants and N is growing.)

I don’t have any particular need to know this — the question came up in conversation at the very stimulating MSRI Thin Groups workshop just concluded.  Sarnak’s notes are an excellent guide to the topics discussed there.

## 7 thoughts on “Is there a noncommutative Siegel’s Lemma?”

1. Terence Tao says:

I don’t know if SL_3(Z) is complicated enough for this, but I would imagine that if one replaced SL_3(Z) by a sufficiently complex group then the answer would be “Busy beaver function asymptotics”, because one could presumably encode the problem of whether a Turing machine of length N terminated by one as to whether a certain pair of elements of length N in a certain explicit “Turing-complete” group had a nontrivial relation.

2. There are only finitely many pairs of elements with entries at most N, so the assertion is automatic. I’m not familiar with Siegel’s Theorem but I guess the bound is uniform in the dimension of the ambient space? Here we should probably ask for a bound that is uniform as “3” varies.

3. JSE says:

I agree that the assertion that f(N) exists is automatic, for exactly the reason you say! So I suppose in that sense it is trivial that there IS a noncommutative Siegel’s lemma — the question is whether the bound is in fact uselessly huge (as Terry suggests above) or handsomely small….

4. Terence Tao says:

Asking around on mathoverflow led me to this paper http://www.ams.org/mathscinet-getitem?mr=1128014 of Klarner, Birget, and Satterfeld which suggests (for the semigroup case, at least) that determining freeness in SL_3(Z) can in fact be undecidable, which would rule out any computable upper bound. (But their results require more than two generators.)

5. Terence Tao says:

Actually, on closer reading it seems they get undecidability from two generators already. In any case, there are a number of other interesting answers and references at http://mathoverflow.net/questions/88368/can-a-group-be-a-universal-turing-machine

6. Henry Wilton says:

I believe it’s open whether or not it’s decidable if a finite set of matrices generates a free group (ie whether or not f is computable).

Bridson and I proved some undecidability results about presentations of matrix groups here. In particular, there does not exist an algorithm that computes presentations for finitely presentable subgroups of $SL_n(\mathbb{Z})$ which is uniform in n. It’s also fairly easy to prove (using similar machinery) the complementary fact that there does not exist an algorithm (again, uniform in n) that determines if a given finite subset of $SL_n(\mathbb{Z})$ generates a finitely presentable subgroup.

Unfortunately, our techniques do not work for any fixed value of n.

A similar question was asked on Mathoverflow.

7. Henry Wilton says:

Whoops! The above was intended as a reply to Jordan’s post, not to Lior’s comment.