K-регулярная последовательность - K-regular sequence

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

Определение

Существует несколько характеристик k-регулярные последовательности, все из которых эквивалентны. Ниже приведены некоторые общие характеристики. Для каждого берем р' быть коммутативный Кольцо Нётериана и мы берем р быть звенеть содержащий р′.

k-ядро

Позволять k ≥ 2. k-ядро последовательности ${\displaystyle s(n)_{n\geq 0}}$ это множество подпоследовательностей

${\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.}$

Последовательность ${\displaystyle s(n)_{n\geq 0}}$ является (р′, k) -регулярный (часто сокращается до "k-регулярный "), если ${\displaystyle R'}$-модуль, созданный K_k(s) это конечно порожденный р′-модуль.^[1]

В частном случае, когда ${\displaystyle R'=R=\mathbb {Q} }$, последовательность ${\displaystyle s(n)_{n\geq 0}}$ является ${\displaystyle k}$-регулярно, если ${\displaystyle K_{k}(s)}$ содержится в конечномерном векторном пространстве над ${\displaystyle \mathbb {Q} }$.

Линейные комбинации

Последовательность s(п) является k-регулярно, если существует целое число E такое, что для всех е_j > E и 0 ≤ р_j ≤ k^е_j - 1, каждая подпоследовательность s формы s(k^е_jп + р_j) выражается как р′-линейная комбинация ${\displaystyle \sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})}$, куда c_ij целое число, ж_ij ≤ E, и 0 ≤ б_ij ≤ k^ж_ij − 1.^[2]

В качестве альтернативы последовательность s(п) является k-регулярно, если существует целое число р и подпоследовательности s₁(п), ..., s_р(п) такое, что для всех 1 ≤ я ≤ р и 0 ≤ а ≤ k - 1, каждая последовательность s_я(кн + а) в k-ядро K_k(s) является р′ -Линейная комбинация подпоследовательностей s_я(п).^[2]

Формальная серия

Позволять Икс₀, ..., Икс_k − 1 быть набором k некоммутирующие переменные, и пусть τ - отображение, отправляющее некоторое натуральное число п к строке Икс_а0 ... Икс_ае − 1, где база-k представление Икс это строка а_е − 1...а₀. Тогда последовательность s(п) является k-регулярно тогда и только тогда, когда формальная серия ${\displaystyle \sum _{n\geq 0}s(n)\tau (n)}$ является ${\displaystyle \mathbb {Z} }$-рациональный.^[3]

Теоретико-автоматные

Определение формального ряда k-регулярная последовательность приводит к характеристике автомата, подобной Schützenberger Матричная машина.^[4][5]

История

Понятие k-регулярные последовательности впервые были исследованы в паре работ Аллуша и Шаллита.^[6] До этого Берстель и Ройтенауэр изучали теорию рациональный ряд, который тесно связан с k-регулярные последовательности.^[7]

Примеры

Последовательность линейки

Позволять ${\displaystyle s(n)=\nu _{2}(n+1)}$ быть ${\displaystyle 2}$-адическая оценка из ${\displaystyle n+1}$. Последовательность линейки ${\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }$ (OEIS: A007814) является ${\displaystyle 2}$-регулярный, а ${\displaystyle 2}$-ядро

${\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}$

содержится в двумерном векторном пространстве, порожденном ${\displaystyle s(n)_{n\geq 0}}$ и постоянная последовательность ${\displaystyle 1,1,1,\dots }$. Эти базисные элементы приводят к рекуррентным соотношениям

${\displaystyle {\begin{aligned}s(2n)&=0,\\s(4n+1)&=s(2n+1)-s(n),\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}}$

которое вместе с начальными условиями ${\displaystyle s(0)=0}$ и ${\displaystyle s(1)=1}$, однозначно определяют последовательность.^[8]

Последовательность Туэ – Морса

В Последовательность Туэ – Морса т(п) (OEIS: A010060) это фиксированная точка морфизма 0 → 01, 1 → 10. Известно, что последовательность Туэ – Морса 2-автоматна. Таким образом, он также 2-регулярен, и его 2-ядро

${\displaystyle \{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}$

состоит из подпоследовательностей ${\displaystyle t(n)_{n\geq 0}}$ и ${\displaystyle t(2n+1)_{n\geq 0}}$.

Числа Кантора

Последовательность Числа Кантора c(п) (OEIS: A005823) состоит из чисел, тройной расширения не содержат единиц. Несложно показать, что

${\displaystyle {\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}}$

и, следовательно, последовательность чисел Кантора 2-регулярна. Аналогичным образом Последовательность Стэнли

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (последовательность A005836 в OEIS )

чисел, тернарные разложения которых не содержат двоек, также 2-регулярны.^[9]

Сортировка чисел

Несколько интересное приложение понятия k-регулярность к более широкому изучению алгоритмов обнаруживается при анализе Сортировка слиянием алгоритм. Учитывая список п значений, количество сравнений, сделанных алгоритмом сортировки слиянием, является сортировка чисел, управляемый рекуррентным соотношением

${\displaystyle {\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}}$

В результате последовательность, определяемая рекуррентным соотношением для сортировки слиянием, Т(п), составляет 2-регулярную последовательность.^[10]

Другие последовательности

Если ${\displaystyle f(x)}$ является целочисленный многочлен, тогда ${\displaystyle f(n)_{n\geq 0}}$ является k-регулярно для каждого ${\displaystyle k\geq 2}$.

В Глейшер-Гулд последовательность 2-регулярная. Последовательность Штерна – Броко 2-регулярна.

Аллуш и Шаллит приводят ряд дополнительных примеров k-регулярные последовательности в своих работах.^[6]

Характеристики

k-регулярные последовательности обладают рядом интересных свойств.

• Каждый k-автоматическая последовательность является k-обычный.^[11]
• Каждый k-синхронизированная последовательность является k-обычный.
• А k-регулярная последовательность принимает конечное число значений тогда и только тогда, когда она k-автоматический.^[12] Это непосредственное следствие класса k-регулярные последовательности, являющиеся обобщением класса k-автоматические последовательности.
• Класс k-регулярные последовательности замкнуты относительно почленного сложения, почленного умножения и свертка. Класс k-регулярные последовательности также замыкаются при масштабировании каждого члена последовательности на целое число λ.^{[12][13][14][15]} В частности, набор k-регулярный степенной ряд образует кольцо.^[16]
• Если ${\displaystyle s(n)_{n\geq 0}}$ является k-регулярно, то для всех целых чисел ${\displaystyle m\geq 1}$, ${\displaystyle (s(n){\bmod {m}})_{n\geq 0}}$ является k-автоматический. Однако обратное неверно.^[17]
• Для мультипликативно независимых k, л ≥ 2, если последовательность k-регулярные и л-регулярна, то последовательность удовлетворяет линейной рекуррентности.^[18] Это обобщение результата Кобэма относительно последовательностей, которые являются k-автоматический и л-автоматический.^[19]
• В п-й срок k-регулярная последовательность целых чисел растет не более чем полиномиально за п.^[20]
• Если ${\displaystyle F}$ это поле и ${\displaystyle x\in F}$, то последовательность степеней ${\displaystyle (x^{n})_{n\geq 0}}$ является k-регулярно тогда и только тогда, когда ${\displaystyle x=0}$ или же ${\displaystyle x}$ является корнем единства.^[21]

Доказательство и опровержение k-регулярность

Учитывая последовательность кандидатов ${\displaystyle s=s(n)_{n\geq 0}}$ это не известно k-обычный, k-регулярность обычно может быть доказана непосредственно из определения путем вычисления элементов ядра ${\displaystyle s}$ и доказывая, что все элементы формы ${\displaystyle (s(k^{r}n+e))_{n\geq 0}}$ с ${\displaystyle r}$ достаточно большой и ${\displaystyle 0\leq e<2^{r}}$ можно записать в виде линейных комбинаций элементов ядра с меньшими показателями вместо ${\displaystyle r}$. Обычно это просто с вычислительной точки зрения.

С другой стороны, опровергая k-регулярность последовательности кандидатов ${\displaystyle s}$ обычно требуется один для создания ${\displaystyle \mathbb {Z} }$-линейно независимое подмножество в ядре ${\displaystyle s}$, что обычно бывает сложнее. Вот один из примеров такого доказательства.

Позволять ${\displaystyle e_{0}(n)}$ обозначить количество ${\displaystyle 0}$в двоичном разложении ${\displaystyle n}$. Позволять ${\displaystyle e_{1}(n)}$ обозначить количество ${\displaystyle 1}$в двоичном разложении ${\displaystyle n}$. Последовательность ${\displaystyle f(n):=e_{0}(n)-e_{1}(n)}$ может быть 2-регулярным. Последовательность ${\displaystyle g=g(n):=|f(n)|}$ однако не является 2-регулярным по следующему аргументу. Предполагать ${\displaystyle (g(n))_{n\geq 0}}$ 2-регулярный. Мы утверждаем, что элементы ${\displaystyle g(2^{k}n)}$ за ${\displaystyle n\geq 1}$ и ${\displaystyle k\geq 0}$ 2-ядра ${\displaystyle g}$ линейно независимы над ${\displaystyle \mathbb {Z} }$. Функция ${\displaystyle n\mapsto e_{0}(n)-e_{1}(n)}$ сюръективен на целые числа, поэтому пусть ${\displaystyle x_{m}}$ - наименьшее целое число такое, что ${\displaystyle e_{0}(x_{m})-e_{1}(x_{m})=m}$. По 2-регулярности ${\displaystyle (g(n))_{n\geq 0}}$, существуют ${\displaystyle b\geq 0}$ и константы ${\displaystyle c_{i}}$ так что для каждого ${\displaystyle n\geq 0}$,

${\displaystyle \sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.}$

Позволять ${\displaystyle a}$ быть наименьшим значением, для которого ${\displaystyle c_{a}\neq 0}$. Тогда для каждого ${\displaystyle n\geq 0}$,

${\displaystyle g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).}$

Оценивая это выражение в ${\displaystyle n=x_{m}}$, куда ${\displaystyle m=0,-1,1,2,-2}$ и так далее, в левой части получим

${\displaystyle g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,}$

а с правой стороны

${\displaystyle \sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

Отсюда следует, что для любого целого числа ${\displaystyle m}$,

${\displaystyle |m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

Но для ${\displaystyle m\geq -a-1}$, правая часть уравнения монотонна, поскольку имеет вид ${\displaystyle Am+B}$ для некоторых констант ${\displaystyle A,B}$, а левая - нет, что можно проверить, последовательно подключив ${\displaystyle m=-a-1}$, ${\displaystyle m=-a}$, и ${\displaystyle m=-a+1}$. Следовательно, ${\displaystyle (g(n))_{n\geq 0}}$ не является 2-регулярным.^[22]

Примечания

1. Аллуш и Шаллит (1992), определение 2.1.
2. Аллуш и Шаллит (1992), теорема 2.2.
3. Аллуш и Шаллит (1992), теорема 4.3.
4. Аллуш и Шаллит (1992), теорема 4.4.
5. Шютценбергер, М.-П. (1961), «Об определении семейства автоматов», Информация и контроль, 4 (2–3): 245–270, Дои:10.1016 / S0019-9958 (61) 80020-X.
6. Аллуш и Шаллит (1992, 2003).
7. Берстель, Жан; Ройтенауэр, Кристоф (1988). Рациональные серии и их языки. Монографии EATCS по теоретической информатике. 12. Springer-Verlag. ISBN  978-3-642-73237-9.
8. Allouche & Shallit (1992), пример 8.
9. Allouche & Shallit (1992), примеры 3 и 26.
10. Allouche & Shallit (1992), пример 28.
11. Аллуш и Шаллит (1992), теорема 2.3.
12. Allouche & Shallit (2003) стр. 441.
13. Аллуш и Шаллит (1992), теорема 2.5.
14. Аллуш и Шаллит (1992), теорема 3.1.
15. Allouche & Shallit (2003) стр. 445.
16. Аллуш и Шаллит (2003) стр. 446.
17. Аллуш и Шаллит (2003) стр. 441.
18. Белл, Дж. (2006). «Обобщение теоремы Кобэма для регулярных последовательностей». Séminaire Lotharingien de Combinatoire. 54A.
19. Кобхэм, А. (1969). «О базисной зависимости множеств чисел, распознаваемых конечными автоматами». Математика. Теория систем. 3 (2): 186–192. Дои:10.1007 / BF01746527.
20. Allouche & Shallit (1992) Теорема 2.10.
21. Аллуш и Шаллит (2003) стр. 444.
22. Аллуш и Шаллит (1993) стр. 168–169.

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

• Аллуш, Жан-Поль; Шаллит, Джеффри (1992), «Кольцо k-регулярные последовательности », Теорет. Comput. Sci., 98 (2): 163–197, Дои:10.1016 / 0304-3975 (92) 90001-в.
• Аллуш, Жан-Поль; Шаллит, Джеффри (2003), «Кольцо k-регулярные последовательности, II ", Теорет. Comput. Sci., 307: 3–29, Дои:10.1016 / s0304-3975 (03) 00090-2.
• Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. ISBN  978-0-521-82332-6. Zbl  1086.11015.