Additive Combinatorics輪講 6章
[Szemerediの定理] 任意のkとd>0に対して、ある N0が存在して、任意のn>N0に対して、任意のA[n], |A|dnは長さkの等差数列を持つ。 Szemerediの定理のk=3の場合に対するRothの証明を 紹介する。 ここでは[n]の代わりにFpn上で証明する。 [定理6.2.1] 任意のd>0に対して、あるN0が存在し、 任意のn>N0に対して、任意のAFpn , |A|d|Fpn|に 対して、あるa,bFpnが存在し、a,a+b,a+2bAを満た す。
証明の概要 以下のどちらかが成り立つことを示す。 前者が成り立つ時、等差数列はある。 Aが等差数列を多数持つ(ランダムに選んだa,bFpnに対して、 a,a+b,a+2bAである確率が正) AがFpn の(n-1)次元のアフィン部分空間において密度 d+d2/4以上(AはFpn で密度d以上)。 前者が成り立つ時、等差数列はある。 後者が成り立つ時、部分空間上の等差数列はAでも 等差数列である。 後者が成り立つ時、密度が1+d/4倍になるが、密度 は1を超えられないのでいずれ止まる(O(1/d)ステッ プ)。 等差数列が1点になってしまわないか？
フーリエ変換の定義 関数f, g: Fpn Cの内積 フーリエ変換用の正規直交基底を|Fpn|=pn個作る。 tFpnに対してct:Fpn Cをct(x)=wt xと定める。但し w=e2pi/p。 フーリエ変換:
定理6.2.1の証明 集合AFpn , |A|d|Fpn|とすると以下のどちらかが成 立することを示す。 ct(x)=wt x 集合AFpn , |A|d|Fpn|とすると以下のどちらかが成 立することを示す。 Aに少なくともd3|Fpn|2/2-|A|個の等差数列が存在する。 Fpnの(n-1)次元の部分空間Hが存在してAのH上での密度が d+d2/4以上。 A(x)=(xAの時1、そうでないとき0)と置く。 最後の等式はA(x)=0 or 1による
定理6.2.1の証明 E=Ex,y[A(x)A(x+y)A(x+2y)]と置く。 EはA中の等差数列の割合とみなせる。 ct(x)=wt x E=Ex,y[A(x)A(x+y)A(x+2y)]と置く。 EはA中の等差数列の割合とみなせる。 a+b+c=0かつb+2c=0の時だけ非0になる。 c=a, b=-2a
定理6.2.1の証明 もしMd3/2ならばEd3/2となり、A中の(非自明な) 等差数列の数はd3/2|Fpn |-|A| M>d3/2とすると、あるa0が存在して cFpが存在し、E{x|ax=c}[A(x)]>d+d2/4であることを 示す。
定理6.2.1の証明 |Ex[A(x)w-ax]|>d2/2であり、a0からaxは{0,1,…,p- 1}上の一様分布になるので、 B(x)=A(x)-dと置く。 a0から Ex[B(x)]=0 三角不等式より
定理6.2.1の証明 E{x|ax=i}[B(x)]=aiと置くと、(| a0|+|a1|+…+|ap- 1|)/p>d2/2 Ex[B(x)]=0から、 a0+a1+…+ap-1=0。 ⇒(a0+| a0|+a1+|a1|+… +ap-1+|ap-1|)/p>d2/2 よってあるiが存在して、ai+ |ai|>d2/2。すなわ ち ai>d2/4。 ゆえにあるcが存在して、 E{x|ax=c}[A(x)]>d+d2/4
Rothの定理の証明 Fpnを[n]に置き換えて議論する。 A[n], |A|dnは以下のどちらかを満たす。 Aが少なくともd3n2-|A|個の長さ3の等差数列を持つ。 ある等差数列P, |P|>d2sqrt(n)/256が存在して、AはPにおい て密度d+d2/4以上。 それ以外の証明はほぼ同じなので省略。
Behrend’s Construction 任意のe に対して、[n]の大きさW(n1-e)の部分集合 で等差数列を持たないものが存在することを示す。 [定理6.4.1] あるcが存在して、任意のnに対して、等 差数列を含まないA[n], |A|n/2c sqrt(n)が存在する。 (証明) 点集合{xRd |x12+x22+…+xd2=m, 0xik}を考える。 あるmdk2が存在して、解の数はkd/dk2以上。 この時の点集合をSとする。|S|kd/dk2である。
Behrend’s Construction Rdの点を整数に変換する。 f(x1, x2,…,xd)=x1+(2k+1) x2+…+(2k+1)d-1xk f(x)+f(y)=2f(z), x,y,zSならばx+y=2zであるが、これは Sの作り方からあり得ない。 よってA={f(x)|xS}は長さ3の等差数列を持たない。 |A|kd/dk2で整数の大きさは(2k+1)d以下。 nに対してd=sqrt(log(n)), (2k+1)=2sqrt(log n)と選ぶと、 |A|n/2Q(sqrt(log n))。 1940年代に証明されて以降、この記録は現在まで破 られていない。