Закрытие с изюминкой

Замыкание с поворотом — свойство подмножеств алгебраической структуры . Подмножество $Y$ алгебраической структуры $X$ Говорят, что оно демонстрирует замыкание с поворотом, если для каждых двух элементов

$y_{1},y_{2}\in Y$

существует автоморфизм $\phi$ из $X$ и элемент $y_{3}\in Y$ такой, что

$y_{1}\cdot y_{2}=\phi (y_{3})$

где " $\cdot$" — обозначение операции над $X$ сохранено $\phi$.

Двумя примерами алгебраических структур, которые демонстрируют замыкание с поворотом, являются cwatset и обобщенный cwatset , или GC-set .

Cватсет

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

Если каждая строка в cwatset, скажем, C имеет длину n , то C будет подмножеством $\mathbb {Z} _{2}^{n}$. Таким образом, две строки в C добавляются путем сложения битов в строках по модулю 2 (то есть сложение без переноса или исключающая дизъюнкция ). Симметричная группа из n букв, ${\text{Sym}}(n)$, действует на $\mathbb {Z} _{2}^{n}$ по битовой перестановке:

$p((c_{1},\ldots ,c_{n}))=(c_{p(1)},\ldots ,c_{p(n)}),$

где $c=(c_{1},\ldots ,c_{n})$ является элементом $\mathbb {Z} _{2}^{n}$ и p является элементом ${\text{Sym}}(n)$. Замыкание с поворотом теперь означает, что для каждого элемента c в C существует некоторая перестановка $p_{c}$ так что, когда вы добавляете c к произвольному элементу e а затем применяете перестановку, результатом также будет элемент C. в cwatset , То есть, обозначая сложение без переноса $+$, C будет cwatset тогда и только тогда, когда

$\forall c\in C:\exists p_{c}\in {\text{Sym}}(n):\forall e\in C:p_{c}(e+c)\in C.$

Это условие также можно записать как

$\forall c\in C:\exists p_{c}\in {\text{Sym}}(n):p_{c}(C+c)=C.$

Примеры

• Все подгруппы ​ $\mathbb {Z} _{2}^{n}$ — то есть непустые подмножества $\mathbb {Z} _{2}^{n}$ которые замкнуты относительно сложения без переноса, — это тривиальные наборы cwats, поскольку мы можем выбрать каждую перестановку как _pc тождественную перестановку.
• Пример cwatset, который не является группой:

Ф = {000,110,101}.

Чтобы продемонстрировать, что F является набором cwatset, заметим, что

Ф + 000 = Ф .

F + 110 = {110 000 011}, то есть F с транспонированными первыми двумя битами каждой строки.

F + 101 = {101 011 000}, что совпадает с F после обмена первым и третьим битами в каждой строке.

• Матричное представление набора cwatset формируется путем записи его слов в виде строк матрицы 0–1. Например, матричное представление F имеет вид

$F={\begin{bmatrix}0&0&0\\1&1&0\\1&0&1\end{bmatrix}}.$

Чтобы увидеть, что F является набором cwatset, использующим эту запись, обратите внимание, что

$F+000={\begin{bmatrix}0&0&0\\1&1&0\\1&0&1\end{bmatrix}}=F^{id}=F^{(2,3)_{R}(2,3)_{C}}.$

$F+110={\begin{bmatrix}1&1&0\\0&0&0\\0&1&1\end{bmatrix}}=F^{(1,2)_{R}(1,2)_{C}}=F^{(1,2,3)_{R}(1,2,3)_{C}}.$

$F+101={\begin{bmatrix}1&0&1\\0&1&1\\0&0&0\end{bmatrix}}=F^{(1,3)_{R}(1,3)_{C}}=F^{(1,3,2)_{R}(1,3,2)_{C}}.$

где $\pi _{R}$ и $\sigma _{C}$ обозначают перестановки строк и столбцов матрицы соответственно, выраженные в обозначениях цикла .

• Для любого $n\geq 3$ еще один пример cватсета: $K_{n}$, который имеет $n$-к- $n$ матричное представление

$K_{n}={\begin{bmatrix}0&0&0&\cdots &0&0\\1&1&0&\cdots &0&0\\1&0&1&\cdots &0&0\\&&&\vdots &&\\1&0&0&\cdots &1&0\\1&0&0&\cdots &0&1\end{bmatrix}}.$

Обратите внимание, что для $n=3$, $K_{3}=F$.

• Пример негруппового cwatset с прямоугольным матричным представлением:

$W={\begin{bmatrix}0&0&0\\1&0&0\\1&1&0\\1&1&1\\0&1&1\\0&0&1\end{bmatrix}}.$

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

Позволять $C\subset \mathbb {Z} _{2}^{n}$ будь ватсетом.

• Степень C степени n равна . показателю
• Порядок C обозначаемый , | C |, — мощность множества C .
• Существует необходимое условие порядка cватсета по его степени, а именно:

аналог теоремы Лагранжа в теории групп. А именно,

Теорема . Если C — это набор степени n и порядка m , то m делит $2^{n}!$.

Условие делимости необходимо, но недостаточно. Например, не существует cwatset степени 5 и порядка 15.

Обобщенный набор сообщений

В математике обобщенный cwatset ( GC-set ) — это алгебраическая структура, обобщающая понятие замыкания с поворотом, определяющей характеристики cwatset.

Определения

Подмножество , H группы G если является GC-множеством для каждого $h\in H$, существует $\phi _{h}\in {\text{Aut}}(G)$ такой, что $\phi _{h}(h)\cdot H=\phi _{h}(H)$.

Более того, GC-множество H ⊆ G является циклическим GC-множеством, если существует $h\in H$ и $\phi \in {\text{Aut}}(G)$ такой, что $H={h_{1},h_{2},...}$ где $h_{1}=h$ и $h_{n}=h_{1}\cdot \phi (h_{n-1})$ для всех $n>1$.

Примеры

• Любой cwatset является GC-набором, поскольку $C+c=\pi (C)$ подразумевает, что $\pi ^{-1}(c)+C=\pi ^{-1}(C)$.
• Любая группа является GC-множеством, удовлетворяющим определению с тождественным автоморфизмом.
• Нетривиальный пример GC-множества: $H={0,2}$ где $G=Z_{10}$.
• Непример, показывающий, что определение нетривиально для подмножеств $Z_{2}^{n}$ является $H={000,100,010,001,110}$.

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

• GC-множество ⊆ G всегда содержит единицу G H .
• Прямым продуктом GC-множеств снова является GC-множество.
• Подмножество G H ⊆ G оно является проекцией подгруппы Aut(G) ⋉ является GC-множеством тогда и только тогда , , полупрямого произведения Aut (G) и G. когда
• Как следствие предыдущего свойства, GC-множества имеют аналог теоремы Лагранжа : порядок GC-множества делит порядок Aut(G ⋉ G. )
• Если GC-множество H имеет тот же порядок, что и подгруппа в Aut(G) ⋉ G которой оно является , проекцией , то для каждой простой степени $p^{q}$ который делит порядок H , H содержит подмножества GC порядков p , $p^{2}$,..., $p^{q}$. (Аналог первой теоремы Силова )
• GC-множество является циклическим тогда и только тогда, когда оно является проекцией циклической подгруппы Aut (G) ⋉ G .

Ссылки

• Шерман, Гэри Дж.; Ваттенберг, Мартин (1994), «Представляем… cwatsets!», Mathematics Magazine , 67 (2): 109–117, doi : 10.2307/2690684 , JSTOR   2690684 .
• Cwatset of a Graph, Нэнси-Элизабет Буш и Пол А. Исихара, Mathematics Magazine 74 , № 1 (февраль 2001 г.), стр. 41–47.
• О группах симметрии гиперграфов совершенных квацмножеств, Дэниел К. Бисс , Ars Combinatorica 56 (2000), стр. 271–288.
• Автоморфные подмножества n -мерного куба, Гарет Джонс, Михаил Клин и Феликс Лазебник, Вклад в алгебру и геометрию 41 (2000), № 2, стр. 303–323.
• Дэниел С. Смит (2003) RHIT-UMJ, RHIT [1]