3.2.3～3.3 D3 川原　純

3.2.3 (Sum-Product Theorem の) 数論への応用 　　　　を有限体（次数は素数p）、G を　　の部分乗法群とする。 定義 3.2.8 ex) 　　　 = {0,1,...,6}, = {1,...,6}, 掛け算を mod p で定義 a におけるフーリエ係数

Theorem 3.2.9 証明

Sum-Product Theorem のない時… は自明。 を示したい。 Sum-Product Theorem のない時… [T. Wolff 99] [D. Heath-Brown 96] [S. Konyagin and I. Shparlinski 99] Sum-Product Theorem のある時… [K. N. Bourgain, J. and T. Tao 04] [G. A. Bourgain, J. and S. Konyagin 06]

3.2.4 (Sum-Product Theorem の) グラフ理論への応用 H を有限群、T を H の生成元の集合とする。 生成元 = それの積によってその群のすべての元を表現できるような元 定義 3.2.12 Cay(H;T) を頂点が V=H、辺が であるグラフ（Cayley グラフ）と定義する。 Diam(H;T)： グラフの直径 = 最大で T の要素を何回かければ V の任意の頂点を表せるか u・v-1 v・w-1 v u w u から w への walk が存在　⇒　w にTの要素を繰り返し掛けて u にできる (u・v-1) (v・w-1)w = u

Cay(H; T) がエキスパンダーグラフなら、Cay(H; T) 上の ランダムウォークのマルコフ過程によって定義される行列の 直径は O(log|H|) となる。 エキスパンダーグラフ S G S から外に出る辺の集合 連結率 連結率が定数 α > 0 以上のものを エキスパンダーグラフと呼ぶ。 H=SL(2,p) : 2×2 の　 上の行列で、逆行列をもつものの集合。 群をなす。 このとき、Cay(H;T) はエキスパンダーである [Selberg 65] etc. Sum-Product Theorem を使うと… すべてのTについて、Cay(H;T) の直径は < polylog(|H|) [Helfgott 年度不明]

Sum-Product Theorem を使うと… ランダムなT（|T|=2）について、Cay(H;T) は高い確率で エキスパンダーになる。 <T> が H=SL(2, Z) のサイクルでないなら、 Cay(H;T) はエキスパンダー。 [J. Borgain and A. Gamburd 06]

3.2.5 Extractor and Disperser 近年の流行分野？ 難しすぎるので次回

3.3 Sum-Product Theorem の 証明の概要 Theorem 3.3.1 (Sum-Product Theorem) F =Fp とする。すべての δ < 0.9 に対して、また|A| = |F|δ を満たすすべての A ⊂ F に対して、|A + A| ≧ |A|1+ε と |A × A| ≧ |A|1+ε の少なくとも一方を満たす ε > 0 が存在する。

定理の証明に必要な2つのLemma Lemma 3.3.2 すべての A に対して、|R0(A)|>|A|1+δ を満たす rational expression R0 が存在する。 Lemma 3.3.3 もし |A+A|<|A|1+ε かつ |A×A|<|A|1+ε なら、すべてのRについて「|B|>|A|1-cε かつ |R(B)|<B1+cε となる B ⊆ A が存在する」ような c = c(R) が存在する。 rational expression R(A) 例えば R(A) = (A+A-A) / (A×A) = { x | x = (a1 + a2 – a3) / (a4 × a5), ai ∈ A }

Lemma 3.3.2 の証明 R0(A) := (A’ – A’) / (A’ – A’) = A’’ , すべての A に対して、|R0(A)|>|A|1+δ を満たす rational expression R0 が存在する。 R0(A) := (A’ – A’) / (A’ – A’) = A’’ , A’ := (A – A) / (A – A) を定義する。 δ’, δ’’ を |A’| = |F|δ’, |A’’|=|F|δ’’ と定義する。 δ ∈ (1 / (k + 1), 1 / k) なら δ’ > 1 / k を示せばよい。 なぜなら… δ‘’ > 1 / (k – 1) が成り立つので δ δ' δ‘’ 1 1 1 1 1 k + 1 k s + 1 s k – 1

Lemma 3.3.2 の証明 R0(A) := (A’ – A’) / (A’ – A’) = A’’ , すべての A に対して、|R0(A)|>|A|1+δ を満たす rational expression R0 が存在する。 R0(A) := (A’ – A’) / (A’ – A’) = A’’ , A’ := (A – A) / (A – A) を定義する。 δ’, δ’’ を |A’| = |F|δ’, |A’’|=|F|δ’’ と定義する。 δ ∈ (1 / (k + 1), 1 / k) なら δ’ > 1 / k を示せばよい。 なぜなら… δ‘’ > 1 / (k – 1) が成り立つので

δ ∈ (1 / (k + 1), 1 / k) なら δ’ > 1 / k A’ := (A – A) / (A – A) δ ∈ (1 / (k + 1), 1 / k) なら δ’ > 1 / k の証明 δ’ < 1 / k を仮定する。 s0, s1, ... , sk ∈ F を次のように構成する。 s0 = 1 sj を sj ∈ s0A’ + s1A’ + … + sj-1A’ となるようにとる。 もしとれないなら、s0A’ + s1A’ + … + sj-1A’ = F ⇒ |A’|j-1 > |F| ⇒ |A’| > |F|1/(j-1) |A’| = |F|δ’ なので δ’>1/(j-1) ≧1/(k-1) となり矛盾

δ ∈ (1 / (k + 1), 1 / k) なら δ’ > 1 / k ∈A’ δ’ < 1 / k を仮定する。 A’ := (A – A) / (A – A) δ ∈ (1 / (k + 1), 1 / k) なら δ’ > 1 / k の証明 ∈A’ δ’ < 1 / k を仮定する。 s0, s1, ... , sk ∈ F を次のように構成する。 sj = s0 + s1 + … +sj-1 x0 – y0 yj – xj x1 – y1 xj-1 – yj-1 s0 = 1 sj を sj ∈ s0A’ + s1A’ + … + sj-1A’ となるようにとる。 g(x0,...,xk) := ∑sixi と定義 (g は Ak+1 から F への写像) |A|k+1 > |F| なので、g は単写にはなり得ない x ≠y で g(x) = g(y) となるものが存在。 異なる g(x) = s0x0 + s1x1 + … + sjxj + …+ skxk ー) g(y) = s0y0 + s1y1 + … + sjyj + …+ skyk 0 = s0(x0-y0) + s1(x1-y1) + … + sj(xj-yj)

いくつかのTheorem Theorem 3.3.4 Theorem 3.3.5 Theorem 3.3.6 |A+A|<|A|1+ε　⇒　|A – A| < |A|1+2ε Theorem 3.3.5 |A+A|<|A|1+ε　⇒　|A + kA| < |A|1+kε Theorem 3.3.6 ||A+A||-1<|A|1+ε　⇒　∃A’ ⊆ A, |A’|>|A|1-5ε but 　　　　　　　　　　　　|A’+A’| < |A’|1+5ε