\documentstyle{SibMatJ}
% \TestXML
\Rus
\topmatter

  \Author             Gubarev
    \Initial          V.
    \Initial          Yu.
    \ORCID            0000-0002-7839-5714
    \Email            wsewolod89\@gmail.com
    %\Email           vsevolodgu@math.nsc.ru
    %\Email           vsevolodgu@mail.ru
    \AffilRef         1
    \AffilRef         2
  \endAuthor

  \Author             Zheng
    \Initial          Z.
    \Sign             Zhang Zheng %\?сама написала
    \Email            2268663734\@qq.com
    \AffilRef         2
  \endAuthor

  \Affil 1
    \Organization     Sobolev Institute of Mathematics
    \City             Novosibirsk
    \Country          Russia
  \endAffil

  \Affil 2
    \Organization     Novosibirsk State University
    \City             Novosibirsk
    \Country          Russia
  \endAffil

  \opages
    ???--???
  \endopages

  \datesubmitted      July 7, 2025\enddatesubmitted
  \daterevised        December 13, 2025\enddaterevised
  \dateaccepted       December 20, 2025\enddateaccepted

  \UDclass
    512.554.38 %17A30
  \endUDclass

  \thanks
    Работа выполнена в рамках государственного задания ИМ СО РАН, тема FWNF--2026--0017.
    %The work was carried out in the framework of the State Task to the Sobolev Institute of Mathematics (project FWNF--2026--0017).
  \endthanks

  \title
    Универсальная обертывающая алгебры $n$ согласованных скобок Ли
  \endtitle

  \abstract
    Изучается (мультипликативная) универсальная обертывающая алгебра
    в смысле В.~Гинзбурга и М.~Капранова $U({\goth g})$ алгебры ${\goth g}$
    набора $n$ согласованных скобок Ли.
    При помощи базисов Гребнера~--- Ширшова найден базис алгебры $U({\goth g})$.
    Найдена асимптотика скорости роста алгебры~$U({\goth g})$ при $n$, $\dim {\goth g}\gg1$.
  \endabstract

  \keywords
    универсальная мультипликативная обертывающая алгебра,
    алгебра Ли согласованных скобок,
    скорость роста, базис Гребнера~--- Ширшова
  \endkeywords

\endtopmatter
\input epsf
\input gutable

\head  %\?все параграфы без нумерации. Если решите сделать \specialhead, то заготовила
Введение
\endhead
%\specialhead Введение \endspecialhead

Алгебра $\langle L,[\cdot,\cdot]_1,[\cdot,\cdot]_2\rangle$ над полем $\Bbbk$
принадлежит многообразию $\operatorname{Lie}_2$ пар согласованных скобок Ли, если
$\alpha [\cdot,\cdot]_1 + \beta [\cdot,\cdot]_2$ есть скобка Ли
для любых $\alpha,\beta\in \Bbbk$.
Аналогично определяется многообразие $\operatorname{Lie}_n$ алгебр
$\langle L,[\cdot,\cdot]_1,\dots,[\cdot,\cdot]_n\rangle$
$n$ согласованных скобок Ли.
Свободные алгебры в многообразии $\operatorname{Lie}_2$ исследовались в~работах~[1--3].
Кожулевость операды, соответствующей многообразию $\operatorname{Lie}_2$,
была показана в~[4].

В~1994 г. В.~Гинзбург и М.~Капранов~[5]
определили так называемую (мультипликативную) универсальную обертывающую
ассоциативную алгебру~$U(A)$ данной алгебры~$A$.
Ключевое свойство такой обертывающей заключается в~том, что категория модулей
над~$A$
и~категория левых модулей над $U(A)$ эквивалентны.

В~2022 г. А. Хорошкин активно исследовал~[6] универсальную
мультипликативную обертывающую алгебру в~смысле Гинзбурга и Капранова,
получив ее явное задание в~терминах порождающих и соотношений.
Там же А.~Хорошкин установил, что универсальная мультипликативная
обертывающая алгебра
$U_{\operatorname{Lie}_2}({\goth g})$
алгебры ${\goth g}$, принадлежащей многообразию $\operatorname{Lie}_2$
пар согласованных скобок Ли, удовлетворяет свойству Пуанкаре~--- Биркгофа~---
Витта.
Последнее означает, в~частности, что базис
$U_{\operatorname{Lie}_2}({\goth g})$
не зависит от обеих скобок Ли, заданных на ${\goth g}$.
В~работе 2022 г.~[7] В.Ю.~Губарев при помощи техники базисов
Гребнера~--- Ширшова нашел базис алгебры
$U_{\operatorname{Lie}_2}({\goth g})$
и~вычислил ее скорость роста как $m+1$, где
$m = \dim{\goth g}$.

В~работе при помощи базисов Гребнера~--- Ширшова найден базис алгебры
$U_{\operatorname{Lie}_n}({\goth g})$ для произвольного $n$.
Обозначим $m = \dim {\goth g}$.
При помощи частично коммутативных алгебр показано, что при $n,m\gg1$
скорость роста алгебры $U_{\operatorname{Lie}_n}({\goth g})$ асимптотически
равна
$\alpha nm$, где $\alpha = \frac{4}{q_0^2} \approx 0{.}69166$,
$q_0$~--- наименьший корень функции $J_0(2\sqrt{x}) = 0$,
а~$J_0(z)$~--- функция Бесселя первого рода.

\head
Основные сведения о~базисах Гребнера~--- Ширшова
\endhead
%\specialhead Основные сведения о~базисах Гребнера~--- Ширшова \endspecialhead

Пусть $X$ непусто, порядок $\leq$, заданный на множестве $X^*$
всех слов в~алфавите $X$, называется {\it мономиальным}, если из
$u\leq v$ следует
$wu\leq wv$ и $uw\leq vw$ для любого $w\in X^*$.

Пусть $(X,\leq)$ вполне упорядочено.
Зададим на $X^*$ порядок следующим образом:
$u = x_1\dots %\?в таких случаях, возможно, надо \cdots
x_n<v=y_1\dots y_m$,
если и только если
$n<m$ или $n=m$ и найдется $i$ такое, что
$x_i<y_i$, а $x_j=y_j$ для всех $j<i$.
Полученный порядок называется порядком deg-lex, и он мономиален.

Зафиксируем некоторое множество $X$ и мономиальный порядок $\leq$
на множестве $X^{*}$ такой, что $(X^{*}, \leq)$ является
вполне упорядоченным множеством.

Через $\operatorname{As}(X)$ будем обозначать свободную ассоциативную алгебру,
порожденную множеством~$X$.
Пусть $f \in \operatorname{As}(X)$~--- ассоциативный некоммутативный
многочлен от~$X$,
$f \neq 0$. Обозначим через
$\overline{f} \in  X^{*}$
старшее слово многочлена $f$~--- самое большое $u \in X^{*}$,
входящее в~$f$ с~ненулевым коэффициентом.
Многочлен~$f$ называется {\it унитарным},
если старшее слово $\overline{f}$
входит в~него с~коэффициентом, равным единице.

Свойство мономиальности порядка обеспечивает равенство
$\overline{fg} %\? набор должен быть одинаковый, наверное. Но, скорее всего, это разные вещи
= \overline{f}\overline{g} %\? набор должен быть одинаковый, наверное
\in X^{*}$
для любых ненулевых $f, g \in \operatorname{As}(X)$.

Пусть $S \subset \operatorname{As}(X)$~--- некоторое множество унитарных
многочленов.
Слово $u \in X^{*}$ называется
{\it редуцированным относительно\/} $S$,
если $u$ нельзя представить в~виде
$u = u_{1}\overline{f}u_{2}$
ни для каких $u_{1}, u_{2} \in X^{*}$, $f \in S$.

\demo{Definition 1}
Пусть $f$ и $g$~--- унитарные многочлены в~$\operatorname{As}(X)$,
причем $\omega  = \overline{f} = u_{1}\overline{g}u_{2}$ для некоторых
$u_1, u_2 \in X^{*}$. Тогда многочлен
$h = f - u_{1} g u_{2}$
называется {\it композицией включения многочленов\/} $f$ и~$g$.
\enddemo

\demo{Definition 2}
Пусть $f$ и $g$~--- унитарные многочлены в~$\operatorname{As}(X)$,
$\omega \in X^{*}$~--- такое слово, что
$\omega = \overline{f}u = v\overline{g}$
для некоторых слов $u, v \in X^{*}$,
причем длина $\omega$ строго меньше
суммы длин $\overline{f}$ и $\overline{g}$.
Последнее условие означает, что
подслова $\overline{f}$ и $\overline{g}$ пересекаются,
а~именно, непустое начало слова $\overline{g}$ совпадает с~окончанием слова
$\overline{f}$.
{\it Композицией\/} пересечения $f$~и~$g$ называется многочлен
$h = fu-vg$.
\enddemo

Как видно из определений, с~каждой композицией связано некоторое слово
$\omega \in X^{*}$, которое равно большему старшему слову для композиций
включения и ``объединению'' старших слов для композиций пересечения.
Чтобы подчеркнуть связь слова~$\omega$ с~той или иной композицией многочленов
$f$~и~$g$, используется следующее обозначение:
$h = (f, g)_{\omega}$.

\demo{Definition 3}
Пусть $S$~--- множество унитарных многочленов в~$\operatorname{As}(X)$
и~$\omega \in X^{*}$~--- некоторое слово.
Многочлен~$h$ называется {\it тривиальным относительно\/} $(S, \omega)$, если
$$
h = \sum{ \lambda_{i}u_{i}f_{i}v_{i}}
$$
для некоторых
$\lambda_{i} \in \Bbbk$, $f_{i} \in S$, и $u_{i}, v_{i} \in X^{*}$,
причем $u_{i}\overline{f}v_{i} < \omega$.
\enddemo

\demo{Definition 4}
Пусть $S$~--- множество унитарных многочленов в~$\operatorname{As}(X)$.
Множество $S$ называется базисом Гребнера~--- Ширшова
в~$\operatorname{As}(X)$,
если любая композиция
$(f, g)_{\omega}$ для $f, g\in S$ тривиальна относительно $(S, w)$.
\enddemo

Будем использовать стандартное обозначение $\operatorname{As}(X \mid S)$
копредставления для алгебры $A\cong \operatorname{As}(X)/(S)$.

\proclaim{Theorem 1}
Пусть $S$~--- некоторое множество унитарных многочленов
в~$\operatorname{As}(X)$.
Тогда следующие условия эквивалентны:

\itemitem{\rm(C1)} $S$ является базисом Гребнера~--- Ширшова;
\itemitem{\rm(C2)} если $f \in (S)$, то слово $\overline{f}$  не является редуцированным относительно~$S$;
\itemitem{\rm(C3)} образы редуцированных относительно $S$ слов при естественном
гомоморфизме
$\operatorname{As}(X)\to \operatorname{As}(X \mid S)$
образуют базис алгебры
$\operatorname{As}(X \mid S)$ как векторного пространства.
\endproclaim

\head
Базис $U_{\operatorname{Lie}_n}({\goth g})$
\endhead
%\specialhead Базис $U_{\operatorname{Lie}_n}({\goth g})$\endspecialhead

Пусть $X$~--- базис алгебры ${\goth g}$\quad
 $n$ согласованных скобок Ли,
через $X^{(1)},\dots, X^{(n)}$
обозначим попарно не пересекающиеся множества,
каждое из которых биективно~$X$.
Согласно следствию~2.11 из статьи~[6]
мультипликативная универсальная обертывающая ассоциативная алгебра данной
алгебры Ли
${\goth g}$\quad  %\?
$n$
согласованных скобок задается как
$U_{\operatorname{Lie}_n}(X) = \operatorname{As}\langle X^{(1)}\cup X^{(2)}
\cup \dots \cup X^{(n)}\mid S\rangle$, где $S$ состоит из соотношений

\Item (a) %1)
$x^{(i)}y^{(i)} - y^{(i)}x^{(i)} + [x,y]_i = 0$,
\Item (b) %2)
$x^{(i)}y^{(j)}-y^{(j)}x^{(i)}+x^{(j)}y^{(i)}-y^{(i)}x^{(j)}
 + ([x,y]_i)^{(j)} + ([x,y]_j)^{(i)} = 0$, $i<j$.

В~[6] для случая $n = 2$ было установлено свойство Пуанкаре~--- Биркгофа~---
Витта:
существует такая фильтрация на
$U_{\operatorname{Lie}_2}({\goth g})$, что
$\operatorname{gr}U_{\operatorname{Lie}_2}({\goth g})
 \cong U_{\operatorname{Lie}_2}({\goth g}_0)$,
где ${\goth g}_0$ есть векторное пространство~${\goth g}$
с~тривиальными скобками $[\cdot,\cdot]_1$~и
$[\cdot,\cdot]_2$.
Наша ближайшая цель~--- установить свойство Пуанкаре~--- Биркгофа~--- Витта
для произвольного~$n$.
Свойство Пуанкаре~--- Биркгофа~--- Витта означает, что для алгебры
${\goth g}$ с~$n$ согласованными скобками Ли и ее универсальной
обертывающей алгебры
$U_{\operatorname{Lie}_{n}}({\goth g})$ можно
найти такую подходящую фильтрацию,
что ее градуированная алгебра изоморфна $U_{\operatorname{Lie}_{n}}({\goth g}_{0})$,
где ${\goth g}_{0}$ представляет собой векторное пространство
${\goth g}$ с~$n$~тривиальными скобками Ли.

Мы не будем давать в~силу его громоздкости строгого определения операды~[5].
Тем не менее попытаемся пояснить суть этого понятия.

Набор линейных пространств $\{{\Cal C}(n)\}_{n\geq1}$ над полем $\Bbbk$
и~множество линейных отображений (правило композиции)
$\operatorname{Comp}^\pi\colon
{\Cal C}(n)\otimes{\Cal C}(m_1)\otimes\dots\otimes
{\Cal C}(m_n)\to {\Cal C}(m)$, где $\pi = (m_1,\dots,m_n)$
есть $n$-разбиение числа~$m$,
называется {\it операдой}, если для правила композиции выполнены естественные
аналоги
ассоциативности и наличия нейтрального элемента.
Мы также полагаем, что есть согласованное с~правилом композиции действие
групп $S_n$ на пространства ${\Cal C}(n)$.

Операда $\Cal  P$ называется {\it бинарной},
если она порождена
пространством операций $E = {\Cal P}(2)$, и~{\it квадратичной}, если все
соотношения между операциями из ${\Cal P}(2)$ задаются действием
$S_2$ на ${\Cal P}(2)$ и определяющими соотношениями~$R$ пространства
${\Cal P}(3)$.
Именно, пространство полилинейных термов степени~3 будем отождествлять с
$$
E(3) = \Bbbk S_3\otimes_{\Bbbk{S}_2}(E\otimes E), \quad {\Cal P}(3) = E(3)/R,
$$
действие $(12)$ на $E\otimes E$ определяется как
$\operatorname{id}\otimes(12)$.
Полученную операду будем обозначать через
${\Cal P}(E, R)$.

Для бинарной квадратичной операды $\Cal  P = \Cal  P(E,R)$
кожуль-двойственная операда $\Cal  P^!$ определяется как
$\Cal  P(E^\vee, R^\perp)$,
где $E^\vee $~--- дуальное пространство к~пространству~$E$,
снабженное знакопеременным действием группы $S_2$, а
$R^\perp$~--- подпространство в~$E^\vee (3)\cong E(3)^\vee$,
ортогональное к~$R$.

Алгебра $A$ называется {\it градуированной}, если
$A = \bigoplus\nolimits_{n\geq0}A_n$, где $A_i$
является подпространством в~$A$
для любого натурального~$i$
и~при этом $A_i\cdot A_j\subseteq A_{i+j}$.
Напомним, что по каждой коммутативной (ассоциативной) градуированной алгебре
$A = \bigoplus\nolimits_{n\geq 0} A_n$ можно задать симметрическую операду
${\Cal O}_A$,
пространство ${\Cal O}_A(n)$ $n$-арных операций
еоторого изоморфно $A_{n-1}$,
действие $S_n$ берется тривиальным, а правила композиции определяются
при помощи умножения в~алгебре~$A$ так:
$$
\circ_i\colon {\Cal O}_A(m) \otimes {\Cal O}_A(n)
 = A_{m-1}\otimes A_{n-1} \to A_{m+n-2} = {\Cal O}_A(m+n-1).
$$

\proclaim{Proposition}
Имеется изоморфизм операд
${\Cal O}_{\Bbbk[x_1,\dots,x_n]} \simeq \operatorname{Lie}_n^!$.
\endproclaim

\demo{Proof}
Для того чтобы доказать утверждение, необходимо и~достаточно
(см. следствие~2.2.9 из~[5]) установить, что
$D\otimes B \in \operatorname{Lie}$ для произвольных алгебр
$D\in {\Cal O}_{\Bbbk[x_1,\dots,x_n]}$ и $B \in \operatorname{Lie}_n$.
Поскольку алгебра
$A = \Bbbk[x_1,\dots,x_n]$
является свободной в~классе
${\Cal O}_{\Bbbk[x_1,\dots,x_n]}$-алгебр,
достаточно проверить условие
$A\otimes B \in \operatorname{Lie}$ для произвольной алгебры $B \in
\operatorname{Lie}_n$.
Обозначим ${\Cal O}_{\Bbbk[x_1,\dots,x_n]}(2) = L(x_1,\dots,x_n)$ и
$\operatorname{Lie}_n(2) = L(\mu_1,\dots,\mu_n)$.
Ясно, что операция
$\xi = \sum\nolimits_{i=1}^n x_i\otimes \mu_i$ в~$(A\otimes B)(2)$
антикоммутативна, поскольку
$(x_i\otimes \mu_i)^{(12)}
 = x_i^{(12)}\otimes \mu_i^{(12)}
 = x_i \otimes (-\mu_i)$.
Нам нужно проверить выполнение тождества Якоби для $\xi$:
$$
1\otimes_{\Bbbk S_2}(\xi\otimes\xi)-(13)\otimes_{\Bbbk S_2}(\xi\otimes\xi)
 -(23)\otimes_{\Bbbk S_2}(\xi\otimes\xi) = 0.
$$
Раскрывая скобки и приводя подобные слагаемые в~левой части выражения,
получаем при $x_i^2$ выражение
$$
1\otimes_{\Bbbk S_2}(\mu_{i}\otimes\mu_{i})
 -(13)\otimes_{\Bbbk S_2}(\mu_{i}\otimes\mu_{i})
 -(23)\otimes_{\Bbbk S_2}(\mu_{i}\otimes\mu_{i}),
$$
которое равно нулю из-за выполнения тождества Якоби
для операции $\mu_i$ в~$B\in \operatorname{Lie}_n$.
При $x_i x_j$, $i\neq j$, получаем выражение
$$
\align
-(13)\otimes_{\Bbbk S_2}(\mu_{j}\otimes\mu_{i})
& -(23)\otimes_{\Bbbk S_2}(\mu_{j}\otimes\mu_i)
 +1\otimes_{\Bbbk S_2}(\mu_{j}\otimes\mu_i) \\
& - (13)\otimes_{\Bbbk S_2}(\mu_{i}\otimes\mu_{j})
 -(23)\otimes_{\Bbbk S_2}(\mu_i\otimes\mu_j)
 +1\otimes_{\Bbbk S_2}(\mu_{i}\otimes\mu_j),
\endalign
$$
равное нулю из-за выполнения тождества Якоби для операций
$\mu_i$, $\mu_j$, $\mu_i{+} %\?
\mu_j$ в~$B \in \operatorname{Lie}_n$.
\qed\enddemo

Перед тем как установить важное свойство мультипликативной
универсальной обертывающей от алгебры набора согласованных скобок Ли,
приведем необходимые сведения.
Градуированная ассоциативная алгебра
$A = \bigoplus\nolimits_{i\geq0}A_i$ называется
{\it кожулевой\/} [8], если
(a) %1)
$A_0$ полупроста и
(b) %2)
$A_0$, рассматриваемая как левый $A$-модуль,
допускает градуированную проективную резольвенту
$$
\dots \to P^2 \to P^1 \to P^0 \twoheadrightarrow A_0,
$$
при этом каждый из градуированных модулей $P^i$ порождается
своей $i$-й компонентой, т.~е.  $P^i = AP_i^i$.

\proclaim{Corollary 1}
Пусть $n\geq1$.
Для пары $(U_{\operatorname{Lie}_n},\operatorname{Lie}_n)$
выполняется свойство Пуанкаре~--- Биркгофа~--- Витта.
\endproclaim

\demo{Proof}
Известно, что алгебра многочленов
$A = \Bbbk[x_1,\dots,x_n]$ кожулева (здесь $A_0 \cong \Bbbk$).
Согласно теореме~5.3 из~[9]
кожулевость алгебры~$A$ влечет кожулевость операды
${\Cal O}_A$.
По теореме~4.1 из~[6] (см. также обсуждение в~примере~4.6 из~[6])
выполняется свойство Пуанкаре~--- Биркгофа~--- Витта.
\qed\enddemo

Алгебру ${\goth g}$\quad  $n$ согласованных скобок Ли
будем обозначать через ${\goth g}_0$,
если все $n$~скобок на ней тривиальны.
В~силу \Par*{Corollary~1} достаточно рассмотреть случай алгебры ${\goth g}_0$.
Полагаем, что множество~$X$ вполне упорядочено.
Тогда
$U_{\operatorname{Lie}_n}(X) = \operatorname{Ass}\langle X^{(1)}\cup X^{(2)}
 \cup \dots \cup X^{(n)}\mid S\rangle$, где $S$~состоит из соотношений

\Item (a) %1)
$x^{(i)}y^{(i)} = y^{(i)}x^{(i)}$, $x>y$,
\Item (b) %2)
$x^{(i)}y^{(j)}-y^{(j)}x^{(i)}+x^{(j)}y^{(i)}-y^{(i)}x^{(j)} = 0$, $x>y$, $i<j$.

Продолжаем порядок с~множества~$X$ на множество
$X^{(1)}\cup X^{(2)} \cup \dots \cup X^{(n)}$ так:
$x^{(i)} > y^{(j)}$, если $i<j$ или $i = j$ и $x>y$.
На слова из
$\operatorname{Ass}\langle X^{(1)}\cup X^{(2)}
\cup \dots \cup X^{(n)}\rangle$
данный порядок распространяем по правилу deg-lex.

\proclaim{Theorem 2}
Соотношения~$S$ образуют базис Гребнера~--- Ширшова алгебры
$U_{\operatorname{Lie}_n}(X)$.
\endproclaim

\demo{Proof}
Рассмотрим возможные композиции соотношений.
Ясно, что композиция вида
$x^{(i)}y^{(i)}z^{(i)}$, где $x>y>z$, тривиальна.

(a): %1)
$x^{(i)}y^{(i)}z^{(j)}$, где $x>y>z$, $i<j$.
Тогда
$$
\align
x^{(i)}y^{(i)}z^{(j)}
&\overset{(2)}\to{\to}
x^{(i)}z^{(j)}y^{(i)}-x^{(i)}y^{(j)}z^{(i)} + x^{(i)}z^{(i)}y^{(j)}
\\
&\overset{(2)}\to{\to}
z^{(j)}x^{(i)}y^{(i)} - x^{(j)}z^{(i)}y^{(i)} + z^{(i)}x^{(j)}y^{(i)}
\\
&\qquad - ( y^{(j)}x^{(j)}z^{(i)} - x^{(j)}y^{(i)}z^{(i)} + y^{(i)}x^{(j)}z^{(i)} )
 + x^{(i)}z^{(i)}y^{(j)}
\\
&\overset{(1)}\to{\to}
z^{(j)}x^{(i)}y^{(i)} + z^{(i)}(x^{(j)}y^{(i)}+x^{(i)}y^{(j)})
-(y^{(j)}x^{(i)}+y^{(i)}x^{(j)})z^{(i)}
\\
&\overset{(2)}\to{\to}
z^{(j)}x^{(i)}y^{(i)}
+ z^{(i)}(y^{(j)}x^{(i)}+y^{(i)}x^{(j)})
-(y^{(j)}x^{(i)}+y^{(i)}x^{(j)})z^{(i)}
\\
&\overset{(1)}\to{\to}
z^{(j)}x^{(i)}y^{(i)}
+ z^{(i)}y^{(j)}x^{(i)}+y^{(i)}z^{(i)}x^{(j)}
-(y^{(j)}x^{(i)}+y^{(i)}x^{(j)})z^{(i)}
\\
&\overset{(2)}\to{\to}
z^{(j)}x^{(i)}y^{(i)}
+ (y^{(j)}z^{(i)}x^{(i)}
- z^{(j)}y^{(i)}x^{(i)}
+ y^{(i)}z^{(j)}x^{(i)})
+ y^{(i)}z^{(i)}x^{(j)}
\\
&\qquad-(y^{(j)}x^{(i)}+y^{(i)}x^{(j)})z^{(i)}
\\
&\overset{(1)}\to{\to}
y^{(i)}z^{(j)}x^{(i)} + y^{(i)}z^{(i)}x^{(j)} - y^{(i)}x^{(j)}z^{(i)}
\overset{(2)}\to{\to} y^{(i)}x^{(i)}z^{(j)}.
\endalign
$$

(b): %2)
$x^{(i)}y^{(j)}z^{(j)}$, где $x>y>z$, $i<j$.
Тогда
$$
\align
x^{(i)}y^{(j)}z^{(j)}
&\overset{(2)}\to{\to}
y^{(j)}x^{(i)}z^{(j)}-x^{(j)}y^{(i)}z^{(j)}+y^{(i)}x^{(j)}z^{(j)}
\\
&\overset{(2)}\to{\to}
y^{(j)}z^{(j)}x^{(i)}-y^{(j)}x^{(j)}z^{(i)}+y^{(j)}z^{(i)}x^{(j)}
\\
&\qquad -(x^{(j)}z^{(j)}y^{(i)}-x^{(j)}y^{(j)}z^{(i)}+x^{(j)}z^{(i)}y^{(j)})
 +y^{(i)}x^{(j)}z^{(j)}
\\
&\to y^{(j)}z^{(j)}x^{(i)}-y^{(j)}x^{(j)}z^{(i)}+y^{(j)}z^{(i)}x^{(j)}
\\
&\qquad -x^{(j)}z^{(j)}y^{(i)}+x^{(j)}y^{(j)}z^{(i)}-x^{(j)}z^{(i)}y^{(j)}
 +y^{(i)}x^{(j)}z^{(j)}
\\
&\overset{(1)}\to{\to}
y^{(j)}z^{(j)}x^{(i)}-y^{(j)}x^{(j)}z^{(i)}+y^{(j)}z^{(i)}x^{(j)}
\\
&\qquad -x^{(j)}z^{(j)}y^{(i)}+y^{(j)}x^{(j)}z^{(i)}-x^{(j)}z^{(i)}y^{(j)}
 +y^{(i)}x^{(j)}z^{(j)}
\\
&\to y^{(j)}z^{(j)}x^{(i)}+y^{(j)}z^{(i)}x^{(j)}-x^{(j)}z^{(j)}y^{(i)}
-x^{(j)}z^{(i)}y^{(j)}+y^{(i)}x^{(j)}z^{(j)}
\\
&\overset{(1)}\to{\to}
y^{(j)}z^{(j)}x^{(i)}+y^{(j)}z^{(i)}x^{(j)}-x^{(j)}z^{(j)}y^{(i)}
 -x^{(j)}z^{(i)}y^{(j)}+y^{(i)}z^{(j)}x^{(j)}
\\
&\to y^{(j)}z^{(j)}x^{(i)}+(y^{(j)}z^{(i)}+y^{(i)}z^{(j)})x^{(j)}
 -x^{(j)}(z^{(j)}y^{(i)}+z^{(i)}y^{(j)})
\\
&\overset{(1)(2)}\to{\longrightarrow} %\?увеличила стрелку
z^{(j)}y^{(j)}x^{(i)}+(z^{(j)}y^{(i)}+z^{(i)}y^{(j)})x^{(j)}
 -x^{(j)}(y^{(j)}z^{(i)}+y^{(i)}z^{(j)})
\\
&\to z^{(j)}y^{(j)}x^{(i)}+z^{(j)}y^{(i)}x^{(j)}+z^{(i)}y^{(j)}x^{(j)}
-x^{(j)}y^{(j)}z^{(i)}-x^{(j)}y^{(i)}z^{(j)}
\\
&\to z^{(j)}y^{(j)}x^{(i)}-z^{(j)}x^{(j)}y^{(i)}+z^{(j)}y^{(i)}x^{(j)}
-x^{(j)}y^{(j)}z^{(i)}
\\
&\qquad +z^{(j)}x^{(j)}y^{(i)}-x^{(j)}y^{(i)}z^{(j)} +z^{(i)}y^{(j)}x^{(j)}
\\
&\overset{(1)}\to{\to}
z^{(j)}y^{(j)}x^{(i)}-z^{(j)}x^{(j)}y^{(i)}+z^{(j)}y^{(i)}x^{(j)}
-x^{(j)}y^{(j)}z^{(i)}
\\
&\qquad +x^{(j)}z^{(j)}y^{(i)}-x^{(j)}y^{(i)}z^{(j)} +z^{(i)}y^{(j)}x^{(j)}
\\
&\to z^{(j)}y^{(j)}x^{(i)}-z^{(j)}x^{(j)}y^{(i)}+z^{(j)}y^{(i)}x^{(j)}
 -x^{(j)}(y^{(j)}z^{(i)}
\\
&\qquad -z^{(j)}y^{(i)}+y^{(i)}z^{(j)})+z^{(i)}y^{(j)}x^{(j)}
\\
&\overset{(2)}\to{\to}
z^{(j)}x^{(i)}y^{(j)}-x^{(j)}z^{(i)}y^{(j)}+z^{(i)}x^{(j)}y^{(j)}
\overset{(2)}\to{\to}
x^{(i)}z^{(j)}y^{(j)}
\overset{(1)}\to{\to} x^{(i)}y^{(j)}z^{(j)}.
\endalign
$$

(c): %3)
$x^{(i)}y^{(j)}z^{(k)}$, где $x>y>z$, $i<j<k$.
С~одной стороны,
$$
\align
x^{(i)}y^{(j)}z^{(k)}
&\overset{(3)}\to{\to}
y^{(j)}x^{(i)}z^{(k)} - x^{(j)}y^{(i)}z^{(k)} + y^{(i)}x^{(j)}z^{(k)}
\\
&\to ^{(5)} %\?так и надо, наверное, ибо много такого набора
y^{(j)}z^{(k)}x^{(i)}-x^{(k)}z^{(i)}+z^{(i)}x^{(k)})
 - x^{(j)}y^{(i)}z^{(k)} + y^{(i)}x^{(j)}z^{(k)}
\\
&\to^{(6)} z^{(k)}y^{(j)}x^{(i)}-y^{(k)}z^{(j)}x^{(i)}+z^{(j)}y^{(k)}x^{(i)}
 - y^{(j)}x^{(k)}z^{(i)}
\\
&\qquad+ y^{(j)}z^{(i)}x^{(k)}-x^{(j)}y^{(i)}z^{(k)}+y^{(i)}x^{(j)}z^{(k)}
\\
&\to ^{(6)}z^{(k)}y^{(j)}x^{(i)}-y^{(k)}z^{(j)}x^{(i)}+z^{(j)}y^{(k)}x^{(i)}
 - y^{(j)}x^{(k)}z^{(i)} + y^{(j)}z^{(i)}x^{(k)}
\\
&\qquad-x^{(j)}y^{(i)}z^{(k)}+y^{(i)}z^{(k)}x^{(j)}-y^{(i)}x^{(k)}z^{(j)}
 +y^{(i)}z^{(j)}x^{(k)}
\\
&\to^{(5)} z^{(k)}y^{(j)}x^{(i)}-y^{(k)}z^{(j)}x^{(i)}+z^{(j)}y^{(k)}x^{(i)}
 - y^{(j)}x^{(k)}z^{(i)} + y^{(j)}z^{(i)}x^{(k)}
\\
&\qquad-x^{(j)} y^{(i)} z^{(k)} +y^{(i)} z^{(k)} x^{(j)} -y^{(i)}x^{(k)}z^{(j)}
 +z^{(j)}y^{(i)}x^{(k)}-y^{(j)}z^{(i)}x^{(k)}+{z^{(i)}y^{(j)}x^{(k)}}
\\
&\to^{(6)} z^{(l)}y^{(j)}x^{(i)}-y^{(k)}z^{(j)}x^{(i)}+z^{(j)}y^{(k)}x^{(i)}
 - y^{(j)}x^{(k)}z^{(i)} + y^{(j)}z^{(i)}x^{(k)}-x^{(j)}z^{(k)}y^{(i)}
\\
&\qquad+x^{(j)}y^{(k)}z^{(i)}-x^{(j)}z^{(i)}y^{(k)}+y^{(i)}z^{(k)}x^{(j)}
 -y^{(i)}x^{(k)}z^{(j)}
\\
&\qquad+z^{(j)}y^{(i)}x^{(k)}-y^{(j)}z^{(i)}x^{(k)}
  +z^{(i)}y^{(j)}x^{(k)}
\\
&\to^{(6)} z^{(k)}y^{(j)}x^{(i)}-y^{(k)}z^{(j)}x^{(i)}+z^{(j)}y^{(k)}x^{(i)}
\\
&\qquad- y^{(k)}x^{(k)}z^{(i)} + y^{(j)}z^{(i)}x^{(k)} -x^{(j)}z^{(k)}y^{(i)}
+y^{(k)}x^{(j)}z^{(i)}-x^{(k)}y^{(j)}z^{(i)} +y^{(j)}{x'}^{(k)}z^{(i)}
\\
&\qquad-x^{(j)}z^{(i)}y^{(k)}+y^{(i)}z^{(k)}x^{(j)}-y^{(i)}x^{(k)}z^{(j)}
 +z^{(j)}y^{(i)}x^{(k)}-y^{(j)}z^{(i)}x^{(k)}+z^{(i)}y^{(j)}x^{(k)}
\\
&\to^{(6)} z^{k}y^{(j)}x^{(i)}-y^{(k)}z^{(j)}x^{(i)}+z^{(j)}y^{(k)}x^{(i)}
 - y^{(j)}x^{(k)}z^{(i)} + y^{(j)}z^{(i)}x^{(k)}
\\
&\qquad-z^{(k)}x^{(j)}y^{(i)}+x^{(k)}z^{(j)}y^{(i)}-z^{(j)}x^{(k)}y^{(i)}
 +y^{(k)}x^{(j)}z^{(i)} -x^{(k)}y^{(j)}z^{(i)}+y^{(j)}x^{(k)}z^{(i)}
\\
&\qquad-x^{(j)}z^{(i)}y^{(k)}+y^{(i)}z^{(k)}x^{(j)}-y^{(i)}x^{(k)}z^{(j)}
+z^{(j)}y^{(i)}x^{(k)}-y^{(j)}z^{(i)}x^{(k)}+z^{(i)}y^{(j)}x^{k}
\\
&\to -y^{(k)}z^{(j)}x^{(i)}- y^{(j)}x^{(k)}z^{(i)}
 + y^{(j)}z^{(i)}x^{(k)}+x^{(k)}z^{(j)}y^{(i)}+y^{(k)}x^{(j)}z^{(i)}
\\
&\qquad-x^{(k)}y^{(j)}z^{(i)}+y^{(j)}x^{(k)}z^{(i)} -x^{(j)}z^{(i)}y^{(k)}
 +y^{(i)}z^{(k)}x^{(j)}-y^{(i)}x^{(k)}z^{(j)}-y^{(j)}z^{(i)}x^{(k)}
 \\
&\to -y^{(k)}z^{(j)}x^{(i)}- y^{(j)}x^{(k)}z^{(i)} + y^{(k)}{x'}^{(j)}z^{(i)}
 +y^{(j)}x^{(k)}z^{(i)}
\\
&\qquad-x^{(j)}z^{(i)}y^{(k)}+y^{(i)}z^{(k)}x^{(j)}
 -y^{(i)}x^{(k)}z^{(j)}
\\
&\to - y^{(j)}x^{(k)}z^{(i)} +y^{(j)}x^{(k)}z^{(i)}+z^{(k)}y^{(i)}x^{(j)}
 -y^{(k)}z^{(i)}x^{(j)}
\\
&\qquad+z^{(i)}y^{(k)}x^{(j)}\to -y^{(k)}z^{(i)}x^{(j)}.
\endalign
$$

С~другой стороны,
$$
\align
x^{(i)}y^{(j)}z^{(k)}
&\overset{(6)}\to{\to}
x^{(i)}z^{(k)}y^{(j)}-x^{(i)}y^{(k)}z^{(j)}+x^{(i)}z^{(j)}y^{(k)}
\\
&\to ^{(5)(6)} x^{(i)}z^{(k)}y^{(j)}-y^{(k)}x^{(i)}z^{(j)}
 + x^{(k)}y^{(i)}z^{(j)}-y^{(i)}x^{(k)}z'{}^{(j)}+z^{(j)}x^{(i)}y^{(k)}
\\
&\qquad-x^{(j)}z^{(i)}y^{(k)}+z^{(i)}x^{(j)}y^{(k)}
\\
&\to ^{(6)} x^{(i)}z^{(k)}y^{(j)}-y^{(k)}x^{(i)}z^{(j)}+x^{(k)}y^{(i)}z^{(j)}
 -y^{(i)}x^{(k)}z^{(j)}+z^{(j)}x^{(i)}y^{(k)}
\\
&-x^{(j)}z^{(i)}y^{(k)}+z^{(i)}y^{(k)}x'{}^{(j)}-z^{(i)}x^{(k)}y^{(j)}
 +z^{(i)}y^{(j)}x'{}^{(k)}
\\
&\to ^{(6)}z^{(k)}x^{(i)}y^{(j)}-x^{(k}z^{(i)}y^{(j)}+z^{(i)}x^{(k)}y^{(j)}
 -y^{(k)}x^{(i)}z^{(j)}+x^{(k)}y^{(i)}z^{(j)}
\\
&\qquad-y^{(i)}x^{(k)}z^{(j)}+z^{(j)}x^{(i)}y^{(k)}-x^{(j)}z^{(i)}y^{(k)}
 +z^{(i)}y^{(k)}x^{(j)}-z^{(i)}x^{(k)}{y'}^{(j)}+z^{(i)}y^{(j)}x^{(k)}
\\
&\to ^{(5)}z^{(k}y^{(j)}x^{(i)}-z^{(k)}x^{(j)}y^{(i)}+z^{(k)}y^{(i)}x^{(j)}
-x^{(k)}z^{(i)}y^{(j)}+z^{(i)}x^{(k)}y^{(j)}
\\
&\qquad-y^{(k)}x^{(i)}z^{(j)}+x^{(k)}y^{(i)}z^{(j)}
\\
&\qquad-y^{(i)}x^{(k)}z^{(j)}+z^{(j)}x^{(i)}y^{(k)}-
x^{(j)}z^{(i)}y^{(k)}+z^{(i)}y^{(k)}x^{(j)}
-z^{(i)}x^{(k)}y^{(j)}+z^{(i)}y^{(j)}x^{(k)}
\\
&\to ^{(3)}z^{(k)}y^{(j)}x^{(i)}-z^{(k)}x^{(j)}y^{(i)}+z^{(k)}y^{(i)}x^{(j)}
 -x^{(k)}z^{(i)}y^{(j)}-y'{}^{(k)}x^{(j)}z^{(i)} + x^{(k)}z^{(j)}y^{(i)}
\\
&\qquad-x^{(k)}y^{(j)}z^{(i)}+x^{(k)}z^{(i)}y^{(j)}-y^{(i)}x^{(k)}z^{(j)}
+z^{(j)}x^{(i)}y^{(k)}
\\
&\qquad-x^{(j)}z^{(i)}y^{(k)}+z^{(i)}y^{(k)}x^{(j)}+z^{(i)}y^{(j)}x^{(k)}
\\
&\to z^{(k)}y^{(j)}x^{(i)}-z^{(k)}x^{(j)}y^{(i)}+z^{(k)}y^{(i)}x^{(j)}
 -y^{(k)}x^{(i)}z^{(j)}+x^{(k)}z^{(j)}y^{(i)}-x^{(k)}y^{(j)}z^{(i)}
\\
&\qquad -y^{(i)}x^{(k)}z^{(j)}+z^{(j)}x^{(i)}y^{(k)}-x^{(j)}z^{(i)}y^{(k)}
 +z^{(i)}y^{(k)}x^{(j)}+z^{(i)}y^{(j)}x^{(k)}
\\
&\to  ^{(5)}z^{(k)}y^{(j)}x^{(i)}-z^{(k)}x^{(j)}y+z^{(k)}y^{(i)}x^{(j)}
 -y^{(k)}x^{(i)}z^{(j)}+x^{(k)}z^{(j)}y^{(i)}-x^{(k)}y^{(j)}z^{(i)}
\\
&\qquad -y^{(i)}x^{(k)}z^{(j)} +z^{(j)}y^{(k)}x^{(i)}-z^{(j)}x^{(k)}y^{(i)}
 +z^{(j)}y^{(i)}x^{(k)}
\\
&\qquad-x^{(j)}z^{(i)}y^{(k)}+z^{(i)}y^{(k)}x^{(j)} +z^{(i)}y^{(j)}x^{(k)}
\\
&\to  ^{(3)}z^{(k)}y^{(i)}x^{(j)}-y^{(k)}z^{(j)}x^{(i)}+y^{(k)}x^{(j)}z^{(i)}
-y^{(k)}z^{(i)}x^{(j)}+x^{(k)}z^{(j)}y^{(i)}
\\
&\qquad-x^{(k)}y^{(j)}z^{(i)}-y^{(i)}x^{(k)}z^{(j)}-x^{(j)}z^{(i)}y^{(k)}
 +z^{(i)}y^{(k)}x^{(j)}
\\
&\to z^{(k)}y^{(i)}x^{(j)}-y^{(k)}z^{(j)}x^{(i)}+y^{(k)}x^{(j)}z^{(i)}
 -y^{(k)}z^{(i)}x^{(j)}
\\
&\qquad-y^{(i)}x^{(k)}z^{(j)}-x^{(j)}z^{(i)}y^{(k)} +z^{(i)}y^{(k)}x^{(j)}
\\
&\to z^{(k)}y^{(i)}x^{(j)}-y^{(k)}z^{(i)}x^{(j)}+z^{(i)}y^{(k)}x^{(j)}
\to -y^{(k)}z^{(i)}x^{(j)}.
\endalign
$$

Тем самым мы проверили тривиальность всех композиций и $S$~является базисом
Гребнера~--- Ширшова.
\qed\enddemo

\proclaim{Corollary 2}
В~качестве базиса алгебры $U_{\operatorname{Lie}_n}({\goth g}_0)$
берем редуцированные относительно~$S$ слова, т.~е. слова,
не содержащие в~качестве подслов
$x^{(i)}y^{(i)}$ и $x^{(i)}y^{(j)}$ для $x,y\in X$, $x>y$, $i<j$.
\endproclaim

\head
Скорость роста алгебры $U_{\operatorname{Lie}_n}({\goth g})$
\endhead
%\specialhead Скорость роста алгебры $U_{\operatorname{Lie}_n}({\goth g})$\endspecialhead

Экспоненциальная скорость роста~$\rho(A)$ ассоциативной алгебры~$A$
относительно порождающего множества~$X$ вычисляется как
$$
\rho(A) = \lim\limits_{n\to\infty} \root{n}\of{ a_n},
$$
где $a_n = \dim V_n$,
$V_n$~--- линейная оболочка слов длины~$n$ в~алфавите~$X$.

\proclaim{Question} %\?
Пусть ${\goth g} \in \operatorname{Lie}_n$, $\dim {\goth g} = m$.
Чему равна скорость роста
$\rho(U_{\operatorname{Lie}_n}({\goth g}))$
относительно порождающего множества
$X^{(1)}\cup X^{(2)} \cup \dots \cup X^{(n)}$ при $|X| = m$?
\endproclaim

Покажем, как можно переформулировать вопрос в~терминах более просто
задаваемой ассоциативной алгебры.

Рассмотрим алгебру
$V_{n,m} = \operatorname{Ass}\langle X^{(1)}\cup X^{(2)} \cup \dots \cup X^{(n)}
 \mid T\rangle$, где $T$~состоит из соотношений

\Item (a) %1)
$x^{(i)}y^{(i)} = y^{(i)}x^{(i)}$, $x>y$,

\Item (b) %2)
$x^{(i)}y^{(j)}=y^{(j)}x^{(i)}$, $x>y$, $i<j$.

Это так называемая частично коммутативная алгебра, т.~е.  ассоциативная
алгебра,
получающаяся факторизацией свободной ассоциативной алгебры по множеству
соотношений коммутирования, выполненных для определенных пар порождающих
элементов.
В~работе 1969 г.~[10] Картье и Фоата ввели понятие
частично коммутативного моноида.
Пусть задан простой граф $G(V,E)$, тогда
{\it частично коммутативный моноид\/}
$M(G)$ определяется через копредставление следующим образом:
$M\langle V\mid v_1v_2 = v_2v_1,\,(v_1,v_2)\in E\rangle$,  т.~е.  как фактор
свободного моноида
$M\langle V\rangle$ по отношению эквивалентности, порожденной множеством
$\{v_1v_2 = v_2v_1,\,(v_1,v_2)\in E\}$.
Позднее изучались частично коммутативные ассоциативные алгебры~[11],
частично коммутативные алгебры Ли~[12] и~другие подобные структуры.
Частично коммутативную ассоциативную алгебру, построенную по графу~$G$,
будем обозначать через $\operatorname{As}(G)$.

Легко проверить, что соотношения $T$ образуют базис Гребнера~--- Ширшова
и~поэтому множество редуцированных относительно соотношений~$S$ и~$T$ слов
совпадает.
Отсюда $\rho(U_{\operatorname{Lie}_n}({\goth g})) = \rho(V_{n,m})$.

Введем простой конечный граф~$G$ так: вершины~$G$ соответствуют порождающим
$x^{(i)}$,
а ребро между двумя вершинами проводится, если и~только если
перестановочность соответствующих этим вершинам порождающих входит в~$T$.
Известно~[13], что
$\rho( \operatorname{As}(G)) = \beta(G)$, где $\beta(G)$~--- наибольший
по модулю вещественный корень многочлена
$$
PC(G,x)=x^{t_0}-c_1(G)x^{t_0-1}+c_2(G)x^{t_0-2}
 +\dots+(-1)^{t_0-1}c_{t_0-1}x+(-1)^{t_0}c_{t_0}(G),
$$
где $c_i$ обозначает количество клик размера~$i$ в~графе~$G$
($c_0 := 1$), а $t_0$~--- размер максимальной клики в~$G$.

Поскольку мы работаем с~очень конкретным графом~$G$,
мы сможем явно посчитать все коэффициенты $c_i(G)$.

Всего в~графе~$G$ вершин
$mn = C_m^1 C_n^1$,  ребер, возникающих из первых соотношений ---
$C_m^2 n = C_m^2 C_n^1$,
а из вторых~--- $C_m^2C_n^2$, здесь
$C_m^2$ отвечает за выбор подходящих $x,y$ из алфавита~$X$,
а $C_n^2$ отвечает за выбор пары индексов $(i,j)$.

Для произвольного $1\leq k\leq m$ сперва выбираем $k$~букв
$x_1,\dots,x_k{\in} X$,
далее выбираем $C_n^s$ способами $s$-элементное подмножество
$Z\subset \{0,\dots,n{-}1\}$.
Теперь для каждого $Z$ мы $C_{k-1}^{s-1}$ способами расставляем перегородки,
что соответствует тому, как мы распределяем элементы~$Z$ по индексам
$i_1,\dots,i_k$.
Тем самым
$$
c_k = C_m^k(C_{k-1}^0 C_n^1 + C_{k-1}^1 C_n^2 + C_{k-1}^2 C_n^3
 + \dots + C_{k-1}^l C_n^{l+1} + \dots + C_{k-1}^{k-1}C_n^k).
$$
Комбинаторно легко увидеть, что
$$
C_{k-1}^0 C_n^1 + C_{k-1}^1 C_n^2 + C_{k-1}^2 C_n^3 + \dots
 + C_{k-1}^l C_n^{l+1} + \dots + C_{k-1}^{k-1}C_n^k
 = C_{n+k-1}^k.
$$
Поэтому
$$
\align
PC(G,x)
& = x^m - C_m^1 C_n^1 x^{m-1} + C_m^2 C_{n+1}^2 x^{t_0-2}
 + \dots + (-1)^k C_m^k C_{n+k-1}^k x^{m-k}+ \cdots %\?как правильно рвать, прочитала, вроде так
\\
&\qquad +
(-1)^m C_{n+m-1}^m
 = \sum\limits_{k=0}^m (-1)^k C_m^k C_{n+k-1}^k x^{m-k}.
\endalign
$$

При помощи {\it Wolframalpha\/} %\?{\tt Wolframalpha}; может, так надо WolframAlpha
мы приближенно вычислили $\beta(G)$ для малых значений $n$ и $m$:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%4954t1
   \Figure
% \name{}  \caption{}
 \body
\iftex
\epsfxsize130mm
\epsfbox{4956.ams+tabl1.eps}
\else
\file{4956.ams+tabl1.png}
\fi
\endbody
\endFigure

Для поиска асимптотики $\beta(G)$ нам понадобится следующая

\proclaim{Lemma}
Если $m\geq n$, то
$$
PC(G(m,n),x) = (x-1)^{m-n+1}PC(G(n-1,m+1),x).
$$
\endproclaim

\demo{Proof}
Равенство многочленов сводится после раскрытия скобок
и~подсчета коэффициентов при $x^{m-k}$
к~проверке комбинаторного равенства
$$
\sum\limits_{s=0}^k C_{m-n+1}^s C_{m+k-s}^{k-s}C_{n-1}^{k-s}
 = C_{n+k-1}^k C_m^k.
                                                    \eqno{(1)}
$$
Первый множитель выбираем из первой скобки
$(x-1)^{m-n+1}$ с~коэффициентом
$(-1)^s C_{m-n+1}^{m-n+1-s} = (-1)^s C_{m-n+1}^s$.
Из второй скобки
$x^{n-1-(k-s)}$ приходит с~коэффициентом
$(-1)^{k-s} C_{m+k-s}^{k-s}C_{n-1}^{k-s}$.
Перемножая $(-1)^s$ и $(-1)^{k-s}$, получаем $(-1)^k$.

Левую часть~\Tag(1) можно представить как
$$
\sum\limits_{s=0}^k C_{m-n+1}^s C_{m+k-s}^{k-s}C_{n-1}^{k-s}
 = C_{m+k}^k C_{n-1}^k\, {}_3 F_2(-m+n-1,-k,-k;\,-m-k,n-k;\,1),
                                                                \tag2
$$
где ${}_3 F_2(a,b,c; d,e; z)$ обозначает обобщенный гипергеометрический ряд
$$
{}_3 F_2(a,b,c; d,e; z)
 = \sum\limits_{i=0}^\infty \frac{(a)_i(b)_i(c)_i}{(d)_i(e)_i}\cdot
\frac{z^i}{i!},
$$
здесь
$$
(x)_i = \frac{\Gamma(x+i)}{\Gamma(x)} = \cases
1, & i = 0, \\
x(x+1)\dots %\?
(x+i-1), & i>0,
\endcases
$$
обозначает символ Похгаммера.

Известная теорема Заальшутца (1890) гласит, что
$$
{}_3 F_2(a,b,-n; c, a+b-c-n-1; 1)
 = \frac{ (c-a)_n (c-b)_n }{ (c)_n (c-a-b)_n }.
$$
Тем самым в~формуле~\Tag(2) переписываем
$$
\align
{}_3 F_2(-m&+n-1,-k,-k;\,-m-k,n-k;\,1)
 = \frac{ (-k-n+1)_k (-m)_k }{ (-m-k)_k (-n+1)_k }
\\
& = \frac{ (-k-n+1)\dots (-n)\cdot (-m)\dots (-m+k-1) }{ (-m-k)\dots (-m-
1)\cdot (-n+1)\dots (-n+k) }
\\
& = \frac{ (k+n-1)\dots (n)\cdot (m)\dots (m-k+1) }{ (m+k)\dots (m+1)\cdot
(n+1)\dots (n-k) }
\\
& = \frac{ (C_{n+k-1}^k \cdot k!)\cdot (C_m^k \cdot k!) }{ (C_{m+k}^k \cdot
k!)\cdot (C_{n-1}^k \cdot k!) }
 = \frac{ C_{n+k-1}^k C_m^k }{ C_{m+k}^k C_{n-1}^k },
\endalign
$$
что и~дает после домножения на $C_{m+k}^k C_{n-1}^k$ правую часть~\Tag(1).
\qed\enddemo

Перед тем как вывести асимптотику $\beta(G)$,
напомним определение функции Бесселя первого рода:
$J_0(z) = \sum\nolimits_{k=0}^\infty \frac{ (-1)^k ( z^2/4 )^k }{k!k!}$.

Ниже будем использовать следующие математические знаки:
$\gg$~--- ``много больше,''
$\ll$~--- ``много меньше,''
$\sim$~--- ``асимптотически эквивалентны.''

\proclaim{Theorem 3}
Пусть $m,n\gg1$, тогда $\beta(G) = \alpha(mn+o(mn))$, где
$\alpha = \frac{4}{q_0^2} \approx 0{.}69166$ и
$q_0$~--- наименьший корень функции $J_0(2\sqrt{x})$.
\endproclaim

\demo{Proof}
Пусть $m,n\gg1$. Тогда выполнено
$|E(G)| \sim m^2n^2/4 = |V(G)|^2/4$,
поэтому согласно следствиям 8.4 и~9.3 из~[14] верны оценки
$$
0,5 nm\leq \beta\leq 0{.}751 nm.
$$
Отсюда можно искать~$\beta$ в~виде
$\beta \sim \alpha nm$ для параметра
$\alpha \in [0{.}5;0{.}751]$,
вообще говоря, зависящего от $n$ и $m$.

Наша цель~--- показать, что $\alpha$~удовлетворяет следующему соотношению:
$$
0 = \alpha^m - \frac{\alpha^{m-1}}{1!1!} + \frac{\alpha^{m-2}}{2!2!}
 - \dots + (-1)^k \frac{\alpha^{m-k}}{k!k!} +  \cdots.
                                                    \eqno{(3)}
$$
Его наибольший корень асимптотически равен
$\alpha = \frac{4}{q_0^2} \approx 0{.}69166$,
где $q_0$~--- наименьший корень функции $J_0(2\sqrt{x})$.
Все другие корни~\Tag(3) не превосходят $0{.}14$,
т.~е. не лежат на отрезке $[0{.}5;\,0{.}751]$.

{\sc Случай 1}: $n-1\geq m$.
Тогда коэффициент в~$PC(G,x)$ при $x^{m-k}$ без учета знака можно оценить
следующим образом:
$$
\align
C_m^k C_{n+k-1}^k
& = \frac{m(m-1)\dots(m-k+1)}{k!}\cdot\frac{(n+k-1)(n+k-2)\dots n}{k!}
\\
& = \frac{1}{k!k!}[nm][(m-1)(n+1)]\dots [(m-k+1)(n+k-1)]
 \leq \frac{(nm)^k}{k!k!}.
\endalign
$$

Далее, для $2/5<\gamma<4/5$ выполнено
$$
PC(G,\gamma mn)/(mn)^m
\sim \gamma^m - \gamma^{m-1} + \frac{\gamma^{m-2}}{2!2!} - \cdots,
$$
где для $k \ll O(\sqrt{m})$ соответствующее слагаемое без учета знака
асимптотически равно
$\frac{\gamma^{m-k}}{k!k!}$.
При $k = O(\sqrt{m})$ слагаемое (также без учета знака) не превосходит
$\frac{\gamma^{m-k}}{k!k!}$,
что по формуле Стирлинга $q!\sim \sqrt{2\pi q}(q/e)^q$ можно оценить сверху
так:
$$
\frac{\gamma^{m-k}}{k!k!}
 < \frac{\gamma^m}{p\gamma^{\sqrt{m}/r} (\sqrt{m}/t)^{\sqrt{m}/s}}
 < \frac{\gamma^m}{p(\gamma'\sqrt{m}/t)^{\sqrt{m}/s}}
$$
для некоторых $p$, $t$, $s$, $r$, и $\gamma'$, зависящих от~$k$, но не от $n$ и $m$.
Если мы суммируем даже $m$~слагаемых такого типа,
то все равно получим выражение из $o(\gamma^m)$.
Тем самым приходим к~уравнению~\Tag(3).
Для $y = 1/\alpha$ получаем уравнение
$$
0 = 1 - \frac{y}{1!1!} + \frac{y^2}{2!2!} - \dots + (-1)^k \frac{y^k}{k!k!}
+ \dots  = J_0(2\sqrt{y}),
$$
откуда и находим указанное выше значение~$\alpha$.

{\sc Случай 2}: $m\geq n$.
По лемме выполнено
$$
PC(G(m,n),x) = (x-1)^{m-n+1}PC(G(n-1,m+1),x),
$$
и~мы приходим к~случаю~1. Следовательно,
$$
\beta(G(m,n)) = \beta(G(n-1,m+1)) \sim \alpha (n-1)(m+1)\sim \alpha nm.
$$
Тем самым теорема доказана.
\qed\enddemo

\acknowledgments
Авторы благодарят П.С.~Колесникова и рецензента за ценные замечания.

\Refs

\ref\no1
 \by                      Bershtein M., Dotsenko V., and Khoroshkin A.
 \paper                   Quadratic algebras related to the bi-Hamiltonian operad
 \jour                    Int. Math. Res. Not. IMRN %J.~Amer. Math. Soc.
 \yr                      2007
 \vol                     24
 \num                     22
 \size                    30
\endref

\ref\no2
 \by                      Gonz\'alez D'Le\'on R.S. %D'Le\'{o}n~R.~G.
 \paper                   On the free Lie algebra with multiple brackets
 \jour                    Adv. in Appl. Math.
 \yr                      2016
 \vol                     79
% \issue                  -
 \pages                   37--97
\endref

\ref\no3
 \by                      Liu F.
 \paper                   Combinatorial bases for multilinear parts of free algebras with two compatible brackets
 \jour                    J.~Algebra
 \yr                      2010
 \vol                     323
 \issue                   1
 \pages                   37--97
\endref

\ref\no4
 \by                      Dotsenko V. and Khoroshkin A.
 \paper                   Gr\"{o}bner bases for operads
 \jour                    Duke Math.~J.
 \yr                      2010
 \vol                     153
 \issue                   2
 \pages                   363--396
\endref

\ref\no5
 \by                      Ginzburg V. and Kapranov M.
 \paper                   Koszul duality for operads
 \jour                    Duke Math.~J.
 \yr                      1994
 \vol                     76
 \issue                   1
 \pages                   203--272
\endref

\ref\no6
 \by                     Khoroshkin A.
 \paper                  PBW property for associative universal enveloping algebras over an operad
 \jour                   Int. Math. Res. Not. IMRN
 \yr                     2022
 \vol                    2022
 \issue                  4
 \pages                  3106--3143
\endref

\ref\no7
 \by                     Gubarev V.
 \paper                  Universal enveloping algebra of a~pair of compatible Lie brackets
 \jour                   Internat. J. Algebra Comput.
 \yr                     2022
 \vol                    32
 \issue                  7
 \pages                  1335--1344
\endref

\ref\no8
 \by                     Beilinson A., Ginzburg V., and Soergel~W.
 \paper                  Koszul duality patterns in representation theory
 \jour                   J.~Amer. Math. Soc.
 \yr 1996
 \vol                    9
 \issue                  2
 \pages                  473--527
\endref

\ref\no9
 \by                     Dotsenko V. and Khoroshkin A.
 \paper                  Quillen homology for operads via Gr\"{o}bner bases
 \jour                   Doc. Math.
 \yr                     2013
 \vol                    18
 %\issue                 -
 \pages                  707--747
\endref

\ref\no10
 \by                     Cartier P. and Foata D.
 \book                   Probl\`{e}mes combinatoires de commutation et r\'{e}arrangements
 \publaddr               Berlin
 \publ                   Springer
 \yr                     1969
 \finalinfo              Lecture Notes in Math.,  85
\endref

\ref\no11
 \by                     Kim K., Makar-Limanov L., Neggers J., and Roush~F.
 \paper                  Graph algebras
 \jour                   J.~Algebra
 \yr                     1980
 \vol                    64
 \issue                  1
 \pages                  46--55
\endref

\ref\no12
 \by                     Duchamp G. and Krob D.
 \paper                  The free partially commutative Lie algebra: Bases and ranks
 \jour                   Adv. Math.
 \yr                     1992
 \vol                    95
 \issue                  1
 \pages                  92--126
\endref

\ref\no13
 \by                     Fisher D.C. and Solow A.E.
 \paper                  Dependence polynomial
 \jour                   Discrete Math.
 \yr                     1990
 \vol                    82
 \issue                  3
 \pages                  251--258
\endref

\ref\no 14
  \by                    Gubarev V.
  \preprint              $PC$-Polynomial of Graph\nofrills
  \yr                    2018
  \bookinfo              arXiv:1808.03932
\endref
\endRefs

\enddocument