2.1 Integer Length and Integer Distance

We consider the lattice $\mathbb{Z}^{n}\subset\mathbb{R}^{n}$ . A line is integer if it contains at least two integer points. In other words, this means that the integer segments contained in this line form a full-rank lattice. An integer segment is a segment with endpoints in $\mathbb{Z}^{n}$ .

Definition 2.1.1.

The integer length $\operatorname{l\ell}(AB)$ of a segment $AB$ is the number of lattice points that the closure of this segment contains, minus one.

Definition 2.1.2.

The integer distance $\operatorname{ld}(a,b)$ between two points $a,b\in\mathbb{Z}^{n}$ is the integer length of the line segment between these points.

Example 2.1.3.

Consider the segment $AB$ with endpoints $A=(0,0)$ and $B=(3,12)$ .

Figure 1:

In Figure 1, we see that the segment contains lattice points $(0,0)$ , $(1,4)$ , $(2,8)$ and $(3,12)$ . Hence, the integer length is given by

\operatorname{l\ell}(AB)=4-1=3.

Theorem 2.1.4.

The integer length of segment with endpoints $A=(x_{a},y_{a})$ and $B=(x_{b},y_{b})$ is given by

\operatorname{l\ell}(AB)=\gcd(x_{b}-x_{a},y_{b}-y_{a}).

Proof.

First, we will show that $\operatorname{l\ell}(AB)\geq\gcd(x_{b}-x_{a},y_{b}-y_{a})$ .

Let $d$ be a positive integer such that $d|(x_{b}-x_{a})$ and $d|(y_{b}-y_{a})$ . Then for integers $0\leq m\leq d$ we have that the segment $AB$ contains the point of the form:

\left(x_{a}+m\cdot\frac{x_{b}-x_{a}}{d},y_{a}+m\cdot\frac{y_{b}-y_{a}}{d}% \right).

Thus $\operatorname{l\ell}(AB)\geq(d+1)-1=d.$ To establish the best lower bound on $\operatorname{l\ell}(AB)$ , we choose $d=\gcd(x_{b}-x_{a},y_{b}-y_{a})$ . This gives the inequality

\operatorname{l\ell}(AB)\geq\gcd(x_{b}-x_{a},y_{b}-y_{a}).

Next, we will show that $\operatorname{l\ell}(AB)\leq\gcd(x_{b}-x_{a},y_{b}-y_{a}).$

From the definition, we have $\operatorname{l\ell}(AB)+1$ equally spaced lattice points in the closed segment $AB$ . The complement of lattice points over this segment thus separates $AB$ into $\operatorname{l\ell}(AB)$ connected components.

Hence $\operatorname{l\ell}(AB)|x_{b}-x_{a}$ and $\operatorname{l\ell}(AB)|y_{b}-y_{a}$ . Hence $\operatorname{l\ell}(AB)|\gcd(x_{b}-x_{a},y_{b}-y_{a})$ . Since $a|b$ only if $a\leq b$ we get that $\operatorname{l\ell}(AB)\leq\gcd(x_{b}-x_{a},y_{b}-y_{a})$ .

Combining both halves of the proof, we find that:

\gcd(x_{b}-x_{a},y_{b}-y_{a})\leq\operatorname{l\ell}(AB)\leq\gcd(x_{b}-x_{a},% y_{b}-y_{a});

hence

\operatorname{l\ell}(AB)=\gcd(x_{b}-x_{a},y_{b}-y_{a}).\qed

Remark 2.1.5.

The above proof generalises to higher-dimensional cases. Let $AB$ be a line sector with end points $A=(a_{1},a_{2},\ldots,a_{n})$ and $B=(b_{1},b_{2},\ldots,b_{n})$ . Then $\operatorname{l\ell}(AB)=\gcd(a_{1}-b_{1},a_{2}-b_{2},\ldots,a_{n}-b_{n})$ .

Example 2.1.6.

Consider the segment between points $A=(1,-3)$ and $B=(5,9)$ .

Similarly to Example 2.1.3, we see from Figure 2 that the segment passes through lattice points $(1,-3)$ , $(2,0)$ , $(3,3)$ , $(4,6)$ and $(5,9)$ . From Definition 2.1.1, this gives that

\operatorname{l\ell}(AB)=4.

On the other hand, using Theorem 2.1.4, we have that

\operatorname{l\ell}(AB)=\gcd(1-5,9+3)=\gcd(4,12)=4.

Definition 2.1.7.

Let $a_{1},\ldots,a_{n}$ be real, linearly-independent $n$ -dimensional vectors. A lattice with basis $a_{1},\ldots,a_{n}$ is the set of points $x$ such that there exist integers $u_{1},\ldots,u_{n}$ that satisfy:

x=u_{1}a_{1}+u_{2}a_{2}+\ldots u_{n}a_{n}.

Definition 2.1.8.

Let $L$ be a lattice generated by basis $l_{1},l_{2},\ldots,l_{n}$ and $B$ be a sublattice generated by basis $b_{1},b_{2},\ldots,b_{n}$ , and let $L$ be a sublattice of $B$ . Then the index of $L$ is given

\frac{|\det(l_{1},l_{2},\ldots,l_{n})|}{\det|(b_{1},b_{2},\ldots,b_{n})|}.

Remark 2.1.9.

For sublattices of $\mathbb{Z}^{2}$ , notice that

\big{|}\det(b_{1},b_{2},\ldots,b_{n})\big{|}=\Bigg{|}\det\left(\begin{matrix}1% \\ 0\end{matrix}\right),\left(\begin{matrix}0\\ 1\end{matrix}\right)\Bigg{|}=1.

Hence, the index of a sublattice of $\mathbb{Z}^{2}$ is given by the determinant of its basis.

Definition 2.1.10.

Let $L$ be an integer line and $p$ be an integer point. Then the integer distance $\operatorname{ld}(p,L)$ between $p$ and $L$ is, for all points $V$ that lie on $L$ , the index of the sublattice generated by vectors $pV$ .

Remark 2.1.11.

Let $L$ be an integer line, and $p$ and integer point, with vectors $(x,y)$ , $(a,b)$ such that the point $p+(x,y)$ is on the line $L$ and $(a,b)$ is an integer unit vector along the line L. Then the integer distance $\operatorname{ld}(p,L)$ is given

\operatorname{ld}(p,L)=\begin{Vmatrix}x&a\\ y&b\end{Vmatrix}

Proposition 2.1.12.

Consider point $p$ and line $L$ . Then $\operatorname{ld}(p,L)$ is one more than the number of integer lines parallel to $L$ between (but not including) $L$ and the parallel line containing $p$ .