和積現象(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$ を超える評価が成り立つが、素体でない有限体では部分体が反例になる。
前提知識: 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$ を実数(または体の元)の空でない有限集合とする。
乗法エネルギーは、加法的組合せ論 の加法エネルギー($a+b=c+d$ の解の個数)の積の版である。
$A\subset\mathbb{R}$ を $n$ 個の元からなる集合とする。
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$ の値は計算で確かめた。どちらの集合でも、和と積の一方は大きい。
実数の空でない有限集合 $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)$ を多く通ることを、接続の個数の上界と比べる議論である。
$A\subset(0,\infty)$ を $n$ 個の元からなる集合とする。
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$
$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}\}$ を考える。
段階 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の定理 のような接続の深い評価を使わず、平面の直線の傾きの順序だけを使っている。
$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}
$$
である。
部分体は和と積で閉じているので $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 による。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する