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

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

  • автор:

Указать элемент максимального порядка в группе обратимых элементов

Author24 — интернет-сервис помощи студентам

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

1. Указать элемент максимального порядка в группе обратимых элементов Z462 (*) кольца Z462 (и Z462 (*) и Z462 это остатки от деления по модулю 462). Доказать что его порядок действительно максимален.
Понял, что порядок это степень, при возведении в которую элемента получается 1 но как сделать задачу непонятно.

94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:

В группе GL2(Q) найти элемент конечного порядка, отличный от нейтрального
В группе GL2(Q) найти элемент конечного порядка, отличный от нейтрального

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

Сколько элементов порядка 4 в группе
Сколько элементов порядка 4 в \mathbb^* Мне кажется, что таких элемента два. А какие?

Сколько элементов порядка 6 содержится в группе?
Сколько элементов порядка 6 содержится в группе D2(C), где Dn(F)- группа невырожденных диагональных.

2719 / 1773 / 187
Регистрация: 05.06.2011
Сообщений: 5,134

1. Как понимаю, только полный перебор. Ну, не всех, естественно, остатков, только взаимно простых с 462. Опять же, если , то 25 можно не проверять. Метод не для ручного счёта, естественно.
Максимальная степень — делитель (посмотри функцию Эйлера), хотя это не сильно сокращает перебор. Впрочем, если дойдёшь до степени, большей наибольшего нетривиального делителя, значит, дальше можно не считать.

Эксперт по математике/физике

4166 / 3038 / 914
Регистрация: 19.11.2012
Сообщений: 6,182

Есть метод для счета в уме. Замечаем, что 462=2*3*7*11. По китайской теореме об остатках на языке колец

Тогда мультипликативная группа заданного кольца изоморфна прямому произведению мультипликативных групп сомножителей. Отсюда максимальный порядок это 30. Ну и указать элемент порядка 30 не составляет труда.
Например 5. Как проверить? А по каждому модулю 2,3,7,11 поочередно.

87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь

В данной квадратной матрице порядка 17 указать индексы всех элементов с наименьшим значением
В данной квадратной матрице порядка 17 указать индексы всех элементов с наименьшим значением

В данной квадратной целочисленной матрице порядка 17 указать индексы всех элементов с наибольшим значением
В данной квадратной целочисленной матрице порядка 17 указать индексы всех элементов с наибольшим.

Или воспользуйтесь поиском по форуму:

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

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

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

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

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

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

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

Задача следующая:
Доказать, что порядок любого элемента группы S_nне превосходит e^<n/e>\approx 1.44^n» /></p><div class='code-block code-block-8' style='margin: 8px 0; clear: both;'>
<!-- 8theinternet -->
<script src=

Двигаюсь в следующем направлении: если подстановка \sigmaразлагается в произведение независимых циклов длин p_1,p_2. p_n, то ord(\sigma)=LCM\<p_1,p_2. p_n\>» /> (LCM — наименьшее общее кратное). Стало быть, нужно найти такое разбиение множества n, что мощности элементов разбиения взаимно просты, т.к. в этом случае НОК равно произведению мощностей, след. максимально. Далее, как известно, число таких целых чисел k, что <img decoding=— это функция Эйлера \varphi(n)и она вычисляется так: \varphi(n)=n\displaystyle\prod_

<p>(1-\frac</p>
<p>)» />, где p — все простые делители n. В таком случае <img decoding=; Если мы перемножим наибольшую возможную длину цикла n/eчисло раз (возведем в степень n/e), то мы получим наибольший возможный порядок подстановки \sigma.

e

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

Re: Максимальный порядок элемента группы подстановок
05.08.2010, 17:00

Заслуженный участник

А, функция Ландау, да-да. Короче так. Ваши рассуждения о взаимно простых циклах остроумны и красивы (и даже дают это чёртово n/e), но не имеют отношения к делу. Проще надо, гораздо проще. Наибольшая длина цикла, очевидно, равна n; но такой цикл получится всего один. А если попробовать два, три.

Re: Максимальный порядок элемента группы подстановок
06.08.2010, 12:50
JMH в сообщении #342727 писал(а):

Стало быть, нужно найти такое разбиение множества n, что мощности элементов разбиения взаимно просты, т.к. в этом случае НОК равно произведению мощностей, след. максимально.

Возьмём, например, $n=33$. Имеем $33 = 2 + 31$, $\text<НОК>(2,31) = 62$» />. С другой стороны, <img decoding=и $\text<НОК>(9,24) = 72 > 62$» />. Однако в первом случае берётся разложение <img decoding=на взаимно-простые слагаемые, а во втором — нет.

Re: Максимальный порядок элемента группы подстановок
06.08.2010, 20:35
Профессор Снэйп в сообщении #342897 писал(а):

Возьмём, например, $n=33$. Имеем $33 = 2 + 31$, $\text<НОК>(2,31) = 62$» />. С другой стороны, <img decoding=и $\text<НОК>(9,24) = 72 > 62$» />. Однако в первом случае берётся разложение <img decoding=на взаимно-простые слагаемые, а во втором — нет.

Вы правы и это еще один гвоздь в крышку гроба моей попытки решения Я все пытаюсь сообразить в чем состоит суть подсказки ИСН : ясно что нужно искать максимальное НОК разбиения множества n, но в голову приходит только самая грубая оценка $n!\approx n*ln (n)$; как получить $e^<n/e>$» /> догадаться не получается</p>
<p><b>Re: Максимальный порядок элемента группы подстановок</b><br />
06.08.2010, 21:30<br />
<b>JMH в сообщении #342993</b> писал(а):<br />
все пытаюсь сообразить в чем состоит суть подсказки ИСН.</p>
<p>Да он очень простую вещь предлагает:</p><div class='code-block code-block-13' style='margin: 8px 0; clear: both;'>
<!-- 13theinternet -->
<script src=

$ \begin</p>
<p> \text = \\ \max\limits_> \max \< \text(x_1,\ldots, x_k) : x_1, \ldots, x_k \in \mathbb,\, x_1 + \ldots + x_k = n \> \leqslant \\ \max\limits_> \max \< x_1 \cdot \ldots \cdot x_k : x_1, \ldots, x_k \in \mathbb,\, x_1 + \ldots + x_k = n \> \leqslant \\ \max\limits_> \max \< x_1 \cdot \ldots \cdot x_k : x_1, \ldots, x_k \in \mathbb,\, x_1, \ldots, x_k > 0,\, x_1 + \ldots + x_k = n \> = \\ \max\limits_> \left( \frac \right)^k \leqslant \max\limits_<k \in \mathbb,\, k > 0> \left( \frac \right)^k = e^<\frac> \end $» /><br />Спрашивайте, если что-то вдруг непонятно</p>
<p>— Сб авг 07, 2010 00:39:49 —</p><div class='code-block code-block-14' style='margin: 8px 0; clear: both;'>
<!-- 14theinternet -->
<script src=

$ \lim\limits_<n \to \infty></p>
<p>Кстати, понятно, что<br /> \frac>> = 1 $» /><br />Так что оценка в пределе точна.</p>
<h2>Вычисление порядка элемента в группе</h2>
<p>Пусть [math]G[/math] — группа, [math]a \in G[/math] . Требуется найти порядок элемента [math]a[/math] .</p>
<h3>Решение</h3>
<p>По следствию из теоремы Лагранжа порядок элемента является делителем порядка группы. Таким образом достаточно рассмотреть [math]a^n[/math] , где [math]n \in X[/math] , [math]X[/math] — делители порядка группы.</p><div class='code-block code-block-15' style='margin: 8px 0; clear: both;'>
<!-- 15theinternet -->
<script src=

Алгоритм

  1. Найти все делители [math]|G|[/math] перебором от 1 до [math]\sqrt<|G|>[/math]
  2. Для каждого делителя [math]n[/math] проверить значение [math]a^n[/math] . Наименьший [math]n[/math] , такой что [math]a^n = e[/math] , является порядком элемента [math]a[/math] в группе.

Алгоритмическая сложность

Перебор от [math]1[/math] до [math]\sqrt<|G|>[/math] выполняется за [math]O(\sqrt<|G|>)[/math] . Возведение [math]a[/math] в степень [math]n[/math] выполняется за [math]O(\log n)[/math] . Следовательно время выполнения [math]O(\sqrt <|G|>\cdot \log<|G|>)[/math] .

Порядок элемента

Порядок элемента в теории групп — наименьшее положительное целое [math]\displaystyle< m >[/math] , такое что [math]\displaystyle< m >[/math] -кратное групповое умножение данного элемента [math]\displaystyle< g \in G >[/math] на себя даёт нейтральный элемент:

Иными словами, [math]\displaystyle< m >[/math] — количество различных элементов циклической подгруппы, порождённой данным элементом. Если такого [math]\displaystyle< m >[/math] не существует (или, эквивалентно, число элементов циклической подгруппы бесконечно), то говорят, что [math]\displaystyle< g >[/math] имеет бесконечный порядок. Обозначается как [math]\displaystyle< \mathrm(g) >[/math] или [math]\displaystyle< |g| >[/math] .

Изучение порядков элементов группы может дать сведения о её структуре. Несколько глубоких вопросов о связи порядка элементов и порядка группы содержатся в различных проблемах Бёрнсайда, некоторые из них остаются открытыми.

Основные свойства

Порядок элемента равен единице тогда и только тогда, когда элемент является нейтральным.

Если всякий не нейтральный элемент в [math]\displaystyle< G >[/math] совпадает со своим обратным (то есть [math]\displaystyle< g^2 = e >[/math] ), то [math]\displaystyle< \mathrm(a) = 2 >[/math] и [math]\displaystyle< G >[/math] является абелевой, поскольку [math]\displaystyle< ab=(ab)^=b^a^=ba >[/math] . Обратное утверждение в общем случае неверно: например, (аддитивная) циклическая группа [math]\displaystyle< \Z_6 >[/math] целых чисел по модулю 6 — абелева, но число 2 имеет порядок 3:

Для любого целого [math]\displaystyle< k >[/math] тождество [math]\displaystyle< g^k = e >[/math] выполнено тогда и только тогда, когда [math]\displaystyle< \mathrm(g) >[/math] делит [math]\displaystyle< k >[/math] .

Все степени элемента бесконечного порядка имеют также бесконечный порядок. Если [math]\displaystyle< g >[/math] имеет конечный порядок, то порядок [math]\displaystyle< g^k >[/math] равен порядку [math]\displaystyle< g >[/math] , делённому на наибольший общий делитель чисел [math]\displaystyle< \mathrm (g) >[/math] и [math]\displaystyle< k >[/math] . Порядок обратного элемента совпадает с порядком самого элемента ( [math]\displaystyle< \mathrm(g) = \mathrm(g^) >[/math] ).

Связь с порядком группы

Порядок любого элемента группы делит порядок группы. Например, в симметрической группе [math]\displaystyle< S_3 >[/math] , состоящей из шести элементов, нейтральный элемент [math]\displaystyle< e >[/math] имеет (по определению) порядок 1, три элемента, являющихся корнями из [math]\displaystyle< e >[/math] — порядок 2, а порядок 3 имеют два оставшихся элемента, являющихся корнями элементов порядка 2: то есть, все порядки элементов являются делителями порядка группы.

Частично обратное утверждение верно для конечных групп (теоретико-групповая теорема Коши): если простое число [math]\displaystyle< p >[/math] делит порядок группы [math]\displaystyle< G >[/math] , то существует элемент [math]\displaystyle< g \in G >[/math] , для которого [math]\displaystyle< \mathrm(g) =p >[/math] . Утверждение не выполняется для составных порядков, так, четверная группа Клейна не содержит элемента порядка четыре.

Порядок произведения

В любой группе [math]\displaystyle< \mathrm(ab) = \mathrm(ba) >[/math] .

Не существует общей формулы, связывающей порядок произведения [math]\displaystyle< ab >[/math] с порядками сомножителей [math]\displaystyle< a >[/math] и [math]\displaystyle< b >[/math] . Возможен случай, когда и [math]\displaystyle< a >[/math] , и [math]\displaystyle< b >[/math] имеют конечные порядки, в то время как порядок произведения [math]\displaystyle< ab >[/math] бесконечен, также возможно, что и [math]\displaystyle< a >[/math] , и [math]\displaystyle< b >[/math] имеют бесконечный порядок, в то время как [math]\displaystyle< \mathrm(ab) >[/math] конечен. Пример первого случая — в симметрической группе над целыми числами перестановки, задаваемые формулами [math]\displaystyle< a(x) = 2-x, b(x) = 1-x >[/math] , тогда [math]\displaystyle< ab(x) = x-1 >[/math] . Пример второго случая — перестановки в той же группе [math]\displaystyle< a(x) = x+1, b(x) = x-1 >[/math] , произведение которых является нейтральным элементом (перестановка [math]\displaystyle < ab(x) = \mathrm>[/math] , оставляющая элементы на своих местах). Если [math]\displaystyle< ab = ba >[/math] то можно утверждать, что [math]\displaystyle< \mathrm(ab) >[/math] делит наименьшее общее кратное чисел [math]\displaystyle< \mathrm(a) >[/math] и [math]\displaystyle< \mathrm(b) >[/math] . Следствием этого факта является, что в конечной абелевой группе порядок любого элемента делит максимальный порядок элементов группы.

Подсчёт по порядку элементов

Для данной конечной группы [math]\displaystyle< G >[/math] порядка [math]\displaystyle< n >[/math] , число элементов с порядком [math]\displaystyle< d >[/math] ( [math]\displaystyle< d >[/math] — делитель [math]\displaystyle< n >[/math] ) кратно [math]\displaystyle< \varphi(d) >[/math] , где [math]\displaystyle< \varphi >[/math] — функция Эйлера, дающая число положительных чисел, не превосходящих [math]\displaystyle< d >[/math] и взаимно простых с ним. Например, в случае [math]\displaystyle< S_3 >[/math] [math]\displaystyle< \varphi(3) = 2 >[/math] , и имеется в точности два элемента порядка 3; при этом данное утверждение не даёт никакой полезной информации относительно элементов порядка 2, поскольку [math]\displaystyle< \varphi(2) = 1 >[/math] , и очень ограниченную информацию о составных числах, таких как [math]\displaystyle< d=6 >[/math] , поскольку [math]\displaystyle< \varphi(6)=2 >[/math] , и в группе [math]\displaystyle< S_3 >[/math] имеется нуль элементов порядка 6.

Связь с гомоморфизмами

Гомоморфизмы групп имеют свойство понижать порядок элементов. Если [math]\displaystyle< f: G \to H >[/math] является гомоморфизмом, и [math]\displaystyle< g \in G >[/math] — элемент конечного порядка, то [math]\displaystyle< \mathrm(f(g)) >[/math] делит [math]\displaystyle< \mathrm(g) >[/math] . Если [math]\displaystyle< f >[/math] инъективно, то [math]\displaystyle< \mathrm(f(g)) = \mathrm(g) >[/math] . Этот факт может быть использован для доказательства отсутствия (инъективного) гомоморфизма между двумя какими-либо заданными группами. (Например, не существует нетривиального гомоморфизма [math]\displaystyle< h: S_3 \to \Z_5 >[/math] , поскольку любое число, за исключением нуля, в [math]\displaystyle< \Z_5 >[/math] имеет порядок 5, а 5 не делит ни один из порядков 1, 2 и 3 элементов [math]\displaystyle< S_3 >[/math] .) Другим следствием является утверждение, что сопряжённые элементы имеют одинаковый порядок.

Литература

Для улучшения этой статьи желательно:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *