Balog–Szemerédi–Gowersの定理

同義語:Balog-Szemerédi-Gowersの定理Balog–Szemerédi–Gowers theoremBSGの定理

概要

Balog–Szemerédi–Gowersの定理(Balog–Szemerédi–Gowers theorem)とは、アーベル群の有限集合 $A$ の加法エネルギー($a+b=c+d$ をみたす組の個数)が $\lvert A\rvert^3/K$ 以上なら、大きさ $K^{-O(1)}\lvert A\rvert$ 以上の部分集合 $A'$ で $\lvert A'+A'\rvert\le K^{O(1)}\lvert A'\rvert$ をみたすものがある、という加法的組合せ論の定理である。倍加定数が小さければエネルギーは大きいが、逆は部分集合に移らないと成り立たない。Gowers の証明は、人気のある和だけを辺にした二部グラフで長さ 3 の道を数え、各和を $x-y+z$ の形の多くの表し方に写すもので、評価は $K$ の多項式になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: アーベル群, 二部グラフ, Cauchy–Schwarzの不等式, Plünnecke–Ruzsaの不等式

Balog–Szemerédi–Gowersの定理(Balog–Szemerédi–Gowers theorem)とは、アーベル群の有限集合 $A$ の加法エネルギー($a+b=c+d$ の解の個数)が大きければ、$A$ は倍加定数の小さい大きな部分集合を含む、という 加法的組合せ論 の定理である。
集合の「加法的な構造」の測り方は 2 つある。1 つは $A+A$ が小さいこと(倍加定数が小さいこと)、もう 1 つは $a+b=c+d$ の解が多いこと(加法エネルギーが大きいこと)である。前者から後者は Cauchy–Schwarz の不等式ですぐ従うが、逆は成り立たない。等差数列に構造のない集合をつけ加えると、エネルギーは大きいまま $A+A$ が大きくなるからである。この定理は、逆が「大きな部分集合に移れば」成り立ち、しかも失う量が定数の多項式で済むことを述べる。
Balog と Szemerédi は正則性補題を使ってこれを示したが、評価は塔の形の関数であった。Gowers は多項式の評価をもつ新しい証明を与え、これを Szemerédi の定理の新しい証明で使った(Zha23 p. 265)。この記事では、二部グラフの中の長さ 3 の道を数える Gowers の証明(Sudakov–Szemerédi–Vu による整理、Zha23 §7.13)を、定数を明示して与える。
以下、$\Gamma$ はアーベル群で、演算を加法で書く。

定義

加法エネルギーと制限和

$A,B\subset\Gamma$ を空でない有限集合とする。

  1. $x\in\Gamma$ について $r_{A,B}(x):=\#\{(a,b)\in A\times B\mid a+b=x\}$ とおく。
  2. $E(A,B):=\#\{(a,b,a',b')\in A\times B\times A\times B\mid a+b=a'+b'\}=\sum_xr_{A,B}(x)^2$ を 加法エネルギー という。$E(A):=E(A,A)$ と書く(Zha23 Definition 7.13.1, p. 264、p. 265)。
  3. $G\subset A\times B$ を二部グラフ($A$ と $B$ を頂点の 2 つの組とし、$G$ の元を辺とする)とするとき、$A+_GB:=\{a+b\mid(a,b)\in G\}$ を 制限和 という(Zha23 Definition 7.13.8, p. 266)。$e(G):=\lvert G\rvert$ を辺の本数とする。

$\sum_xr_{A,B}(x)=\lvert A\rvert\lvert B\rvert$ で、$r_{A,B}(x)\le\min\{\lvert A\rvert,\lvert B\rvert\}$ である。

倍加とエネルギー

倍加定数が小さければエネルギーは大きい

$\lvert A+A\rvert\le K\lvert A\rvert$ なら $E(A)\ge\lvert A\rvert^3/K$ である。

Cauchy–Schwarz

$r=r_{A,A}$ は $A+A$ の外で $0$ なので、Cauchy–Schwarzの不等式 により $\lvert A\rvert^4=(\sum_{x\in A+A}r(x))^2\le\lvert A+A\rvert\,E(A)\le K\lvert A\rvert\,E(A)$ である(Zha23 Proposition 7.13.4, p. 265)。$\square$

逆は成り立たない

$N\ge1$ について $P:=\{1,\dots,N\}$、$Q:=\{2^{N+1},\dots,2^{2N}\}$、$A:=P\cup Q$ とする(Zha23 Example 7.13.5, p. 265 と同じ型の例)。$\lvert A\rvert=2N$ である。
$P$ の和 $x$ の表し方の数は $x=2,\dots,2N$ で $1,2,\dots,N,\dots,2,1$ なので、$E(A)\ge E(P)=\sum_{i=1}^{N}i^2+\sum_{i=1}^{N-1}i^2=(2N^3+N)/3\ge\lvert A\rvert^3/12$ である。一方、$Q$ の 2 元の和は 2 進表示からすべて異なるので $\lvert A+A\rvert\ge N(N+1)/2$ で、倍加定数は $(N+1)/4$ 以上である。$N=10$ では $E(A)=1260$、$\lvert A\rvert^3/12\approx666.7$、$\lvert A+A\rvert=174$ である(計算による)。
よって「$E(A)\ge\lvert A\rvert^3/12$」は、$N$ によらない定数 $K'$ での「$\lvert A+A\rvert\le K'\lvert A\rvert$」を導かない。しかし $A$ は半分の大きさの部分集合 $P$ をもち、$\lvert P+P\rvert=2N-1$ である。

主定理

Balog–Szemerédi–Gowersの定理

$A,B\subset\Gamma$ を空でない有限集合、$n\ge\max\{\lvert A\rvert,\lvert B\rvert\}$、$K>0$ とし、$E(A,B)\ge n^3/K$ とする。このとき $A'\subset A$、$B'\subset B$ で
$$ \lvert A'\rvert\ge\frac{n}{96K^3},\qquad\lvert B'\rvert\ge\frac{n}{16K^2},\qquad\lvert A'+B'\rvert\le2^{22}K^9n $$
をみたすものがある。

定数と所在

Zha23 Theorem 7.13.7(p. 265)は、同じ主張を $\lvert A'\rvert,\lvert B'\rvert\ge K^{-O(1)}n$、$\lvert A'+B'\rvert\le K^{O(1)}n$ の形で述べている。ここでの指数と定数は下の証明(prf-bsg-main)から出るもので、最良ではない。$E(A,B)\le\lvert A\rvert^2\lvert B\rvert\le n^3$ なので $K\ge1$ である。

1 つの集合の場合

$A\subset\Gamma$ を空でない有限集合とし、$E(A)\ge\lvert A\rvert^3/K$ とする。このとき $A'\subset A$ で
$$ \lvert A'\rvert\ge\frac{\lvert A\rvert}{96K^3},\qquad\lvert A'+A'\rvert\le2^{55}K^{23}\lvert A'\rvert $$
をみたすものがある(Zha23 Theorem 7.13.6, p. 265 の定数を明示した形)。

和の三角不等式で $B'$ を消す

thm-bsg-main を $B=A$、$n=\lvert A\rvert$ に当てて $A',B'$ を得る。Plünnecke–Ruzsaの不等式 の記事の「和の三角不等式」$\lvert X\rvert\,\lvert Y+Z\rvert\le\lvert X+Y\rvert\,\lvert X+Z\rvert$ を $X=B'$、$Y=Z=A'$ に当てると
$$ \lvert A'+A'\rvert\le\frac{\lvert A'+B'\rvert^2}{\lvert B'\rvert}\le\frac{2^{44}K^{18}n^2}{n/(16K^2)}=2^{48}K^{20}n $$
である。$n\le96K^3\lvert A'\rvert$ と $96\cdot2^{48}=3\cdot2^{53}< 2^{55}$ を使えばよい。$\square$

証明

証明は 3 段からなる。エネルギーの条件を、多くの辺をもち制限和の小さい二部グラフに言い換え(lem-bsg-popular)、そのグラフで長さ 3 の道が多い部分を取り出し(lem-bsg-path3)、道の数を和の数え上げに戻す(thm-bsg-graph)。

エネルギーからグラフへ

人気のある和

thm-bsg-main の仮定の下で、$S:=\{x\mid r_{A,B}(x)\ge n/(2K)\}$ とし、$G:=\{(a,b)\in A\times B\mid a+b\in S\}$ とおく。このとき $e(G)\ge n^2/(2K)$ かつ $\lvert A+_GB\rvert\le2Kn$ である。

人気のない和はエネルギーの半分以下

$r=r_{A,B}$ とおく。$x\notin S$ では $r(x)< n/(2K)$ なので
$$ \sum_{x\notin S}r(x)^2\le\frac{n}{2K}\sum_xr(x)=\frac{n}{2K}\lvert A\rvert\lvert B\rvert\le\frac{n^3}{2K} $$
であり、$\sum_{x\in S}r(x)^2\ge n^3/K-n^3/(2K)=n^3/(2K)$ である。$r(x)\le n$ なので $e(G)=\sum_{x\in S}r(x)\ge\frac1n\sum_{x\in S}r(x)^2\ge n^2/(2K)$ である。また $\lvert S\rvert\cdot n/(2K)\le\sum_{x\in S}r(x)\le n^2$ から $\lvert S\rvert\le2Kn$ で、$A+_GB\subset S$ である(Zha23 pp. 266–267)。$\square$

長さ 2 と長さ 3 の道

二部グラフ $G\subset X\times Y$ で $x\in X$ の近傍を $N(x)\subset Y$、$v\in Y$ の近傍を $N(v)\subset X$ と書き、$x,x'\in X$ の共通近傍の数を $\operatorname{codeg}(x,x'):=\lvert N(x)\cap N(x')\rvert$ とする($x=x'$ も許す)。

長さ 2 の道の補題

$X,Y$ を空でない有限集合、$G\subset X\times Y$ を $e(G)\ge\delta\lvert X\rvert\lvert Y\rvert$($\delta>0$)をみたす二部グラフ、$\varepsilon>0$ とする。このとき $U\subset X$ で、$\lvert U\rvert\ge\delta\lvert X\rvert/\sqrt2$ であり、$\operatorname{codeg}(x,x')< \varepsilon\delta^2\lvert Y\rvert/2$ となる $(x,x')\in U^2$ の個数が $\varepsilon\lvert U\rvert^2$ 未満であるものがある。

1 点の近傍をとる

条件 $\operatorname{codeg}(x,x')< \varepsilon\delta^2\lvert Y\rvert/2$ をみたす組を 疎遠 と呼ぶ。$v\in Y$ について $U_v:=N(v)$、$Z_v$ を $U_v^2$ の中の疎遠な組の個数とし、$v$ を $Y$ 上で平均する(平均を $\mathbb{E}_v$ と書く)。$\mathbb{E}_v\lvert U_v\rvert=e(G)/\lvert Y\rvert\ge\delta\lvert X\rvert$ なので、Cauchy–Schwarz により $\mathbb{E}_v\lvert U_v\rvert^2\ge\delta^2\lvert X\rvert^2$ である。組 $(x,x')$ が $U_v^2$ に入るのは $v\in N(x)\cap N(x')$ のときなので
$$ \mathbb{E}_vZ_v=\frac1{\lvert Y\rvert}\sum_{(x,x')\ \text{疎遠}}\operatorname{codeg}(x,x')\le\lvert X\rvert^2\cdot\frac{\varepsilon\delta^2}2 $$
である。よって $\mathbb{E}_v(\lvert U_v\rvert^2-Z_v/\varepsilon)\ge\delta^2\lvert X\rvert^2/2$ で、$\lvert U_v\rvert^2-Z_v/\varepsilon\ge\delta^2\lvert X\rvert^2/2> 0$ をみたす $v$ がある。$U:=U_v$ とおくと $\lvert U\rvert^2\ge\delta^2\lvert X\rvert^2/2$、$Z_v\le\varepsilon(\lvert U\rvert^2-\delta^2\lvert X\rvert^2/2)< \varepsilon\lvert U\rvert^2$ である(Zha23 Lemma 7.13.10, pp. 267–268 と同じ筋)。$\square$

長さ 3 の道の補題

$A,B$ を空でない有限集合、$G\subset A\times B$ を $e(G)\ge\delta\lvert A\rvert\lvert B\rvert$($0< \delta\le1$)をみたす二部グラフとする。このとき $A'\subset A$、$B'\subset B$ で $\lvert A'\rvert\ge\delta^2\lvert A\rvert/12$、$\lvert B'\rvert\ge\delta\lvert B\rvert/4$ であり、どの $(a,b)\in A'\times B'$ についても、$a$ と $b$ を結ぶ長さ 3 の道 $a\,b_1\,a_1\,b$($(a,b_1),(a_1,b_1),(a_1,b)\in G$)が $\delta^6\lvert A\rvert\lvert B\rvert/(4096\sqrt2)$ 本以上あるものがある。

次数の小さい頂点を 3 回削る

$A_1$. $A_1:=\{a\in A\mid\lvert N(a)\rvert\ge\delta\lvert B\rvert/2\}$ とおく。$A\setminus A_1$ から出る辺は $\delta\lvert A\rvert\lvert B\rvert/2$ 本以下なので、$A_1$ から出る辺は $\delta\lvert A\rvert\lvert B\rvert/2$ 本以上で、$\lvert A_1\rvert\lvert B\rvert$ 本以下である。よって $\lvert A_1\rvert\ge\delta\lvert A\rvert/2$ である。$A_1\times B$ への制限は $\frac\delta2\lvert A_1\rvert\lvert B\rvert$ 本以上の辺をもつ。
$A_2$. $A_1\times B$ への制限に lem-bsg-path2 を $\delta/2$ と $\varepsilon:=\delta/16$ で当てて $A_2\subset A_1$ を得る。$\lvert A_2\rvert\ge\frac{\delta}{2\sqrt2}\lvert A_1\rvert\ge\frac{\delta^2}{4\sqrt2}\lvert A\rvert$ であり、$\tau:=\varepsilon(\delta/2)^2\lvert B\rvert/2=\delta^3\lvert B\rvert/128$ とおくと、$\operatorname{codeg}< \tau$ の組 $(a,a_1)\in A_2^2$ は $\frac\delta{16}\lvert A_2\rvert^2$ 個未満である。
$B'$. $B':=\{b\in B\mid\lvert N(b)\cap A_2\rvert\ge\delta\lvert A_2\rvert/4\}$ とおく。$A_2\subset A_1$ から出る辺は $\frac\delta2\lvert A_2\rvert\lvert B\rvert$ 本以上で、そのうち $B\setminus B'$ に入るのは $\frac\delta4\lvert A_2\rvert\lvert B\rvert$ 本以下なので、$\frac\delta4\lvert A_2\rvert\lvert B\rvert\le\lvert A_2\rvert\lvert B'\rvert$、すなわち $\lvert B'\rvert\ge\delta\lvert B\rvert/4$ である。
$A'$. $A':=\{a\in A_2\mid\operatorname{codeg}(a,a_1)< \tau\text{ となる }a_1\in A_2\text{ が }\delta\lvert A_2\rvert/8\text{ 個以下}\}$ とおく。$A_2\setminus A'$ の各元は $\operatorname{codeg}< \tau$ の相手を $\delta\lvert A_2\rvert/8$ 個より多くもつので、$\lvert A_2\setminus A'\rvert\cdot\frac\delta8\lvert A_2\rvert< \frac\delta{16}\lvert A_2\rvert^2$($A_2\setminus A'$ が空でなければ)となり、$\lvert A'\rvert>\lvert A_2\rvert/2\ge\delta^2\lvert A\rvert/(8\sqrt2)\ge\delta^2\lvert A\rvert/12$ である。
道の数. $(a,b)\in A'\times B'$ とする。$b$ は $A_2$ に $\delta\lvert A_2\rvert/4$ 個以上の近傍をもち、そのうち $\operatorname{codeg}(a,a_1)< \tau$ となる $a_1$ は $\delta\lvert A_2\rvert/8$ 個以下なので、$a_1\in N(b)\cap A_2$ で $\operatorname{codeg}(a,a_1)\ge\tau$ のものが $\delta\lvert A_2\rvert/8$ 個以上ある。各 $a_1$ について $b_1\in N(a)\cap N(a_1)$ が $\tau$ 個以上あり、$a\,b_1\,a_1\,b$ は道である。よって道は
$$ \frac{\delta}{8}\lvert A_2\rvert\cdot\tau\ge\frac\delta8\cdot\frac{\delta^2\lvert A\rvert}{4\sqrt2}\cdot\frac{\delta^3\lvert B\rvert}{128}=\frac{\delta^6\lvert A\rvert\lvert B\rvert}{4096\sqrt2} $$
本以上ある。$\square$

Zha23 Lemma 7.13.11(pp. 268–269)は同じ 3 段の削り方で $c\delta^C$ の形の評価を述べている。上の定数は、各段の密度を追い直して得たものである。

グラフ版から主定理へ

グラフ版の Balog–Szemerédi–Gowers の定理

$A,B\subset\Gamma$ を空でない有限集合、$n\ge\max\{\lvert A\rvert,\lvert B\rvert\}$、$K\ge1$ とし、二部グラフ $G\subset A\times B$ が $e(G)\ge n^2/K$ と $\lvert A+_GB\rvert\le Kn$ をみたすとする。このとき $A'\subset A$、$B'\subset B$ で $\lvert A'\rvert\ge n/(12K^3)$、$\lvert B'\rvert\ge n/(4K^2)$、$\lvert A'+B'\rvert\le4096\sqrt2\,K^9n$ をみたすものがある(Zha23 Theorem 7.13.9, p. 266 の定数を明示した形)。

道を和の 3 つ組に写す

$\delta:=e(G)/(\lvert A\rvert\lvert B\rvert)\ge1/K$ とし、$e(G)\le\lvert A\rvert\,n$ から $\lvert A\rvert\ge n/K$ である。lem-bsg-path3 で $A',B'$ を得ると、$\lvert A'\rvert\ge\delta^2\lvert A\rvert/12\ge n/(12K^3)$、$\lvert B'\rvert\ge\delta\lvert B\rvert/4\ge n/(4K^2)$ であり、各 $(a,b)\in A'\times B'$ を結ぶ道は
$$ \frac{\delta^6\lvert A\rvert\lvert B\rvert}{4096\sqrt2}=\frac{\delta^5e(G)}{4096\sqrt2}\ge\frac{n^2}{4096\sqrt2\,K^6}=:\Pi $$
本以上ある。道 $a\,b_1\,a_1\,b$ に $x:=a+b_1$、$y:=a_1+b_1$、$z:=a_1+b$ を対応させると、3 つとも $G$ の辺の和なので $A+_GB$ に入り、
$$ x-y+z=a+b $$
である。$a,b$ を固定すると、$b_1=x-a$、$a_1=z-b$ なので、異なる道は異なる $(x,y,z)$ を与える。$s\in A'+B'$ ごとに $s=a+b$ となる $(a,b)\in A'\times B'$ を 1 つ選ぶと、$x-y+z=s$ をみたす組が $\Pi$ 個以上あり、$s$ が違えば組も違う。よって $\lvert A'+B'\rvert\cdot\Pi\le\lvert A+_GB\rvert^3\le K^3n^3$ となり、$\lvert A'+B'\rvert\le4096\sqrt2\,K^9n$ である(Zha23 pp. 269–270)。$\square$

グラフ版に当てる

thm-bsg-main を示す。lem-bsg-popular のグラフ $G$ は、$K$ を $2K$ に替えた thm-bsg-graph の仮定をみたす。よって $\lvert A'\rvert\ge n/(12\cdot8K^3)=n/(96K^3)$、$\lvert B'\rvert\ge n/(16K^2)$、$\lvert A'+B'\rvert\le4096\sqrt2\cdot2^9K^9n\le2^{22}K^9n$ である。$\square$

反例の表

仮定を外すと成り立たない

$A:=\{2^i\mid0\le i< n\}$、$B:=\{2^{n+j}\mid0\le j< n\}\subset\mathbb{Z}$ とする。和 $a+b$($a\in A$、$b\in B$)は 2 進表示からすべて異なるので、どの $A'\subset A$、$B'\subset B$ についても $\lvert A'+B'\rvert=\lvert A'\rvert\lvert B'\rvert$ である。

主張外す仮定・形例何が成り立たなくなるか
cor-bsg-symmetric部分集合に移らず $A$ 自身で結論を求めるex-bsg-converse-fails の $A=P\cup Q$$E(A)\ge\lvert A\rvert^3/12$ だが倍加定数は $(N+1)/4$ 以上
thm-bsg-graph$\lvert A+_GB\rvert\le Kn$上の $A,B$ と完全二部グラフ $G=A\times B$$e(G)=n^2$ だが $\lvert A+_GB\rvert=n^2$
thm-bsg-graph$e(G)\ge n^2/K$上の $A,B$ と $G=\{(2^i,2^{n+i})\}$$\lvert A+_GB\rvert=n$ だが $e(G)=n$

2・3 行目では、大きさ $n/c$ 以上の $A',B'$ について $\lvert A'+B'\rvert\ge n^2/c^2$ なので、$n$ を大きくすると「$\lvert A'+B'\rvert\le Cn$」($C$ は $n$ によらない)が成り立たなくなる。2 行目は辺が多くても制限和が大きければ足りないこと、3 行目は制限和が小さくても辺が少なければ足りないことを示す。

応用

  • Szemerédiの定理 の Gowers の証明:多項式の評価をもつこの形の定理は、Gowers による Szemerédi の定理の新しい証明で重要な役割を果たした(Zha23 p. 265)。
  • Freimanの定理 との組合せ:$\Gamma=\mathbb{Z}$ のとき、$A'$ の倍加定数が $K$ の多項式で抑えられるので、$A'$ に Freiman の定理を当てると、エネルギーの大きい集合の大きな部分が一般化等差数列の中にあることが分かる。
  • エネルギーの言い換え:和積現象 の乗法エネルギーのように、エネルギーは和の集合より扱いやすい量であり、この定理はエネルギーの評価を和の集合の評価に戻す橋になる。

関連項目

参考文献

[1]
Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, 1st ed.(頁・番号は 2024年6月18日更新の著者版による), Cambridge University Press, 2023, §7.13 Additive Energy and the Balog–Szemerédi–Gowers Theorem(著者版 pp. 264–270):Definition 7.13.1(p. 264)、Proposition 7.13.4・Example 7.13.5・Theorem 7.13.6・Theorem 7.13.7(p. 265)、Definition 7.13.8・Theorem 7.13.9(p. 266)、人気のある和への帰着(pp. 266–267)、Lemma 7.13.10(pp. 267–268)、Lemma 7.13.11(pp. 268–269)、Theorem 7.13.9 の証明(pp. 269–270)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する