AFTD Auto-Formalizing Theoretical Domains

mondrian_shape_bound

theoremverified

A partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.

Statement

theorem mondrian_shape_bound (n A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (h : mondrian_is_partition n P)
    (hA : ∀ r ∈ P, mondrian_rect_area r = A) :
    P.length ≤ (mondrian_factor_shapes n A).card
Source
arXiv:2610.19193, Section 1, and arXiv:2311.02385, Section 3 (available integer dimension pairs); helper for OP-280 and mondrian_no_perfect_partition.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • mondrian_partition_boundsEvery rectangle of an admissible n-square partition has positive side lengths, upper coordinates at most n, and side lengths at most n.
  • mondrian_mem_factor_shapesA dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its…
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
  • 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_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
  • 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_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 3
  • mondrian_large_prime_descentIf c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the…
  • 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…
  • mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…

The proof, explained

The proof defines a canonical shape function f(r) mapping each rectangle to its sorted dimension pair (min(w, h), max(w, h)). Because a Mondrian partition forbids congruent rectangles, distinct rectangles have distinct shapes under f, so the mapped list has no duplicates. Each rectangle has area A and fits in the n-square, so its shape belongs to the finite set of valid factor shapes of A. The desired bound then follows from the monotonicity of finite set cardinality.

  1. The canonical shape mapping f(r) = (min(width, height), max(width, height)) distinguishes non-congruent rectangles.

    We define f(r) as the sorted pair of dimensions of rectangle r. If f(r) = f(s), projecting to the first and second components via congrArg with Prod.fst and Prod.snd shows that r and s share the same minimum and maximum dimensions. By definition of rectangle congruence (mondrian_rect_congruent), two rectangles whose dimensions share the same minimum and maximum are either identical or transposed, which linear arithmetic (omega) verifies.

    lines 5–13

    uses congrArg, Prod.fst, Prod.snd

      let f := fun r => (min (mondrian_rect_width r) (mondrian_rect_height r),
        max (mondrian_rect_width r) (mondrian_rect_height r))
      have hinj : ∀ r s, f r = f s → mondrian_rect_congruent r s := by
        intro r s he
        have he1 := congrArg Prod.fst he
        have he2 := congrArg Prod.snd he
        dsimp [f] at he1 he2
        unfold mondrian_rect_congruent
        omega
  2. The list of rectangle shapes in the partition contains no duplicates.

    By List.nodup_iff_pairwise_ne and List.pairwise_map, a mapped list is duplicate-free exactly when f(r) ≠ f(s) for all distinct pairs in the list. By definition of a Mondrian partition, distinct rectangles in P are non-congruent. Since identical shapes imply congruence, non-congruence implies distinct shapes, so P.map f has no duplicates.

    lines 14–16

    uses List.nodup_iff_pairwise_ne, List.pairwise_map

      have hn : (P.map f).Nodup := by
        rw [List.nodup_iff_pairwise_ne, List.pairwise_map]
        exact h.2.2.1.imp (fun hh he => hh.2 (hinj _ _ he))
  3. The set of shapes in the partition is a subset of the factor shapes of area A in the n-square.

    Any element of the image set is f(r) for some rectangle r in P (by List.mem_toFinset.mp and List.mem_map.mp). By mondrian_partition_bounds, r has strictly positive width and height bounded by n. According to mondrian_mem_factor_shapes, f(r) is a valid factor shape because: (1) min(w, h) * max(w, h) = w * h = A by min_mul_max and the area hypothesis hA; (2) A ≠ 0 by Nat.mul_pos and Nat.ne_of_gt since w > 0 and h > 0; (3) min(w, h) ≤ max(w, h) holds by definition; and (4) max(w, h) ≤ n since both w ≤ n and h ≤ n.

    lines 17–27

    uses List.mem_toFinset.mp, List.mem_map.mp, mondrian_partition_bounds, mondrian_mem_factor_shapes, min_mul_max, Nat.ne_of_gt, Nat.mul_pos

      have hsub : (P.map f).toFinset ⊆ mondrian_factor_shapes n A := by
        intro d hd
        obtain ⟨r, hr, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hd)
        obtain ⟨hx, hy, hw, hh, hwn, hhn⟩ := mondrian_partition_bounds n P h r hr
        apply (mondrian_mem_factor_shapes n A (f r)).mpr
        refine ⟨?_, ?_, by dsimp [f]; omega, by dsimp [f]; omega⟩
        · dsimp [f]
          rw [min_mul_max]
          exact hA r hr
        · rw [← hA r hr]
          exact Nat.ne_of_gt (Nat.mul_pos hw hh)
  4. The number of rectangles in the partition is bounded by the cardinality of the factor shapes.

    Since the finite set of shapes in P is a subset of the factor shapes, its cardinality is at most that of mondrian_factor_shapes n A (by Finset.card_le_card). Because the list of shapes has no duplicates, its cardinality equals its length (List.toFinset_card_of_nodup), which in turn equals the length of P (List.length_map). Simplifying with these equalities yields the bound P.length ≤ (mondrian_factor_shapes n A).card.

    lines 28–29

    uses Finset.card_le_card, List.toFinset_card_of_nodup, List.length_map

      have hc := Finset.card_le_card hsub
      simpa only [List.toFinset_card_of_nodup hn, List.length_map] using hc
congrArg
Applying a function to equal inputs yields equal outputs: if a₁ = a₂, then f(a₁) = f(a₂).
Prod.fst
The first projection of an ordered pair, extracting its first component.
Prod.snd
The second projection of an ordered pair, extracting its second component.
List.nodup_iff_pairwise_ne
A list has no duplicate elements if and only if every pair of distinct positions holds unequal elements.
List.pairwise_map
A relation holds pairwise on a mapped list l.map f if and only if the pulled-back relation holds pairwise on the original list l.
List.mem_toFinset.mp
If an element belongs to the finite set converted from a list, then it is an element of the list.
List.mem_map.mp
If an element is in the image list l.map f, then it is the image f(x) of some element x in l.
mondrian_partition_bounds
In a Mondrian partition of an n-square, every rectangle has strictly positive width and height bounded above by n.
mondrian_mem_factor_shapes
A pair of dimensions (d₁, d₂) belongs to the factor shapes of area A in an n-square if and only if d₁ * d₂ = A, A ≠ 0, d₁ ≤ d₂, and d₂ ≤ n.
min_mul_max
The product of the minimum and maximum of two numbers equals their ordinary product: min(a, b) * max(a, b) = a * b.
Nat.ne_of_gt
If a natural number is strictly greater than another, they are unequal.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most that of the superset.
List.toFinset_card_of_nodup
Converting a list with no duplicates to a finite set preserves its length as the set cardinality.
List.length_map
Mapping a function over a list preserves the length of the list.

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_shape_bound (n A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (h : mondrian_is_partition n P)    (hA : ∀ r ∈ P, mondrian_rect_area r = A) :    P.length ≤ (mondrian_factor_shapes n A).card := by  let f := fun r => (min (mondrian_rect_width r) (mondrian_rect_height r),    max (mondrian_rect_width r) (mondrian_rect_height r))  have hinj : ∀ r s, f r = f s → mondrian_rect_congruent r s := by    intro r s he    have he1 := congrArg Prod.fst he    have he2 := congrArg Prod.snd he    dsimp [f] at he1 he2    unfold mondrian_rect_congruent    omega  have hn : (P.map f).Nodup := by    rw [List.nodup_iff_pairwise_ne, List.pairwise_map]    exact h.2.2.1.imp (fun hh he => hh.2 (hinj _ _ he))  have hsub : (P.map f).toFinset ⊆ mondrian_factor_shapes n A := by    intro d hd    obtain ⟨r, hr, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hd)    obtain ⟨hx, hy, hw, hh, hwn, hhn⟩ := mondrian_partition_bounds n P h r hr    apply (mondrian_mem_factor_shapes n A (f r)).mpr    refine ⟨?_, ?_, by dsimp [f]; omega, by dsimp [f]; omega⟩    · dsimp [f]      rw [min_mul_max]      exact hA r hr    · rw [← hA r hr]      exact Nat.ne_of_gt (Nat.mul_pos hw hh)  have hc := Finset.card_le_card hsub  simpa only [List.toFinset_card_of_nodup hn, List.length_map] using hc
See it in the graphDiscuss this resultChallenge it