AFTD Auto-Formalizing Theoretical Domains

Research Blogs

不存在公共块面积由两个素数支撑的完美蒙德里安划分

medium tier2026-10-26OP-280本文含 2 个研究级成果审阅: Claude CodeEnglish

摘要

蒙德里安艺术问题询问将一个 $n \times n$ 正方形划分为至少两个两两不全等的整边长矩形的划分中,最大与最小块面积之差(即缺陷)的最小值。若一个划分的缺陷为零,则称其为完美划分;是否存在正方形允许完美划分是一个未决问题,且被猜想为否定答案。我们证明了对于不同素数 $p$ 和 $q$ 以及任意指数 $s, t$,任何整数正方形的完美划分其公共块面积均不可能为 $q^s p^t$。由此可得两个推论:边长至多含有两个不同素因子的正方形均不存在完美划分,且在任何完美划分中,公共块面积至少含有三个不同的素因子。该证明结合了从正方形各行上的矩恒等式得到的同余式,以及完美划分的各块具有两两不同高度这一观察;二者共同迫使 $q$ 整除每个块的两条边长,此后可以将坐标同时除以 $q$,使面积中 $q$ 的指数减少 2。本文的所有结果均已在 Lean 4 中形式化并得到验证。

1. 引言

蒙德里安艺术问题关注将一个 $n \times n$ 正方形划分为边长为正整数的轴对齐矩形。为了排除如相同平行条带之类的平凡构型,容许划分中的矩形被要求两两不全等:任意两个矩形不能具有相同的无序边长对。划分 $P$ 的缺陷为 $$\text{def}(P) = \max_{R \in P} |R| - \min_{R \in P} |R|,$$ 而蒙德里安数 $M(n)$ 则是将 $n \times n$ 正方形划分为两个或更多矩形的所有容许划分中的最小缺陷。

缺陷为零的划分称为完美划分:其矩形两两不全等,但面积均为相同的 $A$,因此当有 $k$ 个矩形时有 $kA = n^2$。正如 arXiv:2610.19193 在第 1 节中所回顾的,是否存在某个 $n$ 使得 $M(n) = 0$ 仍是一个未决问题,尽管人们猜想不存在这样的 $n$。该论文还指出,只要存在一个完美划分就会产生无穷多个,因为将所有边长缩放一个公共因子仍保持缺陷为零,并且通过计算已对所有 $n \le 1000$ 排除了完美划分(arXiv:2311.02385)。在理论方面,素数幂的情形是经典的:边长为素数幂的正方形不存在完美划分(arXiv:2007.09639,Theorem 4.1,通过对可用形状计数),并且密度结果表明有正比例的整数 $n$ 满足 $M(n) > 0$。

本文给出了一个同时适用于所有正方形的阻碍,并且它是用公共块面积而非边长来表述的。主定理 mondrian_no_perfect_two_prime_area 指出,对于不同素数 $p$ 和 $q$ 以及任意指数 $s$ 和 $t$,任何整数正方形的完美容许划分中,所有块的面积均不可能全为 $q^s p^t$。它推广了针对素数幂面积 $p^t$ 的相同命题 mondrian_no_perfect_prime_power_area。这里形式化了两个推论:

  • mondrian_no_perfect_two_prime_powers:对于不同素数 $p, q$ 和所有指数 $e, f$,边长为 $q^f p^e$ 的正方形不存在完美划分。结合素数幂的情形,这排除了至多含有两个不同素因子的所有边长,且对指数没有任何限制。
  • mondrian_perfect_area_three_prime_factors:在任何正方形的任何完美划分中,公共块面积至少含有三个不同的素因子。

在同一形式化开发中,一个较早且较弱的结果 mondrian_no_perfect_prime_mul_prime_pow 通过另一条途径处理了边长 $q p^e$,即计算能放入该正方形内的面积因子对;它是第一推论中 $f = 1$ 的情形。关键的新要素是一个整除性引理:若公共面积为 $q^s p^t$ 且 $q$ 整除 $n$,则 $q$ 整除每个块的两条边长。其证明仅使用了正方形各行上的一个线性恒等式、完美划分中块高度的两两不同性,以及不能被 $q$ 整除的块高度在整除关系下构成一条链这一事实。

2. 预备知识

我们遵循 Lean 形式化的约定。

定义 1(mondrian_rect_width、mondrian_rect_height、mondrian_rect_area)。矩形是自然数的四元组 $r = (x_0, x_1, y_0, y_1)$,其左下角为 $(x_0, y_0)$,右上角为 $(x_1, y_1)$。其宽度为 $x_1 - x_0$,高度为 $y_1 - y_0$,其面积为二者的乘积。

定义 2(mondrian_is_partition)。对于自然数 $n$ 和矩形列表 $P$,当满足以下条件时 mondrian_is_partition n P 成立:

  1. $P$ 至少有两个元素;
  2. 每个 $r \in P$ 均满足 $x_0 < x_1$ 以及 $y_0 < y_1$;
  3. $P$ 的不同项具有不相交的单位元胞集且不全等,其中若两个矩形具有相同的宽度和高度,或者各自的宽度等于另一者的高度,则称这两个矩形全等;
  4. 这些矩形的单位元胞的并集恰好是 $\{0, \dots, n-1\} \times \{0, \dots, n-1\}$。

单位元胞以其左下角命名,因此条件 4 说明这些块覆盖了画布 $[0,n] \times [0,n]$ 且没有块超出画布。

定义 3(mondrian_defect)。$P$ 的缺陷是各块面积的最大值减去其最小值(空列表取值为 0)。若一个划分的缺陷为 0,则称其为完美划分。

贯穿全文使用了两个基本事实。根据 mondrian_defect_zero_equal,缺陷为零的列表中所有块均具有相同的面积。根据 mondrian_perfect_area_product,若 $P$ 是 $n$-正方形的一个完美容许划分且 $r \in P$,则 $|P| \cdot \text{area}(r) = n^2$,因为各个块在元胞上是不相交的且覆盖了画布的 $n^2$ 个元胞。

3. 主要结果

定理(mondrian_no_perfect_two_prime_area)。设 $p$ 与 $q$ 为不同素数,并设 $s, t, n \in \mathbb{N}$。不存在矩形列表 $P$ 满足 mondrian_is_partition n P、mondrian_defect P = 0 且每个 $r \in P$ 的面积均为 $q^s p^t$。

该命题对 $n$ 没有施加任何条件:它纯粹是对公共块面积的阻碍。$s = 0$ 的情形是 mondrian_no_perfect_prime_power_area,它排除了素数幂公共面积 $p^t$(包括面积 1)。

推论 1(mondrian_no_perfect_two_prime_powers)。设 $p$ 和 $q$ 为不同素数,且 $e, f \in \mathbb{N}$。则 $\neg \exists P,\ \text{mondrian\_is\_partition}(q^f p^e, P) \wedge \text{mondrian\_defect}(P) = 0$。

事实上,由 mondrian_perfect_area_product,完美划分的公共面积整除 $n^2 = q^{2f} p^{2e}$,因此具有 $q^s p^t$ 的形式。每个至多含有两个不同素因子的整数 $n \ge 2$ 都具有 $q^f p^e$ 的形式,所以这样的正方形均不存在完美划分。

推论 2(mondrian_perfect_area_three_prime_factors)。若 mondrian_is_partition n P、mondrian_defect P = 0 且 $r \in P$,则 $r$ 的面积至少有三个不同的素因子。

因此,任何假设存在的完美划分其块面积必须能被三个不同的素数整除,又因为该面积整除 $n^2$,其边长 $n$ 也必须至少含有三个不同的素因子。这些结果留下的最小未决边长为 $30, 42, 60, 66, \dots$;通过 arXiv:2311.02385 的计算,排除了所有不超过 1000 的边长,因此这里的结果补充了双素数边长的无穷族,并对任何反例的面积给出了结构性限制。

定理 mondrian_no_perfect_two_prime_area (Lean 4 已验证)
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) : False

4. 证明

在全文中,$P$ 为 $n \times n$ 正方形的一个完美容许划分;对 $r \in P$,我们用 $w(r)$ 和 $h(r)$ 分别表示其宽度与高度,并用 $r = (x_0, x_1, y_0, y_1)$ 表示其坐标。

步骤 1(不同高度)。$P$ 的两个不同块具有不同的高度。若 $h(r) = h(r')$,由于 $w(r)h(r) = w(r')h(r')$ 且高度为正,则亦有 $w(r) = w(r')$,从而 $r$ 与 $r'$ 全等,但这是容许性所禁止的。

步骤 2(行上的矩恒等式)。对于行水平 $0, 1, \dots, n$ 上的任意整数值函数 $f$, $$\sum_{r \in P} w(r)\,\bigl(f(y_1(r)) - f(y_0(r))\bigr) = n\,\bigl(f(n) - f(0)\bigr).$$ 将 $f(y_1) - f(y_0)$ 写为行 $y_0 \le y < y_1$ 上的裂项和,左侧变为 $\sum_{y < n} (f(y+1) - f(y)) \sum_{r \ni y} w(r)$,而穿过任意行 $y$ 的块宽度之和为 $n$,因为这些块构成了该行元胞的一个划分。

步骤 3(孤立块)。设 $d \mid n$ 且 $m \ge 1$。假设 $r \in P$ 满足 $m \nmid h(r)$,且其他任意块 $r'$ 均满足 $d \mid w(r')$ 或 $m \mid h(r')$。则 $d \mid w(r)$。为此,将步骤 2 应用于如下函数:若 $y \equiv y_1(r) \pmod m$ 则 $f(y) = 1$,否则 $f(y) = 0$。右侧是 $n$ 的倍数,因而也是 $d$ 的倍数。满足 $m \mid h(r')$ 的块 $r'$ 满足 $y_0(r') \equiv y_1(r') \pmod m$,因此其对 $f$ 的增量为 0;满足 $d \mid w(r')$ 的块贡献了 $d$ 的倍数。对于 $r$ 本身,因 $m \nmid h(r)$,有 $y_0(r) \not\equiv y_1(r) \pmod m$,所以其增量恰好为 1,对应的项为 $w(r)$。将该恒等式模 $d$ 化简即得 $d \mid w(r)$。

步骤 4(素数链)。设 $d \mid n$,设 $p$ 为素数且 $C > 0$,并假设宽度不能被 $d$ 整除的每个块其高度均形如 $C p^a$。则每个宽度均能被 $d$ 整除。否则,在满足 $d \nmid w$ 的块中,选取高度 $C p^a$ 最小的块 $z$ 并令 $m = C p^{a+1}$。由于 $0 < h(z) < m$,有 $m \nmid h(z)$。由步骤 1,其他任意满足 $d \nmid w(r')$ 的块 $r'$ 的高度 $C p^b$ 均满足 $C p^b \ne C p^a$,且由极小性有 $C p^b \ge C p^a$,因此 $b \ge a + 1$ 且 $m \mid h(r')$。此时步骤 3 给出 $d \mid w(z)$,矛盾。

步骤 5(两条边均能被 $q$ 整除)。假设每个块的面积均为 $q^s p^t$ 且 $q \mid n$。若 $q \nmid w(r)$,则由 $w(r)h(r) = q^s p^t$ 可知整幂 $q^s$ 整除 $h(r)$,剩余因子为 $p^t$ 的约数,因此存在某个 $a$ 使得 $h(r) = q^s p^a$。取 $d = q$ 及 $C = q^s$ 应用步骤 4 表明 $q$ 整除每个宽度。将相同的论据应用于沿对角线翻转后的划分(该划分同样是完美且容许的),表明 $q$ 整除每个高度。

步骤 6(递降)。若 $q$ 整除 $n$ 且整除每个块的两条边,并且公共面积为 $q^2 B$,则将所有坐标除以 $q$ 即可得到 $(n/q)$-正方形的一个公共面积为 $B$ 的完美容许划分。不相交性、覆盖性以及不全等性均可传递,因为划分后矩形的一个元胞 $(i, j)$ 对应于原矩形的元胞 $(q(i+1) - 1, q(j+1) - 1)$。相同的坐标除法构成了 mondrian_perfect_partition_div 的基础。

定理的证明。我们对 $s$ 进行强归纳,同时处理所有的 $n$ 和 $P$。若 $s = 0$,面积为 $p^t$,应用 mondrian_no_perfect_prime_power_area。该结果通过单素数 $p$ 的相同方案证明:步骤 5 应用于面积 $p^t$(指数为零的第二个素数)迫使 $p$ 整除每个块的两条边,递降使指数减少 2,而面积 1 是不可能的,因为两个 $1 \times 1$ 的块全等。若 $s \ge 1$,任取 $z \in P$。根据 mondrian_perfect_area_product,有 $|P| \cdot q^s p^t = n^2$,故 $q \mid n^2$,从而 $q \mid n$。由步骤 5,$q$ 整除 $z$ 的两条边,所以 $q^2 \mid q^s p^t$;因 $q^2$ 与 $p^t$ 互素,这给出 $s \ge 2$。写作 $q^s p^t = q^2 \cdot q^{s-2} p^t$,步骤 6 给出 $(n/q)$-正方形的一个公共面积为 $q^{s-2} p^t$ 的完美容许划分,而这由针对 $s - 2 < s$ 的归纳假设所排除。

推论 1 的证明。$f = 0$ 的情形即为素数幂边长情形 mondrian_no_perfect_prime_power。对于 $f \ge 1$,根据 mondrian_perfect_area_product,公共面积 $A$ 整除 $q^{2f} p^{2e}$,因此 $A = q^s p^t$,且相同的整除性与递降步骤将边长从 $q^{f} p^e$ 降为 $q^{f-1} p^e$,从而完成了对 $f$ 的归纳。

推论 2 的证明。假设公共面积 $A$ 至多含有两个不同的素因子。由于它是正数,因此它只能是 1、素数幂 $p^t$,或满足 $p \ne q$ 的 $q^s p^t$。面积 1 是不可能的,因为所有块都将是全等的单位正方形;另外两种情形分别由 mondrian_no_perfect_prime_power_area 和 mondrian_no_perfect_two_prime_area 所排除。

5. 讨论

该定理表明,无论正方形的大小为何,完美蒙德里安划分的公共块面积均不可能仅由两个素数支撑。其推论排除了至多含有两个不同素因子的所有边长,并表明零缺陷猜想的反例需要其块面积(从而边长)至少能被三个不同的素数整除。

该论证基于正方形各行上的一个线性恒等式以及块高度的两两互异性。步骤 3 利用行的剩余类的指示函数孤立出一个块;只要与 $d$ 互素的宽度的块高度构成一条链 $C p^a$,步骤 4 就能实现这一点,因为此时其中最小者是唯一一个高度不能被链中下一个元素整除的块。在两个素数的情形下,与 $q$ 互素的宽度的余因子被迫处于这样的一条链中。当面积中出现第三个素数 $\ell$ 时,与 $q$ 互素的宽度留下的高度为 $q^s p^a \ell^b$,而这些数在整除关系下不再构成全序,因此孤立步骤无法直接应用。

arXiv:2610.19193 第 1 节中回顾的核心问题——是否存在某个 $n \ge 3$ 使得 $M(n) = 0$——仍然悬而未决。这些结果未涵盖的最小边长(例如 $30 = 2 \cdot 3 \cdot 5$)仅被 arXiv:2311.02385 中针对 $n \le 1000$ 的计算所排除,并且对于具有三个或更多不同素因子的边长,目前尚无统一的论证方法。

为什么是研究级成果

  • 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 声明

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2610.19193 — A Bounded-Defect Construction for the Mondrian Art Problem
  2. arXiv:2007.09639
  3. arXiv:2311.02385

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。