|
Leox
Я не уверен, что из коммутативности умножения двух НАУГАД взятых элементов некоммутативной в целом группы обязательно следует их принадлежность к одной циклической подгруппе. Обратное утверждение справедливо — циклические подгруппы коммутативны всегда. Однако ж, хотя все зайцы млекопитающие, не все млекопитающие зайцы. Если какой-то, наугад взятый млекопитающий, оказался ПОХОЖ на зайца, лучше взять какого-нибудь другого — опять наугад.
С уважением,
Лев Магазаник
-- Сб сен 18, 2010 17:41:34 --
VAL
Я особенно рад тому, что Вы откликнулись на эту тему, потому что в прошлый раз, когда я задавал на форуме такой же наивный вопрос (всего дня три назад), меня отослали к Вашей статье «Два тюремщика» в журнале «Квант» — там я и получил авторитетное подтверждение своим догадкам.
На этот раз я запутался гораздо сильнее. Но случай похожий, опять догадки, хождение в темноте... Null ткнул пальцем в знакопеременную группу, и я про нее вспомнил, но и после этого не вспомнил, что в симметрическую группу степени N вложены как подгруппы симметрические группы меньших степеней, а у двух взятых наугад подстановок могут случайно совпасть неподвижные точки — как раз тот случай, понижение степени на единицу. А есть еще множество вещей, которых я не мог вспомнить, потому что и раньше их не знал и не понимал.
И в жизни бы я не полез в эти дебри, так ведь, понимаете ли, приложения, прикладные задачи... Надо сделать то-то и то-то, и я это делаю с храбростью, происходящей от невежества, а потом уходят многие годы, чтобы понять, что именно я сделал и почему это работает. Какой-нибудь милый вопрос: ах, отчего это такая длинная последовательность символов — и нигде не повторяется? Насилу понял, что она повторяется, только нескоро, раньше солнце и звезды остынут, потому что у нас получился такой очаровательный комбинаторный объект — перестановка всех размещений, мы как раз движемся по какому-то циклу этой перестановки (подстановки) и пытаемся угадать, много ли осталось впереди. Ехать еще долго, есть время подумать, и только тут в голову приходят резонные вопросы: а сколько их всего, всех циклов во всех подстановках, и как они распределены по длине? Ну, как-то догадался, вывел формулу за день, как раз до вечера успел, но ведь никому нельзя признаться, как я ее вывел, надо мной люди смеяться будут, а мне это обидно, я уже не молоденький. Лучше никому не говорить, что я это сам придумал, а сослаться на солидный источник. Вот тут добрые люди и дали ссылку на Вашу статью, VAL. И оказалось, что насчет количества циклов я, к счастью, не наврал.
А в этот раз несомненно наврал. Вынужден это признать. Хотя начало истории такое же, надо было кое-что сделать, я и сделал. Всего-то навсего надо было подобрать какой-нибудь способ перемножать комбинаторные объекты разных типов — перестановки на размещения, размещения на перестановки, вообще какие-то строки различной длины. Всего-навсего, совсем пустяк... Ну, надо так надо, умножаем что угодно на что угодно, это можно. Конечно, алгебры получаются поганенькие, даже и не совсем алгебры, потому что замкнутости нет, операнды не принадлежат одному множеству, и коллизий много — никогда не выполняется условие, чтобы каждое уравнение имело ровно одно решение. Или, например, получается такой однобокий уродец — алгебра, где всякое уравнение однозначно разрешимо относительно одного члена (левого сомножителя) и не имеет однозначного решения для другого члена (правого сомножителя). Можно создать такого уродца, что и назвать его сам затрудняешься — как говорится, «извените у миня труднасти с терминалогией». Ну и ладно, не в словах дело, метод ведь подбирался эпирически, может, и результатов достаточно таких, которые эмпирически достоверны. Авось сойдет для практического пользования? Нет, оказалось, что не сойдет. На практике коллизий никаких, совсем не встречаются. Кажется, что и не встретятся, их надо ждать долго, опять-таки до полного остывания солнца и звезд. Но на этот раз НИКАКИХ обоснований того, что вероятность коллизий низка. Вообще никаких количественных оценок. Просто никаких. Можно эту трудность обойти, использовать другую процедуру, где вероятности прекрасно оцениваются (чего-чего, а различных процедур у нас много), но эта другая процедура громоздкая, неэлегантная и трудоемкая, вычислений больше в 500 раз, а которая процедура быстрая и элегантная — у нее теории никакой. Что-то делает, а как — уму непостижимо. Спустя годы выясняется, что кое-какая теория все же есть. Оказывается, хитрая процедура все-таки сводится к умножению подстановок, только это где-то глубоко спрятано. Оказывается, вопрос о вероятности коллизий сводится к вопросу о том, сколько всего получается различных произведений, если брать в различном порядке множители из некоторого специального набора — этим набором являются все циклические сдвиги какой-то произвольной подстановки, о которой только известно, что она отличается от единичной.
Так сколько их? Какую часть всей группы они покрывают?
Не знаю. Не знаю даже, как правильно задать вопрос.
На этом мои возможности кончаются. Ничего не могу, уже близок к тому, чтобы отказаться от элегантной и темной процедуры в пользу неэлегантной, но ясной.
Ничего не могу, могу только сидеть и громко повторять стихи классика: «Сколько их, куда их гонят, что так жалобно поют...» И ждать, пока кто-нибудь из серьезных алгебраистов пожалеет меня, бедняжку, подскажет что-нибудь.
С уважением,
Лев Магазаник
|
и 
перестановочны, но никакой общей циклической подгруппе 
не принадлежат.
, а иногда что-то меньшее. Я не знаю, какой тут простой критерий и есть ли он вообще.