Энтропия тропических рекуррентных последовательностей

We say that a sequence = { ∈ R}∞ ∈Z is a tropical recurrent sequence that satisfies vector := ( 0,…, ) ∈ (R∪{∞}) +1 where 0, < ∞ if for all ∈ Z { + 0 + } is attained at least twice for at least two different indices 0 1( ) < 2( ) . Also we say that a vector ( 0,..., ) satisfies vector if this condition is true for 0 − . If we set ,( + ) = and zero otherwise then any tropical recurrent sequence { }∞ ∈Z is a solution of the infinite tropical linear system { + }. Linear tropical systems is one of the most important and well-known topics of tropical algebra. There are a lot of works about their solvability and about different algorithms that solves them ([1], [2], [3], [4]). Moreover, in the [5] it was shown that the solution of a system of the arbitrary tropical polynomials reduces to the solution of an infinite tropical linear Macalay system which is in fact, a tropical recurrent sequence. Therefore, the study of infinite linear tropical systems is of particular interest. Now we introduce a crucial feature of vector . For 0 ∈ Z denote by the set of vectors satisfying in R and by the of . is polyhedral complex ([6]). When + = denote by : R → R the projection onto the first coordinates and by : R → R the projection onto the last coordinates. Note that ( ) ⊂ and ( ) ⊂ thus we have + + . Therefore, due to Fekete’s subadditive lemma ([7]) there exists limit: ( ):= lim . →∞ One can extend ([8]) the concept of the tropical entropy to tropical entropy ( ) of the arbitrary tropical ideal . Informally speaking, the tropical entropy is the tropical analogue of the coefficient at the −th power of Hilbert’s polynomial of the ideal, where is the number of variables. In the classical case when = 1 the Hilbert’s polynomial of ideal which is generated by polynomial ( ) = ∑︀ · (the polynomial corresponding to a classical =0 3 linear recurrent sequence ∑︀ · = 0) equals to a constant . Thus its coefficient =0 at the −th power equals to 0. However, in the tropical case ( ) can be bigger than zero. A convex hull of the vertical rays {( , ),0 } we will call a Newton polygon ( ). We will call vector regular if := { | < ∞} is an arithmetic progression and for every ∈ ( , ) is a vertex in the ( ). In the [9] it was shown that ( ) = 0 iff is regular. For non-regular vector in the [10] it was shown that 16 ( ) 1 − 1 . However, these estimates are not sharp as we will show in our results. We also call function ( ) from N to N quasi-linear if it is of the form · + ( ), where ( ) is a periodic function with an integer period. Now we introduce our results. In the 1 section of this paper we prove sharp estimates on ( ) for non-regular vectors . • In the theorem 1.1 we prove that for non-regular vector tropical entropy ( ) 14. Together with the [10, Example 5.5] we obtain that this bound is sharp. This theorem is the answer to the hypothesis that was formulated in the [10, Remark 5.6]. • In the theorem 1.3 we prove that tropical entropy ( ) 1 − 2 . Together +1 with the [10, Example 5.2] we obtain that this bound is sharp. In the 2 section of this paper we study the case when is tropical boolean vector (when all are either 0 or ∞) • In the theorem 2.7 we prove that tropical entropy can be found using zero- infinity graph (finite directed graph corresponding to the tropical boolean vec- tor ). 4 • In the theorem 2.10 and corollary 2.11 we prove that as a function of is quasi-linear starting from some ∈ N. Thus can be considered as a tropical analogue of the Hilbert’s polynomial. This theorem is the answer to the hypothesis that was formulated in the [10, Remark 5.9(ii)] in the case when is tropical boolean vector. In the conclusion we repeat our results and formulate open problems.