Праблемы групы перастановак
Гэтыя даследаванні задач, якія змяшчаюць нататкі і спасылкі на рашэнні, калі яны існуюць. Існуе таксама спіс старых праблем з маёй хатняй старонкі, калі вы зацікаўлены ў практыкаванняў на групы перастановак, Ёсць шмат у маёй кнізе, і вы можаце знайсці некаторыя далейшыя практыкаванні ў Інтэрнэце. Вы таксама можаце быць зацікаўлены ў групах перастановак рэсурсаў старонку або старонку, прысвечаную праблемам з паперы П. Камерон, Перастановы, стар 205-239 у кнізе Пола Эрдеша і яго матэматыкі. II (рэдакцыя Г. Халас, Л. Ловаса, М. Шымановіч і аў SOS), Боя грамадства матэматычных даследаванняў 11, Шпрингер, Берлін, 2002 год.
Праблема 1. Ці існуе функцыя F (т, р) (дзе першы аргумент з'яўляецца цэлым лікам, а другое простае лік), што калі G з'яўляецца канчатковай групы перастановак які р-групы з арбіты м, кожны з якіх памерам па крайняй меры р F (т, р), то G змяшчае нерухомых кропак свабодная стыхія? (Гэта вельмі старая праблема, а для р = 2, яна няяўна з-за Исбелл ў 1959 годзе.)
СТОП ПРЭС 23 снежні 2008: Элеанора Крестани і Пабла Spiga сцвярджаюць, адмоўнае рашэнне гэтай праблемы. Іншыя навіны пазней...
Праблема 2. Няхай група падстановак на бясконцым X мноства. Існуе градуяваная алгебры [G], звязаных з G наступным чынам: й п аднародных Vn кампанент мноства ўсіх G-інварыянтнай функцый з мноства п-элементных падмноства X з комплекснымі лікамі; множанне вызначаецца правіла, што калі F у Vn, г у Vm, а Да (п + т)-элементнай мноства, то
(FG) (K) = сума F (L) г (KL): L subseteq K, | L | = л.
Пастаянная е функцыі ў V 1 са значэннем 1 не з'яўляецца дзельнікам за нуль. Мы кажам, што G з'яўляецца цэлай, калі [G] з'яўляецца вобласцю цэласнасці, і рашуча ўсё, калі [G] / ЕА [G] з'яўляецца вобласцю цэласнасці. Выказана здагадка, што G з'яўляецца (моцна) за ўсё, калі і толькі калі яно не мае канчатковыя арбіты на X. Пры адсутнасці доказаў гэтай гіпотэзы, можна паказаць наступнае:
Калі групы перастановак G 1 на X 1 і G 2 на 2, X (моцна) цэлая, то G 1 × G 2 (у яго непераходнасць дзеянні на X 1 саюз X 2) (моцна) за ўсё.Заўвага: Морыс Pouzet даказаў, што, калі G не мае канчатковых арбіт, то G з'яўляецца цэлай. Гэта выяўляецца ў тэорыі. Інформ. Appl. 42 (2008), 83-103.
Праблема 3. Няхай S будзе симметрической групы на бясконцым X мноства. Разгледзім твор дзеянне на S 2 X 2, і хай лік арбіт на падмноства памеру п. Задача складаецца ў знаходжанні формулы, або эфектыўным сродкам разліку,.
Лік мае розныя іншыя інтэрпрэтацыі:
- Гэты лік нуля і адзінкі матрыц з адзінкамі п, без якіх-небудзь нулявое колькасць радкоў ці слупкоў, да радкоў і слупкоў перастаноўкі.
- Гэты лік двухдольных графаў с т рэбраў, няма ізаляваных вяршыняў, і адрозніваецца Двухдольныя блок, з дакладнасцю да изоморфизма.
Пачатковыя ўмовы ў паслядоўнасці можна знайсці тут.
Праблема 4. Гэтая праблема звязаная з Драган Marusic і Міхаіл Клін. Яна з'яўляецца ў задачы даследавання з 15-га брытанскага камбінаторныя канферэнцыі. Перастаноўка G групы з'яўляецца 2-замкнёнай, калі любая перастаноўка, якая захоўвае арбіты G на упарадкаваных пар належыць G. Праблема: ёсць 2-замкнёная транзітыўных група, не якая змяшчае неадзінкавасці полурегулярны падгрупе?
(Не кожная транзітыўных група падстановак змяшчае неадзінкавасці полурегулярны падгрупы; найменшы контрпример мае ступень 12.)
Заўвага: Майкл Giudici мае некаторыя частковыя вынікі па гэтай праблеме, у тым ліку сцвярджэнне, што кожная мінімальная нармальная падгрупа любы контрпример да гіпотэзы непераходнасць. Гл.:
- PJ Камерон, М. Giudici, Г. А. Джонса, WM Кантар, М. Х. Клін, Д. і Л. А. Marusic Nowitz, Аб транзітыўных груп перастановак без полурегулярных падгруп, J. London Math. Soc. (2) 66 (2002), 325-333.
- М. Giudici, квазипримитивного групы без нерухомых кропак элементаў простага парадку, J. London Math. Soc. (2) 67 (2003), 73-84.
. Праблема 5 базай для групы перастановак G ўяўляе сабой паслядоўнасць кропак, поточечно стабілізатар ідэнтычнасці, гэта тупіковых калі няма сэнсу ў паслядоўнасці усталёўваецца стабілізатар сваіх папярэднікаў. Група G называецца групай IBIS, калі любыя дзве неприводимые базы маюць аднолькавую колькасць элементаў. Калі гэта ўмова выканана, то тупіковых баз асновы матроид (і наадварот). Гэта занадта шмат, каб папрасіць класіфікацыі IBIS груп (так як, напрыклад, любы полурегулярны група IBIS), але ці можна класіфікаваць матроиды, якія могуць узнікнуць?
Звярніце ўвагу, дададзеная 22 лістапада 2001 года: матроиды ўключае ўсе тыя, представимых над канчатковымі палямі (з кожнага элемента замененыя д паралельных элементаў, дзе д парадак палёў). Гл. задачу 18 ніжэй для атрымання дадатковай інфармацыі.
Праблема 6. Макивер і Нэймана, Quart.. J. Math (2) 38 (1987), 473-488, паказаў, што падгрупа симметрической групы Sn можа быць спароджаная не больш чым п / 2 элементаў, пры ўмове, што п не менш за 4. Праблема: Дайце эфектыўны алгарытм знайсці такі генератарнай ўстаноўкі, пераважна "он-лайн" алгарытм (той, які, улічваючы невялікую генератарнай ўстаноўку для H і перастановай г, знаходзіць эфектыўна невялікі генератарнай ўстаноўкі для групы, спароджанай Н і г).
Праблема 7. Марціна Лиебек і Анэр Шалев паказалі, што існуе абсалютная канстанта з, што амаль просты прымітыўнай канчатковай групы перастановак, якая не сіметрычнай або знаказменных групы, якія дзейнічаюць на падмноства ці частак, або класічнай групы, якая дзейнічае на подпространствах ці дадатковыя пар подпространств ў сваім натуральным модулі, мае базу памерам з. Ці азначае гэта зацвярджэнне правесці з = 5 (калі мы дазволім канчатковае лік больш выключэнняў)?
Заўвага ад 2007/07/13: У цяперашні час даказана Бернесс і інш, што сцвярджэнне справядліва і для з = 6, з адным выключэннем, група Мацье M 24..
Праблема 8. Няхай транзітыўных група падстановак на мностве X. Для кожнай арбіты Oi групы С на X 2, мы звязваем аснове матрыцы Ai, чый ўезд ху роўная 1, калі (х, у) знаходзіцца ў Ой, інакш 0. Матрыц Ai прамежак алгебру, якая централизатором алгебры перастаноўкі G групы.
Подалгебра алгебры централизатора які змяшчае адзінкавую матрыцу і спараджаецца сіметрычнымі нуля і адзінкі матрыц Базэ-Mesner алгебра асацыятыўнай схемы на мностве X, і G дзейнічае як група автоморфизмов гэтай схемы аб'яднання. Існуе заўсёды хоць бы адну такую подалгебру, а менавіта прамежак я і СА, дзе J ёсць усе одна матрыца. Мы называем гэта подалгебра або асацыяцыі схема трывіяльная.
Праблема: Для якіх транзітыўных груп падстановак ці праўда, што адзіная схема, асацыяцыю інварыянтнай адносна G з'яўляецца трывіяльнай?
Гэты клас груп ўключае ў сябе 2-аднародных груп. Любая такая група павінна быць прымітыўнай, і (калі не 2-аднародных) альбо дыяганальнага тыпу, або амаль проста.
Прыклады, якія не з'яўляюцца 2-аднастайныя ўсё ж існуюць. Некаторыя з іх могуць быць знойдзены ў табліцы 3.5.1 ІА Faradzev, М. Х. Клін, М. Я. Музычук, "Сотавая кольцаў і груп автоморфизмов графаў", стар 1-152 ў ходзе расследавання ў алгебраічнай тэорыі камбінаторныя аб'ектаў (рэдакцыя І. А. Faradzev, А. А. Іваноў, М. Х. Клін і AJ Woldar), Kluwer, Дордрехт, 1994 год. Самы маленькі ў групе PSL (3,3), якія дзейнічаюць на сумежных класах PO (3,3); гэтая група ступені 234. (Я ўдзячны Леанард Soicher за гэтую спасылку).
Няма такой групы дыяганальных тып вядомы, і праблема прыняцця рашэння аб любой такой групе існуе, застаецца адкрытым. Ёсць ні з двума ці трыма простымі фактарамі ў іх цокаль. Гл.:
- PP Алехандро, Р. Бейлі, і П. Камерон, Асацыяцыя схем і груп перастановак, дыскрэтная матэматыка. 266 (2003), 47-67.
- П. Камерон, кагерэнтныя канфігурацыі, схемы адносін, і групы падстановак, стар 55-71 ў групах, камбінаторыка і геаметрыя (рэдакцыя А. А. Іваноў, МВт Лиебек і Дж. Saxl), World Scientific, Сінгапур, 2003 год.
Праблема 9. засмучэнне праблемы.
Няхай D (да, п) долю засмучэнняў ў сіметрычным Sn групы па сваім дзеянні на да-мностваў. Тады д (да, п) імкнецца да мяжы (да) пры п, якая імкнецца да бясконцасці. (Так, напрыклад, (1) = е-1 -. Гэта звычайная "засмучэнне праблема") ці (к) манатонна імкнуцца да 1 пры да імкнецца да бясконцасці?
Праблема 10. Вядома, што для любой канчатковай групы G, калі X (G, п) ёсць лік (немеченого) графаў на п вяршынях, група автоморфизмов якога ўтрымоўвае G, а ў (G, п) лік, група автоморфизмов Менавіта G, то стаўленне ў (G, п) / х (G, п) імкнецца да мяжы пры п, якая імкнецца да бясконцасці.
Праблема: Ці азначае гэта вынікам правядзення для трохвалентны графаў? А як жа іншыя спецыяльныя класы графаў, такіх як моцна рэгулярных графах?
Праблема 11. вектар Паркер канчатковай групы перастановак G з'яўляецца п-кі якіх да-я кампанента лік арбіт G на мностве да-цыклаў, якія адбываюцца ў элементах G.
Калі G мае той жа вектар Паркер, як група Фробениуса (адпаведна 2-транзітыўнай групы), гэта група Фробениуса (адпаведна 2-транзітыўнай групы)?
Праблема 12. Ці з'яўляецца наступныя праўда?
Калі P з'яўляецца 2-групай, якая не з'яўляецца элементарнай абелевой, то некаторыя не адзінкавы элемент цэнтра P ўяўляе сабой квадрат.Адказ на гэтае пытанне адмоўны. Самы маленькі контрпримеры маюць парадак 128, і Ёсць два з іх. Гэта быў знойдзены Аляксандр Hulpke і Андрэас Caranti. Аляксандр ўмове наступным прыкладзе ў GAP:
Разрыў> G: = SmallGroup (128,36); разрыў> г: = цэнтр (г); групы ([F6, F7]) разрыў> г: = List (ConjugacyClasses (г), прадстаўнік);; разрыў> з: = фільтраваныя (г, г-> Order (я)> 2);; разрыў> Спіс (з, заказ); [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ] прабел> Устанавіць (Спіс (з, я-> я ^ 2)); [f4, f5, f4 * f7, f5 f6 *, f3 * f4 * f5, f3 * f4 f5 * * f6, f3 * f4 f5 * * f7, f3 * f4 f5 * * * f6 f7] прабел> Спіс (прозвішча, я-> я ў г); [хлусня, хлусня, хлусня, хлусня, хлусня, хлусня, хлусня, ілжывае]Калі няма, то наступнае больш слабое зацвярджэнне дакладна?
Калі P з'яўляецца 2-групай, якая не з'яўляецца элементарнай абелевой, а Q з'яўляецца адным з асноўных падгрупа без P, то ёсць элемент, які ляжыць ў якім спалучанае Q якое плошчы.Авиноам Ман таксама прапанаваў вышэй групы ў якасці магчымага контрпример да другое пытанне. Тым не менш, Стыў Линтон і Джон Мюрэй і праверыў, што няма асноўнага падгрупа без Q, для якой ён контрпример. Так што пытанне застаецца адкрытым.
Рашэнне (13 верасня 2004 г.): Адказ на другое пытанне таксама адмоўны. Пабла Spiga выявілі, што група парадку 128 з генератарамі (1,2,7,3) (4,8) (5,11) (6,9) (10,14) (12,16,13,15), (1,4,7,5) (2,8) (3,11) (6,13,14,12) (9,15) (10,16) і (1,6) (2,9, 3,10) (4,12,5,13) (7,14) (8,15) (11,16) ёсць контрпример. Сапраўды, у гэтай групе мноства элементаў з нерухомых кропак супадае з мноствам квадратаў. Гэтая група SmallGroup (128836) у ГАП бібліятэкі.
Матывацыі пытанне, ці з'яўляецца вяршыня-транзітыўных трохвалентнага графа абавязкова мае полурегулярны автоморфизм парадку больш за 2, у цяперашні час застаецца адкрытым. (Але гл. задачу 23).
Праблема 13. Вядома, што, калі G з'яўляецца групай перастановак, у якіх кожны неадзінкавасці элемент фіксуе менавіта да кропак, то альбо G мае фіксаваны набор памераў да, або G з'яўляецца адной з канчатковых спіс груп (пры зададзеным да). Праблема ў тым, каб знайсці добрую верхнюю мяжу (па к) для парадкаў груп у гэтым спісе, вядома.
Напрыклад, калі да = 2, групы чатырохгранныя, октаэдрические і икосаэдрических груп, якія дзейнічаюць на вяршыні, рэбры і грані адпаведных шматкантовікаў. (Кожны кручэнне восі, так што толькі дзве нерухомыя кропкі ў гэтай акцыі.) Так што правільная адзнака 60. (Гэта тэарэма Ивахори, Дж. Fac. Sci., Univ. Токіо 11 (1964), 47-64.)
Верхняя мяжа па да быў знойдзены С. Франка, Аб групах перастановак канчатковага тыпу, еўрапейскія Дж. камбінаторыка 22 (2001), 821-837.
Праблема 14. Няхай канчатковая група, автоморфизм G, а X полупрямое твор G на групу, спароджаныя. Выкажам здагадку, што кожны элемент X не ў G мае просты парадак р.
Адсюль вынікае, што централизатор ў G з'яўляецца р-групай. Хай яго заказ будзе вечара.
Тэарэмы Кегеля (Мф. 75 З. (1961), 373-376) паказвае, што G нильпотентна. Тады тэарэма хухры (Мц 38 нататкі (1985), 652-657) паказвае, што G мае нармальную падгрупу, нильпотентности і індэксам абмежаваныя функцыі р і м.
Ці праўда, што ступень нильпотентности G абмежавана функцыяй ад р і м?
Гэтае пытанне быў урэгуляваны ў сцвярджальна Андрэй Jaikin, выкарыстоўваючы тэарэмы Э. хухры, Аб лакальна нильпотентных групах, якія дапускаюць расшчапляюць автоморфизм простага парадку, Матем. сб. 130 (1986), 120-127.
Праблема 15. Няхай Sn і РП адпаведна симметрической групы (мноства ўсіх перастановак) і мноства ўсіх разбіцця на мностве [1.. п]. Існуе функцыя F ад Sn РП які замяняе любы перастаноўкі па падзеле адпавядае свой цыкл раскладання.
() Ці ёсць эфектыўны спосаб вырашыць мноства разбіцця з'яўляецца чынам пры F падгрупы Sn?
(Б) Калі G і Н падгрупы Sn такое, што F (G) = F (H), то G і H маюць аднолькавы парадак. Ці з'яўляюцца яны абавязкова ізаморфныя?
Заўвага Паведамленні 19 мая 2000 года: адказ на пытанне (б) адмоўны. Имонн О'Браэн паказаў, што Ёсць дзве пары груп парадку 64 (нумары 19 і 111, і 94 і 249, у спісы ў магме і GAP), якія дзейнічаюць transivitely на 16 пунктаў, такіх, што дзве групы, у кожнай Пара спараджаюць аднолькавыя наборы цыклу частак. Вы можаце знайсці праграму GAP, каб пераканацца ў гэтым.
Глядзіце П. Камерон, раздзелаў і перастановак, дыскрэтная матэматыка. 291 (2005), 45-54.
Праблема 16. Няхай G з'яўляецца падгрупы симметрической групы Sn. Для я = 0,..., п хай пі верагоднасць таго, што выпадковы элемент G мае роўна я нерухомых кропак, і хай Fi быць лік арбіт G на я-ок розных кропках. Гэтыя дзве паслядоўнасці вызначаюць адзін аднаго. На самай справе, Н. Бостане, В. Дамброўскі, Т. Foguel, PJ Гиз, Дж. Ливитт, ДТ АСЕ і Д. Джэксан, сувязі ў алгебры 21 (1993), 3259-3275, паказаў, што калі
Р (х) = Sum пі х і F (х) = Sum Fi XI / я!, То
F(x) = P(x+1).
Зараз разгледзім лінейны аналаг. Хай падгрупа поўнай лінейнай групы GL (п, дз). Для я = 0,..., п хай пі верагоднасць таго, што нерухомыя пункту выпадковага элемента формы дакладна я-мернае подпространство, і хай Fi быць лік арбіт G на лінейна незалежных я-ок. Зноў две паслядоўнасці вызначаюць адзін аднаго.
Праблема: Экспрэс сувязь паміж гэтымі двума паслядоўнасцямі ў тэрмінах вырабляюць функцый.
Заўвага: Гэтая праблема зараз вырашана (2 жніўні 2000). Гэта ўсяго толькі выпадку выяўлення права вызначэння д-аналагі! Гл.:
- П. Камерон, С. Маджыд, Плецены лініі і падлік нерухомых кропак GL (D, F дз), Сувязь у алгебры 31 (2003), 2003-2013 гг.
- П. Камерон, Нерухомыя кропкі і цыклы, стар 49-60 у канчатковыя геаметрыі: Працы Чацвёртай Востраў Шыпы канферэнцыі (рэдакцыя А. Blokhuis, СПР Хиршфельд, Д. Jungnickel і Т мае JA), Kluwer, Бостан, 2001 год.
Праблема 17. (старая праблема зноў)
Няхай група падстановак на бясконцым X мноства. Выкажам здагадку, што G з'яўляецца oligomoprhic, гэта значыць G мае толькі канечны лік (скажам, п) арбіты на мностве п-элементных падмноства X. Дугалд Макферсан, Proc. London Math. Soc. (3) 46 (1983), 471-486, паказаў, што калі G прымітыўная на Х (захоўвае няма нетрывіяльных адносіны эквівалентнасці), але не вельмі-транзітыўных набору ((гэта значыць, п> 1 для некаторага п), то паслядоўнасць (п) расце ў геаметрычнай прагрэсіі, гэта значыць, Нтзир (п) 1 / п> 1. Гэтыя два здагадкі ставяцца да ўсяго гэтую праблему, хоць аналагічныя задачы могуць быць пастаўлены з прымітыўнасці расслабленым.
- Ці праўда, што ІТ (п) 1 / п існуе для любой групы С?
- Што такое найменшае магчымае значэнне Нтзир? (Макферсон ніжняя мяжа 21 / 5 была палепшаная Ф. Merola прыкладна да 1,324. Найменшы вядомы паказчык складае 2).
- Якая найменшая лімітавая кропка мноства значэнняў Нтзир?
Дадатковая інфармацыя аб такіх паслядоўнасцяў даступныя ў маім аглядзе.
Праблема 18.
Базай для групы перастановак паслядоўнасці кропак, стабілізатар ідэнтычнасці, гэта тупіковых калі няма сэнсу усталёўваецца стабілізатар сваіх папярэднікаў. Кэмеран і Фон-Дэр-Флаасс, Еўропы. Дж. камбінаторыка 16 (1995), 537-544, званыя групы перастановак група IBIS, калі ўсе неприводимые базы маюць аднолькавы лік элементаў, яны паказалі, што тупіковых асновы група IBIS з'яўляюцца асновай матроида.
Праблема: Якая сувязь паміж Татта мнагачлена матроидом і цыкл індэкса групы перастановак?
Вядома, што часам спачатку вызначае другі, а часам і наадварот. Магчыма, ёсць гаджэт, які абагульняе і іншае! Глядзіце П. Камерон, індэкс цыклу, перечислитель вага і Татта Палінай, Электронныя камбінаторыка Дж. 9 (1) (2002), # N2 (10pp).
Праблема 19.
Наколькі вялікі самы вялікі антицепь падгруп симметрической групы Sn? Дакладней, ацэнка / Sn, дзе з'яўляецца памер самага вялікага антицепь і С. М. агульная колькасць падгруп.
Праблема 20.
Хай L (G) падгрупу рашотцы канчатковай групы G. Ёсць наступныя сапраўдным або ілжывых? Выкажам здагадку, што Булевы рашоткі У (п) падмноства п-элементнага мноства ўкладваецца як адказваць-полурешетка L (G), і выкажам здагадку, што п з'яўляецца максімальным з гэтым уласцівасцю. Тады існуе ўкладанне У (п), а адказваць-полурешетка, так, што найменшы элемент У (п) з'яўляецца нармальнай падгрупы ў G.
Заўвага: група кватернионов Q 8 паказвае, што мы не можам зрабіць найменшы элемент У (п) адпавядаюць ідэнтычнасці ў цэлым.
Праблема 21.
Хай Z (G) пазначае цыкл індэкс перастаноўкі G група, і хай Fn * (G) лік арбіт G на мноства ўсіх п-кі яе перастаноўкі дамена.
Няхай G і Н перастаноўка груп, якія дзейнічаюць на мноствах X і Y адпаведна. Мы лічым, G × H, як група падстановак на X × Y. У нас ёсць
- Z (G × H) = Z (G) аб Z (H), дзе сі пра Sj = (а НАК (I, J)) Нод (I, J), і аперацыя працягваецца мультыплікатыўны і адытыўная;
- Fn * (G × H) = Fn * (G) Fn * (H).
Рашэнне: Рашэнне Даніэлю Gewurz. Глядзіце артыкул Даніэлю Gewurz, Франчэска Merola і мяне ў дыскрэтнай матэматыцы 308 (2008), 386-394; DOI: 10.1016/j.disc.2006.11.054
Праблема 22.
Няхай група Фробениуса з ядром N Фробениуса і фробениусовы дадаткам H, якія маюць парадкаў п і ч адпаведна. Колькасць элементаў N ў выглядзе х 1,..., хп. Цяпер Xij быць п х п матрыца з (K, L) ўваход роўная магутнасці перасячэння XI -1 Hxk і х -1 Hxl. Звярніце ўвагу, што Xii = прывітанне той час як, я і ў розныя, Xij з'яўляецца нулявой адну матрыцу.
Ці праўда, што
Сума да XikXkj = nXij + г (ч-1) J,дзе J з'яўляецца ўсё-адна матрыца?
Рашэнне: Гэтая праблема цяпер вырашаецца станоўча (але я страціў рашэнне...)
Праблема 23. Праблема З 20 у спісе старых праблем мае адмоўнае рашэнне, наступную задачу (з-за Джона Шихана і я, BCC праблема 17/12) адкрыта зноў.
Ці праўда, што вяршыня-трохвалентны граф мае полурегулярны автоморфизм (адзін з усімі цыкламі ж памеру) парадку, большага чым 2?
Заўвага: Гэта ў цяперашні час вырашана сцвярджальна: гл П. Камерон, Дж. Шихан і П. Spiga, Еўропы. Дж. камбінаторыка 27 (2006), 924-930; DOI: 10.1080/00927870701404812, і больш моцны вынік быў дадзены Цай Хэн Лі, Тр. Амер. Мат. Soc. 136 (2008), 1905-1910.
Праблема 24. Няхай група падстановак ступені л. Базавы памер G называецца найменшую колькасць б (G) кропак, стабілізатар ідэнтычнасці; падзел лік G з'яўляецца самым маленькім памерам мноства S кропак, што для любых двух розных пунктаў х, у, існуе з у S такая, што х і ў ляжаць у розных арбітах стабілізатар з.
Відавочна, бы (G) <= S (G). Ці праўда, што, калі G прымітыўная, але не 2-транзітыўнай, то S (G) <= Ь (З) § п?
Глядзіце камбінаторыка Даследчая група адзначае, па гэтай праблеме ( PDF файл ).
Задача 25. Няхай F-мноства паслядоўнасцяў F станоўчых лікаў, N-й член ёсць лік арбіт на п-кі розных элементаў бясконцай групы перастановак.
IS F замкнёна адносна поточечной множання?
Я мяркую, што адказ будзе "не". У прыватнасці, хай Р паслядоўнасці (1,2,4,10,26,...) якога я-й член ёсць лік рашэнняў г 2 = 1 у симметрической групе ступені п. Гэтая паслядоўнасць належыць F, але я мяркую, што паслядоўнасць (1,4,16,100,676...), члены якіх з'яўляюцца квадратамі тэрміны ў гэтай паслядоўнасці няма ў F.
Заўвага: мноства паслядоўнасцяў падліку арбіты групы перастановак на ўсіх набораў замкнёны адносна поточечного множання. Больш таго, мноства паслядоўнасцяў падліку арбіты на п-кі розных элементаў для груп з тым уласцівасцю, што стабілізатар канчатковае мноства выпраўленняў якіх-небудзь дадатковых кропак замкнёна адносна поточечного множання.
Далейшае заўвагу: адказ наогул "няма": калі G з'яўляецца стабілізатарам кропкі ў симметрической групе, паслядоўнасць пачынаецца за 2, 3, 4,..., але група з 4 арбіты на кропкі павінна быць не менш 12 арбіты на упарадкаваных пар розных кропак. Гэта цяжэй для транзітыўных груп (дзе магчыма контрпример прыведзены ў пытанні), і тым больш для прымітыўных груп.
. Праблема 26 я выказаў здагадку ў 1972 годзе, што існуе функцыя F з наступным уласцівасцю: Хай канчатковая прымітыўная група перастановак, з ранг г, і хай S быць subrank з G, максімальны ранг стабілізатарам кропкі на любым з сваіх арбіт. Тады альбо
- G мае базу памерам 2, або
- г <= F (S).
Найбольш яркі прыклад я ведаю, гэта пашырэнне 2 н-мернае вектарнае прастору над GF (2), група диэдра парадку 2 (2 N +1), гэта мае ранг 2 л і 2 л subrank -1 1. Так што, магчыма гіпотэза дакладная з лінейнае функцыі.
Праблема 27. Няхай S будзе мноства элементаў симметрической групы Sn. Гэта не заўсёды правільна, што кожны элемент у групе, спароджанай S можна запісаць у выглядзе слова ў S даўжыні абмежаванага полиномом ад п. (Take S для одноплодной элемент якой мае максімальны магчымы парадак у Sn.)
Праблема: Калі ў групе, спароджанай S змяшчае нерухомых кропак свабодная стыхія, мы можам заўсёды знойдзеце той, які ёсць слова полиномиально абмежаванай даўжыні?