mondrian_perfect_partition_div_common_area
If q divides the square side and both dimensions of every tile in a perfect partition, and the common area is q^2 times B, coordinate division gives a perfect partition of the n/q square with common area B.
Statement
theorem mondrian_perfect_partition_div_common_area (n q A B : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
(hq : 0 < q) (hqn : q ∣ n) (hP : mondrian_is_partition n P)
(hz : mondrian_defect P = 0) (harea : ∀ r ∈ P, mondrian_rect_area r = A)
(hAB : A = q ^ 2 * B)
(hd : ∀ r ∈ P, q ∣ mondrian_rect_width r ∧ q ∣ mondrian_rect_height r) :
∃ Q, mondrian_is_partition (n / q) Q ∧ mondrian_defect Q = 0 ∧
∀ r ∈ Q, mondrian_rect_area r = B- 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 10
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_perfect_partition_divDividing coordinates by a preserves perfect admissible partitions when a is positive and divides every tile side.
- mondrian_rect_areaThe area |R| = width × height of a rectangle.
- mondrian_rect_divDivide all four rectangle coordinates by a using natural-number division.
- mondrian_rect_div_dimensionsDividing coordinates of a positive rectangle whose side lengths are multiples of a divides its width and height exactly 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).
- 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_no_perfect_three_prime_area_one_factorFor three distinct primes p,q,r with p>r+1, no perfect admissible integer square partition has common tile area q^s*r*p^a, for arbitrary…
- mondrian_no_perfect_prime_power_areaNo perfect admissible partition of any integer square can have common tile area equal to a prime power p^t, including exponent zero.
- mondrian_no_perfect_two_prime_areaFor any distinct primes p and q and natural exponents s and t, no perfect admissible partition of any integer square can have common tile…
The proof, explained
The candidate partition Q is obtained by dividing the coordinates of each rectangle in P by q. Since q divides n, the square side factors as q * (n / q), so the lemma mondrian_perfect_partition_div applies to show Q is a defect-0 partition of the (n / q) square. The dimensions of each scaled tile r ∈ Q are 1/q of those of the original tile s ∈ P, so area(r) is scaled down by q^2; cancelling q^2 > 0 from q^2 * area(r) = area(s) = A = q^2 * B establishes that every tile in Q has area B.
The scaled rectangle list Q is a defect-0 partition of the (n / q) × (n / q) square, reducing the goal to verifying the common area condition.
Define Q by dividing the coordinates of every rectangle in P by q. Since q ∣ n, Nat.mul_div_cancel' rewrites n as q * (n / q), viewing P as partitioning a square of side q * (n / q). Applying the scaling theorem mondrian_perfect_partition_div proves that Q is a partition of the (n / q) × (n / q) square with defect 0. Providing Q and these two facts reduces the existential goal to showing that every tile in Q has area B.
uses
Nat.mul_div_cancel',mondrian_perfect_partition_divlet Q := P.map (mondrian_rect_div q) have hP' : mondrian_is_partition (q * (n / q)) P := by simpa only [Nat.mul_div_cancel' hqn] using hP have hQ := mondrian_perfect_partition_div q (n / q) hq P hP' hz hd refine ⟨Q, hQ.1, hQ.2, ?_⟩
Any tile r ∈ Q is the scaled version of some tile s ∈ P, and its width and height are scaled down by q.
Let r ∈ Q. Because Q is the map of P under coordinate division by q, List.mem_map.mp provides a rectangle s ∈ P such that r = mondrian_rect_div q s. Since s has positive width and height (from partition hypothesis hP) and both dimensions are multiples of q (from hd), mondrian_rect_div_dimensions yields q * width(r) = width(s) and q * height(r) = height(s).
uses
List.mem_map.mp,mondrian_rect_div_dimensionsintro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr obtain ⟨hw, hh⟩ := mondrian_rect_div_dimensions q hq s (hP.2.1 s hs).1 (hP.2.1 s hs).2 (hd s hs).1 (hd s hs).2
To show area(r) = B, it suffices to prove q^2 * area(r) = q^2 * B.
Since q > 0, pow_pos ensures q^2 > 0. By Nat.eq_of_mul_eq_mul_left, cancelling the positive factor q^2 from both sides reduces the target equality area(r) = B to q^2 * area(r) = q^2 * B.
uses
Nat.eq_of_mul_eq_mul_left,pow_posapply Nat.eq_of_mul_eq_mul_left (pow_pos hq 2)The equality q^2 * area(r) = q^2 * B holds.
By the definition of rectangle area, q^2 * area(r) expands to (q * width(r)) * (q * height(r)). Substituting the dimension equalities gives width(s) * height(s), which is area(s). Since every rectangle in P has area A and A = q^2 * B, this equals q^2 * B, completing the proof.
calc q ^ 2 * mondrian_rect_area (mondrian_rect_div q s) = mondrian_rect_area s := by calc q ^ 2 * mondrian_rect_area (mondrian_rect_div q s) = (q * mondrian_rect_width (mondrian_rect_div q s)) * (q * mondrian_rect_height (mondrian_rect_div q s)) := by dsimp [mondrian_rect_area] ring _ = mondrian_rect_area s := by rw [hw, hh]; rfl _ = q ^ 2 * B := by rw [harea s hs, hAB]
Nat.mul_div_cancel'- If n divides m, then n * (m / n) = m.
mondrian_perfect_partition_div- If P is a defect-0 partition of the (a * c) × (a * c) square and a > 0 divides both dimensions of every rectangle in P, then scaling all coordinates down by a gives a defect-0 partition of the c × c square.
List.mem_map.mp- If an element belongs to the image of a list under a function, then it is the image of some element of that list.
mondrian_rect_div_dimensions- For a valid rectangle whose width and height are divisible by a > 0, scaling coordinates down by a and then multiplying the new width and height by a recovers the original dimensions.
Nat.eq_of_mul_eq_mul_left- If n > 0 and n * m = n * k, then m = k (left cancellation in ℕ).
pow_pos- A strictly positive element raised to any natural power is strictly positive.
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_partition_div_common_area (n q A B : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hq : 0 < q) (hqn : q ∣ n) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (harea : ∀ r ∈ P, mondrian_rect_area r = A) (hAB : A = q ^ 2 * B) (hd : ∀ r ∈ P, q ∣ mondrian_rect_width r ∧ q ∣ mondrian_rect_height r) : ∃ Q, mondrian_is_partition (n / q) Q ∧ mondrian_defect Q = 0 ∧ ∀ r ∈ Q, mondrian_rect_area r = B := by let Q := P.map (mondrian_rect_div q) have hP' : mondrian_is_partition (q * (n / q)) P := by simpa only [Nat.mul_div_cancel' hqn] using hP have hQ := mondrian_perfect_partition_div q (n / q) hq P hP' hz hd refine ⟨Q, hQ.1, hQ.2, ?_⟩ intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr obtain ⟨hw, hh⟩ := mondrian_rect_div_dimensions q hq s (hP.2.1 s hs).1 (hP.2.1 s hs).2 (hd s hs).1 (hd s hs).2 apply Nat.eq_of_mul_eq_mul_left (pow_pos hq 2) calc q ^ 2 * mondrian_rect_area (mondrian_rect_div q s) = mondrian_rect_area s := by calc q ^ 2 * mondrian_rect_area (mondrian_rect_div q s) = (q * mondrian_rect_width (mondrian_rect_div q s)) * (q * mondrian_rect_height (mondrian_rect_div q s)) := by dsimp [mondrian_rect_area] ring _ = mondrian_rect_area s := by rw [hw, hh]; rfl _ = q ^ 2 * B := by rw [harea s hs, hAB]