Designs M1 後藤　順一.

Presentation on theme: "Designs M1 後藤　順一."— Presentation transcript:

1 Designs M1 後藤　順一

2 　　　　　デザイン 点の集合 ブロック：X の k 点部分集合 Xのどの２点の組も、ちょうど　個のブロックに含まれる (6,3,2)‐デザイン

3 デザイン 点の集合 ブロック：X の k 点部分集合 Xのどの２点の組も、ちょうど 個のブロックに含まれる (v,k,λ)が与えられたとき、
　　　　　デザイン 点の集合 ブロック：X の k 点部分集合 Xのどの２点の組も、ちょうど　個のブロックに含まれる (v,k,λ)が与えられたとき、 　 デザインが存在するか？ 　 どのように構成できるか？ (6,3,2)‐デザイン

4 デザイン Xのどの t点 の組も、ちょうどλ個のブロックに含まれる 他の定義は同じ 右図は t＝３
　　　　　デザイン Xのどの t点 の組も、ちょうどλ個のブロックに含まれる 他の定義は同じ 右図は t＝３ 単に　　　　　　デザインというときは、 t =2のものを指す。 特殊な呼び名 λ＝１のもの　⇒　シュタイナー系(Steiner system) ブロック数が、点の数 v と同じもの　⇒　対称的(symmetric)

5 13.1 正則性(Regularity) r 正則 ： どの点も、ちょうど r 個のブロックに含まれる。 r ： 繰り返し数 定理１３．２
(v,k,λ)デザインは、次の等式を満たす r を繰り返し数として、r 正則である。 証明 どちらもダブルカウント。 v ： 全体の要素数 k ： ブロックあたりの要素数 λ ： 会合数 b ： ブロック数 r ： 繰り返し数

6 定理13.2の証明(1) (1) r (k-1) = λ (v-1) 手法：a を固定して、この組み合わせをダブルカウント λ (v-1)
a でない x は v-1 通り。 a と x が両方入るブロックが λ 個存在する。 r (k-1) a を含むブロックを　　個とする。 ブロックに含まれない x は k-1 通り。 　　　　　　　　　　　となるが、 　　これは a に無関係。証明終。 v ： 全体の要素数 k ： ブロックあたりの要素数 λ ： 会合数 b ： ブロック数 r ： 繰り返し数

7 定理13.2の証明(2) (2) bk = vr 手法： をダブルカウント vr ：どの点も r 回出てくる。
手法：　　　　　　　　　　　　　　　をダブルカウント vr ：どの点も r 回出てくる。 bk：ブロックの数が b 、それぞれの要素数が k 。 v ： 全体の要素数 k ： ブロックあたりの要素数 λ ： 会合数 b ： ブロック数 r ： 繰り返し数

8 存在性 定理13.3 証明 とする。 bk = vr ならば、 r 正則な、 k 要素のブロック b 個の集合が存在する。
　　　　　　　　　　とする。 bk = vr ならば、 r 正則な、 k 要素のブロック b 個の集合が存在する。 証明 k 要素のブロックを b 個つくる。（ r 正則とは限らない） 要素ごとに繰り返し数を数える。異なるもの(xとy、　　　　 )があれば、xが含まれるブロックから１つ選び、xをyに入れ替える。（ブロックが重複しないように） この操作を繰り返す。要素ごとの繰り返し数の差を１以下にできる。 繰り返し数の平均は bk/v であり、これが整数ならば、正則にできる。

9 13.2 有限線形空間(Finite linear spaces)
定義：点の集合X、直線の集合L どの直線も少なくとも２点を含む どの２点も、ちょうど１つの直線が通る 線形代数学の手法で証明されたもののうち、有限線形 空間からでも証明できるものがある。 定理13.4 |L| ≧|X| 等号成立は、どの２直線もちょうど１点で交わるとき。 （定理14.6 Fisherの不等式に似ている） 証明中、b = |L|（直線の数）、v = |X|（点の数）とする。 |L|は、直線 L 上の点の数。

10 定理13.4の証明 を、x を通る直線の数とする。 のとき、 （背理法の仮定） b ≦ v とする。 のとき、
　　　　　のとき、 （背理法の仮定） b ≦ v とする。 　　　　のとき、 等号は、 b = v かつ、どの　　　　　においても　　　　　　のとき。 b < v のときは矛盾。

11 13.3 差集合(Difference sets) この節からは、デザインを構成する方法を紹介する。
　　 を、0から v-1 の自然数の集合で、加算が法 v で計 算される群とみる。 定義13.5 2≦k＜v , λ≧1 とする。 (v,k,λ)-差集合とは、 の k 要素部分集合で、 　　　　　　　　　　が、　　の0を除く要素をλ 回ずつ含むもの。

12 差集合の例 式(13.3) (11,5,2)-差集合 D = {1,3,4,5,9} が成り立つ。 証明
Dj 1 3 4 5 9 Di - 8 7 2 10 6 (11,5,2)-差集合 D = {1,3,4,5,9} 式(13.3) Di – Dj (mod v)の表 　　　　　　　　　　　　　 が成り立つ。 証明 上の表の値の組合せをダブルカウント。 i と j の値の組は k(k-1) 個。 1から v-1 までの数が λ 個あるので、λ(v-1)個。

13 差集合とデザイン 定理13.6 ただし、 できるデザインは対称的。(b = v) D が (v, k, λ)-差集合ならば、
D, 1+D, 2+D,…, (v-1)+D は(v, k, λ)-デザインのブロックとなる。 ただし、 できるデザインは対称的。(b = v) (11,5,2)デザイン

14 定理13.6の証明 点の数 v 、ブロックの要素数 k は明らか。 どの点のペアも λ 個含まれることを言えばよい。
　　　　　　　　　　　　となる a の数を考える。 　　　　　　　　　　　　　とすると、 差集合の定義から、これを満たす組(i,j)は λ 個。 λ 個の組それぞれに対して、 a が決まる。 したがって、条件を満たす a は λ 個。 証明終。

15 差集合をつくる 定理13.7 v は素数、かつ v ≡ 3 (mod 4)
Zv 上の、0を除く数の二乗の集合は、 (v, k, λ)-差集合。 k = (v-1)/2, λ = (v-3)/4 v=11, k=5, λ=2 a 1 2 3 4 5 (a^2)%11 9 D = {1,3,4,5,9}

16 定理13.7の証明(1) まず、 であることを示す。 は 上の数である。
まず、　　　　　であることを示す。 は　　上の数である。 　　　　 の解は ±a の二つであるため、±a の２数は二乗すると同じ数になる。 0 を除く数の半分だから、 この　　の集合を、S とする。

17 定理13.7の証明(2) 差集合であることを確かめる。 のとき、 （ ） S が二乗の集合のとき、 とする。
　　　　　　　　のとき、　　　　　　　　　　　　　　 （ ） S が二乗の集合のとき、　　　　　　　　　　　とする。 -S は S に入らない要素の集合となる。 どのような s に対しても、 　　　　　　　　　　　　　　　　　が成り立つ時に限り、 したがって、s と –s は、二乗した数同士の差の集合で、同じ数 λ だけ現れる。 式(13.3)　　　　　　　　　　　、k = (v-1)/2 より、 　　λ = (v-3)/4　　　証明終。

18 13.4 射影平面(projective planes)
定義13.8 位数 q の射影平面 PG(2,q) は、 q^2 + q + 1 個の点からなり、 (P1) どの直線も q + 1 点を通る。 (P2) どの２点も、ただ１つの直線に乗る。 (q^2+q+1, q+1, 1) デザイン 直線をブロックと見る q = 2 の例　Fano plane. v = b = 7 k = 3 r = 3 λ = 1 Fano plane

19 射影平面 命題13.9 (P3) どの点も q + 1 直線に乗る (P4) 直線の数は q^2 + q + 1

20 射影平面 命題13.9 (P3)の証明 (P3) どの点も q + 1 直線に乗る (P4) 直線の数は q^2 + q + 1
ある1点に着目する。 その点を含む直線は全て、その点以外に q 点を含む。 (P2)により重複する点はない。 着目している点以外には q(q+1) 点ある。 したがって、この点には q(q+1) /q=q+1 の直線が通っている。

21 射影平面 命題13.9 (P4)の証明 (P3) どの点も q + 1 直線に乗る (P4) 直線の数は q^2 + q + 1
組合せ（頂点 , 直線）をダブルカウント。 （直線数×直線当たり頂点数）＝ b (q+1) （頂点数×頂点当たり直線数）＝ (q^2+q+1) (q+1) したがって、 b = q^2+q+1

22 射影平面 命題13.9 (P5)の証明 (P3) どの点も q + 1 直線に乗る (P4) 直線の数は q^2 + q + 1
したがって、その点だけで交わる。

23 13.4.1 射影平面の構成法 q が素数の時、位数 q の射影平面 PG(2,q) を、次のよう にして作ることができる。
13.4.1　射影平面の構成法 q が素数の時、位数 q の射影平面 PG(2,q) を、次のよう にして作ることができる。 有限体　　 の要素3個のベクトルをつくる。ただし(0,0,0)は除く。 作られた　　　 個のベクトルについて、　　の要素を乗ずると同じになるものをひとまとめにする。　　　　　個でき、それらを点と呼ぶ。 各点からベクトル　　　　　　を１つずつ選び、方程式を作る。 この方程式の解となるベクトルを含む点が q+1 個ある。これらの集合を直線（ブロック）とする。 この直線（ブロック）すべての集合が、射影平面（デザイン）となる。

24 構成法の例 (1) (1) 有限体 の要素3個のベクトルをつくる。ただし(0,0,0)は 除く。
構成法の例　　　　　(1) (1)　有限体　　 の要素3個のベクトルをつくる。ただし(0,0,0)は 除く。 (0,0,0) (0,1,0) (0,2,0) (1,0,0) (1,1,0) (1,2,0) (2,0,0) (2,1,0) (2,2,0) (0,0,1) (0,1,1) (0,2,1) (1,0,1) (1,1,1) (1,2,1) (2,0,1) (2,1,1) (2,2,1) (0,0,2) (0,1,2) (0,2,2) (1,0,2) (1,1,2) (1,2,2) (2,0,2) (2,1,2) (2,2,2) (2)　　の要素を乗ずると同じになるものをひとまとめにする。 1 2 3 4 5 6 7 8 9 10 11 12 13 (0,0,1) (0,0,2) (0,1,0) (0,2,0) (0,1,1) (0,2,2) (1,0,1) (2,0,2) (1,1,0) (2,2,0) (0,1,2) (0,2,1) (1,0,2) (2,0,1) (1,2,0) (2,1,0) (1,1,1) (2,2,2) (1,1,2) (2,2,1) (1,2,1) (2,1,2) (2,1,1) (1,2,2) これらのベクトルの集合を点と呼ぶ。

25 構成法の例 (2) (3) 各点からベクトル を選び、方程式を作る。
構成法の例　　　　　(2) (3)　各点からベクトル　　　　　を選び、方程式を作る。 (1,0,1) (2,0,2) 5 (4)　方程式の解となるベクトルを含む点が q+1 個ある。 それらの集合を直線（ブロック）とする。 (0,1,0) (0,2,0) 2 (1,0,2) (2,0,1) 8 (1,1,2) (2,2,1) 11 (2,1,1) (1,2,2) 13 5

26 構成法の例 (3) (5) 直線（ブロック）すべての集合が、射影平面（デザイ ン）となる。 1 2, 3, 6, 8 7
構成法の例　　　　　(3) (5)　直線（ブロック）すべての集合が、射影平面（デザイ ン）となる。 1 2, 3, 6, 8 7 3, 4, 10, 13 2 1, 3, 5, 8 8 2, 5, 10, 12 3 1, 2, 4, 7 9 1, 6, 10, 11 4 3, 7, 11, 12 10 7, 8, 9, 10 5 2, 8, 11, 13 11 4, 5, 9, 11 6 1, 9, 12, 13 12 4, 6, 8, 12 13 5, 6, 7, 13

27 構成法の検証 点の数： 個 直線（ブロック）に含まれる点の数： q+1 個 どの２点もただ１つの直線に乗る
点の数：　　　　　 個 ベクトルは全部で　　　　個、各点にベクトルが　　　 個 直線（ブロック）に含まれる点の数： q+1 個 各方程式の解は、　　　　個、各点にベクトルが q+1 個 どの２点もただ１つの直線に乗る ２つの点 x,y を決めれば、点 a も決まる。（詳細は省略）

28 13.4.2 Bruenの定理 blocking set ：射影平面上のどの直線とも交差する点 の集合
定理13.10 B を位数 q の射影平面の、直線を含まない blocking set とすると、その点の数は、 　　　　点以下の集合は、ある直線を含むか、どの点も通 らない直線があるかのどちらか。 証明は省略。（ダブルカウントによる）

29 13.5 Resolvable なデザイン parallel class ：デザインDの独立なブロックの集合で、そ れらの union が、点全体になるもの。 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) (4,2,1)デザイン (1,2) (3,4) (1,3) (2,4) (1,4) (2,3) ３つの parallel class resolution parallel class に分解することを resolution と言う。 繰り返し数 r は、定理13.2により、次のようになる。

30 13.5.1 アフィン平面(Affine planes)
アフィン平面 AG(2,q) は、次の状況を満たす。 (A1)　どの直線も q 点をもつ。 (A2)　どの２点もただ一つの直線に乗る。 (A3)　どの点も q+1 直線に乗る。 (A4)　直線は　　　　本 ある。 アフィン平面は　　　　　 デザインになる。 以下に、その構成方法を２つ示す。

31 アフィン平面の構成方法 その１ 射影平面上の任意の１つの直線を消す。 消される直線上の点も全て消す。 消される直線を「無限遠直線」
アフィン平面の構成方法　その１ 射影平面上の任意の１つの直線を消す。 消される直線上の点も全て消す。 消される直線を「無限遠直線」 消される点を「無限遠点」という。 parallel class は、無限遠点から出ている直線の集合。

32 アフィン平面の構成方法 その２ q を素数の累乗として、 上の点を考える。 直線を次のように定義する。 parallel class は、
アフィン平面の構成方法　その２ q を素数の累乗として、　　　　 上の点を考える。 直線を次のように定義する。 parallel class は、 　　　　　　　　　と、

33 13.5.2 アフィン平面のBlocking set アフィン平面の blocking set は、どの直線とも交差する 点の集合。
平行でない（同じ点を含む）２本の直線で、blocking set を構成できる。これの点の数は、2q-1点。 定理13.12 q を素数とする。B がアフィン平面 AG(2,q) の blocking set ならば、 q が素数のときは、「２本の直線」よりも、含まれる点の少 ない blocking set は存在しない。