Thursday, May 12, 2011

Gauss's Circle Problem Part 1

So anyway one way or another jumping from one wikipedia aritcle to the next I ended up on this:

And I didn't really think anything of any furthering of the idea or anything until the day after, when I was working on a project where I had to cut a wire screen into a circle which was a pretty big coincidence... I thought about this. Take a circle on a grid like in the Gauss Circle Problem, I chose a diameter of 23. I chose a prime because I thought it would make it easier to see the form of the formula but it didn't really matter in the end.
   Gauss's circle problem asks how many vertices of this grid are within the circle in this case of diameter 23. By vertices I mean how many corners of all the squares counting each only once. 
   So if you read through that wikipedia article you might be able to tell that what I'm about to try here is different than the way they've approached this problem, I'm actually trying to use a millenia old technique by Archimedes on a hundreds of years old problem. First notice the square that completely encloses this circle...
It contains the diameter of the circle squared or 23^2 = 529 vertices or grid points because the diameter of the circle is the same as the length of the side of the square and that squared counts all of them. 

So then I moved onto an octagon, A number above a line means that that many vertices are contained within the octagon on that line beneath it. See the bottom black line for instance covers 9 vertices and goes a bit beyond them.
So after quite a while of looking at how to generalize to get that number 417 up there and for all different starting diameters of circle which lead to a particular size of octagon I found this approach...
Note the green boxes, sometimes the diameter called s in the formulas below evenly divides 3, sometimes it divides 3 with a remainder of 1, sometimes it divides 3 with a remainder of 2. The one above 23 has a remainder of 2, so 3 evenly sized green squares from the top of the octagon to the bottom miss 2 rows of vertices and the 3 going across the middle of the octagon misses two columns of vertices, but besides that together they contain every vertex within the blue square, which we know is 529 = 23^2 vertices.
Ok so if the diameter of the circle divides 3 with a remainder of 2 like above, these two formulas:
Here s is the diameter so (23-2)/3 = 7 = x
Then plug 7 into the bottom to get 417 which is the number that I hand counted were inside the octagon earlier, that was tedious.  This formula tells you for this case without having to count.
To explain the top formula we know s=23 gets divided up into 3 parts but the way they have to be spaced makes two lines of vertices between so 23-2 = 21/3 = 7 = both the width and height of the lines of vertices within each green square. so there are 9*7^2 vertices within the green rectangles because there are nine green boxes and each has 49 because they're 7 on a side. But there are two columns and two rows between those so 4*23 more but where those cross you end up counting them each twice so -4.  All that equals 529 so so far so good, that is the total amount of vertices in the blue square. But the black octagon has the corners cut off....
   So second half in the second formula... x*(x+1)/2 = 7+6+5+4+3+2+1 = starting with the first diagonal of vertices outside one diagonal edge of the black octagon there are 7 vertices, then the next one further away from the octagon has 6, and so on... one corner alltogether has 28 vertices if you add it all up. So there are 4 of them cut off and they're all equal so 529 - 4*28 =  417. Which is the number inside of the black octagon.

I'm going to do at least a part 2 where I move on from octagons to a hexakaidecagon which is 16 sides, then I'll attempt to find a pattern as you keep doubling the number of sides, and hopefully the limit of that as you go to infinite sides will be a formula for exactly how many grid points are inside the circle. There are other exact formulas for this quantity but they use the floor function which is not as nice as an exact algebra equation for a variety of reasons. not too many of which I can name, I just overall floor is not as good somehow.

So the square had 529, the octagon had 417, it ends up the sixteen sided has 393 and I think the 32 sided has 377 which is the correct number within the circle. So usually you don't have to go all that far to get to the right number.

You might remember I said those equations above only work for a remainder of 2 when dividing a diameter by 3. I don't know yet whether when moving to the 16 sided if that breaks up into more cases after the 3 original ones or not, hopefully not.

1 comment:

  1. Ben you do an excellent job of explaining your mathematical ideas, even so a novice like myself can understand.