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

Елизаров Никита Вячеславович
Бесплатно
В избранное
Работа доступна по лицензии 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 Выполненная работа
    Дмитрий Л. КНЭУ 2015, Экономики и управления, выпускник
    4.8 (2878 отзывов)
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    Занимаю 1 место в рейтинге исполнителей по категориям работ "Научные статьи" и "Эссе". Пишу дипломные работы и магистерские диссертации.
    #Кандидатские #Магистерские
    5125 Выполненных работ
    Ольга Б. кандидат наук, доцент
    4.8 (373 отзыва)
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских... Читать все
    Работаю на сайте четвертый год. Действующий преподаватель вуза. Основные направления: микробиология, биология и медицина. Написано несколько кандидатских, магистерских диссертаций, дипломных и курсовых работ. Слежу за новинками в медицине.
    #Кандидатские #Магистерские
    566 Выполненных работ
    Екатерина Б. кандидат наук, доцент
    5 (174 отзыва)
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподав... Читать все
    После окончания института работала экономистом в системе государственных финансов. С 1988 года на преподавательской работе. Защитила кандидатскую диссертацию. Преподавала учебные дисциплины: Бюджетная система Украины, Статистика.
    #Кандидатские #Магистерские
    300 Выполненных работ
    Татьяна П. МГУ им. Ломоносова 1930, выпускник
    5 (9 отзывов)
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по и... Читать все
    Журналист. Младший научный сотрудник в институте РАН. Репетитор по английскому языку (стаж 6 лет). Также знаю французский. Сейчас занимаюсь написанием диссертации по истории. Увлекаюсь литературой и темой космоса.
    #Кандидатские #Магистерские
    11 Выполненных работ
    Александр О. Спб государственный университет 1972, мат - мех, преподав...
    4.9 (66 отзывов)
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальн... Читать все
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальных уравнений. Умею быстро и четко выполнять сложные вычислительные работ
    #Кандидатские #Магистерские
    117 Выполненных работ
    Андрей С. Тверской государственный университет 2011, математический...
    4.7 (82 отзыва)
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на... Читать все
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на продолжение диссертационной работы... Всегда готов помочь! ;)
    #Кандидатские #Магистерские
    164 Выполненных работы
    Виктор В. Смоленская государственная медицинская академия 1997, Леч...
    4.7 (46 отзывов)
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выв... Читать все
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выводы).Пишу статьи в РИНЦ, ВАК.Оформление патентов от идеи до регистрации.
    #Кандидатские #Магистерские
    100 Выполненных работ
    Татьяна П.
    4.2 (6 отзывов)
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки ... Читать все
    Помогаю студентам с решением задач по ТОЭ и физике на протяжении 9 лет. Пишу диссертацию на соискание степени кандидата технических наук, имею опыт годовой стажировки в одном из крупнейших университетов Германии.
    #Кандидатские #Магистерские
    9 Выполненных работ

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

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