|
Уважаемый Mihailm!
Я уже оценил Вашу исключительную доброжелательность и любезность, но теперь у меня сильнейшее искушение этой любезностью злоупотребить.
Дело в том, что вопрос о свойствах левого и правого произведения подстановок не единственный алгебраический вопрос, который меня мучит. Так получилось, что я полез в эту область без должной теоретической подготовки, несколько нечаянных удач меня обольстили, а теперь и остановиться трудно, жаль бросать начатое, хотя понимаю, что рискую насмешить людей, перед глазами недавний пример Сергея Табалевича из Минска, который изобрел алгоритм поиска простых чисел с экспоненциальным временем работы, ослабленную версию решета Эратосфена (кажется, и Вы принимали участие в дискуссии). Пытаюсь утешать себя тем, что пока еще доступен для критики, в состоянии воспринимать мнения более подготовленных людей, не вижу в своих выдумках ничего, что должно опрокинуть всю, всю мировую науку. Словом, ничего революционного, вселенского и основополагающего. Все намного скромнее, мои вопросы более частного и узкого значения.
На сегодня главный из них такой. Имеется некая произвольная подстановка на множестве N элементов и имеется N ее циклических сдвигов (вообще говоря, нетипичное для алгебры понятие, оно чаще встречается в практике программирования. в ассемблере есть даже специальные команды ROR и ROL -правый и левый циклический сдвиги; все элементы смещаются на заданное число шагов, скажем, влево, при этом те, которые слева вышли за границу регистра, помещаются на освободившиеся места справа). Вопрос: каково наибольшее количество различных произведений, если в качестве сомножителей брать подстановки из указанного множества и ограничить число сомножителей тем же числом N. Понятно, что есть N! способов расположить в строке N сомножителей, если каждый используется ровно один раз, и есть N в степени N способов, если эта строка не перестановка, а размещение с повторениями. Также понятно, что в последнем случае все произведения не могут быть различными, потому что всех различных подстановок только N! - между тем число N в степени N всегда больше факториала от N. Однако есть серьезные сомнения в том, что число различных произведений достигает хотя бы N! - это бы значило, что N циклических сдвигов некоторой произвольной подстановки составляют полную систему образующих симметрической группы подстановок. Это весьма, весьма сомнительно. С другой же стороны, случаи, когда сдвиги некоторой подстановки образуют по умножению короткую циклическую подгруппу, очень редки. Простейший пример - единичная подстановка, все ее сдвиги и замыкаются в циклическую подгруппу порядка N. Легко показать, что почти любая другая подстановка, отличающаяся от единичной хотя бы одной транспозицией, имеет другие свойства. Никакие два ее сдвига не принадлежат одной циклической подгруппе, потому что произведение любых двух сдвигов некоммутативно. Из-за этого количество различающихся произведений растет очень быстро, лавиной, темпы роста комбинаторные. Но где этот рост останавливается?
Этот вопрос превышает и мою математическую подготовку, и, вероятно, мои умственные способности. Может, для кого-то он и элементарен, а мне приходится искать какие-то косвенные признаки, например, статистические: получающиеся произведения по своим статистикам, скажем, по средней длине цикла или по количеству неподвижных точек, выглядят так, будто их выбирали наугад из всего множества N! различных. Конечно, это не метод, но у меня другого нет.
Между тем вопрос не пустой. Он вырос из чисто прикладных задач. Если бы удалось доказать, что различных произведений достаточно много - ну, хотя бы не меньше корня квадратного из N! - это позволяло бы довольно смело пользоваться для практических целей некоторыми "плохими" алгебрами, в которых перемножаются комбинаторные объекты разных типов - перестановки на размещения, размещения на перестановки, вообще какие-то строки различной длины. Эти алгебры никогда не будут "хорошими" - они не обладают свойством замкнутости, операнды не принадлежат одному множеству, а значит, в этих алгебрах никогда не будет выполняться требование, чтобы каждое уравнение имело единственное решение. В них всегда будут коллизии, но если вероятность коллизий низка и хорошо оценивается, вся эта механика может оказаться очень и очень полезной во многих приложениях. Как раз такими "нехорошими" алгебрами я занимаюсь уже довольно давно - к сожалению, без необходимой подготовки.
Поэтому всегда буду признателен за любое участие, советы, замечания.
Разумеется, это относится ко всем участникам форума, но в частности меня просто потрясла скорость, с которой Вы, Mihailm, откликнулись на первый мой вопрос об умножении подстановок - получаса не прошло с моего появления на форуме. Фантастика!
Лев Магазаник
|
