مجموعة الفروق

في علم التوافيق ، أ${\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,vk,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 ]}

لقد تم التكهن بأنه إذا كان p عددًا أوليًا يقسم${\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 }$بحيث أنه لكل عدد أولي p يقسم m ، يوجد عدد صحيح i بحيث${\displaystyle t\equiv p^{i}\ {\pmod {v^{*}}}}$إذا كان t قاسمًا عدديًا ، فإن t هو قاسم عددي . ^{[ 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 = 4 n − 1 مجموعات الفرق من نوع Paley .
• ${\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},\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 }$طرق.

مجموعة الفروق هي عائلة فروق ذات${\displaystyle s=1.}$يمكن تعميم معادلة المعاملات أعلاه إلى${\displaystyle s(k^{2}-k)=(v-1)\lambda .}$^{[ 18 ]} التطور${\displaystyle dev(B)=\{B_{i}+g:i=1,\ldots ,s,g\in G\}}$تُسمى عائلة الاختلاف تصميمًا ثنائيًا . كل تصميم ثنائي مع زمرة تماثل منتظم هو${\displaystyle dev(B)}$لبعض الاختلافات العائلية${\displaystyle B.}$

• التصميم التوافقي
• تخمين رايزر بشأن مصفوفات هادامارد الدائرية

• بيث، توماس؛ يونغنيكل، ديتر ؛ لينز، هانفريد (1986)، نظرية التصميم ، كامبريدج: مطبعة جامعة كامبريدج، ISBN 0-521-33334-2Zbl 0602.05001​ 
• كولبورن، تشارلز جيه؛ دينيتز، جيفري إتش (2007)، دليل التصاميم التوافقية ، الرياضيات المتقطعة وتطبيقاتها (  الطبعة الثانية)، بوكا راتون: تشابمان آند هول/ سي آر سي، رقم ISBN 978-1-58488-506-1Zbl 1101.05001​ 
• فان لينت، جيه إتش؛ ويلسون، آر إم (1992)، دورة في التوافقية ، كامبريدج: مطبعة جامعة كامبريدج ، رقم ISBN 0-521-42260-4Zbl 0769.05001​ 
• واليس، دبليو دي (1988). التصاميم التوافقية . مارسيل ديكر. ISBN 0-8247-7942-8. Zbl 0637.05004 . 

• مور، إي إتش؛ بولاستيك، إتش إس كيه (2013). مجموعات الفرق: ربط الجبر والتوافقية والهندسة . الجمعية الأمريكية للرياضيات. رقم ISBN 978-0-8218-9176-6.
• ستورر، توماس (1967). تقسيم الدوائر ومجموعات الفرق . شيكاغو: شركة ماركهام للنشر. 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 لنظرية المعلومات . 52 (7): 3359. doi : 10.1109/tit.2006.876214 . Zbl 1237.94008 . 

• زويلينجر ، دانيال (2003). جداول وصيغ رياضية قياسية من سي آر سي . مطبعة سي آر سي. ص 246. ISBN  1-58488-291-3.