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

Елизаров Никита Вячеславович
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Рассматривается энтропия тропических рекуррентных последовательностей. В первой части работы мы приводим и доказываем точные оценки для энтропии. Во второй части работы рассматривается энтропия тропических булевых векторов. В этом случае вводится тропический булевский граф. Мы доказываем, что нахождение энтропии в этом случае сводится к нахождению оптимального цикла в тропическом булевском графе. Наконец, для тропических булевых векторов мы доказываем, что размерность пространства рекуррентных последовательностей длины s как функция от s является квазилинейной функцией.

Introduction 3
1 Sharp bounds on the positive tropical entropy 6
2 Tropical boolean vectors entropy calculus 20
Conclusion Bibliography
31 32

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.

In the theorems 1.1 and 1.3 it was proved that for non-regular vector it is true
that:
1 ( ) 1− 2 , 4 +1
and these estimates are sharp.
In the theorem 2.7 it was proved that in the case when is tropical boolean vector ( ) could be explicitly found using finite directed graph which corresponds to vector .
In the theorem 2.10 and corollary 2.11 it was proved that is a quasi-linear function of starting from some ∈ N.
Open problems:
1. Construction of the zero-infinity graph for arbitrary vector ( 0, . . . , ), 0 = 0 and = 0.
2. Algorithmforfinding ( )inthecasewhen isanarbitraryvector( 0,…, ), 0 =0and =0.
3. The hypothesis that is a quasi-linear function of for arbitrary vector ( 0,…, ), 0 = 0 and = 0.

[1] Akian M., Gaubert S., Guterman A. Tropical polyhedra are equivalent to mean payoff games //International Journal of Algebra and Computation. – 2012. – Vol. 22. – No. 01. – P. 1250001.
[2] Butkoviˇc P. Max-linear systems: theory and algorithms. – Springer Science & Business Media, 2010.
[3] Grigoriev D. Complexity of solving tropical linear systems //Computational com- plexity. – 2013. – Vol. 22. – No. 1. – P. 71-88.
[4] Grigoriev D., Podolskii V. V. Complexity of tropical and min-plus linear preva- rieties //computational complexity. – 2015. – Vol. 24. – No. 1. – P. 31-64.
[5] Grigoriev D., Podolskii V. V. Tropical effective primary and dual Nullstellens ̈atze //Discrete & Computational Geometry. – 2018. – Vol. 59. – No. 3. – P. 507-552.
[6] Maclagan D., Sturmfels B. Introduction to tropical geometry. – American Math- ematical Soc., 2015. – Vol. 161.
[7] Schechter E. Handbook of Analysis and its Foundations. – Academic Press, 1996.
[8] Grigoriev D. Entropy of radical ideal of a tropical prevariety, arXiv:2007.06195, 2020.
[9] Grigoriev D. On a tropical dual Nullstellensatz //Advances in Applied Mathe- matics. – 2012. – Vol. 48. – No. 2. – P. 457-464.
[10] Grigoriev D. Tropical recurrent sequences //Advances in Applied Mathematics. – 2020. – Vol. 116. – P. 102012.

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

    Нажимая на кнопку, я соглашаюсь на обработку персональных данных и с правилами пользования Платформой

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Татьяна П.
    4.2 (6 отзывов)
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки ... Читать все
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки в одном из крупнейших университетов Германии.
    #Кандидатские #Магистерские
    9 Выполненных работ
    Александра С.
    5 (91 отзыв)
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повы... Читать все
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повышении уникальности текста и оформлении библиографических ссылок по ГОСТу.
    #Кандидатские #Магистерские
    132 Выполненных работы
    Дмитрий К. преподаватель, кандидат наук
    5 (1241 отзыв)
    Окончил КазГУ с красным дипломом в 1985 г., после окончания работал в Институте Ядерной Физики, защитил кандидатскую диссертацию в 1991 г. Работы для студентов выполня... Читать все
    Окончил КазГУ с красным дипломом в 1985 г., после окончания работал в Институте Ядерной Физики, защитил кандидатскую диссертацию в 1991 г. Работы для студентов выполняю уже 30 лет.
    #Кандидатские #Магистерские
    2271 Выполненная работа
    Сергей Е. МГУ 2012, физический, выпускник, кандидат наук
    4.9 (5 отзывов)
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым напра... Читать все
    Имеется большой опыт написания творческих работ на различных порталах от эссе до кандидатских диссертаций, решения задач и выполнения лабораторных работ по любым направлениям физики, математики, химии и других естественных наук.
    #Кандидатские #Магистерские
    5 Выполненных работ
    Дарья С. Томский государственный университет 2010, Юридический, в...
    4.8 (13 отзывов)
    Практикую гражданское, семейное право. Преподаю указанные дисциплины в ВУЗе. Выполняла работы на заказ в течение двух лет. Обучалась в аспирантуре, подготовила диссерт... Читать все
    Практикую гражданское, семейное право. Преподаю указанные дисциплины в ВУЗе. Выполняла работы на заказ в течение двух лет. Обучалась в аспирантуре, подготовила диссертационное исследование, которое сейчас находится на рассмотрении в совете.
    #Кандидатские #Магистерские
    18 Выполненных работ
    Дарья П. кандидат наук, доцент
    4.9 (20 отзывов)
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных... Читать все
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных исследований, связанных с журналистикой, филологией и литературой
    #Кандидатские #Магистерские
    33 Выполненных работы
    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Екатерина Б. кандидат наук, доцент
    5 (174 отзыва)
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподав... Читать все
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподавала учебные дисциплины: Бюджетная система Украины, Статистика.
    #Кандидатские #Магистерские
    300 Выполненных работ
    Оксана М. Восточноукраинский национальный университет, студент 4 - ...
    4.9 (37 отзывов)
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политоло... Читать все
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политологии.
    #Кандидатские #Магистерские
    68 Выполненных работ

    Другие учебные работы по предмету

    Алгоритмы для динамических диаграмм Вороного
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    О локальных свойствах решений задач гидродинамики
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Структуры комодулей на кольцах Чжоу флаговых многообразий
    📅 2021год
    🏢 Санкт-Петербургский государственный университет
    Полнота биортогональных систем для нескольких интервалов
    📅 2021год
    🏢 Санкт-Петербургский государственный университет