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

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

Определение

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

k -ядро

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

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

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

В частном случае, когда $R'=R=\mathbb {Q}$, последовательность $s(n)_{n\geq 0}$ является $k$-обычный, если $K_{k}(s)$ содержится в конечномерном векторном пространстве над $\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 ′ -линейная комбинация $\sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})$, где c _ij — целое число, f _ij ≤ E и 0 ≤ b _ij ≤ k ^{ж _ij}  − 1.

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

серия

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

Теория автоматов

Формальное определение k -регулярной последовательности приводит к автоматной характеризации, аналогичной . матричной машине Шютценбергера

История

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

Примеры

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

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

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

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

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

которое наряду с начальными условиями $s(0)=0$ и $s(1)=1$, однозначно определяют последовательность.

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

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

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

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

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

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

${\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-регулярны.

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

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

${\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-регулярную последовательность.

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

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

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

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

Свойства

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

• Любая k -автоматическая последовательность является k -регулярной.
• Любая k -синхронизированная последовательность является k -регулярной.
• k - регулярная последовательность принимает конечное число значений тогда и только тогда, когда она k -автоматична. Это непосредственное следствие того, что класс k -регулярных последовательностей является обобщением класса k -автоматических последовательностей.
• Класс k -регулярных последовательностей замкнут относительно почленного сложения, почленного умножения и свертки . Класс k -регулярных последовательностей также замкнут при масштабировании каждого члена последовательности на целое число λ. В частности, множество k -регулярных степенных рядов образует кольцо.
• Если $s(n)_{n\geq 0}$ является k -регулярным, то для всех целых чисел $m\geq 1$, $(s(n){\bmod {m}})_{n\geq 0}$ является k -автоматическим. Однако обратное не верно.
• Для мультипликативно независимых k , l ≥ 2, если последовательность является одновременно k -регулярной и l -регулярной, то последовательность удовлетворяет линейной рекуррентности. Это обобщение результата Кобэма относительно последовательностей, которые являются одновременно k -автоматическими и l -автоматическими.
• n -й член k -регулярной последовательности целых чисел растет не более чем полиномиально по n .
• Если $F$ это поле и $x\in F$, то последовательность степеней $(x^{n})_{n\geq 0}$ является k -регулярным тогда и только тогда, когда $x=0$ или $x$ является корнем единства.

и k -

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

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