Квазислучайная группа

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

Мотивация

Понятие квазислучайных групп возникает при рассмотрении подмножеств групп, для которых никакие два элемента в подмножестве не имеют произведения в подмножестве; такие подмножества называются «безпродуктовыми» . Ласло Бабай и Вера Сош задавались вопросом о существовании постоянной $c$ для которой каждая конечная группа $G$ с заказом $n$ имеет подмножество без продуктов размером не менее $cn$ . ^[1] Хорошо известный результат Пауля Эрдеша о множествах целых чисел без сумм можно использовать для доказательства того, что ${\textstyle c={\frac {1}{3}}}$ достаточно для абелевых групп , но оказывается, что такой константы не существует для неабелевых групп . ^[2]

Теперь известны нетривиальные нижняя и верхняя границы размера наибольшего беспроизвольного подмножества группы с порядком $n$ . Нижняя граница ${\textstyle cn^{\frac {11}{14}}}$ можно доказать, взяв большое подмножество объединения достаточного числа смежных классов , ^[3] и верхняя граница ${\textstyle cn^{\frac {8}{9}}}$ задается путем рассмотрения проективной специальной линейной группы $\operatorname {PSL} (2,p)$ для любого простого числа $p$ . ^[4] В процессе доказательства верхней оценки Тимоти Гауэрс определил понятие квазислучайной группы, чтобы инкапсулировать условие отсутствия произведения, и доказал эквивалентности, включающие квазислучайность в теории графов.

Квазислучайность графа

Формально говорить о том, является ли отдельная группа квазислучайной, не имеет смысла. Строгое определение квазислучайности будет применяться к последовательностям групп, но сначала необходимо определить квазислучайность двудольного графа. Мотивация рассмотрения последовательностей групп проистекает из их связи с графонами , которые в определенном смысле определяются как пределы графов.

Исправьте действительное число $p\in [0,1].$ Последовательность двудольных графов $(G_{n})$ (здесь $n$ разрешено пропускать целые числа до тех пор, пока $n$ стремится к бесконечности) при $G_{n}$ имея $n$ вершины, части вершин $A_{n}$ и $B_{n}$ , и $(p+o(1))|A_{n}||B_{n}|$ ребра являются квазислучайными, если выполняется любое из следующих эквивалентных условий:

Для каждого двудольного графа $H$ с вершинными частями $A'$ и $B'$ , количество помеченных копий $H$ в $G_{n}$ с $A'$ встроенный в $A$ и $B'$ встроенный в $B$ является ${\textstyle \left(p^{e(H)}+o(1)\right)|A|^{|A'|}|B|^{|B'|}.}$ Здесь функция $o(1)$ разрешено зависеть от $H.$
Число замкнутых, размеченных дорожек длиной 4 дюйма. $G_{n}$ начиная с $A_{n}$ является $(p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}.$
Количество ребер между $A'$ и $B'$ является $p|A'||B'|+n^{2}o(1)$ для любой пары подмножеств $A'\subseteq A_{n}$ и $B'\subseteq B_{n}.$
$\sum \limits _{a_{1},a_{2}\in A_{n}}N(a_{1},a_{2})^{2}=(p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}$ , где $N(u,v)$ обозначает количество соседей общих $u$ и $v.$
$\sum \limits _{b_{1},b_{2}\in B_{n}}N(b_{1},b_{2})^{2}=(p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}.$
Самое большое собственное значение $G_{n}$ смежности матрица ${\textstyle (p+o(1)){\sqrt {|A||B|}}}$ и все остальные собственные значения имеют величину не более ${\textstyle {\sqrt {|A||B|}}o(1).}$

Чанг-Грэм-Уилсон установил, что каждое из вышеперечисленных условий эквивалентно. ^[5] Такие графы называются квазислучайными, поскольку каждое условие утверждает, что рассматриваемая величина примерно соответствует тому, что можно было бы ожидать, если бы двудольный граф был сгенерирован в соответствии с моделью случайного графа Эрдеша – Реньи ; то есть генерируется путем включения каждого возможного ребра между $A_{n}$ и $B_{n}$ независимо с вероятностью $p.$

Хотя квазислучайность может быть определена только для последовательностей графов, понятие $c$ -квазислучайность может быть определена для конкретного графа, если разрешить допуск к ошибкам в любом из приведенных выше определений квазислучайности графа. Точнее, учитывая любое из эквивалентных определений квазислучайности, $o(1)$ член можно заменить небольшой константой $c>0$ , и любой граф, удовлетворяющий этому конкретному модифицированному условию, можно назвать $c$ -квазислучайный. Оказывается, $c$ -квазислучайность при любых условиях эквивалентна $c^{k}$ -квазислучайность при любых других условиях для некоторой абсолютной константы $k\geq 1.$

Следующим шагом для определения квазислучайности группы является граф Кэли. Двудольные графы Кэли открывают путь от перевода квазислучайности из теории графов в теорию теории групп.

Учитывая конечную группу $\Gamma$ и подмножество $S\subseteq \Gamma$ , двудольный граф Кэли $\operatorname {BiCay} (\Gamma ,S)$ — двудольный граф с наборами вершин $A$ и $B$ , каждый из которых помечен элементами $G$ , чьи ребра $a\sim b$ находятся между вершинами, отношение которых $ab^{-1}$ является элементом $S.$

Определение

С помощью инструментов, определенных выше, теперь можно определить квазислучайность группы. Последовательность групп $(\Gamma _{n})$ с $|\Gamma _{n}|=n$ (снова, $n$ разрешено пропускать целые числа) является квазислучайным , если для каждого действительного числа $p\in [0,1]$ и выбор подмножеств $S_{n}\subseteq \Gamma _{n}$ с $|S_{n}|=(p+o(1))|\Gamma _{n}|$ , последовательность графов $\operatorname {BiCay} (\Gamma _{n},S_{n})$ является квазислучайным. ^[4]

Хотя квазислучайность может быть определена только для последовательностей групп, концепция $c$ -квазислучайность для конкретных групп можно распространить на группы, используя определение $c$ -квазислучайность для конкретных графов.

Характеристики

Как доказал Гауэрс, групповая квазислучайность оказывается эквивалентной ряду различных условий.

Точнее, если задана последовательность групп $(\Gamma _{n})$ , следующие эквивалентны:

$(\Gamma _{n})$ является квазислучайным; то есть все последовательности графов Кэли, определенные формулой $(\Gamma _{n})$ являются квазислучайными.
Размерность наименьшего нетривиального представления $\Gamma _{n}$ является неограниченным.
Размер наибольшего подмножества, не содержащего продуктов $\Gamma _{n}$ является $o(|\Gamma _{n}|).$
Размер наименьшего частного нетривиального $\Gamma _{n}$ является неограниченным. ^[4]

Графы Кэли, сгенерированные из псевдослучайных групп, обладают сильными свойствами перемешивания ; то есть, $\operatorname {BiCay} (\Gamma _{n},S)$ является двусторонним $(n,d,\lambda )$ -график для некоторых $\lambda$ стремится к нулю, так как $n$ стремится к бесконечности. (Напомним, что $(n,d,\lambda )$ график – это график, в котором $n$ вершины, каждая со степенью $d$ , чья матрица смежности имеет второе по величине собственное значение не более $\lambda .$ )

Фактически можно показать, что для любого $c$ -квазислучайная группа $\Gamma$ , количество решений $xy=z$ с $x\in X$ , $y\in Y$ , и $z\in Z$ приблизительно равно тому, что можно было бы ожидать, если бы $S$ был выбран случайно; то есть примерно равно ${\tfrac {|X||Y||Z|}{|\Gamma |}}.$ Этот результат следует из прямого применения леммы о смешивании детандера .

Примеры

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

Проективные специальные линейные группы $\operatorname {PSL} (2,p)$ для премьер-министра $p$ образуют последовательность квазислучайных групп, поскольку классический результат Фробениуса гласит, что ее наименьшее нетривиальное представление имеет размерность не менее ${\tfrac {1}{2}}(p-1).$ Фактически, эти группы являются группами с самым большим известным минимальным нетривиальным представлением в зависимости от порядка группы.
Чередующиеся группы $(A_{n})$ квазислучайны, поскольку его наименьшее нетривиальное представление имеет размерность $n-1.$
Любая последовательность нециклических простых групп возрастающего порядка является квазислучайной, поскольку ее наименьшее нетривиальное представление имеет размерность не менее ${\tfrac {1}{2}}{\sqrt {\log n}}$ , где $n$ это порядок группы. ^[4]

Ссылки

^ Бабай, Ласло ; Сос, Вера Т. (1985), «Множества Сидона в группах и индуцированные подграфы графов Кэли», European Journal of Combinatorics , 6 : 101–114, doi : 10.1016/S0195-6698(85)80001-9
^ Эрдеш, П. (1965), «Экстремальные задачи теории чисел», Proceedings of the Symp. Чистая математика. VIII , Американское математическое общество, стр. 181–189.
^ Кедлайя, Киран С. (1997), «Большие подмножества конечных групп без произведений», Журнал комбинаторной теории , серия A, 77 : 339–343, doi : 10.1006/jcta.1997.2715
^ Jump up to: ^а ^б ^с ^д Гауэрс, WT (2008), «Квазислучайные группы», Combinatorics, Probability and Computing , 17 (3): 363–387, doi : 10.1017/S0963548307008826
^ Чанг, Франция ; Грэм, РЛ ; Уилсон, Р.М. (1989), «Квазислучайные графы», Combinatorica , 9 (4): 345–362, doi : 10.1007/BF02125347 , S2CID 17166765

[1] Бабай, Ласло ; Сос, Вера Т. (1985), «Множества Сидона в группах и индуцированные подграфы графов Кэли», European Journal of Combinatorics , 6 : 101–114, doi : 10.1016/S0195-6698(85)80001-9

[2] Эрдеш, П. (1965), «Экстремальные задачи теории чисел», Proceedings of the Symp. Чистая математика. VIII , Американское математическое общество, стр. 181–189.

[3] Кедлайя, Киран С. (1997), «Большие подмножества конечных групп без произведений», Журнал комбинаторной теории , серия A, 77 : 339–343, doi : 10.1006/jcta.1997.2715

[g-4] Jump up to: ^а ^б ^с ^д Гауэрс, WT (2008), «Квазислучайные группы», Combinatorics, Probability and Computing , 17 (3): 363–387, doi : 10.1017/S0963548307008826

[5] Чанг, Франция ; Грэм, РЛ ; Уилсон, Р.М. (1989), «Квазислучайные графы», Combinatorica , 9 (4): 345–362, doi : 10.1007/BF02125347 , S2CID 17166765

[1]

[2]

[3]

[4]

[5]