Erdősの問題

同義語:エルデシュの問題Erdős problems

概要

Erdősの問題(Erdős problems)とは、Paul Erdős が論文や講演で提起した数学の問題の総称である。組合せ論、数論、離散幾何にまたがり、単位距離、相異なる距離、Ramsey 数、向日葵、逆数和と等差数列の問題が代表で、Thomas Bloom のデータベースは 2026 年 10 月の時点で 1221 問を収録している。解決に賞金が付いた問題も多い。

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

前提知識: グラフ, Ramseyの定理, 素数

Erdős の問題(Erdős problems)は、Paul Erdős が論文や講演で提起した数学の問題の総称である。Hilbertの問題 のように 1 回で発表された一覧ではなく、組合せ論、数論、離散幾何、集合論などにまたがる膨大な問題の集まりである。解決に賞金を付けた問題も多い。Thomas Bloom のデータベースは 2026 年 10 月の時点で 1221 問を収録している(Blo26)。
問題の数が多いので、全体の一覧は作らない。この記事は、述べるのが易しく、Mathpedia の記事に続いている主要な問題の地図である。問題の文は短いが、解くには別の分野の道具が要ることが多い。到達点を表で示し、分野ごとに背景を述べて入口の記事へ案内する。

記号

単位距離と相異なる距離

平面の $n$ 点の集合 $P$ に対し、$u(n)$ を距離がちょうど $1$ である点の組の個数の $P$ についての最大値とする。$g(n)$ を、$P$ の点の間に現れる相異なる距離の個数の $P$ についての最小値とする。

$u(n)$ は 単位距離グラフ の辺の本数の最大値である。Ramsey 数 $R(k)$ は、辺を 2 色に塗った完全グラフ $K_n$ が単色の $K_k$ を必ず含む最小の $n$ である(Ramseyの定理)。向日葵は、どの 2 つの共通部分も同じ集合であるような集合族である(sunflower)。

主な問題の一覧

第 3 列の到達点は、学術誌に出版された論文と教科書にある結果である。$f\gg g$ は、ある定数 $c>0$ で $f\ge cg$ となることを表す。

分野問い到達点入る記事
離散幾何$g(n)\gg n/\sqrt{\log n}$ か(Erd46)$g(n)\gg n/\log n$(Guth–Katz、GK15)離散幾何学
離散幾何$u(n)\le n^{1+o(1)}$ か(Zha23 Conjecture 1.4.7)$n^{1+c/\log\log n}\le u(n)\le Cn^{4/3}$(Erd46、Spencer–Szemerédi–Trotter)。審査前の報告は「未解決問題」の節単位距離グラフ、Szemerédi–Trotterの定理
離散幾何一般の位置にある $2^{n-2}+1$ 点は凸 $n$ 角形を含むか必要な点の個数は $2^{n-2}+1$ 以上で、$2^{n+o(n)}$ 以下(Suk17)Erdős–Szekeresの定理(凸多角形)
組合せ論$\lim_kR(k)^{1/k}$ は存在するか、値は何か$\sqrt2\le\liminf$、$\limsup\le4-\varepsilon$(Campos ら、CGMS26)Ramseyの定理、確率論的方法
組合せ論$k$ を固定すると、大きさ $n$ の集合の族で $c_k^n$ 個以上の元をもつものは $k$ 枚の花びらをもつ向日葵($k$ 個の集合からなる向日葵)を含むか必要な大きさは Erdős–Rado の $n!\,(k-1)^n$ から、およそ $(\log n)^n$ の形へ改良された(ALWZ21)sunflower
組合せ論$\mathrm{ex}(n,K_{s,t})$ の増大度は $n^{2-1/s}$ か($s\le t$。Zha23 Conjecture 1.4.4)上界は Kővári–Sós–Turánの定理。下界は小さい $s$ などで知られている極値グラフ理論、Zarankiewicz問題
加法的組合せ論$\sum_{a\in A}1/a=\infty$ なら $A$ は任意の長さの等差数列を含むか(Zha23 Conjecture 0.2.5)3 項の場合は Bloom–Sisask の評価から従う(Zha23 p. 7。審査前の報告は「未解決問題」の節)。素数の場合は Green–Taoの定理、密度の場合は Szemerédiの定理Szemerédiの定理
数論$n> 2$ について $\frac4n=\frac1a+\frac1b+\frac1c$ は正の整数解をもつか(Erdős–Straus)$n$ を素数に制限してよい。ほとんどすべての $n$ で解がある(Vaughan、Blo26 問題 242)エジプト式分数

解決した問題も、Erdős の問題の大事な一部である。Erdős–Stoneの定理、Erdős–Ko–Radoの定理、Erdős–Ginzburg–Zivの定理 は定理として確立している。密度の形の等差数列の問題は Erdős と Turán の予想(1936 年)で、Szemerédiの定理 として解決した(Zha23 pp. 5–7)。

分野ごとの案内

離散幾何。 平面の点の距離の問題は 1946 年の論文 Erd46 に始まる。単位距離の個数については、$K_{2,3}$ が単位距離グラフに含まれないことから $u(n)=O(n^{3/2})$ が従う。2 点からともに距離 $1$ の点は高々 2 個だからである(Zha23 pp. 25–26)。学術誌に出版された最良の上界 $O(n^{4/3})$ は交差数の不等式で短く示せる(Szemerédi–Trotterの定理)。下界は、正方格子を適当に縮尺して、整数 $r$ が 2 つの平方の和に多くの仕方で書けることを使う(Zha23 p. 25)。相異なる距離の問題では、Guth と Katz が多項式の方法と代数幾何の道具で、格子の例に $\sqrt{\log n}$ の差まで迫る下界を得た(Zha23 p. 26)。凸多角形の問題は、1935 年の Erdős と Szekeres の論文に始まる。予想の値 $2^{n-2}+1$ は $n\le6$ で正しく(Erdős–Szekeresの定理(凸多角形))、Suk17 は上界を $2^{n+o(n)}$ まで下げ、指数の主要項を予想に一致させた。
組合せ論。 $R(k)$ の下界は、ランダムな塗り分けを数える 確率論的方法 の出発点である。上界 $R(k)\le4^k$ は Erdős と Szekeres の 1935 年の評価で、CGMS26 はこれを指数の底で改良した最初の結果である。向日葵の問題は、Erdős と Rado の 1960 年の論文に始まる。Erdős はこの問題に 1000 ドルの賞金を付けた(Blo26 問題 20)。ALWZ21 は、長く $n^n$ の程度にとどまっていた上界を $(\log n)^n$ の程度へ下げた。極値グラフ理論 の問題では、Erdős–Stoneの定理 が非 2 部グラフの禁止の場合を決め、2 部グラフの場合が残る。$K_{s,t}$ の予想は $s=2,3$ と $t$ が $s$ より十分大きい場合に知られ、最初の残りは $K_{4,4}$ である(Zha23 p. 24)。
加法的組合せ論。 逆数和の問題は、素数に等差数列があるかという問いから動機づけられた(Zha23 p. 7)。逆数和が発散する集合は、無限に多くの $N$ で $|A\cap[N]|\ge N/(\log N(\log\log N)^2)$ を満たすので、この問題は Szemerédiの定理 の上界の評価の問題である(Zha23 p. 7)。素数の場合は別の方法で Green–Taoの定理 として解決した。発散の仮定は外せない。$A=\{2^m\mid m\ge0\}$ の逆数和は収束し、$A$ は 3 項の等差数列も含まないので、仮定を外した主張の反例である($a< b< c$ なら $2^{a}+2^{c}=2^{a}(1+2^{c-a})$ は奇数の因子 $1+2^{c-a}> 1$ をもつので、$2^{b+1}$ に等しくない)。もう 1 つの代表は Erdős と Turán の加法基底の問題である。$A+A$ が有限個を除くすべての整数を含むなら、$n=a+a'$($a,a'\in A$)の表し方の個数は有界でない、という予想である(Blo26 問題 28)。
数論。 Erdős–Straus の問題では、$n$ が素数の場合に帰着する。$n=pm$ のとき、$\frac4p$ の表示の各分母を $m$ 倍すれば $\frac4n$ の表示が得られるからである。$n\le10^{18}$ の範囲で確かめられており、$840$ を法とする 6 個の剰余類を除いて証明されている(Blo26 問題 242)。

例:距離の個数の簡単な評価

一覧の最初の 2 行は互いに関係している。その関係と、$g(n)$ の最初の下界は短く示せる。

距離の個数の基本の不等式

$n\ge3$ について、次が成り立つ。

  1. $g(n)\ge\sqrt{(n-2)/2}$。
  2. $g(n)\,u(n)\ge\binom n2$。
円の交点を数える

$P$ を $n$ 点の集合とし、$P$ の点の間の相異なる距離の個数を $d$ とする。
1:$p\ne q$ を $P$ の 2 点とする。ほかの点 $r$ について、組 $(|rp|,|rq|)$ は $d^2$ 通り以下である。組 $(a,b)$ を決めると、$r$ は $p$ を中心とする半径 $a$ の円と $q$ を中心とする半径 $b$ の円の交点である。中心が違う 2 つの円の交点は高々 2 点である。よって $n-2\le2d^2$ である。
2:$P$ の $\binom n2$ 個の組を、距離の値で $d$ 個の組に分ける。距離が $a$ である組の全体は、$P$ を $1/a$ 倍に縮小すると距離 $1$ の組になるから、$u(n)$ 個以下である。よって $\binom n2\le d\,u(n)$ である。$P$ として $d=g(n)$ となるものを選べばよい。

2 と $u(n)\le Cn^{4/3}$ を合わせると、$g(n)\gg n^{2/3}$ となり、1 よりずっと良い下界が得られる。単位距離の上界が距離の個数の下界を与えるが、逆は成り立たない(Zha23 p. 26)。予想される $g(n)$ の大きさは、$\lfloor\sqrt n\rfloor\times\lfloor\sqrt n\rfloor$ の正方格子から来る。格子の 2 点の距離の 2 乗は $a^2+b^2$ の形の整数で、その種類の個数がおよそ $n/\sqrt{\log n}$ だからである(Zha23 p. 26)。

読み進め方

未解決問題

2026 年 10 月の Blo26 で、相異なる距離の予想の形($n/\sqrt{\log n}$)、凸多角形の予想、$\lim R(k)^{1/k}$ の問題、向日葵の問題、Erdős–Straus の問題は未解決と記載されている。
Erdős の問題の状態は速く変わる。問題の文献の探索によって以前の解決が見つかることも、計算機の支援による解答が報告されることもある。学術誌の審査を経ていない報告もある。単位距離の問題では、2026 年 5 月に、無限に多くの $n$ で $u(n)\ge n^{1+c}$($c>0$ は定数)となるという、予想を否定する構成が公表され、Saw26 は $n^{1.014}$ を超える下界を与えた。Alo26 はこの構成を人の手で確かめた要約であり、Blo26 問題 90 はこの問題を否定的に解決したものとして記載している。同じ頁には上界 $O(n^{4/3-c})$ の形式化された証明も挙げられている。逆数和と等差数列の問題でも、Blo26 問題 3 は Erdős の予想の形式化された証明を挙げている。これらは 2026 年 10 月の時点で学術誌の審査を経ていないので、この記事は到達点に含めない。問題ごとの最新の状態は Blo26 の各問題の頁で確かめることを勧める。

関連項目

参考文献

[2]
Will Sawin, An explicit lower bound for the unit distance problem, arXiv preprint, 2026, arXiv:2605.20579v1
[3]
Noga Alon, Thomas F. Bloom, W. T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang, Melanie Matchett Wood, Remarks on the disproof of the unit distance conjecture, arXiv preprint, 2026, arXiv:2605.20695v1
[4]
Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, 著者版(2024 年 6 月 18 日更新), Cambridge University Press, 2023, 著者版の頁。§0.2 pp. 5–7(Conjecture 0.2.5)、§1.4 pp. 24–26(Conjecture 1.4.4、1.4.7、Question 1.4.9、Theorem 1.4.10)
[6]
Larry Guth, Nets Hawk Katz, On the Erdős distinct distances problem in the plane, Annals of Mathematics, 2015, pp. 155–190
[7]
Andrew Suk, On the Erdős–Szekeres convex polygon problem, Journal of the American Mathematical Society, 2017, pp. 1047–1053
[8]
Marcelo Campos, Simon Griffiths, Robert Morris, Julian Sahasrabudhe, An exponential improvement for diagonal Ramsey, Annals of Mathematics, 2026, pp. 869–932
[9]
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang, Improved bounds for the sunflower lemma, Annals of Mathematics, 2021, pp. 795–815

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