Набор различий

Информацию о наборе элементов в одном наборе, но не в другом, см. в разделе Относительное дополнение . О множестве разностей пар элементов см. Разность Минковского .

В комбинаторике А. $(v,k,\lambda )$ набор различий является подмножеством $D$ размера ​ $k$ группы ​ $G$ порядка ​ $v$ такая, что каждый неединичный элемент $G$ можно выразить как произведение $d_{1}d_{2}^{-1}$ элементов $D$ ровно в $\lambda$ пути. Набор различий $D$ называется циклической , абелевой , неабелевой и т. д., если группа $G$ имеет соответствующее свойство. Разница, установленная с $\lambda =1$ иногда называют плоским или простым . Если $G$ — абелева группа, записанная в аддитивной записи, определяющим условием является то, что каждый ненулевой элемент $G$ можно записать как разность элементов $D$ ровно в $\lambda$ пути. Таким образом возникает термин «множество различий».

Основные факты

• Простой подсчет показывает, что существует ровно $k^{2}-k$ пары элементов из $D$ это даст неединичные элементы, поэтому каждый набор разностей должен удовлетворять уравнению $k^{2}-k=(v-1)\lambda .$
• Если $D$ представляет собой набор разностей и $g\in G,$ затем $gD=\{gd:d\in D\}$ и называется переводом также является набором разностей $D$ ( $D+g$ в аддитивной записи).
• Дополнение $(v,k,\lambda )$-разностное множество – это $(v,v-k,v-2k+\lambda )$- набор различий.
• Набор всех трансляций разностного набора $D$ образует симметричную блочную конструкцию , разработкой называемую $D$ и обозначается $dev(D).$ В такой конструкции есть $v$ элементы (обычно называемые точками) и $v$ блоки (подмножества). Каждый блок конструкции состоит из $k$ точек, каждая точка содержится в $k$ блоки. Любые два блока имеют ровно $\lambda$ общие элементы и любые две точки одновременно содержатся ровно в $\lambda$ блоки. Группа $G$ действует как группа автоморфизмов плана. Оно резко транзитивно как по точкам, так и по блокам.
  • В частности, если $\lambda =1$, то разностное множество порождает проективную плоскость . Пример набора разностей (7,3,1) в группе $\mathbb {Z} /7\mathbb {Z}$ это подмножество $\{1,2,4\}$. Трансляции этого набора разностей образуют плоскость Фано .
• Поскольку каждый набор разностей дает симметричную схему , набор параметров должен удовлетворять теореме Брука-Райзера-Чоулы .
• Не каждая симметричная конструкция дает набор различий.

Эквивалентные и изоморфные разностные множества

Два набора различий $D_{1}$ в группе $G_{1}$ и $D_{2}$ в группе $G_{2}$ эквивалентны , если существует групповой изоморфизм $\psi$ между $G_{1}$ и $G_{2}$ такой, что $D_{1}^{\psi }=\{d^{\psi }\colon d\in D_{1}\}=gD_{2}$ для некоторых $g\in G_{2}.$ Два разностных множества изоморфны, если планы $dev(D_{1})$ и $dev(D_{2})$ изоморфны как блочные конструкции.

Эквивалентные разностные множества изоморфны, но существуют примеры изоморфных разностных множеств, которые не эквивалентны. В случае циклического разностного множества все известные изоморфные разностные множества эквивалентны.

Множители

Множитель набора разностного $D$ в группе $G$ является групповым автоморфизмом $\phi$ из $G$ такой, что $D^{\phi }=gD$ для некоторых $g\in G.$ Если $G$ является абелевым и $\phi$ это автоморфизм, который отображает $h\mapsto h^{t}$, затем $t$ называется числовым множителем или Холла множителем .

Была высказана гипотеза , что если p — простое число , делящее $k-\lambda$ и не деля v , то групповой автоморфизм, определенный формулой $g\mapsto g^{p}$ исправляет некоторый перевод D (это эквивалентно множителю). Известно, что это верно для $p>\lambda$ когда $G$ является абелевой группой, и это известно как первая теорема о множителе. Более общий известный результат, Вторая теорема о множителе, утверждает, что если $D$ это $(v,k,\lambda )$-разность, заданная в абелевой группе $G$ экспоненты $v^{*}$ ( наименьшее общее кратное каждого порядков элемента), пусть $t$ быть целым числом, взаимно простым с $v$. Если существует делитель $m>\lambda$ из $k-\lambda$ такой, что для каждого простого числа p, делящего m , существует целое число i такое, что $t\equiv p^{i}\ {\pmod {v^{*}}}$, то t — числовой делитель.

Например, 2 — это множитель упомянутого выше набора (7,3,1)-разностей.

Было упомянуто, что числовой множитель разностного множества $D$ в абелевой группе $G$ исправляет перевод $D$, но можно также показать, что существует перевод $D$ который фиксируется всеми числовыми множителями $D.$

Параметры

Известные наборы разностей или их дополнения имеют один из следующих наборов параметров:

• $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$-разность, заданная для некоторой простой степени $q$ и некоторое положительное целое число $n$. Они известны как классические параметры , и существует множество конструкций разностных множеств, имеющих эти параметры.
• $(4n-1,2n-1,n-1)$-множество разностей для некоторого положительного целого числа $n$. Разностные множества с v = 4 n − 1 называются разностными множествами типа Пэли .
• $(4n^{2},2n^{2}-n,n^{2}-n)$-множество разностей для некоторого положительного целого числа $n$. Набор разностей с этими параметрами является набором разностей Адамара .
• $(q^{n+1}(1+(q^{n+1}-1)/(q-1)),q^{n}(q^{n+1}-1)/(q-1),q^{n}(q^{n}-1)/(q-1))$-разностный набор для некоторой простой степени $q$ и некоторое положительное целое число $n$. Известные как параметры МакФарланда .
• $(3^{n+1}(3^{n+1}-1)/2,3^{n}(3^{n+1}+1)/2,3^{n}(3^{n}+1)/2)$-множество разностей для некоторого положительного целого числа $n$. Известные как параметры Спенса .
• $(4q^{2n}(q^{2n}-1)/(q-1),q^{2n-1}(1+2(q^{2n}-1)/(q+1)),q^{2n-1}(q^{2n-1}+1)(q-1)/(q+1))$-разностный набор для некоторой простой степени $q$ и некоторое положительное целое число $n$. Наборы разностей с этими параметрами называются наборами разностей Дэвиса-Джедваба-Чена .

Наборы известных различий

Во многих конструкциях разностных множеств используются группы, относящиеся к аддитивным и мультипликативным группам конечных полей . Обозначения, используемые для обозначения этих полей, различаются в зависимости от дисциплины. В этом разделе ${\rm {GF}}(q)$ это поле Галуа порядка $q,$ где $q$ это простое число или основная степень. Добавляемую группу обозначают $G=({\rm {GF}}(q),+)$, пока ${\rm {GF}}(q)^{*}$ — мультипликативная группа ненулевых элементов.

• Палей $(4n-1,2n-1,n-1)$- набор различий:

Позволять $q=4n-1$ быть высшей силой. В группе $G=({\rm {GF}}(q),+)$, позволять $D$ быть множеством всех ненулевых квадратов.

• Певица $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$- набор различий:

Позволять $G={\rm {GF}}(q^{n+2})^{*}/{\rm {GF}}(q)^{*}$. Тогда набор $D=\{x\in G~|~{\rm {Tr}}_{q^{n+2}/q}(x)=0\}$ это $((q^{n+2}-1)/(q-1),(q^{n+1}-1)/(q-1),(q^{n}-1)/(q-1))$-разностное множество, где ${\rm {Tr}}_{q^{n+2}/q}:{\rm {GF}}(q^{n+2})\rightarrow {\rm {GF}}(q)$ это функция трассировки ${\rm {{Tr}_{q^{n+2}/q}(x)=x+x^{q}+\cdots +x^{q^{n+1}}.}}$

• Двойная основная мощность $\left(q^{2}+2q,{\frac {q^{2}+2q-1}{2}},{\frac {q^{2}+2q-3}{4}}\right)$-разница устанавливается, когда $q$ и $q+2$ обе являются основными полномочиями:

В группе $G=({\rm {GF}}(q),+)\oplus ({\rm {GF}}(q+2),+)$, позволять $D=\{(x,y)\colon y=0{\text{ or }}x{\text{ and }}y{\text{ are non-zero and both are squares or both are non-squares}}\}.$

История

Систематическое использование наборов циклических разностей и методов для построения симметричных блочных конструкций восходит к Р. К. Бозе и его основополагающей статье в 1939 году. Однако различные примеры появились и раньше, например, «Наборы разностей Пэли», датированные 1933 годом. Обобщение концепции циклического разностного множества на более общие группы принадлежит Р. Х. Бруку. в 1955 году. Мультипликаторы были введены Маршаллом Холлом-младшим. в 1947 году.

Приложение

обнаружили Ся, Чжоу и Яннакис , что наборы разностей можно использовать для построения сложной векторной кодовой книги , которая обеспечивает сложную границу Уэлча для максимальной амплитуды взаимной корреляции. Построенная таким образом кодовая книга также образует так называемое грассманово многообразие.

Обобщения

А $(v,k,\lambda ,s)$ Семейство различий представляет собой набор подмножеств $B=\{B_{1},\ldots ,B_{s}\}$ группы $G$ такой, что порядок $G$ является $v$, размер $B_{i}$ является $k$ для всех $i$, и каждый неидентичный элемент $G$ можно выразить как произведение $d_{1}d_{2}^{-1}$ элементов $B_{i}$ для некоторых $i$ (т.е. оба $d_{1},d_{2}$ родом из того же самого $B_{i}$) ровно $\lambda$ пути.

Набор различий – это семейство различий, в котором $s=1.$ Приведенное выше уравнение параметра обобщается до $s(k^{2}-k)=(v-1)\lambda .$ Развитие $dev(B)=\{B_{i}+g:i=1,\ldots ,s,g\in G\}$ Отличительной чертой семейства является 2-конструкторский вариант .Всякий 2-дизайн с регулярной группой автоморфизмов $dev(B)$ для некоторой разницы семья $B.$

См. также

• Комбинаторный дизайн

Ссылки

• Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1986), Теория дизайна , Кембридж: Издательство Кембриджского университета, ISBN  0-521-33334-2 , Збл   0602.05001
• Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник по комбинаторным расчетам , дискретной математике и ее приложениям (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN  978-1-58488-506-1 , Збл   1101.05001
• ван Линт, Дж. Х.; Уилсон, Р.М. (1992), Курс комбинаторики , Кембридж: Издательство Кембриджского университета , ISBN  0-521-42260-4 , Збл   0769.05001
• Уоллис, WD (1988). Комбинаторные планы . Марсель Деккер. ISBN  0-8247-7942-8 . Артикул   0637.05004 .

Дальнейшее чтение

• Мур, Э.Х.; Полластек, HSK (2013). Наборы различий: соединение алгебры, комбинаторики и геометрии . АМС. ISBN  978-0-8218-9176-6 .
• Сторер, Томас (1967). Циклотомия и разностные множества . Чикаго: Издательская компания Markham. Збл   0157.03301 .
• Ся, Пэнфэй; Чжоу, Шэнли; Яннакис, Георгиос Б. (2005). «Достижение границы Уэлча с помощью наборов различий» (PDF) . Транзакции IEEE по теории информации . 51 (5): 1900–1907. дои : 10.1109/TIT.2005.846411 . ISSN   0018-9448 . S2CID   8916926 . Збл   1237.94007 . .

Ся, Пэнфэй; Чжоу, Шэнли; Яннакис, Георгиос Б. (2006). «Поправка к достижению границы Уэлча с разностными множествами ». IEEE Транс. Инф. Теория . 52 (7): 3359. doi : 10.1109/tit.2006.876214 . Збл   1237.94008 .

• Цвиллингер, Дэниел (2003). Стандартные математические таблицы и формулы CRC . ЦРК Пресс. п. 246 . ISBN  1-58488-291-3 .