Bogolyubov-Ruzsaの補題 (加法的組合せ論)

加法的組合せ論(additive combinatorics)で知られるBogolyubov--Ruzsaの補題と呼ばれる結果を紹介します. この補題は様々なバリエーションが知られていますが, ここでは以下のタイプの結果を証明します. 

加法的組合せ論は極値グラフ理論(ラムゼー理論)と密接に関連しており, 密な部分集合が持つ構造的特徴を解析します. 例えばRothの定理は$\mathbb{N}$上の任意の密な部分集合$S\subseteq\mathbb{N}$は長さ3の非自明な等差数列 (つまり交差が非ゼロ) を含むことを主張します. ここでは$S$が「密な部分集合」, 「長さ3の等差数列を含む」が「構造的特徴」に対応します. なお, Rothの定理よりも強い主張として, 任意の密な自然数の部分集合は無限に長い等差数列を含むという事実が知られています (Szemerédiの定理).

$\mathbb{F}_q$を素体として$n\in\mathbb{N}$に対して線形空間$\mathbb{F}_q^n$を考えます. $D\subseteq\mathbb{F}_q^n$が密である時にそれはどのような性質を持つかを考えます. 幾つか記号を導入します.

• $D+D = \{a+a'\colon a,a'\in D\}$.
• $-D = \{-a\colon a\in D\}$.
• $k\in\mathbb{N}$に対して$kD=\{a_1+\dots+a_k\colon a_1,\dots,a_k\in D\}$.
• $D-D = D+(-D) = \{a-a'\colon a,a'\in D\}$.

例えば$D$が部分空間ならば$D+D,D-D$などは全て$D$と一致します. イメージとしては$D$と$D-D$などの"ギャップ"を考えることによって$D$の"部分空間っぽさ"を捉えることができます. Bogolyubov--Ruzsaの補題は, $D$が密ならば$2D-2D$は大きな線形部分空間を含むことを主張します.

定理1 (Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって

任意の$x\in V$に対してある$a,b,c,d\in D$が存在して$x=a+b-c-d$

を満たすものが存在する (即ち$V\subseteq 2D-2D$).

本記事ではより強いことを主張する以下の結果を証明します.

定理2 (確率的Bogolyubov--Ruzsaの補題).

集合$D\subseteq \mathbb{F}_q^n$が$|D|\geq \delta |\mathbb{F}_q^n|$を満たすならば, $\dim V\geq n-\delta^{-2}$を満たす線形部分空間$V$であって,

任意の$x\in V$に対して$\Pr_{a,b,c,d\sim \mathbb{F}_q^n}[a,b,c,d\in D|a+b-c-d=x]\geq \delta^5$

を満たすものが存在する.

証明.

フーリエ解析の記法を用いる (定義の記事参照). $D\subseteq \mathbb{F}_q^n$に対し, $\mathbb{1}_D$を指示関数 ($x\in D$なら$\mathbb{1}_D(x)=1$, そうでなければ$\mathbb{1}_D(x)=0$) とする. この関数のフーリエ変換$\widehat{\mathbb{1}}_D$を考え, パラメータ$\epsilon>0$に対して

$$R_\epsilon = \{v\in\mathbb{F}_q^n\colon |\widehat{\mathbb{1}}_D(v)|\geq\epsilon\}$$

とする. Parsevalの等式より

$$\delta = \|\mathbb{1}_D\|^2 = \sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^2 \geq \epsilon^2|R_\epsilon|$$

なので$|R_\epsilon|\leq\delta\epsilon^{-2}$である. $V$を$R$の張る部分空間の直交補空間, すなわち

$$V=\{v\in \mathbb{F}_q^n\colon \forall r\in R_{\epsilon},\langle v,r\rangle=0\}$$

とする. 明らかに$\dim V \geq n-|R_\epsilon|\geq n-\delta\epsilon^{-2}$である.

よって, $\epsilon=\delta^{1.5}$のときに上で定義された$V$が所望の性質を満たすことを言えば良い. 関数$f\colon\mathbb{F}_q^n\to\mathbb{C}$を

$$f=\mathbb{1}_D\ast \mathbb{1}_D \ast \mathbb{1}_{-D}\ast \mathbb{1}_{-D}$$

とする. 畳み込みの定義より

$$f(x) = \Pr_{a,b,c,d\sim\mathbb{F}_q^n}[a,b\in D,c,d\in -D|a+b+c+d=x]$$

であるので, 任意の$x\in V$に対して$|f(x)|\geq \delta^5$を示せばよい.

$f(x)$をフーリエ級数展開する. 畳み込みの性質から$\widehat{f}(v)=\widehat{\mathbb{1}}_D(v)^2\widehat{\mathbb{1}}_{-D}(v)^2$だが,

$$\widehat{\mathbb{1}}_{-D}(v) = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{-D}(x) \overline{\omega^{\langle v,x\rangle}}\right] = \mathbf{E}_{x\sim\mathbb{F}_q^n}\left[\mathbb{1}_{D}(x) \omega^{-\langle v,-x\rangle}\right] = \overline{\widehat{\mathbb{1}}_{D}(v)}$$

より, $\widehat{f}(v)=|\widehat{\mathbb{1}}_D|^4$となるので$f(x)=\sum_{v\in\mathbb{F}_q^n}|\widehat{\mathbb{1}}_D(v)|^4\chi_v(x)$である. この和を

1. $v=0$
2. $v\in R_\epsilon$
3. それ以外 ($v\not\in R_\epsilon\cup\{0\}$)

に分けて考える.

• $v=0$の時は$\chi_0\equiv 1$より$\widehat{\mathbb{1}}_D(0)\chi_0(x)=\langle \mathbb{1}_D,1\rangle = \delta$である.
• $v\in R_\epsilon$の時は, $V$の定義より$\langle x,v\rangle = 0$なので$\widehat{\mathbb{1}}_D(v)\chi_v(x)=\widehat{\mathbb{1}}_D(v)$である.

それ以外の場合は, $v\not\in R_\epsilon$より$|\widehat{\mathbb{1}}_D|\leq \epsilon$より

$$\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^4 \leq \epsilon^2\sum_{v\not\in R_\epsilon\cup \{0\}} |\widehat{\mathbb{1}}_D(v)|^2 \leq \epsilon^2\left(\delta -  |\widehat{\mathbb{1}}_D(0)|^2\right)=\epsilon^2(\delta-\delta^2).$$

以上の三つのケース組み合わせると, $\epsilon=\delta^{1.5}$のとき,

$$|f(x)|\geq \delta + \sum_{v\in R_\epsilon}|\widehat{\mathbb{1}}_D(v)|^4 - \epsilon^2(\delta-\delta^2) \geq \delta^5$$

となり主張を得る. (証明終).