#  $\mathbb{F}_{q}$-zeros of sparse trivariate polynomials
and toric 3-fold codes

Kyle Meyer  ,  Ivan Soprunov  and  Jenya Soprunova  Department of Mathematics
UC San Diego
San Diego, CA USA<EMAIL_ADDRESS>Department of Mathematical Sciences
Kent State University
Kent, OH USA<EMAIL_ADDRESS>Department of Mathematics and Statistics
Cleveland State University
Cleveland, OH USA<EMAIL_ADDRESS>
###### Abstract.

For a given lattice polytope $P\subset\mathbb{R}^{3}$, consider the space
$\cal L_{P}$ of trivariate polynomials over a finite field $\mathbb{F}_{q}$,
whose Newton polytopes are contained in $P$. We give upper bounds for the
maximum number of $\mathbb{F}_{q}$-zeros of polynomials in $\cal L_{P}$ in
terms of the Minkowski length of $P$ and $q$, the size of the field.
Consequently, this produces lower bounds for the minimum distance of toric
codes defined by evaluating elements of $\cal L_{P}$ at the points of the
algebraic torus $(\mathbb{F}_{q}^{*})^{3}$. Our approach is based on
understanding factorizations of polynomials in $\cal L_{P}$ with the largest
possible number of non-unit factors. The related combinatorial result that we
obtain is a description of Minkowski sums of lattice polytopes contained in
$P$ with the largest possible number of non-trivial summands.

###### Key words and phrases:

polynomials over finite fields, sparse polynomials, toric codes, lattice
polytopes, Minkowski length

###### 2020 Mathematics Subject Classification:

Primary 11T06, 52B10, 52B20; Secondary 11T71, 14M25, 14G50, 52B55

##  1\. Introduction

Let $X$ be a projective algebraic variety defined over a finite field
$\mathbb{F}_{q}$. It is a classical problem to estimate the number $N_{X}$ of
$\mathbb{F}_{q}$-points of $X$ in terms of its geometric invariants. For
curves, the following estimate is due to Hasse and Weil:

$|N_{X}-(q+1)|\leq 2gq^{\frac{1}{2}},$

where $X$ is an irreducible curve with arithmetic genus $g$, [1, 22]. In
particular, for smooth plane curves we have $2g=(d-1)(d-2)$, where $d$ is the
degree of the curve. In arbitrary dimension such an estimate is provided by
the Lang-Weil bound: For an irreducible projective variety $X$ of dimension
$n$ and degree $d$ defined over $\mathbb{F}_{q}$ one has

(1.1) $|N_{X}-\pi_{n}|\leq(d-1)(d-2)q^{n-\frac{1}{2}}+Cq^{n-1},$

for some constant $C$ depending on $n$, $d$, and $m$ only, see [22]. Here
$\pi_{n}$ denotes the number of $\mathbb{F}_{q}$-points in the $n$-dimensional
projective space, $\pi_{n}=\frac{q^{n+1}-1}{q-1}$. More recently, Ghorpade and
Lachuad proved an effective version of this inequality for complete
intersections, [13]. In addition, they obtained analogous inequalities for
affine varieties. For example, for an affine hypersurface
$X_{f}\subset\bar{\mathbb{F}}_{q}^{n}$ (so $\dim X_{f}=n-1$) defined by an
absolutely irreducible polynomial $f\in\mathbb{F}_{q}[x_{1},\dots,x_{n}]$ of
degree $d$ there is an explicit bound

(1.2)
$|N_{X_{f}}-q^{n-1}|\leq(d-1)(d-2)q^{n-\frac{3}{2}}+12(d+3)^{n+1}q^{n-2},$

see [13, 11.3]. Note that $N_{X_{f}}$, the number of $\mathbb{F}_{q}$-points
in $X_{f}$, is the same as the number of $\mathbb{F}_{q}$-zeros of $f$ in
$\mathbb{F}_{q}^{n}$ and $q^{n-1}$ is the number of $\mathbb{F}_{q}$-points in
the $(n-1)$-dimensional affine space.

In this paper we are dealing with polynomials $f$ with prescribed sets of
monomials and arbitrary coefficients. As the number of monomials of $f$ can be
significantly smaller compared to a generic polynomial of a given degree, such
polynomials are often called sparse. The theory of sparse polynomials (a.k.a.
Newton polytope theory) proposes that many algebraic properties of polynomials
are reflected in their Newton polytopes. Let $f\in\mathbb{F}_{q}[x_{1}^{\pm
1},\dots,x_{n}^{\pm 1}]$ be a Laurent polynomial over $\mathbb{F}_{q}$. The
set of the exponent vectors of the monomials appearing in $f$ is the support
of $f$, denoted by $\cal A(f)$, so we can write

$f=\sum_{a\in\cal A(f)}c_{a}x^{a},\text{ where }x^{a}=x_{1}^{a_{1}}\dotsm
x_{n}^{a_{n}},\ c_{a}\in\mathbb{F}_{q}^{*}.$

We put $\cal A(f)=\varnothing$ when $f=0$. The Newton polytope $P_{f}$ is the
convex hull of the support of $f$. For any two Laurent polynomials $f,g$ we
have $P_{fg}=P_{f}+P_{g}$, so one can view the Newton polytope as a natural
generalization of the degree of a polynomial. The sum here is the Minkowski
sum of the polytopes, which is the set of all sums $v_{1}+v_{2}$ for all pairs
$v_{1}\in P_{f}$ and $v_{2}\in P_{g}$. Therefore, factorizations of a sparse
polynomial correspond to Minkowski sum decompositions of its Newton polytope.

######  Example 1.1.

Consider $f=1-x+z-x^{a}y^{b}z$ for some relatively prime $a,b\in\mathbb{Z}$.
Then $P_{f}$ is a lattice simplex with vertex set
$\\{0,e_{1},e_{3},ae_{1}+be_{2}+e_{3}\\}$. Note that if $P_{f}$ is the
Minkowski sum of two lattice polytopes then one of them must be a single
point. This means that if $f=hg$ then either $h$ or $g$ is a monomial, i.e. a
unit in $\mathbb{F}_{q}[x^{\pm 1},y^{\pm 1},z^{\pm 1}]$. Therefore, $f$ is
absolutely irreducible. For the same reason every non-zero polynomial of the
form $f=c_{0}+c_{1}x+c_{2}z+c_{3}x^{a}y^{b}z$ for $c_{i}\in\mathbb{F}_{q}$ is
either a unit or absolutely irreducible.

When dealing with sparse polynomials $f$ it is natural to look for
$\mathbb{F}_{q}$-zeros of $f$ none of whose coordinate is zero, i.e., those
contained in the algebraic torus $(\mathbb{F}_{q}^{*})^{n}$. Throughout the
paper we use $N_{f}$ to denote this number, i.e.

$N_{f}=|\\{p\in(\mathbb{F}_{q}^{*})^{n}:f(p)=0\\}|.$

We will next illustrate how $N_{f}$ depends on geometric invariants of $P_{f}$
(rather than the degree of $f$) such as its volume. As it is common in the
theory of sparse polynomials, we use $\operatorname{Vol}_{n}(P)$ to denote the
normalized $n$-dimensional volume of a polytope which is the usual Euclidean
volume multiplied by $n!$.

Consider $f=1-x^{a}y^{b}\in\mathbb{F}_{q}[x^{\pm 1},y^{\pm 1}]$ for some
relatively prime $a,b\in\mathbb{N}$. This is an irreducible polynomial of
degree $a+b$. However, we can make a change of variables $x=u^{r}v^{-b}$,
$y=u^{s}v^{a}$ where $r,s\in\mathbb{Z}$ satisfy $ar+bs=1$. This change of
variables preserves the number of zeros in $(\mathbb{F}_{q}^{*})^{2}$ and
turns $f$ into a linear function $f=1-u$ which has $q-1$ zeros
in$(\mathbb{F}_{q}^{*})^{2}$. The geometric reason here is that the Newton
polytope $P_{f}$ is a segment with exactly two lattice points which can be
transformed to the unit segment $[0,e_{1}]$ by an integer linear map. In
general, the affine unimodular group $\operatorname{AGL}(n,\mathbb{Z})$ acts
on the Newton polytope $P_{f}$ and the corresponding monomial changes of
variables preserve $N_{f}$, see Section 2.2.

######  Example 1.2.

Let $f=1-x+z-x^{a}y^{b}z$ as in Example 1.1. To estimate $N_{f}$ first note
that if $x=1$ and $y^{b}=1$ then $(x,y,z)\in(\mathbb{F}_{q}^{*})^{3}$ is a
zero of $f$ for any $z\in\mathbb{F}_{q}^{*}$. If $x\neq 1$ and $x^{a}y^{b}\neq
1$ then $(x,y,z)$ is a zero of $f$ for a unique $z\in\mathbb{F}_{q}^{*}$.
Also, no other $(x,y,z)\in(\mathbb{F}_{q}^{*})^{3}$ can be a zero of $f$. In
the first case we have at most $b(q-1)$ zeros in $(\mathbb{F}_{q}^{*})^{3}$
and in the second case we have at most $(q-1)^{2}-2(q-1)+b$ zeros by the
inclusion-exclusion principle. Therefore,
$N_{f}\leq(q-1)^{2}+(b-2)q+2=(q-1)^{2}+(\operatorname{Vol}_{3}(P_{f})-2)q+2$.
See Theorem 5.5 for a generalization of this bound.

A related question that we are interested in is how to estimate the number of
$\mathbb{F}_{q}$-zeros of polynomials within a family of sparse polynomials
whose Newton polytopes are contained in some fixed lattice polytope $P$. Our
motivation comes from minimum distance estimation for a class of error-
correction codes called toric codes. In addition, this question is related to
factorization properties of sections of line bundles on a toric variety
defined over finite fields. We explain both connections in Section 1.2 below.
Given a lattice polytope $P$ in $\mathbb{R}^{n}$, denote by $\cal L_{P}$ the
family of sparse polynomials whose Newton polytope is contained in $P$:

(1.3) $\cal L_{P}=\\{f\in\mathbb{F}_{q}[x_{1}^{\pm 1},\dots,x_{n}^{\pm
1}]:P_{f}\subseteq P\\}.$

######  Problem 1.3.

Give a (sharp) upper bound on the number of $\mathbb{F}_{q}$-zeros in
$(\mathbb{F}_{q}^{*})^{n}$ of non-zero polynomials $f\in\cal L_{P}$ in terms
of geometric invariants of $P$.

For example, let $d\Delta^{n}$ be the $n$-dimensional simplex with vertex set
$\\{0,de_{1},\dots,de_{n}\\}$ for some positive integer $d<q$. Then $\cal
L_{d\Delta^{n}}$, which we denote simply by $\cal L_{d}$, is the space of all
$n$-variate polynomials of degree at most $d$. It is not hard to see that

$\max\\{N_{f}:0\neq f\in\cal L_{d}\\}=d(q-1)^{n-1}.$

Indeed, it is clear that for distinct $\alpha_{1},\dots,\alpha_{d}$ in
$\mathbb{F}_{q}^{*}$ the polynomial
$f=(x_{1}-\alpha_{1})\cdots(x_{1}-\alpha_{d})$ lies in $\cal L_{d}$ and has
exactly $d(q-1)^{n-1}$ zeros in $(\mathbb{F}_{q}^{*})^{n}$, which is the
largest among all polynomials with $d$ linear factors. One can then use
induction on $n$ to show that any polynomial of degree at most $d$ satisfies
the above bound (see Proposition 6.5). This observation motivates a
potentially easier problem.

######  Problem 1.4.

Give a (sharp) upper bound, in terms of geometric invariants of $P$, on the
number of $\mathbb{F}_{q}$-zeros in $(\mathbb{F}_{q}^{*})^{n}$ of polynomials
$f\in\cal L_{P}$ that have the largest possible number of non-unit factors.

We remark that a solution to Problem 1.4 provides a solution to Problem 1.3
when $q$ is large enough. Indeed, let $f=f_{1}\cdots f_{k}$ be a factorization
of $f\in\cal L_{P}$. Applying (1.1) to $X_{f_{i}}$ and their intersections it
is not hard to show that $|X_{f}(\mathbb{F}_{q})|=kq^{n-1}+o(q^{n-1})$.
Therefore, for large enough $q$, $|X_{f}(\mathbb{F}_{q})|$ is maximal when $k$
is.

Now let $f\in\cal L_{P}$ be a polynomial with the largest possible number $L$
of non-unit factors and let $f=f_{1}\cdots f_{L}$. Note that each $f_{i}$ must
be absolutely irreducible. Moreover, it will stay absolutely irreducible no
matter how we change its coefficients (as long as at least two of the
coefficients are non-zero), otherwise we would have obtained a polynomial in
$\cal L_{P}$ with more than $L$ non-unit factors. Continuing our analogy
between degrees and Newton polytopes, each $f_{i}$ is a “linear factor” whose
irreducibility is due to its “degree” (i.e. its Newton polytope) rather than
its coefficients. The difficulty here is that the Newton polytope of $f_{i}$
can be arbitrarily large in volume and $f_{i}$ can have many more
$\mathbb{F}_{q}$-zeros than a linear polynomial, as we saw in Examples 1.1 and
1.2. Although this may not be an issue for special classes of polytopes, e.g.
for $P=d\Delta^{n}$ considered above, for arbitrary polytopes this difficulty
appears in any dimension $n\geq 3$. When $n=2$ the situation is more
manageable as described in [32], which gave a solution to both Problems 1.4
and 1.3 for $n=2$, i.e. for bivariate sparse polynomials. We next present our
approach to addressing the aforementioned difficulty for $n=3$.

###  1.1. Our approach and results

As noted above, factorizations $f=f_{1}\cdots f_{k}$ for $f\in\cal L_{P}$
correspond to Minkowski sums of the corresponding Newton polytopes. Thus, the
geometric invariant that we need to consider in Problem 1.4 is the largest
number $L$ such that there exist lattice polytopes of positive dimension
$P_{1},\dots,P_{L}$ satisfying $P_{1}+\dots+P_{L}\subseteq P$. This invariant
is called the Minkowski length of $P$ and is denoted $L(P)$. For example,
$L(d\Delta^{n})=d$ (see Section 2.3). In general, there are no simple formulas
for $L(P)$, but there exists a polynomial time algorithm for computing $P$ in
dimensions 2 and 3, see [3, 32].

In the current paper we concentrate on the case $n=3$, i.e. the case of
trivariate sparse polynomials. We next formulate our answer to Problem 1.4 for
$n=3$. We write $[0,q-2]^{n}$ for the $n$-dimensional coordinate cube of side
length $q-2$.

######  Theorem 1.5 (Corollary 6.3).

Let $P\subseteq[0,q-2]^{3}$ be a lattice polytope of Minkowski length $L$.
Assume $\operatorname{char}(\mathbb{F}_{q})>41$ and
$q\geq(c+\sqrt{c^{2}+1})^{2}$, where
$c=\frac{1}{8}\left(\operatorname{Vol}_{3}(P)-3L+3\right)$. Then

$N_{f}\leq L\,(q-1)^{2}+2(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$

for any $f\in\cal L_{P}$ with the largest possible number of absolutely
irreducible factors.

$P$ | vertices | $\operatorname{Vol}_{3}(P)$ | property
---|---|---|---
$T_{0}$ | $\\{e_{1},\,e_{2},\,-e_{1}-e_{2}\\}$ | 0 | 2-dim
$S_{1}$ | $\\{0,e_{1},\,e_{2},\,e_{3}\\}$ | 1 | width one
$S_{2}$ | $\\{e_{1},\,e_{2},\,e_{3},\,e_{1}+e_{2}+e_{3}\\}$ | 2 | width one
$E$ | $\\{0,e_{1},\,e_{2},\,e_{3},\,e_{1}+e_{2}+e_{3}\\}$ | 3 | width one
$K_{1}$ | $\\{e_{1},\,e_{2},\,e_{3},\,-e_{1}-e_{2}-e_{3}\\}$ | 4 | Fano
$K_{2}$ | $\\{e_{1},\,e_{2},\,e_{1}+e_{2}+2e_{3},\,-e_{1}-e_{2}-e_{3}\\}$ | 5 | Fano
Table 1. Possible summands with 4 or more lattice points in a maximal
decomposition

Despite the fact that the combinatorics of polytopes is much richer starting
with $n=3$, the above bound turned out to be quite similar to the one for
$n=2$, which says that for any $P\subset\mathbb{R}^{2}$, the number of zeros
in $(\mathbb{F}_{q}^{*})^{2}$ of any $f\in\cal L_{P}$ with the largest
possible number of absolutely irreducible factors is at most $L\,(q-1)+\lfloor
2\sqrt{q}\rfloor-1$, see [32, Prop 2.3]. The additional factor of $(q-1)$ is
expected due to the dimension change, but, remarkably, the combinatorics only
contributed to the extra factor of 2 and additional assumptions on the size of
$q$.

To give a solution to Problem 1.3 for $n=3$, we show that the bound in Theorem
1.5 holds for large enough $q\geq\alpha(P)$ where the threshold $\alpha(P)$
also depends only on the invariants $L(P)$ and $\operatorname{Vol}_{3}(P)$,
see Theorem 6.4.

Our approach to solving Problem 1.4 for $n=3$ is based on first understanding
what maximal Minkowski decompositions $P_{1}+\dots+P_{L}\subseteq P$ may look
like for arbitrary $P\subset\mathbb{R}^{3}$. It follows from the definition of
$L=L(P)$ that in any such maximal decomposition we must have $L(P_{i})=1$,
$L(P_{i}+P_{j})=2$, $L(P_{i}+P_{j}+P_{k})=3$, and so on.

The classification of lattice polytopes with $L(P)=1$, up to the
$\operatorname{AGL}(3,\mathbb{Z})$-action, was first obtained by Joshua
Whitney in his Ph.D. thesis [38]. Independently, Blanco and Santos gave such a
classification in [6] where they call lattice polytopes with $L(P)=1$ distinct
pair-sums polytopes (dps-polytopes) after [11]. There are 108 classes of dps-
polytopes of lattice width greater than one and infinite families of classes
of lattice polytopes of lattice width one. For comparison, the classification
of planar lattice polytopes with $L(P)=1$, up to the
$\operatorname{AGL}(2,\mathbb{Z})$-action, consists of only three classes:
segments with exactly two lattice points, triangles with exactly three lattice
points, and triangles with exactly three boundary lattice points and one
interior lattice point, see [32, Th 1.4].

We rely on the Whitney and Blanco–Santos result, as well as previous
classification results due to Howe, White, and Kasprzyk [18, 28, 37] to
classify pairs and triples of polytopes (under appropriate lattice
equivalence) which can appear in a maximal Minkowski decomposition. In
particular, our classification implies that if a maximal Minkowski
decomposition contains at least two polytopes with 4 or more lattice points
then each such polytope is equivalent to one in Table 1. See also Figure 1.1
for a visualization. As a consequence, if a maximal Minkowski decomposition
contains more than one 3-dimensional polytope then the volume of each summand
is bounded. (If a maximal Minkowski decomposition contains only one
3-dimensional polytope then its volume can be arbitrarily large as seen in
Example 1.2.) Another implication of our results is that in any maximal
Minkowski decomposition there could be at most one lattice polytope with 6 or
more lattice points, in which case all the other summands are segments. This
classification constitutes a substantial combinatorial part of our work and
can be of independent interest to those working in discrete geometry and
lattice polytopes theory.

Figure 1.1. Possible summands with 4 or more lattice points in a maximal
decomposition

In our second step we estimate $N_{f}$ in the case when $L(P_{f})=1$. Here we
rely on Whitney’s result [38, Th 4.30] which implies that for large enough
characteristic of $\mathbb{F}_{q}$, one has
$N_{f}\leq(q-1)^{2}+(\operatorname{Vol}_{3}(P_{f})-2)q+2$ when $P_{f}$ belongs
to the 108 classes mentioned above. To prove his result he uses the
Grothendieck–Lefschetz trace formula and cohomology computation for the
hypersurface $X_{f}$ in a toric variety corresponding to $P_{f}$. We use
elementary arguments, similar to the ones in Example 1.2, together with the
BKK bound (Section 2.4), to show that the same bound holds for the infinite
families as well, see Theorem 5.5. This, combined with the combinatorial
results about maximal Minkowski decompositions, provides a bound for $N_{f}$
when $f$ factors into the largest number of irreducible factors. Theorem 6.1
gives concrete bounds depending on the number of factors with four or more
monomials whereas Corollary 6.3 gives a universal bound.

###  1.2. Application to toric varieties and toric codes

The polynomial spaces $\cal L_{P}$ we defined above appear naturally in toric
geometry. Consider a complete $n$-dimensional toric variety $X_{\Sigma}$ over
$\bar{\mathbb{F}}_{q}$, the algebraic closure of $\mathbb{F}_{q}$. It is
defined by a rational polyhedral fan $\Sigma$ whose 1-dimensional cones
$\rho_{1}\dots,\rho_{k}$ correspond to the torus invariant prime divisors
$D_{1},\dots,D_{k}$ on $X$. Let $D=\sum_{i=1}^{k}a_{i}D_{i}$ be a torus
invariant Cartier divisor on $X_{\Sigma}$ and $\cal O(D)$ the corresponding
line bundle. It defines a rational polytope

$P_{D}=\\{x\in\mathbb{R}^{n}:\langle x,v_{i}\rangle\geq-a_{i},1\leq i\leq
k\\},$

where $v_{i}\in\mathbb{Z}^{n}$ are the primitive generators of the $\rho_{i}$.
As shown in [12, Prop 4.3.3, 4.3.8], the space of global sections
$\Gamma(X_{\Sigma},\cal O(D))$ is spanned (as a $\bar{\mathbb{F}}_{q}$-linear
space) by the characters corresponding to the lattice points in $P_{D}$,

$\Gamma(X_{\Sigma},\cal O(D))=\sum_{a\in
P_{D}\cap\mathbb{Z}^{n}}\bar{\mathbb{F}}_{q}\chi^{a}.$

Then the space of sections that are invariant under the Frobenius automorphism
$\Phi\in\operatorname{Gal}(\bar{\mathbb{F}}_{q}/\mathbb{F}_{q})$ is the
$\mathbb{F}_{q}$-span of the corresponding characters,

$\Gamma^{\Phi}(X_{\Sigma},\cal O(D))=\sum_{a\in
P_{D}\cap\mathbb{Z}^{n}}\mathbb{F}_{q}\chi^{a}.$

In the case when $\cal O(D)$ is generated by global sections, $P_{D}$ is a
lattice polytope, see [12, Th 6.1.7], so $\Gamma^{\Phi}(X_{\Sigma},\cal O(D))$
is identified with the space $\cal L_{P_{D}}$ we defined in (1.3). Thus,
Problems 1.3 and 1.4 above are related to factorizations of
$\mathbb{F}_{q}$-sections of globally generated line bundles on toric 3-folds
and their $\mathbb{F}_{q}$-zeros.

Algebraic geometry codes (a.k.a. Goppa codes) are linear error-correcting
codes constructed by evaluating $\mathbb{F}_{q}$-sections of a divisor on an
algebraic curve at a fixed set of $\mathbb{F}_{q}$-points of the curve. It was
a major breakthrough in information theory when Tsfasman, Vlăduţ, and Zink
used this construction to improve a previously known bound for parameters of
linear codes (the asymptotic Gilbert-Varshamov bound), [35]. Since then
algebraic geometry codes received much attention and grew into a subfield of
both applied algebraic geometry and information theory. Inspired by this
construction, Hansen [15] introduced toric codes obtained by evaluating
$\mathbb{F}_{q}$-sections of a divisor on a toric surface at a fixed set of
$\mathbb{F}_{q}$-points of the surface. This prompted a series of papers on
toric codes defined for toric surfaces and higher dimensional toric varieties,
see for example [7, 16, 17, 20, 23, 24, 27, 32, 33, 36]. In particular, the
toric code construction for $n=2$ produced about a dozen of new champion
codes, see [9, 10, 25], that is codes with largest known minimum distance with
given length and dimension, as in Grassl’s table of best known codes [14].

Because of the connection described above, toric codes can be defined in
purely combinatorial terms without the use of toric geometry as follows. Fix a
lattice polytope $P\subset\mathbb{R}^{n}$ and let $\cal L_{P}$ be the
corresponding space of Laurent polynomials as in (1.3). Choose an order of the
elements of $(\mathbb{F}_{q}^{*})^{n}=\\{p_{1},\dots,p_{N}\\}$, where
$N=(q-1)^{n}$. This defines an evaluation map

$ev:\cal L_{P}\to\mathbb{F}_{q}^{N},\quad
ev:f\mapsto\left(f(p_{1}),\dots,f(p_{N})\right).$

A toric code $\cal C_{P}$ is the image of the evaluation map, $\cal
C_{P}=ev(\cal L_{P})$. It is known that if the lattice points of $P$ are
distinct in $(\mathbb{Z}/(q-1)\mathbb{Z})^{n}$ then the evaluation map is
injective, and hence, $\dim\cal C_{P}=\dim{\cal L_{P}}=|P\cap\mathbb{Z}^{n}|$,
[27]. In particular, this is true if $P\subseteq[0,q-2]^{n}$. Recall that the
weight $w(v)$ of a vector $v\in\mathbb{F}_{q}^{N}$ is the number of non-zero
entries in $v$. The minimum weight of a code $\cal C\subset\mathbb{F}_{q}^{N}$
(which for linear codes is the same as the minimum Hamming distance) is
defined by

$d=\min\\{w(v):0\neq v\in\cal C\\}.$

This is an important parameter responsible for the reliability of the code:
the larger $d$ is the more errors the code can correct. Thus, it is important
to be able to efficiently compute $d$ or at least provide good lower bounds
for $d$. In general, when $q$ is large, finding the exact value of $d$ becomes
a heavy computational problem. It immediately follows from the above
definitions that for a toric code $\cal C_{P}$ we have

$d=(q-1)^{n}-\max\\{N_{f}:0\neq f\in\cal L_{P}\\}.$

Therefore, Problem 1.3 is equivalent to finding a (sharp) lower bound for the
minimum weight of a toric code, in terms of geometric invariants of $P$. For
$n=3$, the result in Theorem 6.4 provides the following.

######  Corollary 1.6.

Let $P\subseteq[0,q-2]^{3}$ be a lattice polytope of Minkowski length $L$.
Assume $q\geq\alpha(P)$ where $\alpha(P)$ as in (6.2). Then the minimum weight
of the toric code $\cal C_{P}$ satisfies

$d\geq(q-1)^{3}-L\,(q-1)^{2}-2(q-1)(2\sqrt{q}-1).$

This result is a universal lower bound on the minimum distance of any $3$-fold
toric code, which does not require extra combinatorial information beyond
computing $\operatorname{Vol}_{3}(P)$ and $L(P)$. Asymptotically,
$(q-1)^{3}-L\,(q-1)^{2}+O(q^{3/2})$ is what one would expect when comparing
this bound to the known explicit answers for the minimum distance of a toric
code. In fact, $d=(q-1)^{n}-L\,(q-1)^{n-1}+O(q^{n-2})$ for all toric codes
considered in [24, 27, 33]. (Although the Minkowski length $L$ is not
discussed in these papers, one can easily compute it by presenting a Minkowski
decomposition of length $L$ in $P$ and embedding $P$ in $L\Delta^{n}$.)

The downside of the result in Corollary 1.6 for practical purposes is that it
holds for rather large size and characteristic of $\mathbb{F}_{q}$. To get a
better estimate on the minimum distance for a particular $P$ one would first
compute all maximal decompositions in $P$ and apply one of the bounds in
Theorem 6.1, depending on how many summands in a maximal decomposition have 4
or more lattice points. The condition on the characteristic may also be
relaxed, see Remark 5.4. This method already appears in [38]. Together with
our results on the combinatorics of maximal decompositions this may lead to a
practical algorithm for the minimum distance estimation of $3$-fold toric
codes. This is beyond the scope of this paper.

On the upside, when $P$ has lattice width one, we prove a better bound with a
much smaller threshold $q\geq\beta(P)$ (Theorem 7.1) and give an example when
the bound is sharp (Example 7.2). We state the corresponding application to
toric codes below.

######  Corollary 1.7.

Let $P\subseteq\mathbb{R}^{3}$ be a lattice polytope of lattice width one and
Minkowski length $L$. Assume $q\geq\beta(P)$ where $\beta(P)$ as in (7.1).
Then the minimum weight of the toric code $\cal C_{P}$ satisfies

$d\geq(q-1)^{3}-L\,(q-1)^{2}-(q-1)(2\sqrt{q}-1).$

Finally, in Section 8 we give examples of toric codes defined by polytopes of
lattice width greater than one and compare their parameters with theoretical
bounds. The minimum distance of three of the presented toric codes exceeds the
Gilbert-Varshamov bound for linear codes.

###  1.3. Acknowledgments

We are grateful to anonymous referees for their valuable comments which led to
significant improvements of the paper. Work of Meyer and Soprunova was
partially supported by NSF Grant DMS-1156798. Several of our classification
results on maximal Minkowski decomposition require a computer-assisted search.
We use combinatorial arguments to first reduce the question we are dealing
with to a finite number of cases and then use the Magma algebra system [8] to
sort out these cases. We wrote a Magma package to assist us with these
computations. The code is available at https://github.com/isoprou/minkowski-
length.

##  2\. Preliminaries

###  2.1. Lattice polytopes

We begin with standard notions in convex geometry and lattice polytope theory.
A polytope is the convex hull of a finite number of points in a Euclidean
space. We use $[v_{1},\dots,v_{k}]$ to denote the convex hull of
$v_{1},\dots,v_{k}\in\mathbb{R}^{n}$. We will write vectors in
$\mathbb{R}^{n}$ either in the standard basis $\\{e_{1},\dots,e_{n}\\}$ or as
columns of a matrix. The lattice polytope $\Delta^{n}=[0,e_{1},\dots,e_{n}]$
is called the standard $n$-simplex. The dimension $\dim P$ of a polytope
$P\subset\mathbb{R}^{n}$ is the dimension of the smallest affine subspace
containing the polytope. A hyperplane $H\subset\mathbb{R}^{n}$ is called a
supporting hyperplane for a polytope $P$ if $P\cap H\neq\varnothing$ and $P$
is contained in one of the closed half-spaces defined by $H$. In this case the
intersection $P\cap H$ is called a face of $P$. Faces of dimension 0 are
called vertices and faces of dimension $\dim P-1$ are called facets of $P$.

We say that a convex polytope $P\subset\mathbb{R}^{n}$ is a lattice polytope
if all vertices of $P$ are lattice points, that is, they belong to the integer
lattice $\mathbb{Z}^{n}$. We say that a lattice polytope $P$ is empty if its
only lattice points are its vertices. We say that it is clean if its faces are
empty polytopes. A lattice segment (i.e. 1-dimensional lattice polytope) which
is empty is called primitive. Equivalently, a lattice segment $[v_{1},v_{2}]$
is primitive if and only if its direction vector $v_{2}-v_{1}$ is primitive,
that is the coordinates of $v_{2}-v_{1}$ do not have a common divisor larger
than one. Recall that $\operatorname{Vol}_{n}(P)$ denotes the normalized
$n$-dimensional volume of a polytope which is the usual Euclidean volume
multiplied by $n!$. When $P$ is a lattice polytope,
$\operatorname{Vol}_{n}(P)$ is a non-negative integer.

Let $P\subset\mathbb{R}^{n}$ be a lattice polytope and $v\in\mathbb{Z}^{n}$ a
primitive vector. The non-negative integer

${\rm w}_{v}(P)=\max_{u\in P}\langle u,v\rangle-\min_{u\in P}\langle
u,v\rangle$

is called the lattice width of $P$ in the direction of $v$. The lattice width
${\rm w}(P)$ is smallest value of ${\rm w}_{v}(P)$ over all primitive
$v\in\mathbb{Z}^{n}$.

Let $\operatorname{GL}(n,\mathbb{Z})$ be the group of unimodular matrices,
that is, $n\times n$ integer matrices with determinant $\pm 1$. The
automorphism group of $\mathbb{Z}^{n}$, which we denote by
$\operatorname{AGL}(n,\mathbb{Z})$, consists of compositions of a
multiplication by a unimodular matrix and a translation by a lattice vector.
The elements of $\operatorname{AGL}(n,\mathbb{Z})$ are called affine
unimodular maps. The group $\operatorname{AGL}(n,\mathbb{Z})$ acts on the set
of all lattice polytopes in $\mathbb{R}^{n}$. We say that two lattice
polytopes in $\mathbb{R}^{n}$ are equivalent if there is
$\varphi\in\operatorname{AGL}(n,\mathbb{Z})$ that maps one to the other. A
lattice polytope equivalent to $\Delta^{2}$ is called a unit triangle and a
lattice polytope equivalent to $\Delta^{3}$ is called a unit 3-simplex.
Clearly, the volume, the width, and the number of (interior) lattice points
are $\operatorname{AGL}(n,\mathbb{Z})$-invariants.

We say that two $k$-tuples $(P_{1},\dots,P_{k})$ and
$(P^{\prime}_{1},\dots,P^{\prime}_{k})$ of lattice polytopes in
$\mathbb{R}^{n}$ are equivalent if there exists an affine unimodular map
$\varphi\in{\rm AGL}(n,\mathbb{Z})$ and lattice vectors
$v_{i}\in\mathbb{Z}^{n}$ such that $P^{\prime}_{i}=\varphi(P_{i})+v_{i}$ for
$i=1,\dots,k$. Note that the map $\varphi$ is the same for all $i$, but the
lattice translations are individual.

###  2.2. Monomial Changes of Variables

Let $f\in\mathbb{F}_{q}[x_{1}^{\pm 1},\dots,x_{n}^{\pm 1}]$ be a Laurent
polynomial over $\mathbb{F}_{q}$ and let $P=P_{f}$ be its Newton polytope. A
translation $P+v$ by a lattice vector $v\in\mathbb{Z}^{n}$ corresponds to
multiplying $f$ by the monomial $x^{v}$ and does not change the set of zeros
of $f$ in the algebraic torus $(\mathbb{F}_{q}^{*})^{n}$. Let
$U\in\operatorname{GL}(n,\mathbb{Z})$ be a unimodular matrix. Consider the
monomial change of variables $x_{i}=y^{u_{i}}$, where $u_{i}$ is the $i$-th
column of $U$, for $1\leq i\leq n$, and let
$g(y_{1},\dots,y_{n})=f(y^{u_{1}},\dots,y^{u_{n}})$ be the resulting Laurent
polynomial in $\mathbb{F}_{q}[y_{1}^{\pm 1},\dots,y_{n}^{\pm 1}]$. Note that
$x^{a}=y^{Ua}$ for any $a\in\mathbb{Z}^{n}$, which implies that the Newton
polytope of $g$ is the image of $P$ under $U$. Clearly, the map
$\phi:(\mathbb{F}_{q}^{*})^{n}\to(\mathbb{F}_{q}^{*})^{n}$ defined by
$\phi(t)=(t^{u_{1}},\dots,t^{u_{n}})$ is invertible and defines an
automorphism of $(\mathbb{F}_{q}^{*})^{n}$. In particular, the image of the
set of zeros of $f$ under $\phi$ is the set of zeros of $g$. We have, thus,
shown that $N_{f}$ is invariant under the
$\operatorname{AGL}(n,\mathbb{Z})$-action on the Newton polytope of $f$.

###  2.3. Minkowski length

Recall that the Minkowski sum $P+Q$ of two polytopes $P,Q$ in $\mathbb{R}^{n}$
is the set of all vector sums of their points:

$P+Q=\\{p+q:p\in P,q\in Q\\}\subset\mathbb{R}^{n}.$

The Minkowski sum of lattice polytopes is again a lattice polytope.

The full Minkowski length $L(P)$ of a lattice polytope $P$ was first defined
in [32]. In subsequent papers studying this invariant [3, 34] it was referred
to as Minkowski length, and we use this shorter name in the current paper as
well.

######  Definition 2.1.

Let $P\subset\mathbb{R}^{n}$ be a lattice polytope. Then the Minkowski length
$L=L(P)$ is the largest number $L$ such that $P$ contains a Minkowski sum
$P_{1}+\cdots+P_{L}$ of $L$ lattice polytopes $P_{i}$, each of positive
dimension. Every such Minkowski sum $P_{1}+\cdots+P_{L}$ is then called a
maximal decomposition in $P$.

Here are a few basic properties of the Minkowski length which either follow
directly by definition or are contained in [34]:

  1. (1)

$L(P)$ is an $\operatorname{AGL}(n,\mathbb{Z})$-invariant,

  2. (2)

$L(P)$ is superadditive: $L(P+Q)\geq L(P)+L(Q)$,

  3. (3)

$L(d\Delta^{n})=d$, where $d\Delta^{n}$ is the $d$-dilate of the standard
$n$-simplex,

  4. (4)

$L([0,d]^{n})=nd$, where $[0,d]^{n}$ is the $n$-dimensional coordinate cube of
side length $d$,

  5. (5)

if $P_{1}+\cdots+P_{L}\subseteq P$ is a maximal decomposition then
$L(P_{i_{1}}+\dots+P_{i_{k}})=k$ for any non-empty
$\\{i_{1},\dots,i_{k}\\}\subset\\{1,\dots,L\\}$.

Also, there is a simple upper bound on the number of lattice points in $P$ in
terms of $L=L(P)$:

(2.1) $|P\cap\mathbb{Z}^{n}|\leq(L+1)^{n}.$

Indeed, if $P$ has more than $(L+1)^{n}$ lattice points then two of them
coincide modulo $(\mathbb{Z}/(L+1)\mathbb{Z})^{n}$, which means that $P$
contains a lattice segment of lattice length $L+1$. In particular, lattice
polytopes with $L(P)=1$ have a most $2^{n}$ lattice points and this bound is
sharp, see [31, Th 2.5]. A polynomial time algorithm for computing $L(P)$ was
provided for $P\subset\mathbb{R}^{2}$ in [32] and for $P\subset\mathbb{R}^{3}$
in [3].

######  Proposition 2.2.

Let $P\subset\mathbb{R}^{n}$ be a lattice polytope and $L(P)$ its Minkowski
length. Then $L(P)$ is the maximal number of absolutely irreducible factors of
polynomials $f\in\cal L_{P}$.

###### Proof.

Let $f\in\cal L_{P}$ be a Laurent polynomial with the maximal number of
absolutely irreducible factors, $f=f_{1}\cdots f_{L}$. Then
$P_{f}=P_{f_{1}}+\dots+P_{f_{L}}$, $P_{f}$ is contained in $P$, and $\dim
P_{f_{i}}>0$ since $f_{i}$ are not units. Therefore, $L\leq L(P)$.

Conversely, let $P_{1}+\dots+P_{L(P)}$ be a maximal decomposition in $P$.
Choose any Laurent polynomial $f_{i}\in\mathbb{F}_{q}[x_{1}^{\pm
1},\dots,x_{n}^{\pm 1}]$ with $P_{f_{i}}=P_{i}$ for $1\leq i\leq L(P)$. Note
that each $f_{i}$ is absolutely irreducible, otherwise $P_{f_{i}}$ would
decompose into a sum of lattice polytopes of positive dimension, which
contradicts the maximality of the decomposition $P_{1}+\dots+P_{L(P)}$.
Therefore, $L(P)\leq L$. ∎

###  2.4. Mixed volume

The mixed volume $V(P_{1},\dots,P_{n})$ is the unique multilinear (with
respect to Minkowski addition) function of $n$-tuples of convex polytopes
(more generally compact convex sets) in $\mathbb{R}^{n}$ which coincides with
the volume on the diagonal,

$V(P,\dots,P)=\operatorname{Vol}_{n}(P).$

One of the fundamental results in the theory of Newton polytopes is the
Bernstein-Khovanskii-Kushnirenko theorem (a.k.a. the BKK bound) which relates
the intersection number of generic hypersurfaces in the algebraic torus and
the mixed volume of their Newton polytopes, see [4, 19, 21]. Basic properties
of the mixed volume include invariance with respect to independent
translations of the $K_{i}$ and simultaneous unimodular transformations of the
$K_{i}$, as well as monotonicity with respect to inclusion in each of the
$K_{i}$, see [30, Sec 5]. The following property of the mixed volume goes back
to the work of Minkowski [26].

######  Proposition 2.3.

Let $P_{1},\dots,P_{n}\subset\mathbb{R}^{n}$ be convex polytopes. Then
$V(P_{1},\dots,P_{n})=0$ if and only if there exists non-empty
$\\{i_{1},\dots,i_{k}\\}\subseteq\\{1,\dots,n\\}$ such that
$\dim(P_{i_{1}}+\dots+P_{i_{k}})<k$.

We also note that when $P_{1},\dots,P_{n}$ are lattice polytopes
$V(P_{1},\dots,P_{n})$ is a non-negative integer. We will make use of the
following simple observations.

######  Lemma 2.4.

Let $P_{0},P_{1}\subset\mathbb{R}^{2}$ be convex polytopes and
$P\subset\mathbb{R}^{3}$ be the convex hull of
$(P_{0}\times\\{0\\})\cup(P_{1}\times\\{1\\})$. Then
$\operatorname{Vol}_{3}(P)=\operatorname{Vol}_{2}(P_{0})+V(P_{0},P_{1})+\operatorname{Vol}_{2}(P_{1}).$

###### Proof.

We have

$\operatorname{Vol}_{3}(P)=3\int_{0}^{1}\operatorname{Vol}_{2}((1-t)P_{0}+tP_{1})\,dt.$

Using $\operatorname{Vol}_{2}(A+B)=V(A+B,A+B)$ and the bilinearity of the
mixed volume we get
$\operatorname{Vol}_{2}((1-t)P_{0}+tP_{1})=(1-t)^{2}\operatorname{Vol}_{2}(P_{0})+2t(1-t)V(P_{0},P_{1})+t^{2}\operatorname{Vol}_{2}(P_{1})$.
Integrating, we obtain the claim. ∎

######  Lemma 2.5.

Let $P_{1},P_{2}\subset\mathbb{R}^{3}$ be lattice polytopes such that
$P_{1}+P_{2}$ is $3$-dimensional. Then
$\operatorname{Vol}_{3}(P_{1}+P_{2})\geq\operatorname{Vol}_{3}(P_{1})+3$.

###### Proof.

Since $P_{1}+P_{2}$ is $3$-dimensional, we can chose a lattice segment
$I\subseteq P_{2}$ such that $P_{1}+I$ is $3$-dimensional. Then, by the
multilinearity of the mixed volume,

$\operatorname{Vol}_{3}(P_{1}+P_{2})\geq\operatorname{Vol}_{3}(P_{1}+I)=\operatorname{Vol}_{3}(P_{1})+3V(P_{1},P_{1},I)+3V(P_{1},I,I)+\operatorname{Vol}_{3}(I).$

By Proposition 2.3 the last two summands are zero and $V(P_{1},P_{1},I)\geq
1$, since $P_{1}+I$ is $3$-dimensional. ∎

##  3\. Classifying pairs $(P,Q)$ with $L(P+Q)=2$

In this section we concentrate on classifying all pairs $(P,Q)$ of lattice
polytopes in $\mathbb{R}^{3}$, up to equivalence, satisfying $L(P)=L(Q)=1$ and
$L(P+Q)=2$. To simplify notation we write $|P|$ for the number of lattice
points of a polytope $P\subset\mathbb{R}^{3}$, i.e.
$|P|=|P\cap\mathbb{Z}^{3}|$. We call $|P|$ the size of $P$.

###  3.1. First observations

In many of our combinatorial arguments below we reduce the problem to a finite
number of cases which are then sorted with the aid of Magma [8]. Throughout
this section we mention some of the functions we wrote for this purpose and
explain what they do. A complete list of functions with code and description
is contained in https://github.com/isoprou/minkowski-length.

The proof of the next lemma uses the function minktwo, which checks whether
$L(P)\leq 2$ for a given lattice polytope $P$. Our package also includes
functions minkone and minkthree, which check whether $L(P)=1$ and $L(P)\leq
3$, respectively.

######  Lemma 3.1.

Let $P$ be a lattice triangle in $\mathbb{R}^{3}$ that satisfies $L(P)=1$ and
let $I$ be a primitive segment such that $L(P+I)=2$. Let $v$ be a primitive
normal to the lattice plane that contains $P$.

  * (1)

If $P$ is a unit triangle then $\operatorname{w}_{v}(I)\leq 14$.

  * (2)

If $P$ is equivalent to $T_{0}$ then $\operatorname{w}_{v}(I)\leq 2$.

###### Proof.

In part (1) we can assume that $P=[0,e_{1},e_{2}]$ is the standard 2-simplex.
By applying a matrix of the form $\left(\begin{matrix}1&0&\ast\\\ 0&1&\ast\\\
0&0&\pm 1\end{matrix}\right)$, which fixes the $(x,y)$-plane, we can ensure
that the components of the direction vector $u=(p,q,r)$ of $I$ satisfy $0\leq
p,q\leq r$. Due to symmetry we can further assume that $0\leq p\leq q\leq r$.
We then have $v=e_{3}$ and $\operatorname{w}_{v}(I)=r$, so we need to show
that $r\leq 14$.

Let $\Pi$ be the half-open parallelepiped spanned by the vectors
$e_{1},e_{2}$, and $u$:

$\Pi=\\{\lambda_{1}e_{1}+\lambda_{2}e_{2}+\lambda_{3}u\mid
0\leq\lambda_{i}<1\\}.$

Note that $r$ is the Euclidean volume of $\Pi$ and, hence, $\Pi$ contains
exactly $r$ lattice points (see [2, VII.2.5]). On the other hand, the plane
containing $e_{1},e_{2},u+e_{1}$, and $u+e_{2}$ subdivides the closure of
$\Pi$ into $P+I$ and its equivalent copy. Let $e$ be the number of interior
lattice points in $P+I$ and $f$ be the number of lattice points in the
relative interior of the facets of $P+I$. Observe that $P+I$ has no lattice
points in the relative interior of the edges and the triangular facets. Then,
on the one hand, $|P+I|=e+f+6$, and on the other hand $r=|\Pi|=2e+f+1$. This
implies $2|P+I|-r\geq 11$.

Now, since $L(P+I)=2$ there are at most 27 lattice points in $P+I$, see (2.1).
Combining with the previous inequality, we obtain $r\leq 43$. We next use
Magma to check for each $(p,q,r)$ with $0\leq p,q\leq r\leq 43$ whether
$L(P+I)=2$. This allows us to improve the bound to $r\leq 14$ and the
conclusion follows.

In part (2) we can assume that $P=T_{0}$. Since $T_{0}$ contains a unit
triangle, by part (1) the direction vector $(p,q,r)$ of $I$ satisfies $0\leq
p\leq q\leq r\leq 14$ . Using Magma we check for each such triple $(p,q,r)$
whether $L(P+I)=2$ and improve the bound to $r\leq 2$. ∎

Let $P$ be lattice polytope with $L(P)=1$ and let $I$ be a primitive segment
that satisfies $L(P+I)=2$. Let $u=(x,y,z)$ be a direction vector of $I$. Then
by Lemma 3.1, for each face $F_{i}$ with a normal vector
$v_{i}=(a_{i},b_{i},c_{i})$ we have $|a_{i}x+b_{i}y+c_{i}z|\leq 14$. Our
function GoodPolytope(P) outputs the polytope $G$ defined by these
inequalities. Furthermore, the function FindSegments(P) runs through all
primitive $(x,y,z)\in G$, checks whether for $I=[(0,0,0),(x,y,z)]$ we indeed
have $L(P+I)=2$, and outputs all $(x,y,z)$ for which this holds true. The
function AddTriangleHuh(P) checks whether such primitive segments can be used
to form a lattice triangle $T$ with $L(P+T)=2$. The function FindTriangles(P)
lists all such triangles. The function AddTetraHuh(P) checks whether one can
use these segments to form a tetrahedron $T$, possibly degenerate, that
satisfies $L(P+T)=2$. The function FindTetra(P) lists all such tetrahedra.

We now turn to our classification problem. A pair of primitive lattice
segments $(P,Q)$ with $L(P+Q)=2$ is equivalent to either
$([0,e_{1}],[0,e_{2}])$ or $([0,e_{1}],[0,e_{1}+2e_{2}])$, [32, Lemma 1.7]
(see also the proof of Lemma 4.1). As we just explained, given a lattice
polytope $P$ one can use Lemma 3.1 and function FindSegments to list all
primitive segments $Q$ that satisfy $L(P+Q)=2$. In particular, we can
enumerate up to the equivalence all pairs $(P,Q)$ where $P$ is a unit triangle
and $Q$ is a primitive segment that satisfy $L(P+Q)=2$. If $P$ and $Q$ are
both unit triangles we can assume that $P=[0,e_{1},e_{2}]$ and then use the
function FindTriangles to list all the unit triangles $Q$ that satisfy
$L(P+Q)=2$. We do not write these lists explicitly here as they are long and
not needed for our main results. Thus, in what follows we assume that $|P|\geq
4$ and $|Q|\geq 3$. In addition, we can assume $|P|\geq|Q|$, by symmetry.
Recall also that $L(P)=L(Q)=1$ implies $|P|,|Q|\leq 8$, by (2.1). All these
cases are covered by the following four possibilities:

  1. (1)

$P$ is an empty lattice polytope,

  2. (2)

$P$ is equivalent to $T_{0}$,

  3. (3)

$P$ has a subpolytope equivalent to $T_{0}$,

  4. (4)

$P$ is clean, but not empty.

We address each of them below.

###  3.2. $P$ is an empty lattice polytope

In this subsection we assume that $P$ is an empty lattice polytope, i.e., the
only lattice points of $P$ are its vertices. We treat the cases $|P|=4$ and
$|P|=5$ separately and then show that for $|P|\geq 6$ there is no lattice
polytope $Q$ with $|Q|\geq 3$ and $L(P+Q)=2$.

White’s theorem [37] states that every empty lattice tetrahedron in
$\mathbb{R}^{3}$ is equivalent to a tetrahedron

$T_{a,b}=\begin{bmatrix}1&0&0&a\\\ 0&1&0&b\\\ 0&0&1&1\end{bmatrix}.$

(We use such matrix form to denote the convex hull of the columns of the
matrix.) Here $a$ and $b$ are non-negative, relatively prime integers.
Moreover, $T_{a,b}$ is equivalent to $T_{a^{\prime},b^{\prime}}$ if and only
if $a+b=a^{\prime}+b^{\prime}$ and $a^{\prime}=\pm a^{-1}{\rm mod}(a+b)$. It
was further shown in [28] that any empty lattice polytope in $\mathbb{R}^{3}$
is of width one.

######  Lemma 3.2.

Let $P$ be an empty lattice tetrahedron and let $Q$ be a lattice polytope such
that $L(Q)=1$ and $L(P+Q)=2$. Then

  * (1)

If $|Q|=4$ then $\operatorname{Vol}_{3}(P)\leq 2$;

  * (2)

If $|Q|=3$ then $\operatorname{Vol}_{3}(P)\leq 5$.

###### Proof.

By White’s Theorem we can assume that $P=T_{a,b}$, where $b\geq a\geq 0$,
$a+b>0$, and $\gcd(a,b)=1$. Then $\operatorname{Vol}_{3}(P)=a+b$ and the
normals to the facets of $P$ are

$n_{1}=(1,1,1),\ n_{2}=(-1,-1,a+b-1),\ n_{3}=(-b,a,-b),\ {\rm and}\
n_{4}=(b,-a,-a).$

They satisfy the following relations

(3.1) $(a+b)e_{1}=an_{1}+n_{4},\ (a+b)e_{2}=bn_{1}+n_{3},\
(a+b)e_{3}=n_{1}+n_{2}.$

Let $u=(x,y,z)$ with $z\geq 0$ be a direction vector of a primitive lattice
segment in $Q$. By part (1) of Lemma 3.1 we have $|\langle u,n_{i}\rangle|\leq
14$ for $1\leq i\leq 4$. Therefore, by (3.1),

$(a+b)|x|=|\langle u,an_{1}+n_{4}\rangle|\leq a|\langle
u,n_{1}\rangle|+|\langle u,n_{4}\rangle|\leq 14(a+1).$

Similarly, we obtain $(a+b)|y|\leq 14(b+1)$ and $(a+b)|z|\leq 28$.

Suppose first that $a+b>28$. Then $z=0$ and, hence, $|x+y|=|\langle
u,n_{1}\rangle|\leq 14$ and $|bx-ay|=|\langle u,n_{3}\rangle|\leq 14$.
Switching the sign of $u$ if needed, we can assume that $x\geq 0$. But if
$x\geq 1$ and $y\leq-1$ then $14\geq|bx-ay|=bx+a(-y)\geq a+b>28$, a
contradiction. Hence, we can assume that $x,y\geq 0$. We next use Magma to
find all segments $I$ with direction vector $(x,y,0)$ such that $x+y\leq 14$,
$x,y\geq 0$ and the sum of $I$ and
$\operatorname{conv}\\{e_{1},e_{2},e_{3}\\}\subset P$ has Minkowski length 2.
The only such segments are the ones with $(x,y)=(1,0)$, $(0,1)$, and $(1,1)$.
Note that for the first two of these options the condition $|bx-ay|\leq 14$
implies $a\leq 14$ and $b\leq 14$, which contradicts $a+b>28$. Hence, these
two directions cannot appear simultaneously. We conclude that there is no $Q$
with $|Q|\geq 3$ in the case when $a+b>28$.

Next for each $P$ with $0\leq a\leq b$, $a+b\leq 28$, and $\gcd(a,b)=1$ we run
the functions AddTriangleHuh and AddTetraHuh and conclude that $a+b\leq 2$ in
case (1) and $a+b\leq 5$ in case (2), and the conclusions of the lemma follow.
∎

######  Remark 3.3.

Note that by White’s theorem there are six equivalence classes of empty
tetrahedra with volume at most 5 with
$(a,b)=(0,1),(1,1),(1,2),(1,3),(1,4),(2,3)$. Using the functions GoodPolytope
and FindTriangles one can enumerate (up to equivalence) all $(P,Q)$ with
$L(P+Q)=2$, where $P$ is an empty tetrahedron and $Q$ is a unit triangle.

######  Theorem 3.4.

Let $P,Q\subset\mathbb{R}^{3}$ be empty tetrahedra such that $L(P+Q)=2$. Then
each of $P$ and $Q$ is equivalent to $S_{1}$ or $S_{2}$, as defined in Table
1.

###### Proof.

In the notation introduced in Lemma 3.2 we proved that $a+b\leq 2$, so we have
two options, $a=0,b=1$ and $a=b=1$, where the first option gives a tetrahedron
equivalent to $S_{1}$ (since both have volume 1) and the second one gives
$S_{2}$. ∎

The next proposition shows that if each of $P$ and $Q$ is equivalent to
$S_{2}$ then $P$ and $Q$ coincide up to lattice translation.

######  Proposition 3.5.

Suppose that lattice polytopes $P,Q\subset\mathbb{R}^{3}$ are each equivalent
to $S_{2}$ and that $L(P+Q)=2$. Then up to a lattice translation we have
$P=Q$.

###### Proof.

We run the function FindTetra for $S_{2}$ which outputs all $Q$ with $|Q|=4$
such that $L(S_{2}+Q)=2$. We then check which tetrahedra in the output are of
normalized volume 2. The output contains two tetrahedra, each of which is a
lattice translation of $S_{2}$. ∎

######  Theorem 3.6.

Let $P$ be an empty lattice polytope with $|P|=5$ and $L(P)=1$. Let $Q$ be a
lattice polytope such that $|Q|=4$, $L(Q)=1$, and $L(P+Q)=2$. Then the pair
$(P,Q)$ is equivalent to the pair $(E,S_{2})$, as defined in Table 1.

###### Proof.

By Howe’s Theorem [28], $P$ is equivalent to $\left[\begin{matrix}0&1&0&0&a\\\
0&0&1&0&b\\\ 0&0&0&1&1\end{matrix}\right]$, where $b\geq a\geq 0$, $a+b>0$,
and $\gcd(a,b)=1$. By removing the origin from the set of vertices of $P$ and
applying Lemma 3.2 to the obtained empty tetrahedron we conclude that $a+b\leq
2$, and, as in Theorem 3.4, either $a=b=1$ or $a=0$, $b=1$, where the latter
is ruled out since then $L(P)=2$.

For $a=b=1$, that is, for $P=E$ we run the function FindTetra which outputs
all $Q$ with $|Q|=4$ such that $L(P+Q)=2$. The output is a lattice shift of
$S_{2}$. ∎

######  Proposition 3.7.

Let $P$ be an empty lattice polytope with $|P|=6$ and $L(P)=1$. Let $Q$ be a
lattice polytope such that $|Q|\geq 3$ and $L(Q)=1$. Then $L(P+Q)\geq 3$.

###### Proof.

By Howe’s Theorem [28] any empty lattice 3-polytope is of width one. Size 6
lattice polytopes are classified in Tables 6 and 7 of [5]. All the polytopes
in these two tables except for the last entry in Table 7 are either non-empty
or have Minkowski length at least 2. We therefore can assume that
$P=\left[\begin{matrix}0&1&0&0&a&c\\\ 0&0&1&0&b&d\\\
0&0&0&1&1&1\end{matrix}\right]$, where $a,b,c,d>0$, $c+d>a+b$, and $ad-bc=\pm
1$.

It follows from Lemma 3.2 applied to the subpolytopes
$\left[\begin{matrix}1&0&0&a\\\ 0&1&0&b\\\ 0&0&1&1\end{matrix}\right]$ and
$\left[\begin{matrix}1&0&0&c\\\ 0&1&0&d\\\ 0&0&1&1\end{matrix}\right]$ that
$a+b\leq 5$ and $c+d\leq 5$. For each such $P$ we run function AddTriangleHuh
and conclude that there is no $Q$ with $|Q|=3$ and $L(P+Q)=2$. ∎

###  3.3. $P$ is equivalent to $T_{0}$

Now we consider the case when $P$ is equivalent to $T_{0}$, i.e., $P$ is a
lattice triangle with three boundary lattice points and one interior lattice
point. Note that the subgroup of symmetries of $T_{0}$ in ${\rm
GL(2,\mathbb{Z})}$ is isomorphic to the symmetric group $\mathbb{S}_{3}$ and
is generated by $\begin{bmatrix}0&-1\\\ 1&-1\end{bmatrix}$ and
$\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$.

######  Proposition 3.8.

Let $Q\subset\mathbb{R}^{3}$ be a lattice triangle with $|Q|=3$ such that
$L(T_{0}+Q)=2$. Then, after a lattice translation and a unimodular
transformation that maps $T_{0}$ to itself, $Q$ is equal to

$\begin{bmatrix}0&1&0\\\ 0&0&0\\\ 0&0&1\end{bmatrix}\text{ or}\
\begin{bmatrix}0&0&a\\\ 0&0&b\\\ 0&1&-1\end{bmatrix},\ {\rm where}\
a,b\in\mathbb{Z}\ {\rm satisfy}\ |a|,|b|\leq 3.$

###### Proof.

By Lemma 3.1 we have $\operatorname{w}_{e_{3}}(Q)\leq 2$, that is, lattice
points in $Q$ can have difference at most 2 in their $z$-coordinates. Assume
first that no two lattice points in $Q$ have the same $z$-coordinate, so after
a translation we can assume that the $z$-coordinates are $-1,0,1$. Then we can
unimodularly map $Q$ to $\begin{bmatrix}0&0&a\\\ 0&0&b\\\ 0&1&-1\end{bmatrix}$
while fixing the $(x,y)$-plane. The intersection of $Q$ with the $(x,y)$-plane
is the segment $I$ that connects the origin to $(a/2,b/2,0)$. Hence $T_{0}+Q$
contains $[0,e_{2}]+I$ and the area of this parallelogram is $|a|/2$. If
$|a|\geq 12$ the area is at least 6, so the parallelogram has at least 9
lattice points, which contradicts $L(T_{0}+Q)=2$. We conclude that $|a|<12$
and, similarly, we get the same bound on $|b|$. Using Magma we run through all
such values of $a$ and $b$ and check whether $L(T_{0}+Q)=2$. We conclude that
$|a|,|b|\leq 3$.

Next we consider the case when at least two lattice points of $Q$ have the
same $z$-coordinate. Then by Lemma 1.8 from [32] it follows that the vector
connecting these two points is $e_{1}$, $e_{2}$, or $e_{1}+e_{2}$. Using a
symmetry of $T_{0}$ we can assume that it is $e_{1}$. Then, after a lattice
translation and a unimodular transformation that fixes the $(x,y)$-plane, $Q$
has the form

$\begin{bmatrix}0&1&a\\\ 0&0&b\\\ 0&0&c\end{bmatrix}\ {\rm where}\
a,b,c\in\mathbb{Z}\ {\rm satisfy}\ 0\leq a,b<c\leq 2.$

Checking using Magma whether we get $L(T_{0}+Q)=2$ for such values of $a,b$,
and $c$ we conclude that $a=b=0$ and $c=1$, and the conclusion follows. Note
that we have shown that if $Q$ has two lattice points in the plane $z=0$ then
the third lattice point in $Q$ must be in the plane $z=1$ or $z=-1$. ∎

######  Theorem 3.9.

Let $Q\subset\mathbb{R}^{3}$ be a lattice polytope with $|Q|\geq 4$ and
$L(T_{0}+Q)=2$. Then $|Q|=4$ and, after a lattice translation and a unimodular
transformation that maps $T_{0}$ to itself, $Q$ is equal to

$\begin{bmatrix}0&0&3\\\ 0&0&0\\\ 0&1&-1\end{bmatrix}\ {\rm
or}\begin{bmatrix}0&1&0&1\\\ 0&0&0&2\\\ 0&0&1&-1\end{bmatrix}.$

Note that in the first case $Q$ is equivalent to $T_{0}$ and in the second
case $Q$ is equivalent to $S_{2}$.

###### Proof.

By Lemma 3.1 we have $\operatorname{w}_{e_{3}}(Q)\leq 2$, and since $|Q|\geq
4$, we know that $Q$ must have two lattice points with the same
$z$-coordinate, which after a translation can be assumed to be 0. In
Proposition 3.8 we showed that in this case $Q$ may have at most two
additional lattice points, one in the plane $z=1$, and another in $z=-1$,
which implies that $|Q|=4$. Further, by our work in Proposition 3.8, there
exists a unimodular transformation fixing the $(x,y)$-plane which brings $Q$
to the form $\begin{bmatrix}0&1&0&a\\\ 0&0&0&b\\\ 0&0&1&-1\end{bmatrix}$,
where $a,b\in\mathbb{Z}$ satisfy $|a|,|b|\leq 3.$ Using Magma, we find that up
to a lattice translation and a unimodular transformation that maps $T_{0}$ to
itself there are only two options for $Q$,

$\begin{bmatrix}0&0&3\\\ 0&0&0\\\ 0&1&-1\end{bmatrix}\ {\rm and}\
\begin{bmatrix}0&1&0&1\\\ 0&0&0&2\\\ 0&0&1&-1\end{bmatrix}.$

∎

For polytopes of width one, Theorem 3.9 provides the following.

######  Corollary 3.10.

Let $P\subset\mathbb{R}^{3}$ be of lattice width one. Then any maximal
decomposition in $P$ contains at most one summand with 4 or more lattice
points.

###### Proof.

After an affine unimodular transformation, we may assume that $P$ lies between
the planes $z=0$ and $z=1$. Suppose $P_{1},P_{2}$ are two summands in a
maximal decomposition in $P$ with $|P_{1}|\geq|P_{2}|\geq 4$. Note that one of
them, say $P_{1}$, must be 2-dimensional (otherwise
$\operatorname{w}_{e_{3}}(P_{1}+P_{2})>1$) and, hence, must be equivalent to
$T_{0}$. Applying an affine unimodular transformation we may further assume
that $P_{1}=T_{0}$. But then, by Theorem 3.9, $P_{2}$ must be equivalent to a
polytope whose width in the $z$-direction equals two, a contradiction. ∎

###  3.4. $P$ has a subpolytope equivalent to $T_{0}$

We next consider the case when $P$ contains a proper subpolytope equivalent to
$T_{0}$, hence, $|P|\geq 5$. As before, we first treat the case when $|P|=5$
and then show that for the case $|P|\geq 6$ there is no $Q$ with $|Q|\geq 3$
and $L(P+Q)=2$. In particular, this will imply that the subpolytope equivalent
to $T_{0}$ must be a facet of $P$.

According to the classification of size 5 polytopes in [5] the only such
polytopes $P$ with $|P|=5$ are the ones equivalent to

$T_{1}=\left[\begin{matrix}1&0&-1&0\\\ 0&1&-1&0\\\ 0&0&0&1\end{matrix}\right]\
\ {\rm or}\ \ T_{2}=\left[\begin{matrix}1&0&-1&2\\\ 0&1&-1&1\\\
0&0&0&3\end{matrix}\right].$

######  Proposition 3.11.

Let $P=T_{1}$ and let $Q$ be a lattice polytope such that $|Q|\geq 3$ and
$L(Q)=1$. Suppose that $L(P+Q)=2$. Then $|Q|=3$ and, up to a lattice
translation,

$Q=\begin{bmatrix}0&1&0\\\ 0&0&0\\\ 0&0&1\end{bmatrix},\begin{bmatrix}0&0&0\\\
0&1&0\\\ 0&0&1\end{bmatrix},\ {\rm or}\ \begin{bmatrix}0&-1&0\\\ 0&-1&0\\\
0&0&1\end{bmatrix}.$

###### Proof.

This is obtained by running the functions AddTriangleHuh and AddTetraHuh for
$T_{1}$. ∎

######  Remark 3.12.

It is convenient to give an invariant description of the triangles $Q$ in the
statement of Proposition 3.11. Let $P$ be a polytope equivalent to $T_{1}$.
Denote the vertices of $P$ by $v_{1},\dots,v_{4}$ such that
$[v_{1},v_{2},v_{3}]$ is the facet equivalent to $T_{0}$, and let $v_{0}$ be
the center of this facet. Then Proposition 3.11 claims that if $Q$ is a
polytope with $|Q|\geq 3$, $L(Q)=1$, and $L(P+Q)=2$ then $Q$ equals
$[v_{0},v_{1},v_{4}]$, $[v_{0},v_{2},v_{4}]$, or $[v_{0},v_{3},v_{4}]$.

######  Proposition 3.13.

Let $P=T_{2}$ and let $Q$ be a lattice polytope such that $|Q|\geq 3$ and
$L(Q)=1$. Then $L(P+Q)\geq 3$.

###### Proof.

The function AddTriangleHuh for $T_{2}$ gives an empty output and the
conclusion follows. ∎

######  Proposition 3.14.

Let $P$ be a lattice polytope that contains a proper subpolytope equivalent to
$T_{0}$ and let $Q$ be a lattice polytope such that $|Q|\geq 3$. Suppose that
$L(P)=L(Q)=1$ and $L(P+Q)=2$. Then $P$ is equivalent to $T_{1}$ and, in
particular, $|P|=5$.

###### Proof.

If $|P|=5$ then by the classification in [5] $P$ is equivalent to $T_{1}$ or
$T_{2}$, where the latter case is ruled out by Proposition 3.13. Suppose
$|P|\geq 6$. Let $[v_{1},v_{2},v_{3}]$ be the subpolytope equivalent to
$T_{0}$ and let $v_{0}$ be its center. Let $v_{4}$ and $v_{5}$ be two other
lattice points in $P$. Then both $[v_{1},v_{2},v_{3},v_{4}]$ and
$[v_{1},v_{2},v_{3},v_{5}]$ must be equivalent to $T_{1}$. By Remark 3.12,
this implies that
$Q\in\\{[v_{0},v_{1},v_{4}],[v_{0},v_{2},v_{4}],[v_{0},v_{3},v_{4}]\\}$ and,
at the same time,
$Q\in\\{[v_{0},v_{1},v_{5}],[v_{0},v_{2},v_{5}],[v_{0},v_{3},v_{5}]\\}$, which
is impossible. ∎

###  3.5. $P$ is clean, but not empty

We next work on the remaining case when $P$ is clean, but contains at least
one interior lattice point. Recall that clean means that the only boundary
lattice points of $P$ are its vertices. Since we have already considered the
case when $T_{0}$ is a subpolytope of $P$ we can further assume that no four
points in $P$ are coplanar.

First, assume that $P$ is a clean lattice tetrahedron with one interior
lattice point, i.e. a Fano tetrahedron. In the next proposition we use
Kasprzyk’s classification of Fano tetrahedra, see [18, Section 2].

######  Proposition 3.15.

Let $P\subset\mathbb{R}^{3}$ be a Fano tetrahedron and let
$Q\subset\mathbb{R}^{3}$ be a lattice polytope such that $L(Q)=1$ and
$L(P+Q)=2$. If $|Q|\geq 3$ then $P$ is equivalent to either $K_{1}$ or
$K_{2}$, as defined in Table 1.

###### Proof.

By the classification in [18], up to lattice equivalence, there are eight Fano
tetrahedra. For each such $P$, we run function AddTriangleHuh and it returns a
negative answer for all of them except for $K_{1}$ and $K_{2}$. ∎

######  Proposition 3.16.

Let $P=[v_{1},\dots,v_{4}]\subset\mathbb{R}^{3}$ be a Fano tetrahedron and
$v_{0}$ its interior lattice point. Let $Q\subset\mathbb{R}^{3}$ be a lattice
polytope with $|Q|=4$, $L(Q)=1$ and $L(P+Q)=2$.

  1. (1)

If $P$ is equivalent to $K_{1}$ then $Q$ equals $[v_{0},v_{1},v_{2},v_{3}]$,
$[v_{0},v_{1},v_{2},v_{4}]$, $[v_{0},v_{1},v_{3},v_{4}]$, or
$[v_{0},v_{2},v_{3},v_{4}]$. Moreover, $(P,Q)$ is equivalent to
$(K_{1},S_{1})$.

  2. (2)

If $P=K_{2}$ then $Q=\begin{bmatrix}0&0&1&1\\\ 0&1&0&1\\\
0&0&0&2\end{bmatrix}$, which is equivalent to $S_{2}$.

###### Proof.

We run the function AddTetraHuh for $K_{1}$ and $K_{2}$ and obtain the claimed
output. The tetrahedron $Q$ that we obtain in (2) is equivalent to $S_{2}$:

$\begin{bmatrix}-1&0&0\\\ 0&-1&0\\\
-1&-1&1\end{bmatrix}\cdot\begin{bmatrix}0&0&1&1\\\ 0&1&0&1\\\
0&0&0&2\end{bmatrix}+\begin{bmatrix}1\\\ 1\\\
1\end{bmatrix}=\begin{bmatrix}1&1&0&0\\\ 1&0&1&0\\\
1&0&0&1\end{bmatrix}=S_{2}.$

For (1) we also note that there exists a unimodular map preserving $K_{1}$
which maps the convex hull of the origin and any three vertices of $K_{1}$ to
$S_{1}$. ∎

We next work on the case when $P$ has more than one lattice point in the
interior. We can then use the following statement to reduce to the case of a
Fano tetrahedron.

######  Lemma 3.17.

Let $P$ be a lattice polytope in $\mathbb{R}^{3}$ such that no four lattice
points in $P$ are coplanar. If $P$ has an interior lattice point $p$, then $P$
contains a subpolytope which is a Fano tetrahedron with interior lattice point
$p$.

###### Proof.

By Carathéodory’s Theorem [2, I.2.3.] we can find four lattice points
$p_{1},p_{2},p_{3},p_{4}$ in $P$ such that the convex hull
$[p_{1},p_{2},p_{3},p_{4}]$ contains $p$ as an interior point. If $p$ is the
only such interior lattice point, then we are done, if there is another
interior lattice point $q$ then both $p$ and $q$ can be expressed as convex
combinations of $p_{1},p_{2},p_{3},$ and $p_{4}$

$\displaystyle p$
$\displaystyle=\alpha_{1}p_{1}+\alpha_{2}p_{2}+\alpha_{3}p_{3}+\alpha_{4}p_{4},$
$\displaystyle q$
$\displaystyle=\beta_{1}p_{1}+\beta_{2}p_{2}+\beta_{3}p_{3}+\beta_{4}p_{4}.$

Assume without loss of generality that
$\frac{\alpha_{4}}{\beta_{4}}\leq\frac{\alpha_{i}}{\beta_{i}}$ for
$i=1,\dots,4$. Multiplying the second equality by $\alpha_{4}/\beta_{4}$ and
subtracting the result from the first, we get

$p=\frac{\alpha_{1}\beta_{4}-\alpha_{4}\beta_{1}}{\beta_{4}}p_{1}+\frac{\alpha_{2}\beta_{4}-\alpha_{4}\beta_{2}}{\beta_{4}}p_{2}+\frac{\alpha_{3}\beta_{4}-\alpha_{4}\beta_{3}}{\beta_{4}}p_{3}+\frac{\alpha_{4}}{\beta_{4}}q,$

which is a convex combination of $p_{1},p_{2},p_{3},$ and $q$. Note that none
of the coefficients is zero for otherwise $P$ would contain four coplanar
lattice points. Thus $p$ is an interior point of the convex hull
$[p_{1},p_{2},p_{3},q]$. We next pass to this tetrahedron and continue the
process until $p$ is the only interior lattice point. ∎

We next generalize the result of Lemma 3.2 to the case when lattice
tetrahedron $P$ is not necessarily empty.

######  Lemma 3.18.

Let $P$ be a lattice tetrahedron and $Q$ be a lattice polytope such that
$|Q|\geq 3$, $L(P)=L(Q)=1$ and $L(P+Q)=2$. Then $\operatorname{Vol}_{3}(P)\leq
5$.

###### Proof.

We have $4\leq|P|\leq 8$ and the case when $|P|=4$ is covered in Lemma 3.2. We
now argue by induction on $|P|$. We assume that the conclusion holds true for
a tetrahedron with $n$ lattice points and assume that $|P|=n+1$. We pick a
lattice point in $P$ which is not a vertex and connect it to the four vertices
of $P$ to get a partition of $P$ into 3 or 4 tetrahedra (depending on whether
the point is on the surface or in the interior of $P$). Each of these new
tetrahedra has at most $n$ lattice points, so by the induction assumption the
volume of each of them is at most 5, and hence the volume of $P$ is bounded
from above by 20.

The facets of $P$ are either unit triangles or triangles equivalent to
$T_{0}$. Let the vertices of $P$ be $v_{1},\dots,v_{4}$. If the facets
$[v_{1},v_{2},v_{3}]$ and $[v_{1},v_{2},v_{4}]$ are equivalent to $T_{0}$ then
the lattice points inside these facets are $(v_{1}+v_{2}+v_{3})/3$ and
$(v_{1}+v_{2}+v_{4})/3$, but this implies that their difference
$(v_{3}-v_{4})/3$ has integer coordinates and, hence, the edge $[v_{3},v_{4}]$
is not primitive, which contradicts $L(P)=1$. We have shown that at most one
facet of $P$ is equivalent to $T_{0}$, so the remaining ones are unit
triangles. We can now apply a unimodular map to $P$ so that one of such facets
becomes $[0,e_{1},e_{2}]$ and, hence, $P=[0,e_{1},e_{2},(a,b,c)]$ for some
$(a,b,c)\in\mathbb{Z}^{3}$ such that $0\leq a\leq b\leq c\leq 20$. For each
such $P$ with $c\geq 6$ we run function AddTriangleHuh. The output is empty,
and the conclusion follows. ∎

######  Proposition 3.19.

Let $P,Q\subset\mathbb{R}^{3}$ be lattice polytopes such that $L(P)=L(Q)=1$
and $|Q|\geq 3$. Suppose that $P$ properly contains $K_{1}$. Then $L(P+Q)\geq
3$.

###### Proof.

Let $(a,b,c)$ be a vertex of $P$ which does not belong to $K_{1}$. Then the
tetrahedron $[0,e_{1},e_{2},(a,b,c)]$ is a subpolytope of $P$, so using Lemma
3.18 we conclude $|c|\leq 5$. Similarly, we have $|a|\leq 5$ and $|b|\leq 5$.
For each such $(a,b,c)$ we work with the subpolytope

$R=\begin{bmatrix}1&0&0&-1&a\\\ 0&1&0&-1&b\\\ 0&0&1&-1&c\end{bmatrix}$

of $P$. We check whether $L(R)=1$ and if this is the case we run function
AddTriangleHuh, applied to $R$. We observe that the only returned values are
the five lattice points $(a,b,c)\in K_{1}$ and the conclusion follows. ∎

######  Proposition 3.20.

Let $P,Q\subset\mathbb{R}^{3}$ be lattice polytopes such that $L(P)=L(Q)=1$
and $|Q|\geq 3$. Suppose that $P$ properly contains $K_{2}$. Then $L(P+Q)\geq
3$.

###### Proof.

Let $(a,b,c)$ be a vertex of $P$ which is not in $K_{2}$. Then
$R=\begin{bmatrix}1&0&1&-1&a\\\ 0&1&1&-1&b\\\ 0&0&2&-1&c\end{bmatrix}$ is a
subpolytope of $P$. Using Lemma 3.18 and considering the simplices in $R$ that
$(a,b,c)$ generates together with other vertices of $R$ (including the origin)
we get

$|c|\leq 5,\ \ |2b-c|\leq 5,\ \ |2a-c|\leq 5,\ \ |b+c|\leq 5,\ \ |a+c|\leq 5,$

which implies that $|a|\leq 3,|b|\leq 3$, and $|c|\leq 5$. For each $R$ with
such restriction on $a,b$, and $c$ we check whether $L(R)=1$. If this is the
case we run function AddTriangleHuh applied to $R$ and arrive at the stated
conclusion. ∎

###  3.6. Summary of the results

In the next three theorems we summarize the classification according to the
sizes of the polytopes in the pair: $(|P|,|Q|)=(5,4),(5,5),(6,3)$. In fact, we
show that the latter case we have $L(P+Q)\geq 3$. In particular, this implies
that if a maximal decomposition contains a polytope of size larger than 5 then
the other summands must be lattice segments. Note that the cases
$(|P|,|Q|)=(4,3),(4,4)$ are covered by Remark 3.3, Theorem 3.4, Proposition
3.8, and Theorem 3.9.

######  Theorem 3.21.

Let $P,Q\subset\mathbb{R}^{3}$ be lattice polytopes with $L(P)=L(Q)=1$,
$L(P+Q)=2$, $|P|=5$, and $|Q|=4$. Then the pair $(P,Q)$ is unimodularly
equivalent to $(K_{1},S_{1}),(K_{2},S)$, or $(E,S_{2})$, where
$S=\begin{bmatrix}0&0&1&1\\\ 0&1&0&1\\\ 0&0&0&2\end{bmatrix}$ is equivalent to
$S_{2}$.

Further, if (up to a lattice translation) $P=E$ then $Q=S_{2}$. Similarly, if
$P=K_{2}$ then $Q=S$, but if $P=K_{1}$ there are four options for $Q$. Namely,
$Q$ is one of the four empty tetrahedra properly contained in $K_{1}$.

###### Proof.

If $P$ is an empty polytope, by Theorem 3.6 we get the pair $(E,S_{2})$. If
$P$ contains a facet equivalent to $T_{0}$ then $P$ is equivalent to either
$T_{1}$ or $T_{2}$ and by Propositions 3.11 and 3.13 there is no such $Q$.
Finally, if $P$ is a Fano tetrahedron then Proposition 3.16 gives the first
two pairs on the list. ∎

######  Theorem 3.22.

Let $P,Q\subset\mathbb{R}^{3}$ be lattice polytopes with $L(P)=L(Q)=1$,
$L(P+Q)=2$, $|P|=5$, and $|Q|=5$. Then the pair $(P,Q)$ is equivalent to
$(K_{1},K_{1})$.

###### Proof.

By Theorem 3.21 each $P$ and $Q$ is individually equivalent to $K_{1}$,
$K_{2}$, or $E$. Further, if $P$ is equivalent to $E$ or $K_{2}$ then there is
only one option for a $4$-point polytope that can appear in a maximal
decomposition with $P$ and, since, a 5-point $Q$ would contain more than one
4-point subpolytope, we conclude that each $P$ and $Q$ is equivalent to
$K_{1}$. Let $P=K_{1}$ then by Theorem 3.21 the only lattice 4-polytopes that
can appear with $P$ in a maximal decomposition are the four empty tetrahedra
properly contained in $K_{1}$. Then the standard way of assembling these
tetrahedra to form $K_{1}$ is the only way a 5-point lattice polytope can be
formed using these, and we conclude that up to a lattice translation
$P=Q=K_{1}$. We use Magma to check that $L(K_{1}+K_{1})=2$. ∎

Finally, we show that lattice polytopes $P$ and $Q$ with $|P|=6$ and $|Q|=3$
cannot appear together in a maximal decomposition.

######  Theorem 3.23.

Let $P,Q\subset\mathbb{R}^{3}$ be lattice polytopes such that $|P|=6$ and
$|Q|=3$. Then $L(P+Q)\geq 3$.

###### Proof.

The case when $P$ is empty is covered by Proposition 3.7. If $P$ contains a
subpolytope equivalent to $T_{0}$ the conclusion follows from Proposition
3.14. If $P$ is clean then it contains two interior lattice points. Then by
Lemma 3.17 it properly contains a Fano tetrahedron which by Proposition 3.15
is equivalent to $K_{1}$ or $K_{2}$ and these cases are then covered by
Propositions 3.19 and 3.20. ∎

##  4\. Classifying triples $(P,Q,R)$ with $L(P+Q+R)=3$

Our next goal is to explore how three (and more) lattice polytopes with at
least four lattice points each can appear together in a maximal decomposition.

######  Lemma 4.1.

Let $I_{1}$, $I_{2}$, and $I_{3}$ be three lattice segments in
$\mathbb{R}^{3}$ with the corresponding linearly independent direction vectors
$u_{1},u_{2}$, and $u_{3}$ such that $L(I_{1}+I_{2}+I_{3})=3$. Let $v$ be the
primitive normal vector to the plane spanned by $u_{1}$ and $u_{2}$. Then
there are two possible cases:

  * (1)

$I_{1}+I_{2}$ is equivalent to the unit square $[0,e_{1},e_{2},e_{1}+e_{2}]$,
and then $\operatorname{w}_{v}(I_{3})\leq 9$;

  * (2)

$I_{1}+I_{2}$ is equivalent to the parallelogram
$[0,e_{1},e_{1}+2e_{2},2e_{1}+2e_{2}]$, and then
$\operatorname{w}_{v}(I_{3})\leq~{}4$.

###### Proof.

We can assume that $u_{1}=e_{1}$ and $u_{2}=(a,b,0)$ where $0\leq a<b$, and
hence $v=e_{3}$. By [32, Lemma 1.7] we have $b\leq 2$ which implies that
either $b=1$ and $a=0$, or $b=2$ and $a=1$. Note that in the first case
$I_{1}+I_{2}$ is equivalent to the unit square $[0,e_{1},e_{2},e_{1}+e_{2}]$,
and in the second to the parallelogram $[0,e_{1},e_{1}+2e_{2},2e_{1}+2e_{2}]$.
We can now assume that $u_{3}=(a,b,c)$, where $0\leq a\leq b<c$. Applying
Lemma 3.1 to $P=I_{1}+I_{2}$ and $Q=I_{3}$ we get
$c=\operatorname{w}_{e_{3}}(I_{3})\leq 14$. Next we use Magma to check whether
$L(I_{1}+I_{2}+I_{3})=3$ for all such $a,b$, and $c$ and improve the bound to
$c=\operatorname{w}_{e_{3}}(I_{3})\leq 9$ in case (1) and to
$c=\operatorname{w}_{e_{3}}(I_{3})\leq 4$ in case (2). ∎

######  Proposition 4.2.

Let $Q,R\subset\mathbb{R}^{3}$ be lattice polytopes with $|Q|\geq 3$ and
$|R|\geq 3$ such that $L(T_{0}+Q+R)=3$. Then $|Q|=|R|=3$ and up to a lattice
translation

$Q=R=\begin{bmatrix}0&1&0\\\ 0&0&0\\\ 0&0&1\end{bmatrix},\ \
\begin{bmatrix}0&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix},\ {\rm or}\
\begin{bmatrix}0&1&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}.$

###### Proof.

Suppose first that $|Q|=|R|=3$. In light of Proposition 3.8 we first assume
that $Q=\begin{bmatrix}0&0&a\\\ 0&0&b\\\ 0&1&-1\end{bmatrix}$, where
$a,b\in\mathbb{Z}$ satisfy $|a|,|b|\leq 3.$ Then $T_{0}+Q$ contains the sum of
primitive segments with direction vectors $e_{1}$ and $e_{3}$, so by Lemma 4.1
we conclude that if $(p,q,r)$ is a direction vector of a primitive segment in
$R$ then $|q|\leq 9$. Similarly, considering $e_{2}$ in the place of $e_{1}$
we get $|p|\leq 9$. Next, using part (2) of Lemma 3.1 we conclude that
$|r|\leq 2$.

For $|a|,|b|\leq 3$ we next use Magma to find all directions $(p,q,r)$ with
$|p|\leq 9,|q|\leq 9,|r|\leq 2$ such that for $I=[(0,0,0),(p,q,r)]$ we have
$L(T_{0}+Q+I)=3$ and then check whether such segments $I$ can be used to form
a lattice triangle $R$ with $L(T_{0}+Q+R)=3$. The computation confirms that
there are no such lattice triangles and hence by Proposition 3.8 we conclude
that there are three options for each $Q$ and $R$, namely,

$\begin{bmatrix}0&1&0\\\ 0&0&0\\\ 0&0&1\end{bmatrix},\ \
\begin{bmatrix}0&0&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}\\!,\ {\rm and}\
\begin{bmatrix}0&1&0\\\ 0&1&0\\\ 0&0&1\end{bmatrix}.$

Checking using Magma whether $L(T_{0}+Q+R)=3$ for each of these options we
conclude that up to a lattice translation $Q=R$. The general case with
$|Q|\geq 3$ and $|R|\geq 3$ follows. ∎

######  Proposition 4.3.

Suppose that lattice polytopes $P,Q,R\subset\mathbb{R}^{3}$ satisfy
$L(P+Q+R)=3$ and $|P|=|Q|=|R|=4$. If two out of these three polytopes are
individually equivalent to $S_{1}$ then, up to a lattice translation, we have
$P=Q=R=S_{1}$.

###### Proof.

Let $P$ and $Q$ be each equivalent to $S_{1}$ and assume $P=S_{1}$. We run the
function FindTetra for $S_{1}$ and record the output. We then cycle through
$Q$ and $R$ in this output list where we only consider $Q$ of volume one and
check if $L(S_{1}+Q+R)=3$. Up to a lattice translation, the only $Q$ and $R$
that satisfy this property are equal to $S_{1}$. ∎

######  Theorem 4.4.

Suppose that lattice polytopes $P,Q,R\subset\mathbb{R}^{3}$ with
$|P|,|Q|,|R|\geq 4$ satisfy $L(P+Q+R)=3$. Then, up to reordering and
individual lattice translations, there are five options for $(P,Q,R)$, where
in the first three options we have $|P|=|Q|=|R|=4$ and in the fourth one
$|P|=5$ and $|Q|=|R|=4$:

  * (i)

$P=Q=R$ and equivalent to $S_{1}$;

  * (ii)

$P$ is equivalent to $S_{1}$, and $Q=R$ and equivalent to $S_{2}$;

  * (iii)

$P=Q=R$ and equivalent to $S_{2}$;

  * (iv)

$(P,Q,R)$ is equivalent to $(E,S_{2},S_{2})$;

###### Proof.

Suppose first that $|P|=|Q|=|R|=4$. The case when $P=T_{0}$ is ruled out by
Proposition 4.2. Hence $P,Q$, and $R$ are empty tetrahedra and by Theorem 3.4
each of them is individually equivalent to $S_{1}$ or $S_{2}$. If two of them
are equivalent to $S_{1}$ then by Proposition 4.3 we have $P=Q=R=S_{1}$. Also,
$L(kS_{1})=k$ for $k\in\mathbb{N}$, see Section 2.3.

If two are equivalent to $S_{2}$ then by Proposition 3.5 they are the same up
to translation. Also, if all three are equivalent to $S_{2}$ then
$P=Q=R=S_{2}$. We confirmed using Magma that $L(3S_{2})=3$.

By Theorem 3.23 we have $|P|,|Q|,|R|\leq 5$. If, say, $|P|=5$ then such $P$
and options for 4-point $Q$ and $R$ are described in Theorem 3.21. Let first
$P=K_{1}$. Then each $Q$ and $R$ is equivalent to $S_{1}$, but this then
contradicts Proposition 4.3 since $K_{1}$ contains two different copies of
$S_{1}$. Further, if $P=K_{2}$ then $Q=R=S$, where $S$ is equivalent to
$S_{2}$. We rule this case out by checking using Magma that $L(K_{2}+2S)>3$.
If $P=E$ we get $Q=R=S_{2}$ and using Magma we confirm $L(E+2S_{2})=3$.

If $|P|=|Q|=5$ and $|R|=4$, by Theorems 3.21 and 3.22 we conclude that
$|P|=|Q|=K_{1}$ and $R$ is one of the four copies of $S_{1}$ properly
contained in $K_{1}$. We confirm using Magma that $L(K_{1}+K_{1}+S_{1})>3$.

Finally, if $|P|=|Q|=|R|=5$ then $P=Q=R=K_{1}$ and we get $L(P+Q+R)>3$ since
$K_{1}$ contains the segment $I=[(-1,-1,-1),(1/3,1/3,1/3)]$ and $L(3I)=4$. ∎

The following statement follows immediately from Theorem 4.4.

######  Corollary 4.5.

Let $P_{1},\dots,P_{k}\subset\mathbb{R}^{3}$ be $k\geq 3$ lattice polytopes
with at least 4 lattice points each such that $L(P_{1}+\cdots+P_{k})=k$. Then
up to reordering and individual lattice translations there are at most four
options for $(P_{1},\dots,P_{k})$:

  * (i)

$P_{1}=\cdots=P_{k}$ and equivalent to $S_{1}$;

  * (ii)

$P_{1}$ is equivalent to $S_{1}$, and $P_{2}=\cdots=P_{k}$ and equivalent to
$S_{2}$;

  * (iii)

$P_{1}=\cdots=P_{k}$ and equivalent to $S_{2}$;

  * (iv)

$(P_{1},\dots,P_{k})$ is equivalent to $(E,S_{2},\dots,S_{2})$.

######  Remark 4.6.

Note that we only claim that whenever $L(P_{1}+\cdots+P_{k})=k$ for $k\geq 3$,
we are in one of the cases (i) through (iv), but we do not claim that in each
of these cases we indeed have $L(P_{1}+\cdots+P_{k})=k$. Although this is true
in case (i), since $L(kS_{1})=k$ for all $k\geq 1$, we do not know whether
this is true in cases (ii)–(iv).

##  5\. Number of $\mathbb{F}_{q}$-zeros of polynomials with $L(P_{f})=1$

In this section we give an upper bound for the number of
$\mathbb{F}_{q}$-zeros of Laurent polynomials $f\in\mathbb{F}_{q}[x^{\pm
1},y^{\pm 1},z^{\pm 1}]$ whose Newton polytopes $P_{f}$ have Minkowski length
one. We start with a proposition which deals with polynomials that are linear
in $z$.

######  Proposition 5.1.

Consider a polynomial $f=f_{0}+zf_{1}$ for some
$f_{0},f_{1}\in\mathbb{F}_{q}[x^{\pm},y^{\pm}]$ without common factors. Let
$P$, $P_{0}$, and $P_{1}$ be the Newton polytopes of $f$, $f_{0}$, and
$f_{1}$, respectively. Then

$N_{f}\leq(q-1)^{2}+\left(\operatorname{Vol}_{3}(P)-\operatorname{Vol}_{2}(P_{0})-\operatorname{Vol}_{2}(P_{1})\right)q-N_{0}-N_{1},$

where $\operatorname{Vol}_{3}$ and $\operatorname{Vol}_{2}$ denote the
normalized 3- and 2-dimensional volumes, and $N_{i}$ is the number of
$\mathbb{F}_{q}$-zeros of $f_{i}$ in $(\mathbb{F}_{q}^{*})^{2}$, for $i=0,1$.

###### Proof.

Let $Z_{i}\subset(\mathbb{F}_{q}^{*})^{2}$ be the set of
$\mathbb{F}_{q}$-zeros of $f_{i}$, $i=0,1$, and let $Z_{0,1}=Z_{0}\cap Z_{1}$.
Note that for every $(x,y)\in Z_{0,1}$ and any $z\in\mathbb{F}_{q}^{*}$ the
triple $(x,y,z)$ is a zero of $f$. Furthermore, for any
$(x,y)\in(\mathbb{F}_{q}^{*})^{2}\setminus Z_{0}\cup Z_{1}$ there exists a
unique $z\in\mathbb{F}_{q}^{*}$ such that the triple $(x,y,z)$ is a zero of
$f$. Any other triple $(x,y,z)\in(\mathbb{F}_{q}^{*})^{3}$ cannot be a zero of
$f$. Therefore,

$N_{f}=|Z_{0,1}|(q-1)+(q-1)^{2}-|Z_{0}|-|Z_{1}|+|Z_{0,1}|.$

Our next step is to bound $|Z_{0,1}|$ from above by the mixed volume
$V(P_{0},P_{1})$. Let $C_{i}$ be the algebraic curve defined by $f_{i}=0$ in
the toric compactification of $(\bar{\mathbb{F}}_{q}^{*})^{2}$ corresponding
to $P_{0}+P_{1}$. Note that since $f_{0}$ and $f_{1}$ do not have common
factors, the intersection $C_{0}\cap C_{1}$ is zero-dimensional. Therefore, by
the BKK bound [4, Th B] we have

$|Z_{0,1}|\leq|C_{0}\cap C_{1}|\leq V(P_{0},P_{1}).$

It remains to use the formula in Lemma 2.4 which relates the mixed volume
$V(P_{0},P_{1})$ and the normalized volume of $P$. ∎

The following result appears in Whitney’s PhD thesis [38]. Its proof is based
on the Grothendieck-Lefschetz trace formula and cohomology computation for
hypersurfaces $H_{f}$ in a toric variety $X_{P}$, where $P$ is a lattice
polytope from one of the 108 classes of polytopes with $L(P)=1$ and lattice
width greater than one, and $f$ is a Laurent polynomial with Newton polytope
$P$.

######  Theorem 5.2.

[38, Th 4.30] Assume $\operatorname{char}(\mathbb{F}_{q})>41$. Let $f$ be a
Laurent polynomial whose Newton polytope $P$ satisfies $L(P)=1$ and ${\rm
w}(P)>1$. Then

$N_{f}\leq(q-1)^{2}+(\operatorname{Vol}_{3}(P)-F(P)/2)q+F(P)/2,$

where $\operatorname{Vol}_{3}(P)$ is the normalized 3-dimensional volume and
$F(P)$ is the number of facets of $P$.

######  Remark 5.3.

Whitney’s classification is split according to the number of vertices and the
number of interior lattice points of $P$, rather than the lattice width of
$P$. In fact, the “finite cases” in [38, Th 4.30] consist of 109 classes of
lattice polytopes, 1 of which has lattice width one (the class containing
$T_{1}$, see Section 3.4) and the other 108 have lattice width greater than
one.

######  Remark 5.4.

The condition on the field characteristic ensures that the corresponding
hypersurface $H_{f}$ has at worst isolated singularities, [38, Cor 4.18]. For
specific polytopes $P$ this condition can be relaxed. For example, when $P$
equals $K_{1}$ or $K_{2}$ it is enough to require
$\operatorname{char}(\mathbb{F}_{q})\neq 2,3$.

######  Theorem 5.5.

Assume $\operatorname{char}(\mathbb{F}_{q})>41$. Let $f$ be a Laurent
polynomial whose Newton polytope $P$ is 3-dimensional and has Minkowski length
one. Then

$N_{f}\leq(q-1)^{2}+(\operatorname{Vol}_{3}(P)-2)q+2,$

where $\operatorname{Vol}_{3}(P)$ is the normalized 3-dimensional volume of
$P$.

###### Proof.

This follows from Proposition 5.1 and Theorem 5.2. Indeed, if $P$ has lattice
width greater than one then the bound follows directly from Theorem 5.2 as $P$
has at least 4 facets. Thus we may assume that $P$ has lattice width one.
After an affine unimodular transformation which corresponds to a monomial
change of variables in $f$ we may assume that $P$ and $f$ have the form as in
Proposition 5.1. If $f_{0}$ and $f_{1}$ had a common factor then $P_{0}$ and
$P_{1}$ would contain a common Minkowski summand. But then $P_{0}$ and $P_{1}$
would have a pair of parallel sides which forces $P$ to contain a
parallelogram. This contradicts the assumption $L(P)=1$. Therefore, $f_{0}$
and $f_{1}$ do not have common factors and the conditions of Proposition 5.1
are satisfied. It remains to show that the bound in Proposition 5.1 is no
greater than $(q-1)^{2}+(\operatorname{Vol}_{3}(P)-2)q+2$, i.e.,

(5.1)
$\left(2-\operatorname{Vol}_{2}(P_{0})-\operatorname{Vol}_{2}(P_{1})\right)q\leq
N_{0}+N_{1}+2.$

First, each $P_{i}$ is either a point or one of the three polytopes of
Minkowski length one: a primitive segment, a unimodular triangle, or
equivalent to $T_{0}$. If at least one of the $P_{i}$ is equivalent to $T_{0}$
then (5.1) is trivial, as $\operatorname{Vol}_{2}(T_{0})=3$. We have the
following table of values of $\operatorname{Vol}_{2}(P_{i})$ and $N_{i}$ in
the other three cases.

$P_{i}$ | $\operatorname{Vol}_{2}(P_{i})$ | $N_{i}$
---|---|---
point | 0 | 0
primitive segment | 0 | $q-1$
unit triangle | 1 | $q-2$

It is straightforward to check that (5.1) holds for all possible pairs
$(P_{0},P_{1})$ with parameters as in the above table. Note that since $P$ is
3-dimensional the pairs (point, point), (point, segment), and (segment, point)
cannot happen. ∎

######  Proposition 5.6.

Let $P$ be the Newton polytope of a Laurent polynomial
$f\in\mathbb{F}_{q}[x^{\pm 1},y^{\pm 1},z^{\pm 1}]$. Assume
$\operatorname{char}(\mathbb{F}_{q})\neq 2,3$. We have the following upper
bounds on $N_{f}$

$P$ |  upper bound on $N_{f}$
---|---
primitive segment | $(q-1)^{2}$
unit triangle | $(q-1)(q-2)$
unit 3-simplex | $(q-1)^{2}-q+2$
equivalent to $T_{0}$ | $(q-1)(q+\lfloor 2\sqrt{q}\rfloor-2)$
equivalent to $S_{2}$ | $(q-1)^{2}+2$
equivalent to $E$ | $(q-1)^{2}+3$
equivalent to $K_{1}$ | $(q-1)^{2}+2q+2$
equivalent to $K_{2}$ | $(q-1)^{2}+3q+2$

###### Proof.

The first three bounds are standard and, in fact, are exact values of $N_{f}$.
This is because after a monomial change of variables (which preserves $N_{f}$)
the polynomial $f$ can be brought to the form $c_{0}+c_{1}x$,
$c_{0}+c_{1}x+c_{2}y$, and $c_{0}+c_{1}x+c_{2}y+c_{3}z$, respectively, for
some $c_{i}\in\mathbb{F}_{q}^{*}$. The fourth bound follows directly from the
Hasse-Weil bound as in [32, Proposition 2.1]. The fifth and the sixth bounds
follow from Proposition 5.1 as both $S_{2}$ and $E$ have width one. Finally,
the seventh and the eighth bounds follow from Theorem 5.2 and Remark 5.4 using
$\operatorname{Vol}_{3}(K_{1})=4$ and $\operatorname{Vol}_{3}(K_{2})=5$. ∎

##  6\. Number of $\mathbb{F}_{q}$-zeros of polynomials in $\cal L_{P}$

In this section we come to the main results of the paper which provide a
solution to Problems 1.3 and 1.4 for $n=3$. As before, we fix a lattice
polytope $P\subset\mathbb{R}^{3}$ and consider the space $\cal L_{P}$ of
Laurent polynomials whose Newton polytopes are contained in $P$. Let $N_{P}$
denote the largest number of $\mathbb{F}_{q}$-zeros in
$(\mathbb{F}_{q}^{*})^{3}$ over all non-zero $f\in\cal L_{P}$, i.e.

$N_{P}=\max\\{N_{f}:0\neq f\in\cal L_{P}\\}.$

Our goal is to come up with a bound for $N_{P}$ which depends on $q$ and the
Minkowski length of $P$. As in Problem 1.4, we first look at polynomials in
$\cal L_{P}$ that have the largest number of absolutely irreducible factors.

######  Theorem 6.1.

Assume $\operatorname{char}(\mathbb{F}_{q})>41$. Let $P\subset\mathbb{R}^{3}$
be a lattice polytope of Minkowski length $L$. Consider $f\in\cal L_{P}$ with
the largest number of absolutely irreducible factors. Let $k$ be the number of
those factors with $4$ or more monomials. Then

  1. (1)

if $k=0$ then $N_{f}\leq L\,(q-1)^{2}$;

  2. (2)

if $k=1$ then

    1. (a)

$N_{f}\leq L\,(q-1)^{2}+(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$, if $f$ has a
factor with Newton polytope equivalent to $T_{0}$,

    2. (b)

$N_{f}\leq L\,(q-1)^{2}+(\operatorname{Vol}_{3}(P)-3L+1)q+2$, otherwise;

  3. (3)

if $k=2$ then $N_{f}\leq L\,(q-1)^{2}+2(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$;

  4. (4)

if $k\geq 3$ then $N_{f}\leq L\,(q-1)^{2}+2k+1\leq L\,(q-1)^{2}+2L+1$.

###### Proof.

Let $f=f_{1}\cdots f_{L}$ be the factorization of $f$ into $L$ absolutely
irreducible factors. Recall that it corresponds to a maximal decomposition
$P_{1}+\dots+P_{L}\subseteq P$, where $P_{i}$ is the Newton polytope of
$f_{i}$. Ignoring possible common zeros of the $f_{i}$ we have $N_{f}\leq
N_{f_{1}}+\dots+N_{f_{L}}$ so it is enough to bound each $N_{f_{i}}$
separately.

In case (1) each $P_{i}$ is either a primitive segment or a unit triangle.
Using the first two rows in the table of Proposition 5.6 we obtain the bound.
In case (2a) the only summand of size four is equivalent to $T_{0}$ and the
others are either primitive segments or unit triangles, and the bound follows
from Proposition 5.6.

For (2b), assume that $|P_{1}|\geq 4$ and $|P_{i}|\leq 3$ for $i\geq 2$. By
Theorem 5.5,

$N_{f_{1}}\leq(q-1)^{2}+(\operatorname{Vol}_{3}(P_{1})-2)q+2.$

Also, by Lemma 2.5, we have

$\operatorname{Vol}_{3}(P)\geq\operatorname{Vol}_{3}(P_{1}+\dots+P_{L})\geq\operatorname{Vol}_{3}(P_{1})+3(L-1).$

Finally, for $i\geq 2$ we have $N_{f_{i}}\leq(q-1)^{2}$ by Proposition 5.6.
Combining these inequalities we obtain the required bound.

For (3) we use our classification from Section 3. Up to reordering the
$P_{i}$, we may assume that $|P_{1}|\geq|P_{2}|\geq 4$ and $|P_{i}|\leq 3$ for
$i\geq 3$. Then $N_{f_{i}}\leq(q-1)^{2}$ for $i\geq 3$ and we need to show

(6.1) $N_{f_{1}}+N_{f_{2}}\leq 2(q-1)^{2}+2(q-1)(\lfloor 2\sqrt{q}\rfloor-1).$

As we saw in Section 3.6, the only possible pairs of sizes $(|P_{1}|,|P_{2}|)$
are $(4,4)$, $(5,4)$, and $(5,5)$. In the first case, by Theorem 3.4 and
Theorem 3.9, each of $P_{1}$ and $P_{2}$ is equivalent to $S_{1}$, $S_{2}$, or
$T_{0}$. By comparing the bounds in Proposition 5.6, the largest bound for
$N_{f_{1}}+N_{f_{2}}$ is $2(q-1)(q+\lfloor 2\sqrt{q}\rfloor-2)$ when both
$P_{1}$ and $P_{2}$ are equivalent to $T_{0}$, and (6.1) follows. The case
$(|P_{1}|,|P_{2}|)=(5,4)$ is covered by Theorem 3.21. In this case the largest
bound for $N_{f_{1}}+N_{f_{2}}$ is $2(q-1)^{2}+3q+4$ when $P_{1}$ is
equivalent to $K_{2}$ and $P_{2}$ is equivalent to $S_{2}$. But this bound is
smaller than the one in (6.1) for $q\geq 4$. Finally, when
$(|P_{1}|,|P_{2}|)=(5,5)$, by Theorem 3.22, $(P_{1},P_{2})$ is equivalent to
$(K_{1},K_{1})$ and, hence, $N_{f_{1}}+N_{f_{2}}\leq 2(q-1)^{2}+4q+4$, which
is less than the bound in (6.1) for $q\geq 5$.

Lastly, for (4) we use Corollary 4.5. By Proposition 5.6, the largest bound is
obtained in case (iv), i.e., when exactly one of the $P_{i}$ is equivalent to
$E$ and the rest are equivalent to $S_{2}$. In this case we have $N_{f}\leq
L\,(q-1)^{2}+2k+1\leq L\,(q-1)^{2}+2L+1$, as stated. ∎

Note that the assumption $\operatorname{char}(\mathbb{F}_{q})>41$ in Theorem
6.1 is only needed in case (2b). Even in this case it can be relaxed depending
on which of the 108 finite classes the corresponding Newton polytope belongs
to, see Remark 5.4.

We remark that the bounds in Theorem 6.1 are rarely sharp, as the factors
often have common zeros which we do not take into account in the proof. For an
instance when the bound $N_{f}\leq L\,(q-1)^{2}$ is sharp, see Proposition 6.5
below.

######  Example 6.2.

Let $P_{1}=[2e_{1}+e_{2},e_{1}+2e_{2},0]$, $P_{2}=[3e_{1},e_{3},2e_{3}]$, and
$P=P_{1}+P_{2}$. Note that $P_{1}$ and $P_{2}$ are equivalent to $T_{0}$ and
$L(P)=2$, according to Theorem 3.9. Let $\mathbb{F}_{7}$ be the field of size
7 and consider $f_{1}=x^{2}y-2xy^{2}+1$ and $f_{2}=x^{3}-2z+z^{2}$ in
$\mathbb{F}_{7}[x,y,z]$. The $\mathbb{F}_{7}$-space $\cal L_{P}$ has dimension
$|P|=15$. The polynomial $f=f_{1}f_{2}$ is an element of $\cal L_{P}$ with the
largest possible number of non-unit factors. One can check that each of
$f_{1}$ and $f_{2}$ has $54$ zeros in $(\mathbb{F}_{7}^{*})^{3}$. Moreover,
they have 12 zeros in common and, hence, $N_{f}=96$. In fact, this is the
largest number of zeros over all non-zero $f\in\cal L_{P}$, as confirmed using
Magma. Let us compare this to the bounds we obtained above. For $q=7$ the
bound for $N_{f_{i}}$ in the fourth case of Proposition 5.6 equals $60$; and
the bound for $N_{f}$ in case (3) of Theorem 6.1 equals $120$.

As we saw in Theorem 6.1, the difference $N_{f}-L\,(q-1)^{2}$ can have various
orders of magnitude depending on the number of summands in the maximal
decomposition with 4 or more lattice points (i.e. the number of absolutely
irreducible factors of $f$ with 4 or more monomials). In our next result we
give a universal bound for $N_{f}$ in terms of the Minkowski length only, when
$q$ is sufficiently large. The threshold for $q$ also only uses the Minkowski
length and the volume of $P$ and does not require any knowledge of maximal
decompositions in $P$. The corresponding result for bivariate polynomials is
contained in [32, Theorem 2.5].

######  Corollary 6.3.

Let $P\subset[0,q-2]^{3}$ be a lattice polytope and $L=L(P)$ its Minkowski
length. Assume $\operatorname{char}(\mathbb{F}_{q})>41$ and
$q\geq(c+\sqrt{c^{2}+1})^{2}$, where
$c=\frac{1}{8}\left(\operatorname{Vol}_{3}(P)-3L+3\right)$. Consider $f\in\cal
L_{P}$ with the largest number of absolutely irreducible factors. Then

$N_{f}\leq L\,(q-1)^{2}+2(q-1)(\lfloor 2\sqrt{q}\rfloor-1).$

###### Proof.

This follows from the observation that, when $q$ satisfies the above
condition, the bound in case (3) of Theorem 6.1 is the maximum of all the
bounds listed in there. Clearly, it is larger than the bounds in (1) and (2a).
Also, since $P\subset[0,q-2]^{3}$, we have $L=L(P)\leq L([0,q-2]^{3})=3(q-2)$,
see Section 2.3. Since $6(q-2)+1\leq 2(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$, it
follows that the bound in (4) is less than the one in (3). Finally, for the
bound in (2b), the inequality

$(\operatorname{Vol}_{3}(P)-3L+1)q+2\leq 2(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$

holds if and only if $q\geq(c+\sqrt{c^{2}+1})^{2}$, where
$c=\frac{1}{8}\left(\operatorname{Vol}_{3}(P)-3L+3\right)$, by a direct
calculation. ∎

In the next theorem we show that for large enough $q$ the bound in Corollary
6.3 holds for all non-zero $f\in\cal L_{P}$. We let $d$ be the smallest
integer such that $P$ is contained in $d\Delta^{3}$ up to a lattice
translation. We have $L=L(P)\leq L(d\Delta^{3})=d$, see Section 2.3. The case
$L=1$ was considered in the previous section, so we will assume that $L\geq
2$. Also, the case $d=L=2$ is simple: $N_{P}\leq 2(q-1)^{2}$, as follows from
Proposition 6.5 below. Thus, we will also assume that $d\geq 3$.

Define $\alpha(P)$ to be the smallest value of $q\geq 7507$ satisfying the
following two inequalities:

(6.2) $\begin{cases}\
(L-1)q^{2}-(d^{2}-3d-2)q^{3/2}-\left(12(d+3)^{4}+2(L+1)\right)q-4q^{1/2}+L+2\geq
0,\\\ \
q^{2}-(d_{1}^{2}-3d_{1}-2)q^{3/2}-\left(12(d_{1}+3)^{4}+6\right)q-4q^{1/2}+4\geq
0,\\\ \end{cases}$

where $d_{1}=d-L+2$. Note that when $L=2$ the two inequalities coincide.

######  Theorem 6.4.

Let $P\subset d\Delta^{3}$ be a lattice polytope of Minkowski length $L$ and
$3\leq d<q$. Let $\alpha(P)$ be as above. Then for any $q\geq\alpha(P)$ we
have the following bound for the maximal number of $\mathbb{F}_{q}$-zeros over
all $0\neq f\in\cal L_{P}$

(6.3) $N_{P}\leq L\,(q-1)^{2}+2(q-1)({2\sqrt{q}}-1).$

###### Proof.

Consider a non-zero polynomial $f\in\cal L_{P}$. Let $f=f_{1}\cdots f_{m}$ be
the factorization into absolutely irreducible factors. If $m=L$ then the
statement follows from Corollary 6.3, so we assume that $1\leq m\leq L-1$. Let
$k$ be the number of the $f_{i}$ of degree greater than one. If $k=0$ then
$N_{f}\leq m(q-1)^{2}$ which clearly is less than the bound in (6.3), hence,
we assume that $k\geq 1$. Without loss of generality we may assume that
$f_{1},\dots,f_{k}$ have degrees greater than one.

Let $d_{i}=\deg f_{i}$ and let $d^{\prime}=\deg f$. We have
$d^{\prime}=d_{1}+\dots+d_{m}=d_{1}+\dots+d_{k}+(m-k)$ and, hence,
$d^{\prime}\geq m+k$. According to (1.2), for $1\leq i\leq k$,

(6.4) $N_{f_{i}}\leq q^{2}+(d_{i}-1)(d_{i}-2)q^{3/2}+12(d_{i}+3)^{4}q,$

and, hence,

$N_{f}\leq(m-k)(q-1)^{2}+kq^{2}+\sum_{i=1}^{k}(d_{i}-1)(d_{i}-2)q^{3/2}+12(d_{i}+3)^{4}q.$

Note that the function
$\phi(d_{1},\dots,d_{k})=\sum_{i=1}^{k}(d_{i}-1)(d_{i}-2)q^{3/2}+12(d_{i}+3)^{4}q$
is convex and, hence, its maximum on the simplex
$d_{1}+\dots+d_{k}=d^{\prime}-m+k$, $d_{i}\geq 2$ is attained at the vertices.
Therefore,

$\begin{split}\phi(d_{1},d_{2},\dots,d_{k})&\leq\phi(d^{\prime}-m-k+2,2,\dots,2)\\\
&=(d^{\prime}-m-k+1)(d^{\prime}-m-k)q^{3/2}+12\left((d^{\prime}-m-k+5)^{4}+5^{4}(k-1)\right)q.\end{split}$

Note that the right hand side of the above inequality is increasing in
$d^{\prime}$. As $d^{\prime}\leq d$, this implies that $N_{f}$ is bounded
above by the function

$\begin{split}\psi(k,m)&=(m-k)(q-1)^{2}+kq^{2}+(d-m-k+1)(d-m-k)q^{3/2}\\\
&+12\left((d-m-k+5)^{4}+5^{4}(k-1)\right)q.\end{split}$

The function $\psi(k,m)$ is defined on the polygon $\Pi$ given by $1\leq k\leq
m\leq L-1,k+m\leq d$. Direct calculations show that $\psi(k,m)$ is convex on
$\Pi$ and attains maximum at one of its vertices. If $d\geq 2(L-1)$ then $\Pi$
is a triangle with vertices $\\{(1,1),(1,L-1),(L-1,L-1)\\}$. In this case
$\psi(1,L-1)\geq\psi(L-1,L-1)$ for all values of $q>0$. Indeed, when $L=2$
they are equal and when $L\geq 3$ we have

$\begin{split}&\frac{\psi(1,L-1)-\psi(L-1,L-1)}{L-2}=\\\
&(2d-3L+3)q^{3/2}+\left(12(2d-3L+12)\left((d-L+5)^{2}+(d-2L+7)^{2}\right)-12\cdot
5^{4}-2\right)q+1\geq\\\ &2q^{3/2}+550q+1>0,\end{split}$

where in the second to last inequality we used $d\geq 2(L-1)$ and $L\geq 3$.
Therefore,

$N_{f}\leq\psi(k,m)\leq\max\\{\psi(1,1),\psi(1,L-1)\\}.$

If $d<2(L-1)$ then $\Pi$ has four vertices
$\\{(1,1),(1,L-1),(d-L+1,L-1),(d/2,d/2)\\}$. First, we see that
$\psi(1,L-1)\geq\psi(d-L+1,L-1)$. Indeed,

$\begin{split}\psi(1,&L-1)-\psi(d-L+1,L-1)=\\\
&(d-L)(d-L+1)q^{3/2}+\left(12(d-L+5)^{4}-12\cdot
5^{4}(d-L+1)-2(d-L)\right)q+d-L.\end{split}$

One directly checks that each coefficient above is zero when $d=L$ and
positive when $d-L\geq 1$.

Next we note that for $q\geq 7507$ we also have
$\psi(d-L+1,L-1)>\psi(d/2,d/2)$. Indeed,

$\begin{split}\psi(d-L+1,L-1)-\psi(d/2,d/2)=\frac{1}{2}\left(2(L-1)-d\right)\left(q^{2}-7504q+2\right)>0.\end{split}$

It remains to note that $\psi(1,1)\leq L\,(q-1)^{2}+2(q-1)({2\sqrt{q}}-1)$ is
equivalent to the first inequality in (6.2) and $\psi(1,L-1)\leq
L\,(q-1)^{2}+2(q-1)({2\sqrt{q}}-1)$ is equivalent to the second inequality in
(6.2). Therefore,

$N_{f}\leq\max\\{\psi(1,1),\psi(1,L-1)\\}\leq L\,(q-1)^{2}+2(q-1)(\lfloor
2\sqrt{q}\rfloor-1),$

for all $q\geq\alpha(P)$. ∎

To conclude this section, we mention one case when we obtain a sharp upper
bound on $N_{P}$ for all values of $q\geq 2$. As we mentioned in the
introduction, when $P$ is the $L$-dilate of the standard simplex,
$P=L\Delta^{n}$, we have $N_{P}=L\,(q-1)^{n-1}$ by considering the product of
$L$ linear factors in one variable. The next proposition is a slight
generalization of this fact. The method used in the proof is standard and is a
part of folklore.

######  Proposition 6.5.

Let $P$ be a lattice polytope equivalent to a subpolytope of $L\Delta^{n}$.
Then $N_{P}\leq L\,(q-1)^{n-1}$. Moreover, $N_{P}=L\,(q-1)^{n-1}$ if and only
if $P$ contains a lattice segment of lattice length $L$.

###### Proof.

We prove the first statement and the “only if” part of the second statement by
induction on $n$. The case $n=1$ is trivial, so assume $n>1$. By applying an
affine unimodular map to $P$ we may assume $P\subseteq L\Delta^{n}$ and hence
every non-zero $f\in\cal L_{P}$ has degree at most $L$. Thus, we can write

$f=\sum_{i=0}^{m}f_{i}x_{n}^{i},$

where the $f_{i}$ are polynomials in $x_{1},\dots,x_{n-1}$ and $m$ is the
largest integer such that $f_{m}$ is non-zero. Note that $\deg f_{m}\leq L-m$.
Consider

$Z=\\{z\in(\mathbb{F}_{q}^{*})^{n-1}:f_{0}(z)=\dots=f_{m}(z)=0\\}.$

If $z\in Z$ then $f(z,x_{n})=0$ for any $x_{n}\in\mathbb{F}_{q}^{*}$. If
$z\not\in Z$ then $f(z,x_{n})$ is a non-zero polynomial in $x_{n}$ of degree
at most $m$ and, hence, has at most $m$ zeros. Therefore,

(6.5)
$N_{f}\leq|Z|(q-1)+\left((q-1)^{n-1}-|Z|\right)m=m(q-1)^{n-1}+|Z|(q-1-m).$

On the other hand, $|Z|\leq N_{f_{m}}\leq(L-m)(q-1)^{n-2}$, where the last
inequality follows by the inductive hypothesis applied to
$P=(L-m)\Delta^{n-1}$. Combining this with (6.5) produces

(6.6) $N_{f}\leq L\,(q-1)^{n-1}-m(L-m)(q-1)^{n-2}\leq L\,(q-1)^{n-1},$

and the first statement follows.

Now let $f\in\cal L_{P}$ be such that $N_{f}=L\,(q-1)^{n-1}$. Then in (6.6) we
have equality and, hence, either $m=0$ or $m=L$. In the first case $f=f_{0}$
whose support is contained in $P\cap L\Delta^{n-1}$. By induction, this
implies that $P\cap L\Delta^{n-1}$ (and, hence, $P$) contains a lattice
segment of length $L$. In the second case we see that the point $Le_{n}$
belongs to $P$. Replacing $x_{n}$ with $x_{n-1}$ in the above argument we
again see that $P$ contains either a lattice segment of length $L$ or the
point $Le_{n-1}$. But if it contains both $Le_{n-1}$ and $Le_{n}$ then it
contains the segment $[Le_{n-1},Le_{n}]$, by the convexity of $P$.

Finally, the“if” part of the second statement is clear since after an affine
unimodular map we may assume that $P$ contains the segment $[0,Le_{1}]$. Then,
for distinct $\alpha_{1},\dots,\alpha_{L}\in\mathbb{F}_{q}^{*}$, the
polynomial $f=(x_{1}-\alpha_{1})\cdots(x_{1}-\alpha_{L})$ is contained in
$\cal L_{P}$ and has exactly $L\,(q-1)^{n-1}$ zeros in
$(\mathbb{F}_{q}^{*})^{n}$. ∎

##  7\. Number of $\mathbb{F}_{q}$-zeros of polynomials in $\cal L_{P}$ when
$P$ has lattice width one

As we have seen in the previous section, the values of the function
$\alpha(P)$ in Theorem 6.4 are quite large. We expect that the bound (6.3)
holds for smaller values of $q$ as well, but the precise lower bound for $q$
depends on the geometry of $P$ in a non-trivial way. The reason why our
threshold is so large is because we used rather crude estimate (6.4) that
involve the degree of the $f_{i}$ and do not take into account the
combinatorics of their Newton polytopes. To the best of our knowledge, there
are no known generalizations of (6.4) (and, more generally, of (1.2)) that
estimate the number of $\mathbb{F}_{q}$-zeros of absolutely irreducible
polynomials in terms of the Newton polytope, rather than the degree, besides
the case $L(P)=1$ in [38, Th 4.30] (see Theorem 5.2) and when $P$ has lattice
width one (see Proposition 5.1). In this section we use Proposition 5.1 to
produce a better bound for $N_{P}$ than (6.3) for $P$ of lattice width one,
which holds for all $q$ starting with a much smaller threshold.

Let $P\subset\mathbb{R}^{3}$ be a lattice polytope of lattice width one. After
a unimodular transformation we may assume that
$P=\operatorname{conv}(P_{0}\times\\{0\\})\cup(P_{1}\times\\{1\\})$ for some
lattice polytopes $P_{0},P_{1}$ in $\mathbb{R}^{2}$. As in Lemma 2.4, let
$V(P_{0},P_{1})=\operatorname{Vol}_{3}(P)-\operatorname{Vol}_{2}(P_{0})-\operatorname{Vol}_{2}(P_{1})$
be the mixed volume of $P_{0}$ and $P_{1}$. Define $\beta(P)$ to be

(7.1)
$\beta(P)=\max\\{37,(C+\sqrt{C^{2}+5/2})^{2},(c+\sqrt{c^{2}+3})^{2},(V(P_{0},P_{1})+1)^{2}/4\\},$

where $C=\max_{i=0,1}\\{\operatorname{Vol}_{2}(P_{i})/4-L(P_{i})+9/4\\}$, and
$c=\min_{i=0,1}\\{\operatorname{Vol}_{2}(P_{i})/2-2L+11/2\\}$.

######  Theorem 7.1.

Let $P=\operatorname{conv}(P_{0}\times\\{0\\})\cup(P_{1}\times\\{1\\})$ be a
lattice polytope of width one and Minkowski length $L$, and let $\beta(P)$ be
as above. Then for any $q\geq\beta(P)$ we have the following bound for the
maximal number of $\mathbb{F}_{q}$-zeros over all $0\neq f\in\cal L_{P}$

(7.2) $N_{P}\leq L\,(q-1)^{2}+(q-1)(\lfloor 2\sqrt{q}\rfloor-1).$

###### Proof.

In the proof we make extensive use of the bounds proved in [32]. The reader
should keep in mind that even when a Laurent polynomial depends on $x,y$ only,
we are still interested in its zeros in $(\mathbb{F}_{q}^{*})^{3}$. This is
why the bounds from [32] are multiplied by a factor of $(q-1)$ in the
arguments below.

Consider $0\neq f\in\cal L_{P}$. First, assume that $f\in\mathbb{F}_{q}[x^{\pm
1},y^{\pm 1}]$. Then, applying to $P_{0}$ Theorem 2.6, part (1) in [32], we
obtain

$N_{f}\leq L\,(q-1)^{2}+(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$

for all $q\geq\beta(P)$. Here we used $L(P_{0})\leq L$ and the fact that
$\beta(P)$ is larger than the threshold that appears in [32, Th 2.6 (1)]. The
case when $f=hz$ for some $h\in\mathbb{F}_{q}[x^{\pm 1},y^{\pm 1}]$ is
analogous, with $P_{0}$ replaced by $P_{1}$.

It remains to consider the case when $f=f_{0}+f_{1}z$ for non-zero
$f_{0},f_{1}\in\mathbb{F}_{q}[x^{\pm 1},y^{\pm 1}]$. We write $f=gh$ where
$g=g_{0}+g_{1}z$ is absolutely irreducible and
$g_{0},g_{1},h\in\mathbb{F}_{q}[x^{\pm 1},y^{\pm 1}]$ are non-zero. As the
Newton polytope $P_{g}$ is of positive dimension, we have

$L(P)\geq L(P_{f})=L(P_{g}+P_{h})\geq L(P_{g})+L(P_{h})\geq 1+L(P_{h})$

and, hence, $L(P_{h})\leq L-1$. We have two cases: (a) $L(P_{h})=L-1$ and (b)
$L(P_{h})\leq L-2$.

(a) Assume $L(P_{h})=L-1$ and, hence, $L(P_{g})=1$. Suppose there is a maximal
decomposition in $P_{h}$ which contains a summand with 4 lattice points (i.e.
is equivalent to $T_{0}$). By adding $P_{g}$ we obtain a maximal decomposition
in $P$. Then Corollary 3.10 implies that $P_{g}$ has at most 3 lattice points
and, hence, $N_{g}\leq(q-1)^{2}$, see Proposition 5.6. On the other hand,
applying [32, Th 2.6 (1)] to $P_{h}$, we obtain

$N_{h}\leq(L-1)\,(q-1)^{2}+(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$

for all $q\geq\beta(P)$. Here $L(P_{h})=L-1$ and $\beta(P)$ is greater than
the threshold in [32, Th 2.6 (1)] since $P_{g_{i}h}\subseteq P_{i}$ and so the
area of $P_{h}$ cannot exceed the area of each $P_{i}$, for $i=0,1$. Combining
the above two inequalities, we get

$N_{f}\leq N_{g}+N_{h}\leq L\,(q-1)^{2}+(q-1)(\lfloor 2\sqrt{q}\rfloor-1),$

for $q\geq\beta(P)$.

Now suppose there is no maximal decomposition in $P_{h}$ which contains a
summand with 4 lattice points. Then by [32, Th 2.6 (2)] applied to $P_{h}$ we
have $N_{h}\leq(L-1)(q-1)^{2}$ for $q\geq\beta(P)$. To bound $N_{g}$ we use
Proposition 5.1 (note that $g_{0}$ and $g_{1}$ do not have common factors, as
$g$ is irreducible):

$N_{g}\leq(q-1)^{2}+V(P_{g_{0}},P_{g_{1}})q.$

By picking a point $v\in P_{h}$ we see that $P_{g_{i}}+v\subseteq
P_{g_{i}h}\subseteq P_{i}$, for $i=0,1$. Thus, by monotonicity and invariance
of the mixed volume (see Section 2.4) we have

$V(P_{g_{0}},P_{g_{1}})=V(P_{g_{0}}+v,P_{g_{1}}+v)\leq V(P_{0},P_{1}).$

Combining, we obtain

$N_{f}\leq N_{g}+N_{h}\leq L\,(q-1)^{2}+V(P_{0},P_{1})q.$

Since $\beta(P)\geq(V(P_{0},P_{1})+1)^{2}/4$, we see that the right hand side
of the above inequality is no greater than $L\,(q-1)^{2}+(q-1)(\lfloor
2\sqrt{q}\rfloor-1)$ for $q\geq\beta(P)$, as required.

(b) Assume $L(P_{h})\leq L-2$. We mimic the proof of [32, Th 2.6] to show

(7.3) $N_{h}\leq(L-1)(q-1)^{2},\quad\text{for }\ q\geq\beta(P).$

Then, repeating the argument at the end of case (a), we get the required
bound.

Let $h=h_{1}\cdots h_{k}$ be a factorization into absolutely irreducible
factors. Note that $k\leq L-2$. First assume that none of the $P_{h_{i}}$ has
interior lattice points. Then each $P_{h_{i}}$ either has lattice width one
(as a polytope in $\mathbb{R}^{2}$) or is equivalent to $2\Delta^{2}$. In the
former case $N_{h_{i}}\leq(q-1)^{2}$ and in the latter case
$N_{h_{i}}\leq(q+1)(q-1)$, see [32, Cor 2.2]. Let $s$ be the number of
$P_{h_{i}}$ equivalent to $2\Delta^{2}$. We have

$L-2\geq L(P_{h})\geq\sum_{i=1}^{k}L(P_{h_{i}})\geq 2s+(k-s)=k+s.$

Then

$\displaystyle N_{h}\leq\sum_{i=1}^{k}N_{h_{i}}$ $\displaystyle\leq
s(q+1)(q-1)+(k-s)(q-1)^{2}=\left(2(k+s)+k(q-3)\right)(q-1)$
$\displaystyle\leq\left(2(L-2)+(L-2)(q-3)\right)(q-1)=(L-2)(q-1)^{2}.$

Now assume that at least one $P_{h_{i}}$ has interior lattice points. Then, by
[32, Lem 2.7], we have

$N_{h}\leq k(q-1)^{2}+(B\sqrt{q}+2)(q-1),$

where $B=\operatorname{Vol}_{2}(P_{h})-4k+3$. As before, the area of $P_{h}$
is no greater than the area of $P_{i}$, for $i=0,1$, so we may replace
$\operatorname{Vol}_{2}(P_{h})$ in $B$ with the smaller of the
$\operatorname{Vol}_{2}(P_{i})$. To ensure that

$k(q-1)^{2}+(B\sqrt{q}+2)(q-1)\leq(L-1)(q-1)^{2}$

we must choose $q$ large enough to satisfy

$(L-k-1)q-B\sqrt{q}-(L-k+1)\geq 0,$

which is a quadratic inequality in $\sqrt{q}$. Arguments similar to the ones
in the proof of Theorem 2.6, part (1) in [32] show that it suffices to choose
$q\geq\max\\{37,(c+\sqrt{c^{2}+3})^{2}\\}$, where
$c=\min_{i=0,1}\\{\operatorname{Vol}_{2}(P_{i})/2-2L+11/2\\}$.

∎

######  Example 7.2.

Let $P=T_{0}+D$, where $D=[0,e_{1},e_{3}]$. This is a polytope of lattice
width one as in Theorem 7.1, with $P_{0}=T_{0}+I$ and $P_{1}=T_{0}$, where
$I=[0,e_{1}]$, see Figure 7.1.

Figure 7.1. Lattice polytope of width one with $L(P)=2$

It is easy to check that $L(P)=L(P_{0})=2$ and $L(P_{1})=1$. Also,
$\operatorname{Vol}_{3}(P)=15$, $\operatorname{Vol}_{2}(P_{0})=7$,
$\operatorname{Vol}_{2}(P_{1})=3$, and so $V(P_{0},P_{1})=5$. Theorem 7.1
provides

(7.4) $N_{P}\leq 2(q-1)^{2}+(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$

for all $q\geq 107$. In fact, this bound holds for all $q\geq 5$. Indeed,
since $L(P)=2$, any non-zero $f\in\cal L_{P}$ is either absolutely irreducible
or is a product of two absolutely irreducible factors. In the first case
$N_{f}\leq(q-1)^{2}+5q$, by Proposition 5.1 and monotonicity of the mixed
volume. In the second case, at most one of the factors, say $f_{1}$, has 4 or
more monomials. Then $N_{f_{2}}\leq(q-1)^{2}$. If $P_{f_{1}}$ is equivalent to
$T_{0}$ then $N_{f_{1}}\leq(q-1)^{2}+(q-1)(\lfloor 2\sqrt{q}\rfloor-1)$ and so

$N_{f}\leq N_{f_{1}}+N_{f_{2}}\leq 2(q-1)^{2}+(q-1)(\lfloor
2\sqrt{q}\rfloor-1)$

for all $q\geq 2$. Otherwise, $P_{f_{1}}$ has width one. Note that the top
face of $P_{f_{1}}$ must be a vertex, otherwise $P_{1}$ would contain a sum of
two segments which contradicts $L(P_{1})=1$. But then the mixed volume of the
top and the bottom faces of $P_{f_{1}}$ is zero and Proposition 5.1 produces
$N_{f_{1}}\leq(q-1)^{2}$. Thus,

$N_{f}\leq N_{f_{1}}+N_{f_{2}}\leq 2(q-1)^{2}.$

It remains to notice that $(q-1)^{2}+5q\leq 2(q-1)^{2}+(q-1)(\lfloor
2\sqrt{q}\rfloor-1)$ for all $q\geq 5$. We used Magma to compare this bound
with the actual values of $N_{P}$ for $5\leq q\leq 11$:

$q\ \ $ | $\ \ 5\ \ $ | $\ \ 7\ \ $ | $\ \ 8\ \ $ | $\ \ 9\ \ $ | $\ 11\ $
---|---|---|---|---|---
$N_{P}\ $ | 40 | 90 | 112 | 160 | 250
bound in (7.4) | 44 | 96 | 126 | 168 | 250

In particular, this shows that the bound in (7.4) is sharp.

##  8\. Examples of toric 3-fold codes of dimension 8 over small fields

In this section we consider toric 3-fold codes defined by polytopes with
$L(P)=1$ which have 8 lattice points and lattice width greater than one.
Recall that a linear code $\cal C$ is an $[n,k,d]_{q}$-code if it is defined
over $\mathbb{F}_{q}$, has length $n$, dimension $k$, and minimum distance
$d$. For a toric 3-fold code $\cal C_{P}$ we have $n=(q-1)^{3}$, $k=|P|$, and
$d=n-N_{P}$, see Section 1.2.

Since our bound in Corollary 1.6 depends on $L(P)$ and not $k=|P|$, it is
reasonable to look for good toric codes among the ones whose polytope $P$ has
the largest possible value of $|P|$ for fixed $L(P)$. By (2.1), $|P|=8$ is the
largest possible number of lattice points for 3-dimensional polytopes with
$L(P)=1$. According to the classification in [6, 38], there are exactly five
lattice polytopes with $L(P)=1$, $|P|=8$, and width greater than one, up to
$\operatorname{AGL}(3,\mathbb{Z})$-equivalence. Using Magma, we computed the
parameters of all five toric $3$-fold codes over $5\leq q\leq 13$. For
$q=5,7,8,11,13$ the best parameters are produced by a clean lattice simplex
with four interior lattice points, $P=\left[\begin{matrix}0&1&0&6\\\
0&0&1&8\\\ 0&0&0&35\end{matrix}\right]$. For $q=9$ the best parameters are
produced by a 5-vertex polytope with three interior lattice points,
$Q=\left[\begin{matrix}0&1&0&0&2\\\ 0&0&0&1&15\\\
0&1&1&1&28\end{matrix}\right]$. Although $P$ and $Q$ do not lie in
$[0,q-2]^{3}$ for $5\leq q\leq 13$, one can check that their lattice points
are distinct modulo $(\mathbb{Z}/(q-1)\mathbb{Z})^{3}$.

One feature of toric 3-fold codes is that the length $n$ grows very quickly
and already starting with $q=7$ their parameters fall outside of the ranges
set in linear code tables such as MinT and Grassl’s table [14, 29]. Thus, we
compare the parameters of $\cal C_{P}$ and $\cal C_{Q}$ with the Griesmer and
the Gilbert-Varshamov bounds. Recall that the Griesmer bound states that for
any linear $[n,k,d]_{q}$-code $n\geq\sum_{i=0}^{k-1}\lceil d/q^{i}\rceil$ and,
hence, provides an upper bound on $d$ when $k$ and $n$ are fixed, [35, Th
1.1.43]. The Gilbert-Varshamov bound asserts that if

(8.1) $q^{n-k}>\sum_{i=0}^{d-2}{n-1\choose i}(q-1)^{i}$

then there exists a linear $[n,k,d]_{q}$-code [35, Th 1.1.59]. Therefore, it
is desirable to find linear codes whose minimum distance exceeds the largest
value of $d$ which satisfies (8.1) with fixed $n$ and $k$. We have the
following table of values of $d$ for $\cal C_{P}$ and $\cal C_{Q}$ for $5\leq
q\leq 13$.

$q\ \ $ | $\ \ 5\ \ $ | $\ \ 7\ \ $ | $\ \ 8\ \ $ | $\ \ 9\ \ $ | $\ 11\ $ | $\ 13\ $
---|---|---|---|---|---|---
Griesmer upper bound | 47 | 181 | 296 | 451 | 904 | 1590
$d(\cal C_{P})\ $ | 36 | 162 | 252 | 392 | 861 | 1535
$d(\cal C_{Q})\ $ | 36 | 150 | 252 | 416 | 850 | 1512
Glibert-Varshamov lower bound | 37 | 159 | 268 | 416 | 857 | 1519

Although for $q=5$ the resulting codes have minimum distance far from the best
known $[64,8,42]_{5}$-code in [14], for $q=9$ the minimum distance of $\cal
C_{Q}$ (in purple) meets the Gilbert-Varshamov bound and for $q=7,11,13$ the
minimum distance of $\cal C_{P}$ (in red) exceeds the Gilbert-Varshamov bound.

## References

  * [1] Yves Aubry and Marc Perret, A Weil theorem for singular curves, Arithmetic, geometry and coding theory (Luminy, 1993) de Gruyter, Berlin, 1996, pp. 1–7.
  * [2] Alexander Barvinok, _A course in convexity_ Graduate Studies in Mathematics, 54. American Mathematical Society, Providence, RI, 2002.
  * [3] O. Beckwith, M. Grimm, J. Soprunova, B. Weaver, Minkowski length of 3D lattice polytopes, Discrete and Computational Geometry 48, Issue 4 (2012), 1137–1158.
  * [4] D. N. Bernstein, The number of roots of a system of equations, Funct. Anal. and Appl. 9 (2), (1975) 183–185.
  * [5] M. Blanco, F. Santos, _Lattice 3-Polytopes With Six Lattice Points_ , SIAM J. Discrete Math., 30(2), 687–717 (2016).
  * [6] M. Blanco, F. Santos, _Enumeration of Lattice 3-Polytopes by Their Number of Lattice Points_ , Discrete Comput. Geom. 60, 756-800 (2018)
  * [7] Mahir Bilen Can, Takayuki Hibi, Toric Codes from Order Polytopes, Discrete Comput Geom (2021). https://doi.org/10.1007/s00454-021-00329-w
  * [8] Bosma, Wieb, Cannon, John, Playoust, Catherine, 1997. The Magma algebra system. I. The user language. J. Symbolic Comput., 24, 235–265.
  * [9] Gavin Brown, Alexander M. Kasprzyk, Small polygons and toric codes, Journal of Symbolic Computation, Vol. 51, April (2013), pp. 55–62.
  * [10] Gavin Brown, Alexander M. Kasprzyk, Seven new champion linear codes, LMS Journal of Computation and Mathematics, Vol. 16 (2013), pp. 109–117.
  * [11] M. D. Choi, T. Y. Lam, B. Reznick, Lattice polytopes with distinct pair-sums, Discrete Comput. Geom. 27 (2002), no. 1, 65–72.
  * [12] David A. Cox, John B. Little, and Henry K. Schenck, Toric Varieties. Graduate Studies in Mathematics, 124. American Mathematical Society, Providence, RI, 2011
  * [13] Sudhir Ghorpade, Gilles Lachaud, Étale cohomology, Lefschetz theorems and number of points of singular varieties over finite fields. Mosc. Math. J. 2 (2002), no. 3, 589–631.
  * [14] Markus Grassl, Bounds on the minimum distance of linear codes and quantum codes, online available at http://www.codetables.de/. Accessed on 2022-01-13.
  * [15] J. Hansen, Toric Surfaces and Error–correcting Codes in Coding Theory, Cryptography, and Related Areas, Springer (2000), pp. 132-142.
  * [16] J. Hansen, Toric varieties Hirzebruch surfaces and error-correcting codes, Appl. Algebra Engrg. Comm. Comput. 13 (2002), pp. 289–300
  * [17] D. Joyner, Toric codes over finite fields, Appl. Algebra Engrg. Comm. Comput., 15 (2004), pp. 63–79.
  * [18] Alexander M. Kasprzyk, _Toric Fano three-folds with terminal singularities_ , Tohoku Math. J. (2) 58 (2006), no. 1, 101-121.
  * [19] A. G. Khovanskii, Newton polyhedra and the genus of complete intersections, Funct. Anal. Appl., 12 (1978), pp. 38–46.
  * [20] James Lee Kimball, Bounds on codes from smooth toric threefolds with ${\rm rank}({\rm Pic}(X))=2$, Thesis (Ph.D.) Texas A&M University. 2008.
  * [21] A. G. Kushnirenko, Newton polyhedra and Bezout’s theorem (Russian) Funkcional. Anal. i Prilozhen. 10, no. 3, (1976) 82–83.
  * [22] Serge Lang, André Weil, Number of points of varieties in finite fields. Amer. J. Math. 76 (1954), 819–827
  * [23] J. Little, H. Schenck, Toric surface codes and Minkowski sums, SIAM J. Discrete Math. 20 (2006), no. 4, 999–1014 (electronic).
  * [24] J. Little, R. Schwarz, On toric codes and multivariate Vandermonde matrices, Appl. Algebra Engrg. Comm. Comput. 18 (4) (2007), pp. 349–367.
  * [25] John B. Little, Remarks on generalized toric codes, Finite Fields and Their Applications, Volume 24, November (2013), pp. 1–14.
  * [26] H. Minkowski, Theorie der konvexen Körpern, insbesonder der Begründung ihres Oberflächenbegriffs. Gesammelte Abhandlungen, 2, Teubner (1911) pp. 131–229.
  * [27] Diego Ruano, On the parameters of $r$-dimensional toric codes, Finite Fields and Their Applications 13 (2007), pp. 962–976.
  * [28] Herbert E. Scarf, _Integral polyhedra in three space_ , Mathematics of Operations Research 10, no. 3, (1985) pp. 403–438
  * [29] Wolfgang Ch. Schmid and Rudolf Schürer, The MinT project, online available at http://mint.sbg.ac.at, Accessed on 2022-01-13.
  * [30] Rolf Schneider, Convex bodies: the Brunn-Minkowski theory, Second expanded edition. Encyclopedia of Mathematics and its Applications, 151. Cambridge University Press, Cambridge, 2014
  * [31] I. Soprunov, Lattice polytopes in coding theory, J. Algebra Comb. Discrete Struct. Appl. 2 (2015), no. 2, 85–94.
  * [32] I. Soprunov and J. Soprunova, _Toric surface codes and Minkowski length of polygons_ , SIAM J. Discrete Math. 23 (2008/09), no. 1, 384-400.
  * [33] I. Soprunov, J. Soprunova, Bringing Toric Codes to the next dimension, SIAM J. Discrete Math. 24, Issue 2, (2010) pp. 655-665
  * [34] I. Soprunov, J. Soprunova, Eventual quasi-linearity of the Minkowski length, European Journal of Combinatorics 58 (2016), pp 107-117
  * [35] M. A. Tsfasman, S. Vlăduţ, Th. Zink, Modular curves, Shimura curves, and Goppa codes, better than Varshamov - Gilbert bound, Math. Nachr. 109 (1982), 21–28.
  * [36] V. Gauthier Umana, M. Velasco Dual toric codes and polytopes of degree one, SIAM J. Discrete Math. 29 (2015), no. 1, 683–692.
  * [37] G. White, _Lattice tetrahedra_ , Canadian J. Math. 16, 389-396, (1964).
  * [38] Josh Whitney, A bound on the minimum distance of three dimensional toric codes, Thesis (Ph.D.), University of California, Irvine, 2010