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

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

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

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

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

• Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (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.