О некоторых мерах сложности конечных абелевых групп

Кочергин, В.В.

Автор: Кочергин В.В.
Журнал: Дискретная математика
Том: 27
Номер: 3
Год издания: 2015
Издательство: ФГБУ "Издательство "Наука"
Местоположение издательства: Москва
Первая страница: 25
Последняя страница: 43
DOI: 10.4213/dm1333
Аннотация: Пусть конечная абелева мультипликативная группа $G$ задана базисом $B = \{ a_1, a_2, \ldots , a_q\}$, т.\,е. группа $G$ раскладывается в прямое произведение циклических подгрупп, порожденных элементами множества $B$: $G= \langle a_1 \rangle \times \langle a_2 \rangle \times \ldots \times \langle a_q \rangle.$ Сложность $L(g;B)$ элемента $g$ группы $G$ в базисе $B$ определяется как минимальное число операций умножения, достаточное для вычисления элемента $g$, исходя из элементов базиса $B$ (разрешается многократное использование результатов промежуточных вычислений). Пусть $L(G, B)= \max\limits_{g \in G} L(g; B),$ $ LM(G)= \max\limits_{B} L(G, B),$ $Lm(G)= \min\limits_{B} L(G, B),$ $M(n) = \max\limits_{G \colon |G| \le n} LM(G),$ $m(n) = \max\limits_{G \colon |G| \le n} Lm(G),$ $M_{\hbox{\small ср}}(n) = \left( \sum\limits_{G \colon |G|= n}{ LM(G)}\right)/{A(n)},$ $m_{\hbox{\small ср}}(n) = \left( \sum\limits_{G \colon |G|= n}{ Lm(G)}\right)/{A(n)},$ где $A(n)$~--- количество абелевых групп порядка $n$. В работе получены асимптотические оценки величин $L(G, B)$, $M(n)$, $m(n)$, $M_{\hbox{\small ср}}(n)$ и $m_{\hbox{\small ср}}(n)$.
Добавил в систему: Кочергин Вадим Васильевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ИНХС РАН

О некоторых мерах сложности конечных абелевых группстатья

Прикрепленные файлы