Как найти порядок элемента по умножению

Задача про группу перестановок

Sn — группа перестановок длины n.
An — группа чётных подстановок длины n.
Задача:
а) Найти максимально возможный порядок элемента в этой группе.
б) Найти число различных циклических подгрупп максимального порядка в этой группе.

Задачу решить как для Sn, так и для An.

Народ, помогите, пожалуйста! Наш преподаватель категорически отказывается объяснять, как решается эта задача, а без неё я не смогу получить допуск к зачёту. Если не можете написать решение целиком — хотя бы выскажите идею.

Заранее благодарю, Сергей.

Или я чего-то не понимаю, или это зверская задача.
Если воспользоваться теоремой о разложении перестановки в произведение циклов, то легко видеть, что порядок некоторой перестановки есть наименьшее общее кратное длин циклов, на которые она разлагается.
Т. е. если некоторая перестановка длины n разложена в произведение r циклов длины n_1, n_2, n_3, . n_r, то порядок этой перестановки есть НОК(n_1, n_2, n_3, . n_r).
Как максимизировать это число, сходу совершенно не понятно.
Или я что-то прочно забыл?

Надо найти НАИБОЛЬШЕЕ среди всех наименьших общих кратных длин циклов, на которые разлагается перестановка. Но как это сделать — ума не приложу.

А по пункту «б» — вообще не понятно, как подступиться к этой задаче.

К пункту «б».
У кто-то вывел формулу:
N = k * n! / (f(m)*m), где
n — длина перестановки;
m — максимальный порядок подгруппы;
k — количество различных разложений перестановки длины n на циклы, при которых (при разложениях) НОК максимально.
f(n) — функция Эйлера.

Однако есть две неприятные вещи:
1. Формула работает не всегда.
2. Непонятно, откуда в ней взялась функция Эйлера.

Лично у меня есть следующие соображения.
1. Надо найти разложение: k1+k2+. +ks = n, такое что, НОК(k1, k2, . ks) — максимально.
2. Найти, сколькими способами можно заполнить БЕЗ ПОВТОРЕНИЙ s циклов (длины k1, . ks соответственно) n натуральными числами — это и будет количеством различных циклических подгрупп максимального порядка.

Поправьте меня, если я не прав.

Никаких идей нет 🙁

Сергей, но если формула работает не всегда, то это уже не формула :(.
Или у Вас есть надежда ее подправить? Но тогда нужно бы знать, как она получена.

Цитата

Лично у меня есть следующие соображения.
1. Надо найти разложение: k1+k2+. +ks = n, такое что, НОК(k1, k2, . ks) — максимально.
2. Найти, сколькими способами можно заполнить БЕЗ ПОВТОРЕНИЙ s циклов (длины k1, . ks соответственно) n натуральными числами — это и будет количеством различных циклических подгрупп максимального порядка.

Поправьте меня, если я не прав.

Первое — несомненно (но что это дает? — все равно ведь неясно, как считать НОК неизвестных чисел и, тем более, как его максимизировать), второе — сомнительно. Вы уверены ли ли, что разные заполнения соответствуют разным подгруппам?

P.S. Это где ж такой зачет? %(( Это ж ужас! 🙁

В МГТУ им. Либермана, тьфу, Баумана на кафедре «Информационная безопасность». 🙂

Кстати, отдельное «спасибо» Чашкину А.В. за то, что он очень хорошо нам «объяснил» алгебру, а также за то, что мы очень хорошо «умеем» решать задачи. 🙂

Такая задача ставится для небольших n.
n<=20.

В общем случае она явно нерешаемая. 🙂

Сергей, для небольших n все подсчитать несложно.
Просто вручную, перебором (нужно только его верно организовать).
Во всяком случае для пункта а). Про б) я еще не успел подумать, но и там, похоже, все не сложно.
P.S. Не надо больше так, хорошо? А то я вчера весь вечер только и думал, как решить Вашу задачку в общем случае.

Приведена таблица для группы S_n. m — максимальный порядок, f(m) — функция Эйлера. (немного странная запись чисел в таблице вызвана желанием выравнять столбцы)
_n | _m_ |f(m)| соответствующие разбиения n на слагаемые
01 | 001 | 01 | [1]
02 | 002 | 01 | [2]
03 | 003 | 02 | [3]
04 | 004 | 02 | [4]
05 | 006 | 02 | [2, 3]
06 | 006 | 02 | [6], [1, 2, 3]
07 | 012 | 04 | [3, 4]
08 | 015 | 08 | [3, 5]
09 | 020 | 08 | [4, 5]
10 | 030 | 08 | [2, 3, 5]
11 | 030 | 08 | [1, 2, 3, 5], [5, 6]
12 | 060 | 16 | [3, 4, 5]
13 | 060 | 16 | [1, 3, 4, 5]
14 | 084 | 24 | [3, 4, 7]
15 | 105 | 48 | [3, 5, 7]
16 | 140 | 48 | [4, 5, 7]

Для вычисления количества циклических подгрупп максимального порядка при n <=16 можно использовать формулу k*n!/(m * f(m))
Метод разумного перебора, я думаю, позволяет добраться и до 20, но на это мне надо еще где-то час времени, а времени нынче не хватает 🙂 Вот до 16 доходится быстро и легко.

Извините, забыл.
Но решение задачи в общем случае также представляет интерес. 🙂

Кстати, а как быть для An?

Для начала по пункту а).
Нужно, чтобы элемент максимального порядка оказался четной перестановкой — тогда он лежит в A_n. Здесь можно использовать два правила: 1) при перемножении перестановок их четности складываются; 2) четность цикла длины k равна четности числа (k-1).
С учетом этих правил теперь надо искать таки наборы k_1, . k_s, что сумма k_1 + . + k_s = n, НОК(k_1, . k_s) максимально и еще количество четных чисел среди k_1, . k_s само четно (это даст четность перестановки, получаемой перемножением циклов с длинами k_1, . k_s). Т.е. снова получится перебор, только с большим числом условий.

Пусть n — длина перестановки, m — максимальный порядок элемента, и пусть есть k наборов (k_1, . k_s) на которых реализуется максимум.
Для определенности рассмотрим одни такой набор. Посмотрим, сколько из него можно организовать элементов максимального порядка. Фактически нам надо расставить произвольно без повторений числа от 1 до n — это n! способов. Вот только мы некоторые элементы получили по несколько раз из-за того, что циклы (234), (342), (423) — это на самом деле один и тот же цикл. Вообще, цикл длины t был посчитан t раз. Таким образом, каждый максимальный элемент мы посчитали k_1*k_2*. *k_s раз (первый цикл можно «представить» k_1 способами, независимо от него второй цикл можно «представить» k_2 способами и т.д.). Таким образом, число элементов максимального порядка будет равно n!/(k_1*. *k_s) — это для одного набора k_1, . k_s.
Надо такое проделать для каждого из имеющихся k наборов — так мы посчитаем вообще все элементы максимального порядка в группе S_n — получится сумма по всем максимизирующим наборам k_1, . k_s выражения n!/(k_1*. *k_s).
Теперь рассмотрим все циклические группы подгруппы максимального порядка. Каждая такая группа порождена каким-то элементом максимального порядка, причем элементы максимального порядка из разных подгрупп не могут совпадать (иначе совпадали бы сами подгруппы). Но количество порождающих элементов в циклической группе порядка m равно f(m), поскольку если элемент g — порождающий, то элемент g^x будет порождающим если и только если x и m взаимно просты, а количество элементво, взаимно простых с m равно f(m). Итак, если N — число групп, то число элементов максимального проядка равно N*f(m).
Значит, N*f(m) = сумма(n!/(k_1*. *k_s)) по всем максимизирующим (k_1, . k_s).
Заметим теперь еще, что если все k_1, . k_s — попарно взаимно просты, то m = HOK(k_1, . k_s) = k_1*. *k_s. Значит, если в каждом максимизирующем наборе все k_i попарно взаимно просты, то сумма(n!/(k_1*. *k_s)) = k*n!/m, где k — число максимизирующих наборов.
Таким образом, получаем написанную ранее вами формулу
N = k*n!/(m*f(m))
и получаем условия, когда ею можно пользоваться

теория-групп — Элемент с максимальным порядком в кольце

Дано кольцо $%Z_$%. Необходимо найти максимальный порядок элемента по умножению. На данный момент результат следующий: $$ Z_ cong Z_ times Z_ times Z_ times Z_$$ То есть, исходное кольцо изоморфно прямому произведению соответствующих групп. Также получена оценка сверху максимального порядка изоморфной группы: $$ НОК(varphi(2), varphi(3), varphi(7), varphi(13)) = 12 $$ После исследования каждого кольца по отдельности, я сделал следующий вывод: в $% Z_, Z_ $% максимальный порядок 2 (элементы 1 и 2 соответственно), в $% Z_ $% — это 6 (элемент 3), в $% Z_ $% — это 12 (элемент 2). делаем вывод, что элемент $% (1, 2, 3, 2) $% является максимальным по умножению, но я не понимаю, как найти соответствующий элемент в $% Z_ $%? Буду рад, если укажете на неправильные рассуждения, скорее всего, они присутствуют.

задан 25 Фев ’19 1:35

1 ответ

У Вас с содержательной точки зрения почти всё уже сделано, но есть ряд терминологических неточностей. Понятие порядка элемента даётся не для колец, а для групп. С кольцом связана аддитивная группа, о которой здесь речь не идёт, и мультипликативная группа, которая и имеется в виду, так как сказано про умножение. Но не уточнено, из каких элементов она состоит. Если $%R$% — кольцо с единицей, то все его обратимые элементы образуют группу относительно умножения, обозначаемую $%R^$%, и называемую группой обратимых элементов кольца, или его мультипликативной группой.

Для колец вычетов $%mathbb Z_n$% группа $%mathbb Z_n^$% состоит из $%varphi(n)$% элементов — тех остатков, которые взаимно просты с $%n$%.

Кольцо $%mathbb Z_$% в самом деле изоморфно прямому произведению, но не групп, а колец вычетов. В то же время, его мультипликативная группа изоморфна прямому произведению мультипликативных групп сомножителей, то есть $$Z_^cong Z_2^times Z_3^times Z_7^times Z_^.$$ Известно, что для простого $%p$% группа $%mathbb Z_p^$% является циклической, то есть обладает элементом порядка $%varphi(p)=p-1$%. Такие элементы для каждой из компонент Вы указали верно.

Для нахождения элемента порядка 12 в группе $%mathbb Z_^$% можно поступить чуть проще (правда, его не следует называть «максимальным по умножению» — максимален ведь не сам элемент, а его порядок в группе). Берём сначала элемент 2: он имеет требуемый порядок по модулю 13, но его брать нельзя, так как он не взаимно прост с 546. Однако, прибавляя к нему несколько раз 13, мы получаем элемент с тем же свойством. Он имеет порядок 12 по модулю 13, а потому и по «старшему» модулю 546 он не уменьшится. Увеличиться он также не может, так как значение 12 максимально. Итого имеем 2, 15, 28, 41, и на последнем элементе можно остановиться, так как он не делится ни на одно из чисел 2, 3, 7, 13.

Тем не менее, если продолжать Ваше рассуждение, то надо решить систему линейных сравнений $%xequiv1pmod2$%; $%xequiv2pmod3$%; $%xequiv3pmod7$%; $%xequiv2pmod$%.

Способы решения таких систем описаны в учебниках по теории чисел. См., например у Бухштаба. Здесь можно сразу заменить второе и последнее сравнение на условие $%xequiv2pmod$%, записать решение в виде $%x=39y+2$%, и подставить в третье сравнение. Также надо будет учесть нечётность. В итоге должно получиться значение $%x=353$%. Такой остаток существует и единственен по известной теореме (китайская теорема об остатках).

отвечен 25 Фев ’19 3:12

@falcao, подскажите пожалуйста, а как поступать в такой ситуации(звездочки чего-то не показываются, имеются в виду только обратимые элементы):

С первыми двумя множителями прямого произведения все ясно, но вот с третьим как «руками» подобрать элемент порядка $%varphi(7^2)=42$% не очень понятно.

@Квантиль: для построения элемента порядка 42 достаточно построить элементы взаимно простых порядков 2, 3, 7 и перемножить. Для начала берём первообразный корень по модулю 7 — число a=3. Его порядок по модулю 7 равен 6. По модулю 49 порядок делится на 6. Прямая проверка показывает, что здесь он равен 42, то есть нам случайно повезло, и это уже ответ. В общем случае, если вышло 6k, то берём a^k, и это элемент порядка 6. Примером элемента порядка p=7 по модулю p^2 будет 1+p, что проверяется через биномиальную формулу. В конце берём a^k(1+p) mod p^2.

@falcao, добрый вечер. Подскажите, пожалуйста, в примере от Квантиль каким образом поступать далее? Получается, наибольший порядок элемента = 42. Для первой группы из суммы образующий элемент g = 1 (mod 2), для второй – g = 2 (mod 3) , для третьей – g = 3 (mod 49). Итого получаем систему из трёх линейных сравнений. Решением является число x = 101 (mod 294). Но при проверке и возведении икса в степень 42 по модулю 294 не получается единицы… не понимаю, где допускаю ошибку в рассуждениях.

@Kai: ответ 101 правильный. Я только что это проверил. Думаю, Вы просто ошиблись при возведении в степень.

@falcao, благодарю! Если рассматривать вопрос о перечислении всех элементов степени 42, нужно поступить следующим образом: взять 3, имеющую степень 42 по модулю 49, и прибавлять к ней 49. Получается ряд: 52, 101, 150, 199, 248. Из этих чисел только два (101, 199) являются искомыми, так как взаимно просты с модулем. Поправьте, пожалуйста, если допустила ошибку.

@Kai: задача нахождения всех элементов кольца, порядок которых в мультипликативной группе равен 42, достаточно сложна. Таких элементов много (по-моему, штук 36), и их не так просто выписать. И сам метод надо обосновывать — почему выписаны будут все такие элементы? Оба числа 101 и 199 годятся, но это явно не весь «улов».

@falcao, можете рассказать, как Вы получили 36?

Проверил на компьютере. Наверное, можно к этому числу прийти и как-то вручную при помощи стандартной техники. Но выписывать все эти значения — задача явно громоздкая.

Здравствуйте

Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

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

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Максимальный порядок элемента группы подстановок

Задача следующая:
Доказать, что порядок любого элемента группы не превосходит разлагается в произведение независимых циклов длин , то — это функция Эйлера и она вычисляется так: ; Если мы перемножим наибольшую возможную длину цикла число раз (возведем в степень ), то мы получим наибольший возможный порядок подстановки .

Вот тут я застрял — судя по условию задачи, наибольшая возможная длина цикла равна (а такого не может быть), не могу дотумкать, что здесь не так?
Заранее благодарен за любые идеи!

Возьмём, например, . Имеем , и на взаимно-простые слагаемые, а во втором — нет.