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

Математическая последовательность

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

Определение

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

к-ядро

Пусть 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\}.}$

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

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

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

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

Альтернативно, последовательность s ( n ) является k -регулярной, если существуют целое число r и подпоследовательности s ₁ ( n ), ..., s _r ( n ) такие, что для всех 1 ≤ i ≤ r и 0 ≤ a ≤ k  − 1 каждая последовательность si ( kn  +  a ) в k -ядре K _{k (} s ) является R ′-линейной _{комбинацией} подпоследовательностей si ( n ). ^[2]

Официальная серия

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

Автоматно-теоретический

Формальное определение серии k -регулярной последовательности приводит к характеристике автомата, аналогичной матричной машине Шютценбергера. [ ^{4] [5]}

История

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

Примеры

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

Пусть будет -адической оценкой . Последовательность линейки ( OEIS : A007814 ) является -регулярной, а -ядро ${\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 }$ ${\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}}}$

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

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

Последовательность Туэ–Морса t ( n ) ( 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 ( n ) ( 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, также являются 2-регулярными. ^[9]

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

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

${\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}}}$

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

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

Если — целочисленный многочлен , то он является k -регулярным для любого . ${\displaystyle f(x)}$ ${\displaystyle f(n)_{n\geq 0}}$ ${\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]
• Если является k -регулярным, то для всех целых чисел является k -автоматическим . Однако обратное утверждение неверно. ^[17] ${\displaystyle s(n)_{n\geq 0}}$ ${\displaystyle m\geq 1}$ ${\displaystyle (s(n){\bmod {m}})_{n\geq 0}}$
• Для мультипликативно независимых k ,  l  ≥ 2, если последовательность является как k -регулярной, так и l -регулярной, то последовательность удовлетворяет линейной рекуррентности. ^[18] Это обобщение результата Кобэма относительно последовательностей, которые являются как k -автоматическими, так и l -автоматическими. ^[19]
• Член n- го порядка k -регулярной последовательности целых чисел растет не более чем полиномиально по n . ^[20]
• Если — поле и , то последовательность степеней является k -регулярной тогда и только тогда, когда или — корень из единицы. ^[21] ${\displaystyle F}$ ${\displaystyle x\in F}$ ${\displaystyle (x^{n})_{n\geq 0}}$ ${\displaystyle x=0}$ ${\displaystyle x}$

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

Если задана последовательность-кандидат, о которой неизвестно, является ли она k -регулярной, то k -регулярность обычно можно доказать непосредственно из определения, вычислив элементы ядра и доказав, что все элементы формы с достаточно большими и могут быть записаны как линейные комбинации элементов ядра с меньшими показателями степеней вместо . Обычно это вычислительно просто. ${\displaystyle s=s(n)_{n\geq 0}}$ ${\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}$

Пусть обозначает количество ' в двоичном разложении . Пусть обозначает количество ' в двоичном разложении . Можно показать, что последовательность является 2-регулярной. Однако последовательность не является 2-регулярной, с помощью следующего аргумента. Предположим, что является 2-регулярным. Мы утверждаем, что элементы для и 2-ядра линейно независимы над . Функция сюръективна на целые числа, поэтому пусть будет наименьшим целым числом таким, что . В силу 2-регулярности , существуют и константы такие, что для каждого , ${\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)}$ ${\displaystyle g=g(n):=|f(n)|}$ ${\displaystyle (g(n))_{n\geq 0}}$ ${\displaystyle g(2^{k}n)}$ ${\displaystyle n\geq 1}$ ${\displaystyle k\geq 0}$ ${\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}$ ${\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|.}$

Но для правая часть уравнения монотонна, поскольку она имеет вид для некоторых констант , тогда как левая часть не является монотонной, что можно проверить, последовательно подставляя , , и . Следовательно, не является 2-регулярным. ^[22] ${\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}}$

Примечания

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

Ссылки

• Аллуш, Жан-Поль; Шаллит, Джеффри (1992), «Кольцо k -регулярных последовательностей», Теор. вычисл. наук , 98 (2): 163–197, doi : 10.1016/0304-3975(92)90001-v.
• Аллуш, Жан-Поль; Шаллит, Джеффри (2003), «Кольцо k -регулярных последовательностей, II», Теор. вычисл. наук , 307 : 3–29, doi : 10.1016/s0304-3975(03)00090-2.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Автоматические последовательности: теория, приложения, обобщения . Cambridge University Press . ISBN 978-0-521-82332-6. Збл  1086.11015.