AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_swap

theoremverified

Exchanging the x and y coordinate pairs of every rectangle preserves an admissible partition of the n-square.

Statement

theorem mondrian_partition_swap (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (hp : mondrian_is_partition n P) :
    mondrian_is_partition n (P.map mondrian_rect_swap)
Source
Helper for OP-280: modular shape inventories for the zero-defect question in arXiv:2610.19193, Section 1. The weighted row and prime-free count argument is developed here; it supplements the available-shape counting in arXiv:2311.02385, Section 3.
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_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_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_swapExchange the x and y coordinate pairs of an integer rectangle.
  • mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
Used by 4

The proof, explained

To prove that exchanging the x and y coordinates of every rectangle preserves an admissible partition of the n × n square, the proof verifies the four partition conditions for the mapped list. The key observation is that swapping a rectangle's coordinate intervals transposes its constituent grid cells, so (x, y) belongs to the swapped rectangle if and only if (y, x) belonged to the original. Because mapping preserves list length, non-degeneracy merely exchanges the width and height strict inequalities, and rectangle congruence is symmetric under interchanging width and height, the swapped rectangles remain non-degenerate, pairwise disjoint, and pairwise non-congruent. Finally, the swapped rectangles cover the n × n square because the square itself is invariant under coordinate transposition.

  1. A cell (x, y) belongs to the swapped rectangle if and only if the transposed cell (y, x) belongs to the original rectangle.

    Unfolding the definitions of rectangle swap and rectangle cells, the membership (x, y) ∈ [y₁, y₂) × [x₁, x₂) reduces by Finset.mem_product and Finset.mem_Ico to (y₁ ≤ x ∧ x < y₂) ∧ (x₁ ≤ y ∧ y < x₂). Propositional logic reorders this conjunction to (x₁ ≤ y ∧ y < x₂) ∧ (y₁ ≤ x ∧ x < y₂), which is exactly the condition that (y, x) ∈ [x₁, x₂) × [y₁, y₂).

    lines 6–11

    uses Finset.mem_product, Finset.mem_Ico

      have hcell : ∀ r : ℕ × ℕ × ℕ × ℕ, ∀ x y : ℕ,
          (x, y) ∈ mondrian_rect_cells (mondrian_rect_swap r) ↔
            (y, x) ∈ mondrian_rect_cells r := by
        intro r x y
        simp only [mondrian_rect_swap, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico]
        tauto
  2. The swapped partition contains at least two rectangles.

    The first requirement of an admissible partition is that the list of rectangles has length at least 2. Mapping the coordinate swap over the list preserves list length by List.length_map, so the swapped list has the same length as P, which is at least 2.

    line 12

    uses List.length_map

      refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩
  3. Every rectangle in the swapped list is non-degenerate.

    For every rectangle r in the swapped list, List.mem_map.mp yields a rectangle s in P such that r is the swap of s. Since s has positive width and positive height (s₁ < s₂ and s₃ < s₄), the swapped rectangle r, whose width is s₄ - s₃ and height is s₂ - s₁, also has positive width and positive height (s₃ < s₄ and s₁ < s₂).

    lines 13–15

    uses List.mem_map.mp

      · intro r hr
        obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr
        exact ⟨(hp.2.1 s hs).2, (hp.2.1 s hs).1⟩
  4. The rectangles in the swapped partition remain pairwise disjoint and pairwise non-congruent.

    By List.pairwise_map, it suffices to show that if two rectangles r and s in P are disjoint and non-congruent, then their swaps are also disjoint and non-congruent. For disjointness, if a cell (x, y) belonged to both swapped rectangles, the cell transposition equivalence from the first step would place (y, x) in both original rectangles r and s, contradicting their disjointness via Finset.disjoint_left and Finset.disjoint_left.mp. For non-congruence, two rectangles are congruent when their dimensions match up to reordering; since swapping interchanges width and height, congruence is invariant under swapping, so the non-congruence of r and s implies the non-congruence of their swaps.

    lines 16–27

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

      · rw [List.pairwise_map]
        apply hp.2.2.1.imp
        intro r s hrs
        refine ⟨?_, ?_⟩
        · rw [Finset.disjoint_left]
          rintro ⟨x, y⟩ hr hs
          exact Finset.disjoint_left.mp hrs.1 ((hcell r x y).mp hr) ((hcell s x y).mp hs)
        · intro hc
          apply hrs.2
          simp only [mondrian_rect_congruent, mondrian_rect_width,
            mondrian_rect_height, mondrian_rect_swap] at hc ⊢
          tauto
  5. The union of the cells of the swapped rectangles is the full n × n grid.

    Set extensionality reduces the claim to showing that (x, y) is covered by the swapped partition if and only if (x, y) ∈ {0, …, n - 1}². In the forward direction, if (x, y) lies in the swapped partition, decomposing the membership with Finset.mem_biUnion.mp, List.mem_toFinset.mp, and List.mem_map.mp yields an original rectangle s containing (y, x). Recombining via Finset.mem_biUnion.mpr and List.mem_toFinset.mpr shows that (y, x) is in the union of P, which is the n × n square. By Finset.mem_product, Finset.mem_range, and commutativity of conjunction (and_comm), (y, x) ∈ {0, …, n - 1}² implies (x, y) ∈ {0, …, n - 1}². In the reverse direction, if (x, y) is in the square, then (y, x) is also in the square by Finset.mem_product, Finset.mem_range, and and_comm, hence (y, x) is covered by some rectangle r ∈ P via Finset.mem_biUnion.mp. The swapped rectangle of r belongs to the mapped partition by List.mem_toFinset.mpr and List.mem_map.mpr, and contains (x, y) by transposition, completing the union via Finset.mem_biUnion.mpr.

    lines 28–45

    uses Finset.mem_biUnion.mp, List.mem_map.mp, List.mem_toFinset.mp, Finset.mem_biUnion.mpr, List.mem_toFinset.mpr, Finset.mem_product, Finset.mem_range, and_comm, List.mem_map.mpr

      · ext ⟨x, y⟩
        constructor
        · intro h
          obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp h
          obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr)
          have hu : (y, x) ∈ P.toFinset.biUnion mondrian_rect_cells :=
            Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, (hcell s x y).mp hc⟩
          rw [hp.2.2.2] at hu
          simpa only [Finset.mem_product, Finset.mem_range, and_comm] using hu
        · intro h
          have hu : (y, x) ∈ Finset.range n ×ˢ Finset.range n := by
            simpa only [Finset.mem_product, Finset.mem_range, and_comm] using h
          rw [← hp.2.2.2] at hu
          obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp hu
          apply Finset.mem_biUnion.mpr
          exact ⟨mondrian_rect_swap r,
            List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩),
            (hcell r x y).mpr hc⟩
and_comm
Conjunction is commutative: a ∧ b is logically equivalent to b ∧ a.
Finset.disjoint_left
Two finite sets are disjoint if and only if every element of the first set is not in the second set.
Finset.disjoint_left.mp
If two finite sets are disjoint, any element belonging to the first set cannot belong to the second set.
Finset.mem_Ico
An element x belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
Finset.mem_product
A pair (x, y) belongs to the Cartesian product s ×ˢ t if and only if x ∈ s and y ∈ t.
Finset.mem_range
A natural number m belongs to the range {0, …, n - 1} if and only if m < n.
Finset.mem_biUnion.mp
If an element belongs to a big union ⋃_{a ∈ s} t(a), then it belongs to t(a) for some a ∈ s.
Finset.mem_biUnion.mpr
If an element belongs to t(a) for some a ∈ s, then it belongs to the big union ⋃_{a ∈ s} t(a).
List.length_map
Mapping a function over a list preserves its length: length(f(L)) = length(L).
List.mem_map.mp
If an element is in the image List.map f l, then it equals f(a) for some a ∈ l.
List.mem_map.mpr
If an element a is in a list l, then f(a) belongs to List.map f l.
List.mem_toFinset.mp
If an element belongs to the Finset representation of a list, then it belongs to the list.
List.mem_toFinset.mpr
If an element belongs to a list, then it belongs to the Finset representation of that list.
List.pairwise_map
A mapped list List.map f l is pairwise related by R if and only if the original list l is pairwise related by (a, b) ↦ R (f a) (f 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

open scoped BigOperatorstheorem mondrian_partition_swap (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (hp : mondrian_is_partition n P) :    mondrian_is_partition n (P.map mondrian_rect_swap) := by  have hcell : ∀ r : ℕ × ℕ × ℕ × ℕ, ∀ x y : ℕ,      (x, y) ∈ mondrian_rect_cells (mondrian_rect_swap r) ↔        (y, x) ∈ mondrian_rect_cells r := by    intro r x y    simp only [mondrian_rect_swap, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico]    tauto  refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩  · intro r hr    obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr    exact ⟨(hp.2.1 s hs).2, (hp.2.1 s hs).1⟩  · rw [List.pairwise_map]    apply hp.2.2.1.imp    intro r s hrs    refine ⟨?_, ?_⟩    · rw [Finset.disjoint_left]      rintro ⟨x, y⟩ hr hs      exact Finset.disjoint_left.mp hrs.1 ((hcell r x y).mp hr) ((hcell s x y).mp hs)    · intro hc      apply hrs.2      simp only [mondrian_rect_congruent, mondrian_rect_width,        mondrian_rect_height, mondrian_rect_swap] at hc ⊢      tauto  · ext ⟨x, y⟩    constructor    · intro h      obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp h      obtain ⟨s, hs, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hr)      have hu : (y, x) ∈ P.toFinset.biUnion mondrian_rect_cells :=        Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, (hcell s x y).mp hc⟩      rw [hp.2.2.2] at hu      simpa only [Finset.mem_product, Finset.mem_range, and_comm] using hu    · intro h      have hu : (y, x) ∈ Finset.range n ×ˢ Finset.range n := by        simpa only [Finset.mem_product, Finset.mem_range, and_comm] using h      rw [← hp.2.2.2] at hu      obtain ⟨r, hr, hc⟩ := Finset.mem_biUnion.mp hu      apply Finset.mem_biUnion.mpr      exact ⟨mondrian_rect_swap r,        List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩),        (hcell r x y).mpr hc⟩
See it in the graphDiscuss this resultChallenge it