(corresponding to the scalable case) to $10$. For the case with preprocessing,
we consider the sum of the iterations needed for the Sinkhorn-like method
described in Algorithm 1 to find the support $\mathcal{S}$, and of the ones
needed for the Sinkhorn algorithm then applied to the problem
$\operatorname{Sch}(\mathds{1}_{\mathcal{S}}R;\mu,\nu)$. We observe that the
preprocessing makes the number of iterations needed for the convergence to be
significantly smaller than for the case without preprocessing when the number
of additional zero entries is high. It is also smaller than for the case when
the naive approximate method is applied, illustrating the benefit of our
approach.

Figure 5: Number of iterations needed for convergence _vs._ number of
additional zero entries of the limits $P^{*}$ and $Q^{*}$ from Theorem 11
w.r.t. $R$, using: the Sinkhorn algorithm (2) (solid line); the Sinkhorn
algorithm where at each step, the entries below the threshold (46) are set to
zero (dashed line); Algorithm 1 to compute the support $\mathcal{S}$ of the
limits, and then the Sinkhorn algorithm replacing $R$ by
$\mathds{1}_{\mathcal{S}}R$ (dotted line). When the threshold $\varepsilon$ is
small enough, as it is the case here, these three methods provide the same
limits.

###  6.3 Comparison of the method with the balanced and unbalanced Sinkhorn
algorithms

We compared in Figure 6 the outputs of the Sinkhorn algorithm when the problem
$\operatorname{Sch}(R;\mu,\nu)$ is non-scalable, given by the geometric mean
described in Theorem 17, and two alternatives:

  * •

When the reference coupling $R$ is modified such that it has only positive
entries. For that, we built a new coupling $R_{\varepsilon}$ by adding on
every zero entry of $R$ a small quantity $\varepsilon$. We then found the
optimizers $R^{*}_{\varepsilon}$ of the Schrödinger problems
$\operatorname{Sch}(R_{\varepsilon};\mu,\nu)$ and compared its distance in
total variation of its solution to $R^{*}$, for different values of
$\varepsilon$.

  * •

When we the marginal constraints are replaced by marginal penalizations,
leading to an unbalanced problem of the form (21), using the scaling algorithm
described in [6]. We then compared the distance in total variation of its
solution to $R^{*}$, for different values of $\lambda$.

For the comparison realized here, we took a coupling $R$ of size $100\times
100$ and $R,\mu,\nu$ as in Figure 4 in such a way that $R^{*}$ has only two
blocks $A_{1}\times B_{1}$ and $A_{2}\times B_{2}$ for which the factor
$\lambda$ appearing in the procedure of Proposition 28 is greater than one for
the first component, and smaller for the second one. The problem is thus non-
scalable. As expected, we observe in Figure 6(a) that in the first case it is
impossible for the solution $R^{*}_{\varepsilon}$ of
$\operatorname{Sch}(R_{\varepsilon};\mu,\nu)$ to be close to $R^{*}$ (and then
to recover the right minimum entropy), and that the faster is the convergence,
the further $R^{*}_{\varepsilon}$ is from $R^{*}$. In the second case, we
observe in Figure 6(b) that the solution $R^{*}_{\lambda}$ of the unbalanced
problem with penalization $\lambda$ converges to $R^{*}$ when
$\lambda\to\infty$. However, the convergence goes faster only for values of
$\lambda$ smaller than $150$, for which we still observe a significant
difference between $R^{*}$ and $R^{*}_{\lambda}$.

Note that these results are not limited to Schrödinger problems similar to the
one described in Figure 4, and that we observed the same type of results for
randomly-generated $R$, $\mu$ and $\nu$ in non-scalable cases.

(a)

(b)

Figure 6: Comparison of the outputs of the Sinkhorn algorithm in a non-
scalable case, where $R^{*}$ is given by Theorem 17, and: 6(a) the Sinkhorn
algorithm (2) where the zero entries of $R$ are replaced by a small value
$\varepsilon$; 6(b) the unbalanced Sinkhorn algorithm from [6] applied to
solve $\textrm{Schu}_{\lambda}(R;\mu,\nu)$ for large values of $\lambda$.

## Acknowledgments

This work was supported by funding from French agency ANR (SingleStatOmics;
ANR-18-CE45-0023-03). We would like to thank Olivier Gandrillon, Thibault
Espinasse and Thomas Lepoutre for enlightening discussions, and the latter and
Gauthier Clerc for critical reading of the manuscript. We finally thank the
BioSyL Federation, the LabEx Ecofect (ANR-11-LABX-0048) and the LabEx Milyon
of the University of Lyon for inspiring scientific events.

##  Appendix A Example of Schrödinger problems without solutions

There exists a lot of degenerate cases where the problem
$\operatorname{Sch}(R;\mu,\nu)$ has no solution. Indeed, in the extreme
situation where most of the entries of $R$ cancel, two randomly chosen vectors
$\mu$ and $\nu$ have more chance to be non-scalable than to satisfy the
conditions of Theorem 23. For example, in the typical example of a squared
diagonal reference coupling $R$, we must necessarily have $\mu=\nu$ for these
conditions to be satisfied.

When illustrating our results at Sections 5 and 6, we chose $R$ to be a
squared upper-diagonal matrix (see Figure 4). This is of particular interest,
as it corresponds to a case that typically arises when considering entropy
minimization problems in cell biology. Indeed, the dynamics of mRNA levels
within a cell, which drives cellular differentiation processes, is often
modeled by a piecewise deterministic Markov process, where stochastic bursts
of mRNAs compensate their deterministic degradation [32, 33]. Considering the
simplest cartoonish but enlightening situation where there is no degradation,
a constant number of cells, and where we measure the activity of only one
gene, the quantity of mRNAs in the cells corresponding to this gene can only
increase with time. Therefore, if $R$ is the matrix whose entry $R_{ij}$ gives
the number of cells having $i$ molecules of mRNA at a first timepoint and $j$
molecules at a later timepoint, $R$ must be upper-diagonal.

To give an insight of the behaviour of the Sinkhorn algorithm in the non-
scalable case with an upper-diagonal reference matrix, let us treat explicitly
a simple example. We consider:

$R=\begin{pmatrix}1&1&1\\\ 0&1&1\\\
0&0&1\end{pmatrix},\quad\mu=(2,2,2),\quad\nu=(2,3,1).$

In this example, $\mu_{3}>\nu_{3}$ while the image of $x_{3}$ by the graph
associated to $R$ is reduced to $y_{3}$, that is, with the formalism of
Section 5, $F_{R}(\\{x_{3}\\})=\\{y_{3}\\}$ and hence
$\nu(F_{R}(\\{x_{3}\\})<\mu(\\{x_{3}\\})$. In view of Theorem 23 (which is
very easy to check in our simple situation), the problem is therefore indeed
non-scalable: no matrix can satisfy the marginal constraints and be absolutely
continuous w.r.t $R$ at the same time.

With the notations of (2), let us reproduce below the output of the Sinkhorn
algorithm at some of the first iterations. Starting at Iteration 5, we only
give approximate numerical values.

Iteration 1:

$a^{1}=(2/3,1,2),\quad b^{0}=(1,1,1),\quad P^{1}=\begin{pmatrix}2/3&2/3&2/3\\\
0&1&1\\\ 0&0&2\end{pmatrix}.$

Iteration 2:

$a^{1}=(2/3,1,2),\quad b^{1}=(3,9/5,3/11),\quad
Q^{1}=\begin{pmatrix}2&6/5&2/11\\\ 0&9/5&3/11\\\ 0&0&6/11\end{pmatrix}.$

Iteration 5:

$a^{3}=(2.7e^{-1},8.6e^{-1},1.7e^{1}),\quad b^{2}=(5.0,2.2,1.2e^{-1}),\quad
P^{3}=\begin{pmatrix}1.4&0.59&3.2e^{-2}\\\ 0&1.9&1.0e^{-1}\\\
0&0&2.0\end{pmatrix}.$

Iteration 11:

$a^{6}=(1.2e^{-1},5.1e^{-1},1.5e^{2}),\quad
b^{5}=(1.3e^{1},3.9,1.3e^{-2}),\quad
P^{6}=\begin{pmatrix}1.55&0.45&1.5e^{-3}\\\ 0&2.0&6.6e^{-3}\\\
0&0&2.0\end{pmatrix}.$

Iteration 80:

$a^{40}=(5.5e^{-5},2.8e^{-4},2.7e^{12}),\quad
b^{40}=(3.6e^{4},9.1e^{3},3.8e^{-13}),\quad
Q^{40}=\begin{pmatrix}2.0&0.50&1.7e^{-17}\\\ 0&2.5&8.4e^{-16}\\\
0&0&1.0\end{pmatrix}.$

Iteration 81:

$a^{41}=(4.4e^{-5},2.2e^{-4},5.3e^{12}),\quad
b^{40}=(3.6e^{4},9.1e^{3},3.8e^{-13}),\quad
P^{40}=\begin{pmatrix}1.6&0.40&4.2e^{-17}\\\ 0&2.0&2.1e^{-16}\\\
0&0&2.0\end{pmatrix}.$

Of course, in this case, the matrices $P^{*}$, $Q^{*}$, $R^{*}$ from Theorem
11, 17 are given by

$P^{*}=\begin{pmatrix}8/5&2/5&0\\\ 0&2&0\\\ 0&0&2\end{pmatrix},\quad
Q^{*}=\begin{pmatrix}2&1/2&0\\\ 0&5/2&0\\\ 0&0&1\end{pmatrix},\quad
R^{*}=\begin{pmatrix}4/\sqrt{5}&1/\sqrt{5}&0\\\ 0&\sqrt{5}&0\\\
0&0&\sqrt{2}\end{pmatrix}.$

Finally, to get $\bar{R}{}^{*}$ from Theorem 22, it suffices to normalize
$R^{*}$.

This very simple example illustrates the different points developed in this
article:

  * •

When $R$ does not have only positive entries, the limits of the sequences
$(P^{n})$ and $(Q^{n})$ given by the Sinkhorn algorithm may be different and
have more zero entries than $R$;

  * •

Because new zero entries appear, the potentials $(a^{n})$ and $(b^{n})$ that
are updated at each iteration of the Sinkhorn algorithm cannot converge: some
of their coordinates have to tend to $0$ and then some other ones need to
diverge to $+\infty$ as the number of iterations increases;

  * •

More precisely, for $(i,j)$ on the common support of $P^{*}$ and $Q^{*}$ from
Theorem 11, the infinitely small and high values of the two potentials are
compensated. For $(i,j)$ outside of this common support, but still in the one
of $R$, the multiplication of the two potentials generate infinitely small
values. Outside of the support of $R$, the multiplication of the potentials
can diverge. Also, the zero entries of $R$ prevent the sums involved in the
computations of $(a^{n})$ and $(b^{n})$ to diverge: the large values of the
potentials are sent to zero in the multiplication with $R$;

  * •

When the problem is non-scalable, the algorithm still converges to two limits
and the algorithm alternates between them. These two limits correspond to
solutions of the Schrödinger problem with modified marginals, that is with
modified $\mu$ or modified $\nu$ alternatively (see the iterations 80 and 81).

Going back to the context of the beginning of the section, where the upper-
diagonal $R$ models the evolution of the quantity of mRNAs corresponding to
one gene in a population of cells between two timepoints, we see that the non-
scalable case appears when there exists a threshold such that more cells with
less mRNAs than the threshold are measured at the second timepoint than at the
first one, which is incompatible with the model where the quantity of mRNAs
can only increase. If we believe enough in our model, it is natural to look
for a solution with modified marginals – like for instance the law
$\bar{R}^{*}$ described in Theorem 22 – and to advocate for a bad sampling or
imprecise measurements when collecting data.

If we consider that such incompatibilities between the theoretical model $R$
and the observations $\mu$ and $\nu$ should be rare, this law $\bar{R}^{*}$ is
a natural choice since among all the solutions of a Schrödinger problem w.r.t.
$R$, it is the one whose marginals are the closest (in a specific entropic
sense) to the experimental ones.

##  Appendix B Proof of Theorem 23

In this section, we prove Lemma 24 and then Theorem 23. The following
classical proposition will be used in the proof of Lemma 24:

######  Proposition 36.

Let $R\in\mathcal{M}_{+}(\mathcal{D}\times\mathcal{F})$,
$\mu\in\mathcal{M}_{+}(\mathcal{D})$ and $\nu\in\mathcal{M}_{+}(\mathcal{F})$
be such that the problem $\operatorname{Sch}(R;\mu,\nu)$ admits a solution
$R^{*}$. Then for all $P\in\Pi(\mu,\nu)$ such that $P\ll R$, we necessarily
have $P\ll R^{*}$.

###### Proof of Proposition 36.

Let $P\in\Pi(\mu,\nu)$ be such that $P\ll R$. For all $\varepsilon>0$,
$P^{\varepsilon}:=(1-\varepsilon)R^{*}+\varepsilon P$ is a competitor for
$\operatorname{Sch}(R;\mu,\nu)$, so that by minimality of $R^{*}$,
$H(P^{\varepsilon}|R)\geq H(R^{*}|R)$. But because $s\mapsto s\log s$ is
decreasing with infinite slope near $s=0$, this is possible for $\varepsilon$
small only if $P\ll R^{*}$. ∎

Let us now prove Lemma 24.

###### Proof of Lemma 24.

In Lemma 24, we are looking for necessary and sufficient conditions for
$\operatorname{Sch}(R;\mu,\nu)$ to be scalable. As
$\mathsf{M}(\mu)=\mathsf{M}(\nu)$ is clearly a necessary condition because of
Remark 2, we assume once for all that it is true. Up to normalizing, we assume
that $\mu\in\mathcal{P}(\mathcal{D})$ and $\nu\in\mathcal{P}(\mathcal{F})$.

In order to clarify what (a’) and (b’) mean, we start by considering the case
where the reference matrix $R$ is such that the graph
$(\mathcal{D}\cup\mathcal{F},\triangle)$ is connected. In that case, recalling
that $\mu$ and $\nu$ are assumed to be probability measures, the conditions
(a’) and (b’) are equivalent to:

  1. (a”)

The measures $\mu$ and $\nu$ have full support, and for all
$\emptyset\subsetneq A\subsetneq\mathcal{D}$, $\mu(A)<\nu(F_{R}(A))$,

  2. (b”)

The measures $\mu$ and $\nu$ have full support, and for all
$\emptyset\subsetneq B\subsetneq\mathcal{F}$, $\nu(B)<\mu(D_{R}(B))$.

Indeed, it is easy to see that in the balanced and connected case, the only
subsets $A$ of $\mathcal{D}$ for which $\mu^{R}(A)=\nu^{R}(F_{R}(A))$ are
$A=\emptyset$ and $A=\mathcal{D}$. Similarly, the only subsets $B$ of
$\mathcal{F}$ for which $\nu^{R}(B)=\mu^{R}(D_{R}(B))$ are $B=\emptyset$ and
$B=\mathcal{F}$.

We are going to prove Lemma 24 under this connectivity assumption. Passing to
the general case is direct, up to restricting ourselves to connected
components of $(\mathcal{D}\cup\mathcal{F},\triangle)$.

We only prove (b”)$\Leftrightarrow$(c’), as (a”)$\Leftrightarrow$(c’) is
proved in the same way. The idea of the proof is to fix
$\mu\in\mathcal{P}(\mathcal{D})$ of full support, that is, such that for all
$i=1,\dots,N$, $\mu_{i}>0$, and to introduce the two following subsets of
$\mathcal{P}(\mathcal{F})$:

$\displaystyle\mathfrak{A}:=\\{\nu\in\mathcal{P}(\mathcal{F})\,|\,\forall\emptyset\subsetneq
B\subsetneq\mathcal{D},\,\nu(B)<\mu(D_{R}(B))\mbox{ and }\forall
j=1,\dots,M,\,\nu_{j}>0\\},$
$\displaystyle\mathfrak{B}:=\\{\nu:=\nu^{\bar{R}}\,|\,\bar{R}\sim R\mbox{ and
}\mu^{\bar{R}}=\mu\\}.$

With these definitions, proving (b”)$\Leftrightarrow$(c’) exactly means
proving

$\mathfrak{A}=\mathfrak{B},$

and this is what we will prove now. To do so, we will first show that
$\mathfrak{B}\subset\mathfrak{A}$, and then that $\mathfrak{B}$ is open and
closed in $\mathfrak{A}$. As $\mathfrak{A}$ is convex, and hence connected,
the result will follow.

Step 1: $\mathfrak{B}\subset\mathfrak{A}$.

Let us show that $\mathfrak{B}\subset\mathfrak{A}$. To this end, let us
consider $\nu\in\mathfrak{B}$, and $\bar{R}$ such that $R\in\Pi(\mu,\nu)$ and
$\bar{R}\sim R$. For all $\emptyset\subsetneq B\subsetneq\mathcal{D}$ we have:

$\nu(B)=\sum\limits_{x_{i}\in\mathcal{D}}\sum_{y_{j}\in
B}\bar{R}_{ij}=\sum_{x_{i}\in D_{R}(B)}\sum_{y_{j}\in
B}\bar{R}_{ij}\leq\sum_{x_{i}\in
D_{R}(B)}\sum_{y_{j}\in\mathcal{F}}\bar{R}_{ij}=\mu(D_{R}(B)),$

and the equality holds only if for all $(x_{i},y_{j})\in D_{R}(B)\times
B^{c}$, $\bar{R}_{ij}=0$ and hence $R_{ij}=0$. As by definition of $D_{R}(B)$,
for all $(x_{i},y_{j})\in D_{R}(B)^{c}\times B$, we have $R_{ij}=0$, an
equality in the formula above would imply that $D_{R}(B)\times B$ is not
connected to $D_{R}(B)^{c}\times B^{c}$ in
$(\mathcal{D}\times\mathcal{F},\triangle)$, which contradicts our connectivity
assumption. We have thus a strict inequality. Finally, the full support of
$\nu$ is also an consequence of the connectivity of
$(\mathcal{D}\times\mathcal{F},\triangle)$: For all $y_{j}\in\mathcal{F}$, let
$x_{i}\in\mathcal{D}$ such that $R_{ij}>0$, and hence $\bar{R}_{ij}>0$. We
have $\nu_{j}\geq\bar{R}_{ij}>0$. Thus, $\mathfrak{B}\subset\mathfrak{A}$.

Step 2: $\mathfrak{B}$ is open in $\mathfrak{A}$.

It is clear by its definition that $\mathfrak{A}$ is open in
$\mathcal{P}(\mathcal{F})$. Therefore, to prove that $\mathfrak{B}$ is open in
$\mathfrak{A}$, it suffices to prove that $\mathfrak{B}$ is open in
$\mathcal{P}(\mathcal{F})$. Let $\nu\in\mathfrak{B}$, and $\bar{R}$ be such
that $\bar{R}\sim R$ and $\nu^{\bar{R}}=\nu$. We choose:

$\displaystyle 0<\varepsilon<\min\\{\bar{R}_{ij}\,|\,i,j\mbox{ s.t.\
}\bar{R}_{ij}>0\\},$ (47)

which is possible because $\mathcal{D}$ and $\mathcal{F}$ are finite. By
convexity, it is enough to prove that for all $j\neq j^{\prime}$ in
$\\{1,\dots,M\\}$,
$\nu+\varepsilon(\delta_{j}-\delta_{j^{\prime}})\in\mathfrak{B}$. As
$(\mathcal{D}\cup\mathcal{F},\triangle)$ is connected, we can find
$j=j_{0},i_{1},j_{1},\dots,i_{p},j_{p}=j^{\prime}$ such that

$y_{j}=y_{j_{0}}\triangle x_{i_{1}}\triangle y_{j_{1}}\triangle\dots\triangle
x_{i_{p}}\triangle y_{j_{p}}=y_{j^{\prime}}.$

Then we set

$P:=\bar{R}+\varepsilon\sum_{n=1}^{p}\Big{(}\delta_{i_{n}j_{n-1}}-\delta_{i_{n}j_{n}}\Big{)}.$

It is easy to check that $P\sim R$ (by the definition (47) of $\varepsilon$),
that $\mu^{P}=\mu$, and that
$\nu^{P}=\nu+\varepsilon(\delta_{j}-\delta_{j^{\prime}})$, which therefore
belongs to $\mathfrak{B}$.

Step 3: $\mathfrak{B}$ is closed in $\mathfrak{A}$, strategy of the proof.

Let us introduce the following subset of $\mathcal{P}(\mathcal{F})$:

$\mathfrak{C}:=\\{\nu:=\nu^{\bar{R}}\,|\,\bar{R}\ll R\mbox{ and
}\mu^{\bar{R}}=\mu\\}.$

This set is clearly closed in $\mathcal{P}(\mathcal{F})$, so to prove that
$\mathfrak{B}$ is closed in $\mathfrak{A}$, it suffices to prove that
$\mathfrak{B}=\mathfrak{A}\cap\mathfrak{C}$. As we have already seen that
$\mathfrak{B}\subset\mathfrak{A}$, and as clearly
$\mathfrak{B}\subset\mathfrak{C}$, the only inclusion that needs to be
justified is $\mathfrak{A}\cap\mathfrak{C}\subset\mathfrak{B}$.

Let us choose $\nu\in\mathfrak{A}\cap\mathfrak{C}$, and let us consider
$R^{*}$ the solution of $\operatorname{Sch}(R;\mu,\nu)$. We will prove by
contradiction that $R^{*}\sim R$, and hence that $\nu\in\mathfrak{B}$.

So let us assume that $R^{*}\nsim R$. Once again, we choose
$0<\varepsilon<\min\\{R^{*}_{ij}\,|\,i,j\mbox{ s.t.\ }R^{*}_{ij}>0\\}$. For
all $i,j$, we write

$x_{i}\blacktriangle y_{j}$

whenever $R^{*}_{ij}>0$. We will first prove that
$(\mathcal{D}\cup\mathcal{F},\blacktriangle)$ is connected (this is the
hardest part of the proof), and then that it coincides with
$(\mathcal{D}\cup\mathcal{F},\triangle)$, which exactly means that $R^{*}\sim
R$.

Step 4: $(\mathcal{D}\cup\mathcal{F},\blacktriangle)$ is connected.

We call
$\mathcal{D}_{1}\cup\mathcal{F}_{1},\dots,\mathcal{D}_{p}\cup\mathcal{F}_{p}$
the connected components of $(\mathcal{D}\cup\mathcal{F},\blacktriangle)$. Let
us assume that $p>1$, and show that it leads to a contradiction.

First, we claim that if $p>1$, there exist
$k_{1},\dots,k_{l}\in\\{1,\dots,p\\}$ a family of two by two distinct indices,
$x_{i^{k_{1}}},\dots,x_{i^{k_{l}}}\in\mathcal{D}$ and
$y_{j^{k_{1}}},\dots,y_{j^{k_{l}}}\in\mathcal{F}$ such that for all
$q=1,\dots,l$, $x_{i^{k_{q}}}\in\mathcal{D}_{k_{q}}$ and
$y_{j^{k_{q}}}\in\mathcal{F}_{k_{q}}$, and with the convention $l+1=1$,
$y_{j^{k_{q}}}\triangle x_{i^{k_{q+1}}}$.

For proving this claim, we start by building a directed graph structure on
$\\{1,\dots,p\\}$, the set of indices of the connected components of
$(\mathcal{D}\cup\mathcal{F},\blacktriangle)$. For all
$k,k^{\prime}\in\\{1,\dots,p\\}$, we write $k\leadsto k^{\prime}$ whenever
$k\neq k^{\prime}$ and there exists $y_{j}\in\mathcal{F}_{k}$ and
$x_{i}\in\mathcal{D}_{k^{\prime}}$ such that $y_{j}\triangle x_{i}$. Of
course, our claim precisely means that the directed graph
$(\\{1,\dots,p\\},\leadsto)$ admits a cycle. Let us prove that for all
$k=1,\dots,p$, there exists $k^{\prime}\in\\{1,\dots,p\\}$ such that
$k\leadsto k^{\prime}$, which is clearly enough to conclude.

Let us consider $k\in\\{1,\dots,p\\}$. Because $\nu\in\mathfrak{A}$, we have
$\mu(D_{R}(\mathcal{F}_{k}))>\nu(\mathcal{F}_{k})$. On the other hand,
$\nu(\mathcal{F}_{k})=\mu(\mathcal{D}_{k})$ (as under $R^{*}$, all the mass on
$\mathcal{D}_{k}$ is sent to $\mathcal{F}_{k}$ and _vice versa_), and
$\mathcal{D}_{k}\subset D_{R}(\mathcal{F}_{k})$ (as $R^{*}\ll R$). Therefore,
$\mu(D_{R}(\mathcal{F}_{k})\backslash\mathcal{D}_{k})=\mu(D_{R}(\mathcal{F}_{k}))-\mu(\mathcal{D}_{k})>0$,
and we conclude that
$D_{R}(\mathcal{F}_{k})\backslash\mathcal{D}_{k}\neq\emptyset$. Let $x_{i}\in
D_{R}(\mathcal{F}_{k})\backslash\mathcal{D}_{k}$, and $k^{\prime}$ such that
$x_{i}\in\mathcal{D}_{k^{\prime}}$. As $x_{i}\in D_{R}(\mathcal{F}_{k})$,
there is $y_{j}\in\mathcal{F}_{k}$ such that $y_{j}\triangle x_{i}$. It
follows that $k\leadsto k^{\prime}$, and the claim is proved, and we can
consider $k_{1},\dots,k_{l}$ satisfying the properties above.

We now show that we reach a contradiction, which allows to conclude that
actually, $p$ must be equal to $1$ and hence that
$(\mathcal{D}\cup\mathcal{F},\blacktriangle)$ needs to be connected.

For all $q=1,\dots,l$, as
$(\mathcal{D}_{k_{q}}\cup\mathcal{F}_{k_{q}},\blacktriangle)$ is connected, we
can find a family of indices
$i^{k_{q}}=i^{k_{q}}_{1},j^{k_{q}}_{1},\dots,i^{k_{q}}_{n_{q}},j^{k_{q}}_{n_{q}}=j^{k_{q}}$
such that

$x_{i^{k_{q}}}=x_{i^{k_{q}}_{1}}\blacktriangle
y_{j^{k_{q}}_{1}}\blacktriangle\dots\blacktriangle
x_{i^{k_{q}}_{n_{q}}}\blacktriangle y_{j^{k_{q}}_{n_{q}}}=y_{j^{k_{q}}}$

Now, still keeping the convention $l+1=1$, we set

$P:=R^{*}+\varepsilon\sum_{q=1}^{l}\delta_{i^{k_{q+1}}j^{k_{q}}}-\varepsilon\sum_{q=1}^{l}\left(\sum_{n=1}^{n_{q}-1}\Big{(}\delta_{i^{k_{q}}_{n}j^{k_{q}}_{n}}-\delta_{i^{k_{q}}_{n+1}j^{k_{q}}_{n}}\Big{)}+\delta_{i^{k_{q}}_{n_{q}}j^{k_{q}}_{n_{q}}}\right).$

The matrix $P$ has less zeros than $R^{*}$: by the definition (47) of
$\varepsilon$, it has no additional zero and we have for instance
$P_{i^{k_{2}}j^{k_{1}}}>0$ and $R^{*}_{i^{k_{2}}j^{k_{1}}}=0$. Moreover,
$P\in\Pi(\mu,\nu)$, and the construction of the indices ensures that $P$ has
new non-zero entries w.r.t. $R^{*}$ only on $(x_{i},y_{j})$ such that
$R_{ij}>0$, which ensures that $P\ll R$. In virtue of Proposition 36, this
contradicts the fact that $R^{*}$ is the solution of
$\operatorname{Sch}(R;\mu,\nu)$, and we conclude that $p=1$.

Step 5:
$(\mathcal{D}\cup\mathcal{F},\blacktriangle)=(\mathcal{D}\cup\mathcal{F},\triangle)$.

Our last task is to prove that whenever $x_{i}\triangle y_{j}$, for some
$x_{i}\in\mathcal{D}$ and $y_{j}\in\mathcal{F}$, then we also have
$x_{i}\blacktriangle y_{j}$ (the reciprocal statement follows from $R^{*}\ll
R$). So let us consider $x_{i}\in\mathcal{D}$ and $y_{j}\in\mathcal{F}$ with
$x_{i}\triangle y_{j}$, assume that we do not have $x_{i}\blacktriangle
y_{j}$, and show that we reach a contradiction. As we know that
$(\mathcal{D}\cup\mathcal{F},\blacktriangle)$ is connected., we can find
$i=i_{1},j_{1},i_{2},\dots,i_{p},j_{p}=j^{\prime}$ such that

$x_{i}=x_{i_{1}}\blacktriangle y_{j_{1}}\blacktriangle
x_{i_{2}}\dots\blacktriangle x_{i_{p}}\blacktriangle y_{j_{p}}=y_{j}.$

We set

$P:=R^{*}+\varepsilon\delta_{ij}-\varepsilon\left(\sum_{n=1}^{p-1}\Big{(}\delta_{i_{n}j_{n}}-\delta_{i_{n+1}j_{n}}\Big{)}+\delta_{i_{p}j_{p}}\right).$

Once again, $P$ has less zeros than $R^{*}$, which is a contradiction, and the
result follows. ∎

We are now ready to conclude the proof of Theorem 23.

###### Proof of Theorem 23.

It remains to show that if $\mu$ and $\nu$ are such that (a) is verified (and
not (a’)), then the problem is approximately scalable (once again,
(b)$\Rightarrow$(c) is proved in the same way, and (c)$\Rightarrow$(a) and
(c)$\Rightarrow$(b) are easy).

Let us first remark that the problem $\operatorname{Sch}(R;\mu^{R},\nu^{R})$
is obviously scalable. Let us consider $\varepsilon\in(0,1)$. We define:

$\mu^{\varepsilon}:=(1-\varepsilon)\mu+\varepsilon\mu^{R}\quad\mbox{and}\quad\nu^{\varepsilon}=(1-\varepsilon)\nu+\varepsilon\nu^{R}.$

The condition (a) implies that for all $A\subset\mathcal{D}$:

$\mu^{\varepsilon}(A)\leq(1-\varepsilon)\nu(F_{R}(A))+\varepsilon\nu^{R}(F_{R}(A))=\nu^{\varepsilon}(A).$

with a strict inequality whenever $\mu^{R}(A)<\nu^{R}(F_{R}(A))$.

Let us now assume that Assumption 9 holds. In this case, in virtue of Lemma
24, the problem $\operatorname{Sch}(R;\mu^{\varepsilon},\nu^{\varepsilon})$ is
scalable. In particular, there exists
$R^{\varepsilon}\in\Pi(\mu^{\varepsilon},\nu^{\varepsilon})$ such that
$R^{\varepsilon}$ and $R$ have the same support. As the family
$(R^{\varepsilon})$ has value in the compact set

$\\{R^{\prime}\in\mathcal{M}_{+}(\mathcal{D}\times\mathcal{F})\,|\,\mathsf{M}(R^{\prime})\leq\max(\mathsf{M}(\mu),\mathsf{M}(R))\\},$

we can chose one of its limit points $\bar{R}$ as $\varepsilon\to 0$.
Obviously, $\bar{R}\ll R$ and $\bar{R}\in\Pi(\mu,\nu)$ so that
$\operatorname{Sch}(R;\mu,\nu)$ is approximately scalable.

It remains to prove that (a)$\Rightarrow$(c) even when Assumption 9 does not
hold. To do so, we claim that under (a), assuming Assumption 9 is not
restrictive. The reason is that (a) implies Assumption 8, and hence Assumption
9 up to restricting the problem to the supports of $\mu$ and $\nu$, as
explained in Subsection 2.3.

So let us prove that (a) implies Assumption 8. We suppose that (a) holds, and
we consider $\mathcal{E}$ and $R^{0}$ as defined in Assumption 8.

Let us show that $\mu\ll\mu^{R^{0}}$. Let $x_{i}\in\mathcal{D}$ be such that
$\mu_{i}>0$, and let us show that $\mu^{R^{0}}_{i}>0$. By (a),
$\nu(F_{R}(\\{x_{i}\\})\geq\mu_{i}>0$. Therefore, $F_{R}(\\{x_{i}\\})$ is
nonempty, and there exists $y_{j}\in F_{R}(\\{x_{i}\\})$ such that
$\nu_{j}>0$. This pair $(x_{i},y_{j})$ belongs to $\mathcal{E}$, so
$R^{0}_{ij}>0$, and then $\mu^{R^{0}}_{i}>0$.

Let us show that $\nu\ll\nu^{R^{0}}$. Let $y_{j}\in\mathcal{F}$ be such that
$\nu_{j}>0$, and let us show that $\nu^{R^{0}}_{j}>0$. Let us call
$\mathcal{D}^{\prime}$ the support of $\mu$. By (a),
$\mathsf{M}(\nu)\geq\nu(F(\mathcal{D}^{\prime}))\geq\mu(\mathcal{D}^{\prime})=\mathsf{M}(\mu)$.
But as $\mathsf{M}(\nu)=\mathsf{M}(\mu)$, we conclude that
$\nu(F(\mathcal{D}^{\prime}))=\mathsf{M}(\nu)$, and so in particular that
$y_{j}\in F(\mathcal{D}^{\prime})$. So there exists
$x_{i}\in\mathcal{D}^{\prime}$ such that $R_{ij}>0$. This pair $(x_{i},y_{j})$
belongs to $\mathcal{E}$, so $R^{0}_{ij}>0$, and then $\nu^{R^{0}}_{j}>0$. ∎

## References

  * [1] E. Achilles.  Implications of convergence rates in sinkhorn balancing.  Linear Algebra and its Applications, 187:109–112, 1993.
  * [2] J-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré.  Iterative Bergman projections for regularized transportation problems.  SIAM Journal on Scientific Computing, 37(2):A1111–A1138, 2015.
  * [3] A. Braides.  Gamma-convergence for Beginners, volume 22.  Clarendon Press, 2002.
  * [4] R. Brualdi.  Convex sets of non-negative matrices.  Canadian Journal of Mathematics, 20:144–157, 1968.
  * [5] G. Carlier, V. Duval, G. Peyré, and B. Schmitzer.  Convergence of entropic schemes for optimal transport and gradient flows.  SIAM Journal on Mathematical Analysis, 49(2):1385–1418, 2017.
  * [6] L. Chizat, G. Peyré, B. Schmitzer, and FX. Vialard.  Scaling algorithms for unbalanced optimal transport problems.  Mathematics of Computation, 87(314):2563–2609, 2018.
  * [7] I. Csiszár.  I-divergence geometry of probability distributions and minimization problems.  The annals of probability, pages 146–158, 1975.
  * [8] M. Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In Advances in neural information processing systems, pages 2292–2300, 2013.
  * [9] H. Föllmer.  Random fields and diffusion processes.  In École d’Été de Probabilités de Saint-Flour XV–XVII, 1985–87, pages 101–203. Springer, 1988.
  * [10] R. Fortet.  Résolution d’un système d’équations de M. Schrödinger.  J. Math. Pures Appl., 19:83–105, 1940.
  * [11] I. Gentil, C. Léonard, and L. Ripani.  About the analogy between optimal transport and minimal entropy.  Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série 6, 3:569–600, 2017.
  * [12] A. Hagberg, P. Swart, and D. Chult.  Exploring network structure, dynamics, and function using networkx.  Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
  * [13] U. Herbach, A. Bonnaffoux, T. Espinasse, and O. Gandrillon.  Inferring gene regulatory networks from single-cell data: a mechanistic approach.  BMC Systems Biology, 11:105, 2017.
  * [14] M. Idel.  A review of matrix scaling and sinkhorn’s normal form for matrices and positive maps, 2016.
  * [15] S. Kondratyev, L. Monsaingeon, and D. Vorotnikov.  A new optimal transport distance on the space of finite radon measures.  Advances in Differential Equations, 21(11/12):1117–1164, 2016.
  * [16] H. Lavenant, S. Zhang, Y-H. Kim, and G. Schiebinger.  Towards a mathematical theory of trajectory inference.  arXiv preprint arXiv:2102.09204, 2021.
  * [17] C. Léonard.  From the Schrödinger problem to the Monge–Kantorovich problem.  Journal of Functional Analysis, 262(4):1879–1920, 2012.
  * [18] C. Léonard.  A survey of the Schrödinger problem and some of its connections with optimal transport.  Discrete & Continuous Dynamical Systems-A, 34(4):1533–1574, 2014\.
  * [19] C. Léonard.  Some properties of path measures.  In Séminaire de Probabilités XLVI, pages 207–230. Springer, 2014.
  * [20] M. Liero, A. Mielke, and G. Savaré.  Optimal entropy-transport problems and a new hellinger–kantorovich distance between positive measures.  Inventiones mathematicae, 211(3):969–1117, 2018.
  * [21] T. Mikami.  Monge’s problem with a quadratic cost by the zero-noise limit of h-path processes.  Probability theory and related fields, 129(2):245–260, 2004.
  * [22] M. Nutz.  Introduction to entropic optimal transport.
  * [23] G. Peyré and M. Cuturi.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [24] L. Rüschendorf and W. Thomsen.  Note on the Schrödinger equation and $I$-projections.  Statist. Probab. Lett., 17(5):369–375, 1993.
  * [25] I.N. Sanov.  On the probability of large deviations of random variables.  Technical report, North Carolina State University. Dept. of Statistics, 1958.
  * [26] G. Schiebinger, J. Shu, M. Tabaka, B. Cleary, V. Subramanian, A. Solomon, J. Gould, S. Liu, S. Lin, P. Berube, L. Lee, J. Chen, J. Brumbaugh, P. Rigollet, K. Hochedlinger, R. Jaenisch, A. Regev, and E. S. Lander.  Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming.  Cell, 176:928–943 e22, 2019.
  * [27] E. Schrödinger.  Über die Umkehrung der naturgesetze.  Verlag Akademie der wissenschaften in kommission bei Walter de Gruyter u. Company, 1931.
  * [28] E. Schrödinger.  Sur la théorie relativiste de l’électron et l’interprétation de la mécanique quantique.  In Annales de l’institut Henri Poincaré, volume 2, pages 269–310, 1932.
  * [29] R. Sinkhorn.  A relationship between arbitrary positive matrices and doubly stochastic matrices.  The annals of mathematical statistics, 35(2):876–879, 1964.
  * [30] R. Sinkhorn.  Diagonal equivalence to matrices with prescribed row and column sums.  The American Mathematical Monthly, 74(4):402–405, 1967.
  * [31] E. Ventre.  Analyse, calibration et évaluation de modèles stochastiques d’expression des gènes.  Hal, 2022.
  * [32] E. Ventre.  Reverse engineering of a mechanistic model of gene expression using metastability and temporal dynamics.  In Silico Biology, (Preprint):1–25, 2022.
  * [33] E. Ventre, U. Herbach, T. Espinasse, G. Benoit, and O. Gandrillon.  One model fits all: combining inference and simulation of gene regulatory networks.  bioRxiv, 2022.
  * [34] J-C. Zambrini.  Variational processes and stochastic versions of mechanics.  Journal of Mathematical Physics, 27(9):2307–2330, 1986.


# Investigating Trading Mechanisms as a Driver for User Experience in Racing
Games

Georg Arbesser-Rastburg  Graz University of Technology
Graz, Austria
<EMAIL_ADDRESS>Thomas Olip  Graz University of Technology
Graz, Austria
<EMAIL_ADDRESS>Johanna Pirker  Ludwig-Maximilians-Universität München
Munich, Germany
<EMAIL_ADDRESS>
###### Abstract

The exchange of digital goods has become a significant aspect of the global
economy, with digital products offering inexpensive reproduction and
distribution. In-game objects, a type of digital currency, have emerged as
tradable commodities within gaming ecosystems. Despite extensive research on
various aspects of digital goods, little attention has been given to the
impact of in-game trading mechanisms on user experience. This paper presents a
study aimed at evaluating the influence of trading systems on user experience
in a racing game context. We developed a simple racing game featuring an in-
game market for buying and selling car variants and conducted an A/B study
comparing user experiences between groups utilizing the trading system and
those unlocking cars through race completion. Our findings suggest that while
the trading system did not significantly alter the overall user experience,
further exploration of diverse trading approaches may offer insights into
their impact on user engagement.

###### Index Terms:

trading, racing game, user experience

††publicationid: pubid:  979-8-3503-5067-8/24/$31.00 ©2024 IEEE

##  I Introduction

The exchange of digital goods has impacted the global economy. Digital goods
are traded between producers/sellers and consumers in digital formats, making
them inexpensive to reproduce and distribute [1].

One type of digital goods is tradable in-game objects, which can be seen as
digital currency [2]. These in-game objects can be used to purchase goods and
services within the game, and popular games like the Pokémon
series111www.pokemon.com/us/pokemon-video-games or Massively Multiplayer
Online Role-Playing Games (MMORPGs) like World of
Warcraft222worldofwarcraft.blizzard.com have incorporated trading systems to
facilitate this process. For instance, Forza Horizon 5333www.forza.net/horizon
has an auction house where players can offer their vehicles for sale.

The field of trading in digital games has been studied in various aspects.
Researchers have explored how markets outside the actual games can emerge and
affect the game itself [3]. Furthermore, in addition to trading virtual goods,
current games allow players to make in-game purchases using real money.
Researchers have investigated various aspects of this phenomenon, including
its impact on game balance and player behavior [4]. Especially the effects of
loot boxes in games have been researched in the past years, for instance, the
relationship between loot boxes and gambling [5].

However, despite the extensive research in the digital goods industry, there
has yet to be research on the effect of in-game trading mechanisms on the user
experience. Therefore, this paper aims to take a first step toward evaluating
whether integrating a trading system significantly influences the user
experience. To achieve this, we implemented a simple racing game that allows
players to buy and sell car variants in an in-game market. By analyzing the
user feedback, we aim to provide insights into the impact of in-game trading
mechanisms on the user experience.

We describe the racing game in Section II. Using this game, we ran an A/B
study where one group used the in-game market, whereas the other group
unlocked new cars by simply completing races. We describe the study in Section
III and discuss our findings, the study’s limitations, and potential future
research in Section IV. More information about the work can be found in [6].

##  II Racing Game Implementation

To determine how trading mechanisms affect user experience in racing games, we
implemented a simple racing game in Unity444www.unity.com. In addition, we
used the Vehicle Physics Pro script555evp.vehiclephysics.com as a basis for
the vehicle physics implementation. The goal for the players is to reach
speeds as high as possible on a German highway without crashing into other
vehicles or the environment.

Currently, the game contains one highly detailed sports car (called Teron
Kanaani) that is available for racing. While only a single vehicle is
available, it comes in different colors that, for now, serve as a substitute
for different cars.

###  II-A Game Menus

When players start the game, they are taken to the main menu. From here, they
can access several submenus:

  * •

Collection

  * •

Garage

  * •

Market

  * •

Profile

  * •

Events

The collection displays the different available vehicle variants. The players
can view unseen, encountered, and owned vehicles, which are visualized
differently to give them an overview of their progress. The garage shows the
player’s currently selected vehicle in a simple island environment. The market
allows players to sell and buy cars. At the moment, players cannot yet trade
with each other and can only sell their cars for a fixed price and buy
vehicles from a random selection in a simulated market (see Figure 1). The
profile menu shows different player statistics, such as the number of owned
cars, total distance traveled, and the number of completed races. It also
displays various achievements, which come in three levels (bronze, silver, and
gold) and reward the player in nine categories (e.g., total traveled distance,
number of sold cars, or number of collected vehicles). Finally, the events
menu allows players to start new races. However, currently, only highway races
are available.

Figure 1: Screenshot depicting the in-game market. Players can sell their
vehicles in the bottom half and buy new ones in the top half.

###  II-B Highway Races

The highway is procedurally generated on runtime by concatenating blocks
containing the road and decorations like concrete road barriers or sound
barriers. The individual segments can be spawned in a predefined order to
facilitate the transition between blocks with different numbers of lanes. Cars
populate the highway as obstacles for the players.

These cars are dynamically spawned on the road out of the player’s sight to
optimize performance. Players must overtake without colliding with them or the
environment. One special type of car is police cars that also drive on the
highway. If the player collides with a police car, its blue emergency lights
are turned on, and roadblocks are created in front of the player to stop the
player’s vehicle. However, any collision, whether with a regular car, a police
car, or the environment, automatically invalidates the current race, and the
player will not receive any rewards for the race.

To complete a race, the player has to leave the highway and bring the car to a
standstill. Therefore, the player has to choose whether to keep driving and
risk crashing while trying to beat their current maximum speed or leave the
highway to finish the race. A screenshot from a race can be seen in Figure 2.

Figure 2: Screenshot taken from a race on the highway with a HUD on the bottom
and the traveled distance on top of the screen.

##  III Evaluation

We conducted an A/B study to assess how trading affects user experience in
racing games. Participants were asked to complete a pre- and post-
questionnaire, and in-game data was collected.

###  III-A Methodology

Two modes of obtaining new car variants were used in the study:

  * •

Mode A: Players receive a random vehicle after completing a race.

  * •

Mode B: Players must use in-game currency to purchase new car variants or
trade in one of their existing ones.

In Mode A, the in-game store is disabled, while in Mode B, players are
required to use it. In Mode B, players can only own up to ten cars, so they
must trade in an existing one to obtain a new vehicle at some point.
Additionally, players in Mode A receive an initial car, while players in Mode
B receive an initial budget for purchasing cars.

####  III-A1 Quest System

To guide users through the study, we implemented a simple quest system. The
current quest number and the quest’s description were displayed in the top
right corner of the user interface. Table I provides a complete list of all
quests.

TABLE I:  Quests during the study per group. Quest Number |  Test Group |  Quest Description
---|---|---
1. |  A |  Select your new car in the ’Collection’ tab.
1. |  B |  Visit the ’Market’, buy a car, and select it in the ’Collection’ tab.
2. |  A/B |  Start a speed run in the ’Garage’ tab. Drive at least 1 km.
3. |  A |  Change your car in the ’Collection’ tab.
3. |  B |  Visit the ’Market’ and buy another car.
4. |  A/B |  Start a speed run and drive at least 2 km. Try not to crash!
5. |  A |  Change your car again in the ’Collection’ tab.
5. |  B |  Visit the ’Market’ and buy another car.
6. |  A/B |  Complete a speed run (no collision, at least 1km). To complete the run, stop your car in the parking lane. Skip this quest if it is too hard.
7. |  A/B |  Feel free to play some more races. When you are done, press ’Finish’.

####  III-A2 Procedure

A link to the game was distributed online in Discord groups or directly
provided to interested persons. Using the link, users could download the game,
which supports Windows, macOS, and Linux. After starting the game, users had
to complete the pre-questionnaire and were randomly assigned to group A or B.
Afterward, they had to complete their quests, and finally, the users were
asked to fill out the post-questionnaire.

####  III-A3 In-Game Data Collection

During the game sessions, we collected in-game data to evaluate the number of
cars obtained by the players and the number of interactions with different
elements in the game. The data was automatically sent to a database for later
evaluation. A complete list of the collected in-game data is provided in Table
II.

TABLE II: List of in-game data collected during the study. Name |  Description
---|---
Play Time |  Total time spent in the program, measured in seconds.
Distance |  Combined driven distance with the cars, measured in meters.
Races |  Total driven races, including aborted races.
Finished Runs |  Total finished races without crashes or disqualification.
Cars Collected |  Total cars obtained through winning or trading.
Market Visits |  Clicks on the market tab in the user interface.
Collection Visits |  Clicks on the collection tab in the user interface.
Garage Visits |  Clicks on the garage tab in the user interface.
Event Visits |  Clicks on the events tab in the user interface.
Profile Visits |  Clicks on the profile tab in the user interface.
Finished Quests |  Number of quests the user completed.

####  III-A4 Questionnaires

In addition to the in-game data collected, we asked the study participants to
fill out a pre- and a post-questionnaire. Both were integrated directly into
the game. The pre-questionnaire only contained questions regarding the
players’ age and sex. The post-questionnaire consisted of the System Usability
Scale (SUS) [7] and the Game Experience Questionnaire (GEQ) [8]. We used the
shortened In-Game module of the GEQ to keep the questionnaire brief.

####  III-A5 Participants

39 participants, eight female and 31 male, took part in the study. The
participants’ ages ranged from 14 to 41, with an average of 25.0 and a
standard deviation of 6.1.

###  III-B Results

Out of the 39 participants, 30 filled out the questionnaires.

####  III-B1 System Usability Scale

We excluded three participants from the SUS analysis due to inconsistent
answers. The SUS comprises alternating positively and negatively framed
questions. If participants choose the same answer for all questions, this
could be due to either not understanding the questions correctly or a lack of
attention. Two participants answered all questions the same, while another
chose almost the same responses for all questions.

Table III shows the SUS results per group and the result of a two-sample
t-test. While Group A has a lower mean (69.29) than Group B (80.54), the
higher standard deviation in Group A (22.69) compared to Group B (7.73) leads
to inconclusive results, which is confirmed by the t-test.

TABLE III: System Usability Score results, including the mean and standard deviation per group, and the statistical significance with $\alpha$ = 0.05. | Group A | Group B |  t(26) | p
---|---|---|---|---
|  M |  SD |  M |  SD |  |
System Usability Score |  69.29 |  22.69 |  80.54 |  7.73 | 1.76 | .090

####  III-B2 Game Experience Questionnaire

The 14 questions that the GEQ comprises can be grouped into seven different
categories, which are shown together with their results in Table IV. In
general, negative affect received a low rating, while positive affect,
challenge, and competence were rated relatively high. All other categories are
in the midfield. Due to the large standard deviations and similar mean values,
the results are inconclusive, however, and no differences between the groups
can be observed.

TABLE IV: Game Experience Questionnaire results, including the mean and standard deviation per Group, and the statistical significance with $\alpha$ = 0.05. | Group A | Group B |  t(29) | p
---|---|---|---|---
|  M |  SD |  M |  SD |  |
Competence |  2.46 |  0.93 |  2.59 |  1.00 | -0.35 | .726
Sensory and Imaginative Immersion |  1.96 |  0.84 |  2.09 |  1.15 | -0.33 | .740
Flow |  2.04 |  1.03 |  2.18 |  1.29 | -0.33 | .742
Tension |  1.54 |  0.91 |  1.85 |  1.30 | -0.77 | .446
Challenge |  2.82 |  0.67 |  2.38 |  1.07 | 1.34 | .192
Negative affect |  0.96 |  0.77 |  1.71 |  1.46 | -1.71 | .098
Positive affect |  2.46 |  0.87 |  2.41 |  1.20 | 0.14 | .892

####  III-B3 In-Game Data

Finally, Table V shows the collected in-game data. Both the number of market
visits and cars sold is 0 for Group A, as this group had no access to the in-
game store. Aside from the number of cars sold and the number of market
visits, one statistically significant difference between the two groups can be
observed: the number of collected cars.

TABLE V: Collected in-game data including mean and standard deviation per group, and the statistical significance with $\alpha$ = 0.05. | Group A | Group B |  t(33) | p
---|---|---|---|---
|  M | SD |  M | SD |  |
Market Visits |  0.00 | 0.00 |  11.61 | 10.98 | -4.36 |  $<$ .001
Collection Visits |  17.65 | 10.94 |  17.17 | 11.80 | 0.13 | .901
Garage Visits |  28.00 | 18.14 |  18.00 | 10.75 | 2.00 | .054
Event Visits |  5.94 | 8.30 |  2.61 | 3.97 | 1.53 | .136
Profile Visits |  2.88 | 3.66 |  1.11 | 1.23 | 1.94 | .060
Distance (km) |  55.71 | 60.99 |  26.50 | 25.39 | 1.87 | .070
Play Time (min) |  43.21 | 40.22 |  23.81 | 13.42 | 1.93 | .061
Races |  27.53 | 26.43 |  14.44 | 10.01 | 1.96 | .058
Finished Runs |  2.24 | 2.02 |  1.50 | 1.42 | 1.25 | .219
Cars Collected |  11.53 | 6.35 |  4.94 | 3.42 | 3.85 | .001
Cars Sold |  0 | 0 |  1.61 | 3.09 | -2.15 | .039

##  IV Discussion

The general outcome of the study is positive, with both SUS and GEQ showing
positive overall results. SUS indicates average to above-average system
usability [9]. Another interesting aspect is the time spent by the players.
While the study itself could be completed in 10 to 15 minutes, many players
spent much more time in the game and completed more races than was required.
This suggests that the game was engaging and enjoyable for the players.
Interestingly, the players did not exhaust the limited number of garage slots
for Group B; still, they sold more cars than required by the quests. This
indicates a high level of interest in the game’s mechanics and a willingness
to explore the game beyond the required tasks.

The study also revealed no statistically significant differences in player
experience or system usability between the two groups, except for the number
of collected cars, which was higher in Group A. This finding suggests that the
game’s mechanics were equally enjoyable and usable for both groups.

###  IV-A Limitations & Future Work

The study presented in this paper has certain limitations that need to be
acknowledged. First, the sample size of the study participants is relatively
small, and a larger number of participants would increase the statistical
power of the results.

Second, the study participants could only trade with a simulated market.
Introducing a social element, such as allowing participants to trade with each
other directly, might lead to different outcomes and provide a more realistic
representation of trading behavior.

Third, players could only acquire the same car in different colors, which may
not have motivated them enough to trade cars. Offering different cars with
varying stats for acceleration or top speed could increase the motivation to
trade. Additionally, integrating car upgrades could make the trading process
more interesting and engaging for the players.

Finally, the rarity of certain cars could play a role in incentivizing players
to trade more common cars for rare ones. Being able to collect rare cars might
be an incentive for players to trade more frequently and make the trading
process more exciting. Overall, these limitations need to be considered when
interpreting the study results and should be addressed in future research to
provide a more comprehensive understanding of trading behavior in racing
games.

###  IV-B Conclusion

In this study, we developed a racing game with a simple trading system to
investigate whether trading affects user experience. In the game, players can
buy new car variants in an in-game store and race on a highway. During these
races, players try to beat their own top speeds without colliding with other
vehicles or the environment. To finish the race, players have to bring their
cars to a standstill. We tested this system in an A/B study where one group
unlocked a new car variant after each race, and the other group had to use an
in-game store to buy and sell cars. The results indicate a good overall user
experience, but no statistically significant difference between the groups
could be observed. This could be due to the fact that players could only buy
different variants of one car without any performance differences, and they
could only trade with a simulated market. Based on our findings, we conclude
that a simple trading system like this does not have a significant impact on
user experience. Further research could explore the influence of different
trading approaches on user experience.

## References

  * [1] S. Bradley, C. Kim, J. Kim, and I. Lee, “Toward an evolution strategy for the digital goods business,” _Management Decision_ , vol. 50, no. 2, pp. 234–252, 3 2012.
  * [2] E. E. W. Adams and J. Dormans, _Game mechanics : advanced game design_. New Riders, 2012.
  * [3] Y. Guo and S. Barnes, “Why people buy virtual items in virtual worlds with real money,” _ACM SIGMIS Database: the DATABASE for Advances in Information Systems_ , vol. 38, no. 4, pp. 69–76, 10 2007. [Online]. Available: https://dl.acm.org/doi/10.1145/1314234.1314247
  * [4] A. Urschel, “Understanding Real Money Trading in MMORPGs,” New World Order, Tech. Rep., 2011.
  * [5] W. Li, D. Mills, and L. Nower, “The relationship of loot box purchases to problem video gaming and problem gambling,” _Addictive Behaviors_ , vol. 97, pp. 27–34, 10 2019.
  * [6] T. Olip, “Implementation of Trading as a Collecting Mechanic in a Novel Racing Game,” Master’s thesis, Graz University of Technology, Graz, 2024.
  * [7] J. Brooke, “SUS: A ’Quick and Dirty’ Usability Scale,” in _Usability Evaluation In Industry_. CRC Press, 6 1996, pp. 207–212.
  * [8] W. A. Ijsselsteijn, D. Kort, and Y. A. W. . Poels, “The Game Experience Questionnaire,” Technische Universiteit Eindhoven, Tech. Rep., 1 2013.
  * [9] J. R. Lewis and J. Sauro, “Item Benchmarks for the System Usability Scale,” _Journal of Usability Studies_ , vol. 13, pp. 158–167, 2018.


# Lattice Size of Width One Lattice Polytopes in $\mathbb{R}^{3}$

Abdulrahman Alajmi  Department of Mathematical Sciences
Kent State University
800 E. Summit st., Kent, OH 44242, USA<EMAIL_ADDRESS>and  Jenya Soprunova
Department of Mathematical Sciences
Kent State University
800 E. Summit st., Kent, OH 44242, USA<EMAIL_ADDRESS>http://www.math.kent.edu/ soprunova/

###### Abstract.

Lattice size $\operatorname{ls_{\Delta}}(P)$ of a lattice polytope $P$ is an
important invariant, which was formally introduced in relation to the problem
of bounding the total degree and the bi-degree of the defining equation of an
algebraic curve, but appeared implicitly earlier in geometric combinatorics.
In this paper, we show that for an empty lattice polytope
$P\subset\mathbb{R}^{3}$ there exists a reduced basis of $\mathbb{Z}^{3}$
which computes its lattice size $\operatorname{ls_{\Delta}}(P)$. This leads to
a fast algorithm for computing $\operatorname{ls_{\Delta}}(P)$ for such $P$.
We also extend this result to another class of lattice width one polytopes
$P\subset\mathbb{R}^{3}$. We then provide a counterexample demonstrating that
this result does not hold true for an arbitrary lattice polytope
$P\subset\mathbb{R}^{3}$ of lattice width one.

###### Key words and phrases:

Lattice size, lattice width, lattice polygons, generalized basis reduction.

###### 2010 Mathematics Subject Classification:

11H06, 52B20, 52C05

††copyright: ©:

##  1\. Introduction

A point in $\mathbb{R}^{d}$ is a lattice point if it belongs to
$\mathbb{Z}^{d}\subset\mathbb{R}^{d}$. We say that $P\subset\mathbb{R}^{n}$ is
a lattice polytope if $P$ is a convex polytope all of whose vertices are
lattice points. A segment connecting two lattice points is called a lattice
segment. A lattice segment is primitive if its only lattice points are its
endpoints.

Recall that a unimodular matrix $A\in{\rm GL}(d,\mathbb{Z})$ is a square
matrix of size $d$ with integer entries that satisfies $\det A=\pm 1$.
Further, ${\rm AGL}(d,\mathbb{Z})$ is the group of affine unimodular
transformations $T\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ of the form
$T(x)=Ax+v$, where $A\in{\rm GL}(d,\mathbb{Z})$ and $v\in\mathbb{Z}^{d}$. Two
lattice polytopes in $P,Q\subset\mathbb{R}^{d}$ are lattice-equivalent if
$Q=T(P)$ for some $T\in{\rm AGL}(d,\mathbb{Z})$. We will write $AP$ for the
image of $P$ under the map $T\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ defined by
$T(x)=Ax$.

Recall that for a lattice polytope $P\subset\mathbb{R}^{d}$ the lattice width
of $P$ in the direction of $h\in\mathbb{R}^{d}$ is

$\operatorname{w}_{h}(P)=\max\limits_{x\in P}\langle h,x\rangle-\min_{x\in
P}\langle h,x\rangle,$

where $\langle h,x\rangle$ denotes the standard dot-product. Then the lattice
width $\operatorname{w}(P)$ of $P$ is the minimum of $\operatorname{w}_{h}(P)$
over all non-zero primitive vectors $h\in\mathbb{Z}^{d}$.

Let $0\in\mathbb{R}^{d}$ denote the origin and let $(e_{1},\dots,e_{d})$ be
the standard basis of $\mathbb{R}^{d}$. Then
$\Delta=\operatorname{conv}\\{0,e_{1},\dots,e_{d}\\}\subset\mathbb{R}^{d}$ is
the standard simplex. The central object of this paper is the lattice size. It
was formally defined in [6], appeared earlier implicitly in [2, 4, 5, 10, 13],
and was further studied in [7, 8, 14]. We now reproduce its definition.

######  Definition 1.1.

The lattice size $\operatorname{ls_{\Delta}}(P)$ of a lattice polytope
$P\subset\mathbb{R}^{d}$ with respect to the standard simplex $\Delta$ is the
smallest $l\geq 0$ such that $T(P)$ is contained in the $l$-dilate $l\Delta$
for some $T\in{\rm AGL}(d,\mathbb{Z})$.

That is, if we define

$l_{1}(P)=\max\limits_{(x_{1},\dots,x_{d})\in
P}(x_{1}+\cdots+x_{d})-\min\limits_{(x_{1},\dots,x_{d})\in
P}x_{1}-\cdots-\min\limits_{(x_{1},\dots,x_{d})\in P}x_{d},$

then $\operatorname{ls_{\Delta}}(P)=\min\\{l_{1}(T(P))\mid T\in{\rm
AGL}(d,\mathbb{Z})\\}$.

If we replace in Definition 1.1 the standard simplex $\Delta$ with the unit
cube $\square=[0,1]^{d}$, we obtain the definition of the lattice size with
respect to the cube, denoted by $\operatorname{ls_{\square}}(P)$.

In [6] the authors explained an algorithm for computing the lattice size
$\operatorname{ls_{\Delta}}(P)$ and $\operatorname{ls_{\square}}(P)$ of a
plane lattice polygon $P$. This algorithm is based on a procedure for mapping
a polytope inside a small multiple of the unit simplex, introduced by Schicho
in [13]. In this algorithm, called the “onion skins” algorithm, one passes
recursively from $P$ to the convex hull of the interior lattice points of $P$.
It was then shown in [7, 8] that basis reduction provides a faster way of
computing the lattice size $\operatorname{ls_{\Delta}}(P)$ and
$\operatorname{ls_{\square}}(P)$, which works not only for lattice polygons,
but also for plane convex bodies. We next introduce further definitions in
order to explain these results.

######  Definition 1.2.

For $P\subset\mathbb{R}^{d}$, the naive lattice size
$\operatorname{nls_{\Delta}}(P)$ is the smallest $l$ such that $T(P)\subset
l\Delta$, where $T\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is a composition of
matrix multiplication by a diagonal matrix $A$ with entries $\pm 1$ on the
main diagonal, and a lattice translation. Further, for $d=2$, let

$\displaystyle l_{1}(P)$ $\displaystyle:=$ $\displaystyle\max\limits_{(x,y)\in
P}(x+y)-\min\limits_{(x,y)\in P}x-\min\limits_{(x,y)\in P}y,$ $\displaystyle
l_{2}(P)$ $\displaystyle:=$ $\displaystyle\max\limits_{(x,y)\in
P}x+\max\limits_{(x,y)\in P}y-\min\limits_{(x,y)\in P}(x+y),$ $\displaystyle
l_{3}(P)$ $\displaystyle:=$ $\displaystyle\max\limits_{(x,y)\in
P}y-\min\limits_{(x,y)\in P}x+\max\limits_{(x,y)\in P}(x-y),$ $\displaystyle
l_{4}(P)$ $\displaystyle:=$ $\displaystyle\max\limits_{(x,y)\in
P}x-\min\limits_{(x,y)\in P}y+\max\limits_{(x,y)\in P}(y-x).$

Then in the case of $d=2$ the naive lattice size
$\operatorname{nls_{\Delta}}(P)$ is the smallest of these four values. For
$P\subset\mathbb{R}^{3}$ one can similarly write
$\operatorname{nls_{\Delta}}(P)$ as the minimum of eight $l_{i}(P)$, each
corresponding to a vertex of the unit cube.

######  Definition 1.3.

We say that a basis $(h^{1},\dots,h^{d})$ of $\mathbb{Z}^{d}$ computes
$\operatorname{ls_{\Delta}}(P)$ if for matrix $A$ with rows
$h^{1},\dots,h^{d}$ we have
$\operatorname{ls_{\Delta}}(P)=\operatorname{nls_{\Delta}}(AP)$.

Let $(-P)$ be the reflection of $P$ in the origin, and define $K$ to be the
polar dual of the Minkowski sum of $P$ with $(-P)$, that is,
$K:=(P+(-P))^{\circ}$. Then $K$ is origin-symmetric and convex and it defines
a norm on $\mathbb{R}^{d}$ by

$\|h\|_{K}=\inf\\{\lambda>0\mid h/\lambda\in K\\}.$

For details see, for example, [3]. We then have

$\|h\|_{K}=\inf\\{\lambda>0\mid\langle h,x\rangle\leq\lambda{\rm\ for\ all\
}x\in K^{\circ}\\}=\max\limits_{x\in K^{\circ}}\langle
h,x\rangle=\frac{1}{2}\operatorname{w}_{h}(K^{\circ})=\operatorname{w}_{h}(P).$

In what follows we will often write $\|h\|$ for the lattice width
$\operatorname{w}_{h}(P)$.

######  Definition 1.4.

Let $P\subset\mathbb{R}^{2}$. We say that a basis $(h^{1},h^{2})$ of the
integer lattice $\mathbb{Z}^{2}\subset\mathbb{R}^{2}$ is reduced (with respect
to $P$) if

  1. (1)

$\|h_{1}\|\leq\|h_{2}\|$ and

  2. (2)

$\|h_{1}\pm h_{2}\|\geq\|h_{2}\|$.

It was shown in [7] that if the standard basis $(e_{1},e_{2})$ is reduced with
respect to a convex body $P\subset\mathbb{R}^{2}$ then
$\operatorname{ls_{\square}}(P)=\operatorname{w}_{e_{2}}(P)$. This result was
extended to the lattice size with respect to the unit simplex
$\Delta\subset\mathbb{R}^{2}$ in [8], where it was shown that if the standard
basis $(e_{1},e_{2})$ is reduced with respect to $P$ then is computes
$\operatorname{ls_{\Delta}}(P)$. Since one can find a reduced basis using the
generalized Gauss reduction algorithm [9, 11], these results provide a fast
way of finding $\operatorname{ls_{\Delta}}(P)$ and
$\operatorname{ls_{\square}}(P)$ for plane convex bodies $P$, which, as
explained in [7, 8], outperforms the “onion skins” algorithm of [6].

Since the condition $\|h_{1}\pm h_{2}\|\geq\|h_{2}\|$ is equivalent to
requiring that $\|mh_{1}+h_{2}\|\geq\|h_{2}\|$ for $m\in\mathbb{Z}$ (see [7]),
the following definition is a natural extension of the previous one.

######  Definition 1.5.

Let $P\subset\mathbb{R}^{3}$. We say that a basis $(h^{1},h^{2},h^{3})$ of
$\mathbb{Z}^{3}$ is reduced (with respect to $P$) if

  1. (1)

$\|h_{1}\|\leq\|h_{2}\|\leq\|h_{3}\|$;

  2. (2)

$\|h_{1}\pm h_{2}\|\geq\|h_{2}\|$;

  3. (3)

$\|mh^{1}+nh^{2}+h^{3}\|\geq\|h^{3}\|$ for all $m,n\in\mathbb{Z}$.

It was shown in [7] that if the standard basis $(e_{1},e_{2},e_{3})$ is
reduced with respect to a convex body $P\subset\mathbb{R}^{3}$, then
$\operatorname{ls_{\square}}(P)=\operatorname{w}_{e_{3}}(P)$. This result does
not extend to the lattice size with respect to the standard simplex. An
example provided in [8] demonstrates that there exists a lattice polytope
$P\subset\mathbb{R}^{3}$ such that there is no reduced basis that computes
$\operatorname{ls_{\Delta}}(P)$.

In order to compute the lattice size $\operatorname{ls_{\Delta}}(P)$ of a
lattice polytope $P\subset\mathbb{R}^{3}$ one can use the following
observation from [5]. Let $l=l_{1}(P)$ and shift $P$ so that its barycenter is
at the origin. Consider a ball $B\subset P$ centered at the origin of the
largest possible radius $R$. Denote by $\|h\|_{2}$ the Euclidean norm of $h$.
Then if $\|h\|_{2}\geq\frac{l}{R}$ we have

$\|h\|=\operatorname{w}_{h}(P)\geq\operatorname{w}_{h}(B)=R\cdot\|h\|_{2}\geq
l.$

Hence, in order to compute the lattice size $\operatorname{ls_{\Delta}}(P)$,
one can find all directions $h$ with $\|h\|_{2}<\frac{l}{R}$, check which ones
of them satisfy $\operatorname{w}_{h}(P)<l$ and then use vectors from this
list as rows to build all possible unimodular matrices $A$. Then
$\operatorname{ls_{\Delta}}(P)$ is the minimum of $l_{1}(AP)$ over all such
matrices. We implemented this algorithm, which we call here the Brute Force
Algorithm, using Magma, and ran the code on polytopes which are convex hulls
of $n$ random lattice points in $\mathbb{R}^{3}$ with absolute values of
coordinates bounded by 7, where $n$ is a random number between 10 and 15. The
Brute Force Algorithm is fairly fast: We ran 100 such experiments and they
took 4.3 sec on average. The described experimentation is implemented in
Experiment1.mgm, [1].

In contrast, when we considered lattice polytopes $P$ of lattice width one,
the algorithm was much slower. We randomly picked two polygons $P_{0}$ and
$P_{1}$ as convex hulls of $n_{0}$ and $n_{1}$ lattice points in the planes
$x=0$ and $x=1$ correspondingly, with the absolute value of the $y$ and $z$
coordinates of these points bounded by 7, and $n_{0}$ and $n_{1}$ picked
randomly between 5 and 8. We then defined $P$ as the convex hull of $P_{0}$
and $P_{1}$. We ran 100 such experiments, and they took 97.5 sec on average.

Furthermore, this algorithm takes even longer when $P\subset\mathbb{R}^{3}$ is
an empty lattice tetrahedron. Recall that a lattice polytope $P$ is empty if
its only lattice points are its vertices. It was shown in [15] that up to
lattice equivalence empty lattice tetrahedra $P\subset\mathbb{R}^{3}$ are of
the form

$P=\begin{bmatrix}1&0&0&p\\\ 0&1&0&q\\\ 0&0&1&1\end{bmatrix},$

where $p$ and $q$ are non-negative integers satisfying $\gcd(p,q)=1$. Note
that the columns of this matrix are the vertices of $P$. (We will be using
this notation throughout the paper: The polytope written as a matrix is the
convex hull of its column vectors.) It was further shown in [12] that any
empty lattice polytope $P\subset\mathbb{R}^{3}$ has lattice width one.

In Experiment1.mgm in [1] we ran the Brute Force Algorithm on empty lattice
tetrahedra $P$ with $p$ and $q$ picked randomly between $0$ and 14. The
average run time in 25 such experiments was 2907 sec.

In this paper we concentrate our attention on computing the lattice size of
lattice polytopes $P\subset\mathbb{R}^{3}$ with $\operatorname{w}(P)=1$ and,
in particular, of empty lattice polytopes. In Theorem 3.1 we prove that for an
empty lattice polytope $P\subset\mathbb{R}^{3}$ there exists a reduced basis
that computes its lattice size $\operatorname{ls_{\Delta}}(P)$ and provide an
algorithm (Algorithm 3.2) for finding such a basis, which works significantly
faster than the Brute Force Algorithm explained above.

In Section 4 we consider another class of lattice polytopes
$P\subset\mathbb{R}^{3}$ of lattice width one and show in Theorem 4.3 that
there exists a reduced basis that computes their lattice size. It follows that
Algorithm 3.2 computes the lattice size in this case as well.

Based on our results, it is reasonable to ask whether the conclusion extends
to all lattice polytopes $P\subset\mathbb{R}^{3}$ of lattice width one. In
Section 5 we explain an algorithm for testing this question. We ran 10 000
experiments and found a lattice width one polytope $P$, for which there is no
reduced basis that computes its lattice size $\operatorname{ls_{\Delta}}(P)$.
Interestingly, such counterexamples are quite rare: Only two out of our 10 000
experiments resulted in counterexamples.

##  2\. Definitions and First Lemmas

Note that for $h\in\mathbb{R}^{3}$ and $A\in{\rm GL}(3,\mathbb{Z})$ we have

$\operatorname{w}_{h}(AP)=\max\limits_{x\in P}\langle h,Ax\rangle-\min_{x\in
P}\langle h,Ax\rangle=\max\limits_{x\in P}\langle A^{T}h,x\rangle-\min_{x\in
P}\langle A^{T}h,x\rangle=\operatorname{w}_{A^{T}h}(P).$

Therefore, if the rows of $A$ are $h_{1},h_{2},h_{3}$ then
$\operatorname{w}_{e_{i}}(AP)=\operatorname{w}_{h_{i}}(P)$ for $i=1,2,3$.

If $(e_{1},e_{2},e_{3})$ is the standard basis, then
$l_{1}(P)\geq\operatorname{w}_{e_{i}}(P)$. We check this for $i=1$:

$\displaystyle l_{1}(P)$ $\displaystyle=\max\limits_{(x,y,z)\in
P}(x+y+z)-\min\limits_{(x,y,z)\in P}x-\min\limits_{(x,y,z)\in
P}y-\min\limits_{(x,y,z)\in P}z$ $\displaystyle\geq\max\limits_{(x,y,z)\in
P}x+\min\limits_{(x,y,z)\in P}y+\min\limits_{(x,y,z)\in
P}z-\min\limits_{(x,y,z)\in P}x-\min\limits_{(x,y,z)\in
P}y-\min\limits_{(x,y,z)\in P}z$ $\displaystyle=\max\limits_{(x,y,z)\in
P}x-\min\limits_{(x,y,z)\in P}x=\operatorname{w}_{e_{1}}(P).$

Hence, for $A\in{\rm GL}(3,\mathbb{Z})$ with rows $h_{1},h_{2},h_{3}$ we get

$l_{1}(AP)\geq\operatorname{w}_{e_{i}}(AP)=\operatorname{w}_{h_{i}}(P).$

We next prove 3D versions of Lemmas 2.5 and 2.6 from [8].

######  Lemma 2.1.

Let $h_{1},h_{2}$, and $h_{3}$ be the rows of $A\in{\rm GL}(3,\mathbb{Z})$.
Then

  * (a)

$l_{1}(AP)=\max_{x\in P}\langle h_{1}+h_{2}+h_{3},x\rangle-\min_{x\in
P}\langle h_{1},x\rangle-\min_{x\in P}\langle h_{2},x\rangle-\min_{x\in
P}\langle h_{3},x\rangle$;

  * (b)

$l_{1}(AP)$ does not depend on the order of the rows in $A$;

  * (c)

$l_{1}(AP)=l_{1}\left(\begin{bmatrix}h_{1}\\\ h_{2}\\\
-(h_{1}+h_{2}+h_{3})\end{bmatrix}P\right).$

###### Proof.

We check (c) using (a)

$\displaystyle l_{1}\left(\begin{bmatrix}h_{1}\\\ h_{2}\\\
-(h_{1}+h_{2}+h_{3})\end{bmatrix}P\right)$ $\displaystyle=\max_{x\in
P}\langle-h_{3},x\rangle-\min_{x\in P}\langle h_{1},x\rangle-\min_{x\in
P}\langle h_{2},x\rangle$ $\displaystyle-\min_{x\in P}\langle-
h_{1}-h_{2}-h_{3},x\rangle=l_{1}(AP).$

∎

######  Lemma 2.2.

Let $l\in\mathbb{R}$ and suppose that for matrix $A\in{\rm GL}(3,\mathbb{Z})$
with the rows $h_{1}$, $h_{2}$, and $h_{3}$ we have $l_{1}(AP)<l$. Then the
lattice width of $P$ in the directions
$h_{1},h_{2},h_{3},h_{1}+h_{2},h_{1}+h_{3},h_{2}+h_{3}$, and
$h_{1}+h_{2}+h_{3}$ is also less than $l$.

###### Proof.

Denote $l_{1}=l_{1}(P)$. Since $AP\subset l_{1}\Delta$, we get
$\operatorname{w}_{e_{1}}(AP)\leq\operatorname{w}_{e_{1}}(l_{1}\Delta)=l_{1}$.
Hence $\operatorname{w}_{h_{1}}(P)=\operatorname{w}_{e_{1}}(AP)\leq l_{1}<l$.
The argument for the remaining directions is similar. ∎

######  Definition 2.3.

Let $P\subset\mathbb{R}^{3}$ be a convex body and denote
$\|h\|=\operatorname{w}_{h}(P)$. Then a basis $(h_{1},h_{2},h_{3})$ of
$\mathbb{Z}^{3}$ is Minkowski reduced (with respect to $P$) if

  * (1)

$\|h_{1}\|\leq\|h\|$ for all $h\in\mathbb{Z}^{3}$;

  * (2)

$\|h_{2}\|\leq\|h\|$ for all $h\in\mathbb{Z}^{3}$ that are not multiples of
$h_{1}$;

  * (3)

$\|h_{3}\|\leq\|h\|$ for all $h\in\mathbb{Z}^{3}$ that are not linear
combinations of $h_{1}$ and $h_{2}$.

Clearly, a Minkowski reduced basis is reduced. It was explained in Theorem 3.3
of [7] how to find a Minkowski reduced basis starting with a reduced basis
$(h_{1},h_{2},h_{3})$. For this, consider set
$E=\\{ah_{1}+bh_{2}+ch_{3}:|a|=|b|=1,|c|=2\\}$ and let $u$ be the direction of
the smallest norm in $E$. Then the two vectors of smallest norm among
$\\{h_{1},h_{2},u\\}$, written in the order of increasing norm together with
$h_{3}$ form a Minkowski reduced basis. Note that if in a reduced basis
$\|h^{3}\|\geq\|h^{1}\|+\|h^{2}\|$ then for any $h\in E$ we have

$\|h\|\geq 2\|h^{3}\|-\|h^{1}\|-\|h^{2}\|\geq\|h^{3}\|$

and hence such a reduced basis is also Minkowski reduced.

######  Lemma 2.4.

Let $(h_{1},h_{2},h_{3})$ be a Minkowski reduced basis. Then
$\operatorname{ls_{\Delta}}(P)\geq\|h_{3}\|$.

###### Proof.

Let $A\in{\rm GL}(3,\mathbb{Z})$ be such that
$\operatorname{ls_{\Delta}}(P)=l_{1}(AP)$. The rows $r_{1},r_{2},r_{3}$ of $A$
form a basis of $\mathbb{Z}^{3}$ and hence for one of them, say, $r_{3}$, we
have $\|r_{3}\|\geq\|h_{3}\|$. We conclude

$\operatorname{ls_{\Delta}}(P)=l_{1}(AP)\geq\operatorname{w}_{e_{3}}(AP)=\operatorname{w}_{r_{3}}(P)\geq\|h_{3}\|.$

∎

Let $P\subset\mathbb{R}^{3}$ be an empty lattice polytope. As we explained
above, it was shown in [12] that any such polytope $P$ is of lattice width one
and hence, using lattice equivalence, we can assume that
$\operatorname{w}_{e_{1}}(P)=1$. Let $\Pi_{0}=P\cap\\{x=0\\}$ and
$\Pi_{1}=P\cap\\{x=1\\}$. Then each of $\Pi_{0}$ and $\Pi_{1}$ is lattice-
equivalent to a point, a primitive segment, the standard simplex, or the unit
square $[0,1]^{2}$. Note the unimodular map

$A\begin{bmatrix}x\\\ y\\\ z\end{bmatrix}=\begin{bmatrix}1&0&0\\\ a&1&0\\\
b&0&1\end{bmatrix}\begin{bmatrix}x\\\ y\\\ z\end{bmatrix}$

fixes each point in the plane $x=0$ and shifts the plane $x=1$ by the vector
$(0,a,b)$. Hence, composing such maps with lattice translations, one can use
affine unimodular maps to independently shift $\Pi_{0}$ and $\Pi_{1}$ in the
planes $x=0$ and $x=1$ correspondingly. Note that if, say, $\Pi_{0}$ is a
vertex, we can apply a unimodular map that maps $\Pi_{1}$ inside the unit
square and then shift $\Pi_{0}$ so that $P\subset[0,1]^{3}$.

Each of the bases $\Pi_{0},\Pi_{1}$ of an empty lattice polytope $\Pi$ is a
either a lattice parallelogram of area 1 or is properly contained in such a
parallelogram. We next study some properties of such paralelograms.

######  Proposition 2.5.

Let $\Pi\subset\mathbb{R}^{2}$ be a lattice parallelogram of area 1. Then one
can shift $\Pi$ so that one of its vertices is at the origin and the entire
parallelogram $\Pi$ is contained in the first quadrant or in the second
quadrant.

###### Proof.

Shift $\Pi$ so that its lowest vertex is at the origin. If there are two
vertices at the lowest level, shift $\Pi$ so that one of them is at the
origin. Let $(a,b)$ and $(c,d)$ be the two vertices adjacent to the vertex at
the origin. If $\Pi$ is not entirely in the first or in the second quadrant,
then we may assume $a>0,b\geq 0$, while $c<0$ and $d\geq 0$. Since $\Pi$ is of
area 1 we have $1=ad-bc\geq d+b$, which implies that either $b=0,d=1$ or
$b=1,d=0$. (Note that we cannot have $b=d=0$.) In the first of these cases we
have $a=1$ and we can shift $\Pi$ left by 1 so that one of its vertices is at
the origin and $\Pi$ is contained in the second quadrant. In the second case,
we have $c=-1$ and we shift $\Pi$ right by 1 unit. The second statement also
follows. ∎

If we can shift $\Pi$ so that one of its vertices is at the origin and $\Pi$
is contained in the first quadrant, we say that $\Pi$ is positively oriented;
if we can shift $\Pi$ so that one of its vertices is at the origin and $\Pi$
is contained in the second quadrant, we say that $\Pi$ is negatively oriented.
Clearly, the only $\Pi$ which are both positively and negatively oriented are
translations of the unit square
$\operatorname{conv}\\{(0,0),(1,0),(0,1),(1,1)\\}$.

######  Proposition 2.6.

Let $a,b,c,d$ be non-negative integers and let $\det\begin{bmatrix}a&b\\\
c&d\end{bmatrix}=1$. Then

  * (i)

$a\geq b,c\geq d$ or

  * (ii)

$a\leq b,c\leq d$ or

  * (iii)

$\begin{bmatrix}a&b\\\ c&d\end{bmatrix}=\begin{bmatrix}1&0\\\
0&1\end{bmatrix}$.

###### Proof.

Suppose that $a>b$ but $c<d$. Then $1=ad-bc>bd-b(d-1)=b,$ so $b=0$ and
$a=d=1$. Also, $c\leq d-1=0$ implies $c=0$, so $\begin{bmatrix}a&b\\\
c&d\end{bmatrix}=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix}$. The case $a<b$,
$c>d$ is handled similarly. ∎

######  Proposition 2.7.

Let $\Pi\subset\mathbb{R}^{2}$ be a positively oriented lattice parallelogram
of area 1 with vertices $(0,0),(a,b),(c,d),(a+c,b+d)$, where $a,b,c,d\geq 0$
and $\Pi$ is not the unit square
$\operatorname{conv}\\{(0,0),(1,0),(0,1),(1,1)\\}$. Then the maximum and the
minimum of $x-y$, $x+y$, $x$, and $y$ are attained at $(0,0)$ and $(a+c,b+d)$.

###### Proof.

The statement about $x+y$, $x$, and $y$ is obvious. By Proposition 2.6, we
need to take care of two situations: when $a\geq b,c\geq d$ and when $a\leq
b,c\leq d$. In the first of these we have $0\leq a-b$ and and $0\leq c-d$,
which implies $a-b\leq(a-b)+(c-d)$ and $c-d\leq(a-b)+(c-d)$, so the minimum of
$x-y$ is attained at $(0,0)$, while the maximum is attained at $(a+c,b+d)$. In
the second situation the minimum and the maximum are swapped. ∎

######  Proposition 2.8.

Let $\Pi\subset\mathbb{R}^{2}$ be a negatively oriented lattice parallelogram
of area 1 with vertices $(0,0),(a,b),(c,d),(a+c,b+d)$, where $b,d\geq 0$,
while $a,c\leq 0$, and $\Pi$ is not the unit square
$\operatorname{conv}\\{(0,0),(-1,0),(0,1),(-1,1)\\}$. Then the maximum and the
minimum of $x$, $y$, $x+y$, and $x-y$ are attained at $(0,0)$ and $(a+c,b+d)$.

###### Proof.

This follows from Proposition 2.7 by reflecting $\Pi$ in the $y$-axis. ∎

Note that our definition of orientation extends naturally to primitive
segments and empty lattice triangles. We say that such a segment or triangle
$\Pi$ is positively/negatively oriented if we can shift $\Pi$ so that one of
its vertices is at the origin and $\Pi$ is contained in the first/second
quadrant correspondingly. Clearly, for a segment the orientation coincides
with the sign of its slope, with horizontal and vertical segments being both
positively and negatively oriented. Unless $\Pi$ is a shift of

$\operatorname{conv}\\{(0,0),(1,0),(1,1)\\},\
\operatorname{conv}\\{(0,0),(0,1),(1,1)\\}\ {\rm or}\
\operatorname{conv}\\{(0,0),(1,0),(0,1)\\},$

a positively oriented lattice triangle $\Pi$ after a shift has vertices
$(0,0),(a,b),(a+c,b+d)$, where $a,b,c,d\geq 0$ and the maximum and minimum of
$x$, $y$, $x-y$, and $x+y$ are attained at $(0,0)$ and $(a+b,c+d)$.

Similarly, unless $\Pi$ is a shift of
$\operatorname{conv}\\{(0,0),(0,1),(-1,1)\\}$,
$\operatorname{conv}\\{(0,0),(-1,0),(-1,1)\\}$, or
$\operatorname{conv}\\{(0,0),(-1,0),(0,1)\\}$, a negatively oriented lattice
triangle $\Pi$ after a shift has vertices $(0,0),(a,b),(a+c,b+d)$, where
$a,c\leq 0$ and $b,d\geq 0$ and the maximum and the minimum of $x$, $y$,
$x-y$, and $x+y$ are attained at $(0,0)$ and $(a+b,c+d)$.

######  Definition 2.9.

Let $\Pi$ be either an empty lattice triangle an empty lattice parallelogram,
and assume $\Pi$ is not contained in a shift of the unit square. Then we say
that the main vertices are the two vertices where the maximum and minimum of
$x,y$, $x+y$, $x-y$ are attained. In the case when $\Pi$ is a lattice segment,
we call both of its vertices main vertices.

Note that if we reflect $\Pi$ in the $x$ or $y$-axes, its main vertices are
mapped to the main vertices of the image. The observations that we made above
will allow us to treat empty lattice parallelograms and triangles as a lattice
segments connecting main vertices.

##  3\. Lattice Size of Empty Lattice Polytopes

######  Theorem 3.1.

Let $P\subset\mathbb{R}^{3}$ be an empty lattice polytope. Then there exists a
basis which is Minkowski reduced with respect to $P$ and computes the lattice
size $\operatorname{ls_{\Delta}}(P)$.

###### Proof.

Let the standard basis $(e_{1},e_{2},e_{3})$ be Minkowski reduced with respect
to $P$. Since $\operatorname{w}(P)=1$, we have $\|e_{1}\|=1$, $\|e_{2}\|=m$,
and $\|e_{3}\|=n$, where $1\leq m\leq n$.

If $n=1$, then we also have $m=1$, and hence $P$ is contained in the unit
cube. Then we have three options: $P$ is lattice-equivalent to the unit
simplex, in which case $\operatorname{ls_{\Delta}}(P)=1$; $P$ is the unit
cube, in which case $\operatorname{ls_{\Delta}}(P)=3$; and anything in
between, in which case we have $\operatorname{ls_{\Delta}}(P)=2$.

In what follows we assume that $n>1$. Denote $\Pi_{0}=P\cap\\{x=0\\}$ and
$\Pi_{1}=P\cap\\{x=1\\}$. Then we can assume that each of $\Pi_{0}$ and
$\Pi_{1}$ is a primitive segment, a lattice triangle of area 1/2, or a lattice
parallelogram of area 1, since if one of the $\Pi_{i}$ is a vertex, we can
unimodularly map the other inside the unit square and we would have $n=1$.

Assume first that $\Pi_{0}$ and $\Pi_{1}$ are of opposite orientation, say
$\Pi_{0}$ is positively oriented and $\Pi_{1}$ is negatively oriented.
Additionally, assume that each $\Pi_{0}$ and $\Pi_{1}$ has main vertices. Let
in $\Pi_{0}$ the main vertices be $(0,0,0)$ and $(0,\alpha,\beta)$, and in
$\Pi_{1}$, let these vertices be $(1,\gamma,0)$ and $(1,0,\delta)$, where
$\alpha,\gamma\in[0,m]$ and $\beta,\delta\in[0,n]$. Since $\|e_{2}\|=m$ and
$\|e_{3}\|=n$, and the non-main vertices cannot maximize or minimize $y$ or
$z$, we have $\alpha=m$ or $\gamma=m$ and $\beta=n$ or $\delta=n$.

Note that we can swap the two layers $x=0$ and $x=1$, swapping $\alpha$ with
$\gamma$ and $\beta$ with $\delta$ by applying

$\begin{bmatrix}-1&0&0\\\ 0&1&0\\\
\delta-\beta&0&-1\end{bmatrix}\begin{bmatrix}0&0&1&1\\\ 0&\alpha&\gamma&0\\\
0&\beta&0&\delta\end{bmatrix}+\begin{bmatrix}1\\\ 0\\\
\beta\end{bmatrix}=\begin{bmatrix}1&1&0&0\\\ 0&\alpha&\gamma&0\\\
\beta&0&\delta&0\end{bmatrix}$

Hence we can assume that we have $\delta=n$, which implies that $\gamma>0$ for
otherwise $[(1,\gamma,0),(1,0,\delta)]$ would not be primitive.

Since the standard basis is reduced we have $\|-\gamma e_{1}+e_{2}+e_{3}\|\geq
n$, which gives

$\max\\{0,\alpha+\beta,n-\gamma\\}-\min\\{0,\alpha+\beta,n-\gamma\\}\geq n.$

(Note that since we are minimizing and maximizing $(y+z)$ on each of the
layers here, only the main vertices matter.) Since $\gamma>0$, this condition
implies $\alpha+\beta\geq n$. Hence $\alpha>0$ since otherwise $\beta=n$ and
$[(0,0,0),(0,\alpha,\beta)]$ is not primitive.

Suppose first that $\alpha+\beta=n$. Then $l_{1}(P)=n+1$. Let’s show that in
this case we have $\operatorname{ls_{\Delta}}(P)=n+1$. For this, we look for
integer directions $(a,b,c)$ with $c\geq 0$ such that the lattice width of $P$
in such directions is at most $n$. We have

$\max\\{0,b\alpha+c\beta,a+b\gamma,a+cn\\}-\min\\{0,b\alpha+c\beta,a+b\gamma,a+cn\\}\leq\operatorname{w}_{(a,b,c)}(P)\leq
n.$

Plugging in $\beta=n-\alpha$ we get $b\alpha+c(n-\alpha)\leq n\ \ {\rm and}\ \
cn-b\gamma\leq n.$ If $c>1$ we get $n-b\gamma<cn-b\gamma\leq n$, so
$b\gamma>0$ and hence $b>0$ since we have $\gamma>0$. Also,

$b\alpha+(n-\alpha)<b\alpha+c(n-\alpha)\leq n$

implies $b\alpha<\alpha$ and hence $b<1$ since $\alpha>0$. We have shown that
$c=0$ or 1. This implies that if $l_{1}(T(P))=n$ then the last coordinate of
each of the rows of the corresponding unimodular matrix $A$ has last
coordinate equal to 0, 1, or $-1$. By Lemma 2.2, the same applies to the sum
of any two rows of $A$ as well as to the sum of all three rows. Hence up to
permuting the rows, we have two options for the last column of $A$:

$\pm\begin{bmatrix}0\\\ 0\\\ 1\end{bmatrix}\ {\rm and}\ \
\pm\begin{bmatrix}0\\\ -1\\\ 1\end{bmatrix},$

where by Lemma 2.1 we only need to consider the first option. Denote the rows
of $A$ by $h_{1},h_{2},$ and $h_{3}$. Since the standard basis is reduced and
$h_{3}$ is of the form $ae_{1}+be_{2}\pm e_{3}$ we have
$\operatorname{w}_{h_{3}}(P)=\|h_{3}\|\geq n$. Together with $T(P)\subset
n\Delta$, this implies that $(0,0,n)\in T(P)$. We also have
$\|h_{1}+h_{2}+h_{3}\|\geq n$ and hence $(0,0,0)\in T(P)$. Hence the entire
segment $[(0,0,0),(0,0,n)]$ is contained in $T(P)$. Since $P$ is empty and
$n>1$ we conclude that there is no such map $T$ and hence
$\operatorname{ls_{\Delta}}(P)=n+1$.

We can now assume that $\alpha+\beta\geq n+1.$ In this case we have
$l_{1}(P)=\alpha+\beta$. We also have $\gamma+\delta=n+\gamma\geq n+1$. If we
swap the layers $x=0$ and $x=1$, as explained above, we can unimodularly
inscribe $P$ inside $(\gamma+\delta)\Delta$. We now show that
$\operatorname{ls_{\Delta}}(P)=\min\\{\alpha+\beta,\gamma+\delta\\}$. Let
$(a,b,c)$ be an integer direction with $c\geq 0$ such that
$\|(a,b,c)\|<\min\\{\alpha+\beta,\gamma+\delta\\}$. Then

$\max\\{0,b\alpha+c\beta,a+b\gamma,a+cn\\}-\min\\{0,b\alpha+c\beta,a+b\gamma,a+cn\\}<\min\\{\alpha+\beta,\gamma+\delta\\}.$

If $c>1$ we get $b\alpha+\beta<b\alpha+c\beta<\alpha+\beta$, so
$b\alpha<\alpha$, and since $\alpha>0$ we conclude $b\leq 0$ . Using this, we
get $2n\leq cn\leq cn-b\gamma<n+\gamma$, which implies $n<\gamma$ and this
contradiction proves $c\leq 1$. If $c=1$, we have $b\alpha+\beta<\alpha+\beta$
and hence $b<1$. Also, $n-b\gamma<n+\gamma$, so $b>-1$, and we conclude that
$b=0$. We have checked that $c=0$ or 1 and in the case when $c=1$ we also have
$b=0$.

As before, if we have $l_{1}(T(P))<\min\\{\alpha+\beta,\gamma+\delta\\}$ we
can assume that the last column of the corresponding unimodular matrix $A$ is
the transpose of $\begin{bmatrix}0&0&\pm 1\end{bmatrix}$. Let the rows of $A$
be $h_{1},h_{2}$, and $h_{3}$. Then the last coordinate of
$h_{3},h_{1}+h_{3}$, and $h_{2}+h_{3}$ is 1 so by what we just showed and by
Lemma 2.2 the second component of each of these vectors is 0, so the entire
second column of $A$ would consist of all zeroes. We have checked that in this
case $\operatorname{ls_{\Delta}}(P)=\min\\{\alpha+\beta,\gamma+\delta\\}$.

We next consider the situation where at least one of the $\Pi_{i}$ does not
possess main vertices, that is, $\Pi_{i}$, up to a lattice shift, is either
the unit square or a triangle which is half of the unit square. If this
happens for both $\Pi_{0}$ and $\Pi_{1}$, we have $n=1$. Let us assume
$\Pi_{1}$ is either the unit square

$\operatorname{conv}\\{(1,0,0),(1,0,1),(1,1,0),(1,1,1)\\}$

or a triangle obtained by dropping one of its vertices, and that the main
vertices in $\Pi_{0}$ are $(0,\alpha,0)$ and $(0,0,\beta)$. Then since $n>1$
we have $\beta=n$. We also have $\alpha=m$. This is clear if $m\geq 1$. If
$m=1$, we cannot have $\alpha=0$ since then $[(0,\alpha,0),(0,0,\beta)]$ would
not be primitive.

We have
$\max\\{n,m,n-1,n+1\\}-\min\\{n,m,n-1,n+1\\}\geq\|(n-1)e_{1}+e_{2}+e_{3}\|\geq
n$. If $n>m$ we get $n+1-m\geq n$, which implies $m=1$. If $n\geq 3$ we get
$l_{1}(P)=n$ and hence by Lemma 2.4 we conclude that
$\operatorname{ls_{\Delta}}(P)=n$. If $n=2$, we have $l_{1}(P)=3$. Let
$(a,b,c)$ be an integer direction such that the lattice width of $P$ in this
direction is at most 2. As when showing above that
$\operatorname{ls_{\Delta}}(P)=n+1$ under the assumption that
$\alpha+\beta=n$, here one can easily check that $|c|\leq 1$ and there is no
unimodular map $T$ with $l_{1}(T(P))=n$.

It remains to consider the case when $\Pi_{0}$ and $\Pi_{1}$ are of the same
orientation. We can then assume that $\Pi_{0}$ and $\Pi_{1}$ are both oriented
positively. Shift $\Pi_{0}$ so that its main vertices are $(0,0,0)$ and
$(0,\alpha,\beta)$, where $0\leq\alpha\leq m$ and $0\leq\beta\leq n$. Shift
$\Pi_{1}$ so that its main vertices are at $(1,\gamma,\delta)$ and $(1,m,n)$,
where $0\leq\gamma\leq m$ and $0\leq\delta\leq n$.

We have $\alpha=m$ or $\gamma=0$ since otherwise we can shift $\Pi_{1}$ in
$x=1$ and decrease $\|e_{2}\|$. Similarly, we have $\beta=n$ or $\delta=0$.
Switching the layers $x=0$ and $x=1$, if necessary, we can assume that
$\beta=n$.

Since the standard basis is reduced, we have $\|e_{3}-e_{2}\|\geq n$. By
Proposition 2.7 this gives
$\max\\{0,n-\alpha,\delta-\gamma\\}-\min\\{0,n-\alpha,\delta-\gamma\\}\geq n$.
Since $n-\alpha\geq 0$ this implies
$\max\\{n-\alpha,\delta-\gamma\\}-\min\\{0,\delta-\gamma\\}\geq n$.

If this gives us $n-\alpha\geq n$, and then $\alpha=0$, which implies that
$\beta=1$ for otherwise $[(0,0,0),(0,\alpha,\beta)]$ is not primitive. Hence
$\Pi_{0}=[(0,0,0),(0,0,1)]$ is also negatively oriented and we have considered
this case earlier.

If the above gives $\delta-\gamma\geq n$ then $\delta=n$ and $\gamma=0$, so
$m=1$ and $\Pi_{1}=[(1,0,n),(1,1,1)]$ is negatively oriented, which we have
covered before.

Finally, if $n-\alpha-\delta+\gamma\geq n$ we get $\alpha+\delta\leq\gamma$.
Since $\alpha=m$ or $\gamma=0$, we have $\gamma\leq\alpha$ and hence
$\gamma+\delta\leq\alpha+\delta\leq\gamma$, so $\delta=0$ and $\alpha=\gamma$.
If $\alpha=\gamma=m$, we get $[(1,m,0),(1,m,n)]\subset\Pi_{1}$ and hence
$n=1$. If $\alpha=\gamma=0$ then $\Pi_{0}=[(0,0,0),(0,0,\beta)]$, so $\beta=1$
and $\Pi_{0}$ is again negatively oriented.

∎

Based on the above argument, we can compute the lattice size of an empty
lattice polytope $P$ using the following algorithm.

######  Algorithm 3.2.

Reduce the standard basis with respect to $P$, using Algorithm 3.11 from [7].
Pass to the corresponding Minkowski reduced basis, as explained in the
paragraph following Definition 2.3. For each of the eight matrices

$A=\begin{bmatrix}\pm 1&0&0\\\ 0&\pm 1&0\\\ 0&0&\pm 1\end{bmatrix},$

shift the bases $\Pi_{0}$ and $\Pi_{1}$ of $AP$ in the layers $x=0$ and $x=1$
so that each of them is in the corresponding positive $(y,z)$-octant and
touches the coordinate axes, and call the obtained polytope $Q$. Then
$\operatorname{ls_{\Delta}}(P)$ is the minimum of $l_{1}(Q)$ over the eight
matrices $A$.

To confirm that this algorithm outperforms the Brute Force Algorithm we ran 25
examples using Algorithm 3.2 and the Brute Force Algorithm. In all these
examples we randomly picked $a,b,c,$ and $d$ in the interval from 1 to 14,
checked if $ad-bc=\pm 1$, and if this was the case, computed the lattice size
of

$P=\begin{bmatrix}0&0&0&0&1&1&1&1\\\ 0&1&0&1&0&a&c&a+c\\\
0&0&1&1&0&b&d&b+d\end{bmatrix}$

using each of the two algorithms. The average running time for Algorithm 3.2
was 0.198 sec, while for the Brute Force Algorithm it was 1196.697 sec. For
the code and further details see Experiment2.mgm, [1].

##  4\. Another class of 3D polytopes of lattice width one

In the next proposition, we are working with the plane case, so now
$\Delta\subset\mathbb{R}^{2}$ is the standard 2-simplex. We show that if one
replaces unimodular matrices in the definition of
$\operatorname{ls_{\Delta}}(P)$ with nonsingular integer matrices, then this
will define the same object.

######  Proposition 4.1.

Let $P\subset\mathbb{R}^{2}$ be a lattice polygon. Then for any integer
nonsingular matrix $A$ of size 2 we have
$l_{1}(AP)\geq\operatorname{ls_{\Delta}}(P)$.

###### Proof.

Let $A=UDV$ be the Smith normal form for $A$. That is, $U$ and $V$ are
unimodular matrices and $D$ is an integer diagonal matrix with positive
entries on the diagonal. Then, since $U$ and $V$ are unimodular, we have
$\operatorname{ls_{\Delta}}(UDVP)=\operatorname{ls_{\Delta}}(DVP)$ and
$\operatorname{ls_{\Delta}}(VP)=\operatorname{ls_{\Delta}}(P)$. Since $D$ is
diagonal with positive integer entries on the diagonal and we can assume that
$VP$ contains the origin, we have $VP\subset DVP$ and hence
$\operatorname{ls_{\Delta}}(VP)\leq\operatorname{ls_{\Delta}}(DVP)$. Hence

$l_{1}(AP)\geq\operatorname{ls_{\Delta}}(AP)=\operatorname{ls_{\Delta}}(UDVP)=\operatorname{ls_{\Delta}}(DVP)\geq\operatorname{ls_{\Delta}}(VP)=\operatorname{ls_{\Delta}}(P).$

∎

######  Proposition 4.2.

Let $P\subset\mathbb{R}^{2}$ be a polygon in the $(x,y)$-plane of
$\mathbb{R}^{3}$. Let $\operatorname{ls_{\Delta_{2}}}(P)=l$, where
$\Delta_{2}$ is the standard simplex in the $(x,y)$-plane. Then
$\operatorname{ls_{\Delta}}(P)=l$, where $P$ is now considered as a subset of
$\mathbb{R}^{3}$, and $\Delta$ is the standard simplex in $\mathbb{R}^{3}$.

###### Proof.

Suppose that for

$A=\begin{bmatrix}a_{11}&a_{12}&a_{13}\\\ a_{21}&a_{22}&a_{23}\\\
a_{31}&a_{32}&a_{33}\end{bmatrix}\in{\rm{GL}(3,\mathbb{Z})}$

we have $l_{1}(AP)=l^{\prime}<l$ and hence $AP+v\subset\l^{\prime}\Delta$ for
some $v=(b_{1},b_{2},b_{3})\in\mathbb{Z}^{3}$.

Since $A$ is unimodular, at least one of the matrices
$\begin{bmatrix}a_{11}&a_{12}\\\ a_{21}&a_{22}\end{bmatrix}$,
$\begin{bmatrix}a_{11}&a_{12}\\\ a_{31}&a_{32}\end{bmatrix}$, and
$\begin{bmatrix}a_{21}&a_{22}\\\ a_{31}&a_{32}\end{bmatrix}$ is nonsingular.
We can assume that the determinant of $B:=\begin{bmatrix}a_{11}&a_{12}\\\
a_{21}&a_{22}\end{bmatrix}$ is nonzero. Let
$\pi:\mathbb{R}^{3}\to\mathbb{R}^{2}$ be the projection defined by
$(x,y,z)\mapsto(x,y)$. We have $\pi(AP+v)\subset\pi(l^{\prime}\Delta)$ and
hence $BP+(b_{1},b_{2})\subset l^{\prime}\Delta_{2}$, where $\Delta_{2}$ is
the standard unit simplex in the $(x,y)$-plane. Since
$\operatorname{ls_{\Delta_{2}}}(P)=l$ and $l^{\prime}<l$, this contradicts the
result of Proposition 4.1. ∎

######  Theorem 4.3.

Let $P\subset\mathbb{R}^{3}$ be a convex lattice polytope of lattice width one
enclosed between the planes $x=0$ and $x=1$. Denote

$B_{0}=P\cap\\{x=0\\}\ \ {\rm and}\ \ B_{1}=P\cap\\{x=1\\}.$

Consider $B_{0}$ and $B_{1}$ as subsets of the $(y,z)$-plane by ignoring the
$x$-coordinate and suppose that up to a lattice translation $B_{1}$ is
contained in the convex hull of the interior lattice points of $B_{0}$. Then
$\operatorname{ls_{\Delta}}(P)=\operatorname{ls_{\Delta_{2}}}(B_{0})$ and
there exists a reduced basis that computes $\operatorname{ls_{\Delta}}(P)$.

###### Proof.

Use a unimodular transformation to shift $B_{1}$ in the plane $x=1$ so that
its projection onto the plane $x=0$ along the $x$-axis is contained in the
convex hull of the interior lattice points of $B_{0}$. Next, reduce
$(e_{2},e_{3})$ with respect to $B_{1}$. We will still refer to the obtained
polytope and its bases as $P$, $B_{0}$ and $B_{1}$.

Since $\|e_{1}\|=1$, we have $\|e_{1}\|\leq\|e_{2}\|$ and
$\|e_{1}\|\leq\|e_{3}\|$. Since $(e_{2},e_{3})$ is reduced with respect to
$B_{0}$, and $B_{0}$ contains the projection of $B_{1}$, we have

$\|e_{3}\|=\operatorname{w}_{e_{3}}(P)=\operatorname{w}_{e_{3}}(B_{0})\geq\operatorname{w}_{e_{2}}(B_{0})=\operatorname{w}_{e_{2}}(P)=\|e_{2}\|.$

Next, since $B_{0}$ is contained in the plane $x=0$, we get

$\|e_{1}\pm e_{2}\|=\operatorname{w}_{e_{1}\pm
e_{2}}(P)\geq\operatorname{w}_{e_{1}\pm
e_{2}}(B_{0})=\operatorname{w}_{e_{2}}(B_{0})=\operatorname{w}_{e_{2}}(P)=\|e_{2}\|.$

Finally, for $m,n\in\mathbb{Z}$, we get

$\displaystyle\|me_{1}+ne_{2}+e_{3}\|$
$\displaystyle=\operatorname{w}_{me_{1}+ne_{2}+e_{3}}(P)\geq\operatorname{w}_{me_{1}+ne_{2}+e_{3}}(B_{0})$
$\displaystyle=\operatorname{w}_{ne_{2}+e_{3}}(B_{0})\geq\operatorname{w}_{e_{3}}(B_{0})=\operatorname{w}_{e_{3}}(P)=\|e_{3}\|.$

We have checked that the standard basis is reduced with respect to the
obtained $P$.

Denote $l=\operatorname{ls_{\Delta_{2}}}(P)$. By Proposition 4.2 we have

$\operatorname{ls_{\Delta}}(P)\geq\operatorname{ls_{\Delta}}(B_{0})=\operatorname{ls_{\Delta_{2}}}(B_{0})=l.$

Shifting $P$, if necessary, we can assume that $B_{0}\subset l\Delta$. Since
the projection of $B_{1}$ is contained in the convex hull of the interior
lattice points of $B_{0}$, we also have $B_{0}\subset l\Delta$ and it follows
that $P\subset l\Delta$ Hence $\operatorname{ls_{\Delta}}(P)\leq l$ and we
have checked that $\operatorname{ls_{\Delta}}(P)=l$. ∎

Note that Algorithm 3.2 computes the lattice size for the lattice polytopes
$P$ of lattice width one described in Theorem 4.3.

##  5\. Computer Experimentation and Counterexample

In light of our results proved in Theorems 3.1 and 4.3 it is natural to ask
whether it is true that for any lattice polytope $P\subset\mathbb{R}^{3}$ of
lattice width one there exists a reduced basis that computes its lattice size
$\operatorname{ls_{\Delta}}(P)$.

To test this question, we developed and implemented in Magma a procedure (see
ComputeLSReducton.mgm in [1]), where we first reduce the standard basis
$(e_{1},e_{2},e_{3})$ with respect to $P$ using Algorithm 3.11 from [7], and
then search through reduced bases of the form $(\pm e_{1},ae_{1}\pm
e_{2},be_{1}+ce_{2}\pm e_{3})$ to minimize $l_{1}(AP)$ over the corresponding

$A=\begin{bmatrix}\pm 1&0&0\\\ a&\pm 1&0\\\ b&c&\pm 1\end{bmatrix}.$

We then compare this minimum with the lattice size
$\operatorname{ls_{\Delta}}(P)$ computed using the Brute Force Algorithm
described in the Introduction. See Experiment3.mgm in [1] for the code related
to the described experimentation.

We tested 5,000 polytopes $P$ whose bases $P_{0}\subset\\{x=0\\}$ and
$P_{1}\subset\\{x=0\\}$ are picked as convex hulls of $n_{0}$ and $n_{1}$
random points $(y,z)\in\mathbb{R}^{2}$ correspondingly, that satisfy $|y|\leq
7$ and $|z|\leq 7$. The numbers of points $n_{0}$ and $n_{1}$ in each of the
planes were picked randomly in the interval from 3 to 10. We also tested 5,000
additional examples where we replaced the bound of 7 with 3 and $n_{0}$ and
$n_{1}$ were picked randomly between 3 and 7. In all of the 10,000 examples,
except two, we found a reduced basis of $P$ that computes
$\operatorname{ls_{\Delta}}(P)$. We now explain one of these two examples.

######  Example 5.1.

Let
$P=\operatorname{conv}\\{(0,2,5),(0,-2,5),(0,1,-6),(1,-8,5),(1,2,-5),(1,-4,-3)\\}$.
We ran the Brute Force Algorithm (see BruteForceOriginal.mgm) to find that
$\operatorname{ls_{\Delta}}(P)=13$. One of the matrices that gives this answer
is

$\begin{bmatrix}1&0&0\\\ 2&-1&0\\\ 7&2&1\end{bmatrix}.$

For this $P$, our procedure, implemented in ComputeLSReducton.mgm, returned
the answer of 14. The standard basis in this example is reduced and the norms
of the vectors in a Minkowski reduced basis are 1, 10, and 11. Since there is
no guarantee that our procedure searches through all possible reduced bases,
we next found all the primitive vectors with such norms, and then considered
all unimodular matrices $A$ with rows $h_{1},h_{2}$ and $h_{3}$ that satisfy
$\|h_{1}\|=1$, $\|h_{2}\|=10$, $\|h_{3}\|=11$. We then minimized $l_{1}(AP)$
over all such matrices $A$ and confirmed that the minimum is indeed 14 using
CheckReducedBruteForce.mgm in [1].

Note that in this example we have $\|h_{3}\|\geq\|h_{1}\|+\|h_{2}\|$ and hence
it follows from the comment after Definition 1.5 that for this $P$ any reduced
basis is also Minkowski reduced. We conclude that we have searched through all
the reduced bases and hence for this $P$ there is no reduced basis that
computes its lattice size.

We conclude that one cannot use basis reduction to compute
$\operatorname{ls_{\Delta}}(P)$ for lattice polytopes $P\subset\mathbb{R}^{3}$
with $\operatorname{w}(P)=1$. According to our experimentation, such examples
of lattice polytopes $P$ with $\operatorname{w}(P)=1$ for which there is no
reduced basis that computes $\operatorname{ls_{\Delta}}(P)$ are quite rare: We
only found two such $P$ among 10,000 random examples.

While basis reduction is not guaranteed to compute the lattice size, one can
compute the lattice size using basis reduction in combination with the Brute
Force Algorithm to reduce the running time. For this, one can first reduce the
standard basis with respect to $P$ and then run the Brute Force Algorithm.
This speeds up the algorithm: In our experimentation, see Experiment4.mgm,
[1], the average time of the lattice size computation on 100 random lattice
polytopes $P$ with $\operatorname{w}(P)=1$ ran with the Brute Force Algorithm
was 103 sec, while the average time on the same polytopes when we first
reduced the basis was 34 sec. Here each $P$ is the convex hull of two polygons
$P_{0}$ and $P_{1}$ in the planes $x=0$ and $x=1$ correspondingly, picked as
convex hulls of $n_{0}$ and $n_{1}$ random points in the $(y,z)$-plane with
the magnitude of the components bounded by 7, where each $n_{0}$ and $n_{1}$
is picked randomly between 3 and 10.

## References

  * [1] A. Alajmi and J. Soprunova, Accompanying Magma package, // https://github.com/esoprun/Lattice-Size-Empty.
  * [2] V. Arnold, Statistics of integral convex polygons, Functional Analysis and Its Applications 14(2) (1980), pp. 1-3.
  * [3] A. Barvinok, Integer Points in Polyhedra, Zurich Lectures in Advanced Mathematics, ISBN: 9783037190524, 2008.
  * [4] I. Bárány and J. Pach, On the number of convex lattice polygons, Combinatorics, Probability and Computing 1, Issue 4 (1992), pp. 295-302.
  * [5] G. Brown and A. Kasprzyk, Small polygons and toric codes, Journal of Symbolic Computation, 51 (2013), pp. 55-62.
  * [6] W. Castryck and F. Cools, The lattice size of a lattice polygon, Journal of Combinatorial Theory Series A 136, Issue C (2015), pp. 64-95.
  * [7] A. Harrison and J. Soprunova, Lattice Size and Generalized Basis Reduction in Dimension 3, Discrete Comput Geom (2021), https://doi.org/10.1007/s00454-020-00269-x.
  * [8] A. Harrison, J. Soprunova, and P. Tierney, Lattice Size of Plane Convex Bodies, to appear in SIAM J. Discrete Math.
  * [9] M. Kaib and C. Schnorr, The Generalized Gauss Reduction Algorithm, Journal of Algorithms 21(3), (1996), pp. 565-578.
  * [10] J. Lagarias and G. Ziegler, Bounds for lattice polytopes containing a fixed number of interior points in a sublattice, Canadian Journal of Mathematics 43(5) (1991), pp. 1022-1035.
  * [11] L. Lovász and H. Scarf, The Generalized Basis Reduction Algorithm, Mathematics of Operations Research 17, Issue 3 (1992), pp. 751-764.
  * [12] H. E. Scarf, Integral polyhedra in three space, Mathematics of Operations Research 10, no. 3, 403-438 (1985).
  * [13] J. Schicho, Simplification of surface parametrizations – a lattice polygon approach, Journal of Symbolic Computation 36(3-4) (2003), pp. 535-554.
  * [14] J.Soprunova, Lattice Size and Area of Plane Convex Bodies, arXiv:2112.15134.
  * [15] G. White, Lattice Tetrahedra, Canadian J. Math. 16, 389-396, (1964).