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

В комбинаторике разностное множество — это подмножество размера группы порядка , такое, что каждый нетождественный элемент из может быть выражен как произведение элементов из ровно способами. Разностное множество называется циклическим , абелевым , неабелевым и т. д., если группа обладает соответствующим свойством. Разностное множество с иногда называют планарным или простым . [ ^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 k^{2}-k=(v-1)\lambda .}$
• Если — разностное множество, то — также разностное множество, и называется переводом ( в аддитивной записи). ${\displaystyle D}$ ${\displaystyle g\in G,}$ ${\displaystyle gD=\{gd:d\in D\}}$ ${\displaystyle D}$ ${\displaystyle D+g}$
• Дополнением к -разностному набору является -разностный набор. ^[2] ${\displaystyle (v,k,\lambda )}$ ${\displaystyle (v,v-k,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 (это эквивалентно тому, чтобы быть множителем). Известно, что это верно для случая, когда — абелева группа, и это известно как теорема о первом множителе. Более общий известный результат, теорема о втором множителе, гласит, что если — множество -разностей в абелевой группе экспоненты ( наименьшее общее кратное порядков каждого элемента), пусть — целое число , взаимно простое с . Если существует делитель такой , что для каждого простого числа p, делящего m , существует целое число i с , то t — числовой делитель. ^[8] ${\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 }$ ${\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}}\}.}$

История

Систематическое использование циклических разностных множеств и методов для построения симметричных блок-схем восходит к RC Bose и его основополагающей статье 1939 года. ^[12] Однако различные примеры появились и раньше, например, «Paley Difference Sets», которые датируются 1933 годом. ^[13] Обобщение концепции циклических разностных множеств на более общие группы принадлежит RH Bruck ^[14] в 1955 году . ^[15] Множители были введены Marshall Hall Jr. ^[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.}$

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

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

Примечания

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

Ссылки

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

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

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

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

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