I’m writing to you from the Institute for Advanced Study (!!!! Starstruck!!!! Einstein! 1930! More importantly, Noether!) I’m in the middle of a two week program that’s been going on since 1994 for women and mathematics, and I wanted to share with you an easy-to-state, hard to solve combinatorics problem.
First, some two dimensional background and set up. The Gauss Circle Problem has been around for a looong time (200+ years) and is not actually solved. Let’s live in the xy plane, and mark points where x and y are integers in the plane. We get a lattice of points:
The Gauss circle problem asks: if I make a circle with radius n centered at the origin, how many lattice points are inside that circle? We can count the first few:
There’s four points on the pink circle and one point inside, so G(1)=5. The orange circle has four points on it, and it also adds the four points between the pink and orange circles. So G(2)=4+4+5=13. And the beige circle has eight points on it, and also adds more inside points, so G(3)=29. Gauss thought that . We haven’t talked about this big O notation (it’s literally called big O notation; we’re very creative nomenclators), and I’m not going to do so here: take it as an “error term up to linearity”. That means that while G(273) is around 74529π, it’s off by a factor that’s not “too far” from 273, a.k.a. probably closer to 273 than to 74529.
How do you count G(3)? One way you can do it is count G(2), then count all the added points, like we did above. You can also find a smaller region to look at, then multiply to fill in the circle and subtract double counted points. In the example above, let’s just look at one quadrant.
It’s pretty easy to see how many points are in there: I count 11 integer lattice points. Now we multiply by 4 to get 44 lattice points. But we double counted! Imagine multiplication by two as picking up that pie slice, and rotating it, and putting it back down in the tin in the northwest corner. I’ve overlapped the first slice by one edge, so if I want to count the number of lattice points I’ll have to subtract the four points on that edge from my total. Similarly, multiplying by four double counts all of the edge points on the green lines, and counts the origin four times. So I need to subtract 3 for the quadruple counted origin, and 12 for the double counted edges: that leaves 44-15=29, which is good because it’s what I had above!
For the next problem, we’re going to use a black box called Pick’s Theorem. It’s not an extremely dark black box since there’s a proof of it on that wikipedia page, but I’m not going to explain the proof here, just say the statement: If you have a polygon with integer coordinates in the plane, then A=i+b/2-1, where A is the area of the polygon, i is the number of lattice points inside the polygon, and b is the number of lattice points on the boundary of the polygon. Notice this works for polygons, not circles (circles is the Gauss circle problem, still unsolved).
If I let A, i, and b represent what they do for my initial polygon, I can write a formula for the number of lattice points after I scale the first polygon by n: by Pick’s theorem. Since A stands for area and I’m scaling linearly by a factor of n, . Similarly, b stands for boundary which is a linear factor, so . Plugging these both in to the original equation gives , which is great! You only need to find A and b for the first polygon to find the number of lattice points in any scaling of it.
So here’s the next problem: Find G(n) for an octahedron in three dimensions (we’ve run into the octahedron in the poincare homology sphere posts). For a recap, the octahedron is what happens when you draw vertices at (0,0,n), (0,n,0), (n, 0,0), (-n,0,0), (0,-n,0), (0,0,-n) and draw the edges between them and then fill it in.
So now it’s a little harder and weirder to count, but we can still do it, using a mixture of the techniques above. I’ll show two different ways to count this.
Technique 1: use level sets! My friend and co-author Andrew Sanchez came up with this clever idea, which uses the theorem we have above. Imagine that we’re at the top of the octohedron, at point (0,0,n), and we start taking an elevator down the z-axis. At the very top we see exactly one point. At the next level, we see four points: (1,0,n-1), (0,1,n-1), and the same points with -1s instead of 1s. At the next level we see a diamond: fixing z at n-2, we have a diamond between points (0,2),(2,0),(0,-2),and (-2,0).
This is exactly where D is the diamond! So from the formula above, we can calculate , by find the initial area (2) and number of boundary points (4) of the initial diamond.
Now we’ll need to add all of these points from all of the level sets. The elevator starts with one point, which corresponds to z=n and k=0, and in the fattest part of the octahedron we have z=0 and k=n. Then it gets skinny again. So we can count all the points from z=0 to z=n, multiply by two, and subtract what we double counted (the fat base). This shows up as follows: . There are a bunch of proofs that and that the sum of the first n numbers is . So if I go through the arithmetic (you can do it I believe in you!) I get .
Do you believe it? Let’s do a second technique too! Actually, hate to leave you on a cliffhanger, but a second technique will take a lot more words and this post is already long enough. So you’ll have to wait til next week to see the technique I used with my friend Priyam Patel, whose current research I have previously blogged. Preview: we use partitions!