Number of lattice points inside a triangle and its area

Question

Consider a triangle that has lattice points as vertices (Lattice points are points with integer coordinates). However it is given that no other lattice point lies inside or on the sides of the triangle. We need to prove that the area of the triangle is $\frac{1}{2}$.

I did it in a way that I didn't like which went on like (first, I saw that it is trivial for triangles in the lattice plane that has one of their side parallel to either the $x$-axis or $y$-axis; the rest of the triangles can be checked exhaustively by taking care of all possible different cases and with the help of Pythagoras theorem).

I wish to know an efficient way to solve this.

Also I was curious whether there is a relation between the area of the polygon and the number of lattice points falling inside or on the sides of a polygon.

Answer 1

Do a central reflection of your triangle in the midpoint of any one of its sides to get a new triangle that shares that side, but is otherwise disjoint from the original triangle; the two together form a parallelogram. One easily sees that the hypotheses about the triangle imply that parallelogram still has no interior lattice points, but its four vertices are lattice points.

To show intuitively that the parallelogram must have area $1$, pave the whole plane by translates of the parallelogram laid side-to-side in the obvious way. Now each lattice point is the bottom left corner (for some appropriate meaning of "bottom-left") of a unique parallelogram. Choosing a large convex region, so that the number of parallelograms crossing its boundary is small with respect to the number completely contained in it, the latter number is approximately equal to the number of lattice points in the region, which is approximately equal to the area of the region. Taking the limit as the size of the region goes to infinity, one sees that the area of individual parallelograms must be$~1$.

A somewhat more formal way to complete that argument is to roll up the plane to a torus: take the projection $\def\R{\Bbb R}\def\Z{\Bbb Z}\R^2\to\R^2/(n\Z\times m\Z)$ for some positive integers $n,m$. The codomain is a compact surface of area $nm$, which contains $nm$ points that are the image of a lattice points (element of $\Z\times\Z$). Choosing preimages for those points, and taking the corresponding set of parallelograms, one obtains a region that under the projection covers our compact surface exactly once; since the projection is locally area-preserving, that region has area $nm$, and each parallelogram has area$~1$. In fact one could just choose $n=m=1$.

Answer 2

Perform a shear transformations (http://en.wikipedia.org/wiki/Shear_mapping) on your lattice so that one edge of the triangle is parallel to the $x$ axis and another edge is parallel to the $y$ axis, and remember that shear transformations preserve area.

Answer 3

Let $L:=\{x=j_1 a_1 + j_2 a_2 : j_1, j_2 \in\mathbb{Z}\}$ be the lattice, where $a_1,a_2\in\mathbb{R}^2$ are linearly independent. The vectors $a_1,a_2$ are called the primitive vectors. (In your case we have $L=\mathbb{Z}^2$ and one choice for the primitive vectors would be $a_1 = (1,0)$ and $a_2=(0,1)$.)

A primitive cell $P$ is a volume of $\mathbb{R}^2$ that, if translated by all vectors $R\in L$, fills up completely all space without overlap, i.e. $\mathbb{R}^2 = \stackrel{\cdot}{\bigcup}_{R\in L} \{x+R : x\in P\}$. Every primitive cell contains exactly one lattice point. One example for a primitive cell is the parallelpiped spanned by $a_1,a_2$. Thus let $P:=\{x \in \mathbb{R}^2 : x=\alpha a_1 + \beta a_2 , \alpha,\beta \in [0,1)\}$ that parallelpiped. Its volume, and more importantly the volume of every primitive cell of $L$, is given by $|\det(a_1|a_2)|$. (For $L=\mathbb{Z}^2$ the volume is equal to $1$.)

A triangle $T$ that has lattice points as vertices is (without loss of generality) given by $T:= \{x=\alpha A a_1 + \beta B a_2 : \alpha + \beta \in[0,1) \}$ for some $A,B \in \mathbb{Z}$. Let $\tilde{P}:=\{x=\alpha A a_1 + \beta B a_2 : \alpha, \beta \in[0,1) \}$ be the parallelpiped spanend by $Aa_1$ and $Ba_2$. We have that $2\cdot |T| = |\tilde{P}|$.

So we just have to realize that $\tilde{P}$ is a primitive cell itself and thus $|\tilde{P}| = |P|$ (which is equal to $1$ in your case).

To proof that rigorously we can either show that

• $P \subset \stackrel{\cdot}{\bigcup}_{R\in L}\{x+R : x\in \tilde{P}\}$

or

• $Aa_1$, $Ba_2$ are primitive vectors itself, i.e., $L=\{j_1 (Aa_1) + j_2 (Ba_2) : j_1, j_2 \in\mathbb{Z}\}$.

Answer 4

You can calculate the amount of latice points inside a triangle using Pick´s theorem.

You find:

Let $$ A (x_1, y_1), B (x_2, y_2), C (x_3, y_3) $$ be three points with integer coordinates not all on one line.

Then the amount of latice points L inside the triangle is given by:

$$ L = \frac{1}{2}A_{ \Delta} + 1 - \frac{1}{2} \sum_{1 \le i \lt j \le 3, i \neq j} {gcd( x_i - x_j, y_i - y_j )} $$

where $$ A_{\Delta} $$ is the area of the triangle ABC.

Like I said, one can proof this easily with Pick´s theorem.