4
$\begingroup$

We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers.

Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and $n$ are two given positive integers. Then $S$ is clearly a right-angled triangle.

How to calculate the number $I$ of lattice points in the interior of $S$?

And, how to calculate the number $B$ of lattice points on the boundary of $S$?

Also, how to calculate the quantities $I$ and $B$ for the parallelogram $$T \colon= \{ (x,y) \ | 0 \leq x \leq m, \ \frac{nx}{m} \leq y \leq \frac{nx}{m} + h \}?$$ Here $m$, $n$, and $h$ are positive integers.

In other words, how to calculate the number of points in the interior and the number of points on the boundary of a right-triangle with lattice points as vertices? And how to find these numbers for a parallelogram with lattice points as vertices?

Finally, how to calculate $I$ and $B$ for an arbitrary triangle with lattice points as vertices?

$\endgroup$
2
  • $\begingroup$ What have you tried? $I$ seems rather easy to get. Do you know what Pick's theorem is? $\endgroup$
    – Calvin Lin
    Jun 27, 2014 at 1:52
  • $\begingroup$ More generally, you might be interested in Ehrhart theory. There is a "reciprocity theorem" that allows you to calculate the number of interior lattice points in a polytope if you know a formula for the number of points in the closure as the polytope is scaled (or vice-verse). $\endgroup$ Jul 21, 2014 at 15:08

1 Answer 1

4
$\begingroup$

The way I would do it is first ask the question: given two points on a lattice, how can we find out how many points of the lattice are on the line between them? By inspecting the slope of the line, we can determine this. Let's use the following example: One point is (2,2), the other is (6,10). We determine the slope by rise over run: $$\frac{10-2}{6-2} = 2$$ One way to easily proceed if the numbers are "nice" is to just imagine a right triangle whose hypotenuse has the appropriate slope (in this case, a right triangle with base 1 and height 2 corresponding to the slope) touching the line, with a vertex at one of the endpoints (say (2,2)). Then we ask how many times can we move this triangle until it reaches the other endpoint? The answer is equal to the 4 in this case, by inspection of the distance needed to travel on the x-axis, so the total number of lattice points is five (including the original (2,2) point).

What if we didn't get an integer slope? No problem, if $m$ is your slope just find the smallest integer $n$ such that $sm$ is an integer. Now divide the change in the $x$-axis by $n$ and add 1, and that's how many lattice points are on the line.

Now that we have a general method for figuring this out for a line between two lattice points, we can repeat this method for each side of the triangle, being careful not to double-count the vertices of the triangle, and this gives us how many points are on the border of the triangle. To get the interior points, you could play with a similar approach, but I would recommend using Pick's Theorem, which tells you that the area $A$ of a polygon is equal to the number of interior points $i$ plus half the border points $b$ minus one, that is $$A = i + \frac b 2 -1.$$

This makes calculating the interior points easy - just calculate the area of the triangle (I like the determinant formula for this) and then solve for $i$. Note that this generalizes to any polygon, either directly by turning the polygon into a bunch of triangles, or even easier by first calculating the number of lattice points on the border using the method outlined above and then applying pick's theorem in conjunction with the formula for the area of a polygon given the vertices which was recently highlighted on the Math.StackExchange Community Blog:

$$A = \sum_{k=0}^{n} \frac{(x_{k+1} + x_k)(y_{k+1}-y_{k})}{2}$$

$\endgroup$
2
  • $\begingroup$ process91, I'm sorry, but I still haven't been able to fully appreciate your argument. I wonder if your approach is rigorous enough. $\endgroup$ Jul 1, 2014 at 14:18
  • $\begingroup$ @SaaqibMahmuud Which part do you have questions about? Do you understand how to find out how many lattice points are on a line between two specified ones? $\endgroup$
    – mboratko
    Jul 4, 2014 at 19:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .