Interior Lattice Point

Taking the two points not on the origin as the base of the triangle, we see that regardless of $N$ , the length of the base is $\sqrt{2}$ and the altitude is $907/\sqrt{2}$ , so the area of the triangle is always $\tfrac{907}{2}$ . By Pick's theorem, the number of interior points is $\tfrac{909}{2} - \tfrac{b}{2}$ , where $b$ is the number of lattice points on the boundary. We thus wish to minimize $b$ : it must be at least $3$ for the corner vertices. It would suffice to find a value of $N$ for which $b=3$ , that is there are no lattice points on the interior of any edge; in this case we'll have $453$ interior points. One suitable value is $N = 453$ : then the corners of the triangle are $(0,0), (453, 454), (454,453)$ . It's easy to see that $453$ and $454$ are coprime, hence avoiding lattice points inside the two long edges, while the short edge is too short to ever admit internal lattice points.

The following claim is proved first [Pick's Theorem].

L= A - B/2 + 1

where L= number of lattice points within a triangle which has its endpoints on lattice points A= area of the triangle B= number of lattice points on the boundary lines of the triangle

Proof:-

First consider a rectangle with the end points being integer lattice points. [refer to http://postimage.org/image/9gsnwazax/ ]

Let the length and breadth of the rectangle be l and b respectively.

Then the area of the rectangle will be lb, the number of boundary points will be 2(l+b), and the number of interior points will be (l-1)(b-1).

Now, (l-1)(b-1)= lb - (l+b) + 1.

So this theorem works for a rectangle with endpoints being lattice points.

Now consider a right angled triangle with its endpoints being lattice points. [refer to http://postimage.org/image/ynb0vkz3j/ ]

Let the lengths of the sides adjacent to the right angle be p and q [p>=q]. Let the number of lattice points on the hypotenuse be k [the endpoints are not included].

Then, number of boundary points= m+n+k+1.

Now, this right angled triangle can be expressed as half of a rectangle with length p and breadth q. Then the hypotenuse will be the diagonal of this rectangle.

So, number of integer lattice points within the triangle= 1/2 * (lattice points within the rectangle - lattice points on the hypotenuse) = 1/2 * {(p-1)(q-1) - k}

Also, area of the right angled triangle= pq/2

Now, 1/2 {(p-1)(q-1) - k}= 1/2 {pq - (p+q+k+1) + 2}= pq/2 - (p+q+k+1)/2 + 1.

So this theorem works for a right angle triangle with lattice points.

Now this theorem has to be proved for a general triangle with lattice endpoints.
[refer to http://postimage.org/image/kfeq1exk3/ ]

For a triangle ABC, construct a rectangle PQRC such that the line PQ touches the point A and RQ touches B. It is easy to see that PQRC also has in integer lattice endpoints.

So, we get 3 right angled triangles:- BQA, CRB, and APC.

Let $A_1$ be the area of BQA. Let $A_2$ be the area of CRB. Let $A_3$ be the area of APC.

Let $B_1$ be the number of lattice boundary points on BQA. Let )B_2) be the number of lattice boundary points on CRB. Let $B_3$ be the number of lattice boundary points on APC.

Let $I_1$ be the number of lattice points in the interior of BQA. Let $I_2$ be the number of lattice points in the interior of CRB. Let $I_3$ be the number of lattice interior points of APC.

Let $A_4$ be the area of PQRC. Let $B_4$ be the number of lattice boundary points on ABCD. Let $I_4$ be the number of lattice points in the interior of PQRC.

Let $A_5$ be the area, $B_5$ be the number of lattice boundary points, and $I_5$ be the number of lattice points in the interior of triangle ABC.

From previously proved claims we have the following.

$A_1 = I_1 + B_1 /2 - 1$ $A_2 = I_2 + B_2 /2 - 1$ $A_3 = I_3 + B_3 /2 - 1$ $A_4 = I_4 + B_4 /2 - 1$

Now, $A_5= A_4 - A_1 - A_2 - A_3 - A_4= I_4 - I_1 - I_2 - I_3 - (B_1 + B_2 + B_3 + B_4)/2 + 2$

Now, from the figure it is clear that $B_4= B_1 + B_2 + B_3 - B_5$ and $I_5= I_1 + I_2 + I_3 + I_5 + (B_1 + B_2 + B_3 - B_4)/2 - 3$ [note that the corners of the triangles have been double calculated, so we have to subtract 3].

Now, solving these by a series of substitutions and simplifications, we derive that $I_5= A_5 - B_5/2 + 1$ .

So, we can now calculate the number of integer lattice points within a triangle. The problem has been solved in the next post using this claim.