AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_area_one_impossible

theoremverified

An admissible square partition cannot have every tile of area one.

Statement

theorem mondrian_partition_area_one_impossible (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (hP : mondrian_is_partition n P) (harea : ∀ r ∈ P, mondrian_rect_area r = 1) : False
Source
For OP-280, arXiv:2610.19193, Section 1. Related work: arXiv:2007.09639, Theorem 4.1; HAL:hal-05729522v2, Lemma 2.3 (primitive cross sections and common-side descent). The periodic residue argument and the uniform two-prime common-area exclusion are developed here.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
  • mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
  • mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_cellsThe unit cells [i,i+1]×[j,j+1] of the integer rectangle [x₀,x₁]×[y₀,y₁], recorded as r = (x₀, x₁, y₀, y₁); a cell is named by its…
Used by 2

The proof, explained

By the definition of an admissible Mondrian partition, the partition must contain at least two tiles, ruling out lists of length zero or one. In any partition with at least two rectangles r and s, the hypothesis that every tile has area 1 forces both r and s to have width 1 and height 1, as their dimensions are natural numbers whose product is 1. Consequently, r and s have identical dimensions and are congruent, contradicting the partition requirement that all tiles must be pairwise non-congruent.

  1. The partition P must contain at least two rectangles; it cannot have zero or one rectangle.

    By the definition of an admissible partition, P must contain at least two tiles (2 ≤ |P|). Case analysis on P tests whether P is empty or a singleton [r]. If P is empty, the length condition requires 2 ≤ 0; if P = [r], it requires 2 ≤ 1. In both cases, simplifying the inequality against the list length yields a contradiction, ruling out partitions of length less than two.

    lines 3–7

      cases P with
      | nil => have := hP.1; simp at this
      | cons r P =>
        cases P with
        | nil => have := hP.1; simp at this
  2. The first two rectangles r and s in the partition both have width 1 and height 1.

    With the smaller cases eliminated, P decomposes into r :: s :: P', containing at least two rectangles r and s. By assumption (harea), every rectangle in P has area 1, defined as width * height. Since rectangle dimensions are natural numbers, Nat.eq_one_of_mul_eq_one_right and Nat.eq_one_of_mul_eq_one_left establish that both r and s have width 1 and height 1.

    lines 8–12

    uses Nat.eq_one_of_mul_eq_one_right, Nat.eq_one_of_mul_eq_one_left

        | cons s P =>
          have hrw := Nat.eq_one_of_mul_eq_one_right (harea r (by simp))
          have hrh := Nat.eq_one_of_mul_eq_one_left (harea r (by simp))
          have hsw := Nat.eq_one_of_mul_eq_one_right (harea s (by simp))
          have hsh := Nat.eq_one_of_mul_eq_one_left (harea s (by simp))
  3. Rectangles r and s are congruent, contradicting the partition requirement that distinct tiles are pairwise non-congruent.

    An admissible partition requires distinct tiles to be pairwise disjoint and non-congruent. Extracting this pairwise property for the pair (r, s) using List.pairwise_cons.mp shows that r and s cannot be congruent. However, since both r and s have width 1 and height 1, their dimensions match, so they are congruent by the first disjunct of rectangle congruence via Or.inl (with width and height equality closed by linear arithmetic). This contradiction completes the proof.

    lines 13–14

    uses List.pairwise_cons.mp, Or.inl

          have hpair := (List.pairwise_cons.mp hP.2.2.1).1 s (by simp)
          exact hpair.2 (Or.inl ⟨by omega, by omega⟩)
Nat.eq_one_of_mul_eq_one_right
If the product of two natural numbers is 1, then the first factor is 1 (m * n = 1 → m = 1).
Nat.eq_one_of_mul_eq_one_left
If the product of two natural numbers is 1, then the second factor is 1 (m * n = 1 → n = 1).
List.pairwise_cons.mp
If a list starting with head a and tail l is pairwise related by a relation R, then a is related by R to every element of l, and l is pairwise related under R.
Or.inl
From a proof of proposition a, deduce the disjunction a ∨ b.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem mondrian_partition_area_one_impossible (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (hP : mondrian_is_partition n P) (harea : ∀ r ∈ P, mondrian_rect_area r = 1) : False := by  cases P with  | nil => have := hP.1; simp at this  | cons r P =>    cases P with    | nil => have := hP.1; simp at this    | cons s P =>      have hrw := Nat.eq_one_of_mul_eq_one_right (harea r (by simp))      have hrh := Nat.eq_one_of_mul_eq_one_left (harea r (by simp))      have hsw := Nat.eq_one_of_mul_eq_one_right (harea s (by simp))      have hsh := Nat.eq_one_of_mul_eq_one_left (harea s (by simp))      have hpair := (List.pairwise_cons.mp hP.2.2.1).1 s (by simp)      exact hpair.2 (Or.inl ⟨by omega, by omega⟩)
See it in the graphDiscuss this resultChallenge it