2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Проверка автоморфизма
Сообщение15.07.2024, 11:50 
Аватара пользователя


26/05/12
1694
приходит весна?
Предположим, что даны таблица умножения конечной группы и некоторая перестановка её элементов. Нужно проверить, является ли эта перестановка автоморфизмом.

По определению, необходимо проверить $$\varphi(ab)=\varphi(a)\varphi(b),\quad a,b\in G$$ где уже дано по условию, что $\varphi:G\rightarrow G$ — биекция. То есть технически для проверки требуется два вложенных цикла, чтобы прогнать это соотношение по всем возможным парам элементов.

Мой вопрос: можно ли это сделать более эффективно?

То есть сделать меньше проверок. Одна очевидная оптимизация заключается в том, что надо проверить, что нейтральный элемент отображается в нейтральный, а из остальных проверок его можно исключить, потому что это будут обычные тождества вида $\varphi(a)=\varphi(a)$. Но меня интересует более серьёзная оптимизация. Например, пусть известны (или посчитаны заранее) порождающие элементы данной группы. Их количество будет не более $O(\log |G|)$. Можно ли воспользоваться ими и проверить только верность соотношений только для пар образующая-произвольный элемент? Тогда сложность операции упадёт с $O(|G|^2)$ до всего лишь $O(|G|\log |G|)$, что будет вполне достаточно для моих целей. Можно ли будет улучшить это дальше проверяя только пары образующая-образующая?

 Профиль  
                  
 
 Re: Проверка автоморфизма
Сообщение15.07.2024, 11:58 
Заслуженный участник
Аватара пользователя


16/07/14
9151
Цюрих
B@R5uk в сообщении #1646353 писал(а):
Можно ли воспользоваться ими и проверить только верность соотношений только для пар образующая-произвольный элемент?
Распишите любой элемент в произведение образующих, и отделяйте их по одному.
B@R5uk в сообщении #1646353 писал(а):
Можно ли будет улучшить это дальше проверяя только пары образующая-образующая?
Нет конечно. Уже для $\matbb Z_5$ - переставьте $3$ и $4$.

 Профиль  
                  
 
 Re: Проверка автоморфизма
Сообщение15.07.2024, 12:21 
Аватара пользователя


26/05/12
1694
приходит весна?
Другими словами. Пусть $$g_k\in G$$ есть образующие группы. Пусть элемент y имеет следующее символьное представление в них $$y=c_1c_2\ldots c_m,\quad c_l\in\left\{g_k\right\}$$ И пусть мы проверили все равенства $$\varphi(ag_k)=\varphi(a)\varphi(g_k),\quad\forall a\in G,\;\forall k$$ Тогда $$\varphi(xy)=\varphi(xc_1c_2\ldots c_m)=\varphi(xc_1c_2\ldots c_{m-1})\varphi(c_m)=\ldots=\varphi(x)\varphi(c_1)\varphi(c_2)\ldots\varphi(c_m)=$$ $$=\varphi(x)\varphi(c_1c_2)\varphi(c_3)\ldots\varphi(c_m)=\ldots=\varphi(x)\varphi(c_1c_2\ldots c_m)=\varphi(x)\varphi(y)$$ То есть мы отщепляем с конца по одной образующей до тех пор, пока не "освободится" первый множитель, а потом уже собираем назад второй множитель, но без первого. В результате получается искомое тождество.

mihaild, большое СПАСИБО за оперативный ответ!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group