Counting points is fun! Gauss did it, why can’t we?

17 May

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 and are integers in the plane.  We get a lattice of points:

integerlattice

Why didn’t I fill them all out?  Lattice find out!

The Gauss circle problem asks: if I make a circle with radius centered at the origin, how many lattice points are inside that circle?  We can count the first few:

firstfourcircles

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 G(n)=\pi n^2+ O(n).  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.

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, is the number of lattice points inside the polygon, and 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 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 nG_P(n)=i_n+b_n=A_n+\frac{b_n}{2}+1 by Pick’s theorem.  Since A stands for area and I’m scaling linearly by a factor of n, A_n=n^2a.  Similarly, b stands for boundary which is a linear factor, so b_n=nb.  Plugging these both in to the original equation gives G_P(n)=n^2A+\frac{nb}{2}+1, which is great!  You only need to find and for the first polygon to find the number of lattice points in any scaling of it.

triangles

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

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.

octohagon

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).

level sets

Imagine the thin black line is the z axis, and we’re moving down it through the centers of these sets.

This is exactly G_D(k) where is the diamond!  So from the formula above, we can calculate G_D(k)=2k^2+2k+1, 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: 2[\sum_{k=0}^n (2k^2+2k+1)] - (2n^2+2n+1).  There are a bunch of proofs that \sum_{k=0}^n k^2= \frac{n(n+1)(2n+1)}{6} and that the sum of the first numbers is \frac{n(n+1)}{2}.  So if I go through the arithmetic (you can do it I believe in you!) I get \frac{4}{3}n^3+2n^2+\frac{8}{3}n+1.

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!

Advertisements

3 Responses to “Counting points is fun! Gauss did it, why can’t we?”

  1. j2kun May 17, 2016 at 10:22 pm #

    Your post inspired me to read about the Gauss circle problem. I found out that actually Gauss proved that the error term is indeed O(n), so the conjecture is whether it is o(n). Moreover, it was proved by Hardy the Heartbreakers that the error term is \omega(n^{1/2}), so it’s gotta be somewhere in between those two. So intrigue, such mystery.

    • Anonymous number theorist May 22, 2016 at 7:14 pm #

      The error term in the Gauss circle problem is conjectured to be \ll_{\varepsilon} n^{1/2+\varepsilon}. It is not too hard to show that the error is \ll n^{2/3} 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!!!!!!!!

Trackbacks/Pingbacks

  1. Counting Things | nebusresearch - May 25, 2016

    […] attention to some interesting posts from Baking And Math. Yenergy started, last week, with a post about the Gauss Circle Problem. Carl Friedrich Gauss you may know as the mathematical genius who proved the Fundamental Theorem of […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: