wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Lattice points in a circle
        
(Message started by: TimMann on Nov 2^nd, 2002, 6:40pm)

Title: Lattice points in a circle
Post by TimMann on Nov 2^nd, 2002, 6:40pm

A lattice point in the coordinate plane is one whose x and y coordinates are both integers. For what values of n is it possible to draw a circle (any center) such that exactly n lattice points are in the circle's interior?

This was a problem in a college math newsletter that I solved when I was a senior in high school. I got it fairly quickly, but after publishing my solution, the editors asked a followup question that no one ever solved. It was one of three problems still on the unsolved list when the newsletter ceased publication four years later. I'll give the followup question after someone gets this one.

Title: Re: New puzzle: lattice points in a circle
Post by James Fingas on Nov 4^th, 2002, 12:59pm

I think that it's possible for any n.
Reasoning:
For a given circle A, it is possible to specify another circle B so that B includes everything that A includes, plus an arbitrary sector of A's circumference.

Given this, it is easy to grow the size of the circle to eat lattice points one-at-a-time.

Title: Re: New puzzle: lattice points in a circle
Post by TimMann on Nov 4^th, 2002, 1:57pm

I don't understand the reasoning. What do you mean by "an arbitrary sector of A's circumference"? How do you show that you can always eat one more lattice point without eating another at the same time?

Title: Re: New puzzle: lattice points in a circle
Post by Icarus on Nov 4^th, 2002, 5:36pm

My solution: Choose a circle centered at (a, b), where a is irrational and b is rational, but not a multiple of 0.5 . If two lattice points (m, n), (p, q) are on the circumference of the circle at the same time, then the equation

(m - a)² + (n - b)² = (p - a)² + (q - b)²

simplifies to a linear equation in a with rational coefficients if p != m. Since a is irrational, it cannot satisfy such an equation. If p=m, then we are left with n=q or n=2b-q. By the choice of b, the RHS of the latter equation is not an integer, so it cannot be true. Thus only one lattice point can lie on a circle centered at (a, b).
Because of this, if we start with the radius of the circle=0 and then steadly increase it, lattice points will cross over to the interior one at a time, and we can find a radius with exactly n interior lattice points for any integer n > 0.

I'm guessing that this is essentially the solution you found.

Title: Re: New puzzle: lattice points in a circle
Post by TimMann on Nov 4^th, 2002, 7:59pm

That looks good, Icarus.

My solution from 1976 was similar, but not quite identical, and not as good: I chose (a, b) to be the point (2^1/2, 3^1/2), and I then claimed that this makes (a, b) a different distance from every lattice point in the plane. I'm sure that's true, but I didn't give a full proof.

The followup question was: "Find all points (a, b) in the interior of the unit square (0,0), (0, 1), (1, 1), (1, 0) such that (a, b) is a different distance from every lattice point in the plane."

Since my point isn't in your set, clearly we haven't quite solved this one yet, but we're close. Here's my 2002 guess at the answer: All points (a,b) where 0 < a < 1, 0 < b < 1, a != 1/2, b != 1/2, and a/b is irrational.

Title: Re: New puzzle: lattice points in a circle
Post by Icarus on Nov 4^th, 2002, 9:25pm

Perhaps a better way of formulating the question is to ask which point are equidistant from 2 or more lattice points. Then the equation in my last post applies for some (m, n) & (p, q), and reduces to

m² + n² - p² - q² = 2((m-p)a + (n-q)b)

Though I have not examined it closely, this suggests that there are rational numbers a, b which do not satisfy the equation for any m, n, p, q, and of course irrational pairs that do.

A simplification: let r=m-p, s=m+p, u=n-q, v=n+q. Then

rs+uv=2(ra + ub)

r, s, u, v can still be chosen arbitrarily, except that r and s must have the same parity, and u and v must have the same parity.

Title: Re: New puzzle: lattice points in a circle
Post by James Fingas on Nov 5^th, 2002, 7:29am

An arbitrary sector of a circle's circumference is just any arc that is part of the circle. For instance:

x = 5 cos(t)
y = 5 sin(t)
0.1 < t < 0.6

is an arbitrary sector of the circumference of the following circle:

x² + y² = 25

What I said was not exact, and if preciseness is going to help, here we go:

Given a circle A in the XY plane, and
given a set of lattice points S inside the circle A, and
given a beginning and ending angles, K and L, which define a sector of the circumference of the circle,

it is possible to construct a circle B so that:
All points in S are in B, and
All lattice points outside of A are outside of B, except for the lattice points that lie on the circumference of A, in the sector between K and L.

Eating lattice points consists of the following steps (I'll assume that a point on the circumference of the circle is not "inside" the circle, for simplicity):

1) Start the circle A at any non-lattice point
2) Grow the circle A until it touches any lattice point. If it touches just a single lattice point, eat it by growing A, and continue with step 2. If it simultaneously touches more than a single lattice point, proceed to step 3.
3) We will eat just one of the lattice points that A touches. Select any sector of the circumference of A that contains only one lattice point. Now choose a new circle B according to the rules above, with all previously eaten lattice points as the set S. The new circle will contain the set S and one more lattice point. Now use B instead of A and continue with step 2.

It is easy to see that each iteration of step 2 or step 3 adds a single point to the circle.

I see now that my solution is not helping with the followup question, however.

Title: Re: New puzzle: lattice points in a circle
Post by TimMann on Nov 5^th, 2002, 9:23am

James, that sounds like a correct approach. In fact, I thought it was plausible even before you clarified it, but I wasn't sure exactly what you meant by it. However, you stated the key part without any proof: "it is possible to construct a circle B so that...". How does one construct such a circle? Although I see a way to do it, I don't think that part is obvious enough to omit.

Title: Re: New puzzle: lattice points in a circle
Post by TimMann on Nov 5^th, 2002, 11:25am

Icarus, that equation always has integral solutions in m, n, p, q if a/b is rational. To see this, let a/b = j/k where j, k are integers. Draw a line through (0, 0) and (a, b). This line has slope b/a. Now draw a perpendicular to this line through (0, 0). The perpendicular has slope -a/b = -j/k; therefore points (-k, j) and (k, -j) lie on it, and the original line is the perpendicular bisector of the segment (-k, j)(k, -j).

So you can choose m = -k, n = j, p = k, q = -j to solve the equation.

Title: Re: New puzzle: lattice points in a circle
Post by Icarus on Nov 5^th, 2002, 6:04pm

Yes, I see. But the equation does show that not all pairs with a/b irrational will work either. If I choose any r, s, u, v according to the indicated conditions and with rs != zero, and choose an irrational number b, and set

a=(rs + uv - 2ub)/2r

then a/b = (rs + uv)/2rb - u/r, which is clearly irrational as well. But I can find distinct lattice points (m,n) (p,q) equidistant from (a, b). So your set contains all the points we want, but also some that we don't.

To this end, I'll keep working on the equation. First, we can take r, u as relatively prime, as any common divisor can be divided out. With this additional condition, the LHS of rs + uv = 2(ra + ub) can take on any integer value, provided we drop the parity conditions on s and v. But that we cannot do. Instead, this is what I have so far:

If one of r or u is even, then a,b satisfy the equation iff ra + ub + 1/2 is an integer

If both r and u are odd, then I believe, but have not proven, that a, b satisfy the equation iff ra + ub is an integer.

If the latter is true (to prove it I still need to show that rs + uv can be any even integer), then our set can be expressed as
{(a, b): 0<a<1, 0<b<1, a != 1/2, b != 1/2, and there do not exist relatively prime integers r, u such that (ru is even, and ra + ub +1/2 is an integer) or (ru is odd and ra + ub is an integer)}

That's still a pretty ghastly condition, but *I think* it's a step in the right direction.

Title: Re: Lattice points in a circle
Post by James Fingas on Nov 6^th, 2002, 8:12am

There are definitely solutions where a/b is irrational. This is clear because all points where a+b=1 are equidistant from (0,0) and (1,1). Contained on that line are an infinite number of different points, with all positive values for a/b.

I've been experimenting on this myself, and you can construct the set of numbers that are non-equidistant by starting with the entire square [0,0]-[1,1], then removing a series of lines. First remove x=0, x=1/2, x=1, and y=0, y=1/2, y=1. Now proceed to remove all lines with a slope m/n, with y-intercepts k/n, where m and n are relatively prime. If mn is even, then you can remove all lines with slope m/n and y-intercepts k/2n.

Note that there are an infinite number of such lines, and that they cut the square into an infinite number of very small pieces. By inspection, if a/b is rational, then a line must pass through (a,b).

http://www.ocf.berkeley.edu/~wwu/images/riddles/lattice.gif

Here is an image I made up showing the first few lines that cut up the square. The picture contains all relevant lines with slopes 0, 1, 2, 3, 4, 3/2, 4/2, and the corresponding negative and reciprocal slopes.

Title: Re: Lattice points in a circle
Post by TimMann on Nov 6^th, 2002, 11:48pm

James, are you and Icarus in agreement on the answer? Icarus's "ru is odd and ra + ub is an integer" is the same as your "lines with a slope m/n, with y-intercepts k/n, where m and n are relatively prime", given appropriate renaming of variables. But Icarus's "ru is even, and ra + ub +1/2 is an integer" doesn't look quite the same as your "If mn is even, then you can remove all lines with slope m/n and y-intercepts k/2n." Icarus wants ra + ub to be an integer plus 1/2, while you're satisfied with it being any integral multiple of 1/2. Are the even multiples of 1/2 covered somewhere else in Icarus's solution? If so, I'm not seeing how.

It would be cool if one of you could finish off the thread by posting the proof that this is the right solution. I suppose you have specific point pairs in mind for each line that are equidistant from it, which would make the first half of the proof. I imagine the equidistant points come from something like my construction, which covers the special case where k=0, so I should be able to find them for the k !=0 case, but I'm feeling too tired to make the effort right now. For the other half of the proof, though, how do you show that there are no points to remove other than those on these lines?

Title: Re: Lattice points in a circle
Post by James Fingas on Nov 7^th, 2002, 10:14am

Tim,

Thanks for going over our solutions. I couldn't make heads or tails of Icarus' equation, and I'm sure my explanation isn't easy to understand either.

Icarus's statement "ru is odd, and ra + ub is an integer" is not exactly the same thing as my statement "lines with slope m/n and y-intercepts k/n, m & n relatively prime", because I allow mn to be even here.

When mn is even, you can also have y-intercepts of the form k/n + 1/2n, but this doesn't rule out the y-intercepts of the form k/n. This is evident from examining the line y = 2x (m = 2, n = 1). This is the perpendicular bisector of the line between C=(2,-1) and D=(-2,1), and thus every point on this line is equidistant from C and D. However, it has a y-intercept of zero, clearly of the form k/n. Notice that y=2x-1/2 is the perpendicular bisector of the line between E=(-1,0) and F=(1,-1), an example of the k/2n intercepts.

To see how this applies to Icarus' equation, we use r=4, u=-2, s=0, v=0. It is clear that r,u,s, and v are all the same parity. However, when we get to the step where we make r and u relatively prime, we divide each by 2. Then, the parity of u changes, but the parity of v does not. By making r and u relatively prime, we destroy the constraint on parity of r,s and u,v.

Because s and v are therefore allowed to be even even if r and u aren't, then we can form even sums rs + uv even when r + u is odd.

Unfortunately, Icarus' statement and my statement are probably as close as we can come to a closed-form solution for this one, unless there is something we can do with factorization or primes or such.

Tim,

Just because you ask, here is my thinking:

1) Consider two points, C and D. Join them with the line CD, and consider the perpendicular bisector of CD, I'll call it ^CD, out of sheer laziness.

2) For any point E that's on ^CD, the length EC is equal to the length ED (I think we all realized this a while ago).

3) The solution is simply the square [0,0]-[1,1] with the perpendicular bisectors for all possible pairs of lattice points subtracted. QED!

4) Well, that's not too helpful. I started taking a look at what ^CD looked like for C and D near the origin. I found that when you consider perpendicular bisectors with a given slope m/n, then the possible y-intercepts are a function of m and n. Note that perpendicular bisectors must have a rational slope.

5) For mn odd, the line was a perpendicular bisector only when it passed through lattice points. I found that this led to y-intercepts 0, 1/n, 2/n, 3/n, etc.

6) For mn even, the line was a perpendicular bisector when it passed through lattice points, or when it passed directly between lattice points in just the right way. I found that this led to y-intercepts 0, 1/2n, 1/n, 3/2n, etc.

That's about it. I also include the special case of n=0, although I'm sure that Icarus' solution handles this more naturally.

Title: Re: Lattice points in a circle
Post by TimMann on Nov 7^th, 2002, 10:34am

Quote:

Icarus's statement "ru is odd, and ra + ub is an integer" is not exactly the same thing as my statement "lines with slope m/n and y-intercepts k/n, m & n relatively prime", because I allow mn to be even here.

Oh, right -- how did I miss that? I think I even saw it at one point when comparing the solutions and then forgot. I really was too tired.

Also, I meant to say earlier that your way of describing the solution is actually rather nice. I wouldn't expect anything neater than that.

Thanks for giving the reasoning, too. I feel like I should have thought of that, because I was partway there when I noticed that points (a, b) with a/b rational can be eliminated, but I didn't give it enough thought.

It's interesting how much easier this problem is when you think about it geometrically rather than algebraically.

Title: Re: Lattice points in a circle
Post by Icarus on Nov 7^th, 2002, 4:57pm

on 11/07/02 at 10:34:42, TimMann wrote:

It's interesting how much easier this problem is when you think about it geometrically rather than algebraically.

Isn't it though! James' method is much cleaner than mine, produces an easier description, and a pretty graph! About the only thing I can say about mine is that it produces some interesting number theory results. (Interesting to me that is!)
However one of them is so interesting I haven't figured it out yet. ;)