The Hofstadter consecutive-sum sequence omits infinitely many positive integers

Each language version is independently generated for its own context, not a direct translation.

🎮 ゲームのルール：「連続した足し合わせ」

まず、この「ホフスタッター数列」というゲームのルールを想像してみてください。

スタート： 最初は「1」と「2」だけを書きます。
- 現在のリスト：[1, 2]
次の数字を決める：
- これまでに書いた数字の中から、「連続した 2 つ以上」を足し合わせた数字を作ります。
- その中で、**「今までの数字より大きく、かつ最も小さい」**ものを選びます。
- それをリストの最後に追加します。

【実際の動き】

1 + 2 = 3 → 3 は 2 より大きいので OK。リスト：[1, 2, 3]
2 + 3 = 5 → 4 は作れない（1+2+3=6 だが、4 は作れない）。5 が最小。リスト：[1, 2, 3, 5]
3 + 5 = 8 → 6 は作れる（1+2+3=6）。リスト：[1, 2, 3, 5, 6]
5 + 6 = 11 → 7 は作れない。8 は作れる（3+5）。リスト：[1, 2, 3, 5, 6, 8]

こうして数字が並んでいきます：
1, 2, 3, 5, 6, 8, 10, 11, 14, ...

問題点：
見ての通り、4, 7, 9, 12, 13... という数字が「スキップ（欠落）」しています。
昔から数学者たちは、「このゲームを無限に続けたら、結局『ほとんどすべての数字』が現れるようになるのか？それとも『無限に欠けた数字』が残り続けるのか？」と疑問に思っていました。

🔍 この論文の発見：「欠けた数字は無限に増える」

この論文を書いた唐（タン）さんは、**「欠けた数字は無限に増え続ける」**ことを証明しました。

🧠 直感的な説明（アナロジー）

このゲームを**「数字の階段」**に例えてみましょう。

理想の階段： 1, 2, 3, 4, 5, 6... と段差が 1 ずつで、隙間なく続く階段。
このゲームの階段： 1, 2, 3, 5, 6, 8... と、所々で段が飛び越えられています。

唐さんの証明は、以下のようなロジックです。

「飛び越え」が蓄積する：
このゲームのルールは「連続した数字を足す」ことですが、ある程度大きな数字になると、「2 のべき乗（2, 4, 8, 16, 32...）」という特別な数字が、このルールで作ろうとすると「連続した数字の和」にはなりきれないことがわかってきます。
（例：4 は 1+2+? で作ろうとすると、1+2=3, 1+2+3=6 なので、4 は作れません。8 も同様です。）
数学的な「壁」：
論文では、もし「欠けた数字」が有限個で終わる（つまり、いつか隙間が埋まって階段が綺麗になる）と仮定すると、数学的に**「ありえない方程式」が生まれてしまうことを示しました。
それは、「ある特定の形をした数字（2 のべき乗）が、無限に何度も同じ方法で作られてしまう」**という矛盾です。数学の法則（ディオファントス方程式の解の有限性）によって、これはあり得ないとされています。
結論：
矛盾が生じるということは、最初の仮定（欠けた数字は有限）が間違っていたということです。
つまり、「欠けた数字」は永遠に減らず、むしろどんどん増えていく（無限に存在する）のです。

📈 数字の成長スピード：「どれくらい速く増える？」

論文のもう一つの大きな成果は、この数列が**「どれくらい速く数字を大きくしていくか」**を計算したことです。

予想： 数列は「1, 2, 3...」のようにゆっくり増えるのか、それとも爆発的に増えるのか？
結果： 数列は**「多項式（べき乗）」のスピード**で増えることがわかりました。
- 具体的には、 $n$ 番目の数字は、 $n$ の約 1.66 乗（ $n^{1.66}$ ）くらいの大きさになります。
- これは「指数関数（$2^n $など）」ほど爆発的ではありませんが、単純な「$ n$（1 倍）」よりはかなり速く増えます。

イメージ：

理想（ $n$ ）： 1 歩ずつ歩く。
この数列： 1 歩歩くたびに、少しだけジャンプの幅を広げていく。
結果： 長い距離を走ると、理想の歩行者よりも遥か彼方にいることになります。その「遥か彼方」の分だけ、途中の数字（欠けた数字）が大量に存在していることになります。

🌟 まとめ：なぜこれがすごいのか？

長年の謎を解いた： 1970 年代から数学者たちが頭を悩ませてきた「欠けた数字は無限か？」という問いに、**「Yes（無限に欠ける）」**と答えました。
新しい視点： 単に「欠ける」だけでなく、「なぜ欠けるのか（2 のべき乗などの特殊な数字がルールに合わないから）」というメカニズムを、高度な数学（凸集合の差集合など）を使って説明しました。
将来への道： この数列が「多項式」のスピードで増えるという上限を初めて示したことで、今後の研究の基準ができました。

一言で言うと：
「この数字のゲームは、一見すると数字を埋め尽くしているように見えますが、実は**『2 のべき乗』などの特殊な数字を避けるように動いており、その結果、無限に数字の穴（欠落）を作り出し続ける**という、驚くべき性質を持っていたのです！」

この発見は、数学の「数列」という分野において、非常に重要な一歩となりました。

Each language version is independently generated for its own context, not a direct translation.

以下は、Quanyu Tang 氏による論文「THE HOFSTADTER CONSECUTIVE-SUM SEQUENCE OMITS INFINITELY MANY POSITIVE INTEGERS（ホフスタッター連続和数列は無限に多くの正整数を省略する）」の技術的サマリーです。

1. 問題の背景と定義

ホフスタッター連続和数列（Hofstadter Consecutive-Sum Sequence）
この論文は、OEIS A005243 として知られる数列 $(a_n)_{n \ge 1}$ の漸近挙動に関する問題を取り扱っています。この数列は、以下の貪欲法（greedy process）によって定義されます。

初期値: $a_1 = 1, a_2 = 2$
漸化式: $k \ge 3$ に対して、 $a_k$ を「 $a_{k-1}$ より大きく、かつ数列の前の項の連続する 2 項以上の和として表せる最小の整数」として定義します。
$a_k = \sum_{i=p}^{q} a_i \quad (1 \le p \le q \le k-1, \ q-p \ge 1)$

研究課題（Problem 1.1）
ホフスタッター自身および関連文献（Bloom の Erdős 問題サイトなど）で提起された問題です。「この数列の漸近的な振る舞いはどのようなものか？」という問いです。
数値的には、この数列は「ほとんどすべての整数」を含んでいるように見えますが、4, 7, 9, 12, 13, 15, 20 といった整数は欠落しています。OEIS のコメント欄には「この数列は無限に多くの正整数を省略する」という予想（Conjecture 1.2）が記載されていましたが、証明されていませんでした。

2. 主要な貢献と結果

この論文は、上記の予想を完全に解決し、さらに定量的な上界も示すものです。

定性的結果（無限省略の証明）

定理 1.4 と系 1.5:
任意の有限な正整数の初期列（シード） $u$ に対して、定義される数列 $(a_n)$ において、差分 $b_n = a_n - n$ が最終的に単調増加し、かつ有界でない（発散する）ことを証明しました。

結果: $a_n = n + \omega(1)$ （ $n \to \infty$ で $a_n - n \to \infty$ ）。
帰結: 数列 $(a_n)$ は無限に多くの正整数を省略する。これにより OEIS A005243 の予想が解決されました。

定量的結果（多項式上界）

定理 1.6:
古典的な数列（初期値 1, 2）に対して、任意の $\varepsilon > 0$ に対して定数 $C_\varepsilon$ が存在し、以下の不等式が成り立つことを示しました。
$a_n \le C_\varepsilon n^{4175/2506 + \varepsilon}$
指数 $4175/2506 \approx 1.666 $は、数列が線形成長（$ O(n)$）よりも速く、指数関数的成長よりも遅い多項式成長であることを示しています。これは、この問題に対する最初の多項式上界の提供です。

3. 手法と証明の概要

3.1 定性的証明の手法（無限省略の証明）

証明は背理法を用いています。

仮定: $b_n = a_n - n$ が有界であると仮定します。
線形尾部の導出: $b_n$ が有界かつ単調増加（貪欲性から導かれる）であるため、ある $n_0$ 以降で $a_n = n + B$ （ $B$ は定数）となる線形尾部を持つことになります。
2 のべき乗の矛盾:
- 線形尾部を持つ場合、十分大きな $2^r$ が数列の項として現れる必要があります。
- 連続和の性質（2 のべき乗は連続する 2 項以上の正整数の和で表せない）と、線形尾部における和の構造を解析します。
- これにより、ある有限集合 $E$ に対して、方程式 $v^2 + v + E = 2^k$ が無限に多くの整数解 $(v, k)$ を持つことになります。
ディオファントス近似の適用:
- Schinzel と Tijdeman の定理（多項式 $P(x)$ に対して $y^k = P(x)$ が $k>2$ で有限個の解しか持たないという結果）を適用します。
- 上記の二次方程式は $P(v) = v^2+v+E$ と見なせるため、無限に多くの解を持つことは矛盾します。
- したがって、 $b_n$ は有界ではなく、無限に発散します。

3.2 定量的証明の手法（上界の導出）

古典的数列 $a_n$ の上界を導出するために、加法組合せ論（Additive Combinatorics）の手法を用いています。

代表可能整数の集合: $R_m$ を、最初の $m$ 項から作られる「連続する 2 項以上の和」の集合と定義します。貪欲性により、 $a_n$ は $R$ の要素を昇順に列挙したものであることが示されます。
凸集合と差分集合:
- 部分和 $s_m = \sum_{i=1}^m a_i$ の集合 $\mathcal{S}_m$ は「凸集合（consecutive differences が狭義単調増加）」であることが示されます。
- 連続和は、この部分和集合の差分集合 $\mathcal{S}_m - \mathcal{S}_m$ の要素として表現できます。
Bloom の定理の適用:
- Bloom (2023) による有限凸集合 $A$ に対する差分集合のサイズに関する下限 $|A-A| \ge c |A|^{6681/4175 - \eta}$ を利用します。
- これにより、 $m$ 項までの間に生成される代表可能整数の個数 $|R_m|$ が $m^\delta$ （ $\delta > 1$ ）のオーダーで増加することが示されます。
再帰的評価:
- $|R_m|$ の増加率と貪欲な列挙の性質を組み合わせ、 $a_n$ に関する再帰的不等式 $a_n \le C n^\alpha a_{\lceil C n^\alpha \rceil}$ を導出します（ここで $\alpha = 1/\delta$ ）。
- この再帰式を反復適用し、対数因子を吸収することで、最終的な多項式上界 $n^{1/(\delta-1)}$ を得ます。計算結果、指数は $4175/2506$ となります。

4. 意義と今後の展望

予想の解決: 長年未解決だった「ホフスタッター連続和数列が無限に多くの整数を省略する」という予想を、より一般的な初期値条件付きで証明しました。
成長率の特定: 数列が線形成長（ $O(n)$ ）ではなく、 $n + \omega(1)$ であることを示しました。また、上界が $O(n^{1.666})$ であることを示し、多項式成長であることを確認しました。
ギャップと未解決:
- 定性的な下限（ $n + \omega(1)$ ）と定量的な上界（ $n^{1.666}$ ）の間には大きなギャップがあります。
- 数値実験（ $n$ まで 30,000 項の計算）では、欠落する整数の数 $b_n$ が $n^{1/3}$ 程度のオーダーで増加している可能性が示唆されています（$1/5 < \alpha < 1/2$）。
- 凸集合の差分集合に関する「 $|A-A| \gg |A|^{2-o(1)}$ 」という Erdős-Hegyvári の予想が真であれば、上界は $n^{1+o(1)}$ まで改善可能ですが、それでも $O(n)$ よりも大きいことは現時点では示せていません。

この論文は、数論と加法組合せ論を巧みに組み合わせて、非自明な再帰的数列の構造を解明した重要な成果です。