差分集合

組み合わせ論では、${\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}$ブロック。任意の2つのブロックは正確に${\displaystyle \lambda }$共通要素があり、任意の 2 つの点が同時に正確に含まれる${\displaystyle \lambda }$ブロック。グループ${\displaystyle G}$デザインの自己同型群として機能します。点とブロックの両方で厳密に推移的です。 ^{[ 3 ]}
  • 特に、${\displaystyle \lambda =1}$すると、差分集合は射影平面を生み出す。群における (7,3,1) 差分集合の例${\displaystyle \mathbb {Z} /7\mathbb {Z} }$部分集合は${\displaystyle \{1,2,4\}}$この差分集合の平行移動によってファノ平面が形成されます。
• すべての差分集合は対称的な設計を与えるため、パラメータ集合はブルック・ライザー・チョウラ定理を満たさなければならない。^{[ 4 ]}
• すべての対称デザインが差分集合を与えるわけではない。^{[ 5 ]}

2つの差分セット${\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}.}$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 }$mを割り切るすべての素数pに対して、ある整数iが存在し、${\displaystyle t\equiv p^{i}\ {\pmod {v^{*}}}}$ならば、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の差分集合は、ペイリー型差分集合と呼ばれます。
• ${\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}$これらのパラメータを持つ差分集合は、Davis-Jedwab-Chen差分集合と呼ばれます。

差集合の多くの構成において、使用される群は有限体の加法群および乗法群に関連しています。これらの体を表すために使用される記法は、分野によって異なります。このセクションでは、${\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 ]}

巡回差集合と対称ブロック設計の構築方法の体系的な使用は、RC Boseと彼の 1939 年の画期的な論文に遡ります。 ^{[ 12 ]}しかし、これより前にさまざまな例が現れており、1933 年に遡る「Paley 差集合」などがあります。^{[ 13 ]}巡回差集合の概念をより一般的なグループに一般化したのは、1955 年にRH Bruckによるものです。 ^{[ 14 ] [ 15 ]}乗数は、 1947 年にMarshall Hall Jr.によって導入されました。 ^{[ 16 ] [ 17 ]}

Xia、Zhou、 Giannakisらは、差分集合を用いることで、最大相互相関振幅に関する困難なウェルチ限界を達成する複雑なベクトルコードブ​​ックを構築できることを発見した。

A${\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\}}$差族の は2-デザインである。正則自己同型群を持つすべての 2-デザインは${\displaystyle dev(B)}$家族の違い${\displaystyle B.}$

• 組み合わせ設計
• ライザーの巡回アダマール行列に関する予想

• ベス、トーマス；ユングニッケル、ディーター；レンツ、ハンフリート（1986）、『デザイン理論』、ケンブリッジ：ケンブリッジ大学出版局、ISBN 0-521-33334-2、Zbl 0602.05001 
• コルボーン、チャールズ・J.、ディニッツ、ジェフリー・H. (2007)、『組合せ設計ハンドブック』、離散数学とその応用（第2 版）、ボカラトン：チャップマン＆ホール/CRC、ISBN 978-1-58488-506-1、Zbl 1101.05001 
• van Lint, JH; Wilson, RM (1992), 『組合せ論入門』、ケンブリッジ：ケンブリッジ大学出版局、ISBN 0-521-42260-4、Zbl 0769.05001 
• Wallis, WD (1988).組合せ設計. Marcel Dekker. ISBN 0-8247-7942-8. Zbl 0637.05004 . 

• Moore, EH; Pollastek, HSK (2013).差集合：代数、組み合わせ論、幾何学をつなぐ. AMS. ISBN 978-0-8218-9176-6。
• Storer, Thomas (1967).サイクロトミーと差分集合. シカゴ: Markham Publishing Company. Zbl 0157.03301 . 
• Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2005). "差分集合によるウェルチ限界の達成" (PDF) . IEEE Transactions on Information Theory . 51 (5): 1900– 1907. doi : 10.1109/TIT.2005.846411 . ISSN 0018-9448 . S2CID 8916926 . Zbl 1237.94007 .   。

Xia, Pengfei; Zhou, Shengli; Giannakis, Georgios B. (2006). "差分集合によるウェルチ限界の達成に関する訂正". IEEE Trans. Inf. Theory . 52 (7): 3359. doi : 10.1109/tit.2006.876214 . Zbl 1237.94008 . 

• ズウィリンガー、ダニエル（2003）。CRC標準数表と数式。CRC Press。p . 246。ISBN  1-58488-291-3。