AC06_yyoshida

M2 吉田悠一




[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に対して、任意のAFpn , |A|d|Fpn|に
して、あるa,bFpnが存在し、a,a+b,a+2bAを満たす。

以下のどちらかが成り立つことを示す。
◦ Aが等差数列を多数持つ(ランダムに選んだa,b Fpnに対して、
a,a+b,a+2b Aである確率が正)
◦ AがFpn の(n-1)次元のアフィン部分空間において密度d+d2/4



関数f, g: Fpn Cの内積 f , g  xEF [ f ( x) g ( x)]
フーリエ変換用の正規直交基底を|Fpn|=pn個作る。
t Fpnに対してct:Fpn Cをct(x)=wt xと定める。但し
w=e2pi/p。
n
p
tx
t , t  E [ tx  ]  E [1]  1
xFpn
xFpn
tx
 s ,  t  E [  ]  E [ ( s t )x ]   E [ ( s t ) x ]  0 ( s  t )
s x
xFpn

i
xFpn
i
i
i
xi Fp
フーリエ変換: f ( x)   fˆ (t )  t ( x) where fˆ (t )  f ,  t
tFpn
ct(x)=wt

集合A Fpn , |A| d|Fpn|とすると以下のどちらかが成
立することを示す。
◦ Aに少なくともd3|Fpn|2/2-|A|個の等差数列が存在する。
◦ Fpnの(n-1)次元の部分空間Hが存在してAのH上での密度が
d+d2/4以上。

A(x)=(x Aの時1、そうでないとき0)と置く。
A( x)   Aˆ (t )  ( x) where Aˆ (t )  E[ A( x)  ( x)]
t
x
tFpn
t
Â(0 )  
2
2
ˆ
 A(t )  A, A  E[ A( x) ]  
t
x
最後の等式はA(x)=0 or 1による
x
ct(x)=wt x


E=Ex,y[A(x)A(x+y)A(x+2y)]と置く。
EはA中の等差数列の割合とみなせる。
E  Ex, y
 Aˆ (a)  ( x) Aˆ (b)  ( x  y) Aˆ (c)  ( x  2 y)
a
a
b
b
c
c
 a ,b ,c Aˆ (a ) Aˆ (b) Aˆ (c)E x , y  a ( x)  b ( x  y )  c ( x  2 y )
 a ,b ,c Aˆ (a ) Aˆ (b) Aˆ (c)E x  a ( x)  b ( x)  c ( x)E y  b ( y )  c ( y )  c ( y )
 a ,b ,c Aˆ (a ) Aˆ (b) Aˆ (c)E x  a b  c ( x)E y  b  2 c ( y )

a+b+c=0かつb+2c=0の時だけ非0になる。
◦ c=a, b=-2a
E  a Aˆ (a ) 2 Aˆ (2a )   3  a  0 Aˆ (a ) 2 Aˆ (2a)
   M a  0
3
Aˆ (a )
2
  3  M where M  max a  0 Aˆ (a )

もしM d3/2ならばE d3/2となり、A中の(非自明な)等
差数列の数はd3/2|Fpn |-|A|
◦ nが十分大きければ正
 M>d3/2とすると、あるa

c Fpが存在し、E{x|a
す。
ˆ (a)   3 / 2
A
0が存在して
2/4であることを示
[A(x)]>d+d
x=c}
Aˆ (t )  E[ A( x)  t ( x)]
x

|Ex[A(x)w-ax]|>d2/2であり、a0からaxは{0,1,…,p1}上の一様分布になるので、
1
1
1
2
0
1
p 1
E
A( x) 
E
A( x)   
E
A( x)

p { x|a x 0}
p { x|a x 1}
p { x|a x  p 1}
2







B(x)=A(x)-dと置く。
◦ a0から Bˆ (a)  Aˆ (a)
◦ Ex[B(x)]=0

三角不等式より
1
p
E
{ x|a x 0}
B( x)  1
p
E
{ x|a x 1}
B( x)    1
p
E
{ x|a x  p 1}
B( x) 
2
2

E{x|a x=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。すなわち




Fpnを[n]に置き換えて議論する。
A [n], |A| dnは以下のどちらかを満たす。
◦ Aが少なくともd3n2-|A|個の長さ3の等差数列を持つ。
◦ ある等差数列P, |P|>d2sqrt(n)/256が存在して、AはPにおいて
て密度d+d2/4以上。

それ以外の証明はほぼ同じなので省略。

任意のe に対して、[n]の大きさW(n1-e)の部分集合
で等差数列を持たないものが存在することを示す。
[定理6.4.1] あるcが存在して、任意のnに対して、等
差数列を含まないA[n], |A|n/2c sqrt(n)が存在する。
(証明)
 点集合{xRd |x12+x22+…+xd2=m, 0xik}を考える。
 あるmdk2が存在して、解の数はkd/dk2以上。
 この時の点集合をSとする。|S|kd/dk2である。








Rdの点を整数に変換する。
f(x1, x2,…,xd)=x1+(2k+1) x2+…+(2k+1)d-1xk
f(x)+f(y)=2f(z), x,y,z Sならばx+y=2zであるが、これは
Sの作り方からあり得ない。
よってA={f(x)|x S}は長さ3の等差数列を持たない。
|A| kd/dk2で整数の大きさは(2k+1)d以下。
nに対してd=sqrt(log(n)), (2k+1)=2sqrt(log n)と選ぶと、
|A| n/2Q(sqrt(log n))。
1940年代に証明されて以降、この記録は現在まで破
られていない。

Download Report