Набор различий - Difference set

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

В комбинаторика, а ${\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}$ иногда называют планарный или же просто.^[1] Если ${\displaystyle G}$ является абелева группа записано в аддитивной записи, определяющим условием является то, что каждый ненулевой элемент ${\displaystyle G}$ можно записать как разница элементов ${\displaystyle D}$ точно ${\displaystyle \lambda }$ способами. Таким образом возникает термин «разностное множество».

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

• Простой счетный аргумент показывает, что есть ровно ${\displaystyle k^{2}-k}$ пары элементов из ${\displaystyle D}$ что даст неединичные элементы, поэтому каждый разностный набор должен удовлетворять уравнению ${\displaystyle k^{2}-k=(v-1)\lambda }$.
• Если ${\displaystyle D}$ это набор разностей, и ${\displaystyle g\in G}$, тогда ${\displaystyle gD=\{gd:d\in D\}}$ также является разностным набором и называется переведите из ${\displaystyle D}$ (${\displaystyle D+g}$ в аддитивной записи).
• Дополнение ${\displaystyle (v,k,\lambda )}$-множество различий - это ${\displaystyle (v,v-k,v-2k+\lambda )}$-различия установлены.^[2]
• Набор всех трансляций разностного набора ${\displaystyle D}$ образует симметричная блочная конструкция, называется разработка из ${\displaystyle D}$ и обозначается ${\displaystyle dev(D)}$. В таком дизайне есть ${\displaystyle v}$ элементы (обычно называемые точками) и ${\displaystyle v}$ блоки (подмножества). Каждый блок конструкции состоит из ${\displaystyle k}$ точек, каждая точка содержится в ${\displaystyle k}$ блоки. Любые два блока имеют ровно ${\displaystyle \lambda }$ общих элементов и любые две точки одновременно содержатся точно в ${\displaystyle \lambda }$ блоки. Группа ${\displaystyle G}$ действует как группа автоморфизмов дизайна. Это резко переходно как по точкам, так и по блокам.^[3]
  • В частности, если ${\displaystyle \lambda =1}$, то разностный набор приводит к проективная плоскость. Пример (7,3,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]

Множители

А множитель разностного набора ${\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}$ называется числовой или же зал множитель.^[7]

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

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

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

Параметры

Известные разностные наборы или их дополнения имеют один из следующих наборов параметров:^[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)}$-разница установлена ​​для некоторого положительного целого числа ${\displaystyle n}$. Наборы различий с v = 4n - 1 называются Разностные множества типа Пэли.
• ${\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}$ обе основные силы:

В группе ${\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}}\}.}$^[11]

История

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

Заявление

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

Обобщения

А ${\displaystyle (v,k,\lambda ,s)}$ Различная семья это набор подмножеств ${\displaystyle B=\{B_{1},...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 }$ способами.

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

Смотрите также

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

Примечания

1. ван Линт и Уилсон 1992, п. 331
2. Уоллис 1988, п. 61 - Теорема 4.5
3. ван Линт и Уилсон 1992, п. 331 - Теорема 27.2. Теорема утверждает только точечную транзитивность, но блочная транзитивность следует из этого второго следствия на p. 330.
4. Колборн и Диниц 2007, п. 420 (18.7 замечание 2)
5. Колборн и Диниц 2007, п. 420 (18.7 замечание 1)
6. Колборн и Диниз 2007, п. 420 (замечание 18.9) Ошибка harvnb: цель отсутствует: CITEREFColbournDiniz2007 (помощь)
7. ван Линт и Уилсон 1992, п. 345
8. ван Линт и Уилсон 1992, п. 349 (теорема 28.7)
9. Бет, Юнгникель и Ленц 1986, п. 280 (теорема 4.6)
10. Колберн и Диниц 2007, стр. 422-425 Ошибка harvnb: цель отсутствует: CITEREFColburnDinitz2007 (помощь)
11. Колборн и Диниц 2007, п. 425 (конструкция 18.49)
12. Bose, R.C. (1939), «О построении уравновешенных неполных блочных конструкций», Анналы евгеники, 9: 353–399, Дои:10.1111 / j.1469-1809.1939.tb02219.x, JFM  65.1110.04, Zbl  0023.00102
13. Уоллис 1988, п. 69
14. Брук, Р. (1955), «Разностные множества в конечной группе», Труды Американского математического общества, 78: 464–481, Дои:10.2307/1993074, Zbl  0065.13302
15. ван Линт и Уилсон 1992, п. 340
16. Холл младший, Маршалл (1947), «Циклические проективные плоскости», Герцогский журнал математики, 14: 1079–1090, Дои:10.1215 / s0012-7094-47-01482-8, Zbl  0029.22502
17. Бет, Юнгникель и Ленц 1986, п. 275
18. Бет, Юнгникель и Ленц 1986, п. 310 (2.8.a)

Рекомендации

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

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

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

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

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