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$ の多項式になる。
前提知識: アーベル群, 二部グラフ, 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$ を空でない有限集合とする。
$\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$ である。
$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$ である。
$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$ である。
$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 の定数を明示した形)。
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$
二部グラフ $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'$ も許す)。
$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$ 未満であるものがある。
条件 $\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$
$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)$ 本以上あるものがある。
$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$ の形の評価を述べている。上の定数は、各段の密度を追い直して得たものである。
$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 の定数を明示した形)。
$\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 行目は制限和が小さくても辺が少なければ足りないことを示す。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する