В формате TeX

Омский государственный университет
Математический факультет
Кафедра информационных систем
Усредненная функция Дена

Дипломная работа студентки гр.ММ-802 Кукиной Е.Г.
Научный руководитель д.ф.-м.н., профессор В.А.Романьков

Оглавление

• 1. Введение
  • 1.1 Обзор литературы и предварительные сведения
  • 1.2 Результаты работы
    • 1.2.1 Результаты главы 2
    • 1.2.2 Результаты главы 3
• 2. Усредненная функция Дена для свободных абелевых групп
  • 2.1 Идея доказательства
  • 2.2 Ограничение площади
  • 2.3 Ограничение вероятности выхода за куб
  • 2.4 Окончание доказательства теоремы
  • 2.5 О некоторых плоских кристаллографических группах
• 3. Усредненная функция Дена для группы
  • 3.1 Вычисление усредненной функции Дена для группы
  • 3.2 Сокращения в свободной абелевой группе
• 4. Усредненная функция Дена для группы
  • 4.1 Количество единичных слов для группы
  • 4.2 Точная усредненная функция Дена для
  • 4.3 Некоторые предельные замечания
• 5. Заключение
• Литература

1. Введение

1.1 Обзор литературы и предварительные сведения

Пусть $G = F_r/R$ -- конечно определенная группа, представленная как фактор группа свободной группы $F_r$ конечного ранга $r$ от множества свободных порождающих $X_r = \{x_1, \ldots , x_r\}$ по нормальной подгруппе $R = ncl(r_1, \ldots , r_m).$ Обозначим как ${\mathfrak P(G) = <x_1, ..., x_r \vert r_1, ..., r_m>}$ соответствующее представление группы $G$ через порождающие элементы и определяющие соотношения. Любое (не обязательно редуцированное) слово $w$ в алфавите $X_r$ определяет элемент группы $F_r.$ Через $\vert w\vert$ мы обозначаем его длину. Естественный гомоморфизм $\varphi : F_r \rightarrow G$ позволяет говорить о значении слова $w$ в группе $G.$ В частности, запись $w=_G v$ означает, что значения слов $w, v$ в группе $G$ совпадают. Очевидно, что равенство $w=_G 1$ и включение $w\in R$ равносильны. Они эквивалентны тому, что в группе $F_r$ существует запись вида:

$$w=g_1g_2\ldots g_p,$$ (1.1)

где $g_i=\left(r_{i_j}^{\epsilon_i}\right)^{f_i}$ для некоторого $f_i \in F_r,$ $\epsilon_i\in{\pm1},$ $i_j\in\{1,\ldots m\},$ ${i\in \{1,\ldots p\}.}$ Как обычно, запись $g^f$ означает сопряжение $f^{-1}gf.$

Определим $\Omega_k=\left\{ w=_G1 \Bigl\vert \vert w\vert\le k \Bigr. \right\}$ -- множество слов алфавита $X_r,$ значения которых в группе $G$ равны $1,$ а длина не превосходит фиксированного числа $k.$



Известно (см. [8]), что функции Дена группы $G$ относительно двух различных представлений $\mathfrak P(G),\,\mathfrak Q(G)$ эквивалентны. А это означает, что имеет смысл говорить о функции Дена группы $G$ (не поясняя в каком представлении рассматривается группа). Известно (см. [10]), что линейность функции Дена эквивалентна тому, что группа гиперболическая. А.Ю.Ольшанский [3] (см.также [2] и  [9]) доказал теорему о том, что если функция Дена субквадратична, то группа гиперболическая. Известно [8], что функция Дена группы $\mathbb Z^l$ при $l\ge 2$ квадратична. Следующее определение встречается в работе М.Громова [1].

Рассмотрим два представления группы $G:$ $\mathfrak P_R(G)=\left<x_1, x_2, \ldots x_r\left\vert r_1, r_2, \ldots r_m \right.\right>$ и $\mathfrak P_Q(G)=\left<x_1, x_2, \ldots x_r\left\vert q_1, q_2, \ldots q_k \right.\right>.$ Тогда для любого слова $w$ алфавита $X$, $w=_G1,$ можно ввести $S_w^R$ -- площадь слова $w$ в первом представлении и $S_w^Q$ -- площадь слова $w$ во втором представлении. Обозначим $C=\max\limits_i S_{r_i}^Q.$ Тогда понятно, что для любого слова $w,$ задающего единицу в группе $G,$ $S_w^Q\le C S_w^R.$ А так как длина слова в обоих представлениях одинакова (одно и то же множество порождающих), то усредненные функции Дена для таких двух представлений эквивалентны. Следовательно, имеет смысл говорить об усредненной функции Дена группы $G$ относительно порождающего множества $X.$ В некоторых случаях нам будет удобно использовать вместо усредненной функции Дена другую функцию. Для этого определим $\Delta_k=\left\{ w=_G1 \Bigl\vert \vert w\vert=k \Bigr. \right\}$ -- множество слов алфавита $X_r,$ значения которых в группе $G$ равны $1,$ а длина равна фиксированному числу $k.$

Усредненная функция Дена лучше тем, что она определена $\forall k>2,$ а точная усредненная функция Дена не определена корректно для тех $k,$ для которых множество $\Delta_k=\zero.$

1.2 Результаты работы

1.2.1 Результаты главы 2.

В главе 2 рассматриваем свободные абелевы группы $\Bbb Z^r$ с естественным представлением: $\mathfrak P(\Bbb Z^r)=\left<x_1, x_2, \ldots x_r \Bigl\vert x_ix_jx_i^{-1}x_j^{-1} \,\,(1\le i< j\le r) \Bigr.\right>.$ Каждому элементу множества $\Omega_k$ можно сопоставить замкнутую ориентированную ломаную на графе Кэли длины не больше $k$ с началом (и концом) в единице. Сформулируем основной результат главы 2.

В статье [1] М.Громов высказал это утверждение без доказательства (и без ограничения на представление). Кроме того, в части 2.5 доказывается

Результаты главы 2 сданы в печать в Сибирский Математический Журнал (статья Кукиной Е.Г. и Романькова В.А. "Субквадратичность усредненной функции Дена для свободных абелевых групп" ).

1.2.2 Результаты главы 3

В главе 3 будем использовать другое определение эквивалентности функций.

Это определение удобно тем, что позволяет (в отличие от определения 3) выделять функции, меньшие линейных. При испльзовании такого определения функции Дена группы $G$ относительно двух различных представлений $\mathfrak P(G),\,\mathfrak Q(G)$ остаются эквивалентны. Также при использовании этого определения усредненная функция Дена не меняется при замене системы определяющих соотношений. В главе 3 явно вычислена усредненная функция Дена для группы $\Bbb Z_2$ относительно представления $\mathfrak P(\Bbb Z_2)=\bigl<a\bigl\vert a^2\bigr.\bigr>.$ Доказано, что эта функция эквивалентна $\sqrt{k}.$ В части 3.2 доказано следствие. Оно отвечает на вопрос В.Н.Ремесленникова, заданный автору. Пусть свободная абелева группа ранга $r$ задана в стандартном представлении $\mathfrak P(\Bbb Z^r).$ Введем $\Psi_{r,k}$ -- множество слов длины $k$ в алфавите $X_r.$ Определим функцию

$$c_r(k)=\frac{\sum\limits_{\vert w\vert=k} \vert w\vert _{\Bbb Z^r}} {card{\Psi_{r,k}}}.$$

Результаты главы 3 сданы в печать в Вестник Омского Университета (статья Кукиной Е.Г. "Усредненная функция Дена для группы $\Bbb Z_2$").

2. Усредненная функция Дена для свободных абелевых групп

В этой главе излагается доказательство следующей теоремы.

Как следствие этой теоремы получено

2.1 Идея доказательства

Граф Кэли свободной абелевой группы $\Bbb Z^r$ ранга $r$ в ее естественном представлении $\mathfrak P(\Bbb Z^r)$ реализуем как целочисленную решетку в $r$-мерном евклидовом пространстве. Для этого зафиксируем декартову систему координат $Os_1s_2\ldots s_r.$ В начало системы координат поместим вершину графа Кэли, соответствующую единице; ребра, соответствующие порождающему $x_i,$ пустим параллельно оси $Os_i.$ Примечание. Введенная система координат имеет естественный смысл: $(s_1,\ldots , s_r) \leftrightarrow x_1^{s_1}x_2^{s_2}\ldots x_r^{s_r}.$ Мы выделим в пространстве куб $K_N = [-N; N]^r = {\{(s_1,\ldots ,s_r) \vert \ \vert s_i\vert\le N \,\left(1\le i\le r\right)\}},$ для которого величина $N$ будет определена далее, и докажем, что справедливы следующие утверждения. 1. Площадь тех замкнутых ломаных длины $n,$ которые не выходят за границу куба $K_N$ -- $o\left(n^2\right).$ 2. За границу куба $K_N$ выходит "мало" ломаных длины $n,$ то есть отношение числа выходящих за границу замкнутых ломаных длины $n$ к числу всех замкнутых ломаных длины $n$ (или просто вероятность выхода за границу $K_N$ замкнутой $n$-звенной ломаной) есть $o\left( 1 \right).$ Тогда получим следующую оценку: $\sigma(n) \le {o(n^2) p_1}+{C_1 n^2 p_2},$ где $p_1$ -- вероятность того, что ломаная длины $n$ останется в кубе $K_N, p_2$ -- вероятность того, что эта ломаная выйдет за пределы куба $K_N, C_1 n^2$ -- максимальная площадь, которая может быть ограничена замкнутой ломаной с не более чем $n$ звеньями. Отсюда следует $\sigma(n) \le o(n^2)+o(n^2),$ что и требовалось.

2.2 Ограничение площади

Доказательство утверждения. Каждому элементу ${g\in \Bbb Z^r}$ сопоставим "стандартную запись" -- слово $x_1^{s_1}x_2^{s_2}\ldots , x_r^{s_r}.$ Пусть ${w=y_1y_2\ldots , y_n,}$ где $y_i (1\le i\le n)$ - порождающий или обратный к нему элемент. Пусть $w_i$ -- "стандартная запись" элемента $y_1y_2\ldots , y_i$ для всех $0<i<n.$ Для удобства введем еще два пустых слова $w_0$ и $w_n.$ Запишем новое слово, площадь которого, очевидно, равна площади старого: $w'=\Bigl(w_0y_1w_1^{-1}\Bigr) \Bigl(w_1y_2w_2^{-1}\Bigr)\Bigl(w_2\ldots w_{n-1}^{-1}\Bigr) \Bigl(w_{n-1}y_nw_n^{-1}\Bigr).$ Здесь $n$ подслов вида $v_i=w_{i-1}y_iw_i^{-1}.$ Заметим, что $v_i=_{\Bbb Z^r}1.$ Понятно, что $S_w\le\sum S_{v_i}.$ Остается доказать, что $S_{v_i}\le (r-1)N.$ Т.к. у нас $y_i=x_j^{\epsilon},\,\, \epsilon\in\{\pm 1\}.$ Пусть $w_{i-1} = x_1^{s_1}...x_r^{s_r}.$ Распишем подробнее слово

$$v_i = x_1^{s_1}\ldots x_r^{s_r} \cdot x_j^{\epsilon} \cdot x... ...{j+1}}x_j^{-s_j-\epsilon}x_{j-1}^{-s_{j-1}} \ldots x_1^{-s_1}.$$

Очевидно, что $S_{v_i}\le \sum_{t=j+1}^{r}\vert s_t\vert\le (r-j)N\le (r-1)N,$ так как из того, что ломаная лежит в кубе $K_N = \left[-N; N\right]^{r}$ следует, что $\vert s_t\vert\le N.$ Утверждение доказано.

2.3 Ограничение вероятности выхода за куб

Нам понадобится хорошо известная (см. [4])

Говоря 1-мерная ломаная, будем иметь в виду ломаную с вершинами в целых точках числовой прямой, начинающуюся в нуле. На множестве всех 1-мерных ломаных введем классическую вероятностную меру. Вероятность того, что произвольная 1-мерная ломаная с числом звеньев $m$ выйдет за пределы полосы $\{\vert y\vert\le N\},$ не больше, чем $\frac{m}{N^2}.$ Действительно, пусть в лемме Колмогорова $\xi_n$ -- случайная величина, определяющая направление движения $n$-го звена, то есть ${\xi_n=1}$ с вероятностью $\frac12$ и ${\xi_n=-1}$ с вероятностью $\frac12$. Тогда ${M\xi_n=0},\; M\xi^2_n=1,$ и $S_n=\sum\limits_{k=1}^n \xi_k$ -- координата конца $n$-го звена. Дисперсия суммы независимых величин равна сумме их дисперсий, значит $D S_n=n.$ Поэтому за пределы полосы $\{\vert y\vert\le N\}$ выходит не больше, чем $2^m \frac m{N^2}$ ломаных длины $m.$ Обозначим количество замкнутых 1-мерных ломаных длины $m$, выходящих за пределы полосы$\{\vert y\vert\le N\},$ $Z_m,$ а количество всех замкнутых 1-мерных ломаных длины $m$ обозначим $Y_m.$ Тогда $Z_m\le 2^m \frac m{N^2},\,\,Y_m=C_m^{\frac m2}.$ Из формулы Стирлинга $\frac {n!}{\sqrt{2\pi n}\left( \frac ne\right)^n}\to 1$ (см. [5]) следует $Y_m\ge C_0\frac{2^m}{\sqrt m}.$ Вероятность выхода $m$-звенной 1-мерной ломаной за пределы полосы $\{\vert y\vert\le N\}$ равна $\frac{Z_m}{Y_m}\le\frac{m^{\frac32}}{C_0 N^2}.$ Рассмотрим $n$-звенную $r$-мерную замкнутую ломаную. Рассмотрим ее проекцию на $i$-ю координату, получим 1-мерную замкнутую ломаную длины $m\le n.$ Заметим, что количество $r$-мерных ломаных, переходящих в данную 1-мерную ломаную, одинаково для всех 1-мерных ломаных (обозначим это количество $a_m$). Действительно, оставшиеся (ортогональные оси $s_i$) звенья образую $(r-1)$-мерную $(n-m)$-звенную замкнутую ломаную и звенья двух ломаных (1-мерной и $(r-1)$-мерной) перемешаны в произвольном порядке (совершенно не зависящем от звеньев этих ломаных). Пусть $P_{n,N}$ -- вероятность того, что $n$-звенная $r$-мерная замкнутая ломаная выйдет за пределы полосы $\{\vert s_i\vert\le N\}.$ Тогда $P_{n,N}=\frac{\sum_{m=0}^n a_m Z_m}{\sum_{m=0}^n a_m Y_m}.$ Заметим, что $a_m Z_m\le a_mY_m\frac{m^{\frac32}}{C_0 N^2}\le a_mY_m \frac{n^{\frac32}}{C_0 N^2}.$ Таким образом, $P_{n,N}\le \frac{n^{\frac32}}{C_0 N^2}.$ Заметим, что количество ломаных, выходящих за $r$-мерный куб $K_N = [-N;N]^r,$ меньше суммы количеств ломаных, выходящих за пределы отрезка $[-N;N]$ по одной координате (т.к. бывают ломаные, которые выходят за пределы этого отрезка по нескольким координатам). Так как все координаты равноправны, вероятность того, что $n$-звенная замкнутая ломаная выйдет за пределы $r$-мерного куба $K_N$ не больше, чем $rP_{n,N}.$

2.4 Окончание доказательства теоремы

Площадь слова длины $n$ не превосходит $C_1 n^2.$ Тогда

$$\delta(n)\le (r-1)Nn+r\frac {C_1 n^{\frac72}}{C_0N^2.}$$

Положим $N=n^{\frac 56}.$ Тогда $\delta(n)\le \left(r-1+r \frac{C_1}{C_0}\right) n^{\frac {11}6}=C n^{\frac {11}6}.$ Тогда $\sigma(n)=\sum\limits_{i=1}^n p^{(i)}\delta(i),$ где $p^{(i)}$ -- вероятность того, что ломаная из $\Omega_n$ имеет длину $i.$ Следовательно, $\sigma(n)\le C n^{\frac {11}6}.$ Теорема доказана.

2.5 О некоторых плоских кристаллографических группах

Известно [8], что порядок функции Дена не меняется при конечных расширениях. Следовательно, любое конечное расширение свободной конечно порожденной абелевой группы имеет квадратичную функцию Дена. В частности, плоские кристаллографические группы, которые являются конечными расширениями $\mathbb Z^2,$ имеют квадратичную функцию Дена. В этой части статьи рассмотрим группы $G$ с такой системой порождающих $X$, что граф Кэли $\Gamma(G,X)$ соответствует одному из регулярных замощений плоскости (правильными треугольниками, квадратами или шестиугольниками). Все такие группы -- плоские кристаллографические. Согласно классической теореме Федорова, всего существует 17 плоских кристаллографических групп. Четырнадцать из них в некоторой системе порождающих имеют один из указанных графов Кэли, оставшиеся три -- нет (см. [6]). Эти три группы (в обозначениях из [7]):

$$p4m=\left<r_1, r_2, r_3\Bigl\vert r_1^2,r_2^2, r_3^2, (r_1r_2)^4, (r_2r_3)^4,(r_3r_1)^2\Bigr.\right> ;$$

$$p31m=\left<r,s \Bigl\vert s^3, r^3, (s^{-1}rsr)^3\Bigr.\right>;$$

$$p6m =\left<r_1, r_2, r_3\Bigl\vert r_1^2,r_2^2, r_3^2, (r_1r_2)^3, (r_2r_3)^6,(r_3r_1)^2\Bigr.\right>.$$

Примерами групп, графы Кэли которых являются регулярными замощениями плоскости, могут служить группы (см. [6]):

• $\mathfrak P \left(G\right)=\left<a, b \bigl\vert a^4, b^4, (ab)^2 \bigr.\right>$ -- граф Кэли этой группы изображается квадратами.
• $\Bbb Z_2, \, \mathfrak P\left(\Bbb Z_2\right)=\left<a, b \bigl\vert aba^{-1}b^{-1} \bigr.\right>$ -- граф Кэли этой группы тоже изображается квадратами.
• $\mathfrak P\left(G\right)=\left<a, b, c \bigl\vert a^3, b^3, c^3, abc \bigr.\right>$ -- граф Кэли этой группы изображается треугольниками.
• $\mathfrak P\left(G\right)=\left<a, \varphi \bigl\vert aa\varphi a^{-1}a^{-1}\varphi, \varphi^2\bigr.\right>$ -- граф Кэли этой группы изображается шестиугольниками.

Выберем определяющие соотношения в этих группах следующим образом. Возьмем все слова, которые соответствуют обходам одной клетки (т.е. квадратика, треугольника или шестиугольника), с началом и концом в единице. Например, для группы $\Bbb Z^2$ с графом Кэли, соответствующим квадратам, определяющими словами будут $aba^{-1}b^{-1}, b^{-1}aba^{-1}, a^{-1}b^{-1}ab, ba^{-1}b^{-1}a.$ (Правда в данном примере все эти соотношения получились эквивалентны, поэтому можно оставить только одно из них.) При таком выборе определяющих соотношений легко огранчить площадь слова, представленного замкнутой ломаной. Если ломаная простая (или "петля"), то ее площадь не больше количества клеток, заключенных внутри нее. Если же ломаная не простая, то она распадается на несколько "петель" и несколько "хвостов" (произвольным образом). Площадь такой ломаной не больше суммы количеств клеток, ограниченых каждой "петлей". Как было показано в части 1.1, усредненная функция Дена не зависит от выбора определяющих соотношений. Поэтому дальше будем подразумевать, что определяющие соотношения выбраны именно таким образом.

Доказательство утверждения похоже на доказательство основной теоремы в случае ${k=2.}$ Во-первых, введем систему координат Oxy. Начало координат выберем в вершине графа Кэли, соответствующей единице группы. Для квадратов -- оси идут вдоль сторон квадрата. Для треугольников -- одна ось (Ox) идет вдоль стороны треугольника, а другая (Oy) перпендикулярно ей (по медиане того треугольника, стороны которого не лежат на оси Ox). Единичные отрезки на осях отметим при первом пересечении осей с решеткой. (Т.е. для треугольников масштабы разные!) Для шестиугольников: "дорисовываем" замощение до замощения из треугольников и вводим числовые оси в точности так же, как это было введено для треугольников. Ось $Ox$ будем называть горизонтальной, а ось $Oy$ - вертикальной. Во-вторых, ограничим площадь ломаных, заключенных в квадрате $\{\vert x\vert\le N, \vert y\vert\le N\}.$ Если замкнутая ломаная имеет длину $n$ и не выходит за пределы квадрата $\{\vert x\vert\le N, \vert y\vert\le N\},$ то ее площадь не превосходит $C^*nN.$ В случае "квадратов" "стандартной записью" элемента $g$ будет слово, прочитанное сначала вдоль оси $Ox,$ а потом вдоль оси $Oy.$ Понятно, что ограничение $S_w\le nN$ доказывается аналогично доказательству в пункте 2.2. В случае "треугольников" "стандартной записью" элемента $g$ будет слово, прочитанное сначала по тем ребрам графа Кэли, которые лежат на прямой, находящейся под углом $\frac{\pi}6$ с осью $Ox$, а потом вдоль оси $Ox.$ Тогда легко доказывается неравенство $S_w\le 2nN.$ Ломаную на графе из шестиугольников рассматриваем как частный случай ломаной на графе из треугольников, причем на графе из шестиугольников у нее площадь меньше (в 6 раз), чем на графе из треугольников. Т.е. неравенство $S_w\le 2nN$ также справедливо. В-третьих, ограничим вероятность выхода за квадрат ${\{\vert x\vert\le N, \vert y\vert\le N\}.}$ Понятно, что для групп с "квадратным" графом Кэли все аналогично группе $\Bbb Z^2.$ Рассмотрим группы с "треугольным" или "шестиугольным" графом Кэли. Заметим, что вероятность того, что замкнутая ломаная выйдет за пределы квадрата $\{\vert x\vert\le N, \vert y\vert\le N\},$ меньше, чем вероятность того, что ломаная выйдет за пределы шестиугольника

$$\left\{ (N,0), (\frac{N}2,N),(-\frac{N}2,N),(-N,0),(-\frac{N}2,-N), (\frac{N}2,-N)\right\}.$$

(Т.к. если она вышла за квадрат, то она тем более вышла за шестиугольник.) А эта вероятность не превосходит суммы вероятностей выхода за полосы $\left\{\vert y\vert\le N\right\}$ и двух полос, полученных из нее поворотом на $\frac{\pi}3, \frac{2\pi}3$ (стороны этих трех полос в точности идут по параллельным сторонам шестиугольника). (Т.к. могут быть такие ломаные, которые выходят за пределы нескольких из этих полос.) Поскольку эти полосы симметричны, вероятности выхода за них одинаковы. Значит, вероятность того, что ломаная выйдет за пределы квадрата $\{\vert x\vert\le N, \vert y\vert\le N\},$ не превосходит утроенной вероятности того, что ломаная выйдет за пределы полосы $\{\vert y\vert\le N\}.$ Повторяя рассуждения из пунктов 2.3 и 2.4, завершаем доказательство утверждения.

3. Усредненная функция Дена для группы $\Bbb Z_2$

3.1 Вычисление усредненной функции Дена для группы $\Bbb Z_2$

Посчитаем точную усредненную функцию Дена $\delta(k)$ для группы $\mathbb Z_2$. Пусть $S_k$ -- случайная величина, площадь случайного слова длины $k$. Понятно, что $\delta(k)=\mathbb M(S_k)$. По формуле полной вероятности

$$\mathbb M(S_{k+2})= \mathbb M\left(\mathbb M(S_{k+2}\vert S_k)\right) =$$

здесь $S_k$ -- площадь слова, состоящего из $k$ последних букв исходного слова длины $k+2.$ Продолжаем равенство, применив формулу полной вероятности

$$= \mathbb M(S_{k+2}\vert S_k=0)\cdot P_{k,0}+ \mathbb M\left... ...(S_k\left\vert S_k\ne 0\right.\right))\right)\cdot (1-P_{k,0})=$$

здесь $P_{k,0}$ -- вероятность того, что ломаная длины $k$ имеет площадь 0. Продолжаем равенство. Учитываем, что первые две буквы с вероятностью $\frac12$ дают дополнительную площадь 0, с вероятностью $\frac14$ добавляют к площади единицу и с вероятностью $\frac14$ уменьшают площадь на 1.

${= \frac12 P_{k,0} + (1-P_{k,0}) \cdot \left( \frac12\mathbb M(S_k\vert S_k\n... ...0)\right)} = \frac12 P_{k,0} + (1-P_{k,0}) \cdot \mathbb M(S_k\vert S_k\ne 0).$

Очевидно, что $p(S_k=S\vert S_k\ne 0)=\frac{p(S_k=S)}{1-P_{k,0}}.$ Поэтому $\mathbb M(S_k\vert S_k\ne 0)=\frac{\mathbb M(S_k)}{1-P_{k,0}}.$ Окончательно получаем

$$\delta(k+2)=\frac12 \cdot P_{k,0}+\delta(k).$$ (3.1)

Заметим, что $\delta(2)=\frac12,$ а $P_{k,0}=\frac{C^k_{2k}}{2^{2k}}.$ Таким образом мы полностью вычислили функцию $\delta(k).$ Чтобы определить ее поведение, используем формулу Стирлинга (см. [5]). Получим, $\frac{D}{2\sqrt{\pi k}}\le P_{k,0}\le \frac{C}{2\sqrt{\pi k}},$ где $C,D$ -- некоторые положительные постоянные. Понятно, что $\delta(k)$ имеет смысл только при четных $k.$ Для $k=2l$ имеем

$\delta(2l+2)=\frac12\sum\limits_{t=1}^l P_{2t,0} +\delta(2)\le \frac12\sum\limits_{t=1}^{l}\frac{C}{2\sqrt{2\pi t}} +\frac12.$

Аналогично

$\delta(2l+2)\ge \frac12\sum\limits_{t=1}^l\frac{D}{2\sqrt{2\pi t}} +\frac12.$

Заметим, что $\sum\limits_{t=1}^l\frac1{2\sqrt{2\pi t}}$ -- нижняя сумма Дарбу для $\int\limits_{0}^l \frac{dt}{2\sqrt{2\pi t}}=\sqrt{\frac{l}{2\pi}}.$ Следовательно, $\sum\limits_{t=1}^l\frac1{2\sqrt{2\pi t}} \le\sqrt{\frac{l}{2\pi}}.$ Следовательно,

$$\delta(k+2)\le \frac C 2\sqrt{\frac k{4\pi}}+\frac12.$$

Заметим также, что $\sum\limits_{t=1}^l\frac1{2\sqrt{2\pi t}}$ -- верхняя сумма Дарбу для $\int\limits_{1}^{l+1} \frac{dt}{2\sqrt{2\pi t}}= \sqrt{\frac{l+1}{2\pi}}-\frac1{\sqrt{2\pi}}.$ Следовательно,

$$\delta(k+2)\ge \frac D2\sqrt{\frac {k+2}{4\pi}}-\frac D{2\sqrt{2\pi}} +\frac12.$$

Получили $\delta(k)$ эквивалентна $\sqrt k$. Докажем, что функции $\delta(k)$ и $\sigma(k)$ эквивалентны. Заметим, что

$$\sigma(2k)=\frac{ \sum\limits_{t=1}^k 2^{2t} \delta(2t)}{\frac 43 \left(2^{2k}-1\right) },$$

т.к. $card{\Delta_{2k}}=2^{2k}, card{\Omega_{2k}}=\sum\limits_{t=1}^k 2^{2t} = \frac43\left(2^{2k}-1\right).$ Из (3.1) следует, что $\delta(k)$ возрастает. Поэтому

$$\sigma(2k)\le\delta(2k).$$

Очевидно также, что

$$\sigma(2k)\ge\frac{3\cdot 2^{2k}\delta(2k)}{4\cdot\left(2^{2k}-1\right)}\ge \frac 34 \delta (2k).$$

Получили, что $\delta(k)$ эквивалентна $\sigma(k)$ и $\sqrt k.$ Значит, функции $\sigma(k)$ и $\sqrt k$ эквивалентны.

3.2 Сокращения в свободной абелевой группе

Докажем следствие 1, заявленное во введении. Вначале рассмотрим свободную абелеву группу ранга 1. Пусть $w$ -- произвольное слово длины $2k$ алфавита $X_1.$ Понятно, что $\vert w\vert _{\Bbb Z}$ равна удвоенной площади слова $w$ в группе $Z_2$ относительно представления $\mathfrak P(\Bbb Z_2)=\bigl<a\bigl\vert a^2\bigr.\bigr>.$ Получаем, что $c_1(2k)=2\delta_{Z_2}(2k).$ Кроме того, очевидно $c_1(2k)-1\le c_1(2k+1)\le c_1(2k)+1.$ Отсюда следует, что функция $c_1(k)$ эквивалентна $\sqrt{k}.$ Далее доказательство ведем методом математической индукции. Пусть следствие доказано для свободных абелевых групп рангов меньше $r$. Докажем его для группы $\Bbb Z^r.$ Пусть $w$ -- произвольное слово длины $k$ алфавита $X_r$. В этом слове $l_1$ букв $x_1$ и $l_2$ букв $x_2,\ldots x_r$ ($l_1+l_2=k$). Пусть $w_1$ -- слово, полученное из $w$ опусканием букв $x_2\ldots x_r,$ а $w_2$ -- слово, полученное из $w$ опусканием букв $x_1.$ Заметим, что $\vert w\vert _{\Bbb Z^r}=\vert w_1\vert _{\Bbb Z}+\vert w_2\vert _{\Bbb Z^{r-1}}.$ Зафиксируем буквы $x_2\ldots x_r,$ а вместо букв $x_1$ будем подставлять по очереди все слова длины $l_1$ от буквы $x_1.$ Получили семейство слов, среднее значение функции $\vert\cdot\vert _{\Bbb Z}$ для которых равно $c_1(l_1) +\vert w_2\vert _{\Bbb Z^{r-1}}.$ Теперь во всех словах этого семейства будем фиксировать буквы $x_1,$ а вместо букв $x_2\ldots x_r$ подставлять всевозможные слова длины $l_2$ от букв $x_2\ldots x_r.$ У полученного множества $\Psi_{r,k,w}$ среднее значение функции $\vert\cdot\vert _{\Bbb Z^r}$ равно $c_1(l_1)+c_{r-1}(l_2).$ По предположению индукции получаем $A\sqrt l\ge c_1(l), c_{r-1}(l)\ge B\sqrt l.$ Далее, ${2A\sqrt k} \ge {A\left(\sqrt{l_1}+\sqrt{l_2}\right)} \ge {c_1(l_1)+c_{r-1}(l_2)} \ge {B\left(\sqrt{l_1}+\sqrt{l_2}\right)}\ge {B\sqrt k}.$ Первое неравенство верно в силу возрастания функции $\sqrt k,$ а последнее в силу ее выпуклости вверх (вогнутости). Так как множество $\Psi_{r,k}$ распадается на множества вида $\Psi_{r,k,w},$ то среднее значение функции $\vert\cdot\vert _{\Bbb Z^r}$ на множестве $\Psi_{r,k}$ (т.е. функция $c_r(k)$) будет удовлетворять тем же неравенствам, а именно

$$2A\sqrt k \ge c_r(k)\ge B\sqrt k.$$

Т.е. функции $\sqrt{k}$ и $c_r(k)$ эквивалентны. Что и требовалось.

4. Усредненная функция Дена для группы $\Bbb Z_p$

4.1 Количество единичных слов для группы $\mathbb Z_p.$

Посчитаем $N_n$ -- количество слов длины $n,$ записывающих единицу в группе $\mathbb Z_p=<a>.$ Обозначим через $A_{n,k}$ количество слов длины $n,$ записывающих единицу в группе $Z_p$ и начинающихся на $k$ букв $a\,\, (1\le k\le n)$ и через $A'_{n,k}$ количество слов длины $n,$ записывающих единицу в группе $Z_p$ и начинающихся на $k$ букв $a,$ за которыми следует буква $a^{-1}\,\, (1\le k<n).$ По определению возьмем $N_0 = 1.$ Понятно, что

$$A_{n,1}=\frac12 N_n,$$

$$A'_{n,k}=A_{n-2,k-1},$$

$$A_{n,k+1}= A_{n,k}-A'_{n,k}=A_{n,k}-A_{n-2,k-1}.$$

Докажем методом математической индукции, что

$$A_{n,k}=\frac12 \left(\sum\limits_{i=0}^{\left[\frac k2\right]} (-1)^i C_{k-i}^i \frac k{k-i} N_{n-2i}\right).$$ (4.1)

При $k=1$ равенство обращается в $A_{n,1}=\frac12 N_n,$ а это верно $\forall n\ge 1$. При $k=2$ равенство обращается в $A_{n,2}=\frac12 N_n - N_{n-2} = A_{n,1}- A_{n-2,0},$ что верно $\forall n\ge 2$. Пусть для всех $n< n_0$ равенство верно $\forall k\le n$, а при $n=n_0$ равенство верно для всех $k<k_0.$ Докажем, что равенство верно при $n=n_0, k=k_0.$

$A_{n_0,k_0}=A_{n_0,k-1}-A_{n_0-2, k_0-2}=\frac12 \left(\sum\limits_{i=0}^ {... ...}2\right]} (-1)^j C_{k_0-2-j}^j \frac {k_0-2}{k_0-2-j} N_{n_0-2-2j}\right) =$

Во второй скобке введем новый индекс суммирования ${i=j+1,}$ он будет меняться от $1$ до $\left[\frac {k_0}2\right]$ и слагаемое примет вид: $(-1)^{i+1} C_{k_0-1-i}^{i-1} \frac {k_0-2} {k-1-i} N_{n_0-2i}.$ С учетом минуса перед вторым слагаемым, сгруппируем слагаемые из разных скобок с одинаковым индексом. Продолжаем равенство:

$= \frac12 N_n +\frac12 \left(\sum\limits_{i=1}^{\left[\frac {k_0-1}2\right]}... ...\cdot C_{k_0-1-i}^i +\frac{k_0-2}{k_0-1-i} C_{k_0-1-i}^{i-1}\right)\right) +$

+ если $\left[\frac {k_0}2\right]\ne\left[\frac {k_0-1}2\right],$ надо добавить еще одно слагаемое: $(-1)^{\frac{k_0}2}N_{n_0-k_0}.$ Посчитаем $\frac{k_0-1}{k_0-i-1}\cdot C_{k_0-1-i}^i +\frac{k_0-2}{k_0-1-i} C_{k_0-1-i}^{i-1}= \frac{k_0}{k_0-i} C_{k_0-i}^i.$ На этом доказательство завершается. Заметим, что для группы $\mathbb Z_p\,\, A_{n,p}=N_{n-p}.$ Т.е.

$$N_{n-p}=\frac12 \left(\sum\limits_{i=0}^{\left[\frac p2\right]} (-1)^i C_{p-i}^i \frac p{p-i} N_{n-2i}\right),$$

или

$$N_n=\sum\limits_{i=1}^{\left[\frac p2\right]} (-1)^{i+1} C_{p-i}^i \frac p{p-i} N_{n-2i}+2N_{n-p}.$$ (4.2)

Таким образом получили линейное выражение для $N_n$ через $p$ предыдущих членов этой последовательности. Из общей теории о последовательностях с линейными рекуррентными соотношениями с постоянными коэффициентами (см. [12]) следует, что

$$N_n=\sum\limits_k p_k(n)q_k^n,$$ (4.3)

где $q_k$ -- различные корни характеристического уравнения

$$\sum\limits_{i=0}^{\left[\frac p2\right]} (-1)^{i} C_{p-i}^i \frac p{p-i} x^{p-2i}-2=0,$$ (4.4)

и если кратность корня $q_k - i_k,$ то $p_k(n)$ -- многочлен степени $i_k-1.$ Коэффициенты многочленов находятся из линейной системы уравнений, которую строим по $p$ начальным членам данной последовательности. В нашем случае первые $p$ членов таковы: $N_0=1, N_{2k+1}=0, N_{2k}=C_{2k}^k.$

4.2 Точная усредненная функция Дена для $\mathbb Z_p.$

Обозначим $S(n,k)$ суммарную площадь слов длины $n,$ записывающих единицу и начинающихся на $k$ букв $a,$ $S'(n,k)$ суммарную площадь слов длины $n,$ записывающих единицу, начинающихся на $k$ букв $a$ за которыми следует $a^{-1}.$ Понятно, что $S(n,k)=S(n,k-1)-S'(n,k-1),$ $S'(n,k)=S(n-2,k-1),$ $S(n,0)=S_n=\delta(n)\cdot N_n, S(n,1)=\frac12 S_n.$ Заметим, что $\delta(n,p)=P_{n-p,0}+\delta(n-p),$ где $P_{n,0}$ -- вероятность того, что слово длины $n$ имеет площадь 0 (рассуждения аналогичные рассуждениям для группы $\mathbb Z_2$ из части 3.1.) Т.к. возвратные формулы получились аналогичны формулам из части 4.1, по индукции замечаем, что если $N_n=\sum\limits_{k=1}^p c_k N_{n-k},$ то ${\delta(n)=\sum\limits_{k=1}^p c_k \frac{N_{n-k}}{N_n}\delta(n-k)+ \frac{2N_{n-p}}{N_n} P_{n-p,0}.}$

4.3 Некоторые предельные замечания

Заметим, что для четного $p$ характеристический многочлен -- четная функция, и, следовательно, вместе с корнем $2$ у него есть корень $-2$. Заметим, что у характеристического многочлена для нечетного $p$ корня $-2$ нет, а корень $2$ -- кратности 1, т.к. свободный член характеристического многочлена равен $2$. Предположим, что у характеристического многочлена нет корней из множества $\left\{q\bigl\vert \vert q\vert\ge 2, q\ne\pm2\bigr.\right\}$, а корни $2$ и $-2$ не более чем первой кратности. При нечетном $p$ $N_n=(c+\alpha(n))2^n,$ где $\alpha(n)\to 0$ при $n\to \infty.$ Тогда из равенства (4.1) следует, что $A_{n,k}= (c+\beta_k(n))2^{n-k},$ где $\beta(n)\to 0$ при $n\to \infty$ (т.к. двойка является корнем характеристического уравнения для любого $p$). Заметим, что слов длины $n,$ записывающих элемент $a^{-k}$ ровно столько, сколько слов длины $n+k,$ записывающих единицу и начинающихся на $k$ букв $a,$ т.е. $A_{n+k,k}= (c+\beta_k(n+k)) 2^n.$ Пусть $P_{n,g}$ -- вероятность того, что слово длины $n$ равно $g.$ Теперь понятно, что $c\ne 0.$ Если бы $c$ было равно 0, то $\lim\limits_{n\to\infty}\sum\limits_{k=0}^{p-1} P_{n,a^k} =0,$ а это не так. Т.е. на бесконечности все элементы группы $\mathbb Z_p$ записываются одинаковым количеством слов длины $n,$ т.е. выполнено условие

$$\forall g\in\mathbb Z_p \lim\limits_{n\to\infty}\frac{P_{n,0}}{P_{n,g}}=1.$$

В частности, из этого следует, что коэффициент при $2^n$ в записи $N_n$ равен $\frac1p.$ Пусть $p$ четно. Заметим, что элементы $\Bbb Z_p$ вида $g=a^{2k+1}$ записываются только словами нечетной длины, а элементы вида $g=a^{2k}$ только словами четной длины. Тогда аналогично доказывается,

$$\forall g\in\mathbb Z_p,\, g=a^{2k} \lim\limits_{n\to\infty}\frac{P_{2n,0}}{P_{2n,g}}=1$$

$$\forall g\in\mathbb Z_p,\, g=a^{2k+1} \lim\limits_{n\to\infty}\frac{P_{2n+1,a}}{P_{2n+1,g}}=1.$$

В частности, из этого следует, что коэффициенты при $2^n$ и $(-2)^n$ в записи $N_n$ равны $\frac1p.$ Тем самым было доказано



Действительно, характеристический многочлен

$$F_{p}(x)=\left(\sum_{j=0}^{\left[\frac p2\right]} (-1)^j\frac{p}{p-j}C_{p-j}^j x^{p-2j}\right) -2$$ (4.5)

при четном $p$ раскладывается в произведение вида

$$F_{p}(x)=\left(x^2-4\right){G_{\frac p2-1}(x)}^2,$$ (4.6)

где

$$G_{p}(x)=\left(\sum_{j=0}^{\left[\frac p2\right]} (-1)^j C_{p-j}^j x^{p-2j}\right).$$

Это нетрудно доказать методом математической индукции (рассуждение похоже на рассуждение на стр. ?). Заметим, что

$$pG_p(x)=\frac d{dx} F_{p+1}(x).$$ (4.7)

Из (4.6) и (4.7) по индукции, учитывая тот факт, что корни производной многочлена лежат внутри выпуклой оболочки корней многочлена, легко понять, что многочлен (4.5) при $p=2^t$ не имеет корней из множества $\left\{q\bigl\vert \vert q\vert\ge 2, q\ne\pm2\bigr.\right\}$, а корни $2$ и $-2$ не более чем первой кратности.

У автора есть гипотеза, что этому условию удовлетворяют все многочлены $F_p(x).$ Она пока не доказана.

5. Заключение

Определение усредненной функции Дена дал М.Громов в работе [1] в 1993 году. До сих пор усредненная функция Дена остается мало изученным объектом. Автор не знает публикаций об этой функции. Ясно, что у усредненной функции Дена есть много свойств, неприсущих функции Дена. Например, функция Дена монотонно возрастает, а усредненная функция Дена бывает немонотонна (например, для группы $\Bbb Z_3=<a>$ ${\sigma(3)=\frac12,} {\sigma(4)=\frac 15,} {\sigma(5)=\frac35}$). Неизвестно, зависит ли усредненная функция Дена от представления группы или нет. Если зависит, то как? Ограничение сверху на усредненную функцию Дена для свободных абелевых групп получено, а ограничения снизу нет. Хорошо бы определить ее с точностью до эквивалентности функций. Возможно ли теорему, подобную теореме 1 доказать для автоматных групп? Возможно ли доказать сублинейность усредненной функции Дена для гиперболических или хотя бы для конечных групп? (Как это удалось сделать для группы $\Bbb Z_2$.) Можно ли доказать то, что $\lim\limits_{k\to\infty}\frac{D(k)}{\sigma(k)}=0$ для всех групп? Ответы на эти вопросы неизвестны.

Bibliography

1

M.Gromov, "Asymptotic invariants of infinite groups", in Geometric Group Theory. LMS Lecture Notes, 182 eds. G.A.Niblo and M.A.Roller, Cambridge Univercity Press 1993.

2

B.Bouditch, "A short proof that a subquadratic isoperimetric inequality implies a linear one","Michigan J. Math.", 1995,V.42, p.103-107.

3

A.Yu.Ol'shanskii, "Hyperbolicity of groups with subquadratic isoperimetric inequality", Int. J. Alg. and Comput. 1 (1991), p.281-290.

4

Дж.Ламперти, "Вероятность", М.: Наука, 1973г.

5

В.Феллер, "Введение в теорию вероятностей и ее приложение", Т.1, М.: Мир, 1984г.

6

Беленкова Ж.Т., Романьков В.А. "Регулярные графы Кэли", Сиб. мат. ж., деп. в ВИНИТИ,1997,т.802-B97,с.37.

7

Коксетер Г.С.М., Мозер У.О.Дж. Порождающие элементы и определяющие соотношения дискретных групп: Пер. с англ./Под ред. Ю.И.Мерзлякова, М.: Наука, Главная редакция физико-математической литературы,1980.

8

Epstein D.B.A., Cannon J.W., Holt D.F., Levy S.V.F, Paterson M.S. and Thurston W.P. "Word Processing in Groups", Jones and Bartlett, Boston M.A.,1992

9

Papasoglou P., "On the subquadratic isoperimetric inequality", in Geometric Group Theory. Walter de Gruyter. Berlin - New-York, 1995, p.149-158

10

Лысенок И.Г., "О некоторых алгоритмических свойствах гиперболических групп", Изв. АН СССР, сер. мат. Т.53, №4, 1989г. стр.814-832

11

Громов М., "Гиперболические группы", Ижевск: Институт компьютерных исследований, 2002.

12

Виленкин Н.Я., Комбинаторика, М.: Наука, Главная редакция физико-математической литературы,1969.

13

Спивак М. Восхитительный TEX, М.: Мир, 1993.

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -white -show_section_numbers diplom.tex

The translation was initiated by root on 2003-06-24.