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

Для набора элементов в одном наборе, но не в другом, см. Относительное дополнение . О множестве различий пар элементов см. Разность Минковского .

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

Основные факты [ править ]

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

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

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

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

Множители [ править ]

Умножитель разностного множества в группе является группа автоморфизмов из таких , что для некоторых . Если абелев и является отображающим автоморфизмом , то он называется числовым или холловым множителем . ^[7]${\displaystyle D}$${\displaystyle G}$ ${\displaystyle \phi }$${\displaystyle G}$${\displaystyle D^{\phi }=gD}$${\displaystyle g\in G}$${\displaystyle G}$${\displaystyle \phi }$${\displaystyle h\mapsto h^{t}}$${\displaystyle t}$

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

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

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

Параметры [ править ]

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

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

Известные наборы отличий [ править ]

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

• Пэли - набор различий:${\displaystyle (4n-1,2n-1,n-1)}$

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

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

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

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

Пусть в группе ^[11]${\displaystyle G=({\rm {GF}}(q),+)\oplus ({\rm {GF}}(q+2),+)}$${\displaystyle 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 году. ^[12] Однако различные примеры появились раньше, чем это, такие как «Разностные множества Пэли». которая восходит к 1933 году ^[13] обобщение циклической разности множеств концепции до более общих групп обусловлено RH Брук ^[14] в 1955 г. ^[15] умножители были введены Маршаллом Холл - младшим ^[16] в 1947 году ^{[ 17]}

Заявление [ править ]

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

Обобщения [ править ]

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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

Ся, Пэнфэй; Чжоу, Шэнли; Гианнакис, Георгиос Б. (2006). «Поправка к« Достижению границы Уэлча с помощью разностных множеств ». IEEE Trans. Инф. Теория . 52 (7): 3359. DOI : 10,1109 / tit.2006.876214 . Zbl  1237.94008 .

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