Additive Combinatrics 7

Presentation on theme: "Additive Combinatrics 7"— Presentation transcript:

1 Additive Combinatrics 7
川原　純

2 以下のどちらかの性質を満たすことを示す。 C1:密度dのランダムな集合がもつ長さkの等差数 列の定数倍くらいAが等差数列を持つ。
[Szemerediの定理] 任意のkとd>0に対し て、あるN0が存在して、任意のn>N0に対 して、任意のA ⊆[n], |A|≧dnは長さkの等差 数列を持つ。 k>3に対するGowersの証明 以下のどちらかの性質を満たすことを示す。 C1:密度dのランダムな集合がもつ長さkの等差数 列の定数倍くらいAが等差数列を持つ。 C2:長さ　　　　　　　の等差数列Pが存在し、 [n]での密度よりPでのAの密度が高い。

3 ７章の流れ 7.2 linearly uniformであり、k- pseudorandomでない例を挙げる。
7.3　Gowersの一様ノルムを定義する。 7.4　k-uniformの時、k-pseudorandom であることを示す。 7.5　k-uniformでない時、C2を満たすPが 存在することを示す。 C2:長さ　　　　　　　 の等差数列Pが存在し、[n]での密度より PでのAの密度が高い。

4 7.4 k-Uniform → k-pseudorandom
　　　　 上の k 次formを定義 は集合 に含まれる長さkの等差数列の k-AP 1A (x) = 1 if x ∈A 割合 密度 δ のランダム集合A では（期待値） 個の k-AP を含むので、 よって、k-pseudorandom なら 以下、k=4 で証明するが、一般化は容易

5 Lemma 7.4.1 とする（正規化みたいな関数） 証明 独立とみなせる が成り立つ 任意の x, y, z, w について
　　　　　とする（正規化みたいな関数） が成り立つ 証明 任意の x, y, z, w について Roth の定理のように 期待値を計算すると0 で押さえられる

6 なら、Rothの定理の証明のように、 密度の高いアフィン部分空間が見つかるので OK の場合を考える

7 Lemma 7.4.2 （一般化フォンノイマンの定理）
の場合を考える Lemma （一般化フォンノイマンの定理） を対ごとにdistinctとする。 を を満たす関数とする このとき が成り立つ 特に とすることで が成り立つ 証明は後で

8 Lemma 7.4.3 証明 Lemma 7.4.1 より － ≦ ≦ ＋ << U3(f) + 4 δ4

9 Proposition 7.4.4 の任意の k-uniform な部分集合は k-pseudorandom 証明 Lemma 7.4.3
（となるckが存在） より ≦ (1+ck) δk なので k-pseudorandom

10 Lemma の証明 def ＝ k に関する帰納法で証明 k = 2 x + c1d と x + c2d は独立なので

11 Claim 証明は直後に これが成り立つとすると 証明終

12 Claim の証明 を証明する x = x+c3d Cauchy-Schwarz

13 Claim の証明 を証明する は一様分布 は1で押さえられるので 証明終

14 7.5 k-uniform でない→密度増大な部分空間をとれる
Proposition 7.5.1 もし ならば、A が密度 をもち、少なくとも次元が である ようなアフィン部分空間が存在する。 2つの Lemma で証明する

15 Lemma 7.5.2 もし ならば であるような次元 のアフィン部分空間 と2次形式の多項式 q が存在する。 ここで、Sは2次形式の表面
Proposition 7.5.1 Lemma 7.5.2 …ならば もし ならば 密度 次元 のアフィン部分空間が存在 であるような次元 のアフィン部分空間 と2次形式の多項式 q が存在する。 ここで、Sは2次形式の表面 Lemma 7.5.3 上のベクトル空間 W の任意の2次形式の表面 はそれぞれが少なくとも 次元をもついくつかの部分空間に 分割可能。

16 inverse theorem（復習） 定理7.3.4[Inverse theorem for U3]
をとりうる値の大きさの上界 が1である関数とする。wを1のp乗根とす る。 U3( f ) > ηならば、次元が少なくとも　　 の部分集合Wが存在し、y+W上で以下の式 を満たす二次多項式qy(x)が定義できる。 イータ

17 Lemma7.5.2 の証明 次元の inverse thorem を用いることで、 アフィン部分空間 W が存在して、以下を満たす。
に分解する 各 Wy について、平均 correlation が少なくとも ε となる二次形式 qy が存在する。 を二次形式の表面 とする

18 各 Wy について、平均 correlation
が少なくとも ε となる二次形式 qy が存在する。 を二次形式の表面 とする

19 Lemma 7.5.3 上のベクトル空間 W の任意の2次形式の表面 はそれぞれが少なくとも 次元をもついくつかの部分空間に 分割可能。 証明 q(x) = <x, Mx> + <a, x> + b M: 対象線型演算子 Q(x) = <x, Mx> U を Q(x)=0 なるすべての x によって張られた Wの部分線型空間とする。 剰余類 y + U 上に制限した q はアフィン線型関数となる 各 u について

20 を q を y + U 上に制限した アフィン線型関数とする。 S ∩ (y＋U) は、Sとアフィン超平面 の共通集合に等しい。 したがって、 S ∩ (y＋U) は空か、少なくとも dim(U)－1 次元の y + U のアフィン部分集合である。 あとは、dim(U) ≧ dim(W)/2 – 3/2 を証明すればよい。 任意の x, y ∈ U について、<y, Mx> = 0 なので、 したがって、M は U から U の直交補空間に写像する

21 を　　　　　　の直交補空間とする U は U’ の部分空間である。 Lemma が示されれば、dim(W) ≦ dim(M(U)) + dim(U’) ≦ dim(U) + dim(U’) ≦ 2 dim(U) + 3

22

23 言葉の定義 k-pseudorandom kに対してC1を満たしている。→dk|Fpn|2－|A|程 度 (ランダム集合と似た性質を持つ)
linearly uniform k-uniform 今回もFpn上で議論を進めていく。

24 ７章の流れ 7.2 linearly uniformであり、k- pseudorandomでない例を挙げる。
7.3　Gowersの一様ノルムを定義する。 7.4　k-uniformの時、k-pseudorandom であることを示す。 7.5　k-uniformでない時、C2を満たすPが 存在することを示す。

25 補題7.2.1 二次曲面 はlinearly uniformであり、Fpn上すべての長さkの 等差数列のうち 位を含む。 はAの 密度。
特にk≧4に対して、Aはk-pseudorandomではない。

26 補題7.2.1の証明 まず、Aがlinearly uniformで、 と仮定する。
Rothの証明において長さ3の等差数列が　　　　　　　　　 　あることが示されている。Aが 二次曲面であるから、Fpn上の線は高々2点 を通るか、Aに含まれる。 長さ3の等差数列は長さkの等差数列に拡 張される。Fpn上すべての長さkの等差数列 のうち　　　　位を含む。 not k-pseudorandom

27 補題7.2.1の証明

28 補題7.2.1の証明

29 補題7.2.1の証明 linearly uniformである

30 7.3 Gowers uniformity norm
[Rothの証明] not-3-pseudorandomなFpn上の部分集合のみ を、 関数wa(x)と関連する集合とした。 Fp上次数1の 多項式a(x)による。 関係性は、以下の値で計る。

31 前のセクション：linearly uniformな二次 曲面が4-pseudorandomでないことをみ た。
ノルムの自然な考え方 ：二次多項式と最大相関 ー＞不可能ではないが、等差数列の数と の関連付けが難しい。

32 Gowers unifomity norm direction y∈Fpn のderivative：
より間接的に、ある次元の多項式との関連 性を評価するノルム 集合内のある長さの等差数列の数と、比較 的簡単に関連付けられる。 direction y∈Fpn のderivative：

33 Gowers unifomity norm つまり、gがxのd次多項式ならば、Dyは指 数部分の次数を少なくとも１下げる。
derivativeの例 二次曲面上で3回行った場合：g(x)=x1x2

34 Gowers unifomity norm 未知の(d-1)次の多項式とfの最大相関を測 る代わりに、定数関数ω0=１と　　　　　 の期待相関を測ることができる。

35 Gowers uniformity norm
[定義7.3.1] G:有限群、関数f : G→Cに対する、 次数dのGowers一様ノルムUd( f )を 　以下のように定義する。 d=2はフーリエ変換でのたたみこみのようになる。

36 Gowers uniformity norm

37 Gowers unifomity norm (d-1)次多項式との最大相関は、 常にd次Gowersノルムを下界にもつ。
多項式との相関は、一様性に依ると予想 されている。 inverse theoremsは次数3についてしか 分かっていない。 次数4以上ではうまくいかない例もでてき ている。

38 inverse theorem 定理7.3.4[Inverse theorem for U3]
をとりうる値の大きさの上界 が1である関数とする。wを1のp乗根とす る。 U3( f ) > ηならば、次元が少なくとも　　 の部分集合Wが存在し、y+W上で以下の式 を満たす二次多項式qy(x)が定義できる。 イータ

39 inverse theorem を仮定すると、 k=4に対して、C2を証明するのが簡 単になる。
C2：unifomity でなければ、次元の小 さいアフィン部分空間上で密度が高い。 →(Sec.7.5)

40 d=2：フーリエ変換での畳み込みのかた ち?