AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_mul

theoremverified

Multiplying all rectangle coordinates by a positive integer a sends an admissible c-square partition to an admissible a times c square partition.

Statement

theorem mondrian_partition_mul (a c : ℕ) (ha : 0 < a)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition c P) :
    mondrian_is_partition (a * c) (P.map (mondrian_rect_mul 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 8
  • 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_mulMultiply all four rectangle coordinates by a.
  • mondrian_rect_mul_cellsA cell belongs to a rectangle with coordinates multiplied by positive a exactly when its quotient cell belongs to the original rectangle.
  • mondrian_rect_mul_dimensionsMultiplying coordinates by a multiplies both side lengths 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 theorem verifies the four conditions of an admissible partition for the scaled rectangles: size, non-degeneracy, pairwise disjointness and non-congruence, and exact coverage of the scaled square. List length and strict coordinate inequalities are preserved under scaling by a positive factor a. Disjointness, non-congruence, and square coverage reduce directly to the corresponding properties of the original partition because scaling scales dimensions linearly and maps a cell (i, j) to the scaled rectangle if and only if (⌊i/a⌋, ⌊j/a⌋) lies in the original rectangle.

  1. The scaled list contains at least two rectangles.

    Mapping the scaling function over the list P preserves its length by List.length_map. Because P has length at least 2 by hypothesis hp.1, the scaled list also has length at least 2.

    line 4

    uses List.length_map

      refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩
  2. Every rectangle in the scaled list is non-degenerate (has strictly positive width and height).

    Any rectangle r in the scaled list is the image mondrian_rect_mul a s of some rectangle s ∈ P (by List.mem_map.mp). Since P is a valid partition, s has strictly positive width and height. Multiplying these strict inequalities by the positive factor a via Nat.mul_lt_mul_of_pos_left shows that r also has strictly positive width and height.

    lines 5–8

    uses List.mem_map.mp, Nat.mul_lt_mul_of_pos_left

      · intro r hr
        obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr
        obtain ⟨hx, hy⟩ := hp.2.1 s hs
        exact ⟨Nat.mul_lt_mul_of_pos_left hx ha, Nat.mul_lt_mul_of_pos_left hy ha⟩
  3. The rectangles in the scaled list are pairwise disjoint and pairwise non-congruent.

    By List.pairwise_map, it suffices to show that if two rectangles r, s ∈ P are disjoint and non-congruent, their scalings remain disjoint and non-congruent. If a cell (i, j) belonged to both scaled rectangles, then (⌊i/a⌋, ⌊j/a⌋) would belong to both r and s by mondrian_rect_mul_cells, contradicting disjointness via Finset.disjoint_left.mp. Furthermore, mondrian_rect_mul_dimensions shows that scaling multiplies dimensions by a; if the scaled rectangles were congruent, cancelling the positive factor a using Nat.eq_of_mul_eq_mul_left would imply r and s are congruent, contradicting the non-congruence hypothesis.

    lines 9–34

    uses List.pairwise_map, Finset.disjoint_left, Finset.disjoint_left.mp, mondrian_rect_mul_cells, mondrian_rect_mul_dimensions, Nat.eq_of_mul_eq_mul_left

      · rw [List.pairwise_map]
        apply hp.2.2.1.imp
        intro r s hrs
        refine ⟨?_, ?_⟩
        · rw [Finset.disjoint_left]
          rintro ⟨i, j⟩ hi hj
          exact Finset.disjoint_left.mp hrs.1
            ((mondrian_rect_mul_cells a ha r i j).mp hi)
            ((mondrian_rect_mul_cells a ha s i j).mp hj)
        · intro hcong
          apply hrs.2
          obtain ⟨hrw, hrh⟩ := mondrian_rect_mul_dimensions a r
          obtain ⟨hsw, hsh⟩ := mondrian_rect_mul_dimensions a s
          rcases hcong with ⟨hw, hh⟩ | ⟨hw, hh⟩
          · left
            constructor
            · apply Nat.eq_of_mul_eq_mul_left ha
              simpa only [hrw, hsw] using hw
            · apply Nat.eq_of_mul_eq_mul_left ha
              simpa only [hrh, hsh] using hh
          · right
            constructor
            · apply Nat.eq_of_mul_eq_mul_left ha
              simpa only [hrw, hsh] using hw
            · apply Nat.eq_of_mul_eq_mul_left ha
              simpa only [hrh, hsw] using hh
  4. Every cell belonging to a scaled rectangle is contained in the scaled square [0, a * c) × [0, a * c).

    If a cell (i, j) belongs to some scaled rectangle mondrian_rect_mul a s for s ∈ P, then by mondrian_rect_mul_cells the cell (i / a, j / a) belongs to s, and thus to the union of rectangles in P. Since P partitions [0, c) × [0, c), we have i / a < c and j / a < c. By Nat.div_lt_iff_lt_mul and commutativity of multiplication, this is equivalent to i < a * c and j < a * c, showing that (i, j) lies in the product of ranges.

    lines 35–45

    uses Finset.mem_biUnion.mp, List.mem_map.mp, List.mem_toFinset.mp, mondrian_rect_mul_cells, Finset.mem_biUnion.mpr, List.mem_toFinset.mpr, Finset.mem_product, Finset.mem_range, Nat.div_lt_iff_lt_mul, Nat.mul_comm

      · 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_mul_cells a ha s i j).mp hi
          have hu : (i / a, j / a) ∈ P.toFinset.biUnion mondrian_rect_cells :=
            Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩
          rw [hp.2.2.2] at hu
          simpa only [Finset.mem_product, Finset.mem_range,
            Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hu
  5. Every cell in the scaled square [0, a * c) × [0, a * c) is covered by some scaled rectangle.

    Given a cell (i, j) in [0, a * c) × [0, a * c), the equivalence Nat.div_lt_iff_lt_mul ensures that (i / a, j / a) ∈ [0, c) × [0, c). Because P covers [0, c) × [0, c), there is some rectangle r ∈ P containing (i / a, j / a). Applying mondrian_rect_mul_cells in reverse shows that (i, j) belongs to mondrian_rect_mul a r, which is an element of the scaled partition.

    lines 46–54

    uses Finset.mem_product, Finset.mem_range, Nat.div_lt_iff_lt_mul, Nat.mul_comm, Finset.mem_biUnion.mp, Finset.mem_biUnion.mpr, mondrian_rect_mul_cells, List.mem_toFinset.mpr, List.mem_map.mpr, List.mem_toFinset.mp

        · intro hi
          have hu : (i / a, j / a) ∈ Finset.range c ×ˢ Finset.range c := by
            simpa only [Finset.mem_product, Finset.mem_range,
              Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hi
          rw [← hp.2.2.2] at hu
          obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu
          apply Finset.mem_biUnion.mpr
          refine ⟨mondrian_rect_mul a r, ?_, (mondrian_rect_mul_cells a ha r i j).mpr hm⟩
          exact List.mem_toFinset.mpr (List.mem_map.mpr ⟨r, List.mem_toFinset.mp hr, rfl⟩)
List.length_map
The length of a list is invariant under mapping a function over it.
List.mem_map.mp
An element belongs to the image of a list under a map if and only if it is the image of some element in the list.
List.mem_map.mpr
An element is in the image of a list under a map if it is the image of an element belonging to the list.
Nat.mul_lt_mul_of_pos_left
Multiplying both sides of a strict inequality by a positive natural number preserves the inequality.
List.pairwise_map
A mapped list satisfies a pairwise relation if and only if the original list satisfies the relation pulled back along the mapping function.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first set is in the second set.
Finset.disjoint_left.mp
If two finite sets are disjoint, any element of the first is not an element of the second.
mondrian_rect_mul_dimensions
Scaling a rectangle by a positive factor a multiplies both its width and its height by a.
mondrian_rect_mul_cells
A cell (i, j) belongs to a rectangle scaled by a if and only if (⌊i/a⌋, ⌊j/a⌋) belongs to the unscaled rectangle.
Nat.eq_of_mul_eq_mul_left
A strictly positive natural number can be cancelled from the left of an equality of products.
Finset.mem_biUnion.mp
An element belongs to a union of a family of finite sets only if it belongs to one of the sets in the family.
Finset.mem_biUnion.mpr
If an element belongs to one member of a family of finite sets, it belongs to the big union of the family.
List.mem_toFinset.mp
An element of the finite set constructed from a list is an element of that list.
List.mem_toFinset.mpr
An element belonging to a list belongs to the finite set constructed from that list.
Finset.mem_product
A pair belongs to a Cartesian product of 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 is in Finset.range n if and only if it is strictly less than n.
Nat.div_lt_iff_lt_mul
For a positive divisor k, integer division x / k < y is equivalent to x < y * k.
Nat.mul_comm
Multiplication of natural numbers is commutative.

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_mul (a c : ℕ) (ha : 0 < a)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : mondrian_is_partition c P) :    mondrian_is_partition (a * c) (P.map (mondrian_rect_mul a)) := by  refine ⟨by simpa only [List.length_map] using hp.1, ?_, ?_, ?_⟩  · intro r hr    obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr    obtain ⟨hx, hy⟩ := hp.2.1 s hs    exact ⟨Nat.mul_lt_mul_of_pos_left hx ha, Nat.mul_lt_mul_of_pos_left hy ha⟩  · rw [List.pairwise_map]    apply hp.2.2.1.imp    intro r s hrs    refine ⟨?_, ?_⟩    · rw [Finset.disjoint_left]      rintro ⟨i, j⟩ hi hj      exact Finset.disjoint_left.mp hrs.1        ((mondrian_rect_mul_cells a ha r i j).mp hi)        ((mondrian_rect_mul_cells a ha s i j).mp hj)    · intro hcong      apply hrs.2      obtain ⟨hrw, hrh⟩ := mondrian_rect_mul_dimensions a r      obtain ⟨hsw, hsh⟩ := mondrian_rect_mul_dimensions a s      rcases hcong with ⟨hw, hh⟩ | ⟨hw, hh⟩      · left        constructor        · apply Nat.eq_of_mul_eq_mul_left ha          simpa only [hrw, hsw] using hw        · apply Nat.eq_of_mul_eq_mul_left ha          simpa only [hrh, hsh] using hh      · right        constructor        · apply Nat.eq_of_mul_eq_mul_left ha          simpa only [hrw, hsh] using hw        · apply Nat.eq_of_mul_eq_mul_left ha          simpa only [hrh, hsw] using 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_mul_cells a ha s i j).mp hi      have hu : (i / a, j / a) ∈ P.toFinset.biUnion mondrian_rect_cells :=        Finset.mem_biUnion.mpr ⟨s, List.mem_toFinset.mpr hs, hi'⟩      rw [hp.2.2.2] at hu      simpa only [Finset.mem_product, Finset.mem_range,        Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hu    · intro hi      have hu : (i / a, j / a) ∈ Finset.range c ×ˢ Finset.range c := by        simpa only [Finset.mem_product, Finset.mem_range,          Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] using hi      rw [← hp.2.2.2] at hu      obtain ⟨r, hr, hm⟩ := Finset.mem_biUnion.mp hu      apply Finset.mem_biUnion.mpr      refine ⟨mondrian_rect_mul a r, ?_, (mondrian_rect_mul_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