М. И. Корнев, “$n$-значные косетные группы и динамика”, Матем. заметки, 116:1 (2024), 77–90; Math. Notes, 116:1 (2024), 66

Loading [MathJax]/jax/output/CommonHTML/jax.js

Математические заметки

RUS ENG

ЖУРНАЛЫ ПЕРСОНАЛИИ ОРГАНИЗАЦИИ КОНФЕРЕНЦИИ СЕМИНАРЫ ВИДЕОТЕКА ПАКЕТ AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	Общая информация
	Последний выпуск
	Скоро в журнале
	Архив
	Импакт-фактор
	Правила для авторов
	Лицензионный договор
	Загрузить рукопись

	Поиск публикаций
	Поиск ссылок

	RSS
	Последний выпуск
	Текущие выпуски
	Архивные выпуски
	Что такое RSS

Матем. заметки:
Год:
Том:
Выпуск:
Страница:
	Найти

Персональный вход:
Логин:
Пароль:
	Запомнить пароль
	Войти
	Забыли пароль?
	Регистрация

Математические заметки, 2024, том 116, выпуск 1, страницы 77–90
DOI: https://doi.org/10.4213/mzm14243 (Mi mzm14243)

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

$n$ -значные косетные группы и динамика

М. И. Корнев^ab

^a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
^b Национальный исследовательский университет "Высшая школа экономики", г. Москва

PDF полного текста (796 kB) Полный текст в HTML Список цитирования (1)

Список литературы:

PDF

HTML

DOI: https://doi.org/10.4213/mzm14243

Аннотация: Получены асимптотические и точные формулы для функций роста некоторых семейств

$n$ -значных косетных групп и описаны возникающие связи между теорией

$n$ -значных групп и символической динамикой.
Библиография: 17 названий.

Ключевые слова:

$n$ -значные косетные группы, функция роста, комбинаторика слов, динамические системы, числа

$n$ -боначчи.

Финансовая поддержка	Номер гранта
Национальный исследовательский университет "Высшая школа экономики"
Статья подготовлена в ходе проведения исследования в рамках проекта “Зеркальные лаборатории” НИУ ВШЭ.

Поступило: 02.02.2024
Исправленный вариант: 22.02.2024

Англоязычная версия:
Mathematical Notes, 2024, Volume 116, Issue 1, Pages 66–76
DOI: https://doi.org/10.1134/S000143462407006X

Реферативные базы данных:

Тип публикации: Статья

УДК: 512.54

MSC: 20-XX

1. Введение

В 1971 г. Новиков и Бухштабер определили конструкцию, мотивированную теорией характеристических классов [1]. Эта конструкция описывает умножение, в котором произведением любых пар элементов является неупорядоченное мультимножество из $n$ точек. Аксиоматическое определение $n$ -значных групп и их свойства были разработаны Бухштабером [2]. Множество авторов в настоящее время изучают теорию $n$ -значных конечных, дискретных, топологических и алгебро-геометрических групп с приложениями в различных областях математики и математической физики. Сравнительный анализ теорий однозначных и $n$ -значных групп можно найти в работе [3]. С 1996 г. Бухштабер и Веселов изучают приложения $n$ -значной теории групп к дискретным динамическим системам [4]. Недавно Чирков получил результаты о функции роста серии $n$ -значных косетных групп, $n=2,3, \dots$ , определенных автоморфизмами порядка $n$ на комплексных числах $\mathbb{C}$ [5]. За дальнейшими примерами приложений теории $n$ -значных групп в различных областях математики отсылаем читателя к списку литературы [6]–[9].

Раздел 2 посвящен краткому введению в основные конструкции теории $n$ -значных групп и фиксации некоторых обозначений, следуя [2].

В разделе 3 мы получаем точные и асимптотические формулы для функций роста $n$ -значных косетных групп

$\begin{equation*} \mathbb G_\varphi\bigl(\langle a, b\mid a^m=b^m=1 \rangle\bigr) \qquad\text{и}\qquad \mathbb G_\varphi\bigl(\langle a_1, \dots, a_s \mid a_1^2=\dots=a_s^2=1 \rangle\bigl), \end{equation*} \notag$

где

$\varphi$ – автоморфизм, циклически переставляющий образующие копредставлений групп в каждом случае. Данная проблема удивительным образом оказывается связанной с

$n$ -боначчиевыми числами. Мы используем результат работы [10], чтобы получить искомые выражения.

В разделе 4 мы более подробно рассматриваем случай 2-значной группы

$\begin{equation*} \mathbb G_\varphi(\langle a, b\mid a^3=b^3=1 \rangle), \end{equation*} \notag$

строя некоторое дерево, которое позволяет нам установить одно интересное комбинаторное наблюдение в предложении 6 и связь с символической динамикой.

Благодарности

Автор благодарен Виктору Матвеевичу Бухштаберу за творческую атмосферу и полезные обсуждения при подготовке данной работы. Автор благодарен рецензентам за ценные замечания и комментарии.

2. Предварительные сведения

Дадим некоторые определения и примеры, следуя [2].

Определение 1. $n$ -значным умножением на множестве $X$ называется отображение

$\begin{equation*} \mu\colon X\times X \to \operatorname{sym}^n(X)\colon \mu(x,y)=x*y=[z_1,z_2,\dots, z_n], \qquad z_k=(x*y)_k, \end{equation*} \notag$

где

$\operatorname{sym}^n(X):=X^n/\Sigma_n$ – симметрическая степень

$X$ , эквивалентно, множество, состоящее из мультимножеств

$[x_1, \dots, x_n]$ (или просто множеств далее для краткости), такое что выполнены следующие условия.

$\bullet$ Ассоциативность. $n^2$ -множества
$\begin{equation*} \begin{gathered} \, [x*(y*z)_1,x*(y*z)_2,\dots,x*(y*z)_n], \\ [(x*y)_1*z,(x*y)_2*z,\dots,(x*y)_n*z] \end{gathered} \end{equation*} \notag$
совпадают.
$\bullet$ Единица. Существует элемент $e\in X$ , для которого $e*x=x*e=[x,x,\dots,x]$ для любого $x\in X$ .
$\bullet$ Обратный элемент. Имеется отображение $\mathrm{inv}\colon X\to X$ со свойствами
$\begin{equation*} e\in \mathrm{inv}(x)* x, \qquad e \in x*\mathrm{inv}(x) \end{equation*} \notag$
для любого $x\in X$ .

Определение 2. Если множество $X$ имеет $n$ -значное умножение, то $X$ называется $n$ -значной группой. Иногда мы будем обозначать $n$ -значные группы ажурным шрифтом, например, $\mathbb G$ .

Пример 1. Всякая 1-значная группа $\mathbb G$ является обычной группой: условия ассоциативности, существования единицы и обратного элемента на 1-значное умножение из определения 1 превращаются в условия на некоторую групповую операцию.

Пример 2. Рассмотрим полугруппу неотрицательных целых чисел по сложению $\mathbb{Z}_+$ . Определим умножение $\mu\colon \mathbb{Z}_+\times \mathbb{Z}_+\to \operatorname{sym}^2\mathbb{Z}_+$ по формуле $x*y=[x+y, |x-y|]$ . Единица: $e=0$ . Обратный: $\mathrm{inv}(x)=x$ . Ассоциативность следует из того, что следующие два $4$ -множества совпадают:

$\begin{equation*} \begin{gathered} \, \bigl[x+y+z,\, |x-y-z|,\,x+|y-z|, \,|x-|y-z||\bigr], \\ \bigl[x+y+z,\,|x+y-z|,\,|x-y|+z,\,||x-y|-z|\bigr] \end{gathered} \end{equation*} \notag$

для любых неотрицательных целых

$x,y,z$ (упражнение для читателя).

Как и в случае с обычными группами, можно определить гомоморфизм $n$ -значных групп. Таким образом, класс $n$ -значных групп образует категорию $n\mathscr{G}rp$ .

Определение 3. Отображение $f\colon X\to Y$ между $n$ -значными группами называется гомоморфизмом, если

$\bullet$ $f(e_X)=e_Y$ ,
$\bullet$ $f(\mathrm{inv}_X(x))=\mathrm{inv}_Y(f(x))$ для любого $x\in X$ ,
$\bullet$ $\mu_{Y}(f(x),f(y))=(f)^n\mu_X(x,y)$ для любых $x, y\in X$ .

В частности, следующая диаграмма коммутативна:

Имеется способ построения $n$ -значных групп [2], при котором для данной ( $1$ -значной) группы $G$ с умножением $\mu_0$ , единицей $e_G$ , обратным $\operatorname{inv}_G(u)=u^{-1}$ и для данной конечной подгруппы $H$ группы автоморфизмов $\operatorname{Aut}(G)$ рассматривается множество орбит $X :=G/\varphi(H)$ группы $G$ по действию группы $\operatorname{im}\varphi$ с проекцией $\pi\colon G\to X$ и $n$ -значным умножением

$\begin{equation*} \mu\colon X\times X\to \operatorname{sym}^n(X), \end{equation*} \notag$

по формуле

$\begin{equation} \mu(x, y)=\bigl[ \pi(\mu_0(u, h(v))) \mid h\in H \bigr], \end{equation} \tag{2.1}$

где

$u\in\pi^{-1}(x)$ и

$v\in\pi^{-1}(y)$ .

Теорема 1 (В. М. Бухштабер [2]). Произведение $\mu$ из (2.1) определяет $n$ -значное умножение на пространстве орбит $X=G/\varphi(H)$ с единицей $e_x=\pi(e_G)$ и обратным $\operatorname{inv}_X(x)=\pi(\operatorname{inv}_G(u))$ , где $u\in\pi^{-1}(x)$ .

Определение 4. $n$ -значная группа из теоремы 1, которую мы будем обозначать через $\mathbb G_\varphi(G)$ , называется косетной группой.

Пример 3. Рассмотрим группу $G=\mathbb{Z}/2\ast\mathbb{Z}/2 \cong \langle a, b\mid a^2=b^2=e \rangle$ и конечную циклическую подгруппу автоморфизмов, порожденную элементом $\varphi\colon a\mapsto b$ порядка $2$ . Легко видеть, что подлежащее множество $X=G/\langle \varphi \rangle$ состоит из элементов

$\begin{equation*} u_{2n}=[(ab)^n, (ba)^n], \qquad u_{2n+1}=[b(ab)^n, a(ba)^n] \end{equation*} \notag$

для каждого

$n\geqslant 0$ , и 2-значное умножение в косетной группе

$\mathbb G_\varphi(G)$ выглядит так:

$\begin{equation*} u_k\ast u_\ell=[u_{k+\ell}, u_{|k-\ell|}]. \end{equation*} \notag$

В частности, 2-значные группа

$\mathbb G_\varphi(G)$ и группа

$\mathbb{Z}_{+}$ из примера 2 изоморфны. Это означает, что 2-значная группа

$\mathbb{Z}_{+}$ косетная, однако не всякая

$n$ -значная группа является косетной [11].

Пришло время упомянуть о связи теории $n$ -значных групп с динамическими системами.

Определение 5. $n$ -значной динамикой $T$ на пространстве (необязательно $n$ -значной группе) $X$ называется отображение $T\colon X\to \operatorname{sym}^n(X)$ .

Можно представлять себе $X$ как некоторое пространство состояний. Тогда $n$ -значная динамика $T$ определяет возможные состояния $T(x)=[x_1, \dots, x_n]$ в момент времени $t+1$ как функцию состояния элемента $x$ в момент времени $t$ .

Пример 4. Рассмотрим многочлен относительно переменной $y$ :

$\begin{equation*} F(x, y)=b_0(x)y^n+b_1(x)y^{n-1}+\dots+b_n(x), \qquad x,y\in \mathbb{C}, \end{equation*} \notag$

где

$b_i\colon \mathbb{C}\to \mathbb{C}$ – произвольные функции,

$b_0\neq 0$ . Уравнение

$F(x, y)=0$ относительно

$x$ определяет

$n$ -значную динамику

$\begin{equation*} T\colon \mathbb{C}\to \operatorname{sym}^n(\mathbb{C}), \qquad x\mapsto [y_1, \dots, y_n], \end{equation*} \notag$

где

$[y_1, \dots, y_n]$ –

$n$ -множество корней уравнения

$F(x, y)=0$ относительно

$y$ .

Для любой $n$ -значной динамики $T\colon X\to \operatorname{sym}^n(X)$ имеется полезная характеристика, измеряющая рост динамики $T$ .

Определение 6. Для любого $x\in X$ и любой $n$ -значной динамики $T\colon X\to \operatorname{sym}^n(X)$ , функция роста $\xi_{x}\colon \mathbb{N}\to \mathbb{N}$ сопоставляет числу $k$ количество различных точек в множестве

$\begin{equation*} \bigcup_{i=0}^k T^{i}(x)=\{\ast\}\cup T(x)\cup T^2(x)\cup \dots\cup T^k(x), \end{equation*} \notag$

где

$\ast$ – отмеченная точка в подлежащем множестве

$X$ .

В данном контексте имеется общая проблема характеризации таких $n$ -значных динамик, которые имеют полиномиальный или экспоненциальный рост $\xi_x$ . На рис. 1 изображены примеры двух таких 2-значных динамик в виде ориентированных графов: вершины, лежащие на одной вертикали с номером $k=0, 1, 2,\dots$ (слева направо), соответствуют точкам мультимножества $T^k(x)$ (где $x$ соответствует самой левой вершине графа – нулевой вертикали, которая совпадает с отмеченной точкой $T^0(x)=\ast=x$ ), т.е. точкам, “рожденным в момент времени $k$ ”. Пара ребер, исходящих из любой вершины, соответствует применению отображения $T$ (рождение новой пары точек). Согласно определению 5 слева на рис. 1 мы имеем динамику с квадратичной функцией роста $\xi_x(k)$ , поскольку число точек в множестве $\bigcup_{i = 0}^k T^{i}(x)$ , т.е. суммарное количество точек на всех вертикалях от нулевой до $k$ -й включительно, равно $(k+1)(k+2)/2$ , $k=0, 1, 2,\dots$ . Аналогично, справа на рис. 1 мы имеем динамику с экспоненциальной функцией роста $\xi_x(k) = 2^{k+1} - 1$ , $k = 0, 1, 2,\dots$ .

Рис. 1.Полиномиальный и экспоненциальный рост

$n$ -значные динамики возникают, например, из действий $n$ -значных групп на пространстве.

Определение 7. Действием $n$ -значной группы $\mathbb G$ на пространстве $X$ называется отображение

$\begin{equation*} f\colon \mathbb G\times X\to \operatorname{sym}^n(X), \qquad f(g, x)=g\cdot x= [x_1, \dots, x_n], \end{equation*} \notag$

такое что

$\bullet$ для любых элементов $g_1$ , $g_2\in \mathbb G$ и любого $x\in X$ следующие $n^2$ -множества совпадают:
$\begin{equation*} g_1(g_2x)=[g_1x_1, \dots, g_1x_n], \qquad (g_1g_2)x=[h_1x, \dots, h_nx], \end{equation*} \notag$
где $g_2x=[x_1, \dots, x_n]$ и $g_1g_2=[h_1, \dots, h_n]$ ,
$\bullet$ $ex=[x, \dots, x]$ для любого $x\in X$ .

Пример 5. В контексте определения 7, возьмем в качестве $X$ и $f$ $n$ -значную группу $\mathbb G$ и операцию в $\mathbb G$ соответственно.

Следующий класс $n$ -значных групп находится в центре внимания данной работы.

Определение 8. $n$ -значная группа $\mathbb G$ называется циклической, если существует элемент $g\in \mathbb G$ , такой что любой элемент $h\in G$ принадлежит мультимножеству $g^k(\operatorname{inv}(g))^k$ для некоторого $k>0$ .

3. Рост $n$ -значных групп

В данном разделе мы рассмотрим класс таких конечно определенных групп $G=\langle f_1, \dots, f_n\mid R \rangle$ , которые допускают автоморфизм $\varphi\in\operatorname{Aut}(G)$ , циклически переставляющий $n$ образующих $f_1, \dots, f_n$ . Пусть $\mathbb{G}_\varphi(G)$ обозначает $n$ -значную группу, возникающую из обычной группы $G$ и автоморфизма $\varphi\in\operatorname{Aut}(G)$ . Заметим, что группа $\mathbb G_\varphi(G)$ является циклической в смысле определения 8. Нас интересует функция роста $\xi_g(k)$ , ассоциированная с элементом $g=[f_1, \dots, f_n]$ . В данном контексте мы рассматриваем в качестве отмеченной точки из определения 6 пустое слово $\Lambda$ , или, что равносильно, единичный элемент группы $G$ . Для краткости мы будем использовать обозначение $\xi_k$ вместо $\xi_g(k)$ .

Пример 6. В примере 3 имеем линейный рост $\xi_k=k+1$ .

Предложение 1. Для группы $\mathbb{Z}/3\ast\mathbb{Z}/3=\langle a, b\mid a^3=b^3=1 \rangle$ и автоморфизма $a\mapsto b$ соответствующая $2$ -значная группа $\mathbb{G}_\varphi(\mathbb{Z}/3\ast\mathbb{Z}/3)$ имеет функцию роста

$\begin{equation*} \xi_k=F_{k+3}=\frac{1}{\sqrt{5}}\biggl(\biggl(\frac{1+ \sqrt{5}}{2}\biggr)^{k+3}-\biggl(\frac{1-\sqrt{5}}{2}\biggr)^{k+3}\biggr)-1. \end{equation*} \notag$

Следовательно, рост экспоненциален:

$\xi_k \sim {\alpha^{k+3}}/{\sqrt{5}}$ при

$k\to\infty$ , где

$\alpha=(1+\sqrt{5})/2$ .

Доказательство. Будем считать количество слов длины

$k$ на шаге, при котором вычисляется

$[a, b]^k$ . На нулевом шаге мы имеем пустое слово соответствующее единице 2-значной группы. На первом шаге получается

$[a, b]$ , что соответствует одному элементу 2-значной группы. На втором шаге имеем

$[a, b]^2=[[a^2, b^2], [ab, ba]]$ – два элемента.

На шаге $k$ появятся все слова в нормальной форме группы $\mathbb{Z}/3\ast\mathbb{Z}/3$ . Любое такое слово имеет вид (с точностью до автоморфизма)

$\begin{equation*} a^{k_1}b^{k_2}a^{k_3}\dots, \end{equation*} \notag$

где

$k_i\in \{1, 2\}$ . Значит, всего таких слов длины

$k$ будет столько, сколькими способами можно разбить число

$k$ на слагаемые из множества

$\{1, 2\}$ с учетом порядка. Обозначим последнее количество через

$S_k$ .

От шага $k$ можно перейти к шагу $k-1$ , взяв в качестве первого слагаемого 1 – в этом случае остальные слагаемые можно будет набрать $S_{k-1}$ способами, либо 2 – в этом случае будет $S_{k-2}$ . Значит, имеем рекуррентное соотношение

$\begin{equation*} S_k=S_{k-1}+S_{k-2}, \qquad S_0=1, \qquad S_1=1. \end{equation*} \notag$

Напомним, что рекуррентная последовательность

$\begin{equation*} F_n=F_{n-1}+F_{n-2} \end{equation*} \notag$

с начальными условиями

$\begin{equation*} F_0=0, \qquad F_1=1, \end{equation*} \notag$

называется последовательностью Фибоначчи. Имеется известная формула Бине

$\begin{equation*} F_n=\frac{1}{\sqrt{5}}\biggl( \biggl(\frac{1+\sqrt{5}}{2}\biggr)^n- \biggl(\frac{1-\sqrt{5}}{2}\biggr)^n\biggr ). \end{equation*} \notag$

В нашем случае

$\begin{equation*} S_k=F_{k+1}. \end{equation*} \notag$

По индукции легко доказать, что

$\begin{equation} F_1+\dots+F_k=F_{k+2}-1. \end{equation} \tag{3.1}$

Отсюда

$\begin{equation*} \xi_k=S_0+S_1+\dots+S_k=F_{k+3}-1=\frac{1}{\sqrt{5}}\biggl ( \biggl(\frac{1+\sqrt{5}}{2} \biggr)^{k+3} -\biggl( \frac{1-\sqrt{5}}{2} \biggr )^{k+3} \biggr )-1. \end{equation*} \notag$

Предложение 2. Для группы

$\begin{equation*} \mathbb{Z}/2\ast\mathbb{Z}/2\ast\mathbb{Z}/2=\langle a, b, c \mid a^2=b^2=c^2=1 \rangle \end{equation*} \notag$

с автоморфизмом

$a\mapsto b\mapsto c$ получается

$3$ -значная группа с функцией роста

$\xi_k= 2^k$ . Следовательно, рост экспоненциален.

Доказательство. Нормальная форма с точностью до автоморфизма для группы из условия имеет вид, при котором первая буква слова – буква

$a$ и одинаковые буквы не стоят рядом. Докажем индукцией, что число

$S_k$ различных слов в нормальной форме длины в мультимножестве

$[a, b, c]^k$ равно

$2^{k-1}$ , если

$k>0$ и

$S_0=1$ . При

$k=0$ мы имеем пустое слово. Предположим, что на шаге

$k-1$ мы имеем

$2^{k-2}$ различных слов длины

$k-1$ . Тогда допишем справа к каждому слову длины

$k-1$ по одной букве так, чтобы длина нормальной формы слова увеличилась на 1. Это можно сделать двумя способами для одного фиксированного слова. Всего слов длины

$k-1$ ровно

$2^{k-2}$ , поэтому слов длины

$k$ будет

$2\cdot 2^{k-2}=2^{k-1}$ . Утверждение про

$\xi_k$ теперь очевидно следует.

Предложение 3. Для группы $(\mathbb{Z}/2)^{\ast s}=\langle a_1, \dots, a_s \mid a_1^2=\dots=a_s^2=1 \rangle$ с автоморфизмом $a_i\mapsto a_{i+1}$ (индексы сдвигаются по модулю $s)$ получается $s$ -значная группа с функцией роста

$\begin{equation*} \xi_{k}=\begin{cases} \dfrac{(s-1)^{k}-1}{s-2}+1, & s\geqslant3, \\ k+1, & s=2. \end{cases} \end{equation*} \notag$

Следовательно, рост линеен тогда и только тогда, когда

$s=2$ .

Доказательство аналогично доказательству предложения 2.

Дадим важные для дальнейшего определение и свойства последовательности $n$ -боначчиевых чисел.

Определение 9. Последовательность целых чисел $\{F_k^{(n)}\}$ называется $n$ -боначчиевой, если она удовлетворяет рекуррентному соотношению

$\begin{equation} F_k^{(n)}= F_{k-1}^{(n)}+\dots+F_{k-n}^{(n)} \end{equation} \tag{3.2}$

и начальным условиям

$F_0=\dots=F_{n-2}=0$ и

$F_{n-1}=1$ .

Предложение 4 (Z. Du, G. P. Dresden [6]). Явная формула $k$ -го члена последовательности $n$ -боначчи (обобщенная формула Бине) выглядит следующим образом:

$\begin{equation} F_k=\sum_{i=1}^n \frac{\lambda_i-1}{(n+1)\lambda_i-2n}\lambda_i^{k-n+1}, \end{equation} \tag{3.3}$

где

$\{\lambda_i\mid 1\leqslant i\leqslant n\}$ – множество корней характеристического многочлена

$\chi(\lambda)=\lambda^n-\lambda^{n-1}-\dots-1$ .

В работе [10] формула (3.3) получена из основного результата работы [12] о последовательности, удовлетворяющей рекуррентному соотношению (3.2), но с другими начальными данными. На форуме [13] можно найти прямое доказательство предложения 4, опирающееся на теорию линейных рекуррентов.

Из принципа Руше и правила знаков Декарта легко следует, что многочлен

$\begin{equation*} \chi(\lambda)=\frac{\lambda^{n+1}-2\lambda^n+1}{\lambda-1} \end{equation*} \notag$

из предложения 4 (

$\lambda\neq 1$ ) имеет ровно один положительный корень, больший 1, и

$n$ комплексных корней внутри единичного круга с центром в нуле на комплексной плоскости. Это означает, что среди слагаемых суммы (3.3) имеется ровно одно, модуль которого больше 1. Последний факт также можно увидеть из того, что матрица, задающая соответствующий линейный рекуррент, удовлетворяет теореме Перрона–Фробениуса (см., например, [14; гл. XIII, § 2, формула (37)]) и значит, имеет своим максимальным по модулю собственным значением вещественное число, большее 1. Оказывается, сумма всех остальных слагаемых в формуле (3.3) всегда меньше

$1/2$ , и имеет место следующая

Теорема 2 (Z. Du, G. P. Dresden [10]). Для $k$ -го члена последовательности $n$ -боначчи имеем

$\begin{equation*} F_k^{(n)}=\operatorname{rnd}\biggl(\frac{r-1}{(n+1)r-2n}r^{k-n+1} \biggr), \end{equation*} \notag$

где

$r$ – положительный корень многочлена

$\chi(\lambda)=\lambda^n-\lambda^{n-1}-\dots-1$ , а

$\operatorname{rnd} (\cdot)$ – ближайшее целое.

Применим теперь данный результат в интересующем нас случае.

Предложение 5. Для группы $\mathbb{Z}/m\ast\mathbb{Z}/m=\langle a, b\mid a^m=b^m=1 \rangle$ с автоморфизмом $\varphi\colon a\mapsto b$ функция роста при $m\geqslant 3$

$\begin{equation*} \xi_{k}\sim\frac{r^{k+1}}{mr-2(m-1)} \end{equation*} \notag$

при

$k\to\infty$ , где

$r$ – положительный корень многочлена

$\chi(\lambda)=\lambda^n-\lambda^{n-1}- \dots-1$ .

Замечание. При $m = 2$ мы имеем 2-значную группу, рассмотренную в предложении 3 (при $s = 2$ ). В этом случае рост $\xi_k$ линеен.

Доказательство предложения 5. Нормальная форма в данном случае будет иметь вид

$\begin{equation*} a^{k_1}b^{k_2}a^{k_3}\dots, \end{equation*} \notag$

где

$k_i\in \{1, 2, \dots, m-1\}$ . Пусть

$m\geqslant 3$ . Обозначим через

$S_k$ число различных слов длины

$k$ в мультимножестве

$[a, b]^k$ . Будем считать, что

$\begin{equation*} S_{-(m-2)}=\dots=S_{-1}=0 \qquad \text{и}\qquad S_0=1. \end{equation*} \notag$

Имеем рекуррентное соотношение

$\begin{equation*} S_k=S_{k-1}+S_{k-2}+\dots+S_{k-m+1}. \end{equation*} \notag$

Данное рекуррентное соотношение вместе с начальными условиями определяют сдвинутую на

$m-2$ последовательность

$(m-1)$ -боначчи

$\begin{equation*} S_k^{(m-1)}=F_{k+m-2}^{(m-1)}, \end{equation*} \notag$

где

$k\geqslant -(m-2)$ .

Таким образом, по теореме 2

$\begin{equation*} S_k=\operatorname{rnd} \biggl(\frac{r-1}{mr-2(m-1)}r^{k} \biggr). \end{equation*} \notag$

Учитывая, что $r > 1$ , получаем

$\begin{equation*} \xi_k=S_1+S_2+\dots+S_k \sim \sum_{i=1}^k \frac{r-1}{mr-2(m-1)}r^{i} \sim \frac{r^{k+1}}{mr-2(m-1)} \end{equation*} \notag$

при

$k\to\infty$ .

Замечание. Заметим, что последовательные суммы членов линейного рекуррента сами удовлетворяют некоторому линейному рекурренту (см. [15; п. 4]). В частности, обозначая $\xi_k :=F^{(n)}_0+\dots+F^{(n)}_k$ , получаем

$\begin{equation} \xi_{n+k}= 2\xi_{n+k-1}-\xi_{k-1}. \end{equation} \tag{3.4}$

Для каждого фиксированного

$n$ неопределенные коэффициенты в общем виде решения уравнения (3.4) являются функциями чисел

$n$ -боначчи

$F^{(n)}_0=0, \dots, F^{(n)}_{n-1}=1$ . Например, при

$n=2$ получается равенство (3.1). Для

$n=3$ получается следующее равенство:

$\begin{equation*} F^{(3)}_0+F^{(3)}_1+\dots+F^{(3)}_k=\frac{F^{(3)}_{k+2}+F^{(3)}_{k}- 1}{2}. \end{equation*} \notag$

Автору неизвестно о существовании замкнутой формы для сумм чисел

$n$ -боначчи в общем случае.

4. Связь с символической динамикой

В данном разделе мы более подробно остановимся на 2-значной группе

$\begin{equation*} \mathbb{G}_\varphi(\mathbb{Z}/3\ast\mathbb{ Z}/3) \end{equation*} \notag$

в контексте комбинаторики слов (см., например, [16], [17]).

Для краткости дадим следующее

Определение 10. Будем называть бескубным любое слово в нормальной форме группы $\mathbb{Z}/3\ast\mathbb{Z}/3=\langle a, b\mid a^3=b^3=1 \rangle$ .

Из вида нормальной формы группы $\mathbb{Z}/3\ast\mathbb{Z}/3$ ясно, что на шаге $k$ возникают все возможные бескубные слова в алфавите $\{a, b\}$ . Они разбиваются на классы слов, начинающихся с буквы $a$ (в случае непустого слова).

Построим ориентированное дерево $\Gamma$ , в вершинах которого будут стоять элементы 2-значной группы $\mathbb{G}$ следующим образом (см. рис. 2). На шаге 0 начнем с вершины, отвечающей пустому слову $\Lambda$ , – это корень нашего дерева. На шаге 1 образуем смежную с корнем вершину $[a, b]$ . На шаге 2 от последней вершины отведем два ребра, каждое из которых соответствует приписыванию справа буквы $a$ или $b$ . А именно, первое ребро ведет в вершину, соответствующую классу слова $a^2$ , т.е. элементу $[a^2 , b^2 ]$ . Второе ребро – в вершину, соответствующую классу слова $ab$ , т.е. элементу $[ab,ba]$ . Получатся две вершины со словами длины 2: $[a^2, b^2]$ и $[ab, ba]$ . На шаге $k$ мы стартуем со всех бескубных слов длины $k-1$ и отводим от каждой вершины 1 или 2 ребра, руководствуясь следующим принципом: если слово оканчивается на первую степень буквы, то от данной вершины будет отходить ровно 2 ребра, соответствующих умножению на $a$ или $b$ ; если слово оканчивается на квадрат буквы, то от данной вершины будет отходить в точности одно ребро, соответствующее дополнительной букве.

Рис. 2

В данном дереве на уровне $k$ находится в точности $F_{k+1}$ вершин.

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

Определение 11. Пусть $A$ и $B$ – алфавиты. Морфизмом называется отображение $\mathcal{F}$ между множествами слов $A^\ast$ и $B^\ast$ в соответствующих алфавитах

$\begin{equation*} \mathcal{F}(xy)=\mathcal{F}(x)\mathcal{F}(y) \end{equation*} \notag$

для любых слов

$x, y\in A^\ast$ , т.е.

$\mathcal{F}$ является гомоморфизмом свободных моноидов.

В некоторых случаях последовательность слов $\{\mathcal{F}^{n}(a)\}$ имеет предельное слово $\mathcal{F}^{\infty}(a)$ (см. детали в [16]).

Пример 7 [16]. Рассмотрим морфизм

$\begin{equation*} \mathcal{F}\colon \{a, b\}^\ast\to\{a, b\}^\ast, \qquad a\mapsto ab, \quad b\mapsto a. \end{equation*} \notag$

Бесконечным словом Фибоначчи называется

$\Phi :=\mathcal{F}^{\infty}(a)$

$\begin{equation*} \Phi=abaababaabaababaababaabaababaaba\dots\,. \end{equation*} \notag$

Пример 8 [16]. Морфизм

$\begin{equation*} \mathcal{F}\colon \{a, b\}^\ast\to \{a, b\}^\ast, \ a\mapsto ab,\ b\mapsto ba \end{equation*} \notag$

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

$\mathcal{T}:=\mathcal{F}^\infty(a)$

$\begin{equation*} \mathcal{T}=abbabaabbaababbabaababbaabbabaab\dots\,. \end{equation*} \notag$

Поскольку пути в дереве $\Gamma$ соответствуют всем возможным бескубным словам, то в частности, слово Фибоначчи и последовательность Туэ–Морса определяют некоторые два пути. На рис. 3 фиолетовым показан путь, соответствующий слову Фибоначчи, а также красным показан путь, соответствующий последовательности Туэ–Морса.

Рис. 3

Заметим следующее свойство построенного графа $\Gamma$ .

Лемма 1. На $k$ -м уровне дерева $\Gamma$ расположены сверху вниз в лексикографическом порядке все бескубные слова длины $k$ , начинающиеся с буквы $a$ .

Доказательство. Индукция по

$k$ . При

$k=0$ мы имеем пустое слово, и утверждение очевидно. Рассмотрим все вершины уровня

$k$ – обозначим это множество через

$L_k$ . Пусть

$v_1, v_2\in L_k$ , причем

$v_1 < v_2$ в лексикографическом порядке. Тогда будет выполнено неравенство

$\begin{equation*} \mathrm{Child}(v_1) < \mathrm{Child}(v_2) \end{equation*} \notag$

между потомками вершин

$v_1$ и

$v_2$ соответственно, т.е.

$u_1 < u_2$ для любых

$u_1\in\mathrm{Child}(v_1)$ и

$u_2\in\mathrm{Child}(v_2)$ . Это так в силу того, что дописывания происходят справа, а в лексикографическом порядке слова сравниваются слева.

Лемма 2. Для произвольной вершины $v$ графа $\Gamma$ рассмотрим поддерево $\Gamma_v$ , растущее из этой вершины. Тогда количества вершин на каждом уровне данного поддерева $\Gamma_v$ образуют последовательность Фибоначчи, стартующую либо с $F_1$ , либо с $F_2$ в зависимости от того, на первую или вторую степень буквы оканчивается слово $w(v)$ (начинающееся с $a)$ в вершине $v$ .

Доказательство. Посмотрим на последнюю букву слова

$w(v)$ , а про остальные буквы забудем. Оно является либо первой степенью буквы, скажем,

$a$ , либо второй степенью буквы, скажем

$a^2$ (без ограничения общности). В первом случае получается, что из

$v$ будет расти поддерево

$\Gamma_{[a, b]}$ , а во втором – исходное дерево

$\Gamma_\Lambda=\Gamma$ . Но для исходного дерева

$\Gamma$ количества вершин на каждом уровне образуют последовательность Фибоначчи по построению

$\Gamma$ , как было замечено в предложении 1.

Из данной леммы получается следующее

Предложение 6. Рассмотрим последовательность $\{\Theta_k\}$

$\begin{equation*} \Theta_1 = \Psi a, \quad \Theta_2 = \Psi aa, \quad \Theta_3 = \Psi aab, \quad \dots \end{equation*} \notag$

подслов бесконечного бескубного слова

$\begin{equation*} \Psi aabaabaab\dots=: \Psi(aab), \end{equation*} \notag$

где

$\Psi$ – любое бескубное слово, последняя буква которого отлична от

$a$ . Тогда число

$Q_k$ бескубных слов, не меньших слова

$\Theta_k$ в стандартном лексикографическом порядке, удовлетворяет рекуррентному соотношению

$(k\geqslant 3)$

$\begin{equation*} Q_k=Q_{k-1}+Q_{k-2}. \end{equation*} \notag$

Доказательство. Слову

$\begin{equation*} \Psi aabaabaab\dots=\Psi(aab) \end{equation*} \notag$

соответствует бесконечный путь

$\gamma$ в дереве

$\Gamma$ . Каждому

$\Theta_k$ биективно соответствует некоторая вершина в этом пути. Интересующее нас множество слов

$\bigcup_{k} Q_k$ соответствует всем вершинам, лежащим под

$\gamma$ . Но последнее множество является объединением всех вершин поддеревьев. Теперь утверждение следует из суммирования всех рекуррентных соотношений для каждого поддерева по лемме 2.



СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

1.	В М. Бухштабер, С. П. Новиков, “Формальные группы, степенные системы и операторы Адамса”, Матем. сб., 84 (126):1 (1971), 81–118
2.	V. M. Buchstaber, “ $n$ -valued groups: theory and applications”, Mosc. Math. J., 6:1 (2006), 57–84
3.	H. Behravesh, A. A. Borovik, “A note on multivalued groups”, Ric. Mat., 61:2 (2012), 245–253
4.	V. M. Buchstaber, A. P. Veselov, “Integrable correspondences and algebraic representations of multivalued groups”, Internat. Math. Res. Notices, 1996:8 (1996), 381–400
5.	М. А. Чирков, “Функция роста $n$ -значной динамики”, Матем. заметки, 115:3 (2024), 458–465
6.	В. М. Бухштабер, А. П. Веселов, “Топограф Конвея, $\mathrm{PGL}_2(\mathbb Z)$ -динамика и двузначные группы”, УМН, 74:3 (447) (2019), 17–62
7.	В. М. Бухштабер, А. П. Веселов, А. А. Гайфуллин, “Классификация инволютивных коммутативных двузначных групп”, УМН, 77:4 (466) (2022), 91–172
8.	V. M. Buchstaber, E. G. Rees, “Multivalued groups, their representations and Hopf algebras”, Transform. Groups, 2:4 (1997), 325–349
9.	V. M. Buchstaber, V. Dragovic, “Two-valued groups, Kummer varieties, and integrable billiards”, Arnold Math. J., 4:1 (2018), 27–57
10.	Z. Du, G. P. Dresden, “A simplified Binet formula for $k$ -generalized Fibonacci numbers”, J. Integer Seq., 17:4 (2014), 14.4.7
11.	В. М. Бухштабер, А. М. Вершик, С. А. Евдокимов, И. Н. Пономаренко, “Комбинаторные алгебры и многозначные инволютивные группы”, Функц. анализ и его прил., 30:3 (1996), 12–18
12.	W. R. Spickerman, R. N. Joyner, “Binet's formula for the recursive sequence of order $k$ ”, Fibonacci Quart., 22:4 (1984), 327–331
13.	The forum discussions, bbs.emath.ac.cn/thread-667-4-1.html#pid9145, 2023
14.	Ф. Р. Гантмахер, Теория матриц, Наука, M., 1966
15.	А. И. Маркушевич, Возвратные последовательности, Гостехиздат, М., 1950
16.	M. Lothaire, Algebraic Combinatorics on Words, Cambridge Math. Lib., Cambridge Univ. Press, Cambridge, 2002
17.	Ан. А. Мучник, Ю. Л. Притыкин, А. Л. Семенов, “Последовательности, близкие к периодическим”, УМН, 64:5 (389) (2009), 21–96

Образец цитирования: М. И. Корнев, “

$n$ -значные косетные группы и динамика”, Матем. заметки, 116:1 (2024), 77–90; Math. Notes, 116:1 (2024), 66–76

Цитирование в формате AMSBIB

\RBibitem{Kor24}

\by М.~И.~Корнев

\paper $n$-значные косетные группы и динамика

\jour Матем. заметки

\yr 2024

\vol 116

\issue 1

\pages 77--90

\mathnet{http://mi.mathnet.ru/mzm14243}

\crossref{https://doi.org/10.4213/mzm14243}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4811497}

\transl

\jour Math. Notes

\yr 2024

\vol 116

\issue 1

\pages 66--76

\crossref{https://doi.org/10.1134/S000143462407006X}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001343531800025}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85207234013}

Образцы ссылок на эту страницу:

https://www.mathnet.ru/rus/mzm14243

https://doi.org/10.4213/mzm14243

https://www.mathnet.ru/rus/mzm/v116/i1/p77

Эта публикация цитируется в следующих 1 статьяx:

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Статистика просмотров:
Страница аннотации:	198
PDF полного текста:	12
HTML русской версии:	37
Список литературы:	35
Первая страница:	16

Обратная связь:

Пользовательское соглашение

Регистрация посетителей портала

Логотипы

1. Введение

Благодарности

2. Предварительные сведения

3. Рост nn-значных групп

4. Связь с символической динамикой

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

3. Рост $n$ -значных групп