Additive Combinatorics - 某理論計算機科学者の研究日誌

今回の RANDOM+APPROX 2007 の直後には二日間の集中講義が予定されており，それも聴講してきました．講義の内容は計算量理論への応用が近年注目されている Additive Combinatorics という分野の基本とその応用方法についてです．講師陣は Luca Trevisan, Boaz Barak, Avi Wigderson という超豪華メンバー．基本的な内容は下のような感じでした．

Erdos-Turan conjecture の紹介，Szemerdi's theorem の Szemerdi's Regularity lemma を使った証明, Fourier analysis を使った証明（Trevisan）
Sum-Product Lemma の応用（Wigderson）とその証明（Barak）
Gowers Uniformity の Hardness Amplification への応用（Wigderson）と擬似乱数生成器への応用（Trevisan）

特に Sum-Product Lemma は純粋数学を超えて非常に広い分野で応用されている強力な道具らしいです．（といってもWigdersonが話していたのは主に randomness extractor への応用でしたが）昨年フィールズ賞を受賞した Terence Tao も近い分野を割と最近研究しているようです．Sum-Product Lemma が主張していることは非常に単純です．
２つの集合 $A, B$ の足し算と掛算を，
$A+B=\{a+b| a \in A, b \in B\}, A\times B = \{ab| a \in A, b \in B\}$
と定義します．
このとき任意の集合 $A$ に対して（ $A$ が有限体 $F$ の部分集合の場合には $|A|<|F|^{0.9}$ ）ある定数 $\epsilon>0$ が存在し
$|A+A|>|A|^{1+\epsilon}$ あるいは $|A\times A|>|A|^{1+\epsilon}$ のいずれかが成立します．証明は組み合わせ論的テクニックのみで可能ですが，かなり非自明です．Barakの講義でも3時間かけて特別な場合だけしか証明していませんでした．