Posts Tagged ‘acp’

Progress! (Apollonian Sphere Packings)

August 12, 2010

Since giving the recent talk, I had a bit of a breakthrough.  Two of the problems I mentioned are no longer open!  I now know (and can prove) the following:

Theorem: If a,b,c are nonzero integers, at most one of which is negative, then the numberN_3(a,b,c) of inequivalent occurrences of three mutually tangent spheres of curvature a,b,c is the same as the number of algebraic integers in {\mathbb{Q}}(\sqrt{-3}) with norm (ab+ac+bc), up to multiplication by a unit.  The bijection between algebraic integers with that norm and triples of spheres is natural and explicit.

There is a nice way to compute this number.  Define an arithmetic function \eta on the positive integers as follows.  If p=2 or p\equiv -1\pmod 6, then \eta(p^k)=1 if k is even and \eta(p^k)=0 if k is odd; if p\equiv 1 \pmod 6, then \eta(p^k)=k+1; \eta(3^k)=1 for all k.  Extend \eta to all positive integers by multiplicativity.  Then N_3(a,b,c)=\eta(ab+ac+bc).

Theorem: If a,b are nonzero integers, at most one of which is negative, then the numberN_3(a,b) of inequivalent occurrences of tangent spheres of curvature a,b is given by the formula N_3(a,b) = \left\lceil \frac{1}{12}\left(M_\star+3M_1+3M_3\right)\right\rceil + X.  Here M_\star is the number of solutions (u,v) to the congruence u^2+uv+v^2\equiv ab \pmod{a+b}, M_k is the number of solutions u to the congruence ku^2\equiv ab \pmod{a+b}, and X is 1 if 12|(a+b) and (a+b)|ab, otherwise 0.

(This strange formula comes from an application of Burnside’s Counting Lemma; as always in these problems, the trickiest part is keeping track of which solutions correspond to the same packing.)

The next natural problem in the progression, counting the total number of inequivalent occurrences of a given curvature in integer sphere packings, remains resistant to my current approach.

In the next week, I should have the corresponding result for counting occurrences of a given n-tuple of n-dimensional hyperspheres.  If I’m lucky, my 2- and 3-dimensional techniques will generalize to let me count occurrences of (n-1)-tuples in n dimensions, but I can’t be sure of that part yet.   Beyond that, I currently have no idea how to proceed.


Cap’s MathFest2010 Talk

August 6, 2010

I’m currently in Pittsburgh for the 2010 MathFest conference.  (My probability students must be heart-broken; I had to cancel a class for the endeavour.)  I’ve learned a lot already, and the conference is only half-over.  But I didn’t just come to listen; I also came to give a talk.

You can get the talk slides here.  (Just right-click and select “Save”.)

If you want more in-depth information on Apollonian Circle Packings, the best place to start is probably a sequence of five papers.  (If you want to really know everything, I recommend reading them in the listed order; if your interests are more strictly number-theoretic, then perhaps start with the fourth and jump back to the earlier papers on an as-needed-basis.)  The first four are by Graham, Lagarias, Mallows, Wilks, and Yan.  The fifth is by Erikkson and Lagarias.

A reference for Elena Fuchs’ result is here.

Sarnak’s letter to Lagarias (in which is proved the “twin prime conjecture”) is here.

As Morpheus says, time is always against us.  These slides were written for a 15-minute talk, and I could easily have given two 60-minute talks on this topic, and a third on the generalizations I’ve been playing with most recently.

This talk was part of a special session on open and accessible problems in number theory and algebra, and I tailored it accordingly.  You’ll notice that I’ve written a lot more about questions I haven’t answered than questions I have.  My own discoveries were present only “obliquely”.  Upon my return to Michigan, I hope to complement these slides with some more posts including material from my papers-in-progress and my freshest thoughts on this subject.  So there’s more on the way.

Most importantly (and those of you who saw my talk will know this already), if any part of this interests or intrigues you, contact me.  Use comments here, email me, find your way to the Cafe Aroma in Fenton, whatever.  Graduates and undergraduates, I’m talking to you.  There is a lot of accessible stuff here at a lot of levels and with a lot of flavors.  Want to collaborate?  I am friendly, and I will always work with students.  Just want some more information?  Please ask; if I don’t know the answer, I will find someone who does.

Counting Problems in Apollonian Circle Packings

July 8, 2010

I’ve spent most of the last year and a half contemplating pretty pictures like the one that follows. These pictures, called Apollonian circle packings, have captivated me since I heard Sarnak speak on them at the 2009 Joint Meetings.

Apollonian circle packing with root quadruple (-1,2,2,3)Apollonian circle packing with root quadruple (-1,2,2,3)

Pictures such as these are constructed by inscribing a triple of three circles inside a larger circle, inscribing a circle in each lune created, and iterating the process. The numbers labelling the circles are the curvatures (1/radius). (The exterior circle has radius 1, but because it is exterior we say that it’s curvature is -1 by convention.) To a number theorist, the amazing fact is that if the four circles we begin with have integral curvature (in the figure, the starting circles have curvature -1, 2, 2, 3), or indeed if any four mutually tangent circles in such a packing have integral curvature, all the rest of the circles automatically have integral curvature. Such pictures are called integer Apollonian circle packings (IACPs).

One question I like to think about, the one that got me into the subject, is to think about which numbers appear in IACPs. That is, think about all PACPs at once. How many times does a given curvature appear? What pairs of numbers can appear? How often? All of my counting is up to symmetry; the picture above, for example, accounts for only one occurrence of 6, not four, and only one occurrence of the pair (2,3).

It turns out that answers to these counting problems can be unexpectedly elegant.

(Note: as the “Out[56]” which I clumsily left in the picture suggests, I generated this diagram and all my other Apollonian pictures using Mathematica 7; please contact me if you’re interested in methods for constructing pictures of this sort.)

0. Some basics

Four numbers (a,b,c,d) are the curvatures of four mutually tangent circles iff they satisfy the Descartes equation a^2+b^2+c^2+d^2=2(ab+ac+ad+bc+bd+cd).

Given a triple of mutually tangent circles with curvatures (a,b,c), the possible curvatures of a fourth circle are the roots of the above equation, viewed as a quadratic in d; in general there are two possibilities, a+b+c\pm\sqrt{ab+ac+bc}. In particular, their sum is 2(a+b+c). If we know one curvature d, then the “other” possibility is d'=2(a+b+c)-d.

A nice upshot of this is that, if we know the curvatures of four mutually tangent circles in a packing, we can compute all the rest using only addition and subtraction!


%d bloggers like this: