1
$\begingroup$

Preliminaries.

Consider the semiring $\mathbb{T} = \{\mathbb{R} \cup \{-\infty\}, \oplus, \odot \}$, where the $a \oplus b = \max\{a,b\}$ and that $a \odot b = a + b$. The addition and scalar multiplication ($\oplus$,$\odot$) can be referred to as tropical addition and tropical product, respectively. One can equip this semiring with tropical powers as repetitions of tropical multiplication as follows: $a ^ b = \underbrace{a \odot \dots \odot a}_{b} = ba$ where $b \in \mathbb{N}$.

From this construct, one can define tropical monomials and polynomials analogously to "traditional" algebraic monomials and polynomials. For example, a 2-dimensional tropical monomial is given as follows $x^a \odot y^b = ax + by$. For ease of notation, consider $\mathbf{x},\mathbf{a} \in \mathbb{R}^n$ and thus $\mathbf{x}^\mathbf{a} = x_1^{a_1}x_2^{a_2}\dots x_n^{a_n}$. Now one can define a tropical polynomial as a sum of monomials as follows:


A tropical polynomial $f(x_1,x_2,\dots,x_n)$ is a finite tropical sum of a tropical monomials. $$ \begin{equation} f(\mathbf{x}_1,\dots,\mathbf{x}_k) = (c_1\odot\mathbf{x}_1^{\mathbf{a}_1})\oplus \dots \oplus (c_k \odot \mathbf{x}_k^{\mathbf{a}_k}) \end{equation} $$ where the exponents are integers $\mathbf{a}_i = [a_{i1}, \dots,a_{in} ]^\top\in \mathbb{N}^n$ and that $c_k \in \{\mathbb{R} \cup \{\infty\}\}$.

Note that a tropical polynomial can be seen as max among a set of affine functions as follows:

$$ \begin{equation} f(\mathbf{x}_1,\dots,\mathbf{x}_k) = \max\Bigg\{c_1 + \sum_i^n a_{1i} x_{1i},c_2 + \sum_i^n a_{2i} x_{2i}, \dots,c_k + \sum_i^n a_{ki} x_{ki}\Bigg\} \end{equation} $$

Now, one can define the solution set to a tropical polynomial as the set where the polynomial is not differentiable or achieves its maximum at least twice. This is referred to as a hypersurface. This hypersurface divides the domain of the tropical polynomial into regions where the function is linear in those regions. Thereafter, one can define a dual subdivision of a given hypersurface of the the function f $\Delta_H(f)$ as a convex hull of the exponent powers. For example consider the same tropical polynomial $f(\mathbf{x}_1,\dots,\mathbf{x}_k)$ with $c_i = 0 \forall i$ for ease, we have the definition of the dual subdivision given as follows:

$\Delta_H(f) = \text{convex hull} \Bigg\{ \begin{bmatrix} a_{1i} \\ \vdots \\ a_{1n}\end{bmatrix}, \begin{bmatrix} a_{2i} \\ \vdots \\ a_{2n}\end{bmatrix}, \dots \begin{bmatrix} a_{ki} \\ \vdots \\ a_{kn}\end{bmatrix}\Bigg\}$

Given this geometric view, one can study the complexity of a tropical polynomial in terms of the number of linear regions by studying the number of vertices of the polytope $\Delta_H(f)$ as one is the dual view of the other.

References can be found here Link1, Link2, Link3, Link4.

My question is regarding the more general view of tropical polynomials as signomials where the exponent powers are real numbers and not only integers. To do so, if we equip the semiring $\mathbb{T}$ with a proper definition of tropical power under real exponents through means of defining power inverses as follows $x^b = bx$ when $x,b \in \mathbb{R}$ similar to section 1.3 in ref5. I do not see any reason to NOT view the tropical signomial $f(\mathbf{x}_1,\dots,\mathbf{x_k})$ where the powers $\mathbf{a_i} \forall i$ are real numbers as generic tropical polynomials exhibiting the same hypersurface. That is the number of linear regions and dual subdivision can be equivalently well defined too. Can anyone comment on whether treating or extending geometrically the notion of tropical polynomials to tropical signomials not work for the definition of a hypersurface and a dual subdivision? That is it seems to me that we can still use the same definiton of a hypersurface and its corresponding dual subdivision as the ones used for tropical polynomials and study the complexity tropical signomials (number of linear regions)? I'm aware that other nice geometric structure is lost as there is no clear definition of root multiplicity of the solutions to the hypersurface of the tropical signomial. In short, is there any reason not to study the complexity of a tropical signomial by counting the number of indices of its dual subdivision that is defined precisely as it is for tropical polynomials?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.