How can I obtain the formula for the number of points with
integer coordinates inside a circle? Do you know some web page
about this topic?
Thank you.
Maria Jose.
Maria,
say the center of the circle is (h,k) and let r be its
radius.
Then the equation of the circle is
(x-h)2 + (y-k)2 = r2
If we could find all the integral solution to,
(x-h)2 + (y-k)2 < r2
then you would get your answer.
Any further suggestions guys?
love arun
Must there necessarily be a neat
formula? I think there was once a problem used in training for
the William Lowell Putnam Contest (a very hard olympiad-type
competition for American universtiy students) recently: show that
for all n, there exists a circle in the plane containing
precisely n points. That suggests that the general field is
likely to be quite hard and there is unlikely to be a neat
general formula.
P.S. See if you can solve the Putnam problem I mentioned! There's
a very neat trick.
In the Putnam Contest question, are we talking about an arbitrary set of > =n points in the plane, or integral lattice points? The latter seems quite easy, but I haven't yet worked out how to do the former (if indeed it's true).
Michael:
It was the latter actually - the set of all lattice points. But
the former can be done fairly easily too. Just pick a point P not
on the perpendicular bisector of AB for any of the pairs A and B
of points in the set. (If we assume that there are countably many
points in the set it is obvious that this may be done.) Then no
two points are equidistant from P, so we can simply draw circles
centred at P. As we increase the radius then the number of points
inside the circle increases from 0, but it must increase in steps
of 1. Result follows.
David
Yes, that's pretty neat. (Actually the
proof won't work for some infinite sets of points, but I was
really only asking about finite sets. The result isn't true for
some infinite sets which are dense in places.)
Alternatively for the lattice question, note that if a circle
passes through three points with rational x,y co-ordinates, then
its centre has rational x,y co-ordinates (because the centre is
the intersection of the perpendicular bisectors). Now fix one
point on the circumference of the circle at a point with rational
co-ordinates (say (1/2,1/2)). Now shift the centre of the circle
along the line y = sqrt(2)x. Note that if the circumference ever
intersects two lattice points then its centre necessarily has
rational co-ordinates which is impossible since the centre lies
on y = sqrt(2)x. Therefore it gets one point at a time, as
above.
This can be extended to the general problem by using considering
the minimal field which contains the gradients of each the lines
drawn from the origin to each of the points in the arrangement,
but this is more complicated than your method.