mondrian_two_prime_area_sides_dvd
For a perfect admissible square partition with common area q^s*p^t and q dividing the square side, both dimensions of every tile are divisible by q.
Statement
theorem mondrian_two_prime_area_sides_dvd (n p q s t : ℕ)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q)
(hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n)
(harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) :
∀ r ∈ P, q ∣ mondrian_rect_width r ∧ q ∣ mondrian_rect_height r- 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_of_equalA rectangle list whose members all have the same area has defect zero, including the empty list.
- 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_swapExchanging the x and y coordinate pairs of every rectangle preserves an admissible partition of the n-square.
- 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_swapExchange the x and y coordinate pairs of an integer rectangle.
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_two_prime_area_width_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, every tile width is divisible by q.
- Used by 3
- 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…
- mondrian_no_perfect_two_prime_powersFor any two distinct primes p and q and arbitrary natural exponents e and f, the square of side q^f*p^e has no perfect admissible integer…
The proof, explained
The theorem is proved by combining the width divisibility result with symmetry across the diagonal. First, the auxiliary theorem mondrian_two_prime_area_width_dvd directly shows that q divides the width of every rectangle in the partition. Reflecting the partition across the diagonal produces another valid defect-0 partition with identical tile areas, so applying the same width divisibility result to the reflected partition shows that q divides the width of every reflected rectangle. Since the width of a reflected tile is the height of the original tile, q divides both dimensions of every rectangle in the partition.
For every rectangle in P, q divides its width.
Applying the previously proved theorem mondrian_two_prime_area_width_dvd directly to the partition P establishes that q divides the width of every rectangle, since P is a defect-0 partition of the n × n square with q ∣ n and all tiles having area q^s * p^t.
uses
mondrian_two_prime_area_width_dvdhave hw := mondrian_two_prime_area_width_dvd n p q s t P hp hq hP hz hqn hareaThe swapped partition is a valid partition of the n × n square with defect 0 and common tile area q^s * p^t.
Reflecting each rectangle across the diagonal via mondrian_rect_swap produces another partition of the square (mondrian_partition_swap). For each rectangle r in this swapped partition, r is the swap of some tile u ∈ P (List.mem_map.mp). Coordinate swapping interchanges width and height, so by commutativity of multiplication (Nat.mul_comm), the area of r equals the area of u, namely q^s * p^t. Since all tiles in the swapped partition have equal area, its defect is 0 by mondrian_defect_zero_of_equal.
uses
mondrian_partition_swap,List.mem_map.mp,Nat.mul_comm,mondrian_defect_zero_of_equalhave hswapP := mondrian_partition_swap n P hP have hswapA : ∀ r ∈ P.map mondrian_rect_swap, mondrian_rect_area r = q ^ s * p ^ t := by intro r hr obtain ⟨u, hu, rfl⟩ := List.mem_map.mp hr have hh := harea u hu simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap, Nat.mul_comm] using hh have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * p ^ t) hswapA
For every rectangle in the swapped partition, q divides its width.
Applying mondrian_two_prime_area_width_dvd to the swapped partition (which was shown to be valid, have defect 0, and have all tile areas equal to q^s * p^t) establishes that q divides the width of every swapped tile.
uses
mondrian_two_prime_area_width_dvdhave hh := mondrian_two_prime_area_width_dvd n p q s t (P.map mondrian_rect_swap) hp hq hswapP hswapZ hqn hswapAFor every rectangle r ∈ P, q divides both the width and the height of r.
Fix an arbitrary tile r ∈ P. We already know that q divides its width. Furthermore, swapping r produces an element of the swapped partition (List.mem_map.mpr), so q divides the width of the swapped rectangle. Since the width of the swapped rectangle is definitionally the height of r, q divides the height of r as well.
uses
List.mem_map.mprintro r hr refine ⟨hw r hr, ?_⟩ have hx := hh (mondrian_rect_swap r) (List.mem_map.mpr ⟨r, hr, rfl⟩) simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx
mondrian_two_prime_area_width_dvd- In a defect-0 partition of an n × n square where every tile has area q^s * p^t (for primes p and q) and q divides n, the prime q divides the width of every tile.
mondrian_partition_swap- Swapping the x- and y-coordinates of each rectangle in a partition of an n × n square yields another valid partition of the same square.
List.mem_map.mp- If an element belongs to the image of a list under a function f, then it is equal to f(a) for some element a in the original list.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_defect_zero_of_equal- If every rectangle in a list has the same area, then the defect of the list is zero.
List.mem_map.mpr- If an element has the form f(a) for some element a in a list, then it belongs to the mapped 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_two_prime_area_sides_dvd (n p q s t : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n) (harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) : ∀ r ∈ P, q ∣ mondrian_rect_width r ∧ q ∣ mondrian_rect_height r := by have hw := mondrian_two_prime_area_width_dvd n p q s t P hp hq hP hz hqn harea have hswapP := mondrian_partition_swap n P hP have hswapA : ∀ r ∈ P.map mondrian_rect_swap, mondrian_rect_area r = q ^ s * p ^ t := by intro r hr obtain ⟨u, hu, rfl⟩ := List.mem_map.mp hr have hh := harea u hu simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap, Nat.mul_comm] using hh have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * p ^ t) hswapA have hh := mondrian_two_prime_area_width_dvd n p q s t (P.map mondrian_rect_swap) hp hq hswapP hswapZ hqn hswapA intro r hr refine ⟨hw r hr, ?_⟩ have hx := hh (mondrian_rect_swap r) (List.mem_map.mpr ⟨r, hr, rfl⟩) simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx