| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) М. И. Корневab a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва b Национальный исследовательский университет "Высшая школа экономики", г. Москва
Англоязычная версия:
Mathematical Notes, 2024, Volume 116, Issue 1, Pages DOI: https://doi.org/10.1134/S000143462407006X 
Реферативные базы данных:
   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$ называется отображение где $\operatorname{sym}^n(X):=X^n/\Sigma_n$ – симметрическая степень $X$, эквивалентно, множество, состоящее из мультимножеств $[x_1, \dots, x_n]$ (или просто множеств далее для краткости), такое что выполнены следующие условия. Определение 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$-множества совпадают: для любых неотрицательных целых $x,y,z$ (упражнение для читателя). Как и в случае с обычными группами, можно определить гомоморфизм $n$-значных групп. Таким образом, класс $n$-значных групп образует категорию $n\mathscr{G}rp$. Определение 3. Отображение $f\colon X\to Y$ между $n$-значными группами называется гомоморфизмом, если В частности, следующая диаграмма коммутативна: Имеется способ построения $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(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$ состоит из элементов Пришло время упомянуть о связи теории $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$: где $b_i\colon \mathbb{C}\to \mathbb{C}$ – произвольные функции, $b_0\neq 0$. Уравнение $F(x, y)=0$ относительно $x$ определяет $n$-значную динамику где $[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$ количество различных точек в множестве где $\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$ . $n$-значные динамики возникают, например, из действий $n$-значных групп на пространстве. Определение 7. Действием $n$-значной группы $\mathbb G$ на пространстве $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)$ имеет функцию роста Следовательно, рост экспоненциален: $\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$. Любое такое слово имеет вид (с точностью до автоморфизма) где $k_i\in \{1, 2\}$. Значит, всего таких слов длины $k$ будет столько, сколькими способами можно разбить число $k$ на слагаемые из множества $\{1, 2\}$ с учетом порядка. Обозначим последнее количество через $S_k$.От шага $k$ можно перейти к шагу $k-1$, взяв в качестве первого слагаемого 1 – в этом случае остальные слагаемые можно будет набрать $S_{k-1}$ способами, либо 2 – в этом случае будет $S_{k-2}$. Значит, имеем рекуррентное соотношение Напомним, что рекуррентная последовательность с начальными условиями называется последовательностью Фибоначчи. Имеется известная формула Бине
$$
\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
$$
В нашем случае По индукции легко доказать, что Отсюда Предложение 2. Для группы с автоморфизмом $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$-значная группа с функцией роста Следовательно, рост линеен тогда и только тогда, когда $s=2$. Доказательство аналогично доказательству предложения 2. Дадим важные для дальнейшего определение и свойства последовательности $n$-боначчиевых чисел. Определение 9. Последовательность целых чисел $\{F_k^{(n)}\}$ называется $n$-боначчиевой, если она удовлетворяет рекуррентному соотношению и начальным условиям $F_0=\dots=F_{n-2}=0$ и $F_{n-1}=1$. Предложение 4 (Z. Du, G. P. Dresden [6]). Явная формула $k$-го члена последовательности $n$-боначчи (обобщенная формула Бине) выглядит следующим образом: где $\{\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$-боначчи имеем где $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$ при $k\to\infty$, где $r$ – положительный корень многочлена $\chi(\lambda)=\lambda^n-\lambda^{n-1}- \dots-1$. Замечание. При $m = 2$ мы имеем 2-значную группу, рассмотренную в предложении 3 (при $s = 2$). В этом случае рост $\xi_k$ линеен. Доказательство предложения 5. Нормальная форма в данном случае будет иметь вид где $k_i\in \{1, 2, \dots, m-1\}$. Пусть $m\geqslant 3$. Обозначим через $S_k$ число различных слов длины $k$ в мультимножестве $[a, b]^k$. Будем считать, что Имеем рекуррентное соотношение Данное рекуррентное соотношение вместе с начальными условиями определяют сдвинутую на $m-2$ последовательность $(m-1)$-боначчи где $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$, получаем при $k\to\infty$.Замечание. Заметим, что последовательные суммы членов линейного рекуррента сами удовлетворяют некоторому линейному рекурренту (см. [15; п. 4]). В частности, обозначая $\xi_k :=F^{(n)}_0+\dots+F^{(n)}_k$, получаем Для каждого фиксированного $n$ неопределенные коэффициенты в общем виде решения уравнения (3.4) являются функциями чисел $n$-боначчи $F^{(n)}_0=0, \dots, F^{(n)}_{n-1}=1$. Например, при $n=2$ получается равенство (3.1). Для $n=3$ получается следующее равенство: Автору неизвестно о существовании замкнутой формы для сумм чисел $n$-боначчи в общем случае. 4. Связь с символической динамикойВ данном разделе мы более подробно остановимся на 2-значной группе в контексте комбинаторики слов (см., например, [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$; если слово оканчивается на квадрат буквы, то от данной вершины будет отходить в точности одно ребро, соответствующее дополнительной букве. В данном дереве на уровне $k$ находится в точности $F_{k+1}$ вершин. На данном графе можно отметить два пути, соответствующих двум хорошо известным бесконечным словам в символической динамике. Чтобы их определить, введем понятие морфизма. Определение 11. Пусть $A$ и $B$ – алфавиты. Морфизмом называется отображение $\mathcal{F}$ между множествами слов $A^\ast$ и $B^\ast$ в соответствующих алфавитах для любых слов $x, y\in A^\ast$, т.е. $\mathcal{F}$ является гомоморфизмом свободных моноидов. В некоторых случаях последовательность слов $\{\mathcal{F}^{n}(a)\}$ имеет предельное слово $\mathcal{F}^{\infty}(a)$ (см. детали в [16]). Пример 7 [16]. Рассмотрим морфизм Бесконечным словом Фибоначчи называется $\Phi :=\mathcal{F}^{\infty}(a)$ Пример 8 [16]. Морфизм определяет последовательность Туэ–Морса $\mathcal{T}:=\mathcal{F}^\infty(a)$ Поскольку пути в дереве $\Gamma$ соответствуют всем возможным бескубным словам, то в частности, слово Фибоначчи и последовательность Туэ–Морса определяют некоторые два пути. На рис. 3 фиолетовым показан путь, соответствующий слову Фибоначчи, а также красным показан путь, соответствующий последовательности Туэ–Морса. Заметим следующее свойство построенного графа $\Gamma$. Лемма 1. На $k$-м уровне дерева $\Gamma$ расположены сверху вниз в лексикографическом порядке все бескубные слова длины $k$, начинающиеся с буквы $a$. Доказательство. Индукция по $k$. При $k=0$ мы имеем пустое слово, и утверждение очевидно. Рассмотрим все вершины уровня $k$ – обозначим это множество через $L_k$. Пусть $v_1, v_2\in L_k$, причем $v_1 < v_2$ в лексикографическом порядке. Тогда будет выполнено неравенство между потомками вершин $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\}$ подслов бесконечного бескубного слова где $\Psi$ – любое бескубное слово, последняя буква которого отлична от $a$. Тогда число $Q_k$ бескубных слов, не меньших слова $\Theta_k$ в стандартном лексикографическом порядке, удовлетворяет рекуррентному соотношению $(k\geqslant 3)$ Доказательство. Слову соответствует бесконечный путь $\gamma$ в дереве $\Gamma$. Каждому $\Theta_k$ биективно соответствует некоторая вершина в этом пути. Интересующее нас множество слов $\bigcup_{k} Q_k$ соответствует всем вершинам, лежащим под $\gamma$. Но последнее множество является объединением всех вершин поддеревьев. Теперь утверждение следует из суммирования всех рекуррентных соотношений для каждого поддерева по лемме 2.
Цитирование в формате AMSBIB
\RBibitem{Kor24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|