Dima Grigoriev
email: dmitry.grigoryev@univ-lille.fr

Decomposing tropical rational functions

An algorithm is designed to decompose a tropical univariate rational function into a composition of tropical binomials and trinomials. When a function is monotone, the composition consists just of binomials. Similar algorithms are designed for decomposing tropical algebraic rational functions being (in the classical language) piece-wise linear functions with rational slopes of their linear pieces. In addition, we provide a criterion when the composition of two tropical polynomials commutes (for classical polynomials a similar question was answered by J. Ritt).

Introduction

We study decomposing tropical univariate rational functions (compositions of tropical rational functions find applications in deep learning of neural networks, see e. g. [START_REF] Montúfar | On the number of linear regions of deep neural networks[END_REF], [START_REF] Zhang | Tropical Geometry of Deep Neural Networks[END_REF]). A tropical rational function is the tropical quotient (which corresponds to the subtraction in the classical sense) of two tropical polynomials. Thus, a tropical rational function is (classically) a piece-wise linear function with integer slopes of its linear pieces. A tropical root of a tropical rational function is defined as a point at which the function is not differentiable.

Relaxing the requirement that the slopes are integers allowing them to be rationals, we arrive to the concept of tropical algebraic rational functions or tropical Newton-Puiseux rational functions [START_REF] Grigoriev | Tropical Newton-Puiseux polynomials[END_REF] playing the role of algebraic functions in tropical algebra. Furthermore, in sections 1, 2 one can consider real slopes, then the algorithms are supposed to be executed on Blum-Shub-Smale machines [START_REF] Blum | Complexity and real computation[END_REF].

In classical algebra the problem of decomposing polynomials, rational and algebraic functions was elaborated in [START_REF] Gathen | Functional decomposition of polynomials: the wild case[END_REF], [START_REF] Kozen | Decomposition of algebraic functions[END_REF], [START_REF] Zur Gathen | Multivariate polynomial decomposition[END_REF]. In tropical algebra the answer to the decomposing problem differs essentially from its classical counterpart. We show that a tropical rational function is a composition of binomials and trinomials. The similar holds for tropical algebraic rational functions.

In section 1 we introduce tropical monotone rational and algebraic rational functions and bound the number of tropical roots of compositions of tropical polynomials, monotone rational functions and rational functions.

In section 2 we design an algorithm which decomposes a tropical algebraic function and also a tropical monotone algebraic rational function into a composition of tropical binomials. In addition, we design an algorithm which decomposes a tropical algebraic rational function into a composition of tropical binomials and trinomials. Moreover, we provide a bound on the number of components.

In section 3 decompositions of tropical rational functions (so, with integer slopes of their linear pieces) are studied. We design an algorithm which decomposes a tropical monotone rational function into a composition of tropical monotone binomials and monotone trinomials. Also we design an algorithm which decomposes a tropical rational function into a composition of tropical binomials and trinomials. In addition, a criterion is provided, when a tropical monotone trinomial is decomposable. Finally, bounds on the number of components are given.

In section 4 we prove (Theorem 4.2) that the composition of two tropical polynomials f, g without free terms commutes: f • g = g • f iff there is a common fixed point x 0 (perhaps, x 0 = ∞) for both f, g, i. e. f (x 0 ) = g(x 0 ) = x 0 and there exist a tropical increasing algebraic rational function h and integers a, b ≥ 1, k, m ≥ 0 such that either f = h k , g = h m or f = ax + x 0 (1 -a), g = bx + x 0 (1 -b) on the interval (-∞, x 0 ] (similar conditions hold on the interval [x 0 , ∞)), unless f = x + c 1 , g = x + c 2 , x ∈ R for some c 1 , c 2 ∈ R. In addition, we provide an example of a one-parametric family {T n } n≥2 of (commuting) increasing tropical rational functions on the interval [0, ∞) such that T n •T m = T mn and which do not satisfy the above conclusion of Theorem 4.2 in general. For classical polynomials the answer to commutativity was given in [START_REF] Ritt | Prime and composite polynomials[END_REF], [START_REF] Ritt | Permutable rational functions[END_REF] (more recent generalizations and further references one can find in [START_REF] Pakovich | Semiconjugate Rational Functions: A Dynamical Approach[END_REF]), in which commuting Chebyshev polynomials play a crucial role.

In section 5 we introduce tropical polynomial (respectively, Laurent polynomial and rational) parametrizations of polygonal lines. We show that any polygonal line admits a tropical rational parametrization and provide criteria when it does admit a tropical polynomial (respectively, Laurent polynomial) parametrization.

Tropical monotone rational functions

Recall (see e. g. [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]) that a (univariate) tropical polynomial has a form f = min 0≤i≤d {ix + a i }, a i ∈ R ∪ {∞}. Linear functions ix + a i , 0 ≤ i ≤ d are called tropical monomials. So, the minimum plays the role of the addition in tropical algebra, while the addition plays the role of the multiplication. Thus, f is a convex piece-wise linear function with non-negative integer slopes of the edges of its graph (sometimes, slightly abusing the terminology we call them the edges of f ). We consider the natural ordering of the edges from the left to the right. A point x ∈ R is a tropical root of f if the minimum in f is attained at least for two linear functions ix + a i , 0 ≤ i ≤ d. In other words, tropical roots of f are the points at which f is not differentiable.

A tropical rational function is a difference (which plays the role of the division in tropical algebra) of two tropical polynomials. It is a piece-wise linear function. So, its graph consists of several edges. Conversely, any continuous piece-wise linear function with integer slopes of its linear pieces (edges of its graph) is a tropical rational function (cf. [START_REF] Grigoriev | Tropical Newton-Puiseux polynomials[END_REF] where one can find further references). As the roots of a tropical rational function we again mean the points at which the function is not differentiable.

If g, h are tropical rational functions with p, q tropical roots, respectively, then (see [START_REF] Grigoriev | Tropical combinatorial Nullstellensatz and fewnomials testing[END_REF]) the number of the roots of

• min{g, h} is at most p + q + 1;

• g + h or g -h is at most p + q.

In this paper we study compositions g • h (being tropical rational functions as well). Note that if g, h are tropical polynomials then g • h is also a tropical polynomial. If s 1 , . . . , s k are consecutive (integer) slopes of (the linear pieces of) a tropical rational function g then g is a tropical polynomial iff

s 1 > • • • > s k ≥ 0.
In a tropical monotone increasing (or decreasing, respectively) rational function g its slopes are positive (respectively, negative). Note that any tropical polynomial min 1≤i≤d {ix + a i } without free term is monotone increasing.

One can directly verify the following proposition. Remark 1.2 In general, the number of tropical roots of the composition g• h of tropical rational functions does not exceed pq+p+q. Moreover, if s 0 , . . . , s p (respectively, t 0 , . . . , t q ) are the slopes of (the graph of ) g (respectively, h) listed with possible repetitions (multiplicities), then the slopes of g • h are among s i t j , 0 ≤ i ≤ p, 0 ≤ j ≤ q.

For a tropical rational function g = max{-2x + 1, 2x -1} the number of the tropical roots of k iterations of [START_REF] Montúfar | On the number of linear regions of deep neural networks[END_REF] (see also [START_REF] Grigoriev | Tropical combinatorial Nullstellensatz and fewnomials testing[END_REF]).

g k := g • • • • • g is 2 k -1
Admitting rational coefficients in min i {b i x + a i }, 0 ≤ b i ∈ Q, we arrive to the concept of tropical algebraic functions (or tropical Newton-Puiseux polynomials) [START_REF] Grigoriev | Tropical Newton-Puiseux polynomials[END_REF]. Respectively, we consider tropical algebraic rational functions being differences of tropical algebraic functions [START_REF] Grigoriev | Tropical Newton-Puiseux polynomials[END_REF].

Remark 1.3 The above statement in Proposition 1.1 on the slopes of tropical rational functions holds for tropical algebraic rational functions as well with the difference that now we admit rational slopes rather than just integers. The above bounds on the number of tropical roots also hold literally for tropical algebraic rational functions.

Decomposing tropical algebraic rational functions

In this section we consider tropical algebraic rational functions. As a tropical algebraic rational binomial we mean a function of the form either min{b

1 x + a 1 , b 2 x + a 2 }, 0 = b 1 , b 2 ∈ Q or max{b 1 x + a 1 , b 2 x + a 2 }.
In the geometric language the former function is a convex piece-wise linear function with two (unbounded) edges (and we call it a tropical algebraic binomial), while the latter one is concave. If b 1 , b 2 > 0 then in both cases the functions are monotone increasing.

Proposition 2.1 (i)

There is an algorithm which for a tropical algebraic function f with k tropical roots yields a decomposition of f into k tropical algebraic binomials;

(ii) let f be a tropical monotone algebraic rational function with k tropical roots. Then the algorithm yields a decomposition of f into k tropical monotone algebraic rational binomials.

Remark 2.2 Due to Proposition 1.1 and taking into the account that each tropical algebraic rational binomial has a single tropical root, we conclude that in Proposition 2.1 one can't take less than k components.

Proof. The proofs for both items (i), (ii) proceed similarly. Let f have consecutive slopes s 0 , . . . , s k of its linear pieces. Recall that s 0 > s 1 > • • • > s k ≥ 0 in case (i) and s 1 , . . . , s k > 0 in case (ii). Denote by x l the l-th tropical root of f, 1 ≤ l < k. Take a (piece-wise linear) function h with k slopes s 0 .s 1 , . . . , s l-1 , s l+1 • s l-1 /s l , . . . , s k • s l-1 /s l coinciding with f for x ≤ x l and replacing f by the composition with the linear function ((s l-1 /s l )x + f (x l )(1 -s l-1 /s l )) • f for x ≥ x l . Thus, h has the tropical roots x 1 , . . . , x l-1 , x l+1 , . . . , x k . The described procedure replacing f by h we call straightening: one tropical root (at x l ) disappears.

Take a tropical algebraic rational binomial g coinciding with the identity function x → x for x ≤ f (x l ) and with the linear function (s l /s l-1 )x+f (x l )(1s l /s l-1 ) for x ≥ f (x l ). Then f = g • h. Note that in case (i) g is a tropical algebraic binomial since s l-1 /s l < 1.

Proceeding by induction on k we complete the proof of the Proposition. 2

Remark 2.3 Observe that each tropical root of f corresponds to a suitable component in a decomposition of f . Thus, by choosing (in the proof of Proposition 2.1 above) the tropical roots in different orders, we obtain k! "combinatorially different types" of decompositions of f . Now let f be a tropical algebraic rational function, our goal is to design an algorithm which decomposes f . Let for definiteness the first edge of f with a non-zero slope have a positive slope. Consider tropical roots x of f such that f has an edge with a negative slope to the right of x. If there does not exist such x then f is (non-strictly) monotone increasing, and we proceed to study the monotone case later. Among such x pick x 0 (perhaps, if not unique then pick any of them) with the maximal value f (x 0 ). Take a tropical root x 1 > x 0 of f with the minimal value f (x 1 ), provided that there is a tropical root greater than x 0 . We have f (

x 1 ) < f (x 0 ), f ([x 0 , x 1 ]) = [f (x 1 ), f (x 0 )] in case when x 1 does exist and f ([x 0 , ∞)) = (-∞, f (x 0 )], otherwise. In any case max{f (x) : x ∈ (-∞, x 0 ]} = f (x 0 ).
First we consider the case when f (x) ≤ f (x 0 ) for all x ≥ x 1 , provided that there is a tropical root of f greater than x 0 (or f (x) ≤ f (x 0 ) for all x ≥ x 0 in case when there are no tropical roots greater than x 0 ). Note that in this case f (x) ≤ f (x 0 ) for all x ≥ x 0 due to the choice of x 0 .

If both adjacent to x 0 edges of f have non-zero slopes then the edge to the left from x 0 has a positive slope s 0 > 0, while the edge to the right from x 0 has a negative slope s 1 < 0 (due to the choice of x 0 ). Take as g a tropical algebraic rational binomial which coincides with the identity function x → x for x ≤ f (x 0 ) and with a linear function (s

1 /s 0 )x + f (x 0 )(1 -s 1 /s 0 ) for x ≥ f (x 0 ). So, g is a tropical non-monotone algebraic rational binomial.
As h take a tropical algebraic rational function which coincides with f for x ≤ x 0 and coincides with the composition with the linear function ((

s 0 /s 1 )x+ f (x 0 )(1 -s 0 /s 1 )) • f for x ≥ x 0 . Then f = g • h.
By a block of edges of f we mean a sequence of consecutive edges of the equal signs of their slopes (ignoring edges with zero slopes). Observe that h has one less block of edges than f does. Thus, by passing from f to h we straighten f at point x 0 .

Otherwise, if one of adjacent to x 0 edges has zero slope then as g take a tropical binomial coinciding with the identity function x → x for x ≤ f (x 0 ) and with the linear function -x + 2f (x 0 ) for x ≥ f (x 0 ). As h take a tropical algebraic rational function which coincides with f for x ≤ x 0 and with the composition with the linear function (-x + 2f (x 0 )) • f for x ≥ x 0 . Then again f = g • h, and h has one less block of edges than f does. On the other hand, h has the same number of tropical roots as f does, so one does not straighten a piece-wise linear function at a point if one of two adjacent edges to this point has zero slope. Now we proceed to the case when f (x) takes a value greater than f (x 0 ) for some x > x 1 (in this case there are tropical roots of f greater than x 0 , therefore, x 1 does exist). Then min{f (x) :

x ≥ x 0 } = f (x 1 ).
A tropical regular algebraic rational trinomial is a piece-wise linear function with 3 edges having rational non-zero slopes. If the slopes are decreasing or increasing positive integers we talk about a tropical trinomial.

Construct the following tropical algebraic rational functions h, g. If both the edge of f with the right (and respectively, the left) end-point (x 0 , f (x 0 )) has a non-zero slope s + (respectively, a non-zero slope s -) then h on the interval (-∞, x 0 ] coincides with the composition (-(s

-/s + )x + f (x 0 )(1 + s -/s + )) • f . Note that s + > 0, s -< 0. As g take a function which on the interval (-∞, f (x 0 )] coincides with the linear function -(s + /s -)x + f (x 0 )(1 + s + /s -). We have max{h(x) : x ≤ x 0 } = f (x 0 ) and g((-∞, f (x 0 )]) = (-∞, f (x 0 )]. In case if s + • s -=
0 then h on the interval (-∞, x 0 ] coincides with f , and g on the interval (-∞, f (x 0 )] coincides with the identity function x → x.

On the interval [x 0 , x 1 ] the function h in both cases coincides with the composition (-x+2f (x 0 ))•f , and g on the interval [f (x 0 ), 2f (x 0 )-f (x 1 )] coincides with the linear function

-x+2f (x 0 ). Then h([x 0 , x 1 ]) = [f (x 0 ), 2f (x 0 )-f (x 1 )] and g([f (x 0 , 2f (x 0 ) -f (x 1 )]) = [f (x 1 ), f (x 0 )].
Finally, define h on the interval [x 1 , ∞) and g on the interval [2f (x 0 )f (x 1 ), ∞). Similar to the consideration above of the interval (-∞, x 0 ] denote by t -(respectively, t + ) the slope of the edge of f with the right (respectively, the left) end-point (x 1 , f (x 1 )). If t -• t + = 0 (in this case t -< 0, t + > 0 due to the choice of x 1 ) then h on the interval [x 1 , ∞) coincides with the composition with the linear function (-(t

-/t + )x + 2f (x 0 ) + f (x 1 )(t -/t + -1)) • f . In this case g on the interval [2f (x 0 ) -f (x 1 ), ∞) coincides with the linear function -t + /t -x + f (x 1 ) + t + /t -(2f (x 0 ) -f (x 1 )). Then min{h(x) : x 1 ≤ x < ∞} = 2f (x 0 ) -f (x 1 ) and g([2f (x 0 ) -f (x 1 ), ∞)) = [f (x 1 ), ∞).
Otherwise, if t -• t + = 0 then h on the interval [x 1 , ∞) coincides with the composition (x+2f (x 0 )-2f (x 1 ))•f , and g on the interval [2f (x 0 )-f (x 1 ), ∞) coincides with the linear function x -2f (x 0 ) + 2f (x 1 ). In this case again min{h(x) :

x 1 ≤ x < ∞} = 2f (x 0 ) -f (x 1 ) and g([2f (x 0 ) -f (x 1 ), ∞)) = [f (x 1 ), ∞). Thus, f = g • h.
Observe that h has two less blocks of edges than f does. Also note that x is a tropical root of h with the adjacent to x edges of h with the equal signs of their slopes iff x is a tropical root of f satisfying the same property (we call such x a non-extremal tropical root of h because x is not a local extremal of h). In addition, the numbers of edges with zero slope are the same for f and for h. Thus, applying two described decomposition procedures to f and obtaining g to be either a tropical non-monotone algebraic rational binomial or a tropical regular algebraic rational trinomial, while it is possible, we arrive to a tropical algebraic rational function f 0 which is non-decreasing, so the slopes of its edges are non-negative. Thus,

f = g 1 • • • • • g k • f 0 (1)
where each of g 1 , . . . , g k is either a tropical non-monotone algebraic rational binomial (their number among g 1 , . . . , g k denote by k 2 ) or a tropical regular algebraic rational trinomial (their number denote by k 3 := k -k 2 ). Therefore, k 2 + 2k 3 equals the number of blocks of edges of f . Now take a non-extremal tropical root x 4 of f 0 . Let s -> 0 (respectively, s + > 0) be the slope of the adjacent to x 4 left edge (respectively, right edge) of f 0 . Denote by g (1) a tropical monotone increasing algebraic rational binomial which coincides with the identity function on the interval (-∞, f 0 (x 4 )] and which coincides with the linear function (s + /s -)x + f (x 0 )(1 -s + /s -) on the interval [f 0 (x 4 ), ∞). Denote by h 0 a tropical non-decreasing algebraic rational function which coincides with f 0 on the interval (-∞, x 4 ] and which coincides with the composition ((s -/s + )x+f 0 (x 4 )(1-s -/s + ))•f 0 on the interval [x 4 , ∞).

Then f 0 = g (1) • h 0 and h 0 has no tropical root at x 4 , while having all other tropical roots of f 0 , so h 0 is a straightening of f 0 . Applying the just described procedure to all non-extremal tropical roots of f 0 , we obtain a decomposition

f 0 = g (1) 1 • • • • • g (1) k 1 • f (1) (2)
where each of g

1 , . . . , g

k 1 is a tropical increasing algebraic rational binomial. Every second edge of f (1) has zero slope, and the number k 0 of edges with zero slope of f (1) equals the same number of f . Observe that k 1 equals the number of non-extremal tropical roots of f (and also equals the number of non-extremal tropical roots of f 0 ). Hence k 1 + k 2 + 2k 3 does not exceed the number of edges with non-zero slopes of f .

As a tropical singular algebraic rational trinomial we mean a trinomial whose middle edge has zero slope. Slightly abusing the terminology, we admit singular trinomials without one or two edges with non-zero slopes.

We are looking for a decomposition

f (1) = g (0) k 0 • • • • • g (0) 1 (3)
where g (0)

i , 1 ≤ i ≤ k 0 is a tropical singular algebraic trinomial. To decompose take the left-most interval [x 0 , x 1 ] on which f (1) is constant, in other words, the edge of f (1) on [x 0 , x 1 ] has zero slope. It can happen that x 0 = -∞, in this case some of the following considerations become void. Define g (0)

1 on the interval (-∞, x 0 ] as the identity function and on the interval [x 0 , x 1 ] as the constant function with the value x 0 .

Let f (1) on the interval (-∞, x 0 ] equal a linear function sx + r (so, s is the slope of the left-most edge of f (1) ), in particular sx 0 + r = f (1) (x 0 ). Define g (0) (later we'll get that g (0) = g (0)

k 0 • • • • • g (0)
2 ) on the interval (-∞, x 0 ] as the linear function sx + r. Therefore, g (0) • g (0) 1 on the interval (-∞, x 0 ] coincides with f (1) . The same coincidence holds on the interval [x 0 , x 1 ] as well. Let the edge of f (1) with the left end-point (x 1 , f (1) (x 1 ) = sx 0 + r) have a slope p. Then define g (0)

1 on the interval [x 1 , ∞) as the linear function (p/s)x+x 0 -(p/s)x 1 . Also define g (0) on the interval [x 0 , ∞) as the composition

f (1) • ((s/p)x -(s/p)x 0 + x 1 ). Then f (1) = g (0) • g (0)
1 . Now we observe that g (0) is a continuous non-decreasing piece-wise linear function: we have constructed it by gluing at x 0 two non-decreasing piece-wise linear functions both having the value sx 0 + r = f (1)

(x 0 ) = f (1) (x 1 ) at x 0 .
Moreover, the slope of the edge of g (0) with the right end-point (x 0 , f (1) (x 0 )) equals s which coincides with the slope of the edge of g (0) with the left endpoint (x 0 , f (1) (x 0 )). Therefore, g (0) has no tropical root at x 0 (so, g (0) is a straightening of f (1) ), and g (0) is of a similar shape as f (1) , i. e. g (0) is a non-decreasing piece-wise linear function whose every second edge has zero slope. On the other hand, g (0) has one less edge with zero slope than f (1) does. Continuing in this way, we construct a required decomposition [START_REF] Zur Gathen | Multivariate polynomial decomposition[END_REF].

Combining (1), ( 2) and (3) we complete the proof of the following theorem.

Theorem 2.4 There is an algorithm which decomposes a tropical algebraic rational function

f = g 1 • • • • • g k • g (1) 1 • • • • • g (1) k 1 • g (0) k 0 • • • • • g (0) 1 (4)
where each g i , 1 ≤ i ≤ k is either a tropical regular algebraic rational trinomial or a tropical non-monotone algebraic rational binomial (cf. ( 1)), each g

(1)
j , 1 ≤ j ≤ k 1 is a tropical monotone algebraic rational binomial (cf. ( 2)), and each g

(0) l , 1 ≤ l ≤ k 0 is a tropical singular algebraic trinomial (cf. (3)).
Moreover, if k 3 is the number of tropical regular algebraic rational trinomials, and k 2 is the number of tropical non-monotone algebraic rational binomials in (4), so k 3 + k 2 = k then 2k 3 + k 2 is the number of blocks of edges of f of the equal (non-zero) signs of their slopes. The number 2k 3 +k 2 +k 1 does not exceed the number of edges of f with non-zero slopes, finally k 0 equals the number of edges with zero slopes.

Remark 2.5

The number of tropical roots of f is greater or equal to k 1 + 2k 0 , and on the other hand, is less or equal to 2k 3 + k 2 + k 1 + 2k 0 , the latter number also equals the total number of tropical roots in the components of f from (4) (cf. Remark 1.2).

Tropical rational functions

In this section we study decompositions of tropical rational functions, we recall that the slopes of edges of a piece-wise rational function f are integers (unlike the section 2 in which the slopes could be rationals).

Theorem 3.1 (i)

There is an algorithm which for a tropical monotone rational function f yields its decomposition into tropical monotone binomials and tropical monotone trinomials. The number of components does not exceed the number of tropical roots of f (cf. Proposition 2.1 and Remark 2.2);

(ii) there is an algorithm which decomposes a tropical rational function

f = g 1 • • • • • g k • h 1 • • • • • h m • g (0) k 0 • • • • • g (0) 1 (cf. ( 4
)
) where each g i , 1 ≤ i ≤ k is either a tropical non-monotone rational binomial with ±1 slopes or a tropical non-monotone rational trinomial with ±1 slopes (cf. ( 1)), each h j , 1 ≤ j ≤ m is either a tropical regular monotone binomial or a tropical regular monotone trinomial, and each g (0)

l , 1 ≤ l ≤ k 0 is a tropical singular monotone trinomial. The number of binomials among g 1 , . . . , g k plus the double number of trinomials among g 1 , . . . , g k does not exceed the number of blocks of edges of f (cf. Theorem 2.4). The number m does not exceed the number of edges of f , and the number k 0 equals the number of edges of f with zero slopes (again cf. Theorem 2.4 and (3));

(iii) let f be a tropical monotone rational function (respectively, a tropical polynomial) with the slopes of its edges a 0 , . . . , a n ≥ 1 (respectively, a 0 > . . . > a n ≥ 1) and denote by q i , 1 ≤ i ≤ n the denominator of the irreducible fraction a i /a i-1 . Then f is a composition of tropical rational binomials (respectively, tropical binomials) iff (q

1 • • • q n )|a 0 . Remark 3.2 If f satisfies the latter condition in (iii) we call f completely decomposable.
This condition in (iii) is equivalent to a more symmetric one: for any m ≥ 1 and j ≥ 0 such that m + 2j < n it holds

0≤i≤j a m+2i | 0≤i≤j+1 a m+2i-1 .
In particular, for n = 2 (trinomials), the condition in (iii) for a 0 , a 1 , a 2 is equivalent to a 1 |(a 0 a 2 ).

Proof. (i). If an increasing f has at least 4 edges then take any its tropical root x 0 being neither the left-most nor the right-most. Define h to coincide with f on the interval (-∞, x 0 ] and g to coincide with the identity function on the interval (-∞, f (x 0 )]. Then define h on the interval [x 0 , ∞) to coincide with the linear function x + f (x 0 ) -x 0 , and define g on the interval [f (x 0 ), ∞) to coincide with the composition f

• (x -f (x 0 ) + x 0 ). Then f = g • h.
Continuing in this way, applying further the described construction to g, h we complete the proof of (i).

(ii). First, similar to the proof of Theorem 2.4 one represents (by means of straightening) f = g • h (assume w.l.o.g. that the first edge of f with non-zero slope has a positive slope), where g is either a tropical non-monotone binomial with the slopes of its edges 1 and -1 or a tropical trinomial with the slopes 1, -1, 1, while h being a tropical rational function with less number of blocks of edges than f . Continuing in this way, while it is possible, we arrive to a tropical nondecreasing rational function 1)). Applying to f (0) the constructions from the proof of Theorem 2.4 (cf. ( 3)) and from the proof of Theorem 3.1 (i), we complete the proof of (ii).

f (0) such that f = g 1 • • • • • g k • f (0) (cf. (
(iii). The proofs for both cases f being a tropical increasing rational function or a tropical polynomial go similarly.

Let

f = g 1 • • • • • g k where each g i , 1 ≤ i ≤ k is a tropical increasing rational binomial (respectively, a tropical binomial) with slopes b i , c i , 1 ≤ i ≤ k (respectively, b i > c i ). Denote by r i , 1 ≤ i ≤ k the unique tropical root of g i . Partition R into intervals with the end-points (g i+1 • • • • • g k ) -1 (r i ), 1 ≤ i ≤ k.
In case of tropical polynomials f all these end-points are the tropical roots of f . In case of tropical increasing rational functions f all g i for which

(g i+1 • • • • • g k ) -1 (r i ) being not a tropical root of f , give a contribution into g 1 •• • ••g k by
multiplying all the slopes of its edges on the intervals by the same integer, so w.l.o.g. one can assume that each (

g i+1 • • • • • g k ) -1 (r i ), 1 ≤ i ≤ k is a tropical root of f . For 1 ≤ j ≤ n take the set I j of 1 ≤ i ≤ k such that (g i+1 • • • • • g k ) -1 (r i ) is j-th root t j of f . Then a j /a j-1 = i∈I j (c i /b i ). Therefore, q j | i∈I j b i . Since i b i = a 0 , we conclude that (q 1 • • • q n )|a 0 . Conversely, let (q 1 • • • q n )|a 0 . Put integers b j := q j , 1 ≤ j ≤ n -1, b n := a 0 /(b 1 • • • b n-1 ) and c j := b j a j /a j-1 , 1 ≤ j ≤ n.
Construct g n , . . . , g 1 recursively. As a base of recursion take g n such that its unique tropical root coincides with t n (observe that g n is defined uniquely up to an additive shift, in other words, one can replace g n by g n + e, e ∈ R). Assume that g n , . . . , g m+1 are already constructed by recursion. Then take g m such that its unique tropical root equals (g m+1 • • • • • g n )(t m ). At the very last step of recursion we adjust g 1 by a suitable additive shift to make

g 1 • • • • • g n coincide with f at one (arbitrary) point. Hence f = g 1 • • • • • g n . 2
Remark 3.3 The algorithms designed in sections 2, 3 have polynomial complexity since after each procedure yielding a component (cf. ( 1), ( 2), ( 3)) either the number of blocks of edges or the number of edges drops at least by one.

Tropical polynomials with commuting composition

Let f, g be tropical polynomials without free terms (some statements below hold also for more general tropical increasing algebraic rational functions). In this section we give a criterion when f • g = g • f . Note that the inverse f -1 (i. e. f • f -1 = Id equals the identity function) is a tropical increasing algebraic rational function. Denote by

f k := f • • • • • f the k times iteration of f
. We agree that f 0 := Id. Note that tropical increasing algebraic rational functions constitute a group with respect to the composition.

Remark 4.1 Let f, g be tropical increasing algebraic rational functions and f

• g = g • f hold. We call x a fixed point of f if f (x) = x. The set F f ⊂ R of fixed points is a finite union of disjoint closed intervals {[x i , y i ]} i (including isolated points, i. e. x i = y i ). Since f • g(x) = g • f (x) = g(x) we conclude that g(F f ) = F f , therefore g(x i ) = x i , g(y i ) = y i for all i since g is increasing.
Observe that either g(x) = x for any point y i < x < x i+1 , either g(x) < x for any point y i < x < x i+1 or g(x) > x for any point y i < x < x i+1 . Indeed, otherwise consider the set of fixed points F g ∩ [y i , x i+1 ], and arguing as above in the previous paragraph we get f (F g ∩ [y i , x i+1 ]) = F g ∩ [y i , x i+1 ], again f (x) = x for any end-point of an interval of F g ∩ [y i , x i+1 ], which contradicts the choice of y i , x i+1 , unless F g ⊃ (y i , x i+1 ), in other words g(x) = x for any point y i < x < x i+1 . We allow intervals with ±∞ end-points.

In the case of tropical polynomials f, g without free terms there is at most one end-point of the intervals of fixed points of f, g, which we denote by x 0 , due to the convexity of f, g and taking into the account that the slopes of edges of f, g are greater or equal than 1. Thus, there are at most two intervals

(-∞, x 0 ], [x 0 , ∞) or just one interval (-∞, ∞) when x 0 = ∞. Theorem 4.2 Tropical polynomials f, g commute: f • g = g • f iff either x 0 = ∞ and f = x+c 1 , g = x+c 2 , x ∈ R for some c 1 , c 2 ∈ R or -∞ < x 0 < ∞ and the following is valid.
There exists a tropical increasing algebraic rational function h such that h(x 0 ) = x 0 (see Remark 4.1) and

• either f = h p , g = h q for suitable non-negative integers p, q

• or f = ax + x 0 (1 -a), g = bx + x 0 (1 -b) for suitable integers a, b ≥ 1 holds on the interval [x 0 , ∞). Similarly, • either f = h k , g = h m for suitable non-negative integers k, m • or f = dx + x 0 (1 -d), g = ex + x 0 (1 -e)
for suitable integers d, e ≥ 1 holds on the interval (-∞, x 0 ], Remark 4.3 Note that h is not necessary a tropical polynomial.

Proof. In one direction, namely when either such appropriate h does exist or c 1 , c 2 do exist, obviously f

• g = g • f holds. From now on let f • g = g • f . If f (x) =
x (respectively, g(x) = x) for any x ≥ x 0 one can put h := g, f = h 0 (respectively, h := f, g = h 0 ) on the interval (x 0 , ∞). Thus, from now on we suppose that f (x) > x, g(x) > x for any x > x 0 (cf. Remark 4.1). We construct (increasing) h on the interval (-∞, x 0 ) and separately on the interval (x 0 , ∞) such that h(x 0 ) = x 0 and after that glue them together and obtain a tropical increasing algebraic rational function h required in Theorem 4.2.

Lemma 4.4 Let f, g be tropical increasing algebraic rational functions, f • g = g • f and for some point y i < x < x i+1 it holds f (x) = g(x). Then f coincides with g on the interval (y i , x i+1 ).

Proof of Lemma 4.4. Since neither f nor g has a fixed point in the interval (y i , x i+1 ) one can assume for definiteness that f (y) > y, g(y) > y for any y i < y < x i+1 (see Remark 4.1). For each integer k we have f (f k (x)) = g(f k (x)). The increasing sequence x < f (x) < f 2 (x) < • • • tends to x i+1 taking into the account that F f ∩ (y i x i+1 ) = ∅. Therefore, the right-most edges of f and g on the interval (y i , x i+1 ) coincide. Suppose that f and g do not coincide on the interval (y i , x i+1 ).

Take the left-most point z 0 ∈ (y i , x i+1 ) such that f (y) = g(y) for any z 0 ≤ y < x i+1 . Hence on a sufficiently small interval [z, z 0 ] function f (respectively, g) is linear ax -az 0 + f (z 0 ) (respectively, bx -bz 0 + f (z 0 )) and a = b. Since x i+1 > f (z 0 ) = g(z 0 ) > z 0 and due to the choice of z 0 there exists a linear function cx + d such that on a sufficiently small interval [z, z 0 ] the composition f • g coincides with the linear function cbx -cbz 0 + cf (z 0 ) + d, while the composition g • f on [z, z 0 ] coincides with the linear function cax -caz 0 + cf (z 0 ) + d, which contradicts to the commutativity f • g = g • f and proves Lemma 4.4. 2 Fix an interval (y i , x i+1 ) for the time being and denote by T f the set of tropical roots of f . We considered the case when f (x) = x for any x ∈ (y i , x i+1 ) or when g(x) = x for any x ∈ (y i , x i+1 ) above, so we assume that either f (x) > x for any x ∈ (y i , x i+1 ) or f (x) < x for any x ∈ (y i , x i+1 ), and either g(x) > x for any x ∈ (y i , x i+1 ) or g(x) < x for any x ∈ (y i , x i+1 ) (cf. Remark 4.1). First, we study the case (T f ∪ T g ) ∩ (y i , x i+1 ) = ∅. Since g(y i ) = f (y i ) = y i , g(x i+1 ) = f (x i+1 ) = x i+1 we conclude that one or both end-points of the interval (y i , x x+1 ) equal ±∞.

When both

y i = -∞, x i+1 = ∞, we have f = x + c 1 , g = x + c 2 for some c 1 , c 2 ∈ R.
If y i ∈ R, x i+1 = ∞ (the case y i = -∞, x i+1 ∈ R is analyzed in a similar way) then f (respectively, g) coincides on the interval (y i , ∞) with a linear function ax -ay i + y i (respectively, bx -by i + y i ) for suitable rationals a, b > 0 which establishes Theorem 4.2 in the case (T f ∪ T g ) ∩ (y i , x i+1 ) = ∅.

From now on we again assume f, g to be tropical polynomials and let

(T f ∪ T g ) ∩ (-∞, x 0 ) = ∅ (cf. Remark 4.1). Lemma 4.5 (i) If h 1 , h 2 are tropical algebraic rational functions and x ∈ T h 1 •h 2 then either x ∈ T h 2 or h 2 (x) ∈ T h 1 . For tropical polynomials f, g the converse is true: if either x ∈ T g or g(x) ∈ T f then x ∈ T f •g ; (ii) let f • g = g • f . If x ∈ T g then either f -1 (x) ∈ T g or g • f -1 (x) ∈ T f ; (iii) let f • g = g • f . If x ∈ T f \ T g then g(x) ∈ T f .
Proof of Lemma 4.5. (i). For the converse statement the convexity of f, g is used.

(ii). Denote y := f -1 (x). Due to (i) y ∈ T g•f , hence either y ∈ T g or g(y) ∈ T f again due to (i) and taking into the account that f • g = g • f ;

(iii) Since due to (i) x ∈ T g•f = T f •g we conclude that g(x) ∈ T f again by means of (i). 2

Consider a directed graph G with the nodes being the points from (T f ∪ T g ) ∩ (-∞, x 0 ) and the arrows according to Lemma 4.5 as follows (recall that G is not empty, the case of empty G was studied above). From every node x ∈ T g ∩(-∞, x 0 ) there is an arrow labeled by f -1 to the node f -1 (x), provided that f -1 (x) ∈ T g , and there is an arrow labeled by g•f -1 to the node g

•f -1 (x), provided that g • f -1 (x) ∈ T f (observe that f -1 (x), g • f -1 (x) ∈ (-∞, x 0 )).
In addition, there is an arrow labeled by g from every node x ∈ T f \ T g to the node g(x) ∈ T f (again g(x) ∈ (-∞, x 0 )).

There is a cycle in G (due to Lemma 4.5), let it contain a node x. Denote by t the composition of the labels of the arrows (starting with x) in this cycle. Then t(x) = x and one can represent t = g s • f -r (taking into the account that f • g = g • f ) for some non-negative integers s, r at least one of which being positive. Observe that in fact, s, r > 0 since f (x 1 ) < x 1 , g(x 1 ) < x 1 for any x 1 < x 0 (cf. Remark 4.1).

Hence g s (x) = f r (x). Lemma 4.4 implies that g s coincides with f r on the interval (-∞, x 0 ). Denote n := GCD(s, r), then (g s/n • f -r/n ) n = Id on the interval (-∞, x 0 ). The function u := g s/n • f -r/n is increasing piecewise linear. Therefore, one can partition R into a finite number of intervals (including unbounded ones) such that on each of these intervals [y 0 , y 1 ] it holds u(y 0 ) = y 0 , u(y 1 ) = y 1 , and either u(y) > y for any y 0 < y < y 1 , either u(y) < y for any y 0 < y < y 1 or u(y) = y for any y 0 < y < y 1 (cf. Remark 4.1). Hence u = Id, i. e. g s/n = f r/n on the interval (-∞, x 0 ).

For appropriate positive integers i, j it holds 1 = -i(s/n) + j(r/n). Consider a tropical increasing algebraic rational function h

:= g j • f -i . Then h r/n = g jr/n • f -ir/n = g jr/n • g -is/n = g; h s/n = g js/n • f -is/n = f jr/n • f -is/n = f on the interval (-∞, x 0 ).
In a similar way one produces h on the interval (x 0 , ∞), provided that x 0 < ∞. This completes the proof of Theorem 4.2. 2 Remark 4.6 It would be interesting to give a criterion for commuting tropical increasing algebraic rational functions, and more generally, for tropical non-monotone algebraic rational functions. Remark 4.7 In fact, one can verify a similar to Theorem 4.2 conclusion for any pair of increasing tropical rational functions f, g with commuting composition on an interval [y i , x i+1 ] (cf. Remark 4.1) if any tropical root z ∈ (y i , x i+1 ) of g is also a tropical root of f • g. This condition fails in the next example in which a commuting pair f, g of increasing tropical rational functions does not satisfy the conclusion of Theorem 4.2.

Example 4.8 We exhibit a one-parametric family {T n } n≥2 of increasing tropical rational functions with commuting compositions (defined on the interval [0, ∞), in addition T n (0) = 0, n ≥ 2) and which do not satisfy the conclusion of Theorem 4.2.

Fis a natural number k ≥ 2 and a real w > 0. Then the graph of T n has three edges with the slopes n, kn, n, respectively, and the tropical roots w/n, w (this determines T n uniquely). One can verify that

T n • T m = T m • T n = T mn .
If there exist integers p, q ≥ 0 such that T p n = T q m (cf. Theorem 4.2) then n p = m q . Thus, if for given n, m such p, q do not exist then T n , T m do not satisfy the conclusion of Theorem 4.2.

Tropical polynomial and rational parametrizations

We call a polygonal line L ⊂ R n with k + 1 intervals a sequence of intervals with endpoints v 1 , . . . , v k ∈ Q n such that i-th interval has endpoints v i , v i+1 for 1 ≤ i ≤ k -1, while unbounded 0-th interval (a ray) has v 1 as its right endpoint, and unbounded k-th interval (a ray) has v k as its left endpoint. The vector of slopes of i-th interval, 1 ≤ i ≤ k -1 is defined as (a i,1 , . . . , a i,n ) := v i+1 -v i , similarly one can define a vector of slopes (a 0,1 , . . . , a 0,n ) of 0-th and (a k,1 , . . . , a k,n ) of k-th intervals, respectively (we assume that the latter two vectors of slopes are also rational).

We call a function of a form min -d≤i≤d {a i + ix}, a i ∈ R a tropical Laurent polynomial, thus admitting arbitrary integer (not necessary non-negative) slopes.

We say that tropical rational functions f 1 , . . . , f n in one variable t provide a tropical rational parametrization of L if the map (f 1 , . . . , f n ) : R → L is a bijection and (for definiteness) (f 1 , . . . , f n ) -1 (v i ) < (f 1 , . . . , f n ) -1 (v i+1 ), 1 ≤ i ≤ k -1. In particular, {v 1 , . . . , v k } coincides with the set of all the tropical roots of f 1 , . . . , f n , i. e. the points where one of the functions f 1 , . . . , f n is not smooth. We suppose w.l.o.g. that one can't discard any v i , 1 ≤ i ≤ k while keeping the property of L to be a polygonal line. When f 1 , . . . , f n are tropical polynomials (respectively, tropical Laurent polynomials), we talk about tropical polynomial (respectively, tropical Laurent polynomial) parametrization of L.

In case if L is a subset of a tropical curve one can treat a parametrization of L as a parametrization of the tropical curve (cf. [START_REF] Grigoriev | Tropical Newton-Puiseux polynomials[END_REF]) since a parametrization provides a parametric family of solutions of a system of tropical equations. (ii) a tropical polynomial parametrization iff a i,j ≥ 0, 0 ≤ i ≤ k, 1 ≤ j ≤ n, and a i,j = 0 implies a l,j = 0 for all l ≥ i;

(iii) a tropical Laurent polynomial parametrization iff • a i,j < 0 implies a i+1,j < 0; • a i+1,j > 0 implies a i,j > 0;

• a i,j 0 > 0, a i+1,j 0 > 0, a i,j < 0, a i+1,j < 0 imply a i,j 0 /a i,j ≤ a i+1,j 0 /a i+1,j for all 0 ≤ i ≤ k -1, 1 ≤ j = j 0 ≤ n.

Proof. (i) We have to construct tropical univariate rational functions f 1 , . . . , f n . First we construct piece-wise linear functions g 1 , . . . , g n with rational slopes (in [START_REF] Grigoriev | Tropical Newton-Puiseux polynomials[END_REF] such functions are called tropical Newton-Puiseux rational functions). As a set of tropical roots of g 1 , . . . , g n we take points 1, . . . , k. The vector of the values of g 1 , . . . , g n at point i we put v i , 1 ≤ i ≤ k. Thereby, g 1 , . . . , g n are defined on interval [1, k] ⊂ R. To extend g 1 , . . . , g n to interval (-∞, 1] (respectively, [k, ∞)) use the vector of the slopes of 0-th (respectively, k-th) interval of L.

Remark 5.3 One can construct the required parametrizations in Proposition 5.2 within polynomial complexity following the proofs of (i), (ii), (iii).

It would be interesting to extend parametrizations from 1-dimensional polygonal lines to multidimensional polyhedral complexes.

Proposition 1 . 1

 11 If g, h are tropical monotone rational functions with p, q tropical roots, respectively, then the tropical monotone rational function g • h has at most p+q tropical roots. Moreover, if on an interval [a, b] ⊂ R function h is linear with a slope s, and g is linear with a slope l on the interval [h(a), h(b)] (respectively, [h(b), h(a)]) when h increases (respectively, decreases) then g • h is linear on the interval [a, b] with the slope sl.

Example 5 . 1

 51 Let T ⊂ R 2 be a tropical curve (a tropical line) defined by a tropical polynomial min{x, y, 0}. Then L ⊂ T consisting of two rays {x = 0 ≤ y} ∪ {y = 0 ≤ x} admits a tropical rational parametrization with f 1 := -min{t, 0}, f 2 := -min{-t, 0}. Proposition 5.2 A polygonal line L has (i) always a tropical rational parametrization;

Acknowledgements. The author is grateful to the grant RSF 16-11-10075, to MCCME for inspiring atmosphere and to anonymous referees for useful remarks.

To proceed to tropical rational functions f 1 , . . . , f n (so, piece-wise linear functions with integer slopes), denote by M the least common multiple of all the denominators of the slopes of g 1 , . . . , g n (i. e. the slopes of L). As the set of tropical roots of f 1 , . . . , f n take points 1/M, . . . , k/M . The vector of the values at point i/M we put v i , 1 ≤ i ≤ k. In other words, the corresponding slopes of f 1 , . . . , f n are obtained from the corresponding slopes of g 1 , . . . , g n multiplying by M . Satisfying also the latter condition, one extends f 1 , . . . , f n to intervals (-∞, 1/M ] and [k/M, ∞).

(ii) If f 1 , . . . , f n constitute a tropical polynomial parametrization of L then since the slopes of each f j , 1 ≤ j ≤ n (being a convex function) are nonincreasing non-negative integers we get the conditions stated in (ii).

Conversely, if the latter conditions are fulfilled one can recursively on i choose positive rationals

taking each c i+1 to be the maximal possible among satisfying the latter inequalities. Therefore, one can take c i • a i,j , 1 ≤ j ≤ n as the slopes of (Newton-Puiseux polynomials [START_REF] Grigoriev | Tropical Newton-Puiseux polynomials[END_REF], i. e. convex piecewise linear functions with rational non-negative slopes) g j , 1 ≤ j ≤ n with the tropical roots at points 1, . . . , k. Then as at the end of the proof of (i) one can obtain tropical polynomials f j , 1 ≤ j ≤ n with the non-negative integer slopes M • c i • a i,j , 0 ≤ i ≤ k, 1 ≤ j ≤ n and with the tropical roots at points 1/M, . . . , k/M . Then f 1 , . . . , f n provide a required parametrization of L.

(iii) If there exists a tropical Laurent polynomial parametrization f 1 , . . . , f n of L then the slopes b i,j , 0 ≤ i ≤ k, 1 ≤ j ≤ n of f j , 1 ≤ j ≤ n, respectively, being integers fulfil the conditions b i,j ≥ b i+1,j , 0 ≤ i ≤ k -1, 1 ≤ j ≤ n. On the other hand, there exist positive rationals c 0 , . . . , c k such that b i,j = c i • a i,j , 0 ≤ i ≤ k, 1 ≤ j ≤ n. This entails the conditions from (iii).

Conversely, let the conditions from (iii) be fulfilled. Construct positive rationals

by recursion on i. Assume that c 0 = 1, c 1 , . . . , c i are already constructed. Take the maximal possible c i+1 > 0 such that c i • a i,j ≥ c i+1 • a i+1.j for all 1 ≤ j ≤ n such that a i,j > 0, a i+1,j > 0. Then for suitable j 0 for which a i,j 0 > 0, a i+1,j 0 > 0 it holds c i • a i,j 0 = c i+1 • a i+1,j 0 . For every 1 ≤ j ≤ n for which a i,j < 0, a i+1,j < 0 the condition from (iii) a i,j 0 /a i,j ≤ a i+1,j 0 /a i+1,j implies c i+1 • a i+1,j ≤ c i • a i,j . Thus, as in (i), (ii) one first constructs piece-wise linear functions g j , 1 ≤ j ≤ n with rational non-increasing slopes c i • a i,j , 1 ≤ j ≤ n and with the tropical roots at points 1, . . . , k. Denote by M the common denominator of these slopes and construct tropical Laurent polynomials f 1 , . . . , f n with the slopes obtained from the slopes of g j , 1 ≤ j ≤ n multiplying them by M and with the tropical roots 1/M, . . . , k/M . Then f 1 , . . . , f n provide a required parametrization of L. 2