AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_div

theoremverified

An admissible partition of the a times c square, with every tile side a multiple of positive a, becomes an admissible partition of the c-square after dividing coordinates by a.

Statement

theorem mondrian_partition_div (a c : ℕ) (ha : 0 < a)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition (a * c) P)
    (hd : ∀ r ∈ P, a ∣ mondrian_rect_width r ∧ a ∣ mondrian_rect_height r) :
    mondrian_is_partition c (P.map (mondrian_rect_div a))
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 9
  • mondrian_interval_divAn integer cell i belongs to the coordinatewise quotient of an interval precisely when the last cell of its a-block belongs to the…
  • 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_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…
  • mondrian_rect_divDivide all four rectangle coordinates by a using natural-number division.
  • mondrian_rect_div_cellsMembership in a coordinatewise divided rectangle is equivalent to membership of the corresponding last cell of the original square block.
  • mondrian_rect_div_dimensionsDividing coordinates of a positive rectangle whose side lengths are multiples of a divides its width and height exactly by a.
  • mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
  • 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).
Used by 1

The proof, explained

The proof verifies that dividing coordinates by $a$ transforms a partition of the $(a \cdot c) \times (a \cdot c)$ square into an admissible partition of the $c \times c$ square. Preserving list length and scaling the positive dimensions by $a$ guarantees at least two non-degenerate rectangles. The key link is that a cell $(i, j)$ lies in a divided rectangle $r/a$ if and only if the representative point $(a(i+1)-1, a(j+1)-1)$ lies in $r$; this equivalence directly preserves both pairwise disjointness and complete grid coverage. Finally, non-congruence is preserved because any congruence between divided rectangles would scale up by $a$ to a congruence between the original rectangles.

  1. For every rectangle $r \in P$, scaling the dimensions of the divided rectangle by $a$ recovers the original width and height of $r$.

    Since $a > 0$, each rectangle $r \in P$ is non-degenerate (positive width and height), and $a$ divides both dimensions of $r$ by assumption, the lemma `mondrian_rect_div_dimensions` shows that $a \cdot \text{width}(r / a) = \text{width}(r)$ and $a \cdot \text{height}(r / a) = \text{height}(r)$.

    lines 5–10

    uses mondrian_rect_div_dimensions

      have hdim : ∀ r ∈ P,
          a * mondrian_rect_width (mondrian_rect_div a r) = mondrian_rect_width r ∧
          a * mondrian_rect_height (mondrian_rect_div a r) = mondrian_rect_height r := by
        intro r hr
        exact mondrian_rect_div_dimensions a ha r (hp.2.1 r hr).1
          (hp.2.1 r hr).2 (hd r hr).1 (hd r hr).2
  2. The partition definition decomposes into three remaining goals, and the list of divided rectangles contains at least two rectangles.

    An admissible Mondrian partition requires at least two rectangles, valid positive dimensions, pairwise disjointness and incongruence, and covering the square. Mapping preserves list length by `List.length_map`, so the divided list retains length at least 2 from $P$.

    line 11

    uses List.length_map

      refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩
  3. Every divided rectangle is non-degenerate (its width and height are strictly positive).

    Any rectangle in the mapped list is the division of some original rectangle $s \in P$. Because $s$ has positive width and height, and multiplying the divided rectangle's dimensions by $a$ yields the original dimensions, the divided dimensions must also be positive by `Nat.pos_of_mul_pos_left`, which implies the bottom-left coordinate is strictly less than the top-right coordinate.

    lines 12–23

    uses List.mem_map.mp, Nat.sub_pos_of_lt, Nat.pos_of_mul_pos_left, Nat.lt_of_sub_pos

      · intro r hr
        obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr
        have h1 := (hdim s hs).1
        have h2 := (hdim s hs).2
        have hpos := hp.2.1 s hs
        have hw : 0 < mondrian_rect_width (mondrian_rect_div a s) := by
          have : 0 < mondrian_rect_width s := Nat.sub_pos_of_lt hpos.1
          exact Nat.pos_of_mul_pos_left (by rwa [h1])
        have hh : 0 < mondrian_rect_height (mondrian_rect_div a s) := by
          have : 0 < mondrian_rect_height s := Nat.sub_pos_of_lt hpos.2
          exact Nat.pos_of_mul_pos_left (by rwa [h2])
        exact ⟨Nat.lt_of_sub_pos hw, Nat.lt_of_sub_pos hh⟩
  4. Divided rectangles are pairwise disjoint.

    Via `List.pairwise_map`, the pairwise property on the mapped list reduces to checking disjointness and non-congruence for any pair of distinct rectangles $r, s \in P$. If a cell $(i, j)$ belonged to the intersection of two divided rectangles, then by `mondrian_rect_div_cells` the representative point $(a(i+1)-1, a(j+1)-1)$ would belong to both $r$ and $s$, contradicting their disjointness.

    lines 24–32

    uses List.pairwise_map, Finset.disjoint_left, Finset.disjoint_left.mp, mondrian_rect_div_cells

      · rw [List.pairwise_map]
        apply hp.2.2.1.imp_of_mem
        intro r s hr hs hrs
        refine ⟨?_, ?_⟩
        · rw [Finset.disjoint_left]
          rintro ⟨i, j⟩ hi hj
          exact Finset.disjoint_left.mp hrs.1
            ((mondrian_rect_div_cells a ha r i j).mp hi)
            ((mondrian_rect_div_cells a ha s i j).mp hj)
  5. Divided rectangles are pairwise non-congruent.

    If two divided rectangles were congruent (having matching dimensions either directly or after swapping width and height), then multiplying each dimension by $a$ would imply that the original rectangles $r$ and $s$ are congruent, contradicting the pairwise non-congruence of $P$.

    lines 33–45

        · intro hc
          apply hrs.2
          obtain ⟨hrw, hrh⟩ := hdim r hr
          obtain ⟨hsw, hsh⟩ := hdim s hs
          rcases hc with ⟨hw, hh⟩ | ⟨hw, hh⟩
          · left
            constructor
            · rw [← hrw, ← hsw, hw]
            · rw [← hrh, ← hsh, hh]
          · right
            constructor
            · rw [← hrw, ← hsh, hw]
            · rw [← hrh, ← hsw, hh]
  6. The union of the divided rectangles is contained in the $c \times c$ grid.

    If a cell $(i, j)$ belongs to a divided rectangle $s / a$, then $(a(i+1)-1, a(j+1)-1)$ belongs to $s$, hence to the $(a \cdot c) \times (a \cdot c)$ grid covered by $P$. Applying `mondrian_interval_div` and canceling $a \cdot c / a = c$ via `Nat.mul_div_cancel_left` shows that $i < c$ and $j < c$, so $(i, j)$ is in the $c \times c$ grid.

    lines 46–59

    uses Finset.mem_biUnion.mp, List.mem_map.mp, List.mem_toFinset.mp, mondrian_rect_div_cells, Finset.mem_biUnion.mpr, List.mem_toFinset.mpr, Finset.mem_product, Finset.mem_range, mondrian_interval_div, Nat.zero_le, Nat.mul_div_cancel_left, And.intro

      · ext ⟨i, j⟩
        constructor
        · intro hi
          obtain ⟨r, hr, hi⟩ := Finset.mem_biUnion.mp hi
          obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr)
          have hi' := (mondrian_rect_div_cells a ha s i j).mp hi
          have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈
              P.toFinset.biUnion mondrian_rect_cells :=
            Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩
          rw [hp.2.2.2] at hu
          simp only [Finset.mem_product, Finset.mem_range] at hu ⊢
          have hiq := (mondrian_interval_div a 0 (a * c) i ha).mpr ⟨Nat.zero_le _, hu.1⟩
          have hjq := (mondrian_interval_div a 0 (a * c) j ha).mpr ⟨Nat.zero_le _, hu.2⟩
          simpa only [Nat.mul_div_cancel_left c ha] using And.intro hiq.2 hjq.2
  7. Every cell in the $c \times c$ grid is covered by some divided rectangle.

    Given $(i, j) \in [0, c) \times [0, c)$, we have $i < (a \cdot c) / a$ and $j < (a \cdot c) / a$. By `mondrian_interval_div`, the point $(a(i+1)-1, a(j+1)-1)$ lies in the $(a \cdot c) \times (a \cdot c)$ grid, so it belongs to some rectangle $r \in P$. Then $(i, j)$ belongs to the divided rectangle $r / a$ by `mondrian_rect_div_cells`.

    lines 60–74

    uses Finset.mem_product, Finset.mem_range, mondrian_interval_div, Nat.mul_div_cancel_left, Finset.mem_biUnion.mp, Finset.mem_biUnion.mpr, mondrian_rect_div_cells, List.mem_toFinset.mpr, List.mem_map.mpr, List.mem_toFinset.mp

        · intro hi
          simp only [Finset.mem_product, Finset.mem_range] at hi
          have hi1 := (mondrian_interval_div a 0 (a * c) i ha).mp
            ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.1⟩
          have hi2 := (mondrian_interval_div a 0 (a * c) j ha).mp
            ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.2⟩
          have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈
              Finset.range (a * c) ×ˢ Finset.range (a * c) := by
            simp only [Finset.mem_product, Finset.mem_range]
            exact ⟨hi1.2, hi2.2⟩
          rw [← hp.2.2.2] at hu
          obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu
          apply Finset.mem_biUnion.mpr
          refine ⟨mondrian_rect_div a r, ?_, (mondrian_rect_div_cells a ha r i j).mpr hm⟩
          exact List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩)
And.intro
Given proofs of propositions $a$ and $b$, constructs a proof of their conjunction $a \land b$.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_left.mp
If two finite sets are disjoint, any element belonging to the first cannot belong to the second.
Finset.mem_biUnion.mp
If an element belongs to a big union of finsets, it belongs to at least one component finset in the family.
Finset.mem_biUnion.mpr
If an element belongs to one of the component finsets in a family, it belongs to their big union.
Finset.mem_product
A pair belongs to the Cartesian product of two finite sets if and only if its first component is in the first set and its second component is in the second set.
Finset.mem_range
A natural number $m$ belongs to `Finset.range n` if and only if $m < n$.
List.length_map
Mapping a function over a list preserves the length of the list.
List.mem_map.mp
If an element belongs to the image of a list under a function, it is the image of some element of that list.
List.mem_map.mpr
If an element is the image of some element in a list, it belongs to the mapped list.
List.mem_toFinset.mp
If an element belongs to the finite set associated with a list, it belongs to the list.
List.mem_toFinset.mpr
If an element belongs to a list, it belongs to the finite set associated with that list.
List.pairwise_map
A mapped list is pairwise related by a relation $R$ if and only if the original list is pairwise related by the pullback of $R$ along the map.
mondrian_interval_div
For $a > 0$, an integer index $i$ lies in the interval $[x/a, y/a)$ if and only if $a(i+1)-1$ lies in $[x, y)$.
mondrian_rect_div_cells
A grid cell $(i, j)$ belongs to the divided rectangle $r/a$ if and only if the point $(a(i+1)-1, a(j+1)-1)$ belongs to $r$.
mondrian_rect_div_dimensions
If a rectangle has positive dimensions that are divisible by $a > 0$, multiplying the dimensions of its coordinate division by $a$ recovers its original dimensions.
Nat.lt_of_sub_pos
If $n - m > 0$ for natural numbers, then $m < n$.
Nat.mul_div_cancel_left
For positive $n$, multiplying $m$ by $n$ and then dividing by $n$ yields $m$.
Nat.pos_of_mul_pos_left
If a product of natural numbers $a \cdot b$ is strictly positive, then $b > 0$.
Nat.sub_pos_of_lt
If $m < n$ for natural numbers, then $n - m > 0$.
Nat.zero_le
Every natural number is greater than or equal to zero.

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_div (a c : ℕ) (ha : 0 < a)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition (a * c) P)    (hd : ∀ r ∈ P, a ∣ mondrian_rect_width r ∧ a ∣ mondrian_rect_height r) :    mondrian_is_partition c (P.map (mondrian_rect_div a)) := by  have hdim : ∀ r ∈ P,      a * mondrian_rect_width (mondrian_rect_div a r) = mondrian_rect_width r ∧      a * mondrian_rect_height (mondrian_rect_div a r) = mondrian_rect_height r := by    intro r hr    exact mondrian_rect_div_dimensions a ha r (hp.2.1 r hr).1      (hp.2.1 r hr).2 (hd r hr).1 (hd r hr).2  refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩  · intro r hr    obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr    have h1 := (hdim s hs).1    have h2 := (hdim s hs).2    have hpos := hp.2.1 s hs    have hw : 0 < mondrian_rect_width (mondrian_rect_div a s) := by      have : 0 < mondrian_rect_width s := Nat.sub_pos_of_lt hpos.1      exact Nat.pos_of_mul_pos_left (by rwa [h1])    have hh : 0 < mondrian_rect_height (mondrian_rect_div a s) := by      have : 0 < mondrian_rect_height s := Nat.sub_pos_of_lt hpos.2      exact Nat.pos_of_mul_pos_left (by rwa [h2])    exact ⟨Nat.lt_of_sub_pos hw, Nat.lt_of_sub_pos hh⟩  · rw [List.pairwise_map]    apply hp.2.2.1.imp_of_mem    intro r s hr hs hrs    refine ⟨?_, ?_⟩    · rw [Finset.disjoint_left]      rintro ⟨i, j⟩ hi hj      exact Finset.disjoint_left.mp hrs.1        ((mondrian_rect_div_cells a ha r i j).mp hi)        ((mondrian_rect_div_cells a ha s i j).mp hj)    · intro hc      apply hrs.2      obtain ⟨hrw, hrh⟩ := hdim r hr      obtain ⟨hsw, hsh⟩ := hdim s hs      rcases hc with ⟨hw, hh⟩ | ⟨hw, hh⟩      · left        constructor        · rw [← hrw, ← hsw, hw]        · rw [← hrh, ← hsh, hh]      · right        constructor        · rw [← hrw, ← hsh, hw]        · rw [← hrh, ← hsw, hh]  · ext ⟨i, j⟩    constructor    · intro hi      obtain ⟨r, hr, hi⟩ := Finset.mem_biUnion.mp hi      obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr)      have hi' := (mondrian_rect_div_cells a ha s i j).mp hi      have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈          P.toFinset.biUnion mondrian_rect_cells :=        Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩      rw [hp.2.2.2] at hu      simp only [Finset.mem_product, Finset.mem_range] at hu ⊢      have hiq := (mondrian_interval_div a 0 (a * c) i ha).mpr ⟨Nat.zero_le _, hu.1⟩      have hjq := (mondrian_interval_div a 0 (a * c) j ha).mpr ⟨Nat.zero_le _, hu.2⟩      simpa only [Nat.mul_div_cancel_left c ha] using And.intro hiq.2 hjq.2    · intro hi      simp only [Finset.mem_product, Finset.mem_range] at hi      have hi1 := (mondrian_interval_div a 0 (a * c) i ha).mp        ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.1⟩      have hi2 := (mondrian_interval_div a 0 (a * c) j ha).mp        ⟨by simp, by simpa only [Nat.mul_div_cancel_left c ha] using hi.2⟩      have hu : (a * (i + 1) - 1, a * (j + 1) - 1) ∈          Finset.range (a * c) ×ˢ Finset.range (a * c) := by        simp only [Finset.mem_product, Finset.mem_range]        exact ⟨hi1.2, hi2.2⟩      rw [← hp.2.2.2] at hu      obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu      apply Finset.mem_biUnion.mpr      refine ⟨mondrian_rect_div a r, ?_, (mondrian_rect_div_cells a ha r i j).mpr hm⟩      exact List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩)
See it in the graphDiscuss this resultChallenge it