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

Елизаров Никита Вячеславович
Бесплатно
В избранное
Работа доступна по лицензии 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 (13 отзывов)
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласован... Читать все
    Преподаватель ВУЗа, опыт выполнения студенческих работ на заказ (от рефератов до диссертаций): 20 лет. Образование высшее . Все заказы выполняются в заранее согласованные сроки и при необходимости дорабатываются по рекомендациям научного руководителя (преподавателя). Буду рада плодотворному и взаимовыгодному сотрудничеству!!! К каждой работе подхожу индивидуально! Всегда готова по любому вопросу договориться с заказчиком! Все работы проверяю на антиплагиат.ру по умолчанию, если в заказе не стоит иное и если это заранее не обговорено!!!
    #Кандидатские #Магистерские
    21 Выполненная работа
    Катерина М. кандидат наук, доцент
    4.9 (522 отзыва)
    Кандидат технических наук. Специализируюсь на выполнении работ по метрологии и стандартизации
    Кандидат технических наук. Специализируюсь на выполнении работ по метрологии и стандартизации
    #Кандидатские #Магистерские
    836 Выполненных работ
    Анна С. СФ ПГУ им. М.В. Ломоносова 2004, филологический, преподав...
    4.8 (9 отзывов)
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания... Читать все
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания и проверки (в качестве преподавателя) контрольных и курсовых работ.
    #Кандидатские #Магистерские
    16 Выполненных работ
    Кирилл Ч. ИНЖЭКОН 2010, экономика и управление на предприятии транс...
    4.9 (343 отзыва)
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). С... Читать все
    Работы пишу, начиная с 2000 года. Огромный опыт и знания в области экономики. Закончил школу с золотой медалью. Два высших образования (техническое и экономическое). Сейчас пишу диссертацию на соискание степени кандидата экономических наук.
    #Кандидатские #Магистерские
    692 Выполненных работы
    Анастасия Л. аспирант
    5 (8 отзывов)
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибост... Читать все
    Работаю в сфере метрологического обеспечения. Защищаю кандидатскую диссертацию. Основной профиль: Метрология, стандартизация и сертификация. Оптико-электронное прибостроение, управление качеством
    #Кандидатские #Магистерские
    10 Выполненных работ
    Дарья Б. МГУ 2017, Журналистики, выпускник
    4.9 (35 отзывов)
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных ко... Читать все
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных компаниях, сейчас работаю редактором. Готова помогать вам с учёбой!
    #Кандидатские #Магистерские
    50 Выполненных работ
    Анна Александровна Б. Воронежский государственный университет инженерных технол...
    4.8 (30 отзывов)
    Окончила магистратуру Воронежского государственного университета в 2009 г. В 2014 г. защитила кандидатскую диссертацию. С 2010 г. преподаю в Воронежском государственно... Читать все
    Окончила магистратуру Воронежского государственного университета в 2009 г. В 2014 г. защитила кандидатскую диссертацию. С 2010 г. преподаю в Воронежском государственном университете инженерных технологий.
    #Кандидатские #Магистерские
    66 Выполненных работ
    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Анна В. Инжэкон, студент, кандидат наук
    5 (21 отзыв)
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссе... Читать все
    Выполняю работы по экономическим дисциплинам. Маркетинг, менеджмент, управление персоналом. управление проектами. Есть опыт написания магистерских и кандидатских диссертаций. Работала в маркетинге. Практикующий бизнес-консультант.
    #Кандидатские #Магистерские
    31 Выполненная работа

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

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