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:
Why didn’t I fill them all out? Lattice find out!
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 
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.
I picked the northeast quadrant because that’s where I am!
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: 
Applying Pick’s theorem to right triangles aka the triangle numbers
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.
Octahedron from wikipedia page, link above.
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.
Because it’s messy I only drew the dots on the axes
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).
Imagine the thin black line is the z axis, and we’re moving down it through the centers of these sets.
This is exactly 
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: ![2[\sum_{k=0}^n (2k^2+2k+1)] - (2n^2+2n+1)](https://s0.wp.com/latex.php?latex=2%5B%5Csum_%7Bk%3D0%7D%5En+%282k%5E2%2B2k%2B1%29%5D+-+%282n%5E2%2B2n%2B1%29&bg=ffffff&fg=7a7a7a&s=0&c=20201002)
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!
Baking and Math 
Your post inspired me to read about the Gauss circle problem. I found out that actually Gauss proved that the error term is indeed
, so the conjecture is whether it is 
. Moreover, it was proved by Hardy the Heartbreakers that the error term is 
, so it’s gotta be somewhere in between those two. So intrigue, such mystery.
The error term in the Gauss circle problem is conjectured to be
. It is not too hard to show that the error is 
using Poisson summation with radial test functions which approximate the indicator function for the circle. One can do better using the method of exponent pairs and even better by using the work of Bombieri and Iwaniec, but I don’t know the current record for the bound.
P.S. Yen, I love your blog!!!!!!!!