Теорема Сколема – Малера – Леха. - Skolem–Mahler–Lech theorem

В аддитивная теория чисел, то Теорема Сколема – Малера – Леха. утверждает, что если последовательность чисел генерируется линейное рекуррентное соотношение, то за конечным числом исключений позиции, в которых последовательность равна нулю, образуют регулярно повторяющийся узор. Точнее, этот набор позиций можно разложить на объединение конечный набор и конечное число полных арифметические прогрессии. Здесь бесконечная арифметическая прогрессия является полной, если существуют целые числа а и б такая, что прогрессия состоит из всех положительных целых чисел, равных б по модулюа.

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

Пример

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

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

который чередуется между нулями и Числа Фибоначчи Эта последовательность может быть порождена линейным рекуррентным соотношением

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

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

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

В Сколемская проблема - это проблема определения, имеет ли данная рекуррентная последовательность ноль. Существует алгоритм, проверяющий, существует ли бесконечно много нулей, и если да, то найти разложение этих нулей на периодические множества, существование которых гарантировано теоремой Сколема – Малера – Леха. Однако неизвестно, существует ли алгоритм, чтобы определить, имеет ли рекуррентная последовательность какие-либо непериодические нули (Уакнин и Уоррелл 2012 ).

Рекомендации

  • Сколем, чт. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. акад. Скрифтер, я (6), цитируется по Lech 1953.
  • Малер К. (1935), «Eine arithmetisehe Eigenschaft der Taylor-koeffizienten ralionaler Funktionen», Акад. Wetensch. Амстердам, Proc., 38: 50–60, цитируется по Lech 1953.
  • Лех, К. (1953), «Заметка о повторяющихся сериях», Arkiv för Matematik, 2: 417–421, Дои:10.1007 / bf02590997.
  • Малер К. (1956), "О коэффициентах Тейлора рациональных функций", Proc. Cambridge Philos. Soc., 52: 39–48, Дои:10,1017 / с0305004100030966.
  • Малер К. (1957), "Дополнение к статье" О коэффициентах Тейлора рациональных функций."", Proc. Cambridge Philos. Soc., 53: 544, Дои:10.1017 / с0305004100032552.
  • Уакнин, Джоэль; Уоррелл, Джеймс (2012), "Проблемы решения для линейных рекуррентных последовательностей", Проблемы достижимости: 6-й международный семинар, RP 2012, Бордо, Франция, 17-19 сентября 2012 г., Материалы, Конспект лекций по информатике, 7550, Heidelberg: Springer-Verlag, стр. 21–28, Дои:10.1007/978-3-642-33512-9_3, МИСТЕР  3040104.

внешняя ссылка