Document

M2 吉田

Sum Product Theoremの応用
◦
◦
◦
◦
◦

組合せ幾何
解析/PDE
数論
群論
Extractor Theory
Sum Product Theoremの証明の概要。
◦ 正確な証明は４章(輪講ではさしあたってパスする)


定理[ES] F=Rとする。 e>0, A Fに対して、
|A+A| |A|1+e又は|A A| |A|1+eが成り立つ。
有限体に拡張したい。
e=1/3で成立
e=1-o(1)で成立すると予想されている
◦ |A|=|F|を許すと、 |A+A| ,|A A| |F|=|A|で都合が悪い。
◦ AがFの部分体だとA+A=A A=Aで都合が悪い。

定理[BT,K] pを素数、F=Fpとする。 e>0, A F,
|A| |F|0.9に対して|A+A| |A|1+e又は|A A| |A|1+eが成り
立つ。
e=0.01で成立
e 0.5でなければならない


F2上の幾何を考える。PをF2上のn個の点、LをF2上の
n個の直線とする。
I={(l,p)|l L, p P, pはl上にある}の大きさを知りたい。
F=F5
L={y=2x+1}
P={(4,4)}
|I|=1
0





SPTの登場前
定理[自明] 任意の体Fに対して|I|=O(n3/2)
定理[E] F=Rの時、|I|=O(n4/3)
SPTの登場後
定理[BT] F=Fpの時、|I|=O(n3/2-e)



dp,l=(点pが直線l上にある時1, そうでないとき0)とす
る。
f(l)=SpPdp,l : 直線l上にある点の数
g(p)=SlLdp,l : 点pが乗っている直線の数
| I |  f (l )  1  f (l )  n
lL
 n
lL
 (
lL
 n
pP
p ,l

(Cauchy-Schwartzから)
 
p ,l
lL
)(   p ,l )  n
pP
f (l ) 2
p , p 'P lL
2
g
(
p
)




n
|
I
|

n

 p,l p ',l
p
p  p ' lL
 p ',l
（異なる2点を通る
直線は高々1つ）
|I|について解けば|I|=O(n3/2)となる。

全ての方向の長さ1の線分を含む領域で、面積が最
小なものを知りたい(解析やPDEに応用があるらしい)。
直径1の円: p/40.78
高さ1の正三角形: 1/sqrt(3)0.58

定理[B] 全ての方向の長さ1の線分を含む、任意に面
積の小さい領域SR2を作ることができる。




S (Fp)dが全ての方向の直線を含む時、掛谷集合と呼
ぶ。
全てのb Fpd\{0}に対して、あるa Fpdが存在し、任意
のt Fpに対して、a+tb S。
B(d)を|S|=W(pr)の掛谷集合Sが存在する最小のrとす
る。
B(d)=dと予想されている。





SPTの登場前
定理[自明] B(d) d/2
定理[W] B(d) d/2+1
SPTの登場後
定理[BT] B(d) d/2+1+10-10

Pを(Fp)d中の点集合、Lを(Fp)d中の直線、
I={(p,d) P L | p L}とすると、|I| |P||L|1/2+|L|。

Pを全ての方向の直線を含む点集合(掛谷集合)、Lを
それらの直線とする。
方向は全体で(pd-1)/(p-1)個あるので、|L| (pd-1)/(p-1)。
各直線はp個の点を含むので、p|L| |I| |P||L|1/2+|L|。
|P| |L|1/2(p-1) ((pd-1)(p-1))1/2 pd/2
よってB(d) d/2





Download Report