Document

Extremal Combinatorics
15. Orthogonality and Rank Arguments
2009年7月13日
木下直紀
15.1. Orthogonality
• 2個のベクトル u,v は、内積 <u,v> = 0 のとき、直交
している(orthogonal)という。
• 直感的には、
2個のベクトルが直交 ⇒ ベクトルが「かなり異な
る」
15.1.1. Orthogonal coding
• 族 F の要素からベクトル空間 Fqm への単射
(injection)が可能であるとき、|F | ≦ qm が成り立つ。
• Fqm: 各要素∈{0, …, q–1} の m 次元空間
符号ベクト
ル
(code vector)
単射
族F
ベクトル空間 Fqm
15.1.1. Orthogonal coding
• 命題14.2. 有限次元線形空間 V の部分空間 U⊆V
について、dim U + dim U┴ = dim V
• dim U┴ = {v∈V : v = 0 for all u∈U} を双対(dual)また
は直交補空間(orthogonal complement)という。
• うまく符号ベクトルをとると、各ベクトルはある
次元 d の部分空間に対して直交する。このとき命
題14.2より、
|F | ≦ qm–d が成り立つ。
• このことを用いて次の結果を示す。
15.1.1. Orthogonal coding
•
•
•
•
A,B⊆2X を n 要素集合 X の部分集合族とする。
直積 A×B のサイズはどのくらいだろうか？
何も情報がなければ、|A×B| = |A|・|B| ≦ 22n
A,B がいずれも単調増加（減少）のときは？
• 定理11.6.(Kleitman) |A|・|B| ≦ 2n・|A∩B|
• e.g. X = {1,2,3}, A = {{},{1},{1,2},{1,2,3}}, B = {{},
{3},{2,3},{1,2,3}}, n = 3, |A| = |B| = 4, |A∩B| = 2
• さらに、 A∈A, B∈B について |A∩B| が常に偶数ま
たは常に奇数であるとき、より良い上界が示せる。
15.1.1. Orthogonal coding
•
•
•
•
定理15.1.(Ahlswede–El Gamal–Pang 1984)
A,B : n 要素集合 X の部分集合族
A∈A, B∈B について |A∩B| が常に偶数
⇒ |A|・|B| ≦ 2n
• e.g. X = {1,2,3,4}, A = {{},{2,4},{1,2,3},{1,3,4}}, B =
{{},{1,3},{1,2,4},{2,3,4}}, n = 4, |A| = |B| = 4
• なお「常に奇数」の場合は |A|・|B| ≦ 2n–1 となる
(Exercise 15.1)。
15.1.1.
•
•
•
•
•
•
定理15.1. A,B : n 要素集合 X の部
分集合族、 A∈A, B∈B について
|A∩B| が常に偶数 ⇒ |A|・|B| ≦ 2n
証明.
U,V : A,B に対応する生成(incidence)ベクトル集合
生成ベクトルは F2n 空間。1 + 1 = 0 (mod 2) に注意
U',V' : U,V の張る F2n の部分ベクトル空間
|A|・|B| = |U|・|V| ≦ |U'|・|V'| ≦ 2dim U' + dim V'
生成ベクトルの内積は、対応する集合 A,B の共通
部分サイズのパリティ = |A∩B| mod 2 （常に偶数）
なので、
• for all u∈U, v∈V : <u,v> = 0
15.1.1.
•
•
•
•
•
定理15.1. A,B : n 要素集合 X の部
分集合族、 A∈A, B∈B について
|A∩B| が常に偶数 ⇒ |A|・|B| ≦ 2n
for all u∈U, v∈V : <u,v> = 0 より、U,V は直交
U',V' はそれぞれ U,V の張る空間 ⇒ U',V' も直交
U'⊆V' ┴ および補題14.2より、
dim U' ≦ dim V' ┴ = n – dim V'
|A|・|B| ≦ 2dim U' + dim V' ≦2(n – dim V') + dim V' = 2n
□
• 教科書の証明は「常に奇数」の場合にも対応する
ため少し複雑になっている。上記証明は「常に偶
数」のみに対応して簡略化した。
15.1.2. A bribery party
•
•
•
•
•
•
bribery : わいろ
ある町に n （偶数）人の住人がいる
町会議員はできるだけ次も当選したい
議員は毎年住人に幸福かどうかアンケートを取る
k 年後、町会議員選挙
議員は k 年の間アンケートに幸福(YES)と不幸(NO)
を同じ回数答えた人を「パーティー」に招待する
• 何人パーティーに招待されるか？
• k が奇数なら当然誰も招待されない。k が偶数な
ら？
15.1.2. A bribery party
• 安定性 : どの2年（連続でなくてよい）を比較して
も、ちょうど半分の住人のアンケート結果が異
なっている
• 少なくとも n / k 人は招待されないことを示す。
• s(k) : パーティーに招待されない人数
• i 回目のアンケート結果を (–1,+1) ベクトル vi =
(vi1, …, vin) で表す。vij = +1 ⇔ 住民 j がYESと回答
• s(k) = (v1+…+vk の非ゼロ要素数)
• 安定性より、任意の i ≠ j について <vi,vj> = 0
• 求める結果 s(k) ≧ n / k は次のより一般的な結果で
15.1.2. A bribery party
•
•
•
•
•
•
補題15.2.(Alon 1990a)
1 ≦ i ≦ k について、
v1, …, vk :互いに直交するベクトル
vi = (vi1, …, vin) : vij∈{–1,+1}
実数 c1, …, ck : not-all-zero
⇒ y = c1v1 + … + ckvk は少なくとも n / k 個
0 でない要素を含む。
補題15.2. v1, …, vk :互いに直交, vi = (vi1, …, vin) :
vij∈{–1,+1}, 実数 c1, …, ck : not-all-zero ⇒ y = c1v1 +
… + ckvk は少なくとも n / k 個 0 でない要素を含
む。
15.1.2.
• 証明. 一般性を失わずに、|c1| = maxi |ci|
• y = (y1, …, yn), |y| = (|y1|, …, |yn|)
• s : y の 0 でない要素数 i.e. s = |S|, S = {j : yj ≠ 0}
k
k
kc12 n   ci2 n   ci vi , ci vi 
i 1
i 1
n
  y   yj
j 1
2
j
jS
2
k
k
c v ,c v
i 1
i i

1
  1  y j
s  jS  jS
i 1
2
i i
 y, y
 1

   yj 
 s


 jS



 

Cauchy - Schwartz :   vi2   ui2     vi ui 
 i 1  i 1   i 1

n
n
n
2
2
補題15.2. v1, …, vk :互いに直交, vi = (vi1, …, vin) :
vij∈{–1,+1}, 実数 c1, …, ck : not-all-zero ⇒ y = c1v1 +
… + ckvk は少なくとも n / k 個 0 でない要素を含
む。
• v1, …, vk は互いに直交しているので、 i  1
 vi , v1 : 直交
n
n
n
k
 vi , v1  0
yj 
y j v1 j 
ci vij v1 j
15.1.2.

j 1
vij   1,1


j 1
k
j 1 i 1
n
k
i 1
j 1
i 1
  ci  vij v1 j   ci vi , v1  c1 v1 , v1  c1n
2
 c12 n 2
• 前頁より、 2
1
n


kc1 n    y j  
 s 
s  jS
s
k

□
15.1.2. A bribery party
• Hadamard行列 H : 要素が {–1,+1} からなり、
各行（列）が直交する n×n 行列
• H のランク（線形独立な行の数） : rk(H) = n
• Alonの補題15.2より、H の十分大きな部分行列も、
最大ランク（= 行数）を持つことがいえる。
• 以下、Hadamard行列の要素は実数として扱う。
• 系15.3. t > (1 – 1 / r)・n ⇒ n×n Hadamard行列 H の
r×t 部分行列 H' はランク r を持つ。
15.1.2.
•
•
•
•
•
系15.3. t > (1 – 1 / r)・n
⇒ n×n Hadamard行列 H の
r×t 部分行列 H' はランク r
証明. 背理法。
rk(H') < r とすると、H' のある 2 行 v1,v2 について、
∃c1,c2 ≠ 0 s.t. c1v1 + c2v2 = 0 … (1)
v1,v2 に対応する H の行 : u1,u2
補題15.2より、c1u1 + c2u2 は少なくとも n / r 個
0 でない要素を含む
• ⇒ t > (1 – 1 / r)・n より、c1v1 + c2v2 は少なくとも1
個
0 でない要素を含む
• ⇒ (1)に矛盾
15.1.2. A bribery party
• 行列 M の一部を書き換えてランクを減らす事を考
える
• 定義. rigidity RM(r) : M のランクを r 以下にするため
に書き換えなければならない最小の要素数
• n×n Hadamard行列については、以下の結果がある
• (Pulak–Razborov–Savicky 1988) RH(r) ≧ n2 / r3 log r
•• 系15.3より、次の（上記より強い）結果がいえる
系15.4. H : n×n Hadamard行列 ⇒ R (r) ≧ n2 / r2
H
15.1.2.
•
•
•
•
•
系15.4. H : n×n Hadamard行列
⇒ RH(r) ≧ n2 / r2
n
r
証明.
r
r
H を n / r 個のr×n 部分行列に分割
(n / r)2 未満しか書き換えなかったとするr
部分行列のうち最低1個は n / r 未満の書き換え
書き換えられていない部分だけの部分行列を考え
ると、t > n – n / r として r×t 行列が取れる
• ⇒ 系15.3より、この部分行列のランクは r 以上
• ⇒ RH(r) ≧ n2 / r2
H
□
15.1.3. Hadamard matrices
• Hadamard行列 H : 要素が {–1,+1} からなり、
各行（列）が直交する n×n 行列
•
•
•
•
補題15.5.(J. H. Lindsey)
H : n×n Hadamard行列
T : H の任意の a×b 部分行列
⇒ T の要素で –1 と +1 の個数の差は高々 abn
補題15.5. n×n Hadamard行列 H の任意の
a×b 部分行列 T において要素 –1 と +1 の
個数の差は高々 abn
15.1.3.
• 証明.(Babai, Frankl and Simon)
• vi = (vi1, …, vin) : H の i 行目ベクトル
• T は H の a 行 b 列部分行列
a
b
   vij とおく。　  abn を示したい。
i 1 j 1
a
• x = (1b0n–b) として、y   y1 ,, yn    vi とおくと、
i 1
• Cauchy-Schwartzの不等式より、
2
2
2
2
2
  x, y  x y  b  y
補題15.5. n×n Hadamard行列 H の任意の
a×b 部分行列 T において要素 –1 と +1 の
個数の差は高々 abn
15.1.3.
• H はHadamardであるので、各行 vi は直交するので、
y  y, y 
2
• 前頁より、
a
a
v ,v
i 1
i
i 1
i
a
a
  vi , v j   vi , vi  an
i 1 j 1
  b  y  abn,   abn
2
a
i 1
2
□
15.1.3. Hadamard matrices
• Hadamard行列の任意の行（列）に –1 をかけたもの
もまたHadamard行列である。
• 上記を用いて、1行目と1列目の要素がすべて1から
なる形にできる。この状態を正規(normalized)とい
う。
• 定理15.6.
• H : n×n 正規Hadamard行列
• このとき1行目と1列目以外は –1,+1 が n / 2 ずつあ
る。
• n > 2 ならば、1行（列）目を除く任意の2行（列）
で、
15.1.3.
定理15.6. H : n×n 正規Hadamard行列 ⇒ n > 2 な
らば、1行（列）目を除く任意の2行（列）で、
同じ位置にある +1 の数はちょうど n / 4 個で
ある。
• 証明.
• 「1行目と1列目以外は –1,+1 が n / 2 ずつある」は
自明
• （他の行（列）との内積が 0 になるため）
ui
vi
個数
• 1行目以外の任意の2列を u,v とおく
+1 +1
a
• u,v で両方 +1 が a 個とする
+1 –1 n / 2 – a
• 片方 +1 がそれぞれ n / 2 – a 個
• 両方 –1 が n – a – (n / 2 – a) = a 個 –1 +1 n / 2 – a
–1 –1
a
• <u,v> = 2a – (n – 2a) = 4a – n = 0
n
計
• よって a = n / 4
□
15.1.3. Hadamard matrices
•
•
•
 1

H : n×n Hadamard行列
 1
H 
1
Cn : H, –H のすべての

 1

行の –1 を 0 に置き換えた
 1

ベクトルの集合
 1
H 
Cn をHadamard符号という
1

e.g.   1
 1111 
 1  1  1

 1100 
 1  1  1



 1010 
1 1 1



 1  1  1
 1001 
,C  

 1  1  1 4 0000 

0011
 1  1  1


 1  1  1


0101



0110 
 1  1  1


• 定理15.7.
• Hadamard符号 Cn において、
どの符号語も少なくとも n / 2 箇所異なる。
15.1.3.
•
•
•
•
•
定理15.7. Hadamard符号 Cn において、
どの符号語も少なくとも n / 2 箇所異
なる。
証明.
任意の x,y∈Cn, x ≠ y
x,y がそれぞれ H,–H の同じ i 行目 ⇒ 全個所異なる
それ以外 ⇒ H の中に異なる2行 u,v が存在して、
x∈{u,–u}, y∈{v,–v} （ただし u,v の–1は0に読み替
え）
• ±u,±v はそれぞれ直交するので、<u,v> = 0
• u,v は n / 2 箇所異なる ⇒ x,y は n / 2 箇所異なる
□
15.1.3. Hadamard matrices
• 定義13.1.
• X = {1, …, v} : 点(point)の集合
• X における (v,k,l)-designは X の異なる部分集合
(block)の族 D であって、次を満たすものをいう。
• (1) 各ブロックはそれぞれちょうど k 個の点を含む
• (2) すべての異なる点の2個組(pair)はちょうど l 個
のブロックに含まれる
• 上記で2個組を t 個組にしたもの → t-(v,k,l) 設計
• |D| ≡ b = v のとき対称(symmetric)であるという
15.1.3. Hadamard matrices
• 定義13.1. (v,k,l)-design : v 要素集合 X の k-uniformな
部分集合(block)の族 D で、X の要素の任意のペア
がちょうど l 個のブロックに含まれるもの。
• 特に、|D| = v のとき対称(symmetric)であるという。
• e.g. (7,3,1)-design
X
1234567
D
1
2
4
1
3
7
1
5
6
2
3
5
2
6
7
3
4
6
4
5
7
15.1.3.
定義13.1. (v,k,l)-design : v 要素集合 X の k-uniformな部
分集合(block)の族 D で、X の要素の任意のペアが
ちょうど l 個のブロックに含まれるもの。|D| = v の
とき対称
定理15.6. H : n×n 正規Hadamard行列 ⇒ n > 2 ならば、
1行（列）目を除く任意の2行（列）で、同じ位置に
ある +1 の数はちょうど n / 4 個である。
• 定理15.8. 次数 4n のHadamard行列に関して、
(4n – 1, 2n – 1, n – 1)-designが存在する。
• 証明.
• H : 次数 4n の正規Hadamard行列（1行,1列が全て
1）
• M : H から1行,1列を削除し、–1を0に書き換えた行
列
• 定理15.6より、各行はちょうど 2n – 1 個の 1 を含
み、どの2列の組もちょうど n – 1 個の 1 を共有す
15.1.3.
定義13.1. (v,k,l)-design : v 要素集合 X の k-uniformな部
分集合(block)の族 D で、X の要素の任意のペアが
ちょうど l 個のブロックに含まれるもの。|D| = v の
とき対称
• e.g. (7,3,1)-design
• M の各列を {1, …, 7} の各要素に対応
• どの2列もちょうど1ペアの1を共有する
 1

 1
 1

 1
H 
 1
 1

 1
 1

 1  1  1  1  1  1  1

0 0 0

 1  1  1  1  1  1  1
1 0 0

1 1 1 1 1 1 1
1 1 0


 1  1  1  1  1  1  1
 M  0 1 1

 1  1  1  1  1  1  1
1 0 1

 1  1  1  1  1  1  1
0 1 0

 1  1  1  1  1  1  1

0 0 1

 1  1  1  1  1  1  1
1 0 1 1

0 1 0 1
0 0 1 0

0 0 0 1
1 0 0 0 
1 1 0 0

0 1 1 0
15.2. Rank arguments
• ランクのsub-additivityの応用など
• ランクのsub-additivityとは？
• 任意の行列 A, B について、
• rk(A+B) ≦ rk(A) + rk(B)
• Formula sizeのlower boundへの応用
15.2.1. Balanced families
• 集合 X の部分集合の族 A1, …, Am は、I,J⊆{1, …, m}
s.t. I,J ≠ f, I∩J = f が存在して、次を満たすとき平
衡(balanced)であるという。
 A   A かつ　 A   A
i
iI
j
jJ
i
iI
j
jJ
• 定理15.9.(Lindstorm 1993)
• n 要素集合の異なる部分集合からなる、
サイズ m ≧ n + 2 の族は平衡である。
15.2.1.
定理15.9. n 要素集合の異なる部分集合か
らなる、サイズ m ≧ n + 2 の族は平衡であ
る。
• 証明.
• A ⊆ {1, …, n} について、
• ( A, A )
の生成ベクトルを以下のように定める
• v = (x1, y1, …, xn, yn), xi = 1 iff i∈A, yi ≡ 1 – xi
• これらのベクトルは、x1 + y1 = … = xn + yn を満たす
（実数上）ベクトル空間 V に属する。
• 主張15.10. dim V = n + 1
• 証明. x1, …, xn, y1 がわかれば、残り y2, …, yn は
yi = x1 + y1 – xi として線形従属（主張15.10証明終）
定理15.9. n 要素集合の異なる部分集合か
らなる、サイズ m ≧ n + 2 の族は平衡であ
る。
15.2.1.
•
•
•
•
集合 Ai に対応する生成ベクトル : vi = (vi,1, …, vi,2n)
v1, …, vm は空間 V に属する。
m ≧ n + 2 > n + 1 = dim V より、
I,J⊆{1, …, m} s.t. I,J ≠ f, I∩J = f および任意の
i∈{1, …, m} について i,bi > 0 が存在し、次を満た
す。
 i vi   b j v j

iI
jJ
A  B  A B
• これは次を意味する。
 Ai   Aj かつ　 Ai   Aj   Ai   Aj
iI
jJ
iI
jJ
iI
jJ
15.2.2. Lower bounds for boolean formulas
• DeMorgan formula（または単にformula） : And, Or,
Notゲートにより木構造状に表現される回路
• (1) ブール変数 xi とその否定xi はサイズ1のformula
である（これらは葉と呼ばれる）。
• (2) F1,F2 がサイズ l1,l2 のformulaであるとき、F1∧F2
および F1∨F2 はサイズ l1+l2 のformulaである。
• Formula F のサイズは F の含む葉の数に等しい。
• あるブール関数 f を表わすのに必要なformulaのサ
イズはどのくらい？ → lower bounds
15.2.2. Lower bounds for boolean formulas
• 簡単なcountingで、ほとんどの n 変数関数が n の指
数関数サイズ必要であることがわかる。
• にもかかわらず、明示的な関数としてはいまだに
n3 – o(1) のもの(Hastad 1993)しか得られていない。
• 葉に変数の否定xi を認めない(monotone)場合
• monotoneな関数しか計算できない
• ∀i : xi ≦ yi ⇒ f (x1, …, xn) ≦ f (y1, …, yn)
• この場合超多項式サイズ必要な関数が知られてい
る。
15.2.2. Lower bounds for boolean formulas
Reduction to set-covering
• A,B ⊆ {0,1}n, A∩B = f について、
• あるブール関数 F が存在して、
• ∀a∈A : F(a) = 1, ∀b∈B : F(b) = 0
• を満たすとき、F は「A,B を分割する」という。
15.2.2. Lower bounds for boolean formulas
•
•
•
•
•
•
定義15.11.
A,B ⊆ {0,1}n, A∩B = f, R = A'×B' ⊆ A×B,
以下の条件を満たすとき R をrectangleという。
∃i, ∀a∈A', ∀b∈B' : a(i) ≠ b(i)
次のより強い条件を満たすときmonotoneという。
∃i, ∀a∈A', ∀b∈B' : a(i) = 1, b(i) = 0
• e.g. A,B ⊆ {0,1}3,
• A = {100,101,110,111}, B = {000,001,010,011}
• R = A'×B' ⊆ A×B はmonotone rectangle
15.2.2.
定義15.11. A,B ⊆ {0,1}n, A∩B = f, R = A'×B' ⊆
A×B, ∃i, ∀a∈A', ∀b∈B' : a(i) ≠ b(i) ⇒ R : rectangle,
さらに a(i) = 1, b(i) = 0 ならmonotone
• 次の定理は、DeMorgan formulaのサイズに関する
lower boundを証明する問題を、直積 A×B をdisjoint
なrectanglesでカバーする問題に還元している。
• 補題15.12.(Rychkov 1985)
• A,B がサイズ t の(monotone) DeMorgan formulaに
よって分割されるとき、集合 A×B は t 個の
(monotone) rectanglesによってカバーできる。
15.2.2.
•
•
•
•
•
•
•
定義15.11. A,B ⊆ {0,1}n, A∩B = f, R = A'×B' ⊆ A×B, ∃i,
∀a∈A', ∀b∈B' : a(i) ≠ b(i) ⇒ R : rectangle, さらに a(i) =
1, b(i) = 0 ならmonotone
補題15.12. A,B がサイズ t の(monotone) DeMorgan
formulaによって分割されるとき、集合 A×B は t 個
の(monotone) rectanglesによってカバーできる。
証明.
F : A,B を分割するDeMorgan formula
i.e. A ⊆ F–1(1), B ⊆ F–1(0)
t = size(F) とおき、t に関する帰納法を用いる。
size(F) = 1 のとき :
F は xi もしくはその否定、
A×B はそれ自身rectangle、命題は成り立つ。
15.2.2.
•
•
•
•
•
•
•
•
定義15.11. A,B ⊆ {0,1}n, A∩B = f, R = A'×B' ⊆ A×B, ∃i,
∀a∈A', ∀b∈B' : a(i) ≠ b(i) ⇒ R : rectangle, さらに a(i) =
1, b(i) = 0 ならmonotone
補題15.12. A,B がサイズ t の(monotone) DeMorgan
formulaによって分割されるとき、集合 A×B は t 個
の(monotone) rectanglesによってカバーできる。
size(F) = t のとき :
t 未満のサイズについて命題が成り立つと仮定。
F = F1∧F2 とする（F = F1∨F2 の場合も同様）
ti = size(Fi) とおく ⇒ t = t1 + t2
B1 ≡ {b∈B : F1(b) = 0}, B2 ≡ B – B1
i = 1,2 について、Fi は A,Bi を分割。
仮定より、A×Bi は ti 個のrectanglesでカバーできる。
A×B = A×B1∪A×B2 より、A×B は t = t1 + t2 個の
rectanglesでカバーできる。
□
15.2.2. Lower bounds for boolean formulas
•
•
•
•
•
•
•
Rychkovの補題を、次のKhrapchenkoの定理に適用。
A,B ⊆ {0,1}n, A∩B = f について、
N(A,B) = {(a,b) : a∈A, b∈B は1箇所だけ異なる}
上記のような a,b を「隣り合う」という。
直感的には、
N(A,B) が大きい ⇒ A,B を分割するformulaも大きい
∵Formulaはよく似た入力も区別しなければならな
い
15.2.2. Lower bounds for boolean formulas
• 定理15.13.(Khrapchenko 1971)
2
N  A, B 
• A,B がDeMorgan formula F
size F  
によって分割されるとき、
AB
•
•
•
•
証明.
t
補題15.12の示すrectangle分割 : A  B  i 1 Ai  Bi
このとき、Ri ≡ N(A,B)∩(Ai×Bi) とおく。
Rectangleおよび隣接の定義より、Ai×Bi は各行・各
列に高々1個 Ri の要素を含む。
定理15.13. A,B がDeMorgan formula F によっ
2
て分割されるとき、
N  A, B 
size F  
AB
15.2.2.
• 任意の a∈Ai について、(a,b)∈Ri を満たす b∈Bi は a
と1箇所だけ異なる。
• ⇒ |Ri| ≦ |Ai|, |Ri| ≦ |Bi|
• ⇒ |Ri|2 ≦ |Ai|・|Bi|
• Ri はdisjointなので N(A,B) = R1 ∪ … ∪ Rt
N  A, B   i 1 Ri , N  A, B 
t
2

t
i 1

2
Ri
 viui    vi2  ui2 
• Cauchy-Schwartzの不等式より、
2

t
i 1
  t 
2
Ri
t
i 1
Ri  t  i 1 Ai  Bi  t A  B

t
□
15.2.2.
•
•
•
•
•
定理15.13. A,B がDeMorgan formula F によっ
2
て分割されるとき、
N  A, B 
size F  
AB
定理15.3により、2次サイズのlower boundが示せる。
e.g. パリティ関数 f = x1 + … + xn
A = f –1(1), B = f –1(0), |N(A,B)| = n|A| = n|B|
⇒ size( f ) ≧ n2
この定理で示せるlower boundは2次まで。
15.2.2. Lower bounds for boolean formulas
The rank lower bound
• R = {R1, …, Rn} : A×B をカバーするrectangleの集合
• Canonical（正準） monotone cover Rmon(A,B) :
• Ri = {(a,b)∈A×B : a(i) = 1, b(i) = 0}
• e.g.
001
000
010
A＼B 100
R1
R2
R3
011
110
111
101
15.2.2. Lower bounds for boolean formulas
• A,B 上の行列 : 行、列をそれぞれ A,B の要素でイン
デックス付けした行列
• Rectangle R ⊆ A×B に対応する部分行列 : MR
• Mˆ R : u , v   R
となる mu,v を 0 に書き換えた
行列
• L+( f ) : f を計算するのに必要な最小のmonotone
DeMorgan formulaのサイズ
15.2.2. Lower bounds for boolean formulas
•
•
•
•
定理15.14.(Razborov 1990)
A,B ⊆ {0,1}n, f : monotoneブール関数
任意の a∈A, b∈B について f (a) = 1, f (b) = 0
A,B 上の任意の非零行列 M について、
rk M 
L  f  
max RRmon  A, B rk M R 
15.2.2.
定理15.14. A,B ⊆ {0,1}n, f : monotoneブール関数,
∀a∈A, ∀b∈B : f (a) = 1, f (b) = 0 ⇒ A,B 上の任意の非
rk M 
零行列 M について
L  f  
max RRmon  A, B rk M R 
• 証明.
• t = L+( f ) とおく。
• 補題15.12より、A×B をカバーするdisjointな
monotone rectanglesの集合R が存在し、|R| ≦ t
• M  RR Mˆ R
• ランクのsub-additivityより、
• rk M   rk RR Mˆ R  RR rk Mˆ R


 
15.2.2.
定理15.14. A,B ⊆ {0,1}n, f : monotoneブール関数,
∀a∈A, ∀b∈B : f (a) = 1, f (b) = 0 ⇒ A,B 上の任意の非
rk M 
零行列 M について
L  f  
max RRmon  A, B rk M R 
• 任意の R∈R について、R∈R' となるようなrectangle
R'∈Rmon(A,B) が存在する。よって
• rk M R   rk Mˆ R  rk Mˆ R
• rk M   R  max rk Mˆ 
   


 
RR mon A, B
R
• よって t = |R| = L+( f ) に関するlower boundが示せた。
□
15.2.2.
定理15.14. A,B ⊆ {0,1}n, f : monotoneブール関数,
∀a∈A, ∀b∈B : f (a) = 1, f (b) = 0 ⇒ A,B 上の任意の非
rk M 
零行列 M について
L  f  
max RRmon  A, B rk M R 
• Monotoneでないformulaのlower bound :
• Ri' = {(a,b)∈A×B : a(i) = 0, b(i) = 1}
• という n 個の双対(dual)なrectanglesを Rmon(A,B) に
加えて用いることで同様に示せる。
• しかし、その場合定理15.14の式の右辺は O(n) を超
えないことが示されている(Razborov 1992)。
• Monotoneな場合、O(n) 以上のlower boundも示せる。
15.2.2. Lower bounds for boolean formulas
The lower bound for Paley functions
• 2部グラフ G = (V1,V2,E), |V1| = |V2| = n
• このグラフにmonotoneブール関数 fG,k を関連付け
る。
• f : 2n 変数関数、変数が頂点に対応
• f は X ⊆ V1∪V2 を受け取り、X がサイズ k 以下のあ
るS ⊆ V1 とその共通隣接頂点(common neighbors)
G(S)
S  を含むとき、またその時に限り受理。
 j V2 : i, j  E for all i  S
GG(S)
• f G ,k  X   

xi
S V1 , S  k iS G  S 
S
•
V1
V2
15.2.2. Lower bounds for boolean formulas
• また、共通非隣接頂点(common non-neighbors)
Ĝ S  を次で定義する。
• Gˆ S    j  V2 : i, j   E for no i  S 
 xi
• f G ,k  X   
S V1 , S  k iS G  S 
^
G(S)
S
• 各And節は長さ 2n 以下、
V1
V2
n
• Orで結ばれたAnd節の数はi 0  i 
 
• Isolated neighbor conditionを満たすグラフとしては、
上記のformulaはほぼoptimal
k
15.2.2. Lower bounds for boolean formulas
• Isolated neighbor condition for k : 2部グラフ
G(V1,V2,E) において、|S|+|T| = k を満たす任意の
disjointな S,TG⊆SV 
Gˆ T   f
1 について
• 定理15.15.(Gál 1998)
• G がisolated neighbor condition for 2k を満たすとき、
関数 fG,k はサイズが ik0  ni  より小さいmonotone
DeMorgan formulaを持たない。
15.2.2.
Isolated neighbor condition for k : 2部グラフ G(V1,V2,E)
において、|S|+|T| = k を満たす任意のdisjointな S,T ⊆
V1 について
GS   Gˆ T   f
定理15.15. G がisolated neighbor
condition for 2k を満た
k
n
 i  0  i  より小さい
すとき、関数 fG,k はサイズが
monotone DeMorgan formulaを持たない。
• 証明.
• G がisolated neighbor condition for 2k を満たすなら、
次のintersection propertyが成り立つ。
• Intersection property : サイズ k 以下の任意の S,T ⊆
^
V1 について
S  T  f iff GS   Gˆ T   f
G(S) G(T)
• 以下の0-1行列 M を考える。
S
• M : 行・列は V1 のサイズ k 以下の
部分集合でインデックス付けされ、
T V
各要素は次で定義される。
V2
1
Intersection property (for 2)
• MS,T = 1 iff S∩T = f
Isolated neighbor condition for k : 2部グラフ G(V1,V2,E)
において、|S|+|T| = k を満たす任意のdisjointな S,T ⊆
V1 について
GS   Gˆ T   f
定理15.15. G がisolated neighbor
condition for 2k を満た
k
n
 i  0  i  より小さい
すとき、関数 fG,k はサイズが
monotone DeMorgan formulaを持たない。
15.2.2.
• M : 行・列は V1 のサイズ k 以下の部分集合でイン
デックス付けされ、各要素は次で定義される。
• MS,T = 1 iff S∩T = f
T
1
1
1
1
1
S
M  1
1

1
1
1
1
1
0
1
1
1
0
0
0
1
1
1
1
1
0
1
1
1
0
1
0
0
1
1
1
1
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
1
1
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
0
0
0
0
1   {}
1   {1}
1   {2}
0   {3}
0   {4}
1   {1,2}
0   {1,3}
0   {1,4}
0   {2,3}
0   {2,4}
0   {3,4}
^
G(T)
G(S)
S
1
2
3
T
4
V1
V2
Intersection property (for 2)
15.2.2.
Isolated neighbor condition for k : 2部グラフ G(V1,V2,E)
において、|S|+|T| = k を満たす任意のdisjointな S,T ⊆
V1 について
GS   Gˆ T   f
定理15.15. G がisolated neighbor
condition for 2k を満た
k
n
 i  0  i  より小さい
すとき、関数 fG,k はサイズが
monotone DeMorgan formulaを持たない。
• これは14.2.3節で扱ったdisjointness行列 D(n,k) であ
る。
k
• 定理14.2.3より、M
は F2 上の最大ランクを持つ。
n


rk F2 M     
i
i 0  
•
• 定理15.14を適用するため、M の行・列にベクトル
集合 A,B ⊆ {0,1}2n のベクトルによりラベル付けす
る。
• 以下の条件を満たすような A,B を作りたい :
• (a) ∀a∈A : fG,k(a) = 1, ∀b∈B : fG,k(b) = 0
15.2.2.
•
•
•
•
•
•
•
Isolated neighbor condition for k : 2部グラフ G(V1,V2,E)
において、|S|+|T| = k を満たす任意のdisjointな S,T ⊆
V1 について
GS   Gˆ T   f
定理15.15. G がisolated neighbor
condition for 2k を満た
k
n
 i  0  i  より小さい
すとき、関数 fG,k はサイズが
monotone DeMorgan formulaを持たない。
S⊆V1 に対応する行 : vS i   1  i  S  GS 
T⊆V1 に対応する列 : uT i   0  i  T  Gˆ T 
A = {vS : S⊆V1, |S| ≦ k}, B = {uT : T⊆V1, |T| ≦ k}
条件確認(a) ∀a∈A : fG,k(a) = 1, ∀b∈B : fG,k(b) = 0
fG,k(x) = 1 iff x ≧ vS for some S ∴∀a∈A : fG,k(a) = 1
Intersection propertyより、
∀vS,uT, ∃i : 0 = uT(i) < vS(i) = 1 ∴∀b∈B : fG,k(b) = 0
15.2.2.
Isolated neighbor condition for k : 2部グラフ G(V1,V2,E)
において、|S|+|T| = k を満たす任意のdisjointな S,T ⊆
V1 について
GS   Gˆ T   f
定理15.15. G がisolated neighbor
condition for 2k を満た
k
n
 i  0  i  より小さい
すとき、関数 fG,k はサイズが
monotone DeMorgan formulaを持たない。
• 条件確認(b) ∀R∈Rmon(A,B) : rk(MR) = 1
• 各ノード i∈V1∪V2 について、
• Ri = {(vS,uT) : vS(i) = 1, uT(i) = 0} : rectangle
• vS  S  GS , uT  T  Gˆ T 
• M S ,T  1  S  T  f  GS   Gˆ T   f より、
• i∈V1 ⇒ S∩T ≠ f ⇒ MS,T = 0
• i∈V2 ⇒ GS   Gˆ T   f⇒ MS,T = 1
• Ri に対応する行列 M は全部0または全部1 ⇒ ラン
ク1
15.2.2.
Isolated neighbor condition for k : 2部グラフ G(V1,V2,E)
において、|S|+|T| = k を満たす任意のdisjointな S,T ⊆
V1 について
GS   Gˆ T   f
定理15.15. G がisolated neighbor
condition for 2k を満た
k
n
 i  0  i  より小さい
すとき、関数 fG,k はサイズが
monotone DeMorgan formulaを持たない。
• Ri に対応する行列 M は全部0 or 全部1 ⇒ ランク≦1
• R = {Ri : v∈V1∪V2} : canonical monotone cover
• 定理15.14より、
k


rk
M
L  f G ,k  
 rk M     n 
i
max RR rk M R 
i 0  
□
定理15.14. A,B ⊆ {0,1}n, f : monotoneブール関数,
∀a∈A, ∀b∈B : f (a) = 1, f (b) = 0 ⇒ A,B 上の任意の非
rk M 
零行列 M について
L  f  
max RRmon  A, B rk M R 
15.2.2. Lower bounds for boolean formulas
• Isolated neighbor conditionを満たす k = W(log n) のグ
ラフ : Paley graphs Gn (Sec.11.3.2)
• ⇒ fG,k を表現するmonotone formulaのサイズの
lower bound :  nk   n W logn  : 超多項式
• Circuit（計算結果を再利用できる）はformulaより
強力
• Monotone circuitで多項式サイズだがmonotone
formulaでは超多項式になる例(Karchmer-Wigderson
1990)も存在

Download Report