Lattice Points in a Rectangle

Date: 06/04/99 at 10:56:54
From: John
Subject: Regarding areas

Prove that in any rectangle centered at (0,0) with an area greater 
than 4, you can find lattice points other than (0,0).

I was given a theorem relating to pigeonhole principle that states 
"given areas A1, A2, ..., An and an area A, if A1+A2+...+An > A, then 
there is overlap."

My conjecture is that any rectangle centered at (0,0) with an area of 
4 contains lattice points and so any area greater than 4 must also 
contain lattice points. However, I cannot prove the first part and I 
am not even sure that this is sufficient proof.

I've also given the vertices points (x1,y1), ..., (x4,y4) and 
expressed the area as a product of distances, realizing that for every 
vertex x1^2 + y1^2 = ... = x4^2 +x4^2 since the distance from each 
vertex to the center must be constant. My last thought in this route 
was that each X and Y coordinate must be at least some number 'n' in 
order to contain a lattice point but I cannot find n.

I believe this proof must be much simpler than I am making it but I've 
thought about it for about 3 days now and tried these two routes. I 
would greatly appreciate help. Thank you.

Date: 06/07/99 at 19:38:03
From: Doctor Wilkinson
Subject: Re: Regarding areas

Hi, John!

This is a special case of what is known as Minkowski's Theorem, and it 
is kind of tricky, so you shouldn't feel too bad if you've had trouble 
with it. It's one of those things that seem easy once you see them, 
but it's hard to find the right way of looking at it.

If P = (x,y) and m is any real number, we denote the point (mx,my) by 
mP. In particular we denote (-x,-y) by -P. If P = (a,b) and Q = (c,d), 
we denote (a+c,b+d) by P+Q and (a-c,b-d) by P-Q. That is, we do 
addition and subtraction and multiplication by scalars component-wise.

Let's call the rectangle S.

The two facts we need about our rectangle S are

  (a)  If P is in S, so is -P; and
  (b)  If P and Q are in S, so is (P+Q)/2.

Everything else is just a distraction. In particular, your second 
route is not the way to go.

So let S be a set of points with properties (a) and (b), and with area 
greater than 4.

Look at the set S/2 that you get by shrinking S by a factor of 2; that 
is, it is the set of points P/2, where P is in S. Its area is 1/4 the 
area of S, so it's greater than 1.

Now think of S/2 as being marked out with ink on the coordinate plane, 
viewed as an infinite piece of transparent quad-ruled plastic. Cut the 
paper into squares along the grid lines, and pile all the squares on 
top of each other. If the ink was always just one layer thick, then 
the total area of S/2 would be less than or equal to the area of the 
square, which is 1. But the total area is bigger than 1. So the ink 
must be at least two layers thick at some point. Another way of saying 
this is that there must be points P and Q of S such that P-Q is a 
lattice point. I'll leave it to you to use properties (a) and (b) to 
show that S contains a lattice point other than (0,0). (Of course you 
should also translate all this stuff about ink and plastic into a real 
proof). 

- Doctor Wilkinson, The Math Forum
  http://mathforum.org/dr.math/