erdosの未解決問題を解いてみた

505

初めに

https://www.erdosproblems.com/ にある https://www.erdosproblems.com/315 を解決したという話です. (ただし後述するようにオリジナリティは怪しいです)
とりあえず問題を書くための準備をしていきます:

シルベスター数列 $s_{i}$ を, $s_{0} = 1, s_{1} = 2, s_{i + 1} = s_{i}^{2} - s_{i} + 1$ で帰納的に定める.

$n$ を正の整数としたとき,
$\begin{array}{r} \sum_{i = 1}^{n - 1} \frac{1}{s_{i}} + \frac{1}{s_{n} - 1} = 1 \end{array}$
が成立します. 証明は帰納法すればokです.

erdosproblem-315

正整数の無限列 $a_{1} \leq a_{2} \leq a_{3} \leq \dots$ が次の式を満たしたとする:
$\begin{array}{r} \sum_{i = 1}^{\infty} \frac{1}{a_{i}} = 1 \end{array}$

このとき, $\underset{i}{lim inf} a_{i}^{2^{- i}} \leq lim_{i} s_{i}^{2^{- i}} = 1.264 \dots$ であり, かつ等号成立は $a_{i} = s_{i} (\forall i \in Z_{> 0})$ と同値であるか?
(ここで, $a^{b^{c}}$ は $a^{(b^{c})}$ を意味する)

これが解けたという話をしていくのですが, 先にどうオリジナリティが怪しいかという話をしておきます:
まず, 上の問題に対して, 次のような有限バージョンが考えられます(こっちの方が自然な気もする):

有限版

正整数の列 $a_{1} \leq a_{2} \leq a_{3} \leq \dots \leq a_{n}$ が次の式を満たしたとする:
$\begin{array}{r} \sum_{i = 1}^{n} \frac{1}{a_{i}} = 1 \end{array}$

このとき, $a_{n} \leq s_{n} - 1$ であり, かつ等号成立は $a_{i} = s_{i} (\forall i < n)$ と同値であるか?

で, これはすでに解かれています. 英語版wikipedia によると1919年の論文ですでに言及されているらしいです. 自分もerodosの問題を考えるにあたり, とりあえず上の命題の証明( Sou )を読みました.
すると, 大体そのままの手法でerdosの方の問題が解けてしまいました. なのでオリジナリティが怪しいというわけです.

あとそもそも https://www.erdosproblems.com/ はerdosとは関係ない個人サイトなので, もうすでに解かれている(けどサイトが更新されていない)という可能性もあると思います. 解法が初等的だし.

もしすでに解いてた文献があればご一報ください. 以下証明に入るので常体です.

(追記:2025/3/19) arXivに論文としてあげました. こっちの方が行間がうまってて丁寧かも?(英語だけど) https://arxiv.org/abs/2503.02317 (追記終)

証明

まず, 問題をやや一般化して述べる. そのためにシルベスター数列を一般化し, 性質について調べる.

一般化シルベスター数列

正整数 $n$ に対し, 一般化シルベスター数列 $s_{i} (n)$ を, $s_{0} (n) = n, s_{1} (n) = n + 1, s_{i + 1} (n) = s_{i} (n)^{2} - s_{i} (n) + 1$ で帰納的に定める.

正整数 $n, l$ および非負整数 $m$ に対し, 次の式がすべて成立する.

$\sum_{i = 1}^{m - 1} \frac{1}{s_{i} (n)} + \frac{1}{s_{m} (n) - 1} = \frac{1}{n}$
$s_{m + 1} (n) - 1 = \prod_{i = 0}^{m} s_{i} (n)$
$n^{2^{l - 1}} < s_{l} (n) \leq {(n + 1)}^{2^{l - 1}}$
$s_{l + m - 1} (n) = s_{l} (s_{m} (n) - 1)$

1,2は $m$ の, 3,4は $l$ の帰納法で容易に確かめられる.

$n$ を正の自然数とする.
このとき, 数列 $(s_{i} (n)^{2^{- i}})_{i > 0}$ は広義単調減少数列であり, 数列 $((s_{i} (n) - 1)^{2^{- i}})_{i > 0}$ は広義単調増加である.
従って, どちらの数列も収束先を $[n, n + 1]$ に持つ.

$i$ が正なら, $s_{i + 1} (n) = s_{i} (n)^{2} - s_{i} (n) + 1 \leq s_{i} (n)^{2}$ および $s_{i + 1} (n) - 1 = s_{i} (n)^{2} - s_{i} (n) \geq (s_{i} (n) - 1)^{2}$ から前半がわかる.
後半は命題1の3番目の不等式から従う.

erdosproblem-315(の一般化)

$n$ を正の整数とし, 正整数の無限列 $a_{1} \leq a_{2} \leq a_{3} \leq \dots$ が次の式を満たしたとする:
$\begin{array}{r} \sum_{i = 1}^{\infty} \frac{1}{a_{i}} = \frac{1}{n} \end{array}$
このとき, $\underset{i}{lim inf} a_{i}^{2^{- i}} \leq lim_{i} s_{i} (n)^{2^{- i}}$ であり, かつ等号が成立するのは $a_{i} = s_{i} (n) (\forall i \in Z_{> 0})$ のときのみである.

次が大事な補題となる. (本質的に Sou の議論をパッケージ化したもの.)

$u$ を正の実数, $t$ を正の自然数とする. ここで, 正の実数列 $u_{1} \geq u_{2} \geq u_{3} \geq \dots$ および $v_{1} \geq v_{2} \geq v_{3} \geq \dots$ が次の条件を満たしたとする.

$n \geq t$ ならば, $\sum_{i = 1}^{n} u_{i} + u \prod_{i = 1}^{n} u_{i} = u$ かつ $\sum_{i = 1}^{n} v_{i} + u \prod_{i = 1}^{n} v_{i} \leq u$
$n < t$ ならば, $v_{n} \leq u_{n}$

このとき, 任意の正整数 $n$ に対し, $\sum_{i = 1}^{n} v_{i} \leq \sum_{i = 1}^{n} u_{i}$ .

$n$ の帰納法で示す. 条件2より $n < t$ なら自明. $n (\geq t)$ 未満での成立を仮定し, $n$ での成立を示す.
もし, $v_{n} \leq u_{n}$ なら, $n - 1$ での帰納法の仮定から明らか.
もし, $\prod_{i = 1}^{n} v_{i} \geq \prod_{i = 1}^{n} u_{i}$ なら, 条件1より,
$\begin{array}{r} \sum_{i = 1}^{n} v_{i} \leq u - \prod_{i = 1}^{n} v_{i} \leq u - \prod_{i = 1}^{n} u_{i} = \sum_{i = 1}^{n} u_{i} . \end{array}$
よって, $v_{n} > u_{n}$ かつ $\prod_{i = 1}^{n} v_{i} < \prod_{i = 1}^{n} u_{i}$ と仮定して示せばよい. $\prod_{i = j}^{n} v_{i} < \prod_{i = j}^{n} v_{i}$ を満たすような $j$ の中で最大のものを $m$ と置く.
すると, $m$ の最大性より, $m < l \leq n$ なら $\prod_{i = m}^{l} v_{i} \leq \prod_{i = m}^{l} u_{i}$ が成立する. よって, 下の補題より $\sum_{i = m}^{n} v_{i} \leq \sum_{i = m}^{n} u_{i}$ がわかる. $m - 1$ での帰納法の仮定と合わせ, $\sum_{i = 1}^{n} v_{i} \leq \sum_{i = 1}^{n} u_{i}$ が従う.

この補題は Sou のpropsitionと同一だが, self-containednessを上げるためにここで述べる.

正の実数列 $u_{1} \geq u_{2} \geq \dots \geq u_{n}$ および $v_{1} \geq v_{2} \geq \dots \geq v_{n}$ が次の条件を満たしたとする.

任意の $m \leq n$ に対し, $\prod_{i = 1}^{m} v_{i} \leq \prod_{i = 1}^{m} u_{i}$

このとき, $\sum_{i = 1}^{n} v_{i} \leq \sum_{i = 1}^{n} u_{i}$ が成立する．

必要なら $u_{n}$ を小さく取り替えて, $\prod_{i = 1}^{n} v_{i} = \prod_{i = 1}^{n} u_{i}$ と仮定してよい. $α_{i} = \log (u_{i}), β_{i} = \log (v_{i})$ と置く. すると, $(α_{i})$ が $(β_{i})$ の優数列であるという条件の下で $\sum_{i = 1}^{n} e^{α_{i}} \geq \sum_{i = 1}^{n} e^{β_{i}}$ を示せばよい. これはムーアヘッドの不等式から従う. ムーアヘッドの不等式に関しては AOPS などを参照.

あとは補題2を上手く使っていけば定理1が示せる. 示したい定理を再掲する:

(定理3の再掲)

(定理3)

まず, $a_{1} \neq n + 1$ の場合に帰着できることを示す.

数列 $a_{i}$ が $s_{i} (n)$ と全項が一致するときは主張は自明. よって, $a_{i} \neq s_{i} (n)$ となる $i$ が存在するとしてよい. このような $i$ の中で最小のものを再び $i$ と置く. すると, $i$ の最小性と命題1の1より,
$\begin{array}{r} \sum_{j = i}^{\infty} \frac{1}{a_{j}} = \frac{1}{s_{i} (n) - 1} \end{array}$
が成立する. 命題1の4と合わせ, 数列を $i - 1$ 項分スライドさせることで結局 $a_{1} \neq n + 1$ (従って $a_{1} \geq n + 2$ )としてよい.

$n = 1$ の場合は例外処理がいるので, $n \neq 1$ の場合を先に示す.
正の実数列 $u_{i}$ を次のように定義する:
$\begin{array}{r} u_{i} = {\begin{cases} (n + 2)^{- 1} & i = 1 \\ 2 (n + 1)^{- 2} & i = 2 \\ {s_{i - 2} (l)}^{- 1} & i \geq 3 \end{cases} \end{array}$
ここで, $l = \frac{1}{2} n (n + 1)^{2} (n + 2)$ である. $v_{i} = {a_{i}}^{- 1}$ , $u = n^{- 1}$ , $t = 2$ と置くと, これらが補題2の条件を満たすことを順に示す.
代入計算により, $\frac{1}{n} - (u_{1} + u_{2}) = \frac{2}{n (n + 2)} - \frac{2}{(n + 1)^{2}} = \frac{1}{l} = u u_{1} u_{2} .$
よって, 任意の正の整数 $m \geq t = 2$ に対し,
$\begin{aligned} \frac{1}{n} - \sum_{i = 1}^{m} u_{i} - u \prod_{i = 1}^{m} u_{i} & = \frac{1}{l} - \sum_{i = 3}^{m} u_{i} - \frac{1}{l} \prod_{i = 3}^{m} u_{i} \\ = \frac{1}{l} - \sum_{i = 1}^{m - 2} \frac{1}{s_{i} (l)} - \prod_{i = 0}^{m - 2} \frac{1}{s_{i} (l)} = 0 \end{aligned}$
最後の等式に, 命題1の3,4を用いた. これにより, 条件1の前半がわかった.
次に後半を示す. $m$ を任意の正の整数とし, $q = \frac{1}{n} - \sum_{i = 1}^{m} \frac{1}{a_{i}}$ と置く. $\sum_{i = 1}^{\infty} \frac{1}{a_{i}} = \frac{1}{n}$ より, $q > 0$ . また, $q$ の分母は $n \prod_{i = 1}^{m} a_{i}$ の約数. よって, $q \geq \frac{1}{n} \prod_{i = 1}^{m} \frac{1}{a_{i}}$ . これは条件1の後半を示す.
条件2は $a_{1} \geq n + 2$ より明らか.
よって, 補題2が使え, 任意の $m$ に対し, $\sum_{i = 1}^{m} u_{i} \geq \sum_{i = 1}^{m} v_{i}$ となる. これと, $\sum_{i = 1}^{\infty} u_{i} = u = \sum_{i = 1}^{\infty} v_{i}$ を合わせると, $u_{j} \leq v_{j}$ となる $j$ が無限個ないといけない. ゆえに, $\underset{j}{lim inf} a_{j}^{2^{- j}} = \underset{j}{lim inf} v_{j}^{- 2^{- j}} \leq lim_{j} s_{j - 2} (l)^{2^{- j}}$ . 命題2と合わせ, $\underset{j}{lim inf} a_{j}^{2^{- j}} \leq (s_{1} (l))^{1 / 8} = (l + 1)^{1 / 8}$ . また, 命題2より, $lim_{j} s_{j} (n)^{2^{- j}} \geq (s_{3} (n) - 1)^{1 / 8} = (n (n + 1) (n^{2} + n + 1))^{1 / 8}$ . 今, $n \geq 2$ より, $n (n + 1) (n^{2} + n + 1) > l + 1$ となるので, 所望の不等式が示された.

$n = 1$ の場合は,
$\begin{array}{r} u_{i} = {\begin{cases} \frac{1}{3} & i = 1, 2 \\ \frac{3}{10} & i = 3 \\ {s_{i - 3} (31)}^{- 1} & i \geq 4 \end{cases} \end{array}$
として, $t = 3$ とすれば同様の議論が回る.

投稿日：2024年5月18日

更新日：24日前

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

13703

他の人のコメント

コメントはありません。

読み込み中

erdosの未解決問題を解いてみた

初めに
証明