Erdősの問題(Erdős problems)とは、Paul Erdős が論文や講演で提起した数学の問題の総称である。組合せ論、数論、離散幾何にまたがり、単位距離、相異なる距離、Ramsey 数、向日葵、逆数和と等差数列の問題が代表で、Thomas Bloom のデータベースは 2026 年 10 月の時点で 1221 問を収録している。解決に賞金が付いた問題も多い。
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$ について、次が成り立つ。
$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 の各問題の頁で確かめることを勧める。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する