Теорема Скулема–Малера–Леха

В аддитивной и алгебраической теории чисел теорема Скулема -Малера-Леха утверждает, что если последовательность чисел удовлетворяет линейному разностному уравнению , то, за ограниченным числом исключений, позиции, в которых последовательность равна нулю, образуют регулярно повторяющийся образец. Этот результат назван в честь Торальфа Скулема (который доказал теорему для последовательностей рациональных чисел ), Курта Малера (который доказал ее для последовательностей алгебраических чисел ) и Кристера Леха (который доказал ее для последовательностей, элементы которых принадлежат любому полю характеристики . 0) ). Его известные доказательства используют $p$ -адический анализ и неконструктивны .

Формулировка теоремы

Позволять $s(n)_{n\geq 0}$ быть последовательностью комплексных чисел, удовлетворяющей $s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\cdots +c_{d}s(n-d)$ для всех $n\geq d$ , где $c_{i}$ являются комплексными числовыми константами (т. е. константно-рекурсивной последовательностью порядка $d$ ). Тогда множество нулей $\{n\mid s(n)=0\}$ равно объединению конечного множества и конечного числа арифметических прогрессий .

Если у нас есть $c_{d}\neq 0$ (исключая такие последовательности, как 1, 0, 0, 0, ...), то множество нулей фактически равно объединению конечного множества и конечного числа полных арифметических прогрессий, где бесконечная арифметическая прогрессия является полной, если существуют целые числа a и b такие, что прогрессия состоит из всех натуральных чисел, равных b по модулю a .

Пример

Рассмотрим последовательность

0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, ...

который чередует нули и числа Фибоначчи . Эту последовательность можно сгенерировать с помощью линейного рекуррентного соотношения $F(i)=F(i-2)+F(i-4)$ (модифицированная форма рекурсии Фибоначчи), начиная с базовых случаев F (1) = F (2) = F (4) = 0 и F (3) = 1. Для этой последовательности F ( i ) = 0 тогда и только тогда, когда я один или четный. Таким образом, позиции, в которых последовательность равна нулю, можно разделить на конечное множество ( одноэлементное множество {1}) и полную арифметическую прогрессию (положительные четные числа ).

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

Связанные результаты

Проблема Скулема — это проблема определения того, имеет ли данная рекуррентная последовательность ноль. Существует алгоритм проверки наличия бесконечного числа нулей: ^{[ 1 ]} и если да, то найти разложение этих нулей на периодические множества, существование которых гарантируется теоремой Скулема–Малера–Леха. Однако неизвестно, существует ли алгоритм определения наличия в рекуррентной последовательности непериодических нулей. ^{[ 2 ]}

Ссылки

^ Берстель, Жан; Миньотт, Морис (1976), «Два разрешимых свойства линейных повторяющихся последовательностей» , Bulletin de la Société Mathématique de France , 104 : 175–184, doi : 10.24033/bsmf.1823
^ Уакнин, Жоэль; Уоррелл, Джеймс (2012), «Проблемы принятия решений для линейных рекуррентных последовательностей», Проблемы достижимости: 6-й международный семинар, RP 2012, Бордо, Франция, 17–19 сентября 2012 г., Труды , Конспекты лекций по информатике, том. 7550, Гейдельберг: Springer-Verlag, стр. 21–28, номер документа : 10.1007/978-3-642-33512-9_3 , MR 3040104.

Сколем, Т. (1933), «Некоторые теоремы о некоторых разложениях в ряд и экспоненциальных соотношениях с применением к диофантовым уравнениям», Осло Вид. Акад. Срифтер , I (6) , цит. по Леху 1953.
Малер, К. (1935), «Арифметическое свойство коэффициентов Тейлора рациональных функций», Акад. Амстердам, Proc. , 38 : 50–60 , цитируется по Lech 1953.
Лех, К. (1953), «Заметка о повторяющихся сериях», Архивы математики , 2 (5): 417–421, Бибкод : 1953ArM.....2..417L , doi : 10.1007/bf02590997 .
Малер, К. (1956), «О коэффициентах Тейлора рациональных функций», Proc. Кембриджская философия. Соц. , 52 (1): 39–48, Bibcode : 1956PCPS...52...39M , doi : 10.1017/s0305004100030966 , S2CID 124295518 .
Малер К. (1957), «Дополнение к статье «О коэффициентах Тейлора рациональных функций» », Proc. Кембриджская философия. Соц. , 53 (2): 544, Bibcode : 1957PCPS...53..544M , doi : 10.1017/s0305004100032552 , S2CID 251098312 .

Внешние ссылки

Вайсштейн, Эрик В. , «Теорема Скулема-Малера-Леха» , MathWorld

[1] Берстель, Жан; Миньотт, Морис (1976), «Два разрешимых свойства линейных повторяющихся последовательностей» , Bulletin de la Société Mathématique de France , 104 : 175–184, doi : 10.24033/bsmf.1823

[2] Уакнин, Жоэль; Уоррелл, Джеймс (2012), «Проблемы принятия решений для линейных рекуррентных последовательностей», Проблемы достижимости: 6-й международный семинар, RP 2012, Бордо, Франция, 17–19 сентября 2012 г., Труды , Конспекты лекций по информатике, том. 7550, Гейдельберг: Springer-Verlag, стр. 21–28, номер документа : 10.1007/978-3-642-33512-9_3 , MR 3040104.

[ 1 ]

[ 2 ]