mondrian_three_prime_common_area_sides_divide
For primes p,q,r with p>r+1, if q divides the square side and every tile in a perfect admissible partition has area q^s*r*p^a, then q divides both dimensions of every tile.
Statement
theorem mondrian_three_prime_common_area_sides_divide (n p q r a s : ℕ)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q)
(hr : Nat.Prime r) (hpr : r + 1 < p)
(hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n)
(harea : ∀ u ∈ P, mondrian_rect_area u = q ^ s * r * p ^ a) :
∀ u ∈ P, q ∣ mondrian_rect_width u ∧ q ∣ mondrian_rect_height u- Source
- Helper for the three-prime extension of OP-280, arXiv:2610.19193 Section 1. This combines the width-free height cycle with the two superincreasing chains.
- 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_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_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_prime_free_height_two_chain_encodingIf x*y=q^s*r*p^a for primes p,q,r with p≠r, and q does not divide x, then y lies in one of the chains q^s*p^b or q^s*r*p^b.
- 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₁).
- Used by 1
- 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…
The proof, explained
The proof first establishes that in any defect-zero partition where every tile has area q^s * r * p^a, the prime q must divide the width of every tile: if q did not divide the width, the prime factorisation forces all factors of q into the height, placing the height into a two-chain form that triggers a width-divisibility reduction theorem. Applying this lemma directly to the original partition shows q divides all tile widths. Finally, reflecting the partition across the diagonal exchanges width and height while preserving partition validity and tile areas; applying the width result to this transposed partition shows that q divides every tile's height as well.
p ≠ r automation
Since r + 1 < p and r ≥ 0, linear integer arithmetic (`omega`) immediately shows that p and r are distinct.
have hpne : p ≠ r := by omega
For any defect-zero partition Q of the n × n square whose tiles all have area q^s * r * p^a, the prime q divides the width of every tile in Q.
To apply `mondrian_partition_width_dvd_of_height_two_chains` with constant C = q^s, consider any tile u in Q whose width is not divisible by q. Since the tile area is width(u) * height(u) = q^s * r * p^a, all s factors of q must divide the height. By `mondrian_prime_free_height_two_chain_encoding`, the only remaining prime factors of the height can be p and r, which forces height(u) to equal q^s * p^b or q^s * r * p^b for some b. The reduction theorem then concludes that q divides the width of every tile in Q.
uses
mondrian_partition_width_dvd_of_height_two_chains,pow_pos,mondrian_prime_free_height_two_chain_encodinghave hwidth : ∀ (Q : List (ℕ × ℕ × ℕ × ℕ)), mondrian_is_partition n Q → mondrian_defect Q = 0 → (∀ u ∈ Q, mondrian_rect_area u = q ^ s * r * p ^ a) → ∀ u ∈ Q, q ∣ mondrian_rect_width u := by intro Q hQ hQz hQA apply mondrian_partition_width_dvd_of_height_two_chains n q p r (q ^ s) Q hQ hQz hqn (pow_pos hq.pos s) hr.two_le hpr intro u hu hfree exact mondrian_prime_free_height_two_chain_encoding p q r a s (mondrian_rect_width u) (mondrian_rect_height u) hp hq hr hpne (hQA u hu) hfree
For every tile u in P, q divides the width of u.
Specializing the general width divisibility lemma to the given partition P, which has defect 0 and whose tiles all have area q^s * r * p^a, yields that q divides width(u) for every u ∈ P.
have hw := hwidth P hP hz hareaIn the coordinate-transposed partition, q divides the width of every tile.
Transposing each rectangle across the diagonal via `mondrian_rect_swap` produces another admissible partition P_swap of the square (`mondrian_partition_swap`). For any tile in P_swap, which is the transpose of some tile v ∈ P (`List.mem_map.mp`), its area is height(v) * width(v) = width(v) * height(v) = q^s * r * p^a by commutativity of multiplication (`Nat.mul_comm`). Since all tiles in P_swap have identical area, its defect is 0 (`mondrian_defect_zero_of_equal`). Applying the general width divisibility lemma to P_swap shows that q divides the width of every tile in P_swap.
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 : ∀ u ∈ P.map mondrian_rect_swap, mondrian_rect_area u = q ^ s * r * p ^ a := by intro u hu obtain ⟨v, hv, rfl⟩ := List.mem_map.mp hu simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap, Nat.mul_comm] using harea v hv have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * r * p ^ a) hswapA have hh := hwidth (P.map mondrian_rect_swap) hswapP hswapZ hswapA
For every tile u in P, q divides both the width and the height of u.
Let u ∈ P. Divisibility of width(u) by q was established in step 3. The transposed tile swap(u) belongs to P_swap (`List.mem_map.mpr`), so q divides width(swap(u)) by step 4. Since width(swap(u)) is by definition height(u), q also divides height(u).
uses
List.mem_map.mprintro u hu refine ⟨hw u hu, ?_⟩ have hx := hh (mondrian_rect_swap u) (List.mem_map.mpr ⟨u, hu, rfl⟩) simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx
List.mem_map.mp- If an element is in the image of a list under a function, it is the image of some element in the original list.
List.mem_map.mpr- The image of any element in a list under a function belongs to the mapped list.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_defect_zero_of_equal- If every rectangle in a partition has the same area, the defect of the partition is zero.
mondrian_partition_width_dvd_of_height_two_chains- In an admissible defect-zero partition of an n × n square where d divides n, if every tile whose width is not divisible by d has height of the form C * p^a or C * r * p^a, then d divides the width of every tile.
mondrian_partition_swap- Transposing each rectangle in an admissible partition of an n × n square yields another admissible partition of the square.
mondrian_prime_free_height_two_chain_encoding- If p, q, r are primes with p ≠ r, and x * y = q^s * r * p^a with q not dividing x, then y has the form q^s * p^b or q^s * r * p^b for some natural number b.
pow_pos- A strictly positive base raised to any natural power is strictly positive.
- The proof relies on Lean's `simpa` tactic to unfold the coordinate-swapping definitions and apply commutativity of multiplication.
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_three_prime_common_area_sides_divide (n p q r a s : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q) (hr : Nat.Prime r) (hpr : r + 1 < p) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n) (harea : ∀ u ∈ P, mondrian_rect_area u = q ^ s * r * p ^ a) : ∀ u ∈ P, q ∣ mondrian_rect_width u ∧ q ∣ mondrian_rect_height u := by have hpne : p ≠ r := by omega have hwidth : ∀ (Q : List (ℕ × ℕ × ℕ × ℕ)), mondrian_is_partition n Q → mondrian_defect Q = 0 → (∀ u ∈ Q, mondrian_rect_area u = q ^ s * r * p ^ a) → ∀ u ∈ Q, q ∣ mondrian_rect_width u := by intro Q hQ hQz hQA apply mondrian_partition_width_dvd_of_height_two_chains n q p r (q ^ s) Q hQ hQz hqn (pow_pos hq.pos s) hr.two_le hpr intro u hu hfree exact mondrian_prime_free_height_two_chain_encoding p q r a s (mondrian_rect_width u) (mondrian_rect_height u) hp hq hr hpne (hQA u hu) hfree have hw := hwidth P hP hz harea have hswapP := mondrian_partition_swap n P hP have hswapA : ∀ u ∈ P.map mondrian_rect_swap, mondrian_rect_area u = q ^ s * r * p ^ a := by intro u hu obtain ⟨v, hv, rfl⟩ := List.mem_map.mp hu simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap, Nat.mul_comm] using harea v hv have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * r * p ^ a) hswapA have hh := hwidth (P.map mondrian_rect_swap) hswapP hswapZ hswapA intro u hu refine ⟨hw u hu, ?_⟩ have hx := hh (mondrian_rect_swap u) (List.mem_map.mpr ⟨u, hu, rfl⟩) simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx