# Max-convolution through numerics and tropical geometry

Taylor Brysiewicz  Western University, Department of Mathematics, London, ON,
N6A 5B7 Canada<EMAIL_ADDRESS>,  Jonathan D. Hauenstein  University of Notre
Dame, Department of Applied and Computational Mathematics and Statistics,
Notre Dame, IN 46556 USA<EMAIL_ADDRESS>and  Caroline Hills  University of
Notre Dame, Department of Applied and Computational Mathematics and
Statistics, Notre Dame, IN 46556 USA<EMAIL_ADDRESS>
###### Abstract.

The maximum function, on vectors of real numbers, is not differentiable.
Consequently, several differentiable approximations of this function are
popular substitutes. We survey three smooth functions which approximate the
maximum function and analyze their convergence rates. We interpret these
functions through the lens of tropical geometry, where their performance
differences are geometrically salient. As an application, we provide an
algorithm which computes the max-convolution of two integer vectors in quasi-
linear time. We show this algorithm’s power in computing adjacent sums within
a vector as well as computing service curves in a network analysis
application.

##  1\. Introduction

Given $v=(v_{1},\dots,v_{n})\in\mathbb{R}^{n}$, although computing the maximum
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}M}=\max_{1\leq
i\leq n}v_{i}$ is an elementary task, the function $v\mapsto\max(v)$ is not
differentiable. A common technique used in optimization [15, 16] and machine
learning [1, 7] is to replace the precise computation of $M$ with an
approximate computation. This article investigates three standard ways to
smoothly approximate the maximum function. Equipped with

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}F_{v}(t)}=\sum_{j=1}^{n}t^{v_{j}},\leavevmode\nobreak\
\leavevmode\nobreak\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}L_{v}(t)}=\log_{t}(F_{v}(t)),\leavevmode\nobreak\
\leavevmode\nobreak\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}R_{v}(t)}=\dfrac{tF_{v}^{\prime}(t)}{F_{v}(t)},\leavevmode\nobreak\
\leavevmode\nobreak\ \hbox{and}\leavevmode\nobreak\ \leavevmode\nobreak\
{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}||v||_{p}}=\left(\sum_{j=1}^{n}|v_{j}|^{p}\right)^{\frac{1}{p}},$

we consider the approximations:

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(LogSumExp)}}:\quad\quad
M=\displaystyle\lim_{t\to\infty}L_{v}(t)\quad\quad\quad\quad\quad\quad\quad{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{(Ratio)}}:\quad\quad
M=\displaystyle\lim_{t\to\infty}R_{v}(t)$

and, if each entry of $v$ is non-negative,

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{($p$-norm)}}:\quad\quad
M=\displaystyle\lim_{p\to\infty}||v||_{p}=||v||_{\infty}.$

We drop the subscript $v$ when the vector of interest is clear from context.

Figure 1. Plots of the values of the smooth approximations $L(t),||v||_{p}$,
and $R(t)$ for the vectors $v_{1}=(1,2,3,4,5,6,7)$ and
$v_{2}=(1,2,3,4,5,6,7,7,7,7,7,7)$. These values are plotted against the
natural logarithm of the largest absolute value $T$ of a floating point number
involved in the numerical evalutation of each function.

When $t>0$, the functions $L_{v}(t)$ and $R_{v}(t)$ are smooth as a function
of $v$ and approximate $M$ as shown by the limits above. For
$p\in\mathbb{R}_{>0}$, the function $||v||_{p}$ smoothly approximates $M$
provided that each element of $v$ is non-negative. Each of these functions can
be expressed in terms of

(1)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{L}_{v}(t)}=\log(F_{v}(t)).$

######  Proposition 1.1.

For $v=(v_{1},\ldots,v_{n})\in\mathbb{R}^{n}$, $t\in\mathbb{R}$ with $t>1$, we
have
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}u}=\log(t)>0$,
and

(2) $\displaystyle L_{v}(t)=L_{v}(e^{u})$
$\displaystyle=\frac{1}{u}\mathcal{L}_{v}(e^{u})$ (3) $\displaystyle
R_{v}(t)=R_{v}(e^{u})$ $\displaystyle=\frac{d}{du}\mathcal{L}_{v}(e^{u})$ (4)
$\displaystyle||v||_{\log(t)}=||v||_{u}$
$\displaystyle=e^{L_{\log|v|}(t)}=e^{\frac{1}{u}\mathcal{L}_{\log|v|}(e^{u})}$

where
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\log|\cdot|}:\mathbb{R}^{n}\to\mathbb{R}^{n}$
is the componentwise log-absolute value map.

After providing some basic notation in Section 2, we derive convergence rates
for each of these functions in Section 3 by analyzing $\mathcal{L}_{v}(t)$.
Namely, for $\delta>0$, we give bounds on $t$ for which the absolute error of
these approximations is smaller than $\delta$. As a consequence, when the
vector $v$ is integral, one may use a rounding procedure, such as the floor or
ceiling function, to provably compute $M$ via a single evaluation of an
approximating function.

In practice, when the entries of $v$ are selected from a discrete set, such as
the integers $\mathbb{Z}$, the maximum $M$ is often obtained more than once.
The number of times $M$ is attained is the _multiplicity_ of $M$ in $v$,
namely

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mu_{M}}=\\#\\{i\leavevmode\nobreak\
|\leavevmode\nobreak\ v_{i}=M\\}.$

When the multiplicity of $M$ is large, the ratio approximation significantly
outperforms the other approximations (see Section 5). In Section 3, we express
$\mu_{M}$ as a limit of the aforementioned functions and derive analogous
convergence rates result for computing $\mu_{M}$.

In light of part (3) of Proposition 1.1, we generalize the approximation
$R_{v}(t)$ using higher-order derivatives. In particular, for $k\geq 1$, we
define

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}R_{v}^{(k)}(t)}=-\frac{(-t)^{k}}{(k-1)!}\frac{d^{k}}{dt^{k}}\mathcal{L}_{v}(t).$

Observe that
$R_{v}^{(1)}(t)=R_{v}^{(1)}(e^{u})=\frac{d}{du}\mathcal{L}_{v}(e^{u})=R_{v}(e^{u})=R_{v}(t)$.
We show, in Section 3, that every $R_{v}^{(k)}(t)$ for $k\geq 1$ converges to
$M$ at the same rate. We discuss how to use these higher-order derivatives to
numerically approximate other information about $v$ (see Theorem 3.11).

In Section 4, we explore the geometry of $L_{v}(t)$ and $R^{(k)}_{v}(t)$ in
terms of objects called amoebas from the world of tropical geometry. We
realize the graph of the function $u\mapsto\mathcal{L}_{v}(e^{u})$ as the
upper boundary of a certain amoeba and provide a geometric interpretation of
the performance differences of $R_{v}(t)$ and $L_{v}(t)$ when $\mu_{M}$ is
large.

In Section 5, we conduct a series of experiments showcasing our theoretical
results and the performance differences of the approximation techniques
discussed. In particular, we provide empirical evidence showing the extent to
which the bounds derived in Section 3 are tight. We illustrate how the ratio
approximations perform significantly better than the others when the maximum
appears with non-trivial multiplicity and that this feature persists in the
presence of a noisy model.

In Section 6, we propose an algorithm for the max-convolution problem:

MAXCON: $\displaystyle\text{Given
}a=(a_{0},\dots,a_{n})\in\mathbb{Z}^{n+1}\hbox{\leavevmode\nobreak\
and\leavevmode\nobreak\ }b=(b_{0},\dots,b_{n})\in\mathbb{Z}^{n+1},$ (5)
$\displaystyle\text{compute
}c=(c_{0},\dots,c_{2n})\in\mathbb{Z}^{2n+1}\hbox{\leavevmode\nobreak\ where}$
$\displaystyle c_{k}=\max_{\max\\{0,k-n\\}\leq
i\leq\min\\{k,n\\}}(a_{i}+b_{k-i}).$

Since each $c_{k}$ is a maximum of the integer vector
$v^{(k)}=(a_{i}+b_{k-i})_{i=\max\\{0,k-n\\}}^{\min\\{k,n\\}}$ its value may be
determined by an (appropriately large) evaluation of an approximation of that
maximum. In particular, any algorithm which computes classical convolution
coefficients may be used as an oracle for evaluating $L_{v^{(k)}}(t)$. The
fast Fourier transform, for example, performs such a computation using
$O(n\log(n))$ operations. By combining this fact with our bounds from Section
3, we obtain a quasi-linear time algorithm for the max-convolution problem. We
end by applying our numerical approach to the maximum consecutive subsums
problem and and the computation of service curve constraints.

##  2\. Notation and Fundamental Results

We begin by fixing the following notation

$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v=(v_{1},\ldots,v_{n}):}$
$\displaystyle\text{ an }n\text{-tuple of real numbers}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}M:}$
$\displaystyle\,\,\max(v)$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mu_{c}:}$
$\displaystyle\text{ multiplicity of a real number }c\text{ in }v,\text{ i.e.,
}\\#\\{i\leavevmode\nobreak\ |\leavevmode\nobreak\ v_{i}=c\\}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\ell:}$
$\displaystyle\text{ number of distinct elements in }v$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w=(w_{1},\ldots,w_{\ell}):}$
$\displaystyle\text{ decreasing list of unique elements in }v\text{ i.e.,
}M=w_{1}>\cdots>w_{\ell}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}g=(g_{1},\ldots,g_{\ell}):}$
$\displaystyle\,\,g_{i}=M-w_{i}\text{ with }0=g_{1}<g_{2}<\cdots<g_{\ell}.$

Additionally,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}t}$ will
denote a variable which takes on positive real values whereas
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}u}=\log(t)$
is its image under the natural logarithm.

######  Example 2.1.

To illustrate notation, consider
$v=(7,7,-1,0,1,1,2.5,2.5,7,7)\leavevmode\nobreak\ \in\leavevmode\nobreak\
\mathbb{R}^{10}$.

$M=7,\quad\ell=5,$
$\mu_{7}=4,\quad\mu_{2.5}=2,\quad\mu_{1}=2,\quad\mu_{0}=1,\quad\mu_{-1}=1,$
$w=(7,2.5,1,0,-1),\quad g=(0,4.5,6,7,8).$

In principle, the elements of $v$ can be any real numbers. However, in
practice, they are usually some rational floating point approximations, that
is, $v\in\mathbb{Q}^{n}$. Moreover, we may assume for our analyses that
$v\in\mathbb{Z}^{n}$ since evaluating $\mathcal{L}_{v}(t)$ at a power $t^{k}$
of $t$ corresponds to scaling $v$ by $k$:

(6)
$\mathcal{L}_{v}(t^{k})=\mathcal{L}_{v}(e^{ku})=\mathcal{L}_{kv}(e^{u})=\mathcal{L}_{kv}(t).$

######  Remark 2.2.

We note that $\mathcal{L}_{v}(t)=\mathcal{L}_{uv}(e)$. The function
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textrm{lse}(v)}=\mathcal{L}_{v}(e)$
is a popular activation function in the field of machine learning
traditionally called the _log-sum-exp_ function [10]. Numerical methods for
accurately evaluating it may be found in [3].

The following expansion of $\mathcal{L}_{v}(t)$ near $t=\infty$ is fundamental
for our analysis.

######  Proposition 2.3.

For $v\in\mathbb{Z}^{n}$, $\mathcal{L}_{v}(t)$ near $t=\infty$ has the
following expansion:

(7) $\displaystyle\mathcal{L}_{v}(t)$
$\displaystyle=\log(t)M+\log(\mu_{M})+\log\left(\sum_{i=1}^{\ell}\frac{\mu_{w_{i}}}{\mu_{M}}t^{-g_{i}}\right)$

where the first term inside the logarithm is
$\frac{\mu_{w_{1}}}{\mu_{M}}t^{-g_{1}}=1$. In particular, by expanding the
logarithmic term, there exists nonnegative real numbers
$\\{\alpha_{j}\\}_{j=1}^{\infty}$ such that

(8) $\displaystyle\mathcal{L}_{v}(t)$
$\displaystyle=\log(t)M+\log(\mu_{M})+\sum_{j=1}^{\infty}\alpha_{j}t^{-j}$ (9)
$\displaystyle=uM+\log(\mu_{M})+\sum_{j=1}^{\infty}\alpha_{j}e^{-ju}$

where $\alpha_{1}=\cdots=\alpha_{g_{2}-1}=0$ and
$\alpha_{g_{2}}=\dfrac{\mu_{w_{2}}}{\mu_{M}}$.

We obtain similar expressions for $L_{v}(t)$, $R_{v}(t)$, and $R_{v}^{(k)}(t)$
by combining Propositions 1.1 and 2.3.

######  Proposition 2.4.

For $v\in\mathbb{Z}^{n}$, let $\\{\alpha_{j}\\}_{j=1}^{\infty}$ be as in
Proposition 2.3. Then, near $t=\infty$:

(10) $\displaystyle L_{v}(t)$
$\displaystyle=M+\log_{t}(\mu_{M})+\log_{t}\left(\sum_{i=1}^{\ell}\frac{\mu_{w_{i}}}{\mu_{M}}t^{-g_{i}}\right)$
$\displaystyle=M+\frac{1}{\log(t)}\left(\log(\mu_{M})+\sum_{j=1}^{\infty}\alpha_{j}t^{-j}\right)$
$\displaystyle=M+\frac{1}{u}\left(\log(\mu_{M})+\sum_{j=1}^{\infty}\alpha_{j}e^{-ju}\right),$
(11) $\displaystyle R_{v}(t)$
$\displaystyle=M-\sum_{j=1}^{\infty}j\alpha_{j}t^{-j}$
$\displaystyle=M-\sum_{j=1}^{\infty}j\alpha_{j}e^{-ju},$ (12) $\displaystyle
R_{v}^{(k)}(t)$
$\displaystyle=M-\sum_{j=1}^{\infty}j\binom{j+k-1}{k-1}\alpha_{j}t^{-j}$
$\displaystyle=M-\sum_{j=1}^{\infty}j\binom{j+k-1}{k-1}\alpha_{j}e^{-ju}.$

In particular, $R_{v}(t)$ and, more generally, $R_{v}^{(k)}(t)$ are analytic
at $t=\infty$. Additionally, if each $v_{i}\geq 0$,

(13) $\displaystyle||v||_{\log(t)}$ $\displaystyle=e^{L_{\log|v|}(t)}=M\cdot
e^{L_{\log|v|}(t)-\log(M)}.$

Clearly, $L_{v}(t)\geq M$ and the $\log_{t}(\mu_{M})$ term from (10) is
responsible for a slow convergence rate of $L_{v}(t)$ to $M$. This logarithmic
term is eliminated in $R_{v}(t)$ and, more generally, in $R_{v}^{(k)}(t)$. See
Section 4 for a geometric explanation of this fact.

######  Remark 2.5.

Since $R_{v}(t)$ and, more generally, $R_{v}^{(k)}(t)$ are analytic at
$t=\infty$ when $v\in\mathbb{Z}^{n}$, Cauchy’s integral formula yields that
for each $k\geq 1$ there exists $r>0$ such that

(14) $\frac{1}{2\pi\sqrt{-1}}\oint_{|t|=r}t^{-1}\cdot R_{v}^{(k)}(t^{-1})\cdot
dt=M.$

Numerically, one can use the trapezoid rule [13] to approximate $M$ from this
integral.

Since $R_{v}(t)$ depends on $F_{v}^{\prime}(t)$ which may be difficult to
evaluate in practice (see Section 6), we show below how to approximate
$R_{v}(t)$ from evaluations of $L_{v}(t)$.

######  Proposition 2.6.

For $v\in\mathbb{R}^{n}$, $t>1$, and $\alpha>0$ with $\alpha\neq 1$, define

(15)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}D_{v}(t,\alpha)}=\log_{\alpha}\left(\frac{F_{v}(\alpha\cdot
t)}{F_{v}(t)}\right)=\frac{\mathcal{L}_{v}(\alpha\cdot
t)-\mathcal{L}_{v}(t)}{\log(\alpha)}.$

Then,

$\lim_{\alpha\rightarrow 1}D_{v}(t,\alpha)=R_{v}(t).$

###### Proof.

Applying l’Hôpital’s rule yields $\lim_{\alpha\rightarrow
1}D_{v}(t,\alpha)=\lim_{\alpha\rightarrow 1}R_{v}(\alpha\cdot t)=R_{v}(t).$ ∎

##  3\. Approximating quantities associated to $v$

Equipped with the expansions (10)–(13) and (15), the functions $L_{v}(t)$,
$R_{v}^{(k)}(t)$, $D_{v}(t,\alpha)$, and $||v||_{u}$ may each be used to
approximate certain information about $v$, such as $M$, $\mu_{M}$, and
$g_{2}$.

For each such approximation of $M$, we derive a lower bound on $t$ so that the
absolute error is less than a given value $\delta>0$. For integer vectors, we
pay particular attention to the case where $\delta=1$, since one can use the
floor
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lfloor\cdot\rfloor}$
and ceiling
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lceil\cdot\rceil}$
functions to _provably_ compute these values from their approximations.

###  3.1. Computing the maximum

We derive bounds on the absolute errors of $L_{v}(t)$, $R_{v}(t)$,
$D_{v}(t,\alpha)$, and $||v||_{u}$ in Theorems 3.1, 3.3, 3.6, and 3.7
respectively.

######  Theorem 3.1.

Fix $v\in\mathbb{Q}^{n}$ and $\delta>0$. Then $0\leq L_{v}(t)-M<\delta$
whenever $t>1$ and

$t^{\delta+g_{2}}-t^{g_{2}}\mu_{M}-(n-\mu_{M})>0.$

If $v\in\mathbb{Z}^{n}$ and $\delta=1$, this bound is obtained when

$t>\frac{\mu_{M}+\sqrt{\mu_{M}^{2}+4(n-\mu_{M})}}{2}.$

If additionally $\mu_{M}=1$ then this bound simplifies to
$t>\dfrac{1}{2}+\sqrt{n}$.

###### Proof.

Assume, after reindexing, that $v_{1}=\cdots=v_{\mu_{M}}=M$. Thus,

$L_{v}(t)-M=\log_{t}\left(\mu_{M}+\sum_{j=\mu_{M}+1}^{n}t^{v_{j}-M}\right).$

Hence, $L_{v}(t)-M<\delta$ provided that the expression within the logarithm
is smaller than $t^{\delta}$. Since the function $t^{x}$ is monotonic for
$t>1$,

$\mu_{M}+\sum_{j=\mu_{M}+1}^{n}t^{v_{j}-M}\leq\mu_{M}+(n-\mu_{M})t^{-g_{2}},$

completing the proof of the first statement since this value is less than
$t^{\delta}$ when

$t^{\delta}>\mu_{M}+(n-\mu_{M})t^{-g_{2}}.$

For $v\in\mathbb{Z}^{n}$, we have that $g_{2}\geq 1$ so that a sufficient
condition when $\delta=1$ is

$t^{2}-\mu_{M}t-(n-\mu_{M})>0$

yielding the second statement. The third statement follows immediately. ∎

When $v$ consists of integers and $\mu_{M}$ is known, Theorem 3.1 suggests an
algorithm which provably computes $M$ using one evaluation of $L_{v}(t)$:

_Return $\lfloor L_{v}(t)\rfloor$ for $t$ satisfying the inequality
$2t>\mu_{M}+\sqrt{\mu_{M}^{2}+4(n-\mu_{M})}$. _

The largest $t$ value required is when $\mu_{M}=n$ for which one can take
$t=n+1$. In particular, for any $v\in\mathbb{Z}^{n}$, one always has $\lfloor
L_{v}(n+1)\rfloor=M$.

Figure 2. The graphs of $L_{v_{1}}(t)$ and $L_{v_{2}}(t)$ as in Example 3.2.

The following example illustrates Theorem 3.1 on qualitatively different
input.

######  Example 3.2.

Consider the following integer vectors:

$v_{1}=(1,2,3,4,5,6,7)\hskip 18.06749pt\text{and}\hskip
18.06749ptv_{2}=(1,2,3,4,5,6,7,7,7,7,7).$

The maximum of both vectors is $7$ which has multiplicity $1$ and $5$ in
$v_{1}$ and $v_{2}$, respectively. By Theorem 3.1, $L_{v_{1}}(t)\in[7,8)$ when
$t>3$ and $L_{v_{2}}(t)\in[7,8)$ when $t>6$. Figure 2 displays a verification
of these bounds and illustrates the reduced convergence rate for $v_{2}$ due
to the increased multiplicity of the maximum.

The worst-case scenario analysis for $R_{v}(t)$ is qualitatively distinct from
that of $L_{v}(t)$. The fact which distinguishes these cases is that for a
fixed $t>1$, the function $x\mapsto xt^{-x}$ is decreasing only after reaching
its maximum on $\mathbb{R}_{>0}$ at $x=\log(t)^{-1}$.

######  Theorem 3.3.

Fix $v\in\mathbb{Q}^{n}$ and $\delta>0$. Then $0\leq M-R_{v}(t)<\delta$ when
$t>e^{1/g_{2}}$ and

$t>\left(\frac{(n-\mu_{M})g_{2}}{\delta\cdot\mu_{M}}\right)^{\frac{1}{g_{2}}}.$

If $v\in\mathbb{Z}^{n}$ and $\delta=1$, this bound is obtained when

$t>\max\left(e,\frac{n-\mu_{M}}{\mu_{M}}\right).$

###### Proof.

From (11), a worst-case analysis with $t>e^{\frac{1}{g_{2}}}$ shows that

$M-R_{v}(t)=\sum_{j=1}^{\infty}j\alpha_{j}t^{-j}<\frac{n-\mu_{M}}{\mu_{M}}g_{2}t^{-g_{2}}.$

Therefore, the main result follows from

$M-R_{v}(t)<\delta\quad\quad\text{whenever}\quad\quad
t^{g_{2}}>\frac{(n-\mu_{M})g_{2}}{\delta\cdot\mu_{M}}.$

When $v\in\mathbb{Z}^{n}$ and $\delta=1$, this simplifies to
$t^{g_{2}}>\frac{(n-\mu_{M})g_{2}}{\mu_{M}}$. Since $t>e$ and $g_{2}\geq 1$,
this holds if additionally

$t>\frac{n-\mu_{M}}{\mu_{M}}.$

∎

######  Example 3.4.

For $v_{1}$ and $v_{2}$ as in Example 3.2, Figure 3 compares the graphs of
$L(t)$ and $R(t)$. Note that Theorems 3.1 and 3.3 guarantee that
$L_{v_{2}}(t)\in[7,8)$ when $t>6$ and $R_{v_{2}}(t)\in(6,7]$ when $t>e\approx
2.718$.

Figure 3. The graphs of $L(t)$ and $R(t)$ applied to $v_{1}$ and $v_{2}$ from
Example 3.2.

######  Remark 3.5.

For $v\in\mathbb{Z}^{n}$, one has

$L_{v}(t)-M=\left\\{\begin{array}[]{ll}O(1/\log(t))&\hbox{\leavevmode\nobreak\
\leavevmode\nobreak\ if\leavevmode\nobreak\ }\mu_{M}>1,\\\
O(t^{-g_{2}}/\log(t))&\hbox{\leavevmode\nobreak\ \leavevmode\nobreak\
if\leavevmode\nobreak\ }\mu_{M}=1,\end{array}\right.\hbox{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
}M-R_{v}(t)=O(t^{-g_{2}}).$

When $\mu_{M}=1$, Thereom 3.1 requires $t=O(\sqrt{n})$ while Theorem 3.3
requires $t=O(n)$. However, the bound $\frac{n-\mu_{M}}{\mu_{M}}$ from Theorem
3.3 is smaller than the bound
$\frac{\mu_{M}+\sqrt{\mu_{M}^{2}+4(n-\mu_{M})}}{2}$ from Theorem 3.1 whenever
$\mu_{M}\geq\frac{1}{4}(\sqrt{8n+1}-1)$. For reference, this means that

$(n,\mu_{M})\in\\{(10,2),(105,7),(1081,23),(10153,71),(100576,224),\ldots\\}$

are afforded equal $t$-bounds for $L_{v}(t)$ or $R_{v}(t)$ via Theorems 3.1
and 3.3, respectively. These bounds are derived from the worst-case scenarios
where $M-1$ appears with multiplicity $n-\mu_{M}$. However, on input vectors
$v$ sampled from the uniform distribution on $\\{0,\ldots,M\\}$ with varying
multiplicities $\mu_{M}$, $L_{v}(t)$ consistently performs worse than
$R_{v}(t)$. For more details, see the experiments in Section 5.

Based on the relationship between $D_{v}(t,\alpha)$ and $R_{v}(t)$ summarized
in Proposition 2.6, the error is similar to Theorem 3.3. Here, the worst case
analysis yields the function
$x\mapsto\dfrac{t^{-x}(1-\alpha^{-x})}{\log(\alpha)}$ which is decreasing
after reaching its maximum on $\mathbb{R}_{>0}$ at $x=\dfrac{\log(\log(\alpha
t))-\log(\log(t))}{\log(\alpha)}$ which limits to $\log(t)^{-1}$ as
$\alpha\rightarrow 1$.

######  Theorem 3.6.

Fix $v\in\mathbb{Q}^{n}$, $\delta>0$, and $\alpha>1$. Then, $0\leq
M-D_{v}(t,\alpha)<\delta$ when $t>e^{1/g_{2}}$,

$\begin{array}[]{l}t>\alpha^{\dfrac{\alpha^{-g_{2}}}{1-\alpha^{-g_{2}}}}\xrightarrow{\alpha\rightarrow
1}e^{1/g_{2}},\hbox{\leavevmode\nobreak\ \leavevmode\nobreak\
and\leavevmode\nobreak\ \leavevmode\nobreak\ }\\\\[7.22743pt]
t>\left(\dfrac{n-\mu_{M}}{\delta\cdot\mu_{M}}\cdot\dfrac{1-\alpha^{-g_{2}}}{\log(\alpha)}\right)^{\frac{1}{g_{2}}}\xrightarrow{\alpha\rightarrow
1}\left(\dfrac{(n-\mu_{M})g_{2}}{\delta\cdot\mu_{M}}\right)^{\frac{1}{g_{2}}}.\end{array}$

If $v\in\mathbb{Z}^{n}$ and $\delta=1$, this bound is obtained when $\alpha>1$
and

$t>\max\left(e,\frac{n-\mu_{M}}{\mu_{M}}\right).$

###### Proof.

The worst case analysis using the three assumptions on $\alpha$ and $t$ that
are independent of $\delta$ show that

$M-D_{v}(t,\alpha)<\delta\quad\quad\text{whenever}\quad\quad
t^{g_{2}}>\dfrac{n-\mu_{M}}{\delta\cdot\mu_{M}}\dfrac{1-\alpha^{-g_{2}}}{\log(\alpha)}.$

When $v\in\mathbb{Z}^{n}$ and $\delta=1$, this simplifies to
$t^{g_{2}}>\frac{n-\mu_{M}}{\mu_{M}}\frac{1-\alpha^{-g_{2}}}{\log(\alpha)}$.
Since $t>e$, $\alpha>1$, and $g_{2}\geq 1$, this holds if additionally
$t>\frac{n-\mu_{M}}{\mu_{M}}$. ∎

To analyze the $p$-norm case, following [11, 12], we assume the vector $v$ has
undergone a linear transformation so that each $v_{j}\in[0,1]$.

######  Theorem 3.7.

If $v\in[0,1]^{n}$ and $\delta>0$, then $0\leq||v||_{u}-M<\delta$ when $u>1$
and

$e^{u(\Delta+g_{2})}-e^{ug_{2}}\mu_{M}-(n-\mu_{M})>0\quad\quad\text{where}\quad\Delta=\log\left(1+\frac{\delta}{M}\right).$

###### Proof.

By (13), $||v||_{u}=M\cdot e^{\epsilon(u)}$ where
$\epsilon(u)=L_{\log|v|}(e^{u})-\log(M)$ which is the error when using
$L_{\log|v|}(e^{u})$ to approximate $\log(M)$. Hence, $||v||_{u}-M<\delta$ if
and only if $\epsilon(u)<\log\left(1+\frac{\delta}{M}\right)=:\Delta$. By
Theorem 3.1, this occurs whenever $t>1$ and

$t^{\Delta+g_{2}}-t^{g_{2}}\mu_{M}-(n-\mu_{M})>0.$

Since $u=\log(t)$, changing coordinates gives the result. ∎

Figure 4. The graphs of the $p$-norms of the vectors $v_{1}/7$ and $v_{2}/7$
with entries in $[0,1]$, where $v_{1}$ and $v_{2}$ are from Example 3.2.

Figure 5. Comparison of $D_{v}(t,\alpha)$ for $v_{1}$ and $v_{2}$ from Example
3.2 with various values of $\alpha$.

######  Example 3.8.

The following illustrates the differences between the approximations
$L(t),R(t),D(t,\alpha),$ and $||\cdot||_{p}$ of $M$ on our running examples of
$v_{1}$ and $v_{2}$ from Example 3.2. First, similar to previous plots, Figure
4 shows the difference of convergence rate for the $p$-norm approximation due
to higher multiplicity. Next, Figure 5 compares $R_{v}(t)$ with $D_{v}(t,2)$
and $D_{v}(t,1.5)$ for $v=v_{1}$ and $v=v_{2}$ showing comparable convergence
rates. Finally, we compare the values of $||v||_{p},L_{v}(t)$, $R_{v}(t)$, and
$D_{v}(t,\alpha)$ when they require comparably large (in absolute value)
floating point number for evaluation. Setting
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}T}$ to be
the largest floating point number required, we plot these functions against
$\log(T)$ in Figures 6 and 7 for $v=v_{1}$ and $v=v_{2}$, respectively.

Figure 6. A comparison of the smooth approximations
$L_{v_{1}}(t),R_{v_{1}}(t),||v_{1}||_{p},D_{v_{1}}(t,2)$, and
$D_{v_{1}}(t,1.5)$ of the maximum of $v_{1}$, plotted against the natural
logarithm of $T$, the required absolute value of floating point numbers for
evaluation. Figure 7. A comparison of the smooth approximations
$L_{v_{1}}(t),R_{v_{1}}(t),||v_{1}||_{p},D_{v_{1}}(t,2)$, and
$D_{v_{1}}(t,1.5)$ of the maximum of $v_{2}$, plotted against the natural
logarithm of $T$, the required absolute value of floating point numbers for
evaluation.

###  3.2. Computing the multiplicity

Due to the simplistic nature of the expansion in (10) for $L_{v}(t)$, we
consider computing the multiplicity $\mu_{M}$ for the maximum $M$. In
particular, it is easy to see from (10) that

(16) $\mu_{M}=\lim_{t\to\infty}t^{L_{v}(t)-M}$

Of course, using this expression requires _a priori_ knowledge of $M$ which
can be attained, for example, in the integer case by applying Theorem 3.1.

######  Theorem 3.9.

Given $v\in\mathbb{Z}^{n}$, $\lfloor t^{L_{v}(t)-\lfloor
L_{v}(t)\rfloor}\rfloor=\mu_{M}$ whenever

$t>\max\left\\{n-\mu_{M},\frac{\mu_{M}+\sqrt{\mu_{M}^{2}+4(n-\mu_{M})}}{2}\right\\}$

###### Proof.

When $t>\frac{\mu_{M}+\sqrt{\mu_{M}^{2}+4(n-\mu_{M})}}{2}$, Theorem 3.1
provides that $\lfloor L(t)\rfloor=M$. Using a worst-case analysis, one has

$0\leq t^{L_{v}(t)-M}-\mu_{M}\leq(n-\mu_{M})t^{-1}$

with the worst-case upper bound below $1$ when $t>n-\mu_{M}$. ∎

######  Example 3.10.

Continuing with $v_{1}$ and $v_{2}$ from Example 3.2, Theorem 3.9 provides
$t^{L_{v_{1}}(t)-\lfloor L_{v_{1}}(t)\rfloor}\in[1,2)$ for $t>6$ and
$t^{L_{v_{2}}(t)-\lfloor L_{v_{2}}(t)\rfloor}\in[5,6)$ for $t>6$ with Figure 8
showing convergence in advance of such worst-case bounds.

Figure 8. The graphs of $t^{L(t)-M}$ applied to $v_{1}$ and $v_{2}$ from
Example 3.2.

###  3.3. Combining $R^{(k)}_{v}(t)$ to improve convergence and compute
$g_{2}$

Since all of the higher-order derivatives $R_{v}^{(k)}(t)$ have the same
convergence rate, one can combine them in various ways to increase the
convergence rate as well as extract other information about $v$. The following
demonstrates a higher-order approximation of $M$ along with approximating
$g_{2}$. The computation of $g_{2}$ and $M$ produces, as a byproduct, the
second largest element of $v$, namely $w_{2}=M-g_{2}$.

######  Theorem 3.11.

For $v\in\mathbb{Z}^{n}$, we have

(17)
$\frac{2R_{v}^{(1)}(t)R_{v}^{(3)}(t)-R_{v}^{(2)}(t)\left(R_{v}^{(1)}(t)+R_{v}^{(2)}(t)\right)}{R_{v}^{(1)}(t)-3R_{v}^{(2)}(t)+2R_{v}^{(3)}(t)}=M+O(t^{-g_{2}-1})$

and

(18)
$\frac{R_{v}^{(1)}(t)-3R_{v}^{(2)}(t)+2R_{v}^{(3)}(t)}{R_{v}^{(2)}(t)-R_{v}^{(1)}(t)}=g_{2}+O(t^{-1}).$

###### Proof.

From Proposition 2.3 and (12),

$\begin{array}[]{rcl}R_{v}^{(1)}(t)&=&M-g_{2}\dfrac{\mu_{w_{2}}}{\mu_{M}}t^{-g_{2}}+O(t^{-g_{2}-1}),\\\\[10.84006pt]
R_{v}^{(2)}(t)&=&M-g_{2}(g_{2}+1)\dfrac{\mu_{w_{2}}}{\mu_{M}}t^{-g_{2}}+O(t^{-g_{2}-1}),\\\\[10.84006pt]
R_{v}^{(3)}(t)&=&M-\dfrac{g_{2}(g_{2}+1)(g_{2}+2)}{2}\dfrac{\mu_{w_{2}}}{\mu_{M}}t^{-g_{2}}+O(t^{-g_{2}-1})\end{array}$

and so the result follows by direct symbolic elimination. ∎

######  Example 3.12.

We illustrate Theorem 3.11 using $v_{1}$ and $v_{2}$ from Example 3.2. Figure
9 compares the convergence of $R_{v}^{(1)}(t)$, $R_{v}^{(2)}(t)$,
$R_{v}^{(3)}(t)$, and the combined formula in (17) for $v=v_{1}$ and $v=v_{2}$
to $M=7$ for both. For both cases, one sees faster convergence as expected
from (17). Additionally, Figure 10 shows the convergence of the combined
formula in (18) for $v_{1}$ and $v_{2}$ to $g_{2}=1$ for both.

Figure 9. Comparison of various methods to approximate $M$ for $v_{1}$ and
$v_{2}$. Figure 10. The graphs of (18) for $v_{1}$ and $v_{2}$ which converge
to $g_{2}=1$ for both cases.

######  Remark 3.13.

The functions $R_{v}^{(k)}(t)$ are linear combinations of the derivatives
$\mathcal{D}^{(k)}(t)=\frac{d^{k}}{du^{k}}\mathcal{L}_{v}(e^{u})$, e.g.,

$\displaystyle R^{(1)}(t)$ $\displaystyle=\mathcal{D}^{(1)}(t),$
$\displaystyle R^{(2)}(t)$
$\displaystyle=-\mathcal{D}^{(1)}(t)+\mathcal{D}^{(2)}(t),$ $\displaystyle
R^{(3)}(t)$
$\displaystyle=\frac{2\mathcal{D}^{(1)}(t)-3\mathcal{D}^{(2)}(t)+\mathcal{D}^{(3)}(t)}{2},$
$\displaystyle R^{(4)}(t)$
$\displaystyle=\frac{-6\mathcal{D}^{(1)}(t)+11\mathcal{D}^{(2)}(t)-6\mathcal{D}^{(3)}(t)+\mathcal{D}^{(4)}(t)}{6}.$

In particular, the linear transformation that maps the first $r$ values of
$\mathcal{D}^{(k)}(t)$ to the first $r$ values of $R^{(k)}(t)$ is represented
by an $r\times r$ lower triangular matrix $A^{(r)}$. For $j\leq i$, the
$(i,j)$-entry of $A^{(r)}$ is

$\frac{(-1)^{i+1}}{(i-1)!}\mathcal{S}_{ij}$

where
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{S}_{ij}}$
is a Stirling number of the first kind. For example,

$A^{(4)}=\begin{bmatrix}(-1)^{2}1&0&0&0\\\ (-1)^{3}1&(-1)^{3}(-1)&0&0\\\
\left(\frac{(-1)^{4}}{2}\right)2&\left(\frac{(-1)^{4}}{2}\right)(-3)&\left(\frac{(-1)^{4}}{2}\right)1&0\\\
\left(\frac{(-1)^{5}}{6}\right)6&\left(\frac{(-1)^{5}}{6}\right)(-11)&\left(\frac{(-1)^{5}}{6}\right)6&\left(\frac{(-1)^{5}}{6}\right)(-1)\end{bmatrix}.$

##  4\. The tropical viewpoint

We interpret our previous results geometrically using tools from _tropical
geometry_. We stress that throughout this section, we consider specific
families of tropical constructions which exist more generally. Namely, the
varieties we consider are graphs of univariate Laurent polynomials with
positive coefficients. Such varieties are quite special and so the results of
this section may not hold in the more general setting. For an introduction to
tropical geometry, we invite the interested reader to consult the standard
reference [8].

To utilize the tropical geometry framework, we assume throughout this section
that $v\in\mathbb{Z}^{n}$, define
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbb{C}^{\times}}=\mathbb{C}\backslash\\{0\\}$,
and consider the function

$\displaystyle\varphi:\mathbb{C}^{\times}$ $\displaystyle\to\mathbb{C}^{2}$
$\displaystyle t$ $\displaystyle\mapsto F_{v}(t).$

Let ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}X_{v}}$
be the graph of $\varphi$ intersected with $(\mathbb{C}^{\times})^{2}$. We
note that $X_{v}$ is the set of zeros of the polynomial
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{F}_{v}(t,y)}=y-F_{v}(t)$:

$X_{v}=\\{(t,y)\in(\mathbb{C}^{\times})^{2}\mid\mathcal{F}_{v}(t,y)=0\\}\subset(\mathbb{C}^{\times})^{2}.$

The _Newton polygon_ of $\mathcal{F}_{v}(t,y)$ is the convex hull
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{N}(\mathcal{F}_{v}(t,y))}$
of the exponent vectors of $\mathcal{F}_{v}(t,y)$. In this case,
$\mathcal{N}(\mathcal{F}_{v}(t,y))$ is simply the triangle
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\Delta_{v}}$
with vertices $(M,0)$, $(\min(v),0)$, and $(0,1)$ as illustrated in Figure
11(a). The union of the outer normal rays of $\Delta_{v}$ along with the
origin form a _polyhedral fan_ called the  tropicalization of $X_{v}$, denoted
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textrm{trop}(X_{v})}$
and illustrated in Figure 11(c). The fan $\textrm{trop}(X_{v})$ is a _tropical
curve_ which encodes the asymptotic behavior of $X_{v}$ near the coordinate
axes $\mathbb{C}^{2}\backslash(\mathbb{C}^{\times})^{2}$. Note that in our
specific situation, the Newton polytope $\mathcal{N}(\mathcal{F}_{v}(t,y))$,
and hence the tropical curve $\textrm{trop}(X_{v})$, depends only on $\min(v)$
and $\max(v)$.

Figure 11. (a) The Newton polygon of $\mathcal{F}_{v_{1}}(t,y)$ where $v_{1}$
is as in Example 3.2 (b) The amoeba $\mathcal{A}(X_{v_{1}})$ (c) The tropical
variety $\textrm{trop}(X_{v_{1}})$.

An alternative construction of $\textrm{trop}(X_{v})$, due to Bergman [2],
involves the image
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{A}_{\tau}(X_{v})}$
of $X_{v}$ under the log-absolute value map:

$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textrm{Log}_{\tau}|\cdot|}:(\mathbb{C}^{\times})^{2}$
$\displaystyle\to\mathbb{R}_{u,s}^{2}$ $\displaystyle(t,y)$
$\displaystyle\mapsto(\log_{\tau}(|t|),\log_{\tau}(|y|)).$

The set $\mathcal{A}_{\tau}(X_{v})$ is called the  $\tau$-amoeba of $X_{v}$.
We remark that we use
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}u}$ and
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}s}$ for
coordinates of the codomain and that the overlap of the symbol $u$ with
previous sections is intentional. Undecorated, the notation
$\mathcal{A}(X_{v})\subseteq\mathbb{R}^{2}_{u,s}$ refers to the $e$-amoeba of
$X_{v}$ as illustrated in Figure 11(b). Since
$\mathcal{A}_{\tau}(X_{v})=\frac{1}{\log(\tau)}\mathcal{A}(X_{v})$, the set
$\mathcal{A}(X_{v})$ contains all of the information about all of the amoebas
of $X_{v}$. Since the absolute values of coordinates of points in $X_{v}$ may
be arbitrarily large or small, the set $\mathcal{A}(X_{v})$ is unbounded. The
portions which approach infinity are loosely referred to as the _tentacles_ of
the amoeba. As $\tau\to\infty$, these tentacles limit to the rays of
$\textrm{trop}(X_{v})$. In this sense, $\textrm{trop}(X_{v})$ contains
asymptotic information about $X_{v}$ and is sometimes referred to as the
_logarithmic limit set_ of the amoeba of $X_{v}$.

We call lines which intersect an amoeba $\mathcal{A}(X_{v})$ in a ray
tentacle lines. Up to translation, these rays are exactly those in
$\textrm{trop}(X_{v})$. Note that many tentacle lines may be associated to the
same tropical ray (see the vertical rays of Figure 12). The following
elementary facts relate the Newton polygon
$\mathcal{N}(\mathcal{F}_{v}(t,y))$, amoeba $\mathcal{A}(X_{v})$, and tropical
curve $\textrm{trop}(X_{v})$. We encourage the reader to refer to Figure 12.
These facts are specializations of a more general relationship between these
three objects (see [8] for more details).

  1. (1)

The tentacle lines of $\mathcal{A}(X_{v})$ corresponding to the ray in
$\textrm{trop}(X_{v})$ spanned by $(0,-1)$ correspond to distinct moduli of
complex roots of $F_{v}(t)$.

  2. (2)

When the lowest order term of the Laurent polynomial $F_{v}(t)$ is a constant
$c$, $\textrm{trop}(X_{v})$ contains the ray spanned by $(-1,0)$. There is one
tentacle line of $\mathcal{A}(X_{v})$ associated to that ray, which occurs at
height $\log(c)$.

Additionally, the following facts relate $\mathcal{A}(X_{v})$ and the function
$u\mapsto\mathcal{L}_{v}(e^{u})$.

  1. (3)

The upper boundary
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathcal{U}}$
of $\mathcal{A}(X_{v})$ is the graph of $\mathcal{L}_{v}(e^{u})$.

  2. (4)

$L_{v}(t)=L_{v}(e^{u})=\frac{\mathcal{L}_{v}(e^{u})}{u}$ is the slope of the
ray from the origin to the point
$(u,\mathcal{L}_{v}(e^{u}))\in\mathcal{A}(X_{v})$.

  3. (5)

$\mathcal{D}^{(k)}_{v}(e^{u})=\frac{d^{k}}{du^{k}}\mathcal{L}_{v}(e^{u})$ is
the $k^{\rm th}$ derivative of the function $u\mapsto\mathcal{L}_{v}(e^{u})$.

  4. (6)

$\mathcal{D}_{v}^{(1)}(e^{u})=R^{(1)}_{v}(e^{u})$ is the slope of the tangent
line to the boundary of the amoeba at $(u,\mathcal{L}_{v}(e^{u}))$.

We point out that $(3)$ follows from the fact that all of the coefficients of
$F_{v}(t)$ are non-negative. In general, describing the boundaries of amoebas
is challenging [5].

######  Proposition 4.1.

Let $v\in\mathbb{Z}^{n}$. The tentacle lines of $\mathcal{A}(X_{v})$ are given
by

  1. (a)

$s=\log(\mu_{M})+M\cdot u$

  2. (b)

$s=\log(\mu_{m})+m\cdot u$ where $m=\min(v)$.

  3. (c)

$u=\log(|\xi_{i}|)$ where $\\{\xi_{i}\\}_{i=1}^{d}\subset\mathbb{C}$ are the
roots of $F(t)$.

###### Proof.

As observed already, the tentacles in the $(0,-1)$ direction correspond to
roots $\xi_{i}$ of $F_{v}(t)$ and they occur at $u=\log(|\xi_{i}|)$ which
establishes (c). To see (a) and (b), suppose $m=\min(v)=0$. Then, $F(t)$ has a
constant term of $\mu_{m}$ and hence $\lim_{t\to 0}\log(F(t))=\log(\mu_{m})$.
This limit indicates that $\mathcal{A}(X_{v})$ has a horizontal tentacle
occurring at $s=\log(\mu_{m})$. However, translating $v$ by $a\in\mathbb{Z}$
amounts to sheering the Newton polygon space by
$(\alpha,\beta)\mapsto(\alpha,a\alpha+\beta)$ and the amoeba space by
$(u,s)\mapsto(u-as,s)$. In particular, this transformation does not change the
$s$-intercepts of the tentacle lines. Hence, the tentacle line associated to
the minimum of $v$ has the equation $s=\log(\mu_{m})+m\cdot u$ whereas the
line associated to the maximum $M$ has the equation $s=\log(\mu_{M})+M\cdot
u$. ∎

Figure 12. The amoeba $\mathcal{A}(X_{v})$ of the graph $X_{v}$ where $v$ is
as in Example 4.2 along with its tentacle lines.  Figure 13. The amoeba
$\mathcal{A}(X_{v})$ of the graph $X_{v}$ for $v$ as in Example 4.2 along with
the ray from the $(0,0)$ to $(u,L_{v}(e^{u}))$ and the ray from
$(u,L_{v}(e^{u}))$ with slope
$R^{(1)}_{v}(e^{u})=\mathcal{D}^{(1)}_{v}(e^{u})$.

Proposition 4.1 gives a geometric interpretation of how the multiplicity of
$M$ in $v$ contributes to a slower convergence rate of $L_{v}(t)$ but not for
$R_{v}(t)$: multiplicity corresponds to a translation of the tentacle line of
$\mathcal{A}(X_{v})$ associated to the tropical ray spanned by $(1,M)$. This
is geometrically displayed in Figure 13.

######  Example 4.2.

Let $v=[0_{8},1_{5},2_{40},3_{5},4_{40}]$, where a subscript indicates
multiplicity. The amoeba $\mathcal{A}(X_{v})$ is shown in Figure 12. The
polynomial

$F_{v}(t)=8+5t+40t^{2}+5t^{3}+40t^{4}$

has two pairs $\xi_{1},\bar{\xi_{1}}$ and $\xi_{2},\bar{\xi_{2}}$ of conjugate
roots. Hence, there are two vertical tentacle lines of $\mathcal{A}(X_{v})$.
The tentacle line corresponding to the minimum multiplicity
$\mu_{m}=\mu_{0}=8$ is horizontal at height $\log(8)$ and the equation of the
remaining tentacle line is $s=\log(40)+4u$. The upper boundary of the amoeba
is the image of the positive part of $X_{v}$ under the log-absolute value map.

Figure 12 illustrates a geometric interpretation of the values of
$L_{v}(e^{u})$ and $R^{(1)}_{v}(e^{u})$ as slopes of rays.

One may also interpret the Cauchy integral in Remark 2.5:

$\frac{1}{2\pi\sqrt{-1}}\oint_{|t|=r}t^{-1}\cdot R_{v}^{(k)}(t^{-1})\cdot
dt=M,$

in terms of tropical geometry when $k=1$. This is done via the  order map:

$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textrm{ord}}:\mathbb{R}^{2}$
$\displaystyle\to\mathbb{R}^{2}$ $\displaystyle(u,s)$
$\displaystyle{\tiny{\mapsto\left(\frac{1}{(2\pi\sqrt{-1})^{2}}\int_{\begin{subarray}{c}\textrm{Log}|t|=u\\\
\textrm{Log}|y|=s\end{subarray}}\frac{tF_{v}^{\prime}(t)}{y-F_{v}(t)}\cdot\frac{dtdy}{ty},\frac{1}{(2\pi\sqrt{-1})^{2}}\int_{\begin{subarray}{c}\textrm{Log}|t|=u\\\
\textrm{Log}|y|=s\end{subarray}}\frac{y}{y-F_{v}(t)}\cdot\frac{dtdy}{ty}\right).}}$

The function ord is constant and $\mathbb{Z}^{2}$-valued on connected
components of the complement $\mathbb{R}^{2}\backslash\mathcal{A}(X_{v})$ of
the amoeba [6]. In fact, ord maps these components to distinct integer points
in the Newton polygon $\Delta_{v}$. In particular, for any point $(u,s)$ in
the bottom right complement component, the first integral

$\frac{1}{(2\pi\sqrt{-1})^{2}}\int_{\begin{subarray}{c}\textrm{Log}|t|=u\\\
\textrm{Log}|y|=s\end{subarray}}\frac{tF_{v}^{\prime}(t)}{y-F_{v}(t)}\cdot\frac{dtdy}{ty}$

degenerates as $|y|\to 0$ (or $s\to-\infty$) to the integral

$\frac{1}{2\pi\sqrt{-1}}\oint_{\begin{subarray}{c}\textrm{Log}|t|=u\end{subarray}}\frac{tF_{v}^{\prime}(t)}{F_{v}(t)}\cdot\frac{dt}{t}=\frac{1}{2\pi\sqrt{-1}}\oint_{\begin{subarray}{c}\textrm{Log}|t|=u\end{subarray}}t^{-1}R_{v}^{(1)}(t)\cdot
dt=M$

for sufficiently large $u$ as in (14). The second integral, on the other hand,
evaluates to zero. Since this value of ord on $(u,s)$ is constant on connected
components of the complement of the amoeba, this shows that
$\textrm{ord}(u,s)$ evaluates to the vertex $(M,0)$ of $\Delta_{v}$ when
$(u,s)$ is in the bottom-right component of
$\mathbb{R}^{2}\backslash\mathcal{A}(X_{v})$, in agreement with Remark 2.5.

##  5\. Experiments

Figure 14. Average results of the integer-valued vector $v$ experiments. The
$x$-axis and $y$-axis correspond to $n=1,\ldots,100$ and $\mu=1,\ldots,n$
respectively. Each pixel is the average of $100$ subexperiments measuring
$\log(1+t^{*}_{L_{v}}-t^{*}_{R_{v}})$ where $t^{*}_{L_{v}}$ and
$t^{*}_{R_{v}}$ are the $t$-values such that the absolute error of the
corresponding function is less than $1$. The maximum, $M$, are: (a) 10 (b) 50
(c) 100 (d) 500. Black pixels above the diagonal are when $\mu>n$.

We compare each of the approximations discussed on a gallery of qualitatively
different inputs $v$. In each of the following sections, we sample vectors $v$
from some prescribed distribution. We then compare the approximations of $M$
on these samples on average.

###  5.1. Integer numbers

We compared $L_{v}(t)$ and $R_{v}(t)$ in the integer case by defining a
maximum $M$ with multiplicity $\mu$ for an integer-valued vector
$v\in[1,M]^{n}$. That is, we defined $v$ of varying length $n=1,\dots,100$
with $M$ appearing $\mu$ times, where $\mu\leq n$ and the remaining $n-\mu$
values of $v$ were random integers sampled from $[1,M-1]$. Figure 14 displays
the four experiments comparing the performance of $L_{v}(t)$ and $R_{v}(t)$
for approximating a given maximum $M$, namely $M=10,50,100,$ and $500$,
respectively. Performance is measured by
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}t^{*}}$,
the first value of $t$ to approximate $M$ up to an absolute error of $1$, so
that the maximum is obtained from $L_{v}(t^{*})$ or $R_{v}(t^{*})$ through use
of the floor or ceiling function, respectively. Each experiment consists of
$100$ subexperiments averaged over $\log(1+t^{*}_{L_{v}}-t^{*}_{R_{v}})$. The
plotted values are logarithmic and offset by $1$ since, if
$t^{*}_{L_{v}}=t^{*}_{R_{v}}$, then
$\log(1+t^{*}_{L_{v}}-t^{*}_{R_{v}})=\log(1)=0$.

Figure 15. Average results of the floating point-valued vector $v$
experiments. Each pixel at position $(n,\mu)$ represents the value of
$\log(\alpha+t^{*}_{L_{v}}-t^{*}_{R_{v}})-\log(\alpha)$ averaged over $100$
subexperiments. The $x$-axis and $y$-axis correspond to $n=1,\ldots,100$ and
$\mu=1,\ldots,n$ respectively. The tolerance used to define $t^{*}$ are
absolute error less than: (a) $\textrm{exp}(1)$ (b) $1$ (c) $1/n$ (d) $1/100$.
Black pixels above the diagonal are when $\mu>n$.

###  5.2. Uniformly distributed floating point numbers

We repeat the experiments of the above section with floating point vectors
$v\in[0,1]^{n}$ with $M=1$. Figure 15 displays the results of comparing
$L_{v}(t)$ and $R_{v}(t)$ on vectors whose elements are sampled from the
uniform distribution on $[0,1]$. As with the previous experiments, each pixel
at coordinates $(n,\mu)$ represents the value of
$\log(\alpha+t^{*}_{L_{v}}-t^{*}_{R_{v}})-\log(\alpha)$, where
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}t^{*}}$ is
the first value of $t$ to approximate $M$ up to a given absolute error. To
model a significant $g_{2}$ gap, we constructed these vectors by choosing
$n-\mu$ vectors uniformly from $[0,1]$, multiplying them by $(n-1)/n$ and
appending them to a vector of length $\mu$ with coordinates all equal to $1$.
The figures differ only in the absolute tolerance used to define $t^{*}$. The
value $\alpha=\min(t^{*}_{L_{v}}-t^{*}_{R_{v}})+1$ offsets the results so that
when the results are averaged and plotted logarithmically, the minimum
difference remains $\log(1)=0$. The subtraction of the $\log(\alpha)$ term
then better illustrates the subexperiments where $L_{v}(t)$ outperforms
$R_{v}(t)$. This adjustment is accounted for in the uniform distribution
examples as there are select instances in which $L_{v}(t)$ performs better
than $R_{v}(t)$ by converging at a lesser $t$ value, thus the difference is
non-positive and less than $-1$. This occurs most notably in the experiments
with tolerance $1/n$ and $1/100$ of Figure 15.

###  5.3. Clustering floating point numbers

We repeat a similar experiment with floating point numbers in the presence of
noise. Our goal is to identify the scenarios where it is appropriate to apply
Theorem 3.3 heuristically. Our setup is as follows. Suppose that $5$
measurements, with values in $[0,1]$, are to be taken, but the measuring
device incurs some error $\pm\epsilon$. To rectify this, each measurement is
performed $20$ times. Heuristically, one may choose to apply Theorem 3.3 with
the interpretation that $v$ consists of $5$ numbers, each occurring with
multiplicity $20$, with the goal of obtaining $\max(v)$ up to error
$\epsilon$. In this case, Theorem 3.3 specializes to $t>\left(\frac{4\cdot
g}{\epsilon}\right)^{\frac{1}{g}}$ where $g$ is the gap between the top two
_true_ measurements.

After fixing $\epsilon$ and $g$, we model such a situation by the following
procedure.

  1. (1)

Pick $5$ true measurements $w_{1},\ldots,w_{5}\in[0,1]$ by setting $w_{5}=1$,
$w_{4}=1-g$ and $w_{1},w_{2}$ and $w_{3}$, sampled uniformly at random from
$[0,1-g]$.

  2. (2)

For each $w_{i}$, sample $20$ numbers uniformly from
$[w_{i}-\epsilon,w_{i}+\epsilon]$. Collect all $100$ numbers in $v$.

  3. (3)

Evaluate $R_{v}(t^{*})$ for
$t^{*}=\left(\frac{4g}{\epsilon}\right)^{\frac{1}{g}}$ to obtain the absolute
error $\textrm{err}_{v}=|1-R(t^{*})|$

For each pair $(g,\epsilon)$, where $g=0.01,\ldots,1$ and
$\epsilon=0,\ldots,1$, we repeat the above procedure $500$ times and average
the error obtained in step $3$. Additionally, we deem an approximation a
_success_ if the error is smaller than $\epsilon$. The two figures in Figure
16 display, for each pair $(g,\epsilon)$, the average error and number of
successes.

Figure 16. For each $(g,\epsilon)$ and for $500$ tries, (left) average error
of $R_{v}(t^{*})$ for $t^{*}$ from Theorem 3.3 (right) number of
approximations $R_{v}(t^{*})$ within $\epsilon$ for $t^{*}$ from Theorem 3.3.

As indicated by the experiments summarized in Figure 16, a small gap $g$ and
large $\epsilon$ produces the largest errors with the fewest numbers of
successes, as expected. Interestingly, a large gap and small $\epsilon$,
corresponding to the upper left corner of the figures also impacts the
effectiveness of the heuristic. The large gap size means that
$w_{2},\ldots,w_{5}$ are all chosen within a small interval $[0,1-g]$, and we
suspect that this cluster behaves like the value $\frac{1-g}{2}$ appearing
with high multiplicity. Additionally, the small $\epsilon$ value means it is
difficult to achieve a “success” by having absolute error less than
$\epsilon$.

For these noisy experiments, there are two natural interpretations of what
should be considered $N$ and $\mu$. The first is that $N$ should be $5$, the
number of true measurements, whereas $\mu$ should be $1$. The second
interpretation is that $N$ should be $20\cdot 5=100$, the true length of $v$
while $\mu$ should be $20$, the size of the top cluster. In the $R_{v}(t)$
case, these distinctions cancel out in the bound provided by Theorem 3.3. In
the $L_{v}(t)$ case, however, these interpretations give drastically different
bounds when applying Theorem 3.1. The later interpretation often yields such
enormous $t$ bounds that an application of that result is not useful. In
Figure 17, we display the results of an experiment using the former
interpretation. It did not happen that the $L_{v}(t)$ approximation with the
interpreted bound from Theorem 3.1 achieved the expected accuracy. This
suggests that the later interpretation, despite its lack of utility, is likely
more appropriate. Our experiments also showcase the advantage of using the
$R_{v}(t)$ approximation over $L_{v}(t)$, especially in noisy situations with
high (approximate) multiplicity.

Figure 17. For each $(g,\epsilon)$, over $500$ tries, the average error of
$L_{v}(t^{*})$ from Theorem 3.1.

##  6\. Max-convolution and applications

One way to use smooth approximations of the maximum function is to approximate
the max-convolution of two vectors [12]. To that end, consider two integer
vectors $a=(a_{0},\ldots,a_{n})$ and $b=(b_{0},\ldots,b_{n})$. The classical
convolution problem asks to determine the vector of  convolution coefficients
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}a\star b}$
where

(19) $(a\star b)_{k}=\sum_{i=0}^{k}a_{i}\cdot
b_{k-i}=\sum_{i=\max(0,k-n)}^{\min(k,n)}a_{i}\cdot b_{k-i}.$

We remark that the middle description is sufficient if one takes $a_{i}=0$ and
$b_{i}=0$ whenever they are undefined. With the same input, the problem of
max-convolution, MAXCON, asks for the vector $c$ of  max-convolution
coefficients, where

(20)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}c_{k}}=\max_{\max(0,k-n)\leq
i\leq\min(k,n)}(a_{i}+b_{k-i}).$

These coefficients can be obtained via (19) by replacing the operations
$(\cdot,+)$ with $(+,\max)$, respectively. The form $c_{k}=\max_{0\leq i\leq
n}(a_{i}+b_{k-i})$ may be used if one replaces undefined $a_{i}$ and $b_{i}$
with $-\infty$. Equivalently, through constructing

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}A_{t}(x)}=\sum_{i=0}^{n}t^{a_{i}}x^{i},\quad\quad{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}B_{t}(x)}=\sum_{i=0}^{n}t^{b_{i}}x^{i}\in\mathbb{Q}(t)[x],$

the problem of MAXCON asks for the largest exponents in $t$ appearing in the
coefficients of

$A_{t}(x)\cdot B_{t}(x)=\sum_{k=0}^{2n}\sum_{i=0}^{k}t^{a_{i}+b_{k-i}}x^{k}.$

Setting
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v^{(k)}}=((a_{i}+b_{k-i})\leavevmode\nobreak\
|\leavevmode\nobreak\ \max(0,k-n)\leq i\leq\min(k,n))$, we rewrite this as

$A_{t}(x)\cdot B_{t}(x)=\sum_{k=0}^{2n}F_{v^{(k)}}(t)x^{k}.$

For fixed $t$, the values of $F_{v^{(k)}}(t)$ are _classical_ convolution
coefficients

$((t^{a_{0}},\ldots,t^{a_{n}})\star(t^{b_{0}},\ldots,t^{b_{n}}))_{k}$

which can be computed with $O(n\log(n))$ operations, e.g., using the fast
Fourier transform (FFT) [9]. Applying $\log_{t}$ provides an $O(n\log(n))$
routine for evaluating $L_{v^{(k)}}(t)$, whereby with Theorem 3.1, this
process computes $\max(v^{(k)})=c_{k}$ when evaluated at a sufficiently large
value of $t$. We summarize this discussion in the following quasi-linear time
algorithm.

Input: Two integer vectors $a=(a_{0},\ldots,a_{n})$ and
$b=(b_{0},\ldots,b_{m})$.

Output: The max-convolution coefficients $c=(c_{0},\ldots,c_{n+m})$

1 Choose $t^{*}$ satisfying the bounds of Theorem 3.1 (e.g.,
$t^{*}\geq\max(n,m)$+1)

2 Compute $\alpha=((t^{*})^{a_{0}},\ldots,(t^{*})^{a_{n}})$ and
$\beta=((t^{*})^{b_{0}},\ldots,(t^{*})^{b_{m}})$

3 Compute $\ell(t^{*})=\alpha\star\beta$

4 Apply $\lfloor\log_{t^{*}}(\cdot)\rfloor$ component-wise to $\ell(t^{*})$ to
obtain $c=\lfloor\log_{t^{*}}(\ell(t^{*}))\rfloor$

5 return __ $c$

Algorithm 1 MaxCon

######  Example 6.1.

Consider applying Algorithm 1 to compute the max-convolution coefficients of
the vectors

$a=(3,1,2,4,1,2),\quad\quad b=(5,3,0,4).$

Taking $t^{*}=6$, we obtain

$\alpha=(216,6,36,1296,6,36),\quad\quad\beta=(7776,216,1,1296)$

The classical convolution of $\alpha$ and $\beta$ is

${\ell(6)=\alpha\star\beta=(1679620,93312,281448,10365400,334404,329184,1687400,7812,46656)}$

which under $\log_{6}$ evaluates to

$\log_{6}(\ell(6))=(8,6.38685,7.00301,9.01571,7.09923,7.09045,8.00258,5.00258,6).$

Finally, by applying $\lfloor\cdot\rfloor$, we obtain the max-convolution
coefficents

$c=(8,6,7,9,7,7,8,5,6).$

For completeness and interpretation of $c$, we provide
$A_{t}(x),B_{t}(x)\in\mathbb{Z}[t][x]$ below along with their product:

$A_{t}(x)=t^{3}x^{0}+t^{1}x^{1}+t^{2}x^{2}+t^{3}x^{3}+t^{1}x^{4}+t^{2}x^{5},\quad\quad
B_{t}(x)=t^{5}x^{0}+t^{3}x^{1}+t^{0}x^{2}+t^{4}x^{3},$ $\displaystyle
A_{t}(x)\cdot
B_{t}(x)=t^{8}x^{0}+2t^{6}x^{1}+(t^{7}+t^{4}+t^{3})x^{2}+(t^{9}+t^{7}+t^{5}+t)x^{3}+(t^{7}+t^{6}+t^{5}+t^{2})$
$\displaystyle x^{4}$ $\displaystyle+\leavevmode\nobreak\
(t^{7}+t^{6}+2t^{4})x^{5}+(t^{8}+t^{5}+t)x^{6}+(t^{5}+t^{2})x^{7}+t^{6}$
$\displaystyle x^{8}.$

The key to Algorithm 1 lies in the ability to evaluate $F_{v^{(k)}}(t)$ via
the fast Fourier transform in $O(n\log(n))$ by interpreting these values as
classical convolution coefficients. A subsequent application of $\log_{t}$
turns this into an evaluation of $L_{v^{(k)}}(t)=\log_{t}(F_{v^{(k)}}(t))$
whereby one may apply Theorem 3.1. Similarly, with the aim to apply Theorem
3.6, one may use the approximation of Proposition 2.6 to wrap the ability to
evaluate $F_{v^{(k)}}(t)$ into an algorithm which may require a smaller $t$
evaluation.

Input: Two integer vectors $a=(a_{0},\ldots,a_{n})$ and
$b=(b_{0},\ldots,b_{m})$.

Output: The max-convolution coefficients $c=(c_{0},\ldots,c_{n+m})$

1 Choose $t^{*}$ and $\alpha^{*}$ satisfying the bounds of Theorem 3.6 (e.g.,
$\alpha^{*}>1$ and $t^{*}>\textrm{max}(e,n-1,m-1)$)

2 Compute $\alpha=((t^{*})^{a_{0}},\ldots,(t^{*})^{a_{n}})$ and
$\beta=((t^{*})^{b_{0}},\ldots,(t^{*})^{b_{m}})$

3 Compute
$\alpha^{\prime}=((\alpha^{*}t^{*})^{a_{0}},\ldots,(\alpha^{*}t^{*})^{a_{n}})$
and
$\beta^{\prime}=((\alpha^{*}t^{*})^{b_{0}},\ldots,(\alpha^{*}t^{*})^{b_{m}})$

4 Compute $\ell(t^{*})=\alpha\star\beta$

5 Compute $\ell^{\prime}(t^{*})=\alpha^{\prime}\star\beta^{\prime}$ using FFT

6 Apply $\log_{\alpha^{*}}\left(\ell^{\prime}(t^{*})/\ell(t^{*})\right)$
component-wise to obtain
$c=\lceil\log_{\alpha^{*}}\left(\ell^{\prime}(t^{*})/\ell(t^{*})\right)\rceil$

7 return __ $c$

Algorithm 2 MaxCon - using $D_{v^{(k)}}(t^{*},\alpha^{*})$

######  Remark 6.2.

Algorithms 1 and 2, paired with their corresponding bounds from Section 3,
give algorithms whose output constitute mathematical proofs provided that the
convolution coefficients computed via FFT are exact. Otherwise, the error
introduced by the $\star$ operation must be bounded by $1/2$, $\delta$ should
be taken to be at most $1/2$ in the relevant theorems, and a two-sided
rounding procedure should be applied rather than the ceiling or floor
function.

######  Example 6.3.

We apply Algorithm 2 to the vectors in Example 6.1 using $t^{*}=6$ and
$\alpha^{*}=e$. The values of $\ell(6)$ and $\ell^{\prime}(6)=\ell(e\cdot 6)$
are

$\displaystyle\ell(6)$
$\displaystyle=(1679620,93312,281448,10365400,334404,329184,1687400,7812,46656),$
$\displaystyle\ell^{\prime}(6)$
$\displaystyle=(5006864730.36308,37644747.57839,307062197.51625,81968557661.46344,$
$\displaystyle\quad\quad
326963800.35823,325950992.03191,5008018807.39795,1154326.73120,18822373.78920)$

so that $c=\lceil\log(\ell^{\prime}(6)/\ell(6))\rceil$ gives

$c=\lceil(8.0,6.0,6.99486,8.97562,6.88525,6.89789,7.99561,4.99561,6.0)\rceil=(8,6,7,9,7,7,8,5,6).$

We remark that if we use $t^{*}=2$ and $\alpha^{*}=1.05$, which do not
necessarily meet the bounds of Theorem 3.6, we obtain the following results:

$\displaystyle\ell(2)$ $\displaystyle=(256,128,152,674,228,224,290,36,64),$
$\displaystyle\ell^{\prime}(2)$ $\displaystyle=\ell(1.05\cdot
2)=(378.22859,171.53224,208.81795,1017.32991,311.12599,$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\,\,304.77118,421.16960,45.25101,85.76612),$
$\displaystyle\log_{1.05}(\ell^{\prime}(2)$
$\displaystyle/\ell(2))=(8.0,6.0,6.50915,8.43831,6.37121,6.31101,7.64815,4.68754,6.0).$

A final application of $\lceil\cdot\rceil$ obtains the correct integers $c$
for the max-convolution coefficients of $a$ and $b$.

We conclude with two applications of max-convolution.

###  6.1. Maximum Consecutive Subsums Problem

Given a single vector $v=(v_{1},\ldots,v_{n})\in\mathbb{R}^{n}$, the problem
of determining the largest consecutive sum $\sum_{i=1}^{k}v_{j_{k}+i}$ for
each $k=1,\dots,n$ is known as the _Maximum Consecutive Subsums Problem_
(MCSP). As outlined in [4, § 7.1], MCSP directly reduces to an instance of
MAXCON as follows. Taking $a,b\in\mathbb{R}^{n}$ to be
$a_{k}=-\sum_{i=1}^{k}v_{i}$ and $b_{n-k}=\sum_{i=1}^{k}v_{i}$, the max-
convolution coefficient $c_{n-k}$ describes the largest sum of $k$ consecutive
entries of $v$.

######  Example 6.4.

For $v=(1,4,2,3,8,1,1,5,6,7,5)\in\mathbb{Z}^{11}$, we have

$\displaystyle a$ $\displaystyle=(-1,-5,-7,-10,-18,-19,-20,-25,-31,-38,-43),$
$\displaystyle b$ $\displaystyle=(43,38,31,25,20,19,18,10,7,5,1).$

The max-convolution of $a$ and $b$ is

$c=(42,38,36,33,28,24,23,18,13,8,0,-1,-2,\ldots).$

For example, this shows that the largest sum of $2$ and $5$ consecutive
entries of $v$ is $13$ and $24$ obtained by $6+7$ and $1+5+6+7+5$,
respectively. By convention, one may choose to prepend
$c_{0}=\sum_{i=1}^{n}v_{i}$ to $c$ so as to include the subsum of $n$
consecutive integers in the output as well.

We remark that even though Algorithms 1 and 2 are written for integer input,
the algorithms work for floating point input as well, subject to different
bounds (see Theorems 3.1 and 3.6). When using Algorithm 1, the output is an
upper bound for the true max-convolution coefficients, subject to any error
introduced by the FFT subroutine. Figure 18 shows the magnitude of error on
the $100$ outputs of a random MCSP problem on a vector $v\in[0,1]^{n}$ for
$n=100$ and $n=1000$ with each coordinate selected uniformly at random.

Figure 18. Heatmap of the absolute errors of the numerical computation of
MCSP. The numerical computations were performed on a vector of length $100$
(top) and $1000$ (bottom) with floating-point entries uniformly chosen in
$[0,1]$. The vertical axis indicates the output error on subsums of length $k$
after evaluating at $\textrm{exp}(t)$ (horizontal axis).

###  6.2. Service Curve Constraints

Convolution algorithms are integral in network calculus where systems model
the data flow between networks [14]. The incoming data is described by a
monotonic input function $R(T)$, given in bits per second. The outgoing data
(after a time delay) is described by the output function, $R^{*}(T)$, also in
bits per second. The function $R^{*}(T)$ is constrained by service constraints
that state for any window of time, additional data outputted is bounded. The
curves formed by these constraints are the result of a min-convolution between
the service curve and input function $R(T)$ [14]. That is, a system with an
input function $R(T)$ has an output function $R^{*}(T)$ that will lie in the
area bounded below by a service curve $\beta(T)$ and above by a maximum
service curve $\gamma(T)$ such that

(21) $\inf_{s\leq T}\\{R(T)+\beta(T-s)\\}\leq R^{*}(T)\leq
R(s)+\gamma(T-s),\hskip 14.22636pts\leq T$

Note that the input and output functions admit no subscript to avoid confusion
with the ratio function $R_{v}(t)$. Additionally, we define the time variable
for the service curve to be $T$ rather than $t$ which is the variable base
used for the MAXCON algorithms.

Although the prior focus was on the maximum, it is very simple to reformulate
everything to instead compute the minimum. That is, we take
${t\rightarrow\infty}$ when converging to the maximum while one can take
${t\rightarrow 0^{+}}$ to converge to the minimum.

As an example, we sought to recreate [14, Fig. 5.1] using Algorithm 2 to
compute the discrete min-convolution of the input function and service curves.
To complete this recreation, we first fit a polynomial curve to $R(T)$ from
that plot. In particular, we used the fitted sextic polynomial

$R(T)=1.6738T-0.7492T^{2}-0.08694T^{3}+0.1085T^{4}-0.01101T^{5}-0.001579T^{6}+0.0002085T^{7}.$

The service curves are defined as $\beta(T)=T$ and
$\gamma(T)=\begin{dcases}0&\hbox{if\leavevmode\nobreak\ }T\leq 3\\\
T-3&\hbox{if\leavevmode\nobreak\ }T>3,\end{dcases}$ which corresponds with a 3
second time delay. To create a discrete problem, we evaluated these functions
at equally spaced points.

Figure 19. Discretized service curves computed using Algorithm 2. The curve
$R(T)$ and service constraints $\gamma(T)$ and $\beta(T)$ are discretized into
10 (top) and 100 (bottom) equally spaced points.

We apply Algorithm 2 in the floating-point case, i.e., without rounding, for
the computations with $\alpha=1.01$ and
$t=\left(\frac{1}{(n-1)}\right)^{\frac{1}{0.04}}$. Figure 19 shows the results
of our min-convolution using 10 and 100 discretized points to compute the
corresponding bounds on $R^{*}(T)$ given in (21).

Figure 20. Plots error of the computed points minus the actual points of the
minimum convolution between the lines $R(T)$ and $\beta(T)$ for (left) 10 and
(right) 100 discretized points.

Figure 21. Plots error of the computed points minus the actual points of the
minimum convolution between the lines $R(T)$ and $\gamma(T)$ for (left) 10 and
(right) 100 discretized points.

One can see that even with numerical discretion, the resulting curves in
Figure 19 exhibit satisfactory behavior in recreating the bounds of [14, Fig.
5.1]. Even for 10 discretization points, the computation captures the
essential behavior of the convolution. Furthermore, using 100 discretization
points better captures sharp transitions as well as flatter regions of the
service curve bounds.

Note that this experiment employs two separate convolutions. We compared our
estimated values to the actual minimums computed via brute force, i.e., we
computed the exact minima by computing the bounds given in Equation 21 for
each $T_{i}$, $i=1,\dots,N$ where N is the number of discretized points.
Figures 20 and 21 display the error between the computed points via Algorithm
2 and the actual points for the min-convolution between $R(T)$ and $\beta(T)$,
and $R(T)$ and $\gamma(T)$, respectively. When using a time delay of $3$
seconds, non-zero values first occur when $T>3$ resulting in nearly zero error
before then. Both discretizations have errors on the order of $10^{-3}$ or
smaller. Additionally, the errors are nonnegative which highlights that our
method slightly overestimates the values.

Number of Discrete Points |  $D_{v}(t,\alpha)$) | Brute Force
---|---|---
$10$ | $0.0003841$ | $0.002666$
$50$ | $0.0003392$ | $0.006488$
$100$ | $0.0005358$ | $0.01067$
$500$ | $0.001053$ | $0.04643$
$1000$ | $0.001647$ | $0.1114$
$5000$ | $0.01183$ | $1.3957$
$10000$ | $0.02939$ | $10.5240$
$100000$ | $1.1738$ | $1546.2364$
Table 1. Time, in seconds, to calculate the min-convolution between $R(T)$ and $\beta(T)$. Number of Discrete Points | $D_{v}(t,\alpha)$ | Brute Force
---|---|---
$10$ | $0.0001468$ | $0.002490$
$50$ | $0.0001085$ | $0.005987$
$100$ | $0.0001927$ | $0.007235$
$500$ | $0.0007843$ | $0.03623$
$1000$ | $0.001421$ | $0.1315$
$5000$ | $0.006734$ | $1.5642$
$10000$ | $0.01953$ | $5.2610$
$100000$ | $0.7965$ | $1239.4949$
Table 2. Time, in seconds, to calculate the min-convolution between $R(T)$ and
$\gamma(T)$.

Tables 1 and 2 compare the time in seconds for one application of Algorithm 2
and a brute force computation between $R(T)$ and $\beta(T)$, and $R(T)$ and
$\gamma(T)$, respectively, using a single processor. The difference between
quasi-linear and quadratic time algorithms becomes apparent as $n$ grows. Note
that utilizing Algorithm 1 produced similar error and computational time.

## References

  * [1] K. Asadi and M. L. Littman.  An alternative softmax operator for reinforcement learning.  In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 243–252. JMLR.org, 2017.
  * [2] G. Bergman.  The logarithmic limit-set of an algebraic variety.  Trans. Am. Math. Soc., 157:459–469, 1971.
  * [3] P. Blanchard, D. J. Higham, and N. J. Higham.  Accurately computing the log-sum-exp and softmax functions.  IMA Journal of Numerical Analysis, 41(4):2311–2330, 08 2020.
  * [4] M. Cygan, M. Mucha, K. Wundefinedgrzycki, and M. Włodarczyk.  On problems equivalent to (min,+)-convolution.  ACM Trans. Algorithms, 15(1), 2019.
  * [5] T. DeWolff and F. Schroeter.  The boundary of amoebas.  arXiv Preprint: 1310.7363, 2013.
  * [6] M. Forsberg, M. Passare, and A. Tsikh.  Laurent determinants and arrangements of hyperplane amoebas.  Adv. Math, 151:45–70, 2000.
  * [7] W. Liu, Y. Wen, Z. Yu, and M. Yang.  Large-margin softmax loss for convolutional neural networks.  In M. Balcan and K. Weinberger, editors, INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 48, volume 48 of Proceedings of Machine Learning Research, 2016.  33rd International Conference on Machine Learning, New York, NY, JUN 20-22, 2016.
  * [8] D. Maclagan and B. Sturmfels.  Introduction to Tropical Geometry, volume 161 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2015.
  * [9] R. T. Moenck.  Practical fast polynomial multiplication.  In Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation, SYMSAC ’76, page 136–148, New York, NY, USA, 1976. Association for Computing Machinery.
  * [10] F. Nielsen and K. Sun.  Guaranteed bounds on information-theoretic measures of univariate mixtures using piecewise log-sum-exp inequalities.  Entropy, 18(12), 2016.
  * [11] J. Pfeuffer and O. Serang.  A bounded p-norm approximation of max-convolution for sub-quadratic bayesian inference on additive factors.  J. Mach. Learn. Res., 17:36:1–36:39, 2016.
  * [12] O. Serang.  A fast numerical method for max-convolution and the application to efficient max-product inference in bayesian networks.  Journal of computational biology : a journal of computational molecular cell biology, 22, 01 2015.
  * [13] L. N. Trefethen and J. A. C. Weideman.  The exponentially convergent trapezoidal rule.  SIAM Review, 56(3):385–458, 2014.
  * [14] A. Van Bemten and W. Kellerer.  Network calculus: A comprehensive guide, 10 2016.
  * [15] I. Zang.  A smoothing-out technique for min-max optimization.  Math. Programming, 19(1):61–77, 1980.
  * [16] G. Zhao, Z. Wang, and H. Mou.  Uniform approximation of min/max functions by smooth splines.  Journal of Computational and Applied Mathematics, 236(5):699–703, 2011.  The 7th International Conference on Scientific Computing and Applications, June 13–16, 2010, Dalian, China.