和積現象

同義語:sum-product phenomenonsum-product problem和積予想sum-product conjecturemultiplicative energy

概要

和積現象(sum-product phenomenon)とは、数の有限集合 $A$ の和の集合 $A+A$ と積の集合 $A\cdot A$ が同時に小さくなることはない、という現象である。等差数列では和が、等比数列では積が小さいが、両方を兼ねる集合はない。実数の有限集合について Erdős と Szemerédi は $\max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}\ge\lvert A\rvert^{2-o(1)}$ を予想し、Elekes は指数 $5/4$、Solymosi は乗法エネルギーと直線の傾きの議論で指数 $4/3-o(1)$ の下界を示した。素体 $\mathbb{F}_p$ でも、大きすぎない集合について指数が $1$ を超える評価が成り立つが、素体でない有限体では部分体が反例になる。

$$\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の不等式, 有限体, 加法的組合せ論

和積現象(sum-product phenomenon)とは、数の有限集合 $A$ について、和の集合 $A+A$ と積の集合 $A\cdot A$ が同時に小さくなることはない、という現象である。等差数列は和について閉じた形に近いので $A+A$ が小さく、等比数列は積について閉じた形に近いので $A\cdot A$ が小さい。しかし 1 つの集合が「等差数列らしさ」と「等比数列らしさ」を同時にもつことはできない。
実数の有限集合について、Erdős と Szemerédi は $\max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}$ が $\lvert A\rvert^{2-o(1)}$ 以上になると予想した。これを 和積予想(Erdős–Szemerédi 予想)という。予想は 2023 年の時点で未解決で(Zha23 p. 273・Remark 8.3.3, p. 281)、指数 $2$ に向けて少しずつ下界が改良されてきた。有限体では、素体には「部分環に近い集合」がないことが、同じ型の評価として表れる。
この記事では、和の集合と積の集合の基本的な評価から始め、乗法エネルギーと直線の配置を使う Solymosi の評価 $\lvert A+A\rvert^2\lvert A\cdot A\rvert\gtrsim\lvert A\rvert^4/\log\lvert A\rvert$ を定数まで明示して証明する。最後に有限体での形と、主張が成り立たない例を表にまとめる。

定義

和の集合・積の集合・乗法エネルギー

$A$ を実数(または体の元)の空でない有限集合とする。

  1. $A+A:=\{a+b\mid a,b\in A\}$ を 和の集合、$A\cdot A:=\{ab\mid a,b\in A\}$ を 積の集合 という。$A\cdot A$ を $AA$ とも書く。
  2. $0\notin A$ のとき $A/A:=\{a/b\mid a,b\in A\}$ とおき、$s\in A/A$ について $r(s):=\#\{(a,b)\in A^2\mid a=sb\}$ とおく。
  3. $ab=cd$ をみたす $(a,b,c,d)\in A^4$ の個数を $E_\times(A)$ と書き、$A$ の 乗法エネルギー という(Zha23 p. 279)。

乗法エネルギーは、加法的組合せ論 の加法エネルギー($a+b=c+d$ の解の個数)の積の版である。

基本的な評価と例

自明な下界と上界

$A\subset\mathbb{R}$ を $n$ 個の元からなる集合とする。

  1. $2n-1\le\lvert A+A\rvert\le n(n+1)/2$ である。
  2. $A\subset(0,\infty)$ なら $2n-1\le\lvert A\cdot A\rvert\le n(n+1)/2$ である。
並べて鎖を作る

1:$A=\{a_1< \dots< a_n\}$ とすると
$$ a_1+a_1< a_1+a_2< a_2+a_2< a_2+a_3< \cdots< a_{n-1}+a_n< a_n+a_n $$
は $A+A$ の相異なる $2n-1$ 個の元である。上界は、$a+b=b+a$ なので和は $\{a,b\}$($a=b$ を許す)だけで決まり、そのような組が $n(n+1)/2$ 個しかないことによる。
2:$\log\colon(0,\infty)\to\mathbb{R}$ は狭義単調な写像で $\log(ab)=\log a+\log b$ をみたすので、$\lvert A\cdot A\rvert=\lvert\log A+\log A\rvert$ である。1 を $\log A$ に当てればよい。$\square$

等差数列と等比数列

$A=\{1,2,\dots,n\}$ では $A+A=\{2,\dots,2n\}$ なので $\lvert A+A\rvert=2n-1$ で、下界の等号が成り立つ。$G=\{1,2,4,\dots,2^{n-1}\}$ では $G\cdot G=\{2^0,\dots,2^{2n-2}\}$ なので $\lvert G\cdot G\rvert=2n-1$ である。一方、$2^a+2^b$($a\le b$)の 2 進表示から $\{a,b\}$ が決まるので $\lvert G+G\rvert=n(n+1)/2$ で、上界の等号が成り立つ。

$n$$\lvert A+A\rvert$$\lvert A\cdot A\rvert$$\lvert G+G\rvert$$\lvert G\cdot G\rvert$
$5$$9$$14$$15$$9$
$10$$19$$42$$55$$19$
$20$$39$$152$$210$$39$

$\lvert A\cdot A\rvert$ と $\lvert G+G\rvert$ の値は計算で確かめた。どちらの集合でも、和と積の一方は大きい。

和積予想と掛け算表

和積予想(Erdős–Szemerédi)

実数の空でない有限集合 $A$ について
$$ \max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}\ge\lvert A\rvert^{2-o(1)} $$
である。ここで $o(1)$ は $\lvert A\rvert\to\infty$ のとき $0$ に近づく量である(Zha23 Conjecture 8.0.2, p. 273)。

指数から $o(1)$ を取り除いて「$\ge c\lvert A\rvert^2$」とすることはできない。$A=\{1,\dots,N\}$ では $\lvert A+A\rvert=2N-1$ であり、掛け算表に現れる数の個数 $\lvert A\cdot A\rvert$ は $o(N^2)$ だからである(Erdős による。Zha23 Theorem 8.1.2, p. 274。証明は Hardy–Ramanujanの定理(素因数の個数) を使うので、ここでは主張だけを引く)。計算すると $\lvert A\cdot A\rvert/N^2$ は $N=10,100,1000$ でそれぞれ $0.420$、$0.291$、$0.248$ である(計算による)。
下界の指数の改良は次のように進んできた。

結果指数 $c$($\max\ge\lvert A\rvert^{c}$ の形)方法所在
Erdős–Szemerédi$1+c_0$($c_0>0$ はある定数)(この記事では扱わない)Zha23 p. 273
Elekes$5/4$点と直線の接続(Szemerédi–Trotterの定理)Zha23 Corollary 8.2.2, p. 275
Solymosi$4/3-o(1)$乗法エネルギーと直線の配置(下の thm-sp-solymosi)Zha23 Corollary 8.3.2, p. 279
Konyagin–Shkredov$4/3+c'$($c'>0$ は小さい定数)Solymosi の方法の改良Zha23 Remark 8.3.3, p. 281

Elekes の評価 $\lvert A+A\rvert\,\lvert A\cdot A\rvert\ge\lvert A\rvert^{5/2}/91$ は、定数まで明示した証明が Szemerédi–Trotterの定理 の記事にある。直線 $y=a(x-b)$ が点の集合 $(A+A)\times(A\cdot A)$ を多く通ることを、接続の個数の上界と比べる議論である。

Solymosi の評価

乗法エネルギーの 2 つの表し方

乗法エネルギーの下界と比による表示

$A\subset(0,\infty)$ を $n$ 個の元からなる集合とする。

  1. $E_\times(A)\ge n^4/\lvert A\cdot A\rvert$ である。
  2. $E_\times(A)=\sum_{s\in A/A}r(s)^2$ であり、$\sum_{s\in A/A}r(s)=n^2$、$1\le r(s)\le n$ である。
Cauchy–Schwarz と言い換え

1:$x\in A\cdot A$ について $\rho(x):=\#\{(a,b)\in A^2\mid ab=x\}$ とおく。$E_\times(A)=\sum_{x\in A\cdot A}\rho(x)^2$ で、$\sum_{x\in A\cdot A}\rho(x)=n^2$ である。Cauchy–Schwarzの不等式 により
$$ n^4=\Bigl(\sum_{x\in A\cdot A}\rho(x)\Bigr)^2\le\lvert A\cdot A\rvert\sum_{x\in A\cdot A}\rho(x)^2=\lvert A\cdot A\rvert\,E_\times(A) $$
である。
2:$ab=cd$ は $a/c=d/b$ と同値である。よって $(a,b,c,d)$ を $s:=a/c$ の値で分けると、$a=sc$ をみたす $(a,c)$ が $r(s)$ 通り、$d=sb$ をみたす $(d,b)$ が $r(s)$ 通りで、$E_\times(A)=\sum_sr(s)^2$ である。$(a,b)\in A^2$ はちょうど 1 つの $s=a/b$ に数えられるので $\sum_sr(s)=n^2$ である。$b$ を決めると $a=sb$ は決まるので $r(s)\le n$ である。$\square$

主定理

Solymosiの和積評価

$A\subset(0,\infty)$ を $n\ge1$ 個の元からなる集合とし、$L:=\lfloor\log_2n\rfloor$ とする。このとき
$$ \lvert A+A\rvert^2\,\lvert A\cdot A\rvert\ge\frac{n^4}{4(L+1)} $$
である。

Zha23 Theorem 8.3.1(p. 279)は定数を明示せずに $\lvert A\cdot A\rvert\,\lvert A+A\rvert^2\gtrsim\lvert A\rvert^4/\log\lvert A\rvert$ と述べている。下の証明は Zha23 pp. 279–281 の筋に沿い、定数を追ったものである。

傾きの近い直線の上の点を足す

段階 1(傾きの選び方). $k=0,1,\dots,L$ について $D_k:=\{s\in A/A\mid 2^k\le r(s)< 2^{k+1}\}$ とおく。lem-sp-energy の 2 により $1\le r(s)\le n< 2^{L+1}$ なので、$D_0,\dots,D_L$ は $A/A$ を重ならずに覆う。よって $\sum_{s\in D_k}r(s)^2$ を最大にする $k$ をとると
$$ \sum_{s\in D_k}r(s)^2\ge\frac{E_\times(A)}{L+1} $$
である。$E_\times(A)\ge n^2> 0$ なので $D_k$ は空でない。$m:=\lvert D_k\rvert$ とおくと、各項は $4^{k+1}$ 未満なので $m\cdot4^{k+1}> E_\times(A)/(L+1)$、すなわち
$$ m\,4^k>\frac{E_\times(A)}{4(L+1)}\qquad(\ast) $$
である。
段階 2(直線の上の点). $D_k$ の元を $s_1< s_2< \dots< s_m$ と並べ、$j=1,\dots,m$ について
$$ L_j:=\{(b,s_jb)\mid b\in A,\ s_jb\in A\}\subset A\times A $$
とおく。これは原点を通る傾き $s_j$ の直線の上にある $A\times A$ の点の全体で、$\lvert L_j\rvert=r(s_j)\ge2^k$ である。さらに $a_0:=\min A$ とし、$L_{m+1}:=\{(a_0,y)\mid y\in A,\ y\ge s_ma_0\}$ とおく。$(b,s_mb)\in L_m$ に $(a_0,s_mb)$ を対応させると、$s_mb\in A$ かつ $s_mb\ge s_ma_0$ なので $L_{m+1}$ への単射になり、$\lvert L_{m+1}\rvert\ge\lvert L_m\rvert\ge2^k$ である。
段階 3(和は重ならない). $j=1,\dots,m$ について $L_j+L_{j+1}:=\{p+q\mid p\in L_j,\ q\in L_{j+1}\}$ を考える。

  • $j< m$ のとき:$p=t(1,s_j)$、$q=u(1,s_{j+1})$($t,u>0$)と書ける。$(1,s_j)$ と $(1,s_{j+1})$ は 1 次独立なので、$p+q$ から $(t,u)$ が決まり、$\lvert L_j+L_{j+1}\rvert=\lvert L_j\rvert\,\lvert L_{j+1}\rvert$ である。また $p+q$ の傾き $(ts_j+us_{j+1})/(t+u)$ は $s_j$ と $s_{j+1}$ の重み付き平均なので、開区間 $(s_j,s_{j+1})$ に入る。
  • $j=m$ のとき:$p=t(1,s_m)$、$q=(a_0,y)$ とすると $p+q=(t+a_0,ts_m+y)$ で、第 1 成分から $t$、次に第 2 成分から $y$ が決まるので、$\lvert L_m+L_{m+1}\rvert=\lvert L_m\rvert\,\lvert L_{m+1}\rvert$ である。$y\ge s_ma_0$ なので傾きは $s_m$ 以上である。
    傾きの範囲 $(s_1,s_2),\dots,(s_{m-1},s_m),[s_m,\infty)$ は互いに交わらないので、集合 $L_1+L_2,\dots,L_m+L_{m+1}$ は互いに交わらない。どれも $(A\times A)+(A\times A)=(A+A)\times(A+A)$ に含まれる。

段階 4(まとめ). 段階 3、段階 2、$(\ast)$、lem-sp-energy の 1 を順に使うと
$$ \lvert A+A\rvert^2\ge\sum_{j=1}^m\lvert L_j\rvert\,\lvert L_{j+1}\rvert\ge m\,4^k>\frac{E_\times(A)}{4(L+1)}\ge\frac{n^4}{4(L+1)\lvert A\cdot A\rvert} $$
である。両辺に $\lvert A\cdot A\rvert$ を掛ければよい。$\square$

この証明は、Szemerédi–Trotterの定理 のような接続の深い評価を使わず、平面の直線の傾きの順序だけを使っている。

指数 $4/3-o(1)$

$A\subset(0,\infty)$ を $n$ 個の元からなる集合とすると
$$ \max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}\ge\frac{n^{4/3}}{\bigl(4(\lfloor\log_2n\rfloor+1)\bigr)^{1/3}} $$
である。$A\subset\mathbb{R}$ が $n\ge3$ 個の元をもつときは、$n$ を $m:=\lceil(n-1)/2\rceil$ に替えた同じ不等式が成り立つ。とくに $\max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}\ge\lvert A\rvert^{4/3-o(1)}$ である。

正の部分に帰着する

$M:=\max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}$ とおくと $M^3\ge\lvert A+A\rvert^2\lvert A\cdot A\rvert$ なので、前半は thm-sp-solymosi から従う。後半:$A\setminus\{0\}$ の正の元と負の元のうち多い方を $P_0$ とし、負の元なら $P:=-P_0$、正の元なら $P:=P_0$ とおく。$P\subset(0,\infty)$、$\lvert P\rvert\ge m$ である。$(-a)+(-b)=-(a+b)$、$(-a)(-b)=ab$ なので $\lvert P+P\rvert=\lvert P_0+P_0\rvert\le\lvert A+A\rvert$、$\lvert P\cdot P\rvert=\lvert P_0\cdot P_0\rvert\le\lvert A\cdot A\rvert$ である。$P$ から $m$ 個の元を選んだ部分集合に前半を当てればよい。最後の主張は、右辺の対数の因子が $n^{o(1)}$ であることによる。$\square$

有限体での和積現象

有限体 $\mathbb{F}_q$ では、$A$ が部分体なら $A+A=A\cdot A=A$ であり、和積現象は起こらない。素数 $p$ の素体 $\mathbb{F}_p$ には $\mathbb{F}_p$ 自身のほかに部分体がなく、次の評価が成り立つ。

素体での和積評価(主張と所在)

任意の $\varepsilon>0$ について $\delta>0$ と $c>0$ があり、素数 $p$ と $1< \lvert A\rvert< p^{1-\varepsilon}$ をみたす任意の $A\subset\mathbb{F}_p$ について
$$ \max\{\lvert A+A\rvert,\lvert A\cdot A\rvert\}\ge c\lvert A\rvert^{1+\delta} $$
である。

所在

これは Bourgain–Katz–Tao の結果と、その後の Bourgain–Glibichuk–Konyagin の結果を合わせたものである(Zha23 Remark 8.3.4・Theorem 8.3.5, p. 281)。証明は長いので、この記事では主張だけを引く。Zha23 p. 281 はこれを「素体は近似的な部分環をもたない」と言い表している。

部分体と全体では評価が成り立たない
  1. $q=p^2$ とし、$A:=\mathbb{F}_p\subset\mathbb{F}_{q}$ とすると、$\lvert A\rvert=q^{1/2}$ で $\lvert A+A\rvert=\lvert A\cdot A\rvert=\lvert A\rvert$ である。
  2. $A:=\mathbb{F}_p$ 自身では $\lvert A+A\rvert=\lvert A\cdot A\rvert=\lvert A\rvert$ である。
部分体は和と積で閉じている

部分体は和と積で閉じているので $A+A\subset A$、$A\cdot A\subset A$ である。逆に $a=a+0=a\cdot1$ で $0,1\in A$ なので、どちらも $A$ に等しい。$\lvert\mathbb{F}_p\rvert=p=q^{1/2}$ である。$\square$

1 は thm-sp-prime-field の「素体」の仮定を外すと結論が成り立たないことを、2 は「$\lvert A\rvert< p^{1-\varepsilon}$」の仮定を外すと結論が成り立たないことを示す。2 では $\max=\lvert A\rvert$ で、$c\lvert A\rvert^{1+\delta}$ は $p\to\infty$ のとき $\lvert A\rvert$ を超える。

反例の表

主張が成り立たない例
主張変える仮定・形例何が成り立たなくなるか
和か積の一方が大きい和と積を別の集合でとる($A+A$ と $B\cdot B$)$A=\{1,\dots,n\}$、$B=\{1,2,\dots,2^{n-1}\}$$\lvert A+A\rvert=\lvert B\cdot B\rvert=2n-1$ で、どちらも小さい
和積予想を $c\lvert A\rvert^2$ で述べた形指数の $o(1)$ を外す$A=\{1,\dots,N\}$$\lvert A+A\rvert=2N-1$、$\lvert A\cdot A\rvert=o(N^2)$
thm-sp-prime-field$\mathbb{F}_p$ を素体でない有限体に替える$\mathbb{F}_p\subset\mathbb{F}_{p^2}$和も積も $A$ のまま
thm-sp-prime-field$\lvert A\rvert< p^{1-\varepsilon}$$A=\mathbb{F}_p$和も積も $A$ のまま

1 行目は、和積現象が「同じ集合」の和と積についての主張であることを示す。2 行目の $o(N^2)$ は Zha23 Theorem 8.1.2 による。3・4 行目は prop-sp-subfield による。

応用

  • 接続幾何:Elekes の評価は、和と積の集合の問題を点と直線の接続の個数の上界(Szemerédi–Trotterの定理)に移して得られる。
  • 有限体:thm-sp-prime-field は、素体の部分集合が和と積の両方について閉じた形に近づけないことを述べる。有限体での加法的な問題の例は Cap set問題 や 多項式法 にある。
  • 乗法エネルギー:lem-sp-energy の議論は加法エネルギーの議論の積の版で、Balog–Szemerédi–Gowersの定理 とあわせて、エネルギーと集合の構造の関係を調べる道具になる。

関連項目

参考文献

[1]
Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, 1st ed.(頁・番号は 2024年6月18日更新の著者版による), Cambridge University Press, 2023, 第 8 章(著者版 pp. 273–281):Conjecture 8.0.2(和積予想、p. 273)、Theorem 8.1.2(掛け算表、p. 274)、Corollary 8.2.2(Elekes、p. 275)、§8.3 Theorem 8.3.1・Corollary 8.3.2(Solymosi、p. 279、証明 pp. 279–281)、Remark 8.3.3・Remark 8.3.4・Theorem 8.3.5(p. 281)

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