🔢 mathematics

Restricted partition functions and additive complements

Diese Arbeit beantwortet positiv eine Frage von Dai und Chen aus dem Jahr 2016, indem sie unendliche Mengen positiver Ganzzahlen konstruiert, die eine eingeschränkte Partitionierungsfunktion mit polynomiellem Wachstum ergeben und gleichzeitig sicherstellen, dass jede positive Ganzzahl mindestens eine Darstellung besitzt.

Ursprüngliche Autoren: Yuchen Ding

Veröffentlicht 2026-06-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yuchen Ding

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie hätten einen riesigen, unendlichen Werkzeugkasten voller spezieller Bausteine. Jeder Block hat eine bestimmte Größe, die durch eine Zahl in einer Liste namens Menge A bestimmt wird. Sie haben außerdem ein spezielles Regelbuch namens Menge M, das Ihnen sagt, wie viele von jedem Block Sie verwenden dürfen.

Der Mathematiker in dieser Arbeit, Yuchen Ding, stellt eine sehr spezifische Frage: Können wir diese beiden Listen (A und M) so entwerfen, dass wir jede positive ganze Zahl (1, 2, 3 usw.) mit diesen Blöcken bauen können, ohne dass die Anzahl der Möglichkeiten, sie zu bauen, außer Kontrolle gerät?

Hier ist eine Aufschlüsselung der Konzepte unter Verwendung alltäglicher Analogien:

1. Die Bausteine (Restriktionierte Partitionen)

Stellen Sie sich die Zahl $n$ (wie 100) als einen Turm vor, den Sie bauen wollen.

Menge A ist Ihre Liste der verfügbaren Blockgrößen (z. B. 1, 4, 16, 256...).
Menge M ist Ihr Regelbuch für "Vielfache". Es besagt: "Sie können 0, 1 oder 2 des 4er-Blocks verwenden, aber vielleicht 0, 5 oder 10 des 16er-Blocks."
Das Ziel: Sie möchten in der Lage sein, jede Zahl $n$ mit diesen Regeln zu bauen.
Das Problem: Wenn Sie zu viele Möglichkeiten haben, dieselbe Zahl zu bauen, wird die Mathematik kompliziert. Der Autor möchte beweisen, dass die Anzahl der Möglichkeiten, jeden Turm ( $p$ ) zu bauen, langsam wächst – spezifisch mit "polynomialem Wachstum".

Die Analogie: Stellen Sie sich vor, Sie backen Kekse.

Wenn Sie 100 verschiedene Rezepte für einen Schokoladenkeksi haben, ist das viel Arbeit, um das im Blick zu behalten.
"Polynomiales Wachstum" bedeutet, dass während Sie versuchen, immer größere Chargen Kekse zu backen, die Anzahl der neuen, einzigartigen Rezepte, die Sie entdecken, nicht sofort in die Millionen explodiert. Es wächst in einem handhabbaren, vorhersehbaren Tempo.

2. Das "Lücken"-Problem

Vor dieser Arbeit wussten Mathematiker bereits, wie man Listen erstellt, in denen man jede Zahl bauen kann, aber die "Lücke" zwischen den Größen der Blöcke nicht riesig war.

Die Frage: Können wir eine Liste erstellen, in der die Blöcke massiv größer werden, und zwar sehr schnell? Stellen Sie sich eine Liste vor, in der der erste Block die Größe 1 hat, der nächste 100, der nächste 10.000 und der nächste 1.000.000.
Die Lücke zwischen diesen Zahlen ist so weit, dass die Mathematik normalerweise zusammenbricht, was es unmöglich macht, jede Zahl zu bauen, oder die Anzahl der Rezepte explodieren lässt.

3. Die Lösung: Das "Perfekte Paar"

Ding beweist, dass die Antwort JA lautet. Sie können diese massiven Lücken erzeugen und dennoch jede Zahl mit einer handhabbaren Anzahl an Rezepten bauen.

Er tut dies, indem er einen klugen Trick einführt, der auf additiven Komplementen basiert.

Die Metapher: Stellen Sie sich zwei Teams vor, Team B und Team S.
- Team B hat Mitglieder, die Zweierpotenzen sind (1, 2, 4, 8, 16...).
- Team S ist eine spezielle Gruppe von Zahlen, die die "Löcher" füllt, die Team B hinterlässt.
- Zusammen, wenn Sie eine Person von Team B und eine von Team S nehmen und deren "Werte" addieren, können Sie jede Zahl auf der Zahlenlinie bilden. Sie sind "Komplemente".

Ding verwendet ein berühmtes Ergebnis des Mathematikers Ruzsa, um ein Team S zu finden, das gerade spärlich genug ist, um interessant zu sein, aber dicht genug, um die Lücken zu füllen.

4. Wie die Konstruktion funktioniert

Ding erstellt seine zwei magischen Listen, A und M, basierend auf diesen Teams:

Menge A (Die Blöcke): Er nimmt die Zahlen aus Team B und verwandelt sie in Zweierpotenzen (z. B. $2^1, 2^2, 2^4, 2^8...$ ). Dies erzeugt die "massiven Lücken", die in der Frage gefordert sind.
Menge M (Die Regeln): Er erstellt Regeln basierend auf Team S. Die Regeln erlauben es Ihnen, kleine Stücke aus Team S zu kombinieren, um die Koeffizienten (das "Wie viele"-Teil) zu bilden.

Die Magie: Da Team B und Team S perfekte Komplemente sind, können Sie jede Zahl immer als eine Summe zerlegen, die in diese spezifischen Regeln passt. Da Team S sorgfältig ausgewählt wurde, explodiert die Anzahl der Möglichkeiten, dies zu tun, nicht; sie bleibt innerhalb eines "polynomialen" Limits (einer handhabbaren Wachstumsrate).

5. Warum dies wichtig ist (laut der Arbeit)

Diese Arbeit beantwortet eine spezifische Frage, die von Dai und Chen im Jahr 2016 gestellt wurde.

Die Frage: "Existieren zwei unendliche Mengen, bei denen die Blöcke unendlich weit auseinanderliegen, und dennoch können wir jede Zahl mit einer handhabbaren Anzahl an Kombinationen bauen?"
Die Antwort: Ja. Ding konstruierte ein spezifisches Beispiel, bei dem die Lücken zwischen den Blöcken so schnell wachsen, dass das Verhältnis ihrer Logarithmen gegen Unendlich geht, und das System dennoch perfekt funktioniert.

Ein Hinweis auf die "KI"-Zutat

Der Autor, Yuchen Ding, gibt offen an, dass er während des Forschungsprozesses ein KI-Tool (ChatGPT) verwendet hat.

Was die KI tat: Sie schlug vor, Mengen zu untersuchen, die Zweierpotenzen beinhalten, und wies ihn auf ein spezifisches Theorem von Ruzsa über "lakunäre Sequenzen" (Sequenzen mit großen Lücken) hin.
Was der Autor tat: Der Autor verifizierte die Mathematik, überprüfte die Logik, organisierte den Beweis neu und schrieb die endgültige Arbeit. Er trägt die volle Verantwortung für die Richtigkeit der Arbeit.

Zusammenfassung

Yuchen Ding hat ein Rätsel über das Bauen von Zahlen gelöst. Er hat gezeigt, dass man eine Menge von Bausteinen haben kann, die extrem weit voneinander entfernt liegen (wie eine Leiter mit Sprossen, die immer weiter auseinanderliegen), und ein Regelwerk für deren Verwendung, sodass:

Man jede ganze Zahl bauen kann.
Die Anzahl der Möglichkeiten, sie zu bauen, nicht außer Kontrolle gerät.

Es ist, als würde man beweisen, dass man eine Leiter mit Sprossen haben kann, die eine Meile auseinanderliegen, und man sie dennoch reibungslos erklimmen kann, indem man eine spezifische, handhabbare Menge an Klettertechniken verwendet.

Technisches Resümee: Restriktierte Partitionfunktionen und additive Komplemente

Problemstellung
Die Arbeit befasst sich mit einer spezifischen Frage der additiven Zahlentheorie bezüglich restriktierter Partitionfunktionen. Sei $\mathbb{N}$ die Menge der positiven ganzen Zahlen und $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ . Für Teilmengen $A, M \subseteq \mathbb{N}$ zählt die restriktierte Partitionfunktion $p(n, A, M)$ die Anzahl der Darstellungen einer ganzen Zahl $n$ in der Form:
$n = \sum_{a \in A} m_a a$
wobei $m_a \in M \cup \{0\}$ für alle $a \in A$ gilt und nur endlich viele $m_a$ ungleich Null sind. Die Funktion $p$ wird als polynomielles Wachstum bezeichnet, wenn es Konstanten $c > 0$ und $n_0$ gibt, sodass $p(n, A, M) \leq n^c$ für alle $n \geq n_0$ gilt.

Das zentrale Problem, das von Dai und Chen im Jahr 2016 aufgeworfen wurde (Frage 1), fragt, ob es zwei unendliche Mengen $A = \{a_n\}_{n=1}^\infty$ und $M$ aus positiven ganzen Zahlen gibt, sodass:

Die Menge $A$ extrem dünn besetzt ist, was die Bedingung $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ erfüllt.
$p(n, A, M) > 0$ für alle hinreichend großen $n$ gilt (d. h. jede große ganze Zahl ist darstellbar).
Die Partitionfunktion $p(n, A, M)$ ein polynomielles Wachstum aufweist.

Vorherige Arbeiten von Alon (2012) sowie Dai und Chen (2016) hatten die Existenz solcher Mengen mit polynomischem Wachstum unter weniger strengen Bedingungen der Dünnbesetztheit oder mit spezifischen Exponenten-Schranken (z. B. $p(n) < n^{2+o(1)}$ ) etabliert, aber der Fall der super-logarithmischen Dünnbesetztheit blieb offen.

Methodik
Der Autor, Yuchen Ding, verwendet eine Konstruktion, die auf additiven Komplementen und Binärentwicklungen basiert. Die Kernstrategie umfasst:

Definition additiver Komplemente: Zwei Mengen $B, S \subseteq \mathbb{N}_0$ werden als vollständige additive Komplemente bezeichnet, wenn $B + S = \mathbb{N}_0$ gilt.
Konstruktion der Mengen $A$ und $M$ : Die Arbeit konstruiert $A$ $A$ und $M$ $M$ basierend auf einem Paar additiver Komplemente $B$ $B$ und $S$ $S$ , die eine spezifische Zählbedingung erfüllen. Konkret:
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ (endliche Teilsummen von Zweierpotenzen aus $S$ ).
Injektive Abbildung: Der Beweis etabliert eine injektive Abbildung von den Darstellungen von $n$ , die durch $p(n, A, M)$ gezählt werden, auf endliche Teilmengen des Produktraums $S \times B$ . Durch Nutzung der Eindeutigkeit von Binärentwicklungen zeigt der Autor, dass jede Darstellung von $n$ einer Menge von Paaren $(s, b)$ entspricht, für die $s+b \leq \log_2 n$ gilt.
Abschätzung des Wachstums: Die Anzahl dieser Darstellungen wird durch die Anzahl der Paare $(s, b) \in S \times B$ mit $s+b \leq N$ (wobei $N \approx \log_2 n$ ) begrenzt. Diese Zählung wird gezeigt, dass durch $S(N)B(N)$ beschränkt ist. Wenn $B(x)S(x) \ll x$ gilt, weist die resultierende Partitionfunktion ein polynomielles Wachstum auf.

Wesentliche Beiträge und Ergebnisse
Die Arbeit liefert eine affirmative Antwort auf Frage 1 von Dai und Chen durch folgende Ergebnisse:

Theorem 1: Sei $B$ und $S$ zwei vollständige additive Komplemente, die die Zählbedingung $B(x)S(x) \ll x$ erfüllen. Wenn $A$ und $M$ wie oben definiert sind, dann ist $p(n, A, M) > 0$ für jedes $n \in \mathbb{N}$ und $p(n, A, M)$ weist polynomielles Wachstum auf.
Korollar 1 (Lösung von Frage 1): Durch Anwendung eines Ergebnisses von Ruzsa (1972) bezüglich additiver Komplemente von Zweierpotenzen konstruiert der Autor spezifische Mengen $A$ $A$ und $M$ $M$ , die die Bedingungen von Theorem 1 erfüllen.
- Sei $B = \{0\} \cup \{2^k : k \geq 0\}$ .
- $S$ ist eine Teilmenge von $\mathbb{N}$ , die aus Ruzsas Theorem abgeleitet wurde, sodass $S(x) \ll x / \log x$ und $B+S = \mathbb{N}_0$ (nach Hinzufügung endlich vieler Elemente).
- Die resultierende Menge $A$ hat Elemente $a_n = 2^{2^{n-2}}$ für $n \geq 2$ .
- Diese Konstruktion liefert $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ , was die Anforderung der extremen Dünnbesetztheit erfüllt.
- Da $B(x) \ll \log x$ und $S(x) \ll x / \log x$ , gilt das Produkt $B(x)S(x) \ll x$ , was das polynomielle Wachstum von $p(n, A, M)$ sicherstellt.

Bedeutung
Die Arbeit beansprucht, eine Frage von Dai und Chen aus dem Jahr 2016 positiv zu beantworten. Sie zeigt, dass es möglich ist, restriktierte Partitionfunktionen zu konstruieren, die surjektiv sind (alle positiven ganzen Zahlen darstellen) und ein polynomielles Wachstum aufweisen, selbst wenn die erlaubte Menge der Summanden $A$ deutlich dünner besetzt ist als in bisher bekannten Beispielen (speziell, indem sie eine Bedingung erfüllt, bei der die logarithmische Lücke zwischen aufeinanderfolgenden Elementen schneller wächst als jede Potenz von $\log n$ ).

Die Arbeit verallgemeinert frühere Ergebnisse, indem sie die Wachstumsrate restriktierter Partitionfunktionen direkt mit den Zähleigenschaften additiver Komplemente verknüpft. Der Autor merkt an, dass die Konstruktion ursprünglich mit Unterstützung generativer KI (ChatGPT) untersucht wurde, welche die spezifische Form der Mengen und die Verbindung zu Ruzsas Theorem vorschlug, wobei die mathematische Verifizierung, Reorganisation und der endgültige Beweis jedoch die unabhängige Arbeit des Autors sind.