AFTD Auto-Formalizing Theoretical Domains

mondrian_no_perfect_six

theoremverified

The integer square of side six has no perfect admissible partition.

Statement

theorem mondrian_no_perfect_six :
    ¬ ∃ P, mondrian_is_partition 6 P ∧ mondrian_defect P = 0
Source
Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • mondrian_no_perfect_of_shape_boundThere is no perfect n-square partition if, for every k at least two and positive A with k times A equal to n squared, fewer than k…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

A perfect Mondrian partition of a 6 × 6 square into k ≥ 2 rectangles of equal area A requires k · A = 36 and at least k pairwise incongruent shapes of area A fitting inside the square. By `mondrian_no_perfect_of_shape_bound`, it suffices to show that the count of such shapes is always strictly less than k. Because k ≥ 2, the piece area A is at most 18, and finite computation checks that any area up to 18 has at most 2 fitting shapes; this immediately settles k ≥ 3, while for k = 2 (so A = 18), the only valid shape is 3 × 6, giving 1 < 2.

  1. To rule out a perfect partition, it suffices to show that for any k ≥ 2 and A > 0 with k · A = 36, there are strictly fewer than k incongruent rectangle shapes of area A fitting in a 6 × 6 square.

    By applying `mondrian_no_perfect_of_shape_bound`, a perfect partition of defect 0 requires k rectangles of identical area A such that k · A = 36. Since all pieces must be pairwise non-congruent, at least k distinct shapes of area A must fit in the 6 × 6 square; showing that fewer than k such shapes exist rules out any such partition by the pigeonhole principle.

    line 3

    uses mondrian_no_perfect_of_shape_bound

      apply mondrian_no_perfect_of_shape_bound
  2. Assume k ≥ 2 and A > 0 satisfy k · A = 36; then the piece area A is at most 18.

    We introduce k and A along with the hypotheses that k ≥ 2, A > 0, and k · A = 6² = 36. Since k ≥ 2, non-linear arithmetic (`nlinarith`) establishes that A ≤ 36 / 2 = 18.

    lines 4–5

      intro k A hk hA heq
      have hAtop : A ≤ 18 := by nlinarith
  3. For any such area A, at most 2 incongruent rectangle shapes fit in the 6 × 6 square.

    By exhaustive computation (`decide`), for every integer area d ∈ {0, ..., 18}, the number of pairs (w, h) with w ≤ h ≤ 6 and w · h = d is at most 2. Instantiating this universal statement for A (where A < 19 follows from A ≤ 18 via `omega`) shows that the number of available shapes of area A is at most 2.

    lines 6–8

      have htest : ∀ d : Fin 19, (mondrian_factor_shapes 6 d.val).card ≤ 2 := by decide
      have hcard := htest ⟨A, by omega⟩
      change (mondrian_factor_shapes 6 A).card ≤ 2 at hcard
  4. If k = 2, the number of available shapes of area A is strictly less than k.

    We split into cases on whether k = 2. When k = 2, the relation 2 · A = 36 forces A = 18 by arithmetic. Substituting k = 2 and A = 18, the only rectangle shape of area 18 fitting within side length 6 is 3 × 6 (since 1 × 18 and 2 × 9 exceed 6). Hence there is only 1 shape, and `decide` confirms 1 < 2.

    lines 9–12

      by_cases hk2 : k = 2
      · have hA18 : A = 18 := by nlinarith
        subst k A
        decide
  5. If k ≠ 2, the number of available shapes of area A is strictly less than k.

    In the remaining case k ≠ 2, the assumption k ≥ 2 implies k ≥ 3. Since there are at most 2 shapes of area A, linear integer arithmetic (`omega`) closes the goal because 2 < 3 ≤ k.

    line 13

      · omega
mondrian_no_perfect_of_shape_bound
If every partition of an n × n square into k ≥ 2 rectangles of equal area A requires strictly more rectangles than there are incongruent shapes of area A fitting inside the square, then no perfect partition of defect 0 exists.

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_no_perfect_six :    ¬ ∃ P, mondrian_is_partition 6 P ∧ mondrian_defect P = 0 := by  apply mondrian_no_perfect_of_shape_bound  intro k A hk hA heq  have hAtop : A ≤ 18 := by nlinarith  have htest : ∀ d : Fin 19, (mondrian_factor_shapes 6 d.val).card ≤ 2 := by decide  have hcard := htest ⟨A, by omega⟩  change (mondrian_factor_shapes 6 A).card ≤ 2 at hcard  by_cases hk2 : k = 2  · have hA18 : A = 18 := by nlinarith    subst k A    decide  · omega
See it in the graphDiscuss this resultChallenge it