加法的組合せ論

同義語:additive combinatorics

概要

加法的組合せ論(additive combinatorics)とは、整数やアーベル群の部分集合の加法的な構造を、集合の大きさの情報から調べる分野である。和の集合 $A+A$ が小さい集合の形を問う逆問題(Freiman の定理)と、十分に密な集合が等差数列を含むかを問う密度の問題(Szemerédi の定理)が 2 つの中心である。Fourier 解析、グラフの正則性、多項式法、エントロピーなどを方法とし、素数の中の等差数列(Green–Tao の定理)や和と積の関係の問題にも広がる。

$$\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}} $$

前提知識: アーベル群, 有限体, 数え上げ組合せ論

加法的組合せ論(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$ である。

2 乗和の評価

$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^2$ の中の等差数列

$\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 集合

$\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)$ で抑えられる。

読み進め方

段階読む記事ここで得るもの
1Cauchy–Davenportの定理, Vosperの定理和の集合の下界と、最小に近い集合の形
2Plünnecke–Ruzsaの不等式, Kneserの定理(加法的組合せ論)倍加定数の計算と一般のアーベル群
3Freimanの定理逆問題の中心の定理
4van der Waerdenの定理, Szemerédiの定理3 項の場合の Fourier 解析による証明と密度の定理
5Szemerédiの正則性補題, Green–Taoの定理グラフの方法と疎な集合への移し替え
6多項式法, Szemerédi–Trotterの定理有限体の方法と和積の問題への入口

全体を通した教科書として Zha23 がある。

未解決問題

  • 和積予想:実数の有限集合 $A$ について $\max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}\ge\lvert A\rvert^{2-o(1)}$ であろうという Erdős–Szemerédi の予想である(和積現象、Zha23 Conjecture 8.0.2, p. 273)。下界としては Solymosi の指数 $4/3-o(1)$(Zha23 Corollary 8.3.2, p. 279)があり、Konyagin と Shkredov はこれを小さな定数 $c>0$ について $4/3+c$ に改良した(Zha23 Remark 8.3.3, p. 281)。
  • 整数の上の多項式の構造定理:有界なねじれの群の場合の結果 GGMT26 は $\mathbb Z$ を含まない。$\mathbb Z$ の場合の予想の形は Zha23 Conjecture 7.12.7(p. 263)にあり、GGMT25 の序文は強い形が未解決であると述べている。
  • 等差数列の密度の正確な大きさ:$r_3(N)$ の KM23 の上界と Behrend の下界の間には隔たりがある。$k\ge4$ の上界はさらに弱い(Zha23 §0.2, p. 7)。
  • 有限体の上の 4 項等差数列:$\mathbb F_5^n$ の 4 項等差数列を含まない集合の大きさは、ある $c< 5$ で $O(c^n)$ か。Zha23 Open Problem 6.5.10(p. 226)に挙げられている。

関連項目

参考文献

[1]
Zander Kelley, Raghu Meka, Strong Bounds for 3-Progressions, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 933–973, 2023, arXiv:2302.05537v6 の番号と頁。Theorem 1.1、Theorem 1.2 と Behrend の下界の記述(p. 2)
[2]
W. T. Gowers, Ben Green, Freddie Manners, Terence Tao, On a conjecture of Marton, Annals of Mathematics, 2025, arXiv:2311.05762v2 の番号。§1:Conjecture 1.1、Theorem 1.2、Theorem 1.3 とそのあとの注意
[3]
W. T. Gowers, Ben Green, Freddie Manners, Terence Tao, Marton's conjecture in abelian groups with bounded torsion, Annales de la Faculté des sciences de Toulouse : Mathématiques, 2026, arXiv:2404.02244v2 の番号。Theorem 1.1
[4]
Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, 著者版(2024 年 6 月 18 日更新), Cambridge University Press, 2023, 著者版(2024 年 6 月 18 日更新)の頁。§0.2(p. 7)、§2.4、§6.2(p. 209)、Remark 6.2.10(p. 212)、Theorem 6.5.1(p. 222)、Open Problem 6.5.10(p. 226)、Conjecture 7.12.7(p. 263)、Definition 7.13.1(p. 264)、Proposition 7.13.4・Example 7.13.5・Theorem 7.13.6(p. 265)、Conjecture 8.0.2(p. 273)、Corollary 8.3.2(p. 279)、Remark 8.3.3(p. 281)

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