Кострикин. Курс алгебры, задачник

[Sinoid]

arseniiv в сообщении #1515632 писал(а):

Как-то так, да.

Только это не избавляет все-таки от возможности того, что существуют какие-то транспозиции в количестве, меньшем $k-1$, произведение которых, взятое в каком-нибудь порядке, даст $k$-цикл.

[arseniiv]

Тут надо наоборот разбирать (до тождественной перестановки) цикл, применяя к нему транспозиции. Сможем ли мы это сделать менее чем за $k - 1$ применений? Применяя транспозицию, либо (a) мы увеличиваем число подвижных точек на 2 (если она коммутирует с циклом), либо (b) на 1 (если она имеет одну общую подвижную точку с циклом), либо (c) циклов становится два и подвижных точек остаётся столько же, либо (d) цикл остаётся один и теряет одну подвижную точку — эти два последних если обе подвижные точки транспозиции были в числе подвижных точек цикла. Сложный случай составляет только размножение циклов неединичной длины (c). Мы можем учесть и слияние циклов при применении транспозиции (в общем взяв все те случаи ☙, которые я перечислял выше), главное что количество подвижных точек ведёт себя хорошим образом — оно никогда не уменьшается больше чем на 1 до тех пор пока мы не применяем транспозицию к себе. Но если у нас в конце осталось $m > 1$ транспозиций, когда-то раньше мы должны были «неоптимальные» $m - 1$ штук народить. В общем я уверен, что доказательство можно организовать красиво-модульно-понятно, учтя сразу всё одновременно.

[Sinoid]

arseniiv в сообщении #1515646 писал(а):

Тут надо наоборот разбирать (до тождественной перестановки) цикл, применяя к нему транспозиции. Сможем ли мы это сделать менее чем за $k - 1$ применений? Применяя транспозицию, либо (a) мы увеличиваем число подвижных точек на 2 (если она коммутирует с циклом), либо (b) на 1 (если она имеет одну общую подвижную точку с циклом), либо (c) циклов становится два и подвижных точек остаётся столько же, либо (d) цикл остаётся один и теряет одну подвижную точку — эти два последних если обе подвижные точки транспозиции были в числе подвижных точек цикла. Сложный случай составляет только размножение циклов неединичной длины (c). Мы можем учесть и слияние циклов при применении транспозиции (в общем взяв все те случаи ☙, которые я перечислял выше), главное что количество подвижных точек ведёт себя хорошим образом — оно никогда не уменьшается больше чем на 1 до тех пор пока мы не применяем транспозицию к себе. Но если у нас в конце осталось $m > 1$ транспозиций, когда-то раньше мы должны были «неоптимальные» $m - 1$ штук народить. В общем я уверен, что доказательство можно организовать красиво-модульно-понятно, учтя сразу всё одновременно.

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

[arseniiv]

Заметьте, что декремент перестановки $\sigma \in S_n$ это $n$ минус просто число вообще всех циклов в ней, включая единичные, так как число единичных это и есть число неподвижных точек. Далее, если надо доказать, что нельзя получить перестановку с декрементом $d$ произведением менее чем $d$ транспозиций, давайте индуктивно покажем, что перемножение $m$ транспозиций даст нам декременты не больше $m$.

База. 0 транспозиций в произведении, и декремент единственной подходящей перестановки $d(()) = n - n = 0$.

Переход. Пусть $m$ транспозиций дают нам перестановки с декрементами не больше $m$. Возьмём произвольную $\sigma$ — значит для неё $c \geqslant n - m$, где $c$ — число всех циклов в $\sigma$. Как мы уже знаем, при действии транспозиции один цикл может разделиться на два (возможно, один или оба единичной длины) или два цикла склеятся в один. В новой перестановке таким образом будет $c' = c \pm 1 \geqslant c - 1 \geqslant n - m - 1$ циклов. Декремент новой перестановки будет $n - c' \leqslant m + 1$, а в этом нам и надо было убедиться!

Вот и всё, даже не так страшно как я думал.

[Sinoid]

arseniiv в сообщении #1515664 писал(а):

База. 0 транспозиций в произведении, и декремент единственной подходящей перестановки $d(()) = n - n = 0$.

Это же здесь единственная подходящая перестановка - это тождественная перестановка $E$? Просто внутренние скобки пустые, вот в голову, глядя на это, и приходит пустая перестановка и всякие подобные вужасы.

arseniiv в сообщении #1515664 писал(а):

Возьмём произвольную $\sigma$

у которой декремент не больше $m$? Правильно? arseniiv, спасибо большое!

[Sinoid]

Sinoid в сообщении #1515695 писал(а):

Это же здесь единственная подходящая перестановка - это тождественная перестановка $E$?

Так нет: декремент тождественной перестановки $n$-ой степени равен $-n$.

[arseniiv]

Sinoid в сообщении #1515695 писал(а):

Это же здесь единственная подходящая перестановка - это тождественная перестановка $E$? Просто внутренние скобки пустые, вот в голову, глядя на это, и приходит пустая перестановка и всякие подобные вужасы.

Ага. Её традиционно в цикловой записи записывают как $()$ — это на самом деле до конца естественно (циклов длины 0 не бывает, если только не считать воистину пустую перестановку, единственный элемент $S_0$, но я что-то боюсь и про неё такое заявлять), но пустой строкой будет обозначать очень неудобно.

Sinoid в сообщении #1515746 писал(а):

Так нет: декремент тождественной перестановки $n$-ой степени равен $-n$.

Странно, должен быть нулём. У вас какое там определение? Я брал в Кострикине в «Основах алгебры» в первом томе, где-то там в задаче 3 после одной из глав о перестановках (или единственной главы? я не смотрел в содержание, просто поискал по слову «декремент» и попал туда) и сверился на всякий случай с написанным на заборе в гугле (что вычесть число вообще всех циклов действительно правильно). Как я замечал там выше, в число всех циклов входят неподвижные точки, каждая считается за один, в итоге для тождественной $n - n = 0$.

-- Пн апр 26, 2021 23:34:54 --

У Кострикина-то отдельно вычитается число циклов и отдельно число неподвижных точек, но в число циклов не входят неподвижные точки. Это часто действительно удобно (например $(12) \ne (23)$ как перестановки и потому как циклы, но $(1)$ и $(3)$ соответствуют одной и той же тождественной перестановке), но здесь удобнее считать одноэлементные циклы присутствующими, так как они делают $c' = c \pm 1$ выполняющимся всегда и довольно быстро проверяемым. Если в $c$ учитывать только циклы длин больше 2, то надо будет отдельно учитывать появление и исчезновение неподвижных точек, и станет в конце концов ясно, что они здесь ведут себя так же как циклы больших длин.

[Sinoid]

arseniiv в сообщении #1515751 писал(а):

Ага. Её традиционно в цикловой записи записывают как $()$ — это на самом деле до конца естественно (циклов длины 0 не бывает, если только не считать воистину пустую перестановку, единственный элемент $S_0$, но я что-то боюсь и про неё такое заявлять), но пустой строкой будет обозначать очень неудобно.

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

Насчет пустой перестановки, да, я даже боюсь вслух произнести название чего-нибудь подобного.

[arseniiv]

Я сам $()$ вероятно впервые встретил, играя с GAP, когда пытался заставить его решить НЛО Рубика за меня (так и не смог и не понял в каком месте была ошибка в моей формализации; потом я нашёл человеческие алгоритмы сборки, но их лень было запоминать, а НЛО оказалось проще разобрать и собрать назад). Но потом встречал ещё где-то.

А пустая перестановка это просто пустая функция, ничего особенного в ней нет (кроме того что можно найти в пустой функции). Это примерно как пустая матрица — единственная матрица размера 0 × 0. Такую матрицу имеет линейный оператор на нульмерном пространстве (не путать с матрицами-столбцами 0 × 1 координат векторов этого пространства и матрицами-строками 1 × 0 координат линейных функций на нём).

[vpb]

Sinoid
На всякий случай хочу спросить: а вы то, что написано в указании к задаче 3.13, доказали ? (а то вдруг нет... ).

[Sinoid]

arseniiv в сообщении #1515751 писал(а):

У вас какое там определение?

Я открыл имеющийся у меня бумажный курс Куроша:

Сейчас сравнил с Кострикиным, да, они совпадают. Я только не учел сказанного в сноске. Теперь все, наконец, совпало. Спасибо большое.

-- 26.04.2021, 23:46 --

vpb в сообщении #1515760 писал(а):

Sinoid
На всякий случай хочу спросить: а вы то, что написано в указании к задаче 3.13, доказали ? (а то вдруг нет... ).

А, да, доказал. Да, там ничего такого нет: просто умножение в лоб и все.

-- 26.04.2021, 23:48 --

arseniiv в сообщении #1515758 писал(а):

НЛО

Почему НЛО?

[vpb]

Sinoid в сообщении #1515762 писал(а):

А, да, доказал. Да, там ничего такого нет: просто умножение в лоб и все.

Так отсюда тотчас следует, что если подстановка $\sigma$ имеет $s$ циклов (считая и неподвижные точки за циклы длины 1), и $\pi$ --- какая-то транспозиция, то $\pi\sigma$ имеет по крайней мере $s-1$ циклов. Значит, произведение $t$ транспозиций имеет по крайней мере $n-t$ циклов (доказательство --- очевидной индукцией по $t$). Поэтому декремент этого произведения --- не больше $t$.

[arseniiv]

(НЛО)

Sinoid в сообщении #1515762 писал(а):

Почему НЛО?

Так оно официально называется, и вот как оно выглядит. Я его называл изначально то ли тарелкой, то ли диском (без коробки купил, видимо?..), но post hoc видно, что дизайн специально сделали напоминающим каноническую летающую тарелку.

Комбинаторно совершенно не чета кубику 3 × 3, но что лень с людьми делает, самостоятельно даже алгоритм для тарелки я не разработал. А с кубиками я вообще плохой.

[Sinoid]

vpb в сообщении #1515778 писал(а):

Значит, произведение $t$ транспозиций имеет по крайней мере $n-t$ циклов (доказательство --- очевидной индукцией по $t$).

А, это потому что изначально при такой договоренности было $n$ циклов: $(1)(2)\ldots(n)$, а потом и пошло: умножили на транспозицию $(i,\, j)$, получили $(i,\, j)(1)(2)\ldots(i-2)(i-1)(i+1)(i+2)\ldots(j-2)(j-1)(j+1)(j+2)\ldots(n)$ - $n-2+1=n-1$ циклов, и т. д. Так?

-- 27.04.2021, 23:43 --

(НЛО)

arseniiv в сообщении #1515787 писал(а):

Комбинаторно совершенно не чета кубику 3 × 3

Вы имели ввиду кубик Рубика 3 × 3 × 3 ?

[arseniiv]

(НЛО)

Sinoid в сообщении #1515866 писал(а):

Вы имели ввиду кубик Рубика 3 × 3 × 3 ?

Да, спасибо, забыл придать ему глубины.