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)

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

1 week ago

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).

0 endorsements

Shivam Patel · 15 hours ago