Posts Tagged ‘number theory’

Idle remarks on the Furstenburg topology

July 10, 2010

There are numerous proofs of the infinitude of primes in the literature, but for my money the “cutest” is the “topological proof” due to Hillel Furstenburg.

Make $\mathbb{Z}$ into a topological space by taking as a neighborhood basis the set of arithmetic progressions $A(a,d):=\{a+nd:n\in\mathbb{Z}\}$ (where d>0, of course).  It’s not hard to check that this really is a topology, and that it has the following interesting properties.

  1. The union of finitely many arithmetic progressions is both closed and open.  (Look modulo the gcd of the various differences in the progressions; this set and its complement are each unions of residue classes.)
  2. Any open set which is not empty is infinite.  (Obvious, since the neighborhoods are all infinite.)
  3. The set S=\bigcup_{p\mbox{ prime}} (p\mathbb{Z}) is open; by 1, it is also closed if there are only finitely many primes.
  4. But \mathbb{Z}\setminus S=\{\pm 1\} is finite, so \mathbb{Z}\setminus S is not open, and S is not closed.

That’s the whole proof.  Once you introduce the topology, the theorem practically proves itself!

(If someone has written about this topology and given it an official name, then I don’t know about it; “Furstenburg topology” seems as good a name as any for now.)

(more…)

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!

(more…)


%d bloggers like this: