Rectangle partitions when both sides grow

What Lean checks

The logarithmic asymptotic is proved uniformly for every w ≥ h as h → ∞, for literal integer-sided real-position tilings counted by block multiset. The real-to-grid bridge, cumulative partition asymptotic, both packing reservations, and exact leading constant are checked.

Let p(h,w)p(h,w) be the number of multisets of integer-sided rectangular blocks that tile an h×wh\times w rectangle with sides parallel to the axes. A block may be rotated, and different arrangements of the same multiset count once. All logarithms are natural.

Theorem. For integers h≤wh\le w, put N=hwN=hw and U=min(h,N1/4)U=\min(h,N^{1/4}). As h→∞h\to\infty, uniformly for all w≥hw\ge h,

logp(h,w)=(π2/3+o(1))NlogU.\log p(h,w)=(\pi\sqrt{2/3}+o(1))\sqrt{N\log U}.

This proves both growing-side assertions of Gajdzica and Zakarczemny’s Remark 5.9. Indeed 12logh≤logU≤14logN\frac12\log h\le\log U\le\frac14\log N, giving their lower and upper constants π/3\pi/\sqrt3 and π/6\pi/\sqrt6, respectively. If logw∼logh\log w\sim\log h, then logU∼12logh\log U\sim\frac12\log h and the lower bound is sharp. The theorem also identifies the leading logarithmic term at every intermediate aspect ratio. The two expressions for UU agree at w=h3w=h^3. Original conjecture, Remark 5.9

Upper bound

Every feasible multiset has total area NN and its blocks have smaller side at most hh. First, dropping the restriction on the smaller side gives the multiset count R(N)R(N) of Lemma 5.1 of the original paper. That lemma gives

logp(h,w)≤logR(N)≤(π/6+o(1))NlogN.\log p(h,w)\le \log R(N)\le(\pi/\sqrt6+o(1))\sqrt{N\log N}.

Second, overcount the block types by ordered pairs (a,b)(a,b) with 1≤a≤h1\le a\le h and b≥1b\ge1. For t>0t>0 the logarithm of their multiset generating function evaluated at e−te^{-t} is at most

∑a=1h∑k≥11k(etak−1)≤π2Hh6t,Hh=∑a=1h1a.\sum_{a=1}^{h}\sum_{k\ge1}\frac1{k(e^{tak}-1)} \le \frac{\pi^2 H_h}{6t}, \qquad H_h=\sum_{a=1}^h\frac1a.

Thus logp(h,w)≤tN+π2Hh/(6t)\log p(h,w)\le tN+\pi^2H_h/(6t). Minimizing gives π2NHh/3\pi\sqrt{2NH_h/3}, the explicit upper bound in the authors’ fixed-height paper. Taking the smaller of the two bounds and using Hh=logh+O(1)H_h=\log h+O(1) proves the required upper bound uniformly. Lemma 5.1 · Theorem 1.1

A packing lower bound

Write P(T)P(T) for the ordinary integer partition function and set μ(T)=⌈2TlogT⌉\mu(T)=\lceil2\sqrt{T}\log T\rceil. For all sufficiently large TT at least P(T)/2P(T)/2 partitions of TT have largest part at most μ(T)\mu(T) (Gajdzica–Zakarczemny, Lemma 5.4). From these partitions delete all parts below aa. Each resulting partition λ\lambda has total at most TT, with every part bb satisfying a≤b≤μ(T)a\le b\le\mu(T). It has at most (T+1)a−1(T+1)^{a-1} preimages, by recording the deleted multiplicities. Consequently there are at least P(T)/(2(T+1)a−1)P(T)/(2(T+1)^{a-1}) choices. The threshold on TT is absolute. Lemma 5.4

For each integer aa in a range II starting at a≥2a\ge2, reserve QaQ_a strips of height aa and integer width BaB_a, disjoint across all reservations. Let δ∈(0,1)\delta\in(0,1) and set Ta=⌊(1−δ)QaBa⌋T_a=\lfloor(1-\delta)Q_aB_a\rfloor. Suppose μ(Ta)≤δBa\mu(T_a)\le\delta B_a. Pick a partition λa\lambda_a as above and turn each part bb into a block a×ba\times b. Pack the blocks successively into the reserved strips, starting a new strip whenever the next block does not fit. Every abandoned strip contains width greater than Ba−μ(Ta)B_a-\mu(T_a), whereas the total width is at most Ta≤Qa(Ba−μ(Ta))T_a\le Q_a(B_a-\mu(T_a)). Thus the blocks fit, as in the authors’ Lemma 5.5. Use integer coordinates throughout and fill all unused cells of the board with unit squares.

This map into tile multisets is injective. Remove the unit squares and sort the remaining blocks by their smaller side. Since b≥a≥2b\ge a\ge2, the class with smaller side aa recovers exactly λa\lambda_a, including square blocks. Taking a logarithm gives

logp(h,w)≥∑a∈IlogP(Ta)−∑a∈I((a−1)log(Ta+1)+log2).\log p(h,w)\ge\sum_{a\in I}\log P(T_a) -\sum_{a\in I}\big((a-1)\log(T_a+1)+\log 2\big). \tag{1}

Two strip reservations

Put ℓ=logh\ell=\log h, a0=⌈ℓ2⌉a_0=\lceil\ell^2\rceil, δ=ℓ−1/2\delta=\ell^{-1/2}, and s=w/hs=w/h. Only sufficiently large hh is needed below. Define the upper endpoint MM, the range I=[a0,M]∩ℤI=[a_0,M]\cap\mathbb Z, and L=∑a∈I1/aL=\sum_{a\in I}1/a as follows.

If 1≤s≤ℓ81\le s\le\ell^8, take M=⌊h/ℓ2⌋M=\lfloor\sqrt h/\ell^2\rfloor. Then logU=12ℓ+O(logℓ)\log U=\frac12\ell+O(\log\ell) and L=logU+O(logℓ)L=\log U+O(\log\ell). Set

Qa=⌊hLa2⌋,Ba=w.Q_a=\left\lfloor\frac{h}{La^2}\right\rfloor,\qquad B_a=w .

The strips can be stacked because ∑aaQa≤h\sum_a aQ_a\le h. The argument of the floor is uniformly ≫ℓ3\gg\ell^3 even at a=Ma=M. Consequently

Ta=(1+o(1))NLa2T_a=(1+o(1))\,\frac{N}{La^2} \tag{2}

uniformly. Since Ta≤N/(La2)T_a\le N/(La^2) and logN=O(ℓ)\log N=O(\ell) here,

μ(Ta)w≪1w+h/wlogNaL=O(ℓ−3/2)=o(δ).\frac{\mu(T_a)}{w}\ll\frac{1}{w}+\frac{\sqrt{h/w}\,\log N}{a\sqrt L} =O(\ell^{-3/2})=o(\delta).

If s>ℓ8s>\ell^8, take M=⌊U/ℓ2⌋M=\lfloor U/\ell^2\rfloor. Again L=logU+O(logℓ)L=\log U+O(\log\ell), by the harmonic-sum estimate. Reserve side-by-side columns of integer widths BaB_a across the board, placing QaQ_a strips inside each column, with

Qa=⌊ha⌋,Ba=⌊wLa⌋.Q_a=\left\lfloor\frac{h}{a}\right\rfloor,\qquad B_a=\left\lfloor\frac{w}{La}\right\rfloor .

Indeed aQa≤haQ_a\le h and ∑aBa≤w\sum_a B_a\le w. Both arguments of the floors grow uniformly: h/a≥ℓ2h/a\ge\ell^2 and w/(La)≥sℓ2/Lw/(La)\ge s\ell^2/L. Hence (2) also holds here. In particular,

μ(Ta)Ba≪1Ba+LslogN.\frac{\mu(T_a)}{B_a} \ll \frac{1}{B_a}+\sqrt{\frac{L}{s}}\,\log N .

The first term is O(ℓ−9)O(\ell^{-9}). For the second, (2ℓ+logs)/s(2\ell+\log s)/\sqrt s decreases for s≥ℓ8s\ge\ell^8 once hh is large. Its value at ℓ8\ell^8 is O(ℓ−3)O(\ell^{-3}). Since L=O(ℓ)L=O(\ell) and logN=2ℓ+logs\log N=2\ell+\log s, the second term is O(ℓ−5/2)=o(δ)O(\ell^{-5/2})=o(\delta). This bound also covers widths growing faster than any power of hh.

Summation

In both constructions, L∼logUL\sim\log U, with logU≥ℓ/2\log U\ge\ell/2. Also M≤min(h,N1/4)/ℓ2M\le\min(h,N^{1/4})/\ell^2 in both cases. In particular M2≤N/ℓ4M^2\le\sqrt N/\ell^4. For sufficiently large hh, (2) gives Ta≥N/(2LM2)≥Nℓ4/(2L)T_a\ge N/(2LM^2)\ge\sqrt N\,\ell^4/(2L) for every aa. This lower bound tends to infinity uniformly. Moreover Ta/a2≥N/(2LM4)≥ℓ8/(2L)T_a/a^2\ge N/(2LM^4)\ge\ell^8/(2L), so a≤μ(Ta)a\le\mu(T_a) throughout the construction. The Hardy–Ramanujan formula logP(T)∼π2T/3\log P(T)\sim\pi\sqrt{2T/3} and (2) give

∑a∈IlogP(Ta)=(π2/3+o(1))N/L∑a∈I1a=(π2/3+o(1))NlogU.\sum_{a\in I}\log P(T_a) =(\pi\sqrt{2/3}+o(1))\sqrt{N/L}\sum_{a\in I}\frac1a =(\pi\sqrt{2/3}+o(1))\sqrt{N\log U}.

The subtracted quantity in (1) is O(M2log(N+1))=O(N/ℓ3)O(M^2\log(N+1))=O(\sqrt N/\ell^3). For N≤h4N\le h^4 use M2≤N/ℓ4M^2\le\sqrt N/\ell^4 and logN≤4ℓ\log N\le4\ell. For N>h4N>h^4 use M2≤h2/ℓ4M^2\le h^2/\ell^4 and the decrease of logx/x\log x/\sqrt x on x≥h4x\ge h^4. Thus the loss is negligible uniformly, completing the proof.

Scope and prior work

The square theorem, the unrestricted multiset upper bound, the partition truncation estimate, and the shelf-packing observation are due to Gajdzica and Zakarczemny. Their later paper also uses separate columns for different smaller sides to prove the fixed-height formula. The contribution here is the uniform choice of the active smaller-side range and the two reservations. They attain the better of the two known upper bounds for every sequence of rectangles whose shorter side tends to infinity. The result is an asymptotic for the logarithm. Square case and conjecture · Fixed-height theorem

A November 18, 2026 search by author, statement, aspect ratio, and citing paper found no prior proof of the growing-side conjecture. The fixed-height theorem, Shaikh’s bounded-bar theorem and a subsequent two-row result concern other regimes. The proof above is unrefereed and historical priority remains unconfirmed. Restricted bars · Two-row result

The finite verifier enumerates small instances of the two strip constructions, checks disjointness cell by cell, and recovers each input family from its unordered tile multiset. The limiting estimates follow from the proof above.