🔢 mathematics

A note on the partition function of a rectangle

Diese Arbeit untersucht das asymptotische Verhalten von Rechteck-Partitionen und stellt fest, dass die Anzahl der Möglichkeiten, ein $n \times n$ Quadrat zu partitionieren, als $\exp\left( \left(\frac{\pi}{\sqrt{3}}+o(1)\right)n\sqrt{\log n} \right)$ wächst, während Partitionen eines $3 \times n$ Rechtecks als $\exp\left( \pi\sqrt{\frac{11n}{3}}+O(\log n) \right)$ wachsen.

Ursprüngliche Autoren: Krystian Gajdzica, Maciej Zakarczemny

Veröffentlicht 2026-08-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Krystian Gajdzica, Maciej Zakarczemny

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 sind ein Meisterbaumeister mit einem unendlichen Vorrat an Lego-Steinen, aber mit einer Besonderheit: Sie dürfen nur rechteckige Steine verwenden, und Sie müssen eine perfekte, solide Wand ohne Lücken oder Überlappungen bauen. Stellen Sie sich nun vor, Sie haben einen spezifischen Bauplan für eine Wand, die ein perfektes Quadrat ist, sagen wir $n$ Blöcke breit und $n$ Blöcke hoch. Die Frage, die Mathematiker lieben, lautet: „Auf wie viele verschiedene Arten kann man diese Steine anordnen, um das Quadrat zu füllen?“ Das ist nicht nur das Stapeln in einer Linie; es geht darum, verschiedene Größen zu mischen und zu kombinieren – winzige $1\times1$ -Quadrate, lange $1\times5$ -Streifen oder klobige $2\times3$ -Blöcke. In der Welt der Mathematik wird dies als „Partition“ bezeichnet, und das Zählen dieser Anordnungen ist wie der Versuch, jeden möglichen Weg zu zählen, ein riesiges, komplexes Puzzle zu lösen.

Lange Zeit waren Mathematiker besessen davon, diese Anordnungen für einfache Zahlen zu zählen (wie etwa das einfache Aufsummieren von ganzen Zahlen, um eine Gesamtsumme zu erhalten). Aber wenn man von einer flachen Linie von Zahlen zu einem 2D-Rechteck übergeht, explodiert die Komplexität des Problems. Es ist, als würde man vom Anordnen von Büchern auf einem einzelnen Regal zum Füllen einer ganzen Bibliothek mit Büchern verschiedener Formen übergehen. Diese spezifische Arbeit vertieft sich in zwei sehr knifflige Versionen dieses Puzzles: eine, bei der der Bauplan ein perfektes Quadrat ( $n \times n$ ) ist, und eine andere, bei der der Bauplan ein sehr langes, schmales Rechteck ( $3 \times n$ ) ist. Warum ist das wichtig? Weil diese Muster überall in der Natur und der Physik auftauchen, von der Art und Weise, wie Atome sich zusammenlagern, bis hin zum Verhalten von Energieniveaus. Das Verständnis der „Wachstumsrate“ dieser Muster – wie schnell die Anzahl der Möglichkeiten explodiert, wenn die Wand größer wird – ist wie das Finden des geheimen Codes, der bestimmt, wie Komplexität in unserem Universum entsteht.

Was haben die Autoren dieser Arbeit also tatsächlich entdeckt? Sie haben nicht einfach nur geraten; sie haben eine rigorose mathematische Brücke gebaut, um vom Bekannten zum Unbekannten überzuge-queren. Zuer das befassten sie sich mit dem Quadrat ( $n \times n$ ). Sie bewiesen, dass die Anzahl der Möglichkeiten, dieses Quadrat zu füllen, mit einer ganz bestimmten, wilden Rate wächst, wenn das Quadrat riesig wird. Es ist nicht nur eine einfache Explosion; es ist ein „super-exponentielles“ Wachstum, das von der Größe des Quadrats multipliziert mit der Quadratwurzel seines Logarithmus abhängt. In einfachen Worten haben sie herausgefunden, dass die Anzahl der Möglichkeiten, ein Quadrat zu füllen, etwa $e$ hoch der Potenz von $(\pi/\sqrt{3}) \times n \times \sqrt{\log n}$ ist. Sie lieferten auch einfachere, „gut genuge“ obere und untere Grenzwerte, um zu zeigen, dass ihre Hauptantwort solide ist, selbst wenn die exakte Formel etwas komplex ist.

Dann wandten sie sich dem langen, schmalen Rechteck ( $3 \times n$ ) zu. Dies ist ein anderes Kaliber, da eine Seite fest auf 3 fixiert ist, während die andere unendlich wächst. Hier fanden die Autoren eine noch präzisere Antwort. Sie bewiesen, dass die Anzahl der Möglichkeiten, dieses Rechteck zu füllen, etwa $e$ hoch der Potenz von $\pi \times \sqrt{11n/3}$ ist. Dies ist keine bloße Vermutung oder Simulation; es ist eine mathematisch bewiesene Tatsache mit einer sehr engen Fehlermarge. Sie zeigten auch, dass eine frühere, schwächere Vermutung über dieses Problem zu vage war, und ersetzten sie durch eine viel schärfere, genauere Formel.

Um diese Antworten zu erhalten, mussten die Autoren kreativ werden. Für das Quadrat konnten sie nicht einfach jede einzelne Kachelung zählen (da gibt es zu viele!). Stattdessen verwendeten sie einen cleveren Trick: Sie zählten alle möglichen Sammlungen von Rechtecken, die die Fläche theoretisch füllen könnten, selbst wenn sie sich nicht tatsächlich ohne Lücken zu einem Quadrat anordnen ließen. Dies gab ihnen eine „Decke“ (eine obere Grenze). Dann bauten sie ein spezifisches „Fundament“ (eine untere Grenze), indem sie zeigten, dass sie definitiv eine riesige Anzahl gültiger Quadrate mit einer spezifischen Packstrategie konstruieren konnten. Indem sie die wahre Antwort zwischen diesem Fundament und dieser Decke einschnürten, bewiesen sie die exakte Wachstumsrate. Für das $3 \times n$ Rechteck verwendeten sie eine ähnliche Strategie, mussten das Rechteck jedoch in kleinere, handhabbare Streifen zerlegen und nutzten fortgeschrittene Werkzeuge aus der Theorie der „erzeugenden Funktionen“ (welche wie magische Formeln sind, die Zählprobleme in Algebra verwandeln), um die präzisen Zahlen zu erhalten.

Die Arbeit berührt auch ein größeres, ungelöstes Rätsel. Die Autoren legen nahe, dass es für ein Rechteck der Größe $m \times n$ (wobei $m$ eine feste Zahl wie 4 oder 5 ist und $n$ unendlich groß wird) ein universelles Muster geben könnte, wie diese Zahlen wachsen. Sie haben starke Belege für $m=1, 2$ und $3$, aber für $m=4$ und höher bleibt die Antwort eine faszinierende offene Frage. Sie versuchten sogar, eine „Treppe“ aus Rechtecken zu bauen, um den Fall $4 \times n$ zu lösen, und es funktionierte, aber für $5 \times n$ versagte derselbe Trick, was darauf hindeutet, dass sich die Regeln ändern, sobald das Rechteck breiter wird.

Kurz gesagt ist diese Arbeit ein Triumph der Präzision. Sie nimmt zwei sehr schwierige Zählprobleme auf – eines für Quadrate und eines für lange Rechtecke – und löst sie mit exakten Formeln. Sie sagt uns genau, wie schnell die Anzahl der Möglichkeiten wächst, wenn die Formen größer werden, und ersetzt vage Vermutungen durch harte, bewiesene Mathematik. Obwohl sie das Problem nicht für jede mögliche Rechteckgröße gelöst haben, haben sie den Code für die interessantesten Fälle geknackt und eine Roadmap für die Fälle bereitgestellt, die noch auf ihre Lösung warten.

Technisches Resümee: Eine Notiz zur Partitionsfunktion eines Rechtecks

Problemstellung
Diese Arbeit untersucht das asymptotische Verhalten der Rechteck-Partitionsfunktion $p(m, n)$ , welche die Anzahl der Möglichkeiten zählt, ein Rechteck der Größe $m \times n$ in eine Multimenge von ganzzahligen rechteckigen Blöcken zu partitionieren. Zwei Partitionen gelten als identisch, wenn sie aus derselben Multimenge von Typen bestehen, wobei ein Block $a \times b$ ununterscheidbar von $b \times a$ ist. Die geometrische Anordnung der Blöcke ist für die Zählung irrelevant; nur die Multimenge der Typen zählt, vorausgesetzt, dass die Blöcke theoretisch die Fläche $m \times n$ füllen können.

Die Autoren untersuchen zwei spezifische Fälle:

Quadratische Partitionen: $p(n, n)$ , wobei beide Dimensionen gegen Unendlich gehen.
Rechtecke mit fester Höhe: $p(3, n)$ , wobei die Höhe fest bei 3 liegt und die Breite $n$ gegen Unendlich geht.

Diese Probleme verallgemeinern die klassische Ganzzahl-Partitionsfunktion $p(n)$ , die dem Fall $p(1, n)$ entspricht. Während das asymptotische Verhalten von $p(m, n)$ für ein festes $m$ und großes $n$ von den Autoren und Robin Visser unter Verwendung einer spezifischen Form unter Einbeziehung von harmonischen Zahlen vermutet wurde, stellt das präzise Verhalten für den quadratischen Fall ( $m=n$ ) eine eigenständige asymptotische Herausforderung dar.

Methodik
Die Arbeit verwendet eine Kombination aus analytischer Zahlentheorie, Erzeugungsfunktionen und kombinatorischen Packungskonstruktionen.

Obere Schranken mittels Erzeugungsfunktionen: Die Autoren leiten obere Schranken ab, indem sie die geometrische Tiling-Bedingung (Bedingung 3 in Definition 1.1) lockern. Sie betrachten die Anzahl der Multimengen von Rechtecken mit der Gesamtfläche $mn$, unabhängig davon, ob diese das Rechteck physisch füllen können. Dies wird durch Erzeugungsfunktionen der Form $\prod (1-x^{ab})^{-r(ab)}$ modelliert, wobei $r(ab)$ die Anzahl der Rechtecktypen mit der Fläche $ab$ zählt.
- Für $p(n, n)$ vergleichen sie die Erzeugungsfunktion mit der von Partitionen in Teile aus einer Multimenge, die mit der Divisorfunktion $d(s)$ verwandt ist, unter Verwendung von Ergebnissen von Berndt, Robles, Zaharescu und Zeindler.
- Für $p(3, n)$ zerlegen sie das Problem in Partitionen, die Blöcke der Höhe 3 enthalten, und solche, die keine enthalten, unter Verwendung der Faltung von Erzeugungsfunktionen und Inghams Tauber-Theorem (verfeinert durch Bringmann Jennings–Shaffer und Mahlburg), um asymptotische Koeffizienten zu extrahieren.
Untere Schranken mittels Packungskonstruktionen: Um untere Schranken zu etablieren, konstruieren die Autoren spezifische Tilings.
- Für $p(n, n)$ nutzen sie einen „farbigen Partition“-Ansatz kombiniert mit einem gierigen (greedy) Packalgorithmus. Sie partitionieren das Quadrat in horizontale Streifen variierender Höhen und füllen diese mit Rechtecken, die aus eingeschränkten Ganzzahl-Partitionen abgeleitet sind.
- Für $p(3, n)$ verwenden sie eine „Treppenstufen“-Konstruktion (staircase construction), die das $3 \times n$ Rechteck in horizontale Streifen der Höhen 3, 2 und 1 unterteilt und diese mit Rechtecken der entsprechenden Höhen füllt, die aus Ganzzahl-Partitionen mit eingeschränkten Teilen abgeleitet sind.
Asymptotische Analyse: Die Beweise stützen sich stark auf die Hardy–Ramanujan-Asymptotikformel für $p(n)$ , Eigenschaften der Dedekindschen Eta-Funktion sowie präzise Abschätzungen von harmonischen Summen und Divisorfunktionen.

Wesentliche Beiträge und Ergebnisse

Asymptotische Formel für quadratische Partitionen ( $p(n, n)$ ):
Die Autoren etablieren den Hauptasymptotischen Term für die quadratische Partitionsfunktion:
$p(n, n) = \exp\left( \left(\frac{\pi}{\sqrt{3}} + o(1)\right) n \sqrt{\log n} \right)$
Dieses Ergebnis ist signifikant, da es sich von der vermuteten Form für ein festes $m$ (die mit $\sqrt{n}$ skaliert) unterscheidet. Der quadratische Fall skaliert als $n\sqrt{\log n}$ . Die Arbeit liefert zudem zwei schwächere, elementare obere Schranken und eine einfache untere Schranke, um die Schwierigkeit des Problems vor der Präsentation des Hauptbeweises zu illustrieren.
Asymptotische Formel für $p(3, n)$ :
Die Arbeit beweist das exakte asymptotische Verhalten für das $3 \times n$ Rechteck:
$p(3, n) = \exp\left( \pi \sqrt{\frac{11n}{3}} + O(\log n) \right)$
Dies bestätigt die Vermutung für $m=3$ mit einem stärkeren Fehlerterm ( $O(\log n)$ im Exponenten) als bisher bekannt. Die Konstante $\pi\sqrt{11/3}$ ergibt sich aus dem Zusammenspiel von Partitionen in Teile der Größe $\ge 3$ und den spezifischen Blocktypen, die in der $3 \times n$ Geometrie zulässig sind.
Unabhängige obere Schranken:
Die Autoren präsentieren eine unabhängige obere Schranke für $p(3, n)$ , die schwächer als das Hauptergebnis ist, aber über einen anderen analytischen Ansatz abgeleitet wurde und eine alternative Perspektive auf das Problem bietet.
Vermutungen für allgemeines $m$ :
Während sie den Fall für $m=3$ beweisen, wiederholen die Autoren ihre Vermutung für ein festes $m \ge 4$ :
$p(m, n) = \exp\left( \pi \sqrt{\frac{2m H_m}{3} n} + o(\sqrt{n}) \right)$
wobei $H_m$ die $m$ -te harmonische Zahl ist. Sie merken an, dass der quadratische Fall ( $m=n$ ) ein distinktes Problem bleibt, bei dem beide Dimensionen wachsen.

Bedeutung und Ansprüche
Die Arbeit beansprucht, das präzise logarithmische asymptotische Verhalten für die quadratische Partitionsfunktion $p(n, n)$ gelöst zu haben, ein Problem, das trotz bekannter Werte für kleine $n$ offen geblieben war. Die Autoren betonen, dass der quadratische Fall zu einem fundamental anderen asymptotischen Problem führt als Rechtecke mit fester Höhe, da beide Seitenlängen gegen Unendlich streben.

Für den Fall $3 \times n$ liefert die Arbeit den ersten Beweis der asymptotischen Formel mit einem rigorosen Fehlerterm und bestätigt damit die heuristischen Argumente und numerischen Evidenzen, die zuvor gesammelt wurden. Die Autoren merken bescheiden an, dass während ihre Konstruktion für $p(4, n)$ mit der Vermutung übereinstimmt, die für $m=3$ und $m=4$ verwendete „Treppenstufen“-Konstruktion nicht den vermuteten exponentiellen Term für $m=5$ liefert, was darauf hindeutet, dass für höhere feste Höhen andere geometrische Anordnungen erforderlich sein könnten.

Die Arbeit trägt zur breiteren Theorie der Ganzzahl-Partitionen bei, indem sie die asymptotische Analyse auf geometrische Partitionsprobleme erweitert und die Lücke zwischen klassischer Partitionstheorie und Tiling-Problemen schließt, bei denen die Reihenfolge der Blöcke irrelevant ist.

Mehr davon