Additive Combinatrics 7
照山
[Szemerediの定理] 任意のkとd>0に対して、
あるN0が存在して、任意のn>N0に対して、任
意のA ⊆[n], |A|≧dnは長さkの等差数列を持
つ。
k>3に対するGowersの証明
以下のどちらかの性質を満たすことを示す。
C1:密度dのランダムな集合がもつ長さkの等
差数列の定数倍くらいAが等差数列を持つ。
C2:長さ n (1) 2d の等差数列Pが存在し、
[n]での密度よりPでのAの密度が高い。
| A P |
| A|
O (1)
d ' d d
d '
,d
|P|
n
O (1)
言葉の定義
k-pseudorandom
kに対してC1を満たしている。→dk|Fpn|2－|A|程度
(ランダム集合と似た性質を持つ)
linearly uniform
ˆ ( x) | cd 2を満たしている。
すべてのx 0に対して| A
Aˆ (t ) Ex [ A( x) t ( x)] Ex [ A( x) ax ]
k-uniform
U k 1 (1A d ) ck d k を満たす。
(後で定義)
今回もFpn上で議論を進めていく。
７章の流れ
7.2 linearly uniformであり、k-pseudorandomでな
い例を挙げる。
7.3 Gowersの一様ノルムを定義する。
7.4 k-uniformの時、k-pseudorandomであることを
示す。
7.5 k-uniformでない時、C2を満たすPが存在する
ことを示す。
補題7.2.1
二次曲面
A x Fpn | xi xn / 2i 0 Fp
in / 2
n
はlinearly uniformであり、Fp 上すべての長さkの
3
(
d
) 位を含む。 d 1 / p はAの密度。
等差数列のうち
特にk≧4に対して、Aはk-pseudorandomではない。
ベクトル
x F を(u, v)[u, v F
n
p
n/ 2
p
]と書くことにする。
A {( u, v) | u v} (u v u, v 0)
補題7.2.1の証明
まず、Aがlinearly uniformで、d 1 / p と仮定す
る。
Rothの証明において長さ3の等差数列が
(d 3 | Fpn |2 ) あることが示されている。Aが二次
n
曲面であるから、Fp 上の線は高々2点を通る
か、Aに含まれる。
長さ3の等差数列は長さkの等差数列に拡張
n
される。Fp 上すべての長さkの等差数列のう
ち (d 3 ) 位を含む。
not k-pseudorandom
補題7.2.1の証明
Aの密度dの計算
Aˆ (0) Pr u, v 0
u ,v
Pr u 0 Pr u 0 Pr u, v 0 u 0
u
p
u
n / 2
(1 p
u ,v
n / 2
) 1/ p 2
1
p
0, x
ˆ
A(0) Ex [1A ( x)
] Pr( x A)
1 x A
1A ( x )
0 x A
( n )
補題7.2.1の証明
1 x A
1A ( x )
0 x A
点c (c1 , c2 ) 0に対するフーリエ係数
ˆ (c) E [1 ( x) c , x ]
A
x A
Eu [ c1 ,u Pr (u v) Ev [ c2 ,v | u v]]
v
は1のp乗根。
Pr(u v | u 0)
もしc2 0ならば、上の式は
Eu
c1 ,u
Pr(v u ) Eu
1
p
c1 ,u
(1 1p ) Pr(u 0)
(1 1p ) p n / 2 p n / 2
となる。
Eu c1 ,u 0を用いている
(p乗根すべての和)。
1
p
補題7.2.1の証明
c2 0とする。
u , c2が平行でないとき、
uに直交する部分空間からvを一様に選ぶと、
ランダム変数 c2 , v はFpn上の一様に分布する。
u || c2 : Ev [ c2 ,v | u v]
1
ˆ
| A(c) | Pru (u || c2 ) n 1
p2
p 1
1
p
i
0
i 0
(c2 v)
linearly uniformである
7.3 Gowers uniformity norm
[Rothの証明]
not-3-pseudorandomなFpn上の部分集合のみを、
関数a(x)と関連する集合とした。 Fp上次数1の多項
a( x) a x
式a(x)による。
関係性は、以下の値で計る。
E x
n [1
A
F
R p
a( x)
]
前回のように書くと、
a x
E x [ A( x) t ( x)] E x [ A( x)
]
前のセクション：linearly uniformな二次曲面
が4-pseudorandomでないことをみた。
ー＞4-pseudorandomかどうかの距離を測る
一様ノルムは、集合が二次多項式と関係する
かをはかるノルムより大きい。
ノルムの自然な考え方
：二次多項式と最大相関
ー＞不可能ではないが、等差数列の数との
関連付けが難しい。
Gowers unifomity norm
より間接的に、ある次元の多項式との関連性
を評価するノルム
集合内のある長さの等差数列の数と、比較的
簡単に関連付けられる。
direction
y∈Fpn のderivative：
関数f : Fpn C、ベクトル
y Fpnに対して、
D y f ( x) f ( x) f ( x y )
Gowers unifomity norm
f ( x) と書くとき、
D yは指数部分には差分演算子として働く。
g ( x)
つまり、gがxのd次多項式ならば、Dyは指数
部分の次数を少なくとも１下げる。
derivativeの例
二次曲面上で3回行った場合：g(x)=x1x2
y1 x2 y2 x1 y1 y2
D y (
)
x1 x2
y1 y2 y '1 y '2
D y ' D y (
)
x1 x2
y1 y2 y '1 y '2 2
D y '' D y ' D y (
) |
| 1
x1 x2
Gowers unifomity norm
未知の(d-1)次の多項式とfの最大相関を測る
代わりに、定数関数ω0=１と Dy y f の期待相
関を測ることができる。
1
d
n
y1,, ydはFp から一様ランダムに選
ばれる。
D y1yd D y1 D yd
Gowers uniformity norm
[定義7.3.1]
G:有限群、関数f : G→Cに対する、
次数dのGowers一様ノルムUd( f )を
以下のように定義する。
def
1 / 2d
U ( f ) ( Ex, y1 ,, yd R G Dy1 ,, yd f ( x))
d
( Ex, y1 ,, yd R G [ f ( x) f ( x y1 ) f ( x yd )
1 / 2d
f ( x y1 yd )])
Gowers uniformity norm
E x, y D y f ( x) E x, y f ( x) f ( x y )
E x [ f ( x ) E y f ( x y )]
E x [ f ( x ) E y f ( y )]
E x [ f ( x)]E x [ f ( x)]
2
| E x f ( x) |
Fact
k
2k
k 1
2k 1
U ( f ) E y [U ( D y f ) ]
U 1 ( f ) | E x f ( x) |
Gowers unifomity norm
(d-1)次多項式との最大相関は、
常にd次Gowersノルムを下界にもつ。
多項式との相関は、一様性に依ると予想さ
れている。
inverse theoremsは次数3についてしか分
かっていない。
次数4以上ではうまくいかない例もでてきてい
る。
inverse theorem
定理7.3.4[Inverse theorem for U3]
f : Fpn C をとりうる値の大きさの上界が1で
ある関数とする。を1のp乗根とする。
O (1)
3
n
U ( f ) > ηならば、次元が少なくとも
の
部分集合Wが存在し、y+W上で以下の式を
満たす二次多項式qy(x)が定義できる。
E y
n
R Fp
| ExR y W f ( x)
qy ( x)
| ( (1))
inverse theorem を仮定すると、k=4に対して、
C2を証明するのが簡単になる。
C2：unifomity でなければ、次元の小さいアフィ
ン部分空間上で密度が高い。→(Sec.7.5)
d=2：フーリエ変換での畳み込みのかたち?
2
4
[U ( f )] E x, y1 , y2 [ D y1 , y2 f ( x)]
E y2 [ E x, y1 [ D y1 ( D y2 f ( x))]]
E y2 [| E x [ D y2 f ( x)] | ]
2
E y2 [| E x [ f ( x) f ( x y2 )] | ]
2
E y2 [| f * f ( y2 ) | ]
2
2
4
ˆ
ˆ
ˆ
Et [| f (t ) | | f (t ) | ] Et [| f (t ) | ]
2
© Copyright 2024 ExpyDoc
