This page links to all my research papers (my non-research publications can be found here). The icons on the left let you read the abstract or download the paper in PDF format. The abstract page also links to other formats.
I tend to put papers on the web only when they are essentially complete. If you want to see the current version of a draft manuscript you don't see here or some work in progress, just let me know. Another thing I'm not currently posting here are lecture slides and course notes. They aren't designed to stand on their own, so they are of interest primarily to people who were there. If you were there and want a copy (or weren't there and want to see what you missed), send me e-mail and I'll send you a link.
How densely can we pack congruent, non-overlapping balls into n-dimensional space? This is not only a natural geometric problem, but also a fundamental tool for error correction on noisy channels. I'm interested in this problem in many different settings. The first two papers below deal with upper bounds for density. They prove the best bounds known in dimensions 4 through 36. (For a news report on this work, see the article "The 24-dimensional greengrocer" by Ian Stewart on pages 895-896 of the August 21, 2003 issue of Nature.) The third paper proves that the Leech lattice is the unique densest lattice in R^24, and gives a new proof for E_8 in R^8; the fourth is a research announcement and exposition. (There is also an expository article by Pfender and Ziegler on this and other work by Oleg Musin, as well as a Science News article by Erica Klarreich.)
 |
 |
New upper bounds on sphere packings I
(with Noam Elkies)
Annals of Mathematics 157 (2003), 689-714, arXiv:math.MG/0110009 |
|
|
|
New upper bounds on sphere packings II
Geometry and Topology 6 (2002), 329-353, arXiv:math.MG/0110010 |
|
|
|
Optimality and uniqueness of the Leech lattice among lattices
(with Abhinav Kumar)
to appear in Annals of Mathematics, arXiv:math.MG/0403263 |
|
|
|
The densest lattice in twenty-four dimensions
(with Abhinav Kumar)
Electronic Research Announcements of the American Mathematical Society 10 (2004), 58-67, arXiv:math.MG/0408174 |
|
|
|
Uniqueness of the (22,891,1/4) spherical code
(with Abhinav Kumar)
New York Journal of Mathematics 13 (2007), 147-157, arXiv:math.MG/0607448 |
One natural generalization of sphere packing is the energy minimization problem: given some potential function depending on the pairwise distances between points, how should the points be arranged so as to minimize the total energy? This problem arises naturally in geometry, information theory, and physics. Abhinav Kumar and I have introduced the idea of a universally optimal configuration, which minimizes all completely monotonic potential functions (for example, all inverse power laws). This gives a natural notion of the best way to distribute points on a surface such as a sphere or in space. The first paper listed below studies universal optimality theoretically, the second analyzes a surprising example in detail, and the third collects numerical evidence from massive computer searches and examines many interesting point configurations.
|
|
|
Universally optimal distribution of points on spheres
(with Abhinav Kumar)
Journal of the American Mathematical Society 20 (2007), 99-148, arXiv:math.MG/0607446 |
|
|
|
The D_4 root system is not universally optimal
(with John Conway, Noam Elkies,
and Abhinav Kumar)
to appear in Experimental Mathematics, arXiv:math.MG/0607447 |
|
|
|
Experimental study of energy-minimizing point configurations on spheres
(with Brandon Ballinger, Grigoriy Blekherman, Noah Giansiracusa,
Elizabeth Kelly, and
Achill Schürmann)
preprint (submitted), arXiv:math.MG/0611451 |
Bobby Kleinberg, Balazs Szegedy, Chris Umans, and I have been working on the question of how quickly one can solve the fundamental problems of linear algebra (matrix multiplication, solving systems of linear equations, etc.) using finite group representations. (There is a SIAM News article on this work.)
|
|
|
A group-theoretic approach to fast matrix multiplication
(with Chris Umans)
Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 11-14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438-449, arXiv:math.GR/0307321 |
|
|
|
Group-theoretic algorithms for matrix multiplication
(with Bobby Kleinberg, Balazs Szegedy, and
Chris Umans)
Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379-388, arXiv:math.GR/0511460 |
Given a region in the plane, what would a random tiling of it with dominos look like? (I.e., a tiling with 1-by-2 and 2-by-1 rectangles, chosen uniformly at random out of all the possibilities.) Jim Propp discovered that the appearance can be quite remarkable, and can exhibit bizarre phenomena like phase transitions! You can see some examples here. There turn out to be quite substantial connections with mathematical physics, because domino tiling is the same as the dimer model from statistical mechanics, which describes diatomic molecules adhering to a crystal surface. The papers below are an attempt to give a precise mathematical description of what's going on here. The first two papers analyze in detail specific cases, and the third builds a general theory.
|
|
|
Local statistics for random domino tilings of the Aztec diamond
(with Noam Elkies and Jim Propp)
Duke Mathematical Journal 85 (1996), 117-166, arXiv:math.CO/0008243 |
|
|
|
The shape of a typical boxed plane partition
(with
Michael Larsen
and Jim Propp)
New York Journal of Mathematics 4 (1998), 137-165, arXiv:math.CO/9801059 |
|
|
|
A variational principle for domino tilings
(with Rick Kenyon
and Jim Propp)
Journal of the American Mathematical Society 14 (2001), 297-346, arXiv:math.CO/0008220 |
One of the beautiful things about combinatorics is how often enumerative results have "q-analogues" (i.e., they have a one-parameter generalization depending on a parameter q, often the number of points in a finite field). The simplest case is that counting subspaces of finite fields somehow generalizes counting subsets of finite sets. Why is that? I still don't feel like I understand this phenomenon completely, but this paper gives at least a partial answer. Bobby Kleinberg pointed out an intriguing connection with finite simple groups, which is outlined in the final section. It raises questions neither of us knows how to answer.
If you're interested in this paper, you should also take a look at this one (by Anton Deitmar), which Jim Propp brought to my attention after my paper was published.
|
|
|
Projective geometry over F_1 and the Gaussian binomial coefficients
American Mathematical Monthly 111 (2004), 487-495, arXiv:math.CO/0407093 |
If one is interested in random objects, then a natural question is how to generate them efficiently on a computer, without bias. In the paper below, we analyze a new algorithm (inspired by one of David Wilson's discoveries) for generating random sink-free orientations, which are an interesting class of combinatorial objects. The techniques ought to apply more generally, but we haven't figured out how.
|
|
|
Generating a random sink-free orientation in quadratic time
(with Robin Pemantle
and Jim Propp)
Electronic Journal of Combinatorics 9 (2002), #R10, arXiv:math.PR/0103189 |
The first paper below proves some curious continued fractions for certain series. I don't think the results are connected to much else, but I find the patterns intriguing. The second paper proves a conjecture Jim Propp made about 2-adic continuity of numbers of domino tilings. There's a weird functional equation that reminds me of the functional equation for L-functions, but that's probably just a coincidence. The third paper explains a simple proof of the continued fraction expansion of e and some motivation behind it.
|
|
|
Symmetry and specializability in continued fractions
Acta Arithmetica 75.4 (1996), 297-320, arXiv:math.NT/0008221 |
|
|
|
2-adic behavior of numbers of domino tilings
Electronic Journal of Combinatorics 6 (1999), #R14, arXiv:math.CO/0008222 |
|
|
|
A short proof of the simple continued fraction expansion of e
American Mathematical Monthly 113 (2006), 57-62, arXiv:math.NT/0601660 |