Fix an integer k≥ 1. Let p_k,1(2,n) denote the number of partitions of the rectangle 2× n using the block-size restrictions indexed by k and 1 in the paper. A function f:N_0→N_0 is a quasi-polynomial if there is an integer s≥1 and polynomials q_0,…,q_s-1 such that f(n)=q_i(n) whenever n equiv i pmods; its degree is the maximum degree of these polynomials and its quasi-period is the least possible s. Quasi-polynomial conjecture. For any fixed integer k≥1, the function p_k,1(2,n) is a quasi-polynomial in n for sufficiently large n, of degree k-1 and with quasi-period dividing operatornamelcm(1,2,…,k). In particular, it has a rational generating function P(x)/Q(x) with P(x)∈Z[x] and Q(x)∈Z[x] dividing ∏_i=1^k(1-x^i). This is a conjectural structural description of the restricted rectangle-partition counts. The source gives no proof or resolution; the stated generating-function consequence is part of the conjecture.

Quasi-polynomial conjecture for restricted rectangle partitions p_{k,1}(2,n)

About 1 year old · traced to 2025

Fix an integer $k\geq 1$ . Let $p_{k,1}(2,n)$ denote the number of partitions of the rectangle $2\times n$ using the block-size restrictions indexed by $k$ and $1$ in the paper. A function $f:\mathbb{N}_0\to\mathbb{N}_0$ is a quasi-polynomial if there is an integer $s\geq1$ and polynomials $q_0,\ldots,q_{s-1}$ such that $f(n)=q_i(n)$ whenever $n\equiv i\pmod{s}$ ; its degree is the maximum degree of these polynomials and its quasi-period is the least possible $s$ . Quasi-polynomial conjecture. For any fixed integer $k\geq1$ , the function $p_{k,1}(2,n)$ is a quasi-polynomial in $n$ for sufficiently large $n$ , of degree $k-1$ and with quasi-period dividing $\operatorname{lcm}(1,2,\ldots,k)$ . In particular, it has a rational generating function $P(x)/Q(x)$ with $P(x)\in\mathbb{Z}[x]$ and $Q(x)\in\mathbb{Z}[x]$ dividing $\prod_{i=1}^{k}(1-x^i)$ .

This is a conjectural structural description of the restricted rectangle-partition counts. The source gives no proof or resolution; the stated generating-function consequence is part of the conjecture.

References

Primary source

Krystian Gajdzica, Robin Visser and Maciej Zakarczemny, “Rectangle partitions generalizing integer partitions”, arXiv:2509.20495 (2025).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Open

No public proof or disproof has appeared, and the proposed pattern remains an open conjecture.

The conjecture predicts that, for each fixed $k$ , these restricted rectangle-partition counts eventually follow repeating polynomial formulas of degree $k-1$ , with period controlled by $1,2,\ldots,k$ . It is recorded as Conjecture 5.10, not as a theorem.

Known results

Computations give conjectural formulas for $k\in\{4,5,6,7,8\}$ from the first several hundred values.
The corresponding statement for $p_{k,l}(2,n)$ with $k,l\geq2$ is proved only conditionally on Conjecture 5.10.
The broader counts satisfy an asymptotic estimate of order $n^{k+l-2}$ , but this does not establish eventual quasi-polynomiality.

2026 publication

The published article Rectangle Partitions Generalizing Integer Partitions repeats the conjecture and the computed cases, explicitly describing the larger cases as conjectural; it reports no proof, counterexample, verification, or retraction.

Current status (as of August 2026): The conjecture remains unresolved for general fixed $k$ ; only computational evidence and conditional consequences are recorded.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

Complete proof of Conjecture 5.10, with an all-parameter strengthening.

Let $p_{k,l}(2,n)$ denote the source's number of indistinguishable tile multisets admitting a tiling of a $2\times n$ rectangle. We prove that, for every $k,l\ge1$ , there exists $P_k(x)\in\mathbb Z[x]$ , independent of $l$ , such that

\boxed{ \sum_{n\ge0}p_{k,l}(2,n)x^n = \frac{P_k(x)} {\displaystyle \prod_{i=1}^{k}(1-x^i) \prod_{j=2}^{l}(1-x^j)}, \qquad P_k(1)=2^{k-1}. } \tag{1}

First consider $l=1$ , and encode a tile multiset by its multiplicities

c=(c_1,\ldots,c_k)\in\mathbb N^k

of the $1\times i$ tile types. If $c$ is feasible, its rectangle width satisfies

2n=\sum_{i=1}^k i c_i.

Appending two horizontal $1\times i$ tiles as a $2\times i$ end strip proves

c\text{ feasible}\quad\Longrightarrow\quad c+2e_i\text{ feasible}. \tag{2}

Write $c=\varepsilon+2t$ , with

\varepsilon\in\{0,1\}^k,\qquad t\in\mathbb N^k, \qquad E(\varepsilon)=\sum_{i=1}^k i\varepsilon_i.

Only even $E(\varepsilon)$ can occur. For each such parity vector, define

I_\varepsilon = \{t\in\mathbb N^k:\varepsilon+2t\text{ is feasible}\}.

By (2), $I_\varepsilon$ is upward closed. Dickson's lemma provides a finite set $M_\varepsilon$ of minimal generators:

I_\varepsilon= \bigcup_{u\in M_\varepsilon}(u+\mathbb N^k).

Finite inclusion-exclusion therefore gives

\sum_{t\in I_\varepsilon}x^{\sum_i i t_i} = \frac{H_\varepsilon(x)} {\prod_{i=1}^k(1-x^i)},

where

H_\varepsilon(x)= \sum_{\varnothing\ne J\subseteq M_\varepsilon} (-1)^{|J|+1} x^{\sum_{i=1}^k i\max_{u\in J}u_i} \in\mathbb Z[x].

Since

n=\frac{E(\varepsilon)}2+\sum_{i=1}^k i t_i,

summing over the even parity classes proves (1) for $l=1$ , with

P_k(x)= \sum_{\substack{\varepsilon\in\{0,1\}^k\E(\varepsilon)\ \mathrm{even}}} x^{E(\varepsilon)/2}H_\varepsilon(x).

Every even parity class is nonempty: take $t_1\ge E(\varepsilon)/2$ and $t_i=0$ for $i>1$ ; place the nonunit singleton tiles horizontally in one row and fill both rows with the $2t_1+\varepsilon_1$ available unit tiles. Thus $M_\varepsilon\ne\varnothing$ , and inclusion-exclusion gives

H_\varepsilon(1) = \sum_{\varnothing\ne J\subseteq M_\varepsilon} (-1)^{|J|+1} =1.

Exactly $2^{k-1}$ parity vectors have even $E$ , since toggling $\varepsilon_1$ reverses parity. Consequently

P_k(1)=2^{k-1}. \tag{3}

For general $l$ , the full-height $2\times j$ tiles, $2\le j\le l$ , contribute independent multiplicities. The source's decomposition therefore multiplies the $l=1$ generating function by

\prod_{j=2}^l(1-x^j)^{-1},

proving (1).

All poles in (1) are roots of unity of order dividing

\operatorname{lcm}(1,2,\ldots,\max\{k,l\}).

At $x=1$ , (3) yields

\sum_{n\ge0}p_{k,l}(2,n)x^n \sim \frac{2^{k-1}}{k!\,l!}(1-x)^{-(k+l-1)}.

Every other pole has smaller order. Hence $p_{k,l}(2,n)$ is eventually quasipolynomial of exact degree $k+l-2$ , with period dividing the displayed least common multiple, and

p_{k,l}(2,n) \sim \frac{2^{k-1}}{k!\,l!\,(k+l-2)!}\,n^{k+l-2}.

Taking $l=1$ proves every clause of Conjecture 5.10, including its precise denominator and degree. The general case additionally removes the assumption from Proposition 5.12 of Gajdzica–Visser–Zakarczemny, Annals of Combinatorics (2026).