Additive Combinatorics輪講 ３章前半
３章の内容 Sum Product Theoremの応用 Sum Product Theoremの証明の概要。 組合せ幾何 解析/PDE 数論 群論 Extractor Theory Sum Product Theoremの証明の概要。 正確な証明は４章(輪講ではさしあたってパスする)
3.1 Sum Product Theorem 定理[ES] F=Rとする。e>0, AFに対し て、|A+A||A|1+e又は|AA||A|1+eが成り立つ。 有限体に拡張したい。 |A|=|F|を許すと、 |A+A| ,|AA||F|=|A|で都合が悪い。 AがFの部分体だとA+A=AA=Aで都合が悪い。 定理[BT,K] pを素数、F=Fpとする。 e>0, AF, |A||F|0.9に対して|A+A||A|1+e又は |AA||A|1+eが成り立つ。 e=1/3で成立 e=1-o(1)で成立すると予想されている Erdos, szemeredi Bourgain, tao, konyagin e=0.01で成立 e0.5でなければならない
3.2.1 組合せ幾何 F2上の幾何を考える。PをF2上のn個の点、LをF2上の n個の直線とする。 I={(l,p)|lL, pP, pはl上にある}の大きさを知りたい。 F=F5 L={y=2x+1} P={(4,4)} |I|=1
|I|の上界 SPTの登場前 定理[自明] 任意の体Fに対して|I|=O(n3/2) 定理[E] F=Rの時、|I|=O(n4/3) 定理[BT] F=Fpの時、|I|=O(n3/2-e) Elekes Bourgain, tao
|I|=O(n3/2)の証明 dp,l=(点pが直線l上にある時1, そうでないとき0)とす る。 f(l)=SpPdp,l : 直線l上にある点の数 g(p)=SlLdp,l : 点pが乗っている直線の数 (Cauchy-Schwartzから) （異なる2点を通る 直線は高々1つ） |I|について解けば|I|=O(n3/2)となる。
3.2.2 解析 全ての方向の長さ1の線分を含む領域で、面積が最 小なものを知りたい(解析やPDEに応用があるらしい)。 高さ1の正三角形: 1/sqrt(3)0.58 定理[B] 全ての方向の長さ1の線分を含む、任意に面 積の小さい領域SR2を作ることができる。 Besicovitch
Bescovitchの構成法
有限体 S(Fp)dが全ての方向の直線を含む時、掛谷集合と 呼ぶ。 全てのbFpd\{0}に対して、あるaFpdが存在し、任 意のtFpに対して、a+tbS。 B(d)を|S|=W(pr)の掛谷集合Sが存在する最小のrとす る。 B(d)=dと予想されている。 1916年頃に東北大学の数学科で助教授をしていた掛谷
B(d)の下界 SPTの登場前 定理[自明] B(d)d/2 定理[W] B(d)d/2+1 SPTの登場後 定理[BT] B(d)d/2+1+10-10 Wolff Borgain, tao
B(d)d/2の証明 Pを(Fp)d中の点集合、Lを(Fp)d中の直線、 I={(p,d)PL | pL}とすると、|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/2pd/2 よってB(d)d/2