🔢 mathematics

A note on the partition function of a rectangle

Cet article étudie le comportement asymptotique des fonctions de partition de rectangles, établissant que le nombre de façons de partitionner un carré $n \times n$ croît comme $\exp\left( \left(\frac{\pi}{\sqrt{3}}+o(1)\right)n\sqrt{\log n} \right)$ tandis que les partitions d'un rectangle $3 \times n$ croissent comme $\exp\left( \pi\sqrt{\frac{11n}{3}}+O(\log n) \right)$ .

Auteurs originaux : Krystian Gajdzica, Maciej Zakarczemny

Publié 2026-08-11

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Krystian Gajdzica, Maciej Zakarczemny

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un maître constructeur disposant d'un approvisionnement infini de briques Lego, mais avec une particularité : vous ne pouvez utiliser que des briques rectangulaires, et vous devez construire un mur parfait et solide sans aucun espace vide ni chevauchement. Maintenant, imaginez que vous avez le plan spécifique d'un mur qui est un carré parfait, disons de $n$ blocs de large et $n$ blocs de haut. La question que les mathématiciens adorent poser est la suivante : « De combien de façons différentes pouvez-vous disposer ces briques pour remplir ce carré ? » Il ne s'agit pas seulement d'empiler des éléments en ligne ; il s'agit de mélanger et d'associer différentes tailles — de minuscules carrés de $1\times1$ , de longues bandes de $1\times5$ , ou de gros blocs de $2\times3$ . Dans le monde des mathématiques, cela s'appelle une « partition », et compter ces arrangements revient à essayer de compter toutes les façons possibles de résoudre un puzzle géant et complexe.

Pendant longtemps, les mathématiciens ont été obsédés par le comptage de ces arrangements pour des nombres simples (comme l'addition d'entiers pour obtenir un total). Mais lorsque l'on passe d'une simple ligne de nombres à un rectangle en 2D, le problème explose en complexité. C'est comme passer de l'organisation de livres sur une seule étagère au remplissage d'une bibliothèque entière avec des livres de formes différentes. Ce papier spécifique explore deux versions très complexes de ce casse-tête : l'une où le plan est un carré parfait ( $n \times n$ ), et l'autre où le plan est un rectangle très long et mince ( $3 \times n$ ). Pourquoi cela importe-t-il ? Parce que ces motifs apparaissent partout dans la nature et la physique, de la façon dont les atomes se regroupent à la façon dont les niveaux d'énergie se comportent. Comprendre le « taux de croissance » de ces motifs — la vitesse à laquelle le nombre de possibilités grimpe en flèche à mesure que le mur s'agrandit — revient à trouver le code secret qui régit la façon dont la complexité se construit dans notre univers.

Alors, qu'ont réellement découvert les auteurs de ce papier ? Ils n'ont pas simplement deviné ; ils ont construit un pont mathématique rigoureux pour passer du connu à l'inconnu. D'abord, ils se sont attaqués au carré ( $n \times n$ ). Ils ont prouvé qu'à mesure que le carré devient immense, le nombre de façons de le paver croît selon un rythme très spécifique et sauvage. Ce n'est pas seulement une explosion simple ; c'est une croissance « super-exponentielle » qui dépend de la taille du carré multipliée par la racine carrée de son logarithme. En langage courant, ils ont trouvé que le nombre de façons de paver un carré est approximativement $e$ élevé à la puissance de $(\pi/\sqrt{3}) \times n \times \sqrt{\log n}$ . Ils ont également fourni des limites supérieures et inférieures plus simples, « suffisamment bonnes », pour montrer que leur réponse principale est solide, même si la formule exacte est un peu complexe.

Ensuite, ils se sont tournés vers le rectangle long et mince ( $3 \times n$ ). C'est une bête différente car un côté est fixé à 3 tandis que l'autre grandit indéfiniment. Ici, les auteurs ont trouvé une réponse encore plus précise. Ils ont prouvé que le nombre de façons de paver ce rectangle est approximativement $e$ élevé à la puissance de $\pi \times \sqrt{11n/3}$ . Il ne s'agit pas d'une simple supposition ou d'une simulation ; c'est un fait mathématiquement prouvé avec une marge d'erreur très étroite. Ils ont également montré qu'une hypothèse précédente, plus faible, concernant ce problème était trop imprécise, la remplaçant par une formule beaucoup plus nette et précise.

Pour obtenir ces réponses, les auteurs ont dû faire preuve de créativité. Pour le carré, ils ne pouvaient pas simplement compter chaque pavage (il y en a trop !). Au lieu de cela, ils ont utilisé une astuce ingénieuse : ils ont compté toutes les collections possibles de rectangles qui pourraient s'insérer dans la surface, même s'ils ne pouvaient pas réellement être disposés en un carré sans laisser de vides. Cela leur a donné un « plafond » (une limite supérieure). Ensuite, ils ont construit un « plancher » spécifique (une limite inférieure) en montrant qu'ils pouvaient certainement construire un nombre immense de carrés valides en utilisant une stratégie de remplissage spécifique. En encadrant la véritable réponse entre ce plancher et ce plafond, ils ont prouvé le taux de croissance exact. Pour le rectangle $3 \times n$ , ils ont utilisé une stratégie similaire mais ont dû diviser le rectangle en bandes plus petites et gérables, en utilisant des outils avancés de la théorie des « fonctions génératrices » (qui sont comme des formules magiques transformant les problèmes de comptage en problèmes d'algèbre) pour obtenir les chiffres précis.

Le papier aborde également un mystère plus vaste et non résolu. Les auteurs suggèrent que pour un rectangle de taille $m \times n$ (où $m$ est un nombre fixe comme 4 ou 5 et $n$ devient immense), il pourrait y avoir un modèle universel de croissance pour ces nombres. Ils ont des preuves solides pour $m=1, 2$ et $3$, mais pour $m=4$ et plus, la réponse reste une question ouverte et fascinante. Ils ont même essayé de construire un « escalier » de rectangles pour résoudre le cas $4 \times n$ et cela a fonctionné, mais pour $5 \times n$ , cette même astuce a échoué, suggérant que les règles changent à mesure que le rectangle s'élargit.

En résumé, ce papier est un triomphe de précision. Il prend deux problèmes de comptage très difficiles — l'un pour les carrés et l'autre pour les longs rectangles — et les résout avec des formules exactes. Il indique précisément la vitesse à laquelle le nombre de possibilités croît à mesure que les formes s'agrandissent, remplaçant les suppositions vagues par des mathématiques rigoureuses et prouvées. Bien qu'ils n'aient pas résolu le problème pour chaque taille de rectangle possible, ils ont déchiffré le code pour les cas les plus intéressants et ont fourni une feuille de route pour ceux qui attendent encore d'être résolus.

Résumé Technique : Une Note sur la Fonction de Partition d'un Rectangle

Énoncé du Problème
Cet article étudie le comportement asymptotique de la fonction de partition de rectangle $p(m, n)$ , qui compte le nombre de façons de partitionner un rectangle de dimensions $m \times n$ en un multiensemble de blocs rectangulaires aux côtés entiers. Deux partitions sont considérées comme identiques si elles consistent dans le même multiensemble de types de blocs, où un bloc $a \times b$ est indiscernable d'un bloc $b \times a$ . L'arrangement géométrique des blocs est sans importance pour le décompte ; seul le multiensemble de types importe, à condition que les blocs puissent théoriquement paver la surface $m \times n$ .

Les auteurs se concentrent sur deux cas spécifiques :

Partitions carrées : $p(n, n)$ , où les deux dimensions tendent vers l'infini.
Rectangles à hauteur fixe : $p(3, n)$ , où la hauteur est fixée à 3 et la largeur $n$ tend vers l'infini.

Ces problèmes généralisent la fonction de partition entière classique $p(n)$ , qui correspond au cas $p(1, n)$ . Bien que le comportement asymptotique de $p(m, n)$ pour un $m$ fixé et un $n$ grand ait été conjecturé par les auteurs et Robin Visser comme suivant une forme spécifique impliquant les nombres harmoniques, le comportement précis pour le cas carré ( $m=n$ ) présente un défi asymptotique distinct.

Méthodologie
L'article emploie une combinaison de théorie analytique des nombres, de fonctions génératrices et de constructions de pavage combinatoires.

Bornes Supérieures via les Fonctions Génératrices : Les auteurs dérivent des bornes supérieures en relaxant la condition de pavage géométrique (condition 3 de la Définition 1.1). Ils considèrent le nombre de multiensembles de rectangles ayant une aire totale de $mn$, indépendamment de leur capacité à paver physiquement le rectangle. Cela est modélisé par des fonctions génératrices de la forme $\prod (1-x^{ab})^{-r(ab)}$ , où $r(ab)$ compte le nombre de types de rectangles ayant une aire $ab$.
- Pour $p(n, n)$ , ils comparent la fonction génératrice à celle des partitions en parties issues d'un multiensemble lié à la fonction diviseur $d(s)$ , en utilisant les résultats de Berndt, Robles, Zaharescu et Zeindler.
- Pour $p(3, n)$ , ils décomposent le problème en partitions impliquant des blocs de hauteur 3 et ceux sans hauteur 3, en utilisant la convolution de fonctions génératrices et le théorème tauberien d'Ingham (tel que raffiné par Bringmann Jennings–Shaffer et Mahlburg) pour extraire les coefficients asymptotiques.
Bornes Inférieures via les Constructions de Remplissage : Pour établir des bornes inférieures, les auteurs construisent des pavages spécifiques.
- Pour $p(n, n)$ , ils utilisent une approche de « partition colorée » combinée à un algorithme de remplissage glouton. Ils partitionnent le carré en bandes horizontales de hauteurs variables et les remplissent avec des rectangles dérivés de partitions entières restreintes.
- Pour $p(3, n)$ , ils emploient une construction en « escalier », divisant le rectangle $3 \times n$ en bandes horizontales de hauteurs 3, 2 et 1, et les remplissant avec des rectangles de hauteurs correspondantes dérivés de partitions entières à parties restreintes.
Analyse Asymptotique : Les preuves reposent fortement sur la formule asymptotique de Hardy–Ramanujan pour $p(n)$ , les propriétés de la fonction eta de Dedekind, et des estimations précises de sommes harmoniques et de fonctions diviseurs.

Contributions Principales et Résultats

Formule Asymptotique pour les Partitions Carrées ( $p(n, n)$ ) :
Les auteurs établissent le terme asymptotique principal pour la fonction de partition carrée :
$p(n, n) = \exp\left( \left(\frac{\pi}{\sqrt{3}} + o(1)\right) n \sqrt{\log n} \right)$
Ce résultat est significatif car il diffère de la forme conjecturée pour un $m$ fixé (qui croît en $\sqrt{n}$ ). Le cas carré croît en $n\sqrt{\log n}$ . L'article fournit également deux bornes supérieures élémentaires plus faibles et une borne inférieure simple pour illustrer la difficulté du problème avant de présenter la preuve principale.
Formule Asymptotique pour $p(3, n)$ :
L'article prouve le comportement asymptotique exact pour le rectangle $3 \times n$ :
$p(3, n) = \exp\left( \pi \sqrt{\frac{11n}{3}} + O(\log n) \right)$
Ceci confirme la conjecture pour $m=3$ avec un terme d'erreur plus fort ( $O(\log n)$ dans l'exposant) que ce qui était connu précédemment. La constante $\pi\sqrt{11/3}$ est dérivée de l'interaction entre les partitions en parties de taille $\ge 3$ et les types de blocs spécifiques autorisés dans la géométrie $3 \times n$ .
Bornes Supérieures Indépendantes :
Les auteurs présentent une borne supérieure indépendante pour $p(3, n)$ qui est plus faible que le résultat principal mais dérivée via une approche analytique différente, offrant une perspective alternative sur le problème.
Conjectures pour un $m$ Général :
Tout en prouvant le cas pour $m=3$ , les auteurs réitèrent leur conjecture pour un $m$ fixé $\ge 4$ :
$p(m, n) = \exp\left( \pi \sqrt{\frac{2m H_m}{3} n} + o(\sqrt{n}) \right)$
où $H_m$ est le $m$ -ième nombre harmonique. Ils notent que le cas carré ( $m=n$ ) demeure un problème distinct où les deux dimensions croissent.

Signification et Revendications
L'article prétend résoudre le comportement asymptotique logarithmique précis pour la fonction de partition carrée $p(n, n)$ , un problème resté ouvert malgré la connaissance des valeurs pour de petits $n$ . Les auteurs soulignent que le cas carré mène à un problème asymptotique fondamentalement différent par rapport aux rectangles à hauteur fixe, car les deux longueurs de côté tendent vers l'infini.

Pour le cas $3 \times n$ , l'article fournit la première preuve de la formule asymptotique avec un terme d'erreur rigoureux, confirmant les arguments heuristiques et les preuves numériques précédemment recueillis. Les auteurs notent modestement que bien que leur construction pour $p(4, n)$ s'aligne sur la conjecture, la construction en « escalier » utilisée pour $m=3$ et $m=4$ ne parvient pas à produire le terme exponentiel conjecturé pour $m=5$ , suggérant que des arrangements géométriques différents pourraient être nécessaires pour des hauteurs fixes plus élevées.

Ce travail contribue à la théorie plus large des partitions entières en étendant l'analyse asymptotique aux problèmes de partitions géométriques, comblant le fossé entre la théorie classique des partitions et les problèmes de pavage où l'ordre des blocs est sans importance.

Articles similaires