No Perfect Mondrian Partition Has a Common Tile Area Supported on Two Primes
medium tier2026-10-26OP-2802 research-level results in one postreviewed by Claude Code中文版
Abstract
The Mondrian art problem asks for the minimum defect, the difference between the largest and smallest tile areas, over partitions of an $n \times n$ square into at least two pairwise noncongruent integer-sided rectangles. A partition is perfect if its defect is zero, and it is an open question, conjectured to have a negative answer, whether any square admits one. We prove that for distinct primes $p$ and $q$ and all exponents $s, t$, no perfect partition of any integer square has common tile area $q^s p^t$. Two consequences follow: no square whose side has at most two distinct prime factors admits a perfect partition, and in any perfect partition the common tile area has at least three distinct prime factors. The proof combines a congruence obtained from a moment identity over the rows of the square with the observation that the tiles of a perfect partition have pairwise distinct heights; together they force $q$ to divide both sides of every tile, after which the coordinates can be divided by $q$ and the exponent of $q$ in the area drops by two. Every result here is formalized and checked in Lean 4.
1. Introduction
The Mondrian art problem concerns partitions of an $n \times n$ square into axis-aligned rectangles with positive integer side lengths. To exclude trivial configurations such as identical parallel strips, the rectangles of an admissible partition are required to be pairwise noncongruent: no two share the same unordered pair of side lengths. The defect of a partition $P$ is $$\text{def}(P) = \max_{R \in P} |R| - \min_{R \in P} |R|,$$ and the Mondrian number $M(n)$ is the least defect over all admissible partitions of the $n \times n$ square into two or more rectangles.
A partition of defect zero is called perfect: its rectangles are pairwise noncongruent and yet all have the same area $A$, so that $kA = n^2$ when there are $k$ of them. As arXiv:2610.19193 recalls in Section 1, it is still an open problem whether $M(n) = 0$ for some $n$, though it is conjectured that no such $n$ exists. That paper also notes that a single perfect partition would give infinitely many, since scaling all sides by a common factor preserves the defect zero, and that perfect partitions have been excluded computationally for every $n \le 1000$ (arXiv:2311.02385). On the theoretical side, the prime-power case is classical: squares whose side is a prime power admit no perfect partition (arXiv:2007.09639, Theorem 4.1, by counting the available shapes), and density results show that a positive proportion of integers $n$ have $M(n) > 0$.
This post gives an obstruction that holds for every square at once and is phrased in terms of the common tile area rather than the side. The main theorem, mondrian_no_perfect_two_prime_area, states that for distinct primes $p$ and $q$ and arbitrary exponents $s$ and $t$, no perfect admissible partition of any integer square has all its tiles of area $q^s p^t$. It extends mondrian_no_perfect_prime_power_area, the same statement for a prime-power area $p^t$. Two corollaries are formalized:
mondrian_no_perfect_two_prime_powers: for distinct primes $p, q$ and all exponents $e, f$, the square of side $q^f p^e$ admits no perfect partition. Together with the prime-power case, this excludes every side length with at most two distinct prime factors, with no restriction on the exponents.mondrian_perfect_area_three_prime_factors: in any perfect partition of any square, the common tile area has at least three distinct prime factors.
An earlier, weaker result in the same development, mondrian_no_perfect_prime_mul_prime_pow, treated the sides $q p^e$ by a different route, counting the factor pairs of the area that fit in the square; it is the case $f = 1$ of the first corollary. The key new ingredient is a divisibility lemma: if the common area is $q^s p^t$ and $q$ divides $n$, then $q$ divides both side lengths of every tile. Its proof uses only a linear identity over the rows of the square, the distinctness of tile heights in a perfect partition, and the fact that the tile heights not divisible by $q$ form a chain under divisibility.
2. Preliminaries
We follow the conventions of the Lean formalization.
Definition 1 (mondrian_rect_width, mondrian_rect_height, mondrian_rect_area). A rectangle is a 4-tuple of natural numbers $r = (x_0, x_1, y_0, y_1)$ with lower-left corner $(x_0, y_0)$ and upper-right corner $(x_1, y_1)$. Its width is $x_1 - x_0$, its height is $y_1 - y_0$, and its area is their product.
Definition 2 (mondrian_is_partition). For a natural number $n$ and a list $P$ of rectangles, mondrian_is_partition n P holds when:
- $P$ has at least two elements;
- every $r \in P$ satisfies $x_0 < x_1$ and $y_0 < y_1$;
- distinct entries of $P$ have disjoint sets of unit cells and are not congruent, where two rectangles are congruent if they have the same width and height, or the width of each equals the height of the other;
- the union of the unit cells of the rectangles is exactly $\{0, \dots, n-1\} \times \{0, \dots, n-1\}$.
A unit cell is named by its lower-left corner, so condition 4 says that the tiles cover the canvas $[0,n] \times [0,n]$ and no tile leaves it.
Definition 3 (mondrian_defect). The defect of $P$ is the maximum of the tile areas minus their minimum (with the value 0 for an empty list). A partition is perfect if its defect is 0.
Two basic facts are used throughout. By mondrian_defect_zero_equal, all tiles of a list of defect zero have the same area. By mondrian_perfect_area_product, if $P$ is a perfect admissible partition of the $n$-square and $r \in P$, then $|P| \cdot \text{area}(r) = n^2$, since the tiles are cell-disjoint and cover the $n^2$ cells of the canvas.
3. Main result
Theorem (mondrian_no_perfect_two_prime_area). Let $p$ and $q$ be distinct primes and let $s, t, n \in \mathbb{N}$. There is no list $P$ of rectangles such that mondrian_is_partition n P, mondrian_defect P = 0, and every $r \in P$ has area $q^s p^t$.
The statement places no condition on $n$: it is an obstruction on the common tile area alone. The case $s = 0$ is mondrian_no_perfect_prime_power_area, which excludes a prime-power common area $p^t$ (including area 1).
Corollary 1 (mondrian_no_perfect_two_prime_powers). Let $p$ and $q$ be distinct primes and $e, f \in \mathbb{N}$. Then $\neg \exists P,\ \text{mondrian\_is\_partition}(q^f p^e, P) \wedge \text{mondrian\_defect}(P) = 0$.
Indeed, by mondrian_perfect_area_product the common area of a perfect partition divides $n^2 = q^{2f} p^{2e}$, so it has the form $q^s p^t$. Every integer $n \ge 2$ with at most two distinct prime factors has the form $q^f p^e$, so no such square has a perfect partition.
Corollary 2 (mondrian_perfect_area_three_prime_factors). If mondrian_is_partition n P, mondrian_defect P = 0 and $r \in P$, then the area of $r$ has at least three distinct prime factors.
Any hypothetical perfect partition must therefore have a tile area divisible by three distinct primes, and since the area divides $n^2$, its side $n$ must have at least three distinct prime factors as well. The smallest side lengths left open by these results are $30, 42, 60, 66, \dots$; all sides up to 1000 are excluded by the computation of arXiv:2311.02385, so the results here add the infinite family of two-prime sides and a structural restriction on the area of any counterexample.
theorem mondrian_no_perfect_two_prime_area (p q s t n : ℕ) (hp : Nat.Prime p)
(hq : Nat.Prime q) (hpq : p ≠ q) (P : List (ℕ × ℕ × ℕ × ℕ))
(hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0)
(harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) : False4. Proof
Throughout, $P$ is a perfect admissible partition of the $n \times n$ square; we write $w(r)$ and $h(r)$ for the width and height of $r \in P$, and $r = (x_0, x_1, y_0, y_1)$ for its coordinates.
Step 1 (distinct heights). Two distinct tiles of $P$ have distinct heights. If $h(r) = h(r')$, then since $w(r)h(r) = w(r')h(r')$ and heights are positive, also $w(r) = w(r')$, so $r$ and $r'$ are congruent, which admissibility forbids.
Step 2 (a moment identity over the rows). For every integer-valued function $f$ on the row levels $0, 1, \dots, n$, $$\sum_{r \in P} w(r)\,\bigl(f(y_1(r)) - f(y_0(r))\bigr) = n\,\bigl(f(n) - f(0)\bigr).$$ Writing $f(y_1) - f(y_0)$ as a telescoping sum over the rows $y_0 \le y < y_1$, the left side becomes $\sum_{y < n} (f(y+1) - f(y)) \sum_{r \ni y} w(r)$, and the widths of the tiles crossing any row $y$ add up to $n$ because the tiles partition that row of cells.
Step 3 (an isolated tile). Let $d \mid n$ and $m \ge 1$. Suppose $r \in P$ has $m \nmid h(r)$, and every other tile $r'$ has $d \mid w(r')$ or $m \mid h(r')$. Then $d \mid w(r)$. To see this, apply Step 2 to $f(y) = 1$ if $y \equiv y_1(r) \pmod m$ and $f(y) = 0$ otherwise. The right side is a multiple of $n$, hence of $d$. A tile $r'$ with $m \mid h(r')$ has $y_0(r') \equiv y_1(r') \pmod m$, so its increment of $f$ is 0; a tile with $d \mid w(r')$ contributes a multiple of $d$. For $r$ itself, $y_0(r) \not\equiv y_1(r) \pmod m$ because $m \nmid h(r)$, so its increment is exactly 1 and its term is $w(r)$. Reducing the identity modulo $d$ gives $d \mid w(r)$.
Step 4 (prime chains). Let $d \mid n$, let $p$ be prime and $C > 0$, and suppose every tile whose width is not divisible by $d$ has height of the form $C p^a$. Then every width is divisible by $d$. Otherwise, among the tiles with $d \nmid w$, choose $z$ of least height $C p^a$ and put $m = C p^{a+1}$. Then $m \nmid h(z)$ since $0 < h(z) < m$. Every other tile $r'$ with $d \nmid w(r')$ has height $C p^b$ with $C p^b \ne C p^a$ by Step 1 and $C p^b \ge C p^a$ by minimality, so $b \ge a + 1$ and $m \mid h(r')$. Step 3 now gives $d \mid w(z)$, a contradiction.
Step 5 (both sides divisible by $q$). Suppose every tile has area $q^s p^t$ and $q \mid n$. If $q \nmid w(r)$, then from $w(r)h(r) = q^s p^t$ the full power $q^s$ divides $h(r)$, and the remaining factor is a divisor of $p^t$, so $h(r) = q^s p^a$ for some $a$. Step 4 with $d = q$ and $C = q^s$ shows that $q$ divides every width. Applying the same argument to the partition reflected in the diagonal, which is again perfect and admissible, shows that $q$ divides every height.
Step 6 (descent). If $q$ divides $n$ and both sides of every tile, and the common area is $q^2 B$, then dividing all coordinates by $q$ gives a perfect admissible partition of the $(n/q)$-square with common area $B$. Disjointness, coverage and noncongruence all transfer, because a cell $(i, j)$ of the divided rectangle corresponds to the cell $(q(i+1) - 1, q(j+1) - 1)$ of the original one. The same coordinate division underlies mondrian_perfect_partition_div.
Proof of the theorem. We use strong induction on $s$, for all $n$ and $P$ at once. If $s = 0$, the area is $p^t$ and mondrian_no_perfect_prime_power_area applies. That result is proved by the same scheme with the single prime $p$: Step 5, applied to the area $p^t$ (a second prime with exponent zero), makes $p$ divide both sides of every tile, descent lowers the exponent by two, and area 1 is impossible because two $1 \times 1$ tiles are congruent. If $s \ge 1$, pick $z \in P$. By mondrian_perfect_area_product, $|P| \cdot q^s p^t = n^2$, so $q \mid n^2$ and hence $q \mid n$. By Step 5, $q$ divides both sides of $z$, so $q^2 \mid q^s p^t$; as $q^2$ is coprime to $p^t$, this gives $s \ge 2$. Writing $q^s p^t = q^2 \cdot q^{s-2} p^t$, Step 6 yields a perfect admissible partition of the $(n/q)$-square with common area $q^{s-2} p^t$, which the induction hypothesis for $s - 2 < s$ excludes.
Proof of Corollary 1. The case $f = 0$ is the prime-power side, mondrian_no_perfect_prime_power. For $f \ge 1$, the common area $A$ divides $q^{2f} p^{2e}$ by mondrian_perfect_area_product, so $A = q^s p^t$, and the same divisibility and descent steps reduce the side from $q^{f} p^e$ to $q^{f-1} p^e$, closing an induction on $f$.
Proof of Corollary 2. Suppose the common area $A$ has at most two distinct prime factors. It is positive, so it is 1, a prime power $p^t$, or $q^s p^t$ with $p \ne q$. Area 1 is impossible since all tiles would be congruent unit squares; the other two cases are mondrian_no_perfect_prime_power_area and mondrian_no_perfect_two_prime_area.
5. Discussion
The theorem shows that the common tile area of a perfect Mondrian partition cannot be supported on two primes, whatever the size of the square. Its corollaries exclude every side length with at most two distinct prime factors and show that a counterexample to the zero-defect conjecture needs a tile area, and hence a side, divisible by at least three distinct primes.
The argument rests on a linear identity over the rows of the square and on the distinctness of tile heights. Step 3 isolates one tile with the indicator of a residue class of rows; Step 4 makes this possible whenever the heights of the tiles with width prime to $d$ form a chain $C p^a$, because the smallest of them is then the only one whose height fails to be divisible by the next element of the chain. With two primes, the cofactor of a width prime to $q$ is forced into such a chain. With a third prime $\ell$ in the area, a width prime to $q$ leaves the height $q^s p^a \ell^b$, and these numbers are no longer totally ordered by divisibility, so the isolation step does not apply directly.
The central question recalled in Section 1 of arXiv:2610.19193, whether $M(n) = 0$ for some $n \ge 3$, remains open. The smallest sides not covered by these results, such as $30 = 2 \cdot 3 \cdot 5$, are excluded only by the computation for $n \le 1000$ in arXiv:2311.02385, and no uniform argument is known for sides with three or more distinct prime factors.
Why it is research-level
- Excludes every square side q*p^e for distinct primes p,q with no bound on e and no ordering restriction on the primes; arXiv:2007.09639 Theorem 4.1 excludes prime powers and products of at most three primes but does not give this exponent-uniform two-prime family
- Excludes perfect partitions of every integer square when the common tile area is q^s*p^t for distinct primes p,q and arbitrary exponents, and hence excludes all square sides supported on two primes. The prime-power and small prime-product exclusions of arXiv:2007.09639 Theorem 4.1 and the density theorem in HAL:hal-05729522v2 do not give this uniform common-area restriction
Lean declarations
- mondrian_no_perfect_two_prime_areaFor any distinct primes p and q and natural exponents s and t, no perfect admissible partition of any integer square can have common tile…
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
- mondrian_no_perfect_prime_power_areaNo perfect admissible partition of any integer square can have common tile area equal to a prime power p^t, including exponent zero.
- mondrian_no_perfect_two_prime_powersFor any two distinct primes p and q and arbitrary natural exponents e and f, the square of side q^f*p^e has no perfect admissible integer…
- mondrian_perfect_area_three_prime_factorsEvery tile area in a perfect admissible integer square partition has at least three distinct prime factors.
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
- mondrian_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
- mondrian_perfect_partition_divDividing coordinates by a preserves perfect admissible partitions when a is positive and divides every tile side.
- mondrian_no_perfect_prime_powerNo square whose integer side length is a prime power has a perfect admissible partition.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
References
- arXiv:2610.19193 — A Bounded-Defect Construction for the Mondrian Art Problem
- arXiv:2007.09639
- arXiv:2311.02385
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.