AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_height_injective

theoremverified

The heights of the tiles in a perfect admissible square partition are pairwise distinct.

Statement

theorem mondrian_perfect_height_injective (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) :
    ∀ r ∈ P, ∀ s ∈ P, mondrian_rect_height r = mondrian_rect_height s → r = s
Source
For OP-280, arXiv:2610.19193, Section 1. Related work: arXiv:2007.09639, Theorem 4.1; HAL:hal-05729522v2, Lemma 2.3 (primitive cross sections and common-side descent). The periodic residue argument and the uniform two-prime common-area exclusion are developed here.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
  • mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
  • 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_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_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).
Used by 3

The proof, explained

To show that heights in a zero-defect square partition are pairwise distinct, we first observe that zero defect implies all rectangles have equal area. If two distinct rectangles had the same height, dividing their equal areas by this positive height would force their widths to be equal as well, making them congruent and contradicting the partition requirement. Thus, the heights of rectangles in the partition are pairwise distinct, so the list of heights contains no duplicate elements. Injectivity of the height function on the partition then follows directly.

  1. The rectangles in P have pairwise distinct heights.

    By the definition of an admissible partition, distinct rectangles in P cannot be congruent. To show their heights are pairwise distinct, suppose for contradiction that two rectangles r, s ∈ P share the same height. Because the partition has defect zero, mondrian_defect_zero_equal ensures they have the same area. Since r has strictly positive height by mondrian_partition_bounds, cancelling the common height from the area equation via Nat.eq_of_mul_eq_mul_right proves that r and s also have the same width. But having identical widths and heights means the two rectangles are congruent (via Or.inl), contradicting the partition condition. Hence, no two distinct rectangles share the same height.

    lines 4–13

    uses mondrian_defect_zero_equal, mondrian_partition_bounds, Nat.eq_of_mul_eq_mul_right, Or.inl

      have hpw : P.Pairwise (fun r s => mondrian_rect_height r ≠ mondrian_rect_height s) := by
        apply hP.2.2.1.imp_of_mem
        intro r s hr hs hrs he
        have harea := mondrian_defect_zero_equal P hz r s hr hs
        have hb := mondrian_partition_bounds n P hP r hr
        have hw : mondrian_rect_width r = mondrian_rect_width s := by
          dsimp [mondrian_rect_area] at harea
          rw [← he] at harea
          exact Nat.eq_of_mul_eq_mul_right hb.2.2.2.1 harea
        exact hrs.2 (Or.inl ⟨hw, he⟩)
  2. The list of heights of rectangles in P contains no duplicate entries.

    By List.nodup_iff_pairwise_ne, a list has no duplicates if and only if its elements are pairwise unequal. Applying List.pairwise_map translates this to the requirement that rectangle heights are pairwise distinct along P, which was proved in the preceding step.

    lines 14–16

    uses List.nodup_iff_pairwise_ne, List.pairwise_map

      have hn : (P.map mondrian_rect_height).Nodup := by
        rw [List.nodup_iff_pairwise_ne, List.pairwise_map]
        exact hpw
  3. The height function is injective on the rectangles in P.

    Given two rectangles r, s ∈ P with equal heights, List.inj_on_of_nodup_map applies the duplicate-free property of the mapped heights list to conclude that r = s.

    lines 17–18

    uses List.inj_on_of_nodup_map

      intro r hr s hs he
      exact List.inj_on_of_nodup_map hn hr hs he
mondrian_defect_zero_equal
In a partition with zero defect, any two rectangles have equal area.
mondrian_partition_bounds
Every rectangle in an admissible partition of an n × n square has strictly positive width and height bounded by n.
Nat.eq_of_mul_eq_mul_right
For natural numbers, if n * m = k * m and m > 0, then n = k.
Or.inl
If a is true, then the disjunction a ∨ b is true.
List.nodup_iff_pairwise_ne
A list contains no duplicate elements if and only if its elements are pairwise distinct.
List.pairwise_map
A relation holds pairwise on a mapped list map(f, l) if and only if the relation composed with f holds pairwise on l.
List.inj_on_of_nodup_map
If the image of a list under a function f has no duplicates, then f is injective on the elements of that 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_perfect_height_injective (n : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) :    ∀ r ∈ P, ∀ s ∈ P, mondrian_rect_height r = mondrian_rect_height s → r = s := by  have hpw : P.Pairwise (fun r s => mondrian_rect_height r ≠ mondrian_rect_height s) := by    apply hP.2.2.1.imp_of_mem    intro r s hr hs hrs he    have harea := mondrian_defect_zero_equal P hz r s hr hs    have hb := mondrian_partition_bounds n P hP r hr    have hw : mondrian_rect_width r = mondrian_rect_width s := by      dsimp [mondrian_rect_area] at harea      rw [← he] at harea      exact Nat.eq_of_mul_eq_mul_right hb.2.2.2.1 harea    exact hrs.2 (Or.inl ⟨hw, he⟩)  have hn : (P.map mondrian_rect_height).Nodup := by    rw [List.nodup_iff_pairwise_ne, List.pairwise_map]    exact hpw  intro r hr s hs he  exact List.inj_on_of_nodup_map hn hr hs he
See it in the graphDiscuss this resultChallenge it