The first one I *wrote*, that is. It happened like this: my undergraduate thesis advisor was Persi Diaconis, and in 1993, my senior year, Diaconis was really peeved about the proof via Selberg that every element of SL_2(F_p) could be expressed as a word of length at most C log p in the standard unipotent generators. (See Emmanuel’s comment on Terry’s blog for useful references.) Diaconis felt it was a combinatorial problem and it should be solvable by purely combinatorial means, and that a hard-working undergraduate who was good at Putnam problems, like me, ought to be able to do it.

That turned out not to be the case.

So Persi gave me another thesis problem; he asked if I could get good bounds on the diameter of the *unipotent* subgroup U of SL_n(F_p), with its standard generating set id + e_{i,i+1}. When n = 2, this is easy; the unipotent group is just Z/pZ and its diameter is about p. The question is: what happens asymptotically when n and p are allowed to grow?

It’s not possible any longer for the diameter of U to be on order log |U|, as is the case for SL_2(F_p); the abelianization of U looks like (Z/pZ)^{n-1}, which already has diameter on order of np. Unless n is much larger than p, this swamps log |U|.

But it turns out this is in some sense the *only* obstacle: one can prove that diam(U) is bounded above and below by constant multiples of

np + log |U|.

(My memory is that I conceived the key step of the argument during a boring Advocate meeting.)

Much later, when I was a new postdoc at Princeton, I talked about this problem with Julianna Tymoczko, then a graduate student working with Bob McPherson. Julianna very quickly saw how to make the argument much more conceptual and general, and in particular how to extend it to all the classical groups. So we decided to write it up as a joint paper. That was probably 2002. Then we got around to writing the paper and submitting it. That was 2005. It was accepted in 2007. And now here it is! That’s the abstract; if you’re at a computer that doesn’t subscribe to Forum Math, here’s the arXiv version. 17 years from first version of the theorem to publication!

**Update:** Harald Helfgott politely comment-hints at something I should have put in the original post, which is that nowadays, thanks to him, there *is* a combinatorial proof that the diameter of SL_2(F_p) is on order log p! The subject of uniform bounds for word growth and spectral gaps in finite groups of Lie type is currently moving very quickly. I won’t try to summarize the state of the art, but you can expect in the medium-term to hear something about an interesting application of Harald’s work to arithmetic geometry.

“Diaconis felt it was a combinatorial problem and it should be solvable by purely combinatorial means, and that a hard-working undergraduate who was good at Putnam problems, like me, ought to be able to do it.”

The first half of that statement did turn out to be the case!

Congratulations!

The first problem my thesis advisor, Elias Stein, gave me (back in 1994, I think), I was unable to solve until around 2002, and finally appeared in 2003. It’s not a particularly significant result (it concerns an endpoint estimate for Fourier integral operators) but I was personally very satisfied to finally have knocked it off.

Of course, one has to pity Littlewood, who was apparently given the Riemann hypothesis as his first thesis problem…