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

Елизаров Никита Вячеславович
Бесплатно
В избранное
Работа доступна по лицензии 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 (25 отзывов)
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт напис... Читать все
    Выполняю различные работы на заказ с 2014 года. В основном, курсовые проекты, дипломные и выпускные квалификационные работы бакалавриата, специалитета. Имею опыт написания магистерских диссертаций. Направление - связь, телекоммуникации, информационная безопасность, информационные технологии, экономика. Пишу научные статьи уровня ВАК и РИНЦ. Работаю техническим директором интернет-провайдера, имею опыт работы ведущим сотрудником отдела информационной безопасности филиала одного из крупнейших банков. Образование - высшее профессиональное (в 2006 году окончил военную Академию связи в г. Санкт-Петербурге), послевузовское профессиональное (в 2018 году окончил аспирантуру Уральского федерального университета). Защитил диссертацию на соискание степени "кандидат технических наук" в 2020 году. В качестве хобби преподаю. Дисциплины - сети ЭВМ и телекоммуникации, информационная безопасность объектов критической информационной инфраструктуры.
    #Кандидатские #Магистерские
    33 Выполненных работы
    Екатерина Д.
    4.8 (37 отзывов)
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два об... Читать все
    Более 5 лет помогаю в написании работ от простых учебных заданий и магистерских диссертаций до реальных бизнес-планов и проектов для открытия своего дела. Имею два образования: экономист-менеджер и маркетолог. Буду рада помочь и Вам.
    #Кандидатские #Магистерские
    55 Выполненных работ
    Глеб С. преподаватель, кандидат наук, доцент
    5 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ
    Виктор В. Смоленская государственная медицинская академия 1997, Леч...
    4.7 (46 отзывов)
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выв... Читать все
    Имеют опыт грамотного написания диссертационных работ по медицине, а также отдельных ее частей (литературный обзор, цели и задачи исследования, материалы и методы, выводы).Пишу статьи в РИНЦ, ВАК.Оформление патентов от идеи до регистрации.
    #Кандидатские #Магистерские
    100 Выполненных работ
    Кормчий В.
    4.3 (248 отзывов)
    Специализация: диссертации; дипломные и курсовые работы; научные статьи.
    Специализация: диссертации; дипломные и курсовые работы; научные статьи.
    #Кандидатские #Магистерские
    335 Выполненных работ
    Ксения М. Курганский Государственный Университет 2009, Юридический...
    4.8 (105 отзывов)
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитыв... Читать все
    Работаю только по книгам, учебникам, статьям и диссертациям. Никогда не использую технические способы поднятия оригинальности. Только авторские работы. Стараюсь учитывать все требования и пожелания.
    #Кандидатские #Магистерские
    213 Выполненных работ
    Яна К. ТюмГУ 2004, ГМУ, выпускник
    5 (8 отзывов)
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соот... Читать все
    Помощь в написании магистерских диссертаций, курсовых, контрольных работ, рефератов, статей, повышение уникальности текста(ручной рерайт), качественно и в срок, в соответствии с Вашими требованиями.
    #Кандидатские #Магистерские
    12 Выполненных работ
    Дарья Б. МГУ 2017, Журналистики, выпускник
    4.9 (35 отзывов)
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных ко... Читать все
    Привет! Меня зовут Даша, я окончила журфак МГУ с красным дипломом, защитила магистерскую диссертацию на филфаке. Работала журналистом, PR-менеджером в международных компаниях, сейчас работаю редактором. Готова помогать вам с учёбой!
    #Кандидатские #Магистерские
    50 Выполненных работ
    Логик Ф. кандидат наук, доцент
    4.9 (826 отзывов)
    Я - кандидат философских наук, доцент кафедры философии СГЮА. Занимаюсь написанием различного рода работ (научные статьи, курсовые, дипломные работы, магистерские дисс... Читать все
    Я - кандидат философских наук, доцент кафедры философии СГЮА. Занимаюсь написанием различного рода работ (научные статьи, курсовые, дипломные работы, магистерские диссертации, рефераты, контрольные) уже много лет. Качество работ гарантирую.
    #Кандидатские #Магистерские
    1486 Выполненных работ

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

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