加法的組合せ論(additive combinatorics)とは、整数やアーベル群の部分集合の加法的な構造を、集合の大きさの情報から調べる分野である。和の集合 $A+A$ が小さい集合の形を問う逆問題(Freiman の定理)と、十分に密な集合が等差数列を含むかを問う密度の問題(Szemerédi の定理)が 2 つの中心である。Fourier 解析、グラフの正則性、多項式法、エントロピーなどを方法とし、素数の中の等差数列(Green–Tao の定理)や和と積の関係の問題にも広がる。
加法的組合せ論(additive combinatorics)とは、整数やアーベル群の部分集合の加法的な構造を、集合の大きさの情報から調べる分野である。中心の問いは 2 つある。和の集合 $A+A$ が小さいのはどんな集合か、という問いと、十分に大きな集合は等差数列のような規則的な部分を必ず含むか、という問いである。
等差数列では和が重なるので $A+A$ が小さく、2 の冪の集合では和がほとんど重ならないので $A+A$ が大きい。$A+A$ から $A$ の形を読み取るのが 逆問題 で、その代表が Freimanの定理 である。密度だけから等差数列の存在を導くのが Szemerédiの定理 である。
この記事は分野の地図である。個別の定理の証明はそれぞれの記事にあり、ここでは定義を述べ、問いと結果を表にまとめ、短い証明を 2 つ示す。
以下、$G$ はアーベル群で、演算を加法で書く。
$G$ の空でない有限部分集合 $A,B$ について、$A+B:=\{a+b:a\in A,\ b\in B\}$ を 和の集合 という。$\lvert A+A\rvert/\lvert A\rvert$ を $A$ の 倍加定数 という。
倍加定数は $1$ 以上で、$1$ になるのは $A$ が部分群の剰余類のときに限る(Plünnecke–Ruzsaの不等式)。一般に $\lvert A+A\rvert\le\binom{\lvert A\rvert+1}2$ なので、倍加定数は $(\lvert A\rvert+1)/2$ 以下である。
$G$ の空でない有限部分集合 $A$ について、$a+b=c+d$ をみたす $(a,b,c,d)\in A^4$ の個数を $E(A)$ と書き、$A$ の 加法エネルギー という(Zha23 Definition 7.13.1, p. 264)。
$r(x)$ を $a+b=x$ をみたす $(a,b)\in A^2$ の個数とすると $E(A)=\sum_xr(x)^2$ である。
$k\ge3$ と正の整数 $N$ について、$\{1,\dots,N\}$ の部分集合で $k$ 項の等差数列(公差は $0$ でない)を含まないものの最大の大きさを $r_k(N)$ と書く。
| 問い | 代表的な結果 | 入る記事 |
|---|---|---|
| 和の集合はどこまで小さいか | 整数では $\lvert A+B\rvert\ge\lvert A\rvert+\lvert B\rvert-1$、$\mathbb F_p$ では $\min\{p,\lvert A\rvert+\lvert B\rvert-1\}$ 以上。一般のアーベル群では安定化群による補正が入る | Cauchy–Davenportの定理, Kneserの定理(加法的組合せ論) |
| 下界の等号はいつ成り立つか | $\mathbb F_p$ で $\lvert A\rvert,\lvert B\rvert\ge2$、$\lvert A+B\rvert\le p-2$ なら、等号は公差の等しい等差数列に限る | Vosperの定理 |
| 倍加定数が小さいと反復和はどうなるか | $\lvert A+B\rvert\le K\lvert A\rvert$ なら $\lvert mB-nB\rvert\le K^{m+n}\lvert A\rvert$ | Plünnecke–Ruzsaの不等式 |
| 倍加定数が小さい集合はどんな形か | 整数では、$K$ だけで決まる次元と相対的な大きさの一般化等差数列に含まれる | Freimanの定理 |
| 加法エネルギーが大きい集合はどんな形か | $E(A)\ge\lvert A\rvert^3/K$ なら、大きさ $K^{-O(1)}\lvert A\rvert$ 以上の部分集合 $A'$ で倍加定数が $K^{O(1)}$ 以下のものがある(Balog–Szemerédi–Gowersの定理、Zha23 Theorem 7.13.6, p. 265) | Freimanの定理 |
| 構造定理の評価は多項式にできるか | 有界なねじれのアーベル群では、$\lvert A+A\rvert\le K\lvert A\rvert$ なら、$A$ は大きさ $\lvert A\rvert$ 以下の部分群の $K$ の多項式個(指数はねじれの大きさによる)の剰余類で覆える(Marton の予想。$\mathbb F_2^n$ は GGMT25、一般の場合は GGMT26) | Freimanの定理 |
| 密な集合は等差数列を含むか | 各 $k\ge3$ で $r_k(N)/N\to0$。$k=3$ では $r_3(N)\le N\,2^{-\Omega((\log N)^\beta)}$($\beta>0$ は定数、KM23)と $r_3(N)\ge N\exp(-5\sqrt{\log N})$ | Szemerédiの定理 |
| 塗り分けると同じ色の構造が現れるか | 有限色の塗り分けには単色の長い等差数列と $x+y=z$ の解が現れる | van der Waerdenの定理, Schurの定理(和のない集合), Ramsey理論 |
| 疎な集合でも等差数列が現れるか | 素数は任意の長さの等差数列を含む | Green–Taoの定理 |
| 有限体の上ではどうか | $\mathbb F_3^n$ の 3 項等差数列を含まない集合の大きさは $O(2.76^n)$(Zha23 Theorem 6.5.1, p. 222) | 多項式法 |
| 和と積は同時に小さくなれるか | $\lvert A+A\rvert\,\lvert A\cdot A\rvert\ge\lvert A\rvert^{5/2}/91$(実数の有限集合) | Szemerédi–Trotterの定理 |
| 和が $0$ になる部分列はいつ見つかるか | $2n-1$ 個の整数の中に、和が $n$ で割り切れる $n$ 個がある | Erdős–Ginzburg–Zivの定理, Davenport定数 |
| 方法 | 考え方 | 使われる場所 |
|---|---|---|
| 和の集合の計算 | 三角不等式や被覆の補題で、大きさの評価を別の和の集合へ移す | Plünnecke–Ruzsaの不等式, Freimanの定理 |
| Fourier 解析 | 等差数列の個数を Fourier 係数で書き、大きな係数があれば密度を上げる | Szemerédiの定理, 離散Fourier変換 |
| グラフの正則性 | 加法の問題をグラフの問題へ移し、頂点の分割で調べる(Zha23 §2.4) | Szemerédiの正則性補題 |
| 多項式法 | 集合の上で消える次数の低い多項式から評価を得る | 多項式法, 組合せ論的零点定理 |
| 接続幾何 | 和と積の情報を点と直線の接続に移す | Szemerédi–Trotterの定理 |
| エントロピー | 集合を確率変数に置き換え、エントロピーで距離を測る(GGMT25) | エントロピー |
$A=\{1,2,\dots,n\}$ では $A+A=\{2,3,\dots,2n\}$ なので $\lvert A+A\rvert=2n-1$ で、倍加定数は $2$ 未満である。$G=\{1,2,4,\dots,2^{n-1}\}$ では、$2^a+2^b$($a\le b$)の 2 進表示から $\{a,b\}$ が決まるので $\lvert G+G\rvert=n(n+1)/2$ で、倍加定数は $(n+1)/2$ である。
積を見ると立場が入れ替わる。$G\cdot G=\{2^0,\dots,2^{2n-2}\}$ は $2n-1$ 個である。$n=10$ では次のようになる。
| 集合 | 和の集合の大きさ | 積の集合の大きさ |
|---|---|---|
| $\{1,\dots,10\}$ | $19$ | $42$ |
| $\{1,2,\dots,2^9\}$ | $55$ | $19$ |
和と積の両方が小さい集合はないだろう、というのが下の和積予想である。
$G$ の空でない有限部分集合 $A$ について $\lvert A\rvert^4\le E(A)\,\lvert A+A\rvert$ である。とくに $\lvert A+A\rvert\le K\lvert A\rvert$ なら $E(A)\ge\lvert A\rvert^3/K$ である。
$r(x)$ は $x\in A+A$ でだけ $0$ でなく、$\sum_{x\in A+A}r(x)=\lvert A\rvert^2$ である。Cauchy–Schwarzの不等式 により
$$
\lvert A\rvert^4=\Bigl(\sum_{x\in A+A}r(x)\Bigr)^2\le\lvert A+A\rvert\sum_{x\in A+A}r(x)^2=\lvert A+A\rvert\,E(A)
$$
である。後半は $\lvert A+A\rvert\le K\lvert A\rvert$ を代入すればよい。$\square$
$N\ge1$ について、$P=\{1,\dots,N\}$、$Q=\{2^{N+1},2^{N+2},\dots,2^{2N}\}$、$A=P\cup Q$ とする。$\lvert A\rvert=2N$ である。
$P$ の和 $x$ の表し方の数は $1,2,\dots,N,\dots,2,1$ なので $E(P)=(2N^3+N)/3$ であり、$E(A)\ge E(P)\ge\lvert A\rvert^3/12$ となる。一方で $Q$ の 2 元の和は 2 進表示からすべて異なるので $\lvert A+A\rvert\ge N(N+1)/2$ で、倍加定数は $(N+1)/4$ 以上になる。
したがって $E(A)\ge\lvert A\rvert^3/K$($K=12$ で固定)という性質は、$\lvert A+A\rvert\le K'\lvert A\rvert$($K'$ は $N$ によらない定数)を導かない。prop-adc-energy の逆は成り立たない。ただしこの $A$ は倍加定数の小さい部分集合 $P$ を含む。これが Balog–Szemerédi–Gowersの定理の内容である(Zha23 Example 7.13.5, p. 265 に同じ型の例がある)。
$\mathbb F_3^n$ の相異なる 3 点 $x,y,z$ が 3 項等差数列をなすことは、$x+y+z=0$ と同値である(公差 $d\ne0$ で $x+(x+d)+(x+2d)=3x+3d=0$、逆に $x+y+z=0$ なら $z-y=y-x$)。これは 3 点が 1 本の直線に乗ることでもある。3 項等差数列を含まない集合を cap 集合 という。
$\mathbb F_3^2$ の cap 集合の大きさの最大値は $4$ である。
$\{0,1\}^2$ は cap 集合である。実際、$x,y,z\in\{0,1\}^2$ が $x+y+z=0$ をみたすと、各座標の 3 つの $0,1$ の和は $3$ で割り切れるので、3 つとも等しい。よって $x=y=z$ である。
$\mathbb F_3^2$ は 9 点からなり、相異なる 2 点を通る直線はちょうど 1 本で、各直線は 3 点からなり、各点を通る直線は 4 本ある。また直線は平行な 3 本ずつの組に分かれ、1 組の 3 本は全点を重ならずに覆う。
大きさ $5$ の cap 集合 $A$ があるとして矛盾を導く(cap 集合の部分集合は cap 集合なので、大きさ $5$ 以上の場合はこれに帰着する)。cap 集合の性質から、各直線は $A$ の点を高々 2 個含む。$p\in A$ を通る 4 本の直線は $A$ の残りの 4 点をそれぞれちょうど 1 本で通り、各直線が含む残りの点は高々 1 個なので、4 本のどれも $A$ の点をちょうど 2 個含む。$p$ は任意なので、$A$ の点を通る直線はどれも $A$ の点をちょうど 2 個含む。したがって、どの直線の上の $A$ の点の個数も $0$ か $2$ である。平行な 3 本の組をとると、$A$ の点の総数は偶数になり、$\lvert A\rvert=5$ に反する。$\square$
同じ計算で $\{0,1\}^n$ は $\mathbb F_3^n$ の大きさ $2^n$ の cap 集合である。$n=4$ の最大値は $20$ で、これはカードゲーム SET の問題として知られている(Zha23 p. 209)。大きな $n$ では、$2.21^n$ 以上の大きさの cap 集合があり(Zha23 Remark 6.2.10, p. 212)、上からは $O(2.76^n)$ で抑えられる。
| 段階 | 読む記事 | ここで得るもの |
|---|---|---|
| 1 | Cauchy–Davenportの定理, Vosperの定理 | 和の集合の下界と、最小に近い集合の形 |
| 2 | Plünnecke–Ruzsaの不等式, Kneserの定理(加法的組合せ論) | 倍加定数の計算と一般のアーベル群 |
| 3 | Freimanの定理 | 逆問題の中心の定理 |
| 4 | van der Waerdenの定理, Szemerédiの定理 | 3 項の場合の Fourier 解析による証明と密度の定理 |
| 5 | Szemerédiの正則性補題, Green–Taoの定理 | グラフの方法と疎な集合への移し替え |
| 6 | 多項式法, Szemerédi–Trotterの定理 | 有限体の方法と和積の問題への入口 |
全体を通した教科書として Zha23 がある。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する