Tag Archives: diaconis

In which I publish my first paper

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.

Tagged , , , , ,

Diaconis: From Magic to Mathematics and Back

Persi Diaconis of Stanford speaks tomorrow, 4pm, in Van Vleck room B102, on “From Magic to Mathematics and Back”:

“Sometimes the way that magic tricks work is even more amazing than the tricks themselves. Professor Diaconis will illustrate with tricks that fool magicians (demonstrations provided). The tricks depend on hidden mathematics: combinatorics and group theory (the talk is aimed at a general audience). The math behind the tricks has applications to secret codes, decoding DNA, robot vision and much else. Changing the tricks leads to math problems beyond our current understanding.”

He’ll also be giving colloquium on Friday.  For people outside math:  you might have heard of Diaconis as the guy who proved that it takes seven shuffles to randomize a deck of cards. And that coincidences aren’t surprising.

Tagged , ,

A little more about random configurations

In my previous post about the configuration space of hard discs in a box, I neglected to say anything about the main point of Persi’s article!  It’s the following — even though  you don’t know anything about the topology of the space of configurations, you can still do an excellent job of drawing a configuration at random from the natural distribution using Monte Carlo techniques.  And if you’re a physicist trying to model the behavior of a gas or a fluid, you might be more interested in what a random configuration looks like than whether the space of configurations is connected — it might not be so relevant that you can get from something that looks like tight packing 1 to something that looks like tight packing 2, if the probability of doing so is vanishingly small.  Or to put it another way — if the space looks like a bunch of big blobs connected by extremely narrow paths, then from the point of view of physics it might as well be disconnected.

Still, as a topologist, you might ask:  if I can do a good random sample of points from a mystery manifold M, can I compute topological invariants of M with high confidence?  Can you guess whether M is connected?  More generally, can you guess the homology groups of M?

You might think of this as a massive geometric generalization of the age-old problem of “cluster analysis.”  Let’s say you have a bunch of people, and for each person you measure N variables — let’s say, height, weight, and shoe size.  So you have a bunch of points in R^N — in this case R^3.

Maybe you hope that these points are well-modeled as a sample from some multivariate normal distribution.  But under some circumstances, this is a really bad hope!  For instance, if your sample isn’t segregated by gender, you’re going to see two big clusters — one cluster of women where the mean height is around 5’6″, one cluster of men where the mean height is around 5’9″.  You’re not really sampling from a normal distribution — you might be sampling from a superimposition of two different normal distributions with different centers.  Or, alternately, you could think of yourself as sampling points from a manifold in R^3 consisting of just two points — “the ideal woman and the ideal man” — where your measurements are subject to some error that’s distributed normally.

My impression is that statisticians are pretty good at distinguishing between a normal distribution and a superimposition of some small finite set of normal distributions.  But I think it’s much harder to look at a giant cloud of points in R^100 and say “aha — this is actually a random sample from a normal distribution centered on the union of a surface of genus 2 sitting over here, and these ten disjoint circles sitting over there.”

If you were wondering about this while reading the Diaconis article in the Bulletin, you’d be in luck, because flipping forward a few pages you’d get to Gunnar Carlsson’s long survey article on precisely this genre of problem!  More on “topological statistics” once I’ve read Carlsson’s article, but let me point out now that if you’re a young mathematician interested in these matters you might consider going to the CBMS summer school this August, centered on a lecture series by Ghrist.

Tagged , , , ,
%d bloggers like this: