🔢 mathematics

A note on the partition function of a rectangle

This paper investigates the asymptotic behavior of rectangle partition functions, establishing that the number of ways to partition an $n \times n$ square grows as $\exp\left( \left(\frac{\pi}{\sqrt{3}}+o(1)\right)n\sqrt{\log n} \right)$ while partitions of a $3 \times n$ rectangle grow as $\exp\left( \pi\sqrt{\frac{11n}{3}}+O(\log n) \right)$ .

Original authors: Krystian Gajdzica, Maciej Zakarczemny

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Krystian Gajdzica, Maciej Zakarczemny

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master builder with an infinite supply of Lego bricks, but with a twist: you can only use rectangular bricks, and you must build a perfect, solid wall without any gaps or overlaps. Now, imagine you have a specific blueprint for a wall that is a perfect square, say $n$ blocks wide and $n$ blocks tall. The question mathematicians love to ask is: "How many different ways can you arrange these bricks to fill that square?" This isn't just about stacking them in a line; it's about mixing and matching different sizes—tiny $1\times1$ squares, long $1\times5$ strips, or chunky $2\times3$ blocks. In the world of mathematics, this is called a "partition," and counting these arrangements is like trying to count every possible way to solve a giant, complex puzzle.

For a long time, mathematicians have been obsessed with counting these arrangements for simple numbers (like just adding up integers to get a total). But when you move from a flat line of numbers to a 2D rectangle, the problem explodes in complexity. It's like going from arranging books on a single shelf to filling an entire library with books of different shapes and sizes. This specific paper dives into two very tricky versions of this puzzle: one where the blueprint is a perfect square ( $n \times n$ ), and another where the blueprint is a very long, thin rectangle ( $3 \times n$ ). Why does this matter? Because these patterns show up everywhere in nature and physics, from how atoms pack together to how energy levels behave. Understanding the "growth rate" of these patterns—how fast the number of possibilities skyrockets as the wall gets bigger—is like finding the secret code that governs how complexity builds up in our universe.

So, what did the authors of this paper actually discover? They didn't just guess; they built a rigorous mathematical bridge to cross from the known to the unknown. First, they tackled the square ( $n \times n$ ). They proved that as the square gets huge, the number of ways to tile it grows at a very specific, wild rate. It's not just a simple explosion; it's a "super-exponential" growth that depends on the size of the square multiplied by the square root of its logarithm. In plain English, they found that the number of ways to tile a square is roughly $e$ raised to the power of $(\pi/\sqrt{3}) \times n \times \sqrt{\log n}$ . They also provided some simpler, "good enough" upper and lower limits to show that their main answer is solid, even if the exact formula is a bit complex.

Then, they turned their attention to the long, skinny rectangle ( $3 \times n$ ). This is a different beast because one side is fixed at 3 while the other grows forever. Here, the authors found an even more precise answer. They proved that the number of ways to tile this rectangle is roughly $e$ raised to the power of $\pi \times \sqrt{11n/3}$ . This isn't just a guess or a simulation; it is a mathematically proven fact with a very tight margin of error. They also showed that a previous, weaker guess about this problem was too loose, replacing it with a much sharper, more accurate formula.

To get these answers, the authors had to get creative. For the square, they couldn't just count every single tiling (there are too many!). Instead, they used a clever trick: they counted all possible collections of rectangles that could fit the area, even if they couldn't actually be arranged into a square without gaps. This gave them a "ceiling" (an upper limit). Then, they built a specific "floor" (a lower limit) by showing they could definitely construct a huge number of valid squares using a specific packing strategy. By squeezing the true answer between this floor and ceiling, they proved the exact growth rate. For the $3 \times n$ rectangle, they used a similar strategy but had to break the rectangle into smaller, manageable strips and use advanced tools from the theory of "generating functions" (which are like magic formulas that turn counting problems into algebra problems) to get the precise numbers.

The paper also touches on a bigger, unsolved mystery. The authors suggest that for a rectangle of size $m \times n$ (where $m$ is a fixed number like 4 or 5 and $n$ gets huge), there might be a universal pattern to how these numbers grow. They have strong evidence for $m=1, 2,$ and $3$, but for $m=4$ and higher, the answer remains a tantalizing open question. They even tried to build a "staircase" of rectangles to solve the $4 \times n$ case and it worked, but for $5 \times n$ , that same trick failed, hinting that the rules change as the rectangle gets wider.

In short, this paper is a triumph of precision. It takes two very hard counting problems—one for squares and one for long rectangles—and solves them with exact formulas. It tells us exactly how fast the number of possibilities grows as the shapes get larger, replacing vague guesses with hard, proven mathematics. While they didn't solve the problem for every possible rectangle size, they cracked the code for the most interesting cases and provided a roadmap for the ones that are still waiting to be solved.

Technical Summary: A Note on the Partition Function of a Rectangle

Problem Statement
This paper investigates the asymptotic behavior of the rectangle partition function $p(m, n)$ , which counts the number of ways to partition a rectangle of size $m \times n$ into a multiset of integer-sided rectangular blocks. Two partitions are considered identical if they consist of the same multiset of block types, where a block $a \times b$ is indistinguishable from $b \times a$ . The geometric arrangement of the blocks is irrelevant to the count; only the multiset of types matters, provided the blocks can theoretically tile the area $m \times n$ .

The authors focus on two specific cases:

Square partitions: $p(n, n)$ , where both dimensions tend to infinity.
Fixed-height rectangles: $p(3, n)$ , where the height is fixed at 3 and the width $n$ tends to infinity.

These problems generalize the classical integer partition function $p(n)$ , which corresponds to the case $p(1, n)$ . While the asymptotic behavior of $p(m, n)$ for fixed $m$ and large $n$ was conjectured by the authors and Robin Visser to follow a specific form involving harmonic numbers, the precise behavior for the square case ( $m=n$ ) presents a distinct asymptotic challenge.

Methodology
The paper employs a combination of analytic number theory, generating functions, and combinatorial packing constructions.

Upper Bounds via Generating Functions: The authors derive upper bounds by relaxing the geometric tiling condition (condition 3 in Definition 1.1). They consider the number of multisets of rectangles with total area $mn$ regardless of whether they can physically tile the rectangle. This is modeled using generating functions of the form $\prod (1-x^{ab})^{-r(ab)}$ , where $r(ab)$ counts the number of rectangle types with area $ab$.
- For $p(n, n)$ , they compare the generating function to that of partitions into parts from a multiset related to the divisor function $d(s)$ , utilizing results by Berndt, Robles, Zaharescu, and Zeindler.
- For $p(3, n)$ , they decompose the problem into partitions involving blocks of height 3 and those without, using convolution of generating functions and Ingham's Tauberian theorem (as refined by Bringmann Jennings–Shaffer and Mahlburg) to extract asymptotic coefficients.
Lower Bounds via Packing Constructions: To establish lower bounds, the authors construct specific tilings.
- For $p(n, n)$ , they utilize a "colored partition" approach combined with a greedy packing algorithm. They partition the square into horizontal strips of varying heights and fill them with rectangles derived from restricted integer partitions.
- For $p(3, n)$ , they employ a "staircase" construction, dividing the $3 \times n$ rectangle into horizontal strips of heights 3, 2, and 1, and filling them with rectangles of corresponding heights derived from integer partitions with restricted parts.
Asymptotic Analysis: The proofs rely heavily on the Hardy–Ramanujan asymptotic formula for $p(n)$ , properties of the Dedekind eta function, and precise estimates of harmonic sums and divisor functions.

Key Contributions and Results

Asymptotic Formula for Square Partitions ( $p(n, n)$ ):
The authors establish the main asymptotic term for the square partition function:
$p(n, n) = \exp\left( \left(\frac{\pi}{\sqrt{3}} + o(1)\right) n \sqrt{\log n} \right)$
This result is significant because it differs from the conjectured form for fixed $m$ (which scales as $\sqrt{n}$ ). The square case scales as $n\sqrt{\log n}$ . The paper also provides two weaker, elementary upper bounds and a simple lower bound to illustrate the problem's difficulty before presenting the main proof.
Asymptotic Formula for $p(3, n)$ :
The paper proves the exact asymptotic behavior for the $3 \times n$ rectangle:
$p(3, n) = \exp\left( \pi \sqrt{\frac{11n}{3}} + O(\log n) \right)$
This confirms the conjecture for $m=3$ with a stronger error term ( $O(\log n)$ in the exponent) than previously known. The constant $\pi\sqrt{11/3}$ is derived from the interplay of partitions into parts of size $\ge 3$ and specific block types allowed in the $3 \times n$ geometry.
Independent Upper Bounds:
The authors present an independent upper bound for $p(3, n)$ that is weaker than the main result but derived via a different analytic approach, offering an alternative perspective on the problem.
Conjectures for General $m$ :
While proving the case for $m=3$ , the authors reiterate their conjecture for fixed $m \ge 4$ :
$p(m, n) = \exp\left( \pi \sqrt{\frac{2m H_m}{3} n} + o(\sqrt{n}) \right)$
where $H_m$ is the $m$ -th harmonic number. They note that the square case ( $m=n$ ) remains a distinct problem where both dimensions grow.

Significance and Claims
The paper claims to resolve the precise logarithmic asymptotic behavior for the square partition function $p(n, n)$ , a problem that had remained open despite known values for small $n$ . The authors emphasize that the square case leads to a fundamentally different asymptotic problem compared to fixed-height rectangles, as both side lengths tend to infinity.

For the $3 \times n$ case, the paper provides the first proof of the asymptotic formula with a rigorous error term, confirming the heuristic arguments and numerical evidence previously gathered. The authors modestly note that while their construction for $p(4, n)$ aligns with the conjecture, the "staircase" construction used for $m=3$ and $m=4$ fails to yield the conjectured exponential term for $m=5$ , suggesting that different geometric arrangements may be required for higher fixed heights.

The work contributes to the broader theory of integer partitions by extending asymptotic analysis to geometric partition problems, bridging the gap between classical partition theory and tiling problems where the order of blocks is irrelevant.

More like this