Minimal Polygons with Fixed Lattice Width

Abstract

We classify the unimodular equivalence classes of inclusion-minimal polygons with a certain fixed lattice width. As a corollary, we find a sharp upper bound on the number of lattice points of these minimal polygons.

1 Introduction and Definitions

Let $\Delta \subset \mathbb {R}^2$ be a non-empty lattice polygon, i.e., the convex hull of a finite number of lattice points in $\mathbb {Z}^2$, and consider a lattice direction $v\in \mathbb {Z}^2$, i.e., a non-zero primitive vector. The lattice width of $\Delta$ in the direction v is

$$\begin{aligned} {{\,\mathrm{lw}\,}}_v(\Delta )=\max _{P\in \Delta }\left\langle P,v\right\rangle -\min _{P\in \Delta }\left\langle P,v\right\rangle . \end{aligned}$$

The lattice width of $\Delta$ is defined as ${{\,\mathrm{lw}\,}}(\Delta )=\min _v {{\,\mathrm{lw}\,}}_v(\Delta )$. Throughout this paper we will assume that $\Delta$ is two-dimensional, hence ${{\,\mathrm{lw}\,}}(\Delta )>0$. A lattice direction v that satisfies ${{\,\mathrm{lw}\,}}_v(\Delta )={{\,\mathrm{lw}\,}}(\Delta )$ is called a lattice width direction of $\Delta$.

Two lattice polygons $\Delta$ and $\Delta '$ are called (unimodularly) equivalent if and only if there exists a unimodular transformation $\varphi$, i.e., a map of the form

$$\begin{aligned}&\displaystyle \varphi :\mathbb {R}^2\rightarrow \mathbb {R}^2,\\&\displaystyle x\mapsto Ax+b, \quad \text {where} \quad A\in {{\,\mathrm{GL}\,}}_2(\mathbb {Z}),\ b\in \mathbb {Z}^2, \end{aligned}$$

such that $\varphi (\Delta )=\Delta '$. Equivalent lattice polygons have the same lattice width.

The lattice width of a polygon is a classical notion with connections to algebraic geometry, see for instance [8]. Its study goes back at least to 1974 [6], although the terminology is not uniform.

The lattice width of a polygon can be seen as a specific instance of the more general notion of lattice size, which was introduced in [3].

Definition 1.1

Let $X\subset \mathbb {R}^2$ be a subset with positive Jordan measure. Then the lattice size ${{\,\mathrm{ls}\,}}_X(\Delta )$ of a non-empty lattice polygon $\Delta$ is the smallest $d\in \mathbb {Z}_{\ge 0}$ for which there exists a unimodular transformation $\varphi$ such that $\varphi (\Delta )\subset \mathrm{d}X$.

Note that ${{\,\mathrm{lw}\,}}(\Delta )={{\,\mathrm{ls}\,}}_X(\Delta )$, where $X=\mathbb {R}\times [0,1]$.

This paper is concerned with polygons $\Delta$ that are minimal in the following sense: ${{\,\mathrm{lw}\,}}(\Delta ')<{{\,\mathrm{lw}\,}}(\Delta )$ for each lattice polygon $\Delta '\subsetneq \Delta$. Equivalently, a two-dimensional polygon $\Delta$ is minimal if and only if for each vertex P of $\Delta$, we have that ${{\,\mathrm{lw}\,}}(\Delta _P)<{{\,\mathrm{lw}\,}}(\Delta )$, where

$$\begin{aligned} \Delta _P:={{\,\mathrm{conv}\,}}\big (\big (\Delta \cap \mathbb {Z}^2\big ){\setminus }\{P\}\big ). \end{aligned}$$

This means that removing any vertex and then taking the convex hull of the remaining lattice points always produces a polygon of smaller lattice width.

Our main result is a complete classification of minimal polygons up to unimodular equivalence, see Theorem 2.4. As a corollary, we provide a sharp upper bound on the number of lattice points of these minimal polygons. First, we show in Lemma 2.3 that each minimal polygon $\Delta$ satisfies ${{\,\mathrm{ls}\,}}_\square (\Delta )={{\,\mathrm{lw}\,}}(\Delta )$, where

$$\begin{aligned} \square ={{\,\mathrm{conv}\,}}\left\{ (0,0),(1,0),(1,1),(0,1)\right\} . \end{aligned}$$

The latter can also be proven using results on lattice width directions of interior lattice polygons (see [4, Lemma 5.3]), but we choose to keep the paper self-contained and have provided a different proof. Moreover, we use the technical Lemma 2.2 in the proofs of both Lemmas 2.3 and Theorem 2.4.

In the joint paper [4] with Castryck and Demeyer, we study the Betti table of the toric surface $\text {Tor}(\Delta )\subset \mathbb {P}^{\sharp (\Delta \cap \mathbb {Z}^2)-1}$ for lattice polygons $\Delta$. In particular, we present a lower bound for the length of the linear strand of this Betti table in terms of ${{\,\mathrm{lw}\,}}(\Delta )$, which we conjecture to be sharp. To show this conjecture for polygons of a fixed lattice width, it essentially suffices to prove it for the minimal polygons (see [4, Corollary 5.2]). Hence, Theorem 2.4 allows us to check the conjecture using a computer algebra system.

Remark 1.2

Of course, the question of classifying minimal polytopes can also be asked in higher dimensions. For instance, it can be shown that each three-dimensional minimal polytope $\Delta \subset \mathbb {R}^3$ with ${{\,\mathrm{lw}\,}}(\Delta )=1$ is equivalent to a tetrahedron of the form

$$\begin{aligned} {{\,\mathrm{conv}\,}}\left\{ (0,0,0),(1,0,0),(0,1,0),(1,y,z)\right\} \end{aligned}$$

with $1\le y\le z$ and $\gcd (y,z)=1$. These include the Reeve tetrahedrons (where $y=1$). For comparison, there is only one minimal polygon with lattice width one up to equivalence, namely the standard simplex ${{\,\mathrm{conv}\,}}\{(0,0),(1,0),(0,1)\}$.

In all dimensions $k\ge 2$, among the minimal polytopes, we find the so-called empty lattice simplices$\Delta \subset \mathbb {R}^k$, i.e., convex hulls of $k+1$ lattice points without interior lattice points. If $k\ge 4$, not all empty lattice simplices have lattice width 1. For more information, see [1, 7, 9].

2 The Classification of Minimal Polygons

We use the notation from Sect. 1. The following result appears already in [2, Remark following Lemma 5.2], but can be proven in a shorter way.

Lemma 2.1

Let $\Delta \subset \mathbb {R}^2$ be a lattice polygon with ${{\,\mathrm{lw}\,}}(\Delta )=d$. If $\Delta$ has two linearly independent lattice width directions $v,w\in \mathbb {Z}^2$, then $ls_\square (\Delta )=d$.

Proof

If v and w do not form a $\mathbb {Z}$-basis of $\mathbb {Z}^2$, we take a primitive vector $u\in {{\,\mathrm{conv}\,}}\{(0,0),v,w\}$ such that v and u form a $\mathbb {Z}$-basis. Let $Q,Q'$ be lattice points of $\Delta$ such that

$$\begin{aligned} \left\langle Q',u\right\rangle -\left\langle Q,u\right\rangle ={{\,\mathrm{lw}\,}}_u(\Delta ). \end{aligned}$$

Write $u=\lambda v+\mu w$ with $0<\lambda ,\mu$ and $\lambda +\mu \le 1$. Now

$$\begin{aligned} d\le {{\,\mathrm{lw}\,}}_u(\Delta )=\left\langle Q',(\lambda v+\mu w)\right\rangle -\left\langle Q,(\lambda v+\mu w)\right\rangle \le \lambda {{\,\mathrm{lw}\,}}_v(\Delta )+\mu {{\,\mathrm{lw}\,}}_w(\Delta )\le d, \end{aligned}$$

so ${{\,\mathrm{lw}\,}}_u(\Delta )=d$. After applying a unimodular transformation, we may assume that $u=(0,1)$ and $v=(1,0)$, and that $\Delta$ fits into $d\square$, hence $ls_\square (\Delta )=d$. $\square$

Lemma 2.2

Let $\Delta$ be a lattice polygon with ${{\,\mathrm{lw}\,}}(\Delta )=d>0$. Let P be a vertex of $\Delta$ and $v\in \mathbb {Z}^2$ be a primitive vector. If ${{\,\mathrm{lw}\,}}_v(\Delta _P)<d$ and ${{\,\mathrm{lw}\,}}_v(\Delta _P)<{{\,\mathrm{lw}\,}}_v(\Delta )-1$, then $\Delta$ is equivalent to $\Upsilon _{d-1}:={{\,\mathrm{conv}\,}}\{(0,0),(1,d),(d,1)\}$.

Proof

Since ${{\,\mathrm{lw}\,}}_v(\Delta _P)<{{\,\mathrm{lw}\,}}_v(\Delta )-1$, we have that either

$$\begin{aligned} \min _{Q\in \Delta _P}\left\langle v,Q\right\rangle > \left\langle v,P\right\rangle +1 \quad \text {or} \quad \max _{Q\in \Delta _P}\left\langle v,Q\right\rangle < \left\langle v,P\right\rangle -1. \end{aligned}$$

By replacing v by $-v$, we may assume that we are in the first case. Moreover, we may choose v such that the difference $\min _{Q\in \Delta _P}\left\langle v,Q\right\rangle -\left\langle v,P\right\rangle$ is minimal but greater than one, and such that ${{\,\mathrm{lw}\,}}_v(\Delta _P)<d$.

We apply a unimodular transformation so that $P=(0,0)$ and $v=(0,1)$. Let $y_m$ (resp. $y_M$) be the smallest (resp. greatest) y-coordinate occurring in $\Delta _P$. Note that $y_m=\min _{Q\in \Delta _P}\left\langle v,Q\right\rangle$ and $y_M=\max _{Q\in \Delta _P}\left\langle v,Q\right\rangle$, hence $y_m>1$ and $y_M-y_m<d$.

Define the cone

$$\begin{aligned} C_k:=\{\lambda (k,1)+\mu (k+1,1)|\lambda ,\mu \ge 0\}. \end{aligned}$$

Since

$$\begin{aligned} \Delta \subset \left( \mathbb {R}\times \mathbb {R}_{>0}\right) \cup \{P\} = \cup _{k\in \mathbb {Z}}\, C_k \end{aligned}$$

and $y_m>1$, the polygon $\Delta$ is contained in a cone $C_k$ for some $k\in \mathbb {Z}$. Using the unimodular transformation $(x,y)\mapsto (x-ky,y)$, we may assume that $k=0$, i.e.,

$$\begin{aligned} \Delta \subseteq C_0=\left\{ \lambda (0,1)+\mu (1,1)|\lambda ,\mu \ge 0\right\} . \end{aligned}$$

In fact, we then have that

$$\begin{aligned} \Delta \subseteq {{\,\mathrm{conv}\,}}\left\{ (0,0),(1,y_M),(y_M-1,y_M)\right\} . \end{aligned}$$

If $y_m=2$, we have

$$\begin{aligned} y_M=(y_M-y_m)+2\le d+1. \end{aligned}$$

The strict inequality $y_M<d+1$ is impossible as the horizontal width ${{\,\mathrm{lw}\,}}_{(1,0)}(\Delta )$ would be less than d. So we have that $y_M=d+1$ and

$$\begin{aligned} \Delta \subseteq \Delta '={{\,\mathrm{conv}\,}}\left\{ (0,0),(1,d+1),(d,d+1)\right\} . \end{aligned}$$

Since ${{\,\mathrm{lw}\,}}((\Delta ')_Q)<d$ for

$$\begin{aligned} Q\in \left\{ (1,d+1),(d,d+1)\right\} , \end{aligned}$$

we must have $\Delta =\Delta '$. This is equivalent to $\Upsilon _{d-1}$ via $(x,y)\mapsto (x,y-x)$.

From now on, assume that $y_m>2$. Then $(1,2)\notin \Delta$ which means that either

$$\begin{aligned} \Delta \subseteq \{\lambda (0,1)+\mu (1,2)|\lambda ,\mu \ge 0\}\quad \text {or} \quad \Delta \subseteq \{\lambda (1,2)+\mu (1,1)|\lambda ,\mu \ge 0\}. \end{aligned}$$

We can reduce to the latter case using the transformation $(x,y)\mapsto (y-x,y)$. In fact, we can keep subdividing this cone until we find a cone C containing $\Delta$ that does not contain any lattice point with y-coordinate in $\{1,\ldots ,y_m-1\}$. Let $\ell \in \mathbb {Z}$ be such that C passes in between $(\ell -1,y_m-1)$ and $(\ell ,y_m-1)$. Then

$$\begin{aligned} \Delta _P\subseteq {{\,\mathrm{conv}\,}}\left\{ (\ell ,y_m-1),(\ell ,y_M),(\ell +y_M-y_m+1,y_M)\right\} . \end{aligned}$$

If $x_m$ (resp. $x_M$) is the smallest (resp. greatest) x-coordinate occurring in a lattice point of $\Delta _P$, then $2\le \ell \le x_m<y_m$ and $x_M\le \ell +y_M-y_m$, so $x_M-x_m\le y_M-y_m<d$. But this means that ${{\,\mathrm{lw}\,}}_{(1,0)}(\Delta _P)<d$ and

$$\begin{aligned} 1<\min _{Q\in \Delta _P}\left\langle (1,0),Q\right\rangle < y_m = \min _{Q\in \Delta _P}\left\langle v,Q\right\rangle , \end{aligned}$$

contradicting the minimality of v. $\square$

Lemma 2.3

If $\Delta \subset \mathbb {R}^2$ is a non-empty minimal lattice polygon with ${{\,\mathrm{lw}\,}}(\Delta )=d>0$, then ${{\,\mathrm{ls}\,}}_\square (\Delta )=d$.

Proof

By Lemma 2.1, we only have to show that there are two linearly independent lattice width directions. Suppose that v is a lattice width direction and that $Q,Q'\in \Delta \cap \mathbb {Z}^2$ such that $\left\langle Q,v\right\rangle -\left\langle Q',v\right\rangle =d$. Now let P be a vertex of $\Delta$ different from Q, $Q'$. By minimality of $\Delta$, we have that ${{\,\mathrm{lw}\,}}(\Delta _P)<d$. That means there exists a direction w such that ${{\,\mathrm{lw}\,}}_w(\Delta _P)<d$. Because Q and $Q'$ are still in $\Delta _P$, w cannot be v or $-v$, so w must be linearly independent of v. If ${{\,\mathrm{lw}\,}}_w(\Delta )=d$, we are done. If ${{\,\mathrm{lw}\,}}_w(\Delta )>d$, then by Lemma 2.2, $\Delta$ is equivalent to $\Upsilon _{d-1}\subseteq d\square$. $\square$

Theorem 2.4

Let $\Delta \subset \mathbb {R}^2$ be a non-empty minimal lattice polygon with ${{\,\mathrm{lw}\,}}(\Delta )=d$. Then $\Delta$ is equivalent to a minimal polygon of one of the following forms:

• (T1) ${{\,\mathrm{conv}\,}}\{(0,0),(d,y),(x,d)\}$, where $x,y\in \{0,\ldots ,d\}$ satisfy $x+y\le d$;

• (T2) ${{\,\mathrm{conv}\,}}\{(x_1,0),(d,y_2),(x_2,d),(0,y_1)\}$, where $x_1,x_2,y_1,y_2\in \{1,\ldots ,d-1\}$ satisfy $\max (x_2,y_2)\ge \min (x_1,y_1)$ and $\max (d-x_2,y_1)\ge \min (d-x_1,y_2)$;

• (T3) ${{\,\mathrm{conv}\,}}\{(0,0),(\ell ,0),(d,y+d-\ell ),(x+\ell ,d),(z,z+d-\ell )\}$ with $\ell \in \{2,\ldots ,d-2\}$, $x\in \{1,\ldots ,d-\ell -1\}$, $y,z\in \{1,\ldots ,\ell -1\}$;

• (T4) ${{\,\mathrm{conv}\,}}\{(0,0),(z'+\ell ,z'),(d,y+d-\ell ),(x+\ell ,d),(z,z+d-\ell )\}$ with $\ell \in \{2,\ldots ,d-2\}$, $y,z\in \{1,\ldots ,\ell -1\}$, $x,z'\in \{1,\ldots ,d-\ell -1\}$;

• (T5) ${{\,\mathrm{conv}\,}}\{(x_1,0),(z_2+\ell ,z_2),(d,d-\ell +y_2),(x_2+\ell ,d),(z_1,z_1+d-\ell ),(0,y_1)\}$ with $\ell \in \{2,\ldots ,d-2\}$, $x_1,y_2,z_1\in \{1,\ldots ,\ell -1\}$, $x_2,y_1,z_2\in \{1,\ldots ,d-\ell -1\}$.

Remark 2.5

See Fig. 1 for a picture of the five types. The minimal polygons appearing in the types (T3), (T4) and (T5) are inscribed in the hexagon

$$\begin{aligned} H_\ell :={{\,\mathrm{conv}\,}}\left\{ (0,0),(\ell ,0),(d,d-\ell ),(d,d),(\ell ,d),(0,d-\ell )\right\} . \end{aligned}$$

This is also the case for the triangles of type (T1) with $(x,y)\in \{(d,0),(0,d)\}$ (where we allow $\ell \in \{0,d\}$) and for the quadrangles of type (T2) with $\max (d-x_2,y_1)=\min (d-x_1,y_2)$.

Fig. 1

The five types in the classification

Proof of Theroem 2.4

If $d=0$, then $\Delta$ consists of a single point and it is of shape (T1). So assume $d\ge 1$. Because of Lemma 2.3, we may assume that $\Delta \subset d\square =[0,d]\times [0,d]$. Moreover, we may assume that $\Delta \not \cong \Upsilon _{d-1}$ since $\Upsilon _{d-1}$ is of type (T1). Let P be any vertex of $\Delta$. By Lemma 2.2, if ${{\,\mathrm{lw}\,}}_v(\Delta _P)<d$ for some primitive vector $v\in \mathbb {Z}^2$, then ${{\,\mathrm{lw}\,}}_v(\Delta _P)\ge {{\,\mathrm{lw}\,}}_v(\Delta )-1$, which together with ${{\,\mathrm{lw}\,}}_v(\delta )\ge d$ implies ${{\,\mathrm{lw}\,}}_v(\Delta _P)=d-1$ and ${{\,\mathrm{lw}\,}}_v(\Delta )=d$, hence v is a lattice width direction.

By minimality, we know that there always exists a lattice direction v satisfying ${{\,\mathrm{lw}\,}}_v(\Delta _P)<d$. We claim that we can always take

$$\begin{aligned} v\in \left\{ (0,1),(1,0),(1,1),(1,-1)\right\} . \end{aligned}$$

Indeed, suppose that $v=(v_x,v_y)\in \mathbb {Z}^2$ satisfies

$$\begin{aligned} \left\{ v,-v\right\} \cap \left\{ (0,1),(1,0),(1,1),(1,-1)\right\} =\emptyset \quad \text {and} \quad {{\,\mathrm{lw}\,}}_v(\Delta _P)<d. \end{aligned}$$

After a unimodular transformation, we may assume that $0<v_x<v_y$, hence $(1,1)\in {{\,\mathrm{conv}\,}}\{(0,0),(1,0),v\}$. Using a similar trick as in Lemma 2.1, we get that ${{\,\mathrm{lw}\,}}_{(1,1)}(\Delta _P)<d$, which proves the claim.

Let $\mathcal {V}$ be the set consisting of vectors $v\in \{(1,1),(1,-1)\}$ for which there exists a vertex P of $\Delta$ with ${{\,\mathrm{lw}\,}}_v(\Delta _P)<d$. If $\mathcal {V}=\{(1,1),(1,-1)\}$, then $\Delta$ has 4 different lattice width directions, namely (1, 0), (0, 1), (1, 1) and $(1,-1)$. By [2, Lemma 5.2(v)] or [5], this means that

$$\begin{aligned} \Delta \cong {{\,\mathrm{conv}\,}}\left\{ (d/2,0),(0,d/2),(d/2,d),(d,d/2)\right\} \end{aligned}$$

for some even d, hence it is of type (T2). If $\mathcal {V}=\emptyset$, we claim that $\Delta$ is of type (T1) or (T2). Indeed, for every vertex P of $\Delta$, we have that either ${{\,\mathrm{lw}\,}}_{(1,0)}(\Delta _P)$ or ${{\,\mathrm{lw}\,}}_{(0,1)}(\Delta _P)$ is smaller than d. In particular, this means that there has to be a side of $d\square$ with P as its only point in $\Delta$. One then easily checks the claim: if $\Delta$ is a triangle, then it will be of type (T1); if it is a quadrangle, then it is of type (T2).

From now on, suppose that $\mathcal {V}$ is not equal to $\emptyset$ or $\{(1,1),(1,-1)\}$, hence $\mathcal {V}=\{(1,1)\}$ or $\mathcal {V}=\{(1,-1)\}$. We can suppose that $\mathcal {V}=\{(1,-1)\}$ using the transformation $(x,y)\mapsto (x,-y)$ if necessary. Hence, for each vertex P of $\Delta$, there is a vector $v\in \{(1,0),(0,1),(1,-1)\}$ with ${{\,\mathrm{lw}\,}}_v(\Delta _P)<d$. Since ${{\,\mathrm{lw}\,}}_{(1,-1)}(\Delta )=d$, there exists an integer $\ell \in \{0,\ldots ,d\}$ such that

$$\begin{aligned} \left\langle Q,(1,-1)\right\rangle \in [\ell -d,\ell ] \end{aligned}$$

for all $Q\in \Delta$. If $\ell \in \{0,d\}$, then $\Delta$ is a triangle whose vertices are vertices of $d\square$, so it is of the form (T1). Now assume that $\ell \in \{1,\ldots ,d-1\}$, hence $\Delta$ is contained in the hexagon $H_\ell$ from Remark 2.5. Each side of $H_\ell$ contains at least one lattice point of $\Delta$, and if it contains more than one point, it is also an edge of $\Delta$. Otherwise, there would be a vertex P lying on exactly one side of $H_\ell$, while not being the only point of $\Delta$ on that side of $H_\ell$. But then there is no $v\in \{(0,1),(1,0),(1,-1)\}$ with ${{\,\mathrm{lw}\,}}_v(\Delta _P)<d$ (as every side of $H_\ell$ contains a point of $\Delta _P$), a contradiction.

Denote by $\mathcal {S}$ the set of sides that $\Delta$ and $H_\ell$ have in common. Then $\mathcal {S}$ cannot contain two adjacent sides $S_1,S_2$: otherwise for the vertex $P=S_1\cap S_2$, each side of $H_\ell$ would have a non-empty intersection with $\Delta _P$, contradicting the fact that there is a $v\in \{(0,1),(1,0),(1,-1)\}$ with ${{\,\mathrm{lw}\,}}_w(\Delta _P)<d$.

Assume that $\sharp \mathcal {S}\ge 2$ and take $S_1=[Q_1,Q_2]\in \mathcal {S}$. Its adjacent sides of $H_\ell$ contain no points of $\Delta$ except from $Q_1$ and $Q_2$. This implies that $\mathcal {S}=\{S_1,S_2\}$, where $S_1,S_2$ are opposite edges of $H_\ell$, and that $\Delta$ is the convex hull of these two edges. Hence $\Delta$ is equivalent to the quadrangle

$$\begin{aligned} {{\,\mathrm{conv}\,}}\left\{ (\ell ,0),(d,d-\ell ),(\ell ,d),(0,d-\ell )\right\} \subset H_\ell , \end{aligned}$$

which is of type (T2).

If $\mathcal {S}$ consists of a single side S, we may assume that $S=[Q_1,Q_2]$ is the bottom edge of $H_\ell$. Let $P_1$ (resp. $P_2$) be the vertex of $\Delta$ on the upper left diagonal side (resp. the right vertical edge) of $H_\ell$. If $P_1$ is also on the top edge of $H_\ell$ (i.e., $P_1=(\ell ,d)$), then $\Delta$ has only four vertices, namely $Q_1$, $Q_2$, $P_1$, $P_2$. Applying the transformation $(x,y)\mapsto (x,-x+y+\ell )$, we end up with a quadrangle of type (T2). By a similar reasoning, if $P_2$ is on the top edge of $H_\ell$ (i.e., $P_2=(d,d)$), we end up with type (T2). If neither $P_1$ nor $P_2$ is on the top edge of $H_\ell$, then there is a fifth vertex $P_3$ on that top edge, and we are in case (T3).

The only remaining case is when $\mathcal {S}=\emptyset$, hence each edge of $H_\ell$ contains only one point of $\Delta$. If $H_\ell$ and $\Delta$ have no common vertex, then $\Delta$ is of type (T5). If they share one vertex, we can reduce to type (T4) using a transformation if necessary. Note that two common vertices of $H_\ell$ and $\Delta$ can never be connected by an edge of $H_\ell$ as that edge would be in $\mathcal {S}$, so there are at most three common vertices. If there are three shared vertices, then $\Delta$ is a triangle of type (T1), again using a transformation if necessary. So assume $H_\ell$ and $\Delta$ share two vertices. Together these two points occupy four edges of $H_\ell$ and each of the other two edges of $H_\ell$ (call them A and B) contains exactly one vertex of $\Delta$. Take two pairs of opposite sides of $H_\ell$ (so four sides in total) that together contain A and B, then they contain all vertices of $\Delta$: since any common vertex of $H_\ell$ and $\Delta$ lies on two sides of $H_\ell$, they cannot lie both on the sides we did not choose, as they are parallel. We can find a unimodular transformation mapping these sides into the four sides of $d\square$, hence $\Delta$ is of type (T2). $\square$

Remark 2.6

From the classification in Theorem 2.4, one can easily deduce the following result from [6]: ${{\,\mathrm{vol}\,}}(\Delta )\ge \frac{3}{8}{{\,\mathrm{lw}\,}}(\Delta )^2$ for each lattice polygon $\Delta \subset \mathbb {R}^2$, and equality holds for minimal polygons of type (T1) with d even and $x=y=\frac{d}{2}$. For odd d, this inequality can be sharpened to

$$\begin{aligned} {{\,\mathrm{vol}\,}}(\Delta )\ge \frac{3}{8}{{\,\mathrm{lw}\,}}(\Delta )^2+\frac{1}{8}, \end{aligned}$$

and equality holds for minimal polygons of type (T1) with $x=\frac{d-1}{2}$ and $y=\frac{d+1}{2}$.

Corollary 2.7

If $\Delta \subset \mathbb {R}^2$ is a non-empty minimal lattice polygon with ${{\,\mathrm{lw}\,}}(\Delta )=d>1$, then

$$\begin{aligned} \sharp (\Delta \cap \mathbb {Z}^2)\le \max \bigg (\big (d-1\big )^2+4,\big (d+1\big )\big (d+2\big )/2\bigg ). \end{aligned}$$

Moreover, this bound is sharp.

Note that from $d=6$ onwards $(d-1)^2+4$ starts winning.

Proof of Corollary 2.7

Note that there exist minimal polygons attaining the bound (see Fig. 2): the simplex ${{\,\mathrm{conv}\,}}\{(0,0),(d,0),(0,d)\}$ is of type (T1) and has $(d+1)(d+2)/2$ lattice points, and the quadrangle ${{\,\mathrm{conv}\,}}\{(1,0),(d,1),(d-1,d),(0,d-1)\}$ is of type (T2) and has $(d-1)^2+4$ lattice points.

Fig. 2

Minimal polygons attaining the upper bound

Now let us show that we indeed have an upper bound. If $\Delta$ is minimal of type (T2), (T4) or (T5), then

$$\begin{aligned} \sharp (\Delta \cap \mathbb {Z}^2)\le (d-1)^2+4, \end{aligned}$$

since there are at most 4 lattice points of $\Delta$ on the boundary of $\mathrm{d}\square$ and all the others are in

$$\begin{aligned} (\mathrm{d}\square )^{\circ }\cap \mathbb {Z}^2 = \{1,\ldots ,d-1\}\times \{1,\ldots ,d-1\}. \end{aligned}$$

This also holds for triangles of type (T1) with x and y non-zero. If $\Delta$ is of type (T3), we obtain the same upper bound $(d-1)^2+4$ after applying a unimodular transformation that maps the bottom edge of $\Delta$ to the left upper diagonal edge of $H_\ell$. We are left with triangles of type (T1) with either x or y zero. Assume that $y=0$ (the case $x=0$ is similar). Then $\Delta$ has the edge [(0, 0), (d, 0)] in common with $\mathrm{d}\square$ and its other vertex is (x, d). For each $k\in \{0,\ldots ,d\}$, the intersection of $\Delta$ with the horizontal line on height k is a line segment of length $d-k$, hence it contains at most $d-k+1$ lattice points. So in total, $\Delta$ has at most

$$\begin{aligned} \sum _{k=0}^d (d-k+1)=(d+1)(d+2)/2 \end{aligned}$$

lattice points. $\square$