Friday, January 17, 2014

Guass's circle problem revisited for about the tenth time

Gauss's circle problem is asking how does the number of lattice points inside or on a circle centered at the origin for a certain radius relate to pi*r^2, namely to find a bound in terms of r on how much must be added to pi*r^2.. Here for example is a radius 11 circle on a lattice...
My thought was to draw two polygons, they both have 2 sides along the radius of the circle ,the black  and green polygon starts 2 grid points below the blue at the top of the circle, moves only right or down (starting with right from 1 point below the top of the circle) and visits the nearest points inside the circle, and the blue polygon does the same but only visits points outside the circle starting from 1 unit outside the circle. ...

The black section will have a perimeter of 2*(radius-1) grid points and the blue will have 2*(radius+1) gridpoints. Remember for example the black border has to have the same perimeter as the green because they have to move the same amount moving only down and right no matter the order they do so in. From here I will consider the full polygons around and inside the circle which would be 4 times as large as each of these quarter arcs and then subtract 4 for the 4 overlapping points. . 
Pick's theorem says the enclosed area of a polygon: A is related to the interior grid points i, and the number of points around the border b in the above way. I will use two different versions of this formula one for the blue polygon around the circle (variables sub b) and one for the black polygon (variables sub l ) and average the two formulas together to get a third. 

To make some substitutions to the bottom formula, I will suppose that the average value of the area of the (A[b]+A[l])/2 is (pi*r^2) because the outer is seemingly just as much outside the area of the circle as the inner one is inside.And I'll use 8*(radius+1)-4 for the b[b] and 8*(radius-1)-4 for b[l], and get:

Now, in our example r = 11. But see how i[b] should be all the interior points for r=11 and i[l] would be the interior points for a circle 2 units smaller in radius or r=9. So we might figure the average of i[b] and i[l] should be something close to the interior of a circle with r=10.  So substituting G[r] for the average interior and r+1 for r we get:
This figure is always too high because I took G[r] to be halfway between i[b] and i[l] but it will be actually closer to i[l] because i[b] and i[l] grow quadratically with respect to the radius of the circle.  

The question was how much more than pi*r^2 is this expression so subtract pi*r^2 from the above to get:

So it's roughly 1/4 the size of the upper bound Gauss found as r gets larger and dominates the expression.  

Beyond the part of the wikipedia article discussing Gauss's upper bound I don't understand the modern work that's been done on the subject so I don't know if this is the best that's been found or not. 

No comments:

Post a Comment