mondrian_perfect_height_injective
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
- mondrian_partition_width_dvd_of_height_two_chainsIf d divides the square side and all width-indivisible tiles have heights in two superincreasing chains C*p^a and C*r*p^a, with p>r+1 and…
- mondrian_partition_width_dvd_of_height_prime_chainSuppose d divides the square side and all tiles whose widths are indivisible by d have heights C times powers of a fixed prime p, with…
- mondrian_perfect_width_free_count_ne_twoIn a perfect admissible square partition, for any divisor d of the square side, exactly two tiles cannot have widths indivisible by d.
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.
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.
uses
mondrian_defect_zero_equal,mondrian_partition_bounds,Nat.eq_of_mul_eq_mul_right,Or.inlhave 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⟩)
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.
uses
List.nodup_iff_pairwise_ne,List.pairwise_maphave hn : (P.map mondrian_rect_height).Nodup := by rw [List.nodup_iff_pairwise_ne, List.pairwise_map] exact hpw
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.
uses
List.inj_on_of_nodup_mapintro 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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