Primitive elements of free non-associative algebras over finite fields

Texto integral

1. Введение

Многообразие всех алгебр над полем является шрайеровым многообразием алгебр. Свободная алгебра в этом многообразии – свободная неассоциативная алгебра. Утверждение, аналогичное теореме Нильсена–Шрайера в 1947 году доказал А. Г. Курош для неассоциативных свободных алгебр: всякая подалгебра неассоциативной свободной алгебры с любым множеством свободных образующих, отличная от нуля, является свободной[2].

Для обозначения символов-букв будем использовать множество $X=\{x_1,x_2,\dots ,x_n\}$ в случае их большого числа либо {x, y, z} иначе. Словом длины (степени) k будем называть упорядоченную последовательность из k символов ${\chi }_1\dots {\chi }_k, {\chi }_i\in X$ с заданной расстановкой скобок. Множество всех слов $W=\Gamma \left(X\right)$ образует свободный группоид без единичного элемента в алфавите X с операцией *:  $x_i*x_j=x_i{x}_j,$$x_i*a=x_i\left(a\right),$ $a*x_i=\left(a\right)x_i$, для $x_i\in X$ и слов $a\in W$ длины больше 1, $a*b=\left(a\right)\left(b\right)$, для слов $a,b\in W$ степени больше 1.

Неассоциативной свободной алгеброй A (или короче свободной алгеброй) над полем F с системой свободных образующих X называется алгебра над F, линейной базой которой служит множество всех возможных слов относительно символов из X, при этом умножение индуцируется умножением в Г(X ). Всякий элемент свободной алгебры, отличный от нуля, однозначно представим в виде суммы конечного числа различных слов (называемых членами этого элемента), взятых с отличными от нуля коэффициентами из поля F. Умножение элемента свободной алгебры на некоторый элемент α поля F сводится к умножению на α коэффициентов всех членов элемента.

Свободная алгебра с точностью до изоморфизма определяется числом свободных образующих X (мощностью X ). Система элементов свободной алгебры называется примитивной, если ее можно дополнить до множества свободных образующих этой алгебры. Другими словами, подмножество M ненулевых элементов свободной алгебры A шраерова многообразия называется примитивной системой элементов, если существует множество свободных образующих алгебры A, содержащее подмножество M. Сами элементы такой системы называются примитивными элементами.

В начале 2000-х был получен критерий примитивности системы и отдельного элемента [7], [8, 12.5.1], см. также [1], [2]:

Система $a_1,a_2,\dots ,a_r$ элементов свободной неассоциативной алгебры A примитивна тогда и только тогда, когда матрица $(\partial (a_1),\dots ,\partial (a_r\left)\right)$ обратима слева над алгеброй $U\left(A\right)$. В частности, элемент $a\in A$ является примитивным тогда и только тогда, когда существуют такие элементы $m_1,\dots ,m_n\in U\left(A\right)$, что

${\sum }_{i=1}^n{m}_i\frac{\partial a}{\partial x_i}=1$ .

Здесь U(A) – универсальная мультипликативная обертывающая алгебра для алгебры A, являющаяся свободной ассоциативной алгеброй с множеством свободных образующих $S=\left\{r_w,l_w|w\in W\right\}$ – операторов левого и правого умножения на слова из W.

Пусть I_A – свободный правый U(A)-модуль с базисом $y_1,\dots ,y_n$.

Линейное отображение $\mathcal{D}:A\to I_A,$ заданное формулами $\mathcal{D}\left(x_i\right)=y_i,i=1\dots n$, $\mathcal{D}\left(ab\right)=\mathcal{D}\left(a\right)b+a\mathcal{D}\left(b\right),$

где $a,b\in A$, является универсальным дифференцированием алгебры A. Частные производные $\frac{\partial }{\partial x_i}$

элемента f ∈ A однозначно определяются соотношением  $\mathcal{D}\left(f\right)=\sum _{i=1}^n{y}_i\frac{\partial f}{\partial x_i}.$

2. Векторные подпространства

Элементы свободной алгебры над полем F можно представлять как элементы арифметического векторного пространства – кортежи, составленные из коэффициентов членов. Можно рассматривать свободную алгебру как прямую сумму ее подпространств. При этом можно использовать различные разложения на прямые слагаемые в зависимости от задачи.

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

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

Примеры:

• Мономы длины 0 (элементы поля в алгебрах с 1). Таблица n⁰ = 1 коэффициентов записывается одним числом.
• x_i – мономы длины 1. Таблица n¹ = n коэффициентов записывается вектором длины n.
• x_i x_j – мономы длины 2. Таблица n² коэффициентов записывается квадратной матрицей n × n.
• Ассоциативные мономы x_i x_j x_s длины 3. Таблица n³ коэффициентов записывается кубом n × n × n коэффициентов.
• Неассоциативные мономы $\left(x_i{x}_j\right)x_s$, $x_i\left(x_j{x}_s\right)$ длины 3. Две таблицы n³ коэффициентов записываются $C_{k-1}=C_2=2$ ((k – 1)-е число Каталана) кубами n × n × n коэффициентов.

Единицу и слова свободного группоида также удобно представлять в виде многомерных таблиц. Обозначим $\overline{x}\times \dots \times \overline{x}$  k-мерную таблицу, в которой на месте (i₁, ..., i_k) находится элемент x_i1... x_ik. В неассоциативном случае расстановка скобок в произведении $\overline{x}\times \dots \times \overline{x}$ совпадает с расстановкой скобок в элементе x_i1... x_ik. Считая умножение между таблицами коэффициентов и слов, как и сложение между элементами одного из подпространств, описанных выше, поэлементным, получим более удобное представление элементов свободных алгебр.

Примеры:

• элемент длины 2 свободной алгебры:

$\begin{array}{c}h=a_{x_1}{x}_1+\dots +a_{x_n}{x}_n+a_{x_1{x}_1}{x}_1{x}_1+\\ +a_{x_1{x}_2}{x}_1{x}_2+\dots +a_{x_n{x}_n}{x}_n{x}_n\\ h=\left(\begin{array}{c}{a}_{x_1}{x}_1\\ ⋮\\ a_{x_n}{x}_n\end{array}\right)+\left(\begin{array}{ccc}{a}_{x_1{x}_1}{x}_1{x}_1& \cdots & a_{x_1{x}_n}{x}_1{x}_n\\ ⋮& \ddots & ⋮\\ a_{x_n{x}_1}{x}_n{x}_1& \cdots & a_{x_n{x}_n}{x}_n{x}_n\end{array}\right)\\ h=\left(\begin{array}{c}{a}_{x_1}\\ ⋮\\ a_{x_n}\end{array}\right)\overline{x}+\left(\begin{array}{ccc}{a}_{x_1{x}_1}& \cdots & a_{x_1{x}_n}\\ ⋮& \ddots & ⋮\\ a_{x_n{x}_1}& \cdots & a_{x_n{x}_n}\end{array}\right)\overline{x}\times \overline{x}=\\ =a_{\overline{x}}\cdot \overline{x}+a_{\overline{x}\times \overline{x}}\cdot \overline{x}\times \overline{x}\end{array}$

• элемент длины 3 свободной неассоциативной алгебры:

$\begin{array}{c}h=a_{\overline{x}}\cdot \overline{x}+a_{\overline{x}\times \overline{x}}\cdot \overline{x}\times \overline{x}+\\ +a_{\overline{x}\times (\overline{x}\times \overline{x})}\cdot \overline{x}\times (\overline{x}\times \overline{x})+a_{(\overline{x}\times \overline{x})\times \overline{x}}\cdot (\overline{x}\times \overline{x})\times \overline{x}\end{array}$

Здесь $a_{\left(\right(\dots )\dots )}$ – все коэффициенты при мономах длины k с указанной скобочной структурой, записанные в виде k-мерной таблицы. Такие таблицы неудобно записывать для k > 2, но достаточно легко представлять.

3. Векторные “слои”

Покажем еще одно разложение свободной алгебры в прямую сумму на примере следующей алгебры. Рассмотрим алгебру с базой из всех возможных слов заданной длины k с заданным распределением скобок с алфавитом из n символов:

$A=\left\{\sum _{(i_1,\dots ,i_k)}{\alpha }_{i_1\dots i_k}\left(\right(x_{i_1}\dots x_{i_j})\dots x_{i_k})\right\},$

${\alpha }_{i_1\dots i_k}\in F$, $x_i\in X,0⩽i_s⩽n.$ Зафиксируем один из символов, стоящий на j-м месте, и будем рассматривать все возможные комбинации остальных символов слова. В зависимости от значения зафиксированного символа будут получаться прямые слагаемые:

$A\cong \left\{\sum {\alpha }_{i_1\dots 1\dots i_k}\left(\right(x_{i_1}\dots x_1)\dots x_{i_k})\right\}\oplus \dots$

$\dots \oplus \left\{\sum {\alpha }_{i_1\dots n\dots i_k}\left(\right(x_{i_1}\dots x_n)\dots x_{i_k})\right\}.$

В случае 2-мерных матриц мы оперируем понятиями “строк” и “столбцов” матрицы. Пронумеруем стороны этих таблиц так, что в 2-мерном случае строки индексируются вдоль первой стороны, а столбцы – вдоль второй. В трехмерном случае вдоль первой стороны индексируются горизонтальные “слои”.

Пусть $a_{\left(\right(\overline{x}\dots \times \overline{x})\dots \overline{x})}$ – k-мерная таблица коэффициентов. Обозначим i-й “слой” этой таблицы, индексированный по одной из ее сторон, $a_{\left(\right(\overline{x}\dots \times x_i)\dots \overline{x})}$. Это $(k-1)$-мерная таблица с коэффициентами.

Для примера покажем, как записывается представление $A_{\overline{x}\times (\overline{x}\times \overline{x})}\cdot \overline{x}\times (\overline{x}\times \overline{x})$ при $\overline{x}=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$. Размер таблицы равен 2 × 2 × 2. Запишем ее “слои”, индексированные вдоль третьей стороны (“глубины”), в виде расширенных квадратных матриц.

$\begin{array}{c}{A}_{\overline{x}\times (\overline{x}\times \overline{x})}=\left(A_{\overline{x}\times (\overline{x}\times x_1)}|A_{\overline{x}\times (\overline{x}\times x_2)}\right)=\\ =\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_1\left(x_2{x}_1\right)}\\ a_{x_2\left(x_1{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_1\left(x_2{x}_2\right)}\\ a_{x_2\left(x_1{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)\\ \overline{x}\times (\overline{x}\times \overline{x})=\\ =\left(\begin{array}{cc}{x}_1\left(x_1{x}_1\right)& x_1\left(x_2{x}_1\right)\\ x_2\left(x_1{x}_1\right)& x_2\left(x_2{x}_1\right)\end{array}|\begin{array}{cc}{x}_1\left(x_1{x}_2\right)& x_1\left(x_2{x}_2\right)\\ x_2\left(x_1{x}_2\right)& x_2\left(x_2{x}_2\right)\end{array}\right)\end{array}$

Отметим, что часто удобнее рассматривать “слои”, индексированные вдоль первой стороны (“высоты”):

$A_{x_1\times (\overline{x}\times \overline{x})}=\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_1\left(x_2{x}_1\right)}\\ a_{x_1\left(x_1{x}_2\right)}& a_{x_1\left(x_2{x}_2\right)}\end{array}\right)$

$A_{x_2\times (\overline{x}\times \overline{x})}=\left(\begin{array}{cc}{a}_{x_2\left(x_1{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\\ a_{x_2\left(x_1{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)$

4. Техника свободного дифференциального исчисления в свободных неассоциативных алгебрах

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

Рассмотрим теперь в алгебре $U\left(A\right)$ частные производные, представленные в описанном выше виде:

$\begin{array}{c}\frac{\partial }{\partial x_i}=a_{x_i}+a_{x_i\times \overline{x}}\cdot r_{\overline{x}}+a_{\overline{x}\times x_i}\cdot l_{\overline{x}}+\\ +a_{x_i\times (\overline{x}\times \overline{x})}\cdot r_{\overline{x}\times \overline{x}}+a_{\overline{x}\times (x_i\times \overline{x})}\cdot r_{\overline{x}}\times l_{\overline{x}}+\\ +a_{\overline{x}\times (\overline{x}\times x_i)}\cdot l_{\overline{x}}\times l_{\overline{x}}+a_{(x_i\times \overline{x})\times \overline{x}}\cdot r_{\overline{x}}\times r_{\overline{x}}+\\ +a_{(\overline{x}\times x_i)\times \overline{x}}\cdot l_{\overline{x}}\times r_{\overline{x}}+a_{(\overline{x}\times \overline{x})\times x_i}\cdot l_{\overline{x}\times \overline{x}}+\mathrm{...}\end{array}$

Из матриц $a_{\left(\right(\overline{x}\dots \times x_i)\dots \overline{x})}$ можно составить векторы длины n, сгруппировав их по структуре слов алгебры $U\left(A\right)$.

Например, для мономов вида $l_{\overline{x}}\times r_{\overline{x}}$ получим вектор слоев коэффициентов:

$\left(\begin{array}{c}{a}_{(\overline{x}\times x_1)\times \overline{x}}\\ \dots \\ a_{(\overline{x}\times x_n)\times \overline{x}}\end{array}\right)$

или, что то же самое, исходную матрицу коэффициентов при $(\overline{x}\times \overline{x})\times \overline{x}$, с другим порядком сторон.

4.1. Пример дифференцирования группы мономов длины 3 с двумя образующими

Определим “вклад” группы $a_{\overline{x}\times (\overline{x}\times \overline{x})}\cdot \overline{x}\times (\overline{x}\times \overline{x})$ при $\overline{x}=\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$ 

в выражения для частных производных.

$\begin{array}{c}\mathcal{D}(a_{\overline{x}\times (\overline{x}\times \overline{x})}\cdot \overline{x}\times (\overline{x}\times \overline{x}\left)\right)=\\ =a_{\overline{x}\times (\overline{x}\times \overline{x})}\cdot \left(\begin{array}{c}\mathcal{D}\left(x\right)\times (\overline{x}\times \overline{x})+\\ +\overline{x}\times \left(\mathcal{D}\right(\overline{x})\times \overline{x})+\overline{x}\times (\overline{x}\times \mathcal{D}(\overline{x}\left)\right)\end{array}\right)=\\ =\left(\begin{array}{c}{a}_{x_1\times (\overline{x}\times \overline{x})}\\ a_{x_2\times (\overline{x}\times \overline{x})}\end{array}\right)\cdot \mathcal{D}\left(x\right)\times r_{\overline{x}\times \overline{x}}+\left(\begin{array}{c}{a}_{\overline{x}\times (x_1\times \overline{x})}\\ a_{\overline{x}\times (x_2\times \overline{x})}\end{array}\right)\times \\ \times \mathcal{D}\left(x\right)\times r_{\overline{x}}\times l_{\overline{x}}+\left(\begin{array}{c}{a}_{\overline{x}\times (\overline{x}\times x_1)}\\ a_{\overline{x}\times (\overline{x}\times x_2)}\end{array}\right)\cdot \mathcal{D}\left(x\right)\times l_{\overline{x}}\times l_{\overline{x}}\end{array}$

$\begin{array}{c}\left(\begin{array}{c}\frac{\partial }{\partial x_1}\\ \frac{\partial }{\partial x_2}\end{array}\right)=\left(\begin{array}{c}{a}_{x_1\times (\overline{x}\times \overline{x})}\\ a_{x_2\times (\overline{x}\times \overline{x})}\end{array}\right)\cdot r_{\overline{x}\times \overline{x}}+\left(\begin{array}{c}{a}_{\overline{x}\times (x_1\times \overline{x})}\\ a_{\overline{x}\times (x_2\times \overline{x})}\end{array}\right)\times \\ \times r_{\overline{x}}\times l_{\overline{x}}+\left(\begin{array}{c}{a}_{\overline{x}\times (\overline{x}\times x_1)}\\ a_{\overline{x}\times (\overline{x}\times x_2)}\end{array}\right)\cdot l_{\overline{x}}\times l_{\overline{x}}\end{array}$

$\begin{array}{c}\left(\begin{array}{c}{a}_{x_1\times (\overline{x}\times \overline{x})}\\ a_{x_2\times (\overline{x}\times \overline{x})}\end{array}\right)=\left(\begin{array}{c}\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_1\left(x_2{x}_1\right)}\\ a_{x_1\left(x_1{x}_2\right)}& a_{x_1\left(x_2{x}_2\right)}\end{array}\right)\\ \left(\begin{array}{cc}{a}_{x_2\left(x_1{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\\ a_{x_2\left(x_1{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)\end{array}\right)~\\ ~\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_1\left(x_2{x}_1\right)}\\ a_{x_2\left(x_1{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_1\left(x_2{x}_2\right)}\\ a_{x_2\left(x_1{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)\end{array}$

$\begin{array}{c}\left(\begin{array}{c}{a}_{\overline{x}\times (x_1\times \overline{x})}\\ a_{\overline{x}\times (x_2\times \overline{x})}\end{array}\right)=\left(\begin{array}{c}\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ a_{x_1\left(x_1{x}_2\right)}& a_{x_2\left(x_1{x}_2\right)}\end{array}\right)\\ \left(\begin{array}{cc}{a}_{x_1\left(x_2{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\\ a_{x_1\left(x_2{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)\end{array}\right)~\\ ~\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ a_{x_1\left(x_2{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_2\left(x_1{x}_2\right)}\\ a_{x_1\left(x_2{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)\end{array}$

$\begin{array}{c}\left(\begin{array}{c}{a}_{\overline{x}\times (\overline{x}\times x_1)}\\ a_{\overline{x}\times (\overline{x}\times x_2)}\end{array}\right)=\left(\begin{array}{c}\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ a_{x_1\left(x_2{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\end{array}\right)\\ \left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_2\left(x_1{x}_2\right)}\\ a_{x_1\left(x_2{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)\end{array}\right)~\\ ~\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ a_{x_1\left(x_1{x}_2\right)}& a_{x_2\left(x_1{x}_2\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_2{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\\ a_{x_1\left(x_2{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)\end{array}$

Так, дифференцирование 8 неассоциативных мономов с заданной скобочной структурой дает нам 24 ассоциативных монома алгебры U(A) в выражениях частных производных

5. Критерий примитивности элемента длины 2 и 3 свободной неассоциативной алгебры с двумя образующими

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

Предложение 1. Элемент $h=a\cdot \overline{x}+B\cdot \overline{x}\times \overline{x}+C\cdot (\overline{x}\times \overline{x})\times \overline{x}+D\cdot \overline{x}\times (\overline{x}\times \overline{x}),$ примитивен тогда и только тогда, когда ранг матрицы $\left(a\right|B\left|B^T\right|C\left|C^T\right|D\left|D^T\right)$ больше ранга матрицы $\left(B\right|B^T\left|C\right|C^T\left|D\right|D^T)$.

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

Элемент примитивен тогда и только тогда, когда найдутся такие $m_1,m_2,\dots ,m_n\in U\left(A\right)$, что

$m_1\frac{\partial }{\partial x_1}+m_2\frac{\partial }{\partial x_2}+\dots +m_n\frac{\partial }{\partial x_n}=1.$

Матрица $\left(a\right|B\left|B^T\right|\dots )$ содержит n строк, где n – число свободных образующих. Каждая из строк матрицы соответствует представлению частной производной по одной из переменных в виде многомерных таблиц.

Задача определения примитивности сводится к алгоритму редукции, шагом которого является устранение старших мономов из производных за счет других производных. Поскольку все старшие мономы l_xi и r_xi производных элементов длины 2 (в общем виде будем записывать op_xi) могут быть получены, либо как $a\cdot o{p}_{x_i}=b\cdot (c\cdot o{p}_{x_i}),$ либо как $a\cdot o{p}_{x_i}=(b\cdot o{p}_{x_i})\cdot c,$ возможна только линейная редукция (то есть с коэффициентом из F ). Аналогично, среди мономов производной элемента длины 3 обязательно встретится op_{xi xj} для которого возможна только линейная редукция.

Итак, для редукции используется только умножение на элементы F. В этом случае алгоритм редукции сводится к решению системы линейных уравнений над полем F.

Воспользовавшись критерием Кронекера–Капелли, получаем доказательство утверждения.

Полученное в ходе доказательства утверждение можно сформулировать в виде леммы.

Лемма 1. Если среди членов неассоциативного элемента длины k встречаются мономы вида $x_i\cdot w$ или w · x_i , то среди соответствующих им мономов частных производных встречаются такие, для которых возможна только линейная редукция.

Элемент с такими членами примитивен тогда и только тогда, когда выполняются условия, аналогичные (с учетом большего числа матриц коэффициентов) условиям доказанного критерия примитивности.

Доказательство. К доказанному выше осталось доказать только необходимость выполнения условий. После линейной редукции возможны два случая:

1) одно из выражений частных производных стало константой (то есть элемент примитивен);

2) одно из выражений стало меньшей длины, но не стало константой, другое всё ещё содержит моном вида op_w, из чего следует, что дальнейшая редукция невозможна.

6. Признак примитивности

Полученный для элементов длины 2 и 3 критерий можно обобщить до признака примитивности элементов произвольной длины. Транспонирование матриц при этом заменяется на перестановку сторон таблиц коэффициентов. А вместо ранга матрицы необходимо рассматривать ранг системы векторов, составленных из элементов слоев многомерных таблиц коэффициентов.

Под действие этого признака попадает только случай, когда производится линейная редукция системы частных производных. То есть решается система линейных уравнений:

${\alpha }_1\frac{\partial }{\partial x_1}+\dots +{\alpha }_n\frac{\partial }{\partial x_n}=\mathrm{1,}{\alpha }_1,\dots ,{\alpha }_n\in F.$

7. Оценка числа примитивных элементов с двумя образующими произвольной длины

7.1. Частные производные одной группы мономов

Проиллюстрируем алгоритм расчета числа примитивных элементов на примере рассмотренной выше группы мономов $a_{\overline{x}\times (\overline{x}\times \overline{x})}\cdot \overline{x}\times (\overline{x}\times \overline{x})$. Пусть $\frac{\partial }{\partial x_2}=\alpha +t\frac{\partial }{\partial x_1}$, $\alpha ,t\in F$. Тогда

$\begin{array}{c}\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_1\left(x_2{x}_1\right)}\\ a_{x_2\left(x_1{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_1\left(x_2{x}_2\right)}\\ a_{x_2\left(x_1{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)=\\ =\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_1\left(x_2{x}_1\right)}\\ t{a}_{x_1\left(x_1{x}_1\right)}& t{a}_{x_1\left(x_2{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_1\left(x_2{x}_2\right)}\\ t{a}_{x_1\left(x_1{x}_2\right)}& t{a}_{x_1\left(x_2{x}_2\right)}\end{array}\right)\end{array}$

$\begin{array}{c}\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ a_{x_1\left(x_2{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_2\left(x_1{x}_2\right)}\\ a_{x_1\left(x_2{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)=\\ =\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ t{a}_{x_1\left(x_1{x}_1\right)}& t{a}_{x_2\left(x_1{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_1{x}_2\right)}& a_{x_2\left(x_1{x}_2\right)}\\ t{a}_{x_1\left(x_1{x}_2\right)}& t{a}_{x_2\left(x_1{x}_2\right)}\end{array}\right)\end{array}$

$\begin{array}{c}\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ a_{x_1\left(x_1{x}_2\right)}& a_{x_2\left(x_1{x}_2\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_2{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\\ a_{x_1\left(x_2{x}_2\right)}& a_{x_2\left(x_2{x}_2\right)}\end{array}\right)=\\ =\left(\begin{array}{cc}{a}_{x_1\left(x_1{x}_1\right)}& a_{x_2\left(x_1{x}_1\right)}\\ t{a}_{x_1\left(x_1{x}_1\right)}& t{a}_{x_2\left(x_1{x}_1\right)}\end{array}|\begin{array}{cc}{a}_{x_1\left(x_2{x}_1\right)}& a_{x_2\left(x_2{x}_1\right)}\\ t{a}_{x_1\left(x_2{x}_1\right)}& t{a}_{x_2\left(x_2{x}_1\right)}\end{array}\right)\end{array}$

$\begin{array}{c}{a}_{x_2\left(x_2{x}_2\right)}=t{a}_{x_2\left(x_2{x}_1\right)}=t^2{a}_{x_1\left(x_2{x}_1\right)}=\\ =t{a}_{x_2\left(x_1{x}_2\right)}=t^2{a}_{x_2\left(x_1{x}_1\right)}=\\ =t{a}_{x_1\left(x_2{x}_2\right)}=t^2{a}_{x_1\left(x_1{x}_2\right)}=t^3{a}_{x_1\left(x_1{x}_1\right)},\end{array}$

где t – общий коэффициент пропорциональности между неединичными мономами частных производных. Это равносильно тому, что t – коэффициент пропорциональности при мономах неассоциативной алгебры с одинаковой расстановкой скобок. При выражении $a_{x_2\left(x_2{x}_2\right)}$ через другие коэффициенты его степень равна количеству x₁ в мономе, соответствующем коэффициенту, и обратно, если выражать 

$a_{x_1\left(x_1{x}_1\right)}=\dots =s^3{a}_{x_2\left(x_2{x}_2\right)}.$

7.2. Число примитивных элементов

Полученное правило справедливо для мономов любой длины свободной неассоциативной алгебры над конечным полем. Если матрица коэффициентов при какой-либо группе мономов длины m записывается m-мерной таблицей $\left(a_{i_1{i}_2\dots i_m}\right),$ $i_j\in \left\{\mathrm{1,2}\right\},$ то либо $a_{11\dots 1}=\dots =t^m{a}_{22\dots 2},$ либо $a_{22\dots 2}=\dots =s^m{a}_{11\dots 1}.$ Это позволяет нам для каждой группы мономов задать лишь один из коэффициентов. Остальные получаются умножением на выбранный коэффициент t.

Обозначим через $S_2^k\left(q\right)$ число примитивных элементов длины k свободной неассоциативной алгебры с двумя образующими над конечным полем F_q.

Линейная часть примитивного элемента может быть получена $q^2-1=q(q-1)$ способами.

Для каждого варианта линейной части оценим число способов получения элемента длины k, удовлетворяющего полученным соотношениям. Коэффициент пропорциональности t можно выбрать q способами, при этом в случае t = 0 у нас еще возникает необходимость для каждой группы мономов длины m выбрать $a_{x_2(\dots x_2)}=\dots =t^m{a}_{x_1(\dots x_1)}$ или $a_{x_1(\dots x_1)}=\dots =t^m{a}_{x_2(\dots x_2)}.$ Включив этот выбор в число способов выбора t, получим q + 1 вариант.

Далее оценим число способов выбрать коэффициенты при мономах $x_2(\dots x_2)$ либо $x_1(\dots x_1)$ (в зависимости от выбора t) всех групп длины m. Число вариантов расстановки скобок в мономе длины m равно $(m-1)$-му числу Каталана $C_{m-1}$, число вариантов выбрать в каждой группе коэффициент равно q. В итоге получаем $q^{C_{m-1}}$ вариант. Чтобы длина элемента была равна k, необходимо, чтобы хотя бы один коэффициент при мономах длины k был ненулевым, что даёт нам $q^{C_{k-1}}-1$ вариант выбора коэффициента при мономах длины k. Суммарное число комбинаций коэффициентов для мономов длин $2\dots k-1$ равно $q^{C_1}\cdot \dots \cdot q^{C_{k-2}}=q^{\sum _{m=2}^{k-1}{C}_{m-1}}$.

Итак, мы готовы записать оценку для $S_2^k\left(q\right)$.

$S_2^k\left(q\right)⩾\underset{t}{\underbrace{(q+1)}}\cdot \underset{m=1}{\underbrace{q(q-1)}}\cdot \underset{m=2\dots k-1}{\underbrace{q^{\sum _{m=2}^{k-1}{C}_{m-1}}}}\cdot \underset{m=k}{\underbrace{(q^{C_{k-1}}-1)}}$

Считая, что C₀ = 1, можно сократить запись:

$S_2^k\left(q\right)⩾(q+1)(q-1)q^{\sum _{m=1}^{k-1}{C}_{m-1}}(q^{C_{k-1}}-1).$

7.3. Формулы для некоторых длин

Используя, полученную формулу запишем оценки для некоторых длин:

$S_2^2\left(q\right)=(q+1)(q-1)q^1(q^1-1)=q{(q-1)}^2(q+1)$

$S_2^3\left(q\right)=(q+1)(q-1)q^2(q^2-1)=q^2{(q-1)}^2{(q+1)}^2$

$S_2^4\left(q\right)⩾(q+1)(q-1)q^4(q^5-1)$

$S_2^5\left(q\right)⩾(q+1)(q-1)q^9(q^{14}-1)$

Для $S_2^2\left(q\right)$ и $S_2^3\left(q\right)$ равенство обусловлено тем, что вместо признака можно использовать критерий примитивности.

Правая часть полученной оценки в случае длин 2 и 3 совпадает с формулами подсчета таких элементов, полученными ранее А. А. Чеповским в диссертации [5].

8. Программная реализация алгоритмов

Ранее для исследования примитивных элементов были реализованы алгоритмы[3] работы с примитивными элементами в свободных неассоциативных алгебрах в системе компьютерной алгебры SageMath. Для небольших конечных полей с помощью теста примитивности были посчитаны примитивные элементы небольших длин. Полученные выше формулы дают те же значения для тех же полей и длин.

Описанное представление позволяет оптимизировать алгоритмы работы с примитивными элементами, заменив ресурсоемкие операции на работу с таблицами: вместо символьного дифференцирования производить транспонирование матриц, упростить умножение элементов алгебр.

8.1. Подсчет количества примитивных элементов длины 4 в свободной неассоциативной алгебре с двумя образующими

Выше мы показали, что если элемент содержит один из мономов вида $x\left(x\right(xx\left)\right),$ $x\left(\right(xx\left)x\right),$ $\left(x\right(xx\left)\right)x,$ $\left(\right(xx\left)x\right)x,$ то в алгоритме проверки примитивности элемента будут использованы только линейные редукции. Все такие примитивные элементы можно посчитать по полученной выше формуле. Значит, для получения общего числа примитивных элементов длины 4 необходимо посчитать те, которые требуют умножения на нескалярные элементы алгебры $U\left(A\right)$ в ходе редукции. Все такие элементы будут содержать мономы вида $\left(xx\right)\left(xx\right).$

Найдем частные производные мономов такого вида: 

$\begin{array}{c}\mathcal{D}\left(\right(\overline{x}\overline{x}\left)\right(\overline{x}\overline{x}\left)\right)=r_{\overline{x}\overline{x}}{r}_{\overline{x}}\mathcal{D}\left(\overline{x}\right)+\\ +r_{\overline{x}\overline{x}}{l}_{\overline{x}}\mathcal{D}\left(\overline{x}\right)+l_{\overline{x}\overline{x}}{r}_{\overline{x}}\mathcal{D}\left(\overline{x}\right)+l_{\overline{x}\overline{x}}{l}_{\overline{x}}\mathcal{D}\left(\overline{x}\right).\end{array}$

Пронумеруем получившиеся мономы алгебры U(A) по порядку переменной в мономе $\left(\overline{x}\overline{x}\right)\left(\overline{x}\overline{x}\right),$ по которой при дифференцировании получается $\mathcal{D}\left(\overline{x}\right).$ Получим $1:r_{\overline{x}\overline{x}}{r}_{\overline{x}}$, $2:r_{\overline{x}\overline{x}}{l}_{\overline{x}}$, $3:l_{\overline{x}\overline{x}}{r}_{\overline{x}}$, $4:l_{\overline{x}\overline{x}}{l}_{\overline{x}}$.

Если таблицу мономов вида $\left(\overline{x}\overline{x}\right)\left(\overline{x}\overline{x}\right)$ записать в виде

 

 

то, используя введённые обозначения, частные производные δ/(δx) и δ/(δy) можно записать соответственно таблицами:

 

 

Считая, что

• D – таблица коэффициентов, соответствующих мономам в этих таблицах мономов;
• при использовании ее в качестве коэффициентов при частных производных первый индекс указывает на то, к какой производной относится коэффициент (например, $d_{1ijk}$– коэффициент при некотором мономе δ/(δx), $d_{2ijk}$ а – коэффициент при некотором мономе δ/(δy));
• D^σ – транспонированная таблица коэффициентов, с помощью перестановки σ, то есть $d_{i_1{i}_2{i}_3{i}_4}^{\sigma }=d_{i_{\sigma \left(1\right)}{i}_{\sigma \left(2\right)}{i}_{\sigma \left(3\right)}{i}_{\sigma \left(4\right)}}$;
• из монома $\left(x_1{x}_2\right)\left(x_3{x}_4\right)$ алгебры A получаются следующие мономы алгебры U(A): $r_{x_3{x}_4}{r}_{x_2},$ $r_{x_3{x}_4}{l}_{x_1},$ $l_{x_1{x}_2}{r}_{x_4},$ $l_{x_1{x}_2}{l}_{x_3},$ и соответствующие им перестановки (234), (12334), (321), (4321),

получим следующие выражения частных производных группы мономов $\left(\overline{x}\overline{x}\right)\left(\overline{x}\overline{x}\right)$: $D^{\left(234\right)}{r}_{\overline{x}\overline{x}}{r}_{\overline{x}}+D^{\left(1234\right)}{r}_{\overline{x}\overline{x}}{l}_{\overline{x}}+D^{\left(321\right)}{l}_{\overline{x}\overline{x}}{r}_{\overline{x}}+D^{\left(4321\right)}{l}_{\overline{x}\overline{x}}{l}_{\overline{x}}$. $D^{\left(234\right)}{r}_{\overline{x}\overline{x}}{r}_{\overline{x}}+D^{\left(1234\right)}{r}_{\overline{x}\overline{x}}{l}_{\overline{x}}+D^{\left(321\right)}{l}_{\overline{x}\overline{x}}{r}_{\overline{x}}+D^{\left(4321\right)}{l}_{\overline{x}\overline{x}}{l}_{\overline{x}}$

Если примитивный элемент содержит моном вида $\left(\overline{x}\overline{x}\right)\left(\overline{x}\overline{x}\right),$ частные производные которого требуют редукции, то он не может содержать мономы длины 3. Так как в этом случае в выражения частных производных будут входить мономы вида r_xx или l_xx, которые могут быть редуцированы только такими же мономами. Итак, примитивный элемент длины 4, не подходящий под условия признака примитивности, имеет вид: $A\overline{x}+B\overline{x}\overline{x}+D\left(\overline{x}\overline{x}\right)\left(\overline{x}\overline{x}\right)$.

Также справедливы соотношения для старших мономов, полученные ранее:

$\begin{array}{c}{s}^4{d}_{\left(x_2{x}_2\right)\left(x_2{x}_2\right)}=s^{3}t{d}_{\left(x_2{x}_2\right)\left(x_2{x}_1\right)}=\\ =s^{3}t{d}_{\left(x_2{x}_2\right)\left(x_1{x}_2\right)}=s^{3}t{d}_{\left(x_2{x}_1\right)\left(x_2{x}_2\right)}=\\ =s^{3}t{d}_{\left(x_1{x}_2\right)\left(x_2{x}_2\right)}=s^2{t}^2{d}_{\left(x_2{x}_2\right)\left(x_1{x}_1\right)}=\\ =s^2{t}^2{d}_{\left(x_2{x}_1\right)\left(x_2{x}_1\right)}=s^2{t}^2{d}_{\left(x_1{x}_2\right)\left(x_2{x}_1\right)}=\\ =s^2{t}^2{d}_{\left(x_2{x}_1\right)\left(x_1{x}_2\right)}=s^2{t}^2{d}_{\left(x_1{x}_2\right)\left(x_1{x}_2\right)}=\\ =s^2{t}^2{d}_{\left(x_1{x}_1\right)\left(x_2{x}_2\right)}=s{t}^3{d}_{\left(x_2{x}_1\right)\left(x_1{x}_1\right)}=\\ =s{t}^3{d}_{\left(x_1{x}_2\right)\left(x_1{x}_1\right)}=s{t}^3{d}_{\left(x_1{x}_1\right)\left(x_2{x}_1\right)}=\\ =s{t}^3{d}_{\left(x_1{x}_1\right)\left(x_1{x}_2\right)}=t^4{d}_{\left(x_1{x}_1\right)\left(x_1{x}_1\right)}.\end{array}$

Исходя из этого получим, что подходящих наборов коэффициентов при таких мономах в каждом поле будет $(q+1)(q-1),$ как уже было показано выше.

Посчитаем для некоторых конечных полей для каждого такого набора число примитивных элементов методами компьютерной алгебры.

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

Алгоритм 1. Генерация таблиц коэффициентов для мономов длины 4.

1) подготовить наборы индексов:

1 – 0000;

2 – 1000, 0100, 0010, 0001;

4 – 0111, 1011, 1101, 1110;

5 – 1111;

3 – остальные 6 комбинаций;

2) установить значение множителя $t:=0;$

3) если t > q, перейти к шагу 12;

4) подготовить таблицы-шаблоны с множителями, поместив t ^{k – 1} по индексам набора k; если t = q, то наоборот, по индексам набора k поместить значение t ^{6 – k};

5) установить опорное значение $a:=1;$

6) если $a⩾q,$ перейти к шагу 10;

7) сформировать таблицу коэффициентов как таблицу-шаблон, умноженную на a;

8) увеличить $a:=a+1$;

9) перейти к шагу 6;

10) увеличить $t:=t+1$;

11) перейти к шагу 3;

12) вернуть все сформированные таблицы коэффициентов;

13) завершить алгоритм.

Алгоритм 2. Генерация таблиц коэффициентов для мономов длин 1 и 2.

1) подготовить список из 6 нулевых элементов;

2) установить i := 1;

3) если i > 6 перейти к шагу 11;

4) увеличить элемент i в списке на 1;

5) если значение элемента i меньше q, то перейти к шагу 9;

6) установить элемент i в списке равным 0;

7) увеличить $i:=i+1;$

8) перейти к шагу 3;

9) если в списке есть ненулевые элементы, то сформировать вектор коэффициентов при мономах длины 1 из первых двух элементов списка, матрицу коэффициентов при мономах длины 2 из последних четырех элементов списка;

10) перейти к шагу 2;

11) вернуть все сформированные таблицы коэффициентов;

12) завершить алгоритм.

Алгоритм 3. Проверка примитивности элементов для заданной таблицы коэффициентов при мономах длины 4.

Вход: два выражения p₁ и p₂. На каждом этапе редукция описывается следующими шагами:

1) найти коэффициенты k₁ и k₂, не равные одновременно нулю в соответствующих значениях частных производных для старшего монома;

2) в качестве редуцируемого выражения p₁ выбрать то, в котором найден ненулевой коэффициент;

3) вычислить выражение $p_2:=k_1{p}_2+k_2{p}_1\mathrm{mod}q;$

4) если в выражении p₂ сохранились старшие мономы той же степени, значит редукция невозможна, перейти к шагу 10;

5) найти коэффициенты в соответствующих друг другу группах мономов: k₂ – ненулевые в старших мономах p₂ и k₁ – ненулевые в старших мономах p₁;

6) найти k₂ как $k_1\times k_2$, в качестве нового значения k₂ выбрать любой ненулевой элемент k₂;

7) произвести редукцию  $p_1:=p_2, p_2:=k_1{p}_2+k_2{p}_1\mathrm{mod}q; p_2:=k_1{p}_2+k_2{p}_1\mathrm{mod}q;$

8) если в выражении p₂ сохранились старшие мономы той же степени, значит редукция невозможна, перейти к шагу 10;

9) вернуть p₁, p₂ и завершить алгоритм с кодом УСПЕХ;

10) вернуть исходные выражения, завершить алгоритм с кодом НЕУСПЕХ.

Описанное на шаге 6 алгоритма 3 произведение определим следующим образом. Пусть a – таблица размера $t_1\times t_2\times \dots \times t_{\alpha }$, b – таблица размера $s_1\times s_2\times \dots \times s_{\beta }$. Тогда результатом произведения будет таблица $c=a\times b$ размера $t_1\times t_2\times \dots \times t_{\alpha }\times s_1\times s_2\times \dots \times s_{\beta }$, $t_1\times t_2\times \dots \times t_{\alpha }\times s_1\times s_2\times \dots \times s_{\beta }$ такая, что $c_{i_1\dots i_{\alpha }{j}_1\dots j_{\beta }}=a_{i_1\dots i_{\alpha }}\cdot b_{j_1\dots j_{\beta }}.$

Эта и другие операции с многомерными таблицами реализованы в пакетах NumPy, PyTorch, TensorFlow языка Python. При этом PyTorch и TensorFlow поддерживают вычисления на GPU, что позволяет многократно ускорить обработку больших объёмов данных.

Алгоритм 4. Подсчет примитивных элементов длины 4.

1) перебрать простые числа: 2, 3, 5, 7, 11, ...;

2) с помощью Алгоритма 1 сформировать таблицы коэффициентов при старших мономах по текущему выбранному простому числу;

3) установить счетчик примитивных элементов равным 0;

4) для каждой из таблиц с помощью Алгоритма 2 сформировать таблицы коэффициентов при остальных мономах;

5) произвести с помощью Алгоритма 3 редукцию каждого из элементов пока алгоритм возвращает УСПЕХ;

6) если в какой-то момент одно из возвращаемых Алгоритмом 3 выражений будет ненулевой константой, то элемент примитивен, увеличить счетчик примитивных элементов на 1;

7) вывести по каждому набору коэффициентов старших мономов полученное число примитивных элементов.

В результате работы алгоритма 4 получено, что для каждого набора коэффициентов (вне зависимости от выбранного множителя t и равенства его нулю), число примитивных элементов в простых полях соответственно: F₂ : 3, F₃ : 8, F₅ : 24, F₇ : 48, F₁₁ : 120, ...

Метод неопределённых коэффициентов даёт выражение для этого числа q² – 1. Тогда общее число примитивных элементов с нередуцируемыми линейно частными производными получится ${(q-1)}^2{(q+1)}^2.$

Таким образом, мы получили недостающую часть числа S₂⁴: 

$S_2^4=(q+1)(q-1)q^4(q^5-1)+{(q+1)}^2{(q-1)}^2.$

Источник финансирования

При финансовой поддержке Российского научного фонда, грант 22-11-00052.

Sobre autores

M. Maisuradze

Moscow State University

Autor responsável pela correspondência
Email: maisuradzemv@my.msu.ru

Department of Mechanics and Mathematics

Rússia, Moscow, 119991

А. Mikhalev

Moscow State University

Email: aamikhalev@mail.ru

Department of Mechanics and Mathematics

Rússia, Moscow, 119991

Bibliografia

Arquivos suplementares