🔢 mathematics

Restricted partition functions and additive complements

本論文は、すべての正の整数が少なくとも一つの表現を持つことを保証しつつ、多項式的な成長を示す制限付き分割関数をもたらす正の整数の無限集合を構成することにより、DaiとChenによる2016年の問いに肯定的な回答を与えるものである。

原著者： Yuchen Ding

公開日 2026-06-17

📖 1 分で読めます🧠 じっくり読む

原著者： Yuchen Ding

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

想像してみてください。あなたの手元には、特別な積み木が入った、無限に続く巨大な道具箱があります。それぞれの積み木のサイズは、「集合A」と呼ばれるリスト内の数値によって決まっています。そして、あなたは「集合M」という特別なルールブックを持っており、そこには各積み木をいくつまで使えるかというルールが書かれています。

数学者であるユチェン・ディン（Yuchen Ding）は、非常に具体的な問いを投げかけています。「これら2つのリスト（AとM）を設計することで、すべての正の整数（1, 2, 3...）を作ることができる一方で、その作り方の数が制御不能にならないようにすることは可能だろうか？」

以下に、日常的な例えを用いた概念の解説をまとめます。

1. 積み木（制限付き分割）

数値 $n$ （例えば100）を、あなたが作りたい「塔」だと考えてください。

集合A は、利用可能な積み木のサイズのリストです（例：1, 4, 16, 256...）。
集合M は、「倍数」に関するルールブックです。これは、「4のサイズのブロックは0個、1個、または2個まで使ってよい。しかし、16のサイズのブロックについては、0個、5個、または10個といった具合である」といったルールを定めます。
目標： これらのルールに従って、あらゆる数 $n$ を作れるようにしたいと考えています。
問題点： もし同じ数を作る方法があまりに多すぎると、数学的に扱いが難しくなります。著者は、任意の数（ $p$ ）を作る方法の数が緩やかに増えること、具体的には「多項式成長（polynomial growth）」であることを証明したいと考えています。

例え： クッキーを焼いている場面を想像してください。

もし、チョコチップクッキーのレシピが100通りあったとしたら、管理するのは大変な作業です。
「多項式成長」とは、より大きなバッチのクッキーを作ろうとしても、新しいユニークなレシピが爆発的に増えるのではなく、管理可能で予測可能なペースで増えていくことを意味します。

2. 「ギャップ（隙間）」の問題

この論文以前、数学者たちは、すべての数を作ることができるリストを作る方法は知っていました。しかし、それらのリストにおける積み木のサイズの「ギャップ」は、それほど大きくありませんでした。

問い： 積み木のサイズが劇的に大きくなっていくようなリストを作れるだろうか？例えば、最初のブロックがサイズ1、次が100、その次が10,000、その次が1,000,000というようなリストです。
これらの数字の間のギャップは非常に広いため、通常であれば数学的な仕組みが破綻し、すべての数を作ることが不可能になるか、あるいはレシピの数が爆発的に増えてしまいます。

3. 解決策：「完璧なペア」

ディンは、答えは「YES」であることを証明しました。これら巨大なギャップが存在しながらも、すべての数を作り、かつ管理可能な数のレシピで済ませることは可能です。

彼は、**「加法的補数（Additive Complements）」**を用いた巧妙なトリックを導入することで、これを実現しました。

メタファー： チームBとチームSがいると想像してください。
- チームBのメンバーは、2の累乗（1, 2, 4, 8, 16...）です。
- チームSは、チームBが残した「穴」を埋めるための特別なグループです。
- この両者を組み合わせると、チームBから一人、チームSから一人を選んでその「値」を足し合わせることで、数直線上のすべての数を作ることができます。彼らは「補数」の関係にあります。

ディンは、数学者ルサ（Ruzsa）による有名な結果を用いて、興味深いほど疎（スパース）でありながら、隙間を埋めるのに十分な密度を持つチームSを見つけ出しました。

4. 構築の仕組み

ディンは、これら2つの魔法のリスト、A と M を、これらのチームに基づいて作成します。

集合A（積み木）： 彼はチームBの数値を取り、それを2の累乗（例： $2^1, 2^2, 2^4, 2^8...$ ）へと変換します。これにより、問いで求められた「巨大なギャップ」が生まれます。
集合M（ルール）： 彼はチームSに基づいてルールを作成します。このルールにより、チームSの小さな断片を組み合わせて係数（「いくつ使うか」の部分）を作ることが可能になります。

魔法の正体： チームBとチームSが完璧な補数関係にあるため、どんな数でも、これらの特定のルールに適合する和へと分解することができます。また、チームSは慎重に選ばれているため、その方法の数が爆発することなく、「多項式」の範囲内（管理可能な成長率）に収まるのです。

5. なぜこれが重要なのか（論文による説明）

この論文は、2016年にダイ（Dai）とチェン（Chen）によって提起された特定の問いに答えるものです。

問い： 「積み木の間の間隔が無限に広がっていく場合でも、なお、管理可能な組み合わせ数ですべての数を作ることができる、2つの無限集合は存在するのか？」
答え： はい。ディンは、ブロック間のギャップが非常に速く広がり、その対数の比が無限大に発散するようなケースにおいても、システムが完璧に機能する具体的な例を構築しました。

「AI」の要素について

著者であるユチェン・ディンは、研究プロセスにおいてAIツール（ChatGPT）を使用したことを公に述べています。

AIがしたこと： 2の累乗を含む集合を検討することを提案し、ラセナリー数列（lacunary sequences、大きな隙間を持つ数列）に関するルサの特定の定理へと彼を導きました。
著者がしたこと： 著者は数学的な検証、論理のチェック、証明の再構成、および最終的な論文の執筆を行いました。彼は、その正確性について全責任を負っています。

まとめ

ユチェン・ディンは、数を作るためのパズルを解きました。彼は、積み木の間の間隔が信じられないほど離れていても（まるで梯子の横桟の間隔がどんどん広がっていくような梯子のように）、そしてそれらを使うためのルールがあれば、以下のことが可能であることを示しました。

すべての整数を作ることができる。
それを作る方法の数が制御不能にならない。

これは、たとえ梯子の横桟の間隔が1マイル（約1.6km）離れていたとしても、特定の管理可能なクライミング技術を使えば、スムーズに登ることができ、転落することもない、ということを証明したようなものです。

技術的要約：制限付き分割関数と加法的補数

問題提起
本論文は、制限付き分割関数に関する加法的数論における特定の問いを扱っている。 $\mathbb{N}$ を正の整数の集合、 $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ とする。部分集合 $A, M \subseteq \mathbb{N}$ に対して、制限付き分割関数 $p(n, A, M)$ は、以下の形式による整数 $n$ の表現の数をカウントする：
$n = \sum_{a \in A} m_a a$
ここで、 $m_a \in M \cup \{0\}$ であり、すべての $a \in A$ に対して有限個の $m_a$ が非ゼロである。関数 $p$ が「多項式成長（polynomial growth）」を持つとは、定数 $c > 0$ と $n_0$ が存在し、すべての $n \geq n_0$ に対して $p(n, A, M) \leq n^c$ が成り立つことを指す。

DaiとChenによる2016年の問い（Question 1）は、以下の条件を満たす無限集合 $A = \{a_n\}_{n=1}^\infty$ と正の整数の集合 $M$ が存在するかどうかを問うものである：

集合 $A$ は極めて疎であり、 $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ を満たす。
すべての十分大きな $n$ に対して $p(n, A, M) > 0$ である（すなわち、すべての大きな整数が表現可能である）。
分割関数 $p(n, A, M)$ が多項式成長を示す。

Alon (2012) や Dai and Chen (2016) による先行研究では、より緩やかな疎性の条件や特定の指数境界（例： $p(n) < n^{2+o(1)}$ ）の下で、このような集合の存在が確立されていたが、超対数的な疎性（super-logarithmic sparsity）のケースは未解決のままであった。

手法
著者であるYuchen Dingは、加法的補数（additive complements）と二進展開に基づいた構成を用いている。核心となる戦略は以下の通りである：

加法的補数の定義： 2つの集合 $B, S \subseteq \mathbb{N}_0$ が「完全な加法的補数」であるとは、 $B + S = \mathbb{N}_0$ であることを指す。
集合 $A$ と $M$ の構成： 本論文では、特定の計数条件を満たす一対の加法的補数 $B$ $B$ と $S$ $S$ に基づいて $A$ $A$ と $M$ $M$ を構成する。具体的には：
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ （ $S$ からなる2のべき乗の有限部分和）
単射写像： 証明では、 $p(n, A, M)$ によってカウントされる表現から、積空間 $S \times B$ の有限部分集合への単射写像を確立する。二進展開の一意性を利用することで、任意の表現が $s+b \leq \log_2 n$ を満たすペア $(s, b)$ の集合に対応することを示す。
成長率の境界： これらの表現の数は、 $s+b \leq N$ （ここで $N \approx \log_2 n$ ）を満たすペア $(s, b) \in S \times B$ の数によって抑えられる。このカウントは $S(N)B(N)$ によって抑えられることが示される。もし $B(x)S(x) \ll x$ であれば、結果として得られる分割関数は多項式成長を示す。

主要な貢献と結果
本論文は、以下の結果を通じて、DaiとChenによるQuestion 1に対して肯定的な回答を与えるものである：

定理 1： $B$ と $S$ が計数条件 $B(x)S(x) \ll x$ を満たす完全な加法的補数であるとする。 $A$ と $M$ が上記のように定義されるとき、 $すべての n \in \mathbb{N}$ に対して $p(n, A, M) > 0$ であり、 $p(n, A, M)$ は多項式成長を持つ。
系 1（Question 1の解決）： 2のべき乗の加法的補数に関するRuzsa (1972) の結果を援用することで、著者は定理1を満たす具体的な集合 $A$ $A$ と $M$ $M$ を構成する。
- $B = \{0\} \cup \{2^k : k \geq 0\}$ とする。
- $S$ は、Ruzsaの定理から導かれた、 $S(x) \ll x / \log x$ かつ $B+S = \mathbb{N}_0$ （有限個の要素を加えた後）を満たす $\mathbb{N}$ の部分集合とする。
- この結果得られる集合 $A$ の要素は、 $n \geq 2$ に対して $a_n = 2^{2^{n-2}}$ となる。
- この構成により、 $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ が満たされ、極端な疎性の要件を満たす。
- また、 $B(x) \ll \log x$ および $S(x) \ll x / \log x$ であるため、積 $B(x)S(x) \ll x$ が成立し、これにより $p(n, A, M)$ の多項式成長が保証される。

意義
本論文は、2016年のDaiとChenによる問いに肯定的に答えたと主張している。これは、制限付き分割関数が全射的（すべての正の整数を表現できる）であり、かつ多項式成長を持つことが可能であることを示しており、その際、許容されるパーツの集合 $A$ は、既知の例よりも大幅に疎（具体的には、隣接する要素間の対数的間隔が $\log n$ のいかなる冪関数よりも速く成長するという条件を満たす）であっても実現可能であることを示している。

本研究は、制限付き分割関数の成長率を、加法的補数の計数特性に直接結びつけることで、先行研究の結果を一般化している。著者は、この構成が当初、生成AI（ChatGPT）の支援を受けて探索されたものであると述べている。AIは集合の具体的な形式やRuzsaの定理への関連性を提案したが、数学的な検証、再構成、および最終的な証明は、著者による独立した作業である。