mondrian_large_prime_descent
If c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the c-square.
Statement
theorem mondrian_large_prime_descent (c p e : ℕ) (hc : 0 < c)
(hp : Nat.Prime p) (hpc : c < p) :
(∃ P, mondrian_is_partition (c * p ^ e) P ∧ mondrian_defect P = 0) →
∃ Q, mondrian_is_partition c Q ∧ mondrian_defect Q = 0- Source
- Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 18
- 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_large_prime_count_not_dvdIf enough distinct shapes of a common area fit in a c times p to the e square to account for its area, a prime p greater than c cannot…
- 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_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
- mondrian_perfect_partition_divDividing coordinates by a preserves perfect admissible partitions when a is positive and divides every tile side.
- mondrian_prime_power_dvd_sidesIf p is prime and exceeds c, positive x and y at most c times p to the e whose product is divisible by p to the 2e must each be divisible…
- 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_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_shape_boundA partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.
- 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).
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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 2
- mondrian_no_perfect_six_mul_prime_powFor every prime p greater than six and every natural e, the square of side six times p to the e has no perfect admissible partition.
- mondrian_perfect_partition_large_prime_iffFor every positive integer c, prime p greater than c, and natural exponent e, the square of side c times p to the e has a perfect…
The proof, explained
Assuming there exists a defect-0 partition P of a (c · p^e) × (c · p^e) square into non-congruent rectangles, all rectangles share the same area A and satisfy |P| · A = (c · p^e)². Since c < p and the non-congruence condition limits the number of available factorizations of A, the prime p cannot divide the rectangle count |P|. Consequently, p^(2e) is coprime to |P| and must divide the rectangle area A = width · height. Because each side length is at most c · p^e and c < p, p^e must divide both the width and height of every rectangle, allowing the entire partition to be scaled down by p^e into a defect-0 partition of the c × c square.
Let P be a partition of the (c · p^e) × (c · p^e) square with defect 0.
We assume the hypothesis: there exists a partition P of the square of side c · p^e (hP) with defect 0 (hz), meaning all rectangles in P have the same area.
rintro ⟨P, hP, hz⟩
The partition P cannot be empty.
By definition, any valid Mondrian partition contains at least two rectangles (|P| ≥ 2). If P were empty, its length would be 0, which contradicts 2 ≤ 0.
cases P with | nil => have := hP.1; simp at this
For any rectangle r ∈ P, its area is positive and satisfies |P| · area(r) = (c · p^e)².
Since P is non-empty, we can pick a rectangle r ∈ P. Partition bounds (mondrian_partition_bounds) ensure that both dimensions of r are strictly positive and bounded by c · p^e, so the area of r is strictly positive (Nat.mul_pos). Since the defect is 0, every rectangle in P has area equal to area(r), so the sum of all rectangle areas equals |P| · area(r) = (c · p^e)² (mondrian_perfect_area_product).
uses
mondrian_partition_bounds,Nat.mul_pos,mondrian_perfect_area_product| cons r P => have hr : r ∈ r :: P := by simp have hb := mondrian_partition_bounds (c * p ^ e) (r :: P) hP r hr have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1 have heq := mondrian_perfect_area_product (c * p ^ e) (r :: P) hP hz r hrThe prime p does not divide the number of rectangles |P|.
Because all rectangles in P have equal area (mondrian_defect_zero_equal) and are pairwise non-congruent, the count |P| cannot exceed the number of distinct factorizations of area(r) that fit in the square (mondrian_shape_bound). Together with c < p and the total area equation, this bound implies that p does not divide |P| (mondrian_large_prime_count_not_dvd).
uses
mondrian_defect_zero_equal,mondrian_shape_bound,mondrian_large_prime_count_not_dvdhave hcard := mondrian_shape_bound (c * p ^ e) (mondrian_rect_area r) (r :: P) hP (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr) have hknot := mondrian_large_prime_count_not_dvd c p e (r :: P).length (mondrian_rect_area r) hc hp hpc (by have := hP.1; omega) hA heq hcard
p^(2e) is coprime to |P|.
Since p is prime and does not divide |P|, p and |P| are coprime. Raising p to the power 2e preserves coprimality (pow_left).
uses
pow_lefthave hcop : (p ^ (2 * e)).Coprime (r :: P).length := (hp.coprime_iff_not_dvd.mpr hknot).pow_left (2 * e)p^(2e) divides the area of r.
Rewriting (c · p^e)² as p^(2e) · c² via exponent arithmetic (Nat.mul_comm, pow_mul), p^(2e) divides the total area |P| · area(r) (dvd_mul_right). Since p^(2e) is coprime to |P|, by Euclid's lemma p^(2e) must divide area(r).
uses
Nat.mul_comm,pow_mul,dvd_mul_righthave hpowprod : p ^ (2 * e) ∣ (r :: P).length * mondrian_rect_area r := by rw [heq] have hnn : (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2 := by rw [Nat.mul_comm 2 e, pow_mul] ring rw [hnn] exact dvd_mul_right _ _ have hpow := hcop.dvd_mul_left.mp hpowprod have hpc' : c < p := by nlinarith
For every rectangle s ∈ P, p^e divides both the width and height of s.
Every rectangle s ∈ P has area equal to area(r) (mondrian_defect_zero_equal), so p^(2e) divides width(s) · height(s). Furthermore, the dimensions of s are positive and at most c · p^e (mondrian_partition_bounds). Since c < p, the divisibility lemma mondrian_prime_power_dvd_sides forces p^e to divide both width(s) and height(s).
uses
mondrian_partition_bounds,mondrian_defect_zero_equal,mondrian_prime_power_dvd_sideshave hd : ∀ s ∈ r :: P, p ^ e ∣ mondrian_rect_width s ∧ p ^ e ∣ mondrian_rect_height s := by intro s hs have hbs := mondrian_partition_bounds (c * p ^ e) (r :: P) hP s hs have hspow : p ^ (2 * e) ∣ mondrian_rect_area s := by rw [mondrian_defect_zero_equal (r :: P) hz s r hs hr] exact hpow exact mondrian_prime_power_dvd_sides c p e (mondrian_rect_width s) (mondrian_rect_height s) hp hpc' hbs.2.2.1 hbs.2.2.2.1 hbs.2.2.2.2.1 hbs.2.2.2.2.2 hspow
Dividing every rectangle in P by p^e yields a defect-0 partition of the c × c square.
We construct the candidate partition by dividing the coordinates of every rectangle in P by p^e. Since p^e > 0 (pow_pos) and p^e divides both dimensions of every rectangle, scaling down preserves the partition structure and zero defect, producing a valid defect-0 partition of the c × c square (mondrian_perfect_partition_div, with Nat.mul_comm adjusting the side length product p^e · c).
uses
pow_pos,mondrian_perfect_partition_div,Nat.mul_commrefine ⟨(r :: P).map (mondrian_rect_div (p ^ e)), ?_⟩ exact mondrian_perfect_partition_div (p ^ e) c (pow_pos hp.pos e) (r :: P) (by simpa only [Nat.mul_comm] using hP) hz hd
mondrian_partition_bounds- Every rectangle in a partition of an n × n square has strictly positive width and height bounded above by n, and its coordinates lie within [0, n].
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
mondrian_perfect_area_product- In a defect-0 partition of an n × n square, the number of rectangles times the area of any rectangle equals the total area n².
mondrian_shape_bound- In a partition where every rectangle has area A, the number of rectangles is at most the number of non-congruent rectangular shapes of area A that fit in the n × n square.
mondrian_defect_zero_equal- In a partition with defect 0, all rectangles have identical area.
mondrian_large_prime_count_not_dvd- For prime p > c > 0, if k non-congruent rectangles of area A tile a (c · p^e) × (c · p^e) square, then p does not divide the rectangle count k.
pow_left- If a is coprime to b, then any power a^n is also coprime to b.
Nat.mul_comm- Multiplication of natural numbers is commutative: n · m = m · n.
pow_mul- Power of a power rule: a^(m · n) = (a^m)^n.
dvd_mul_right- Any number a divides the product a · b.
mondrian_prime_power_dvd_sides- If p > c is prime and positive integers x, y ≤ c · p^e satisfy p^(2e) ∣ x · y, then p^e divides x and p^e divides y.
pow_pos- Any power of a strictly positive number is strictly positive.
mondrian_perfect_partition_div- If a > 0 divides both dimensions of every rectangle in a defect-0 partition of an (a · c) × (a · c) square, dividing each rectangle by a yields a defect-0 partition of a c × c square.
- Line 27 reproves the hypothesis c < p via nlinarith under the name hpc' to match the argument position of mondrian_prime_power_dvd_sides.
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_large_prime_descent (c p e : ℕ) (hc : 0 < c) (hp : Nat.Prime p) (hpc : c < p) : (∃ P, mondrian_is_partition (c * p ^ e) P ∧ mondrian_defect P = 0) → ∃ Q, mondrian_is_partition c Q ∧ mondrian_defect Q = 0 := by rintro ⟨P, hP, hz⟩ cases P with | nil => have := hP.1; simp at this | cons r P => have hr : r ∈ r :: P := by simp have hb := mondrian_partition_bounds (c * p ^ e) (r :: P) hP r hr have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1 have heq := mondrian_perfect_area_product (c * p ^ e) (r :: P) hP hz r hr have hcard := mondrian_shape_bound (c * p ^ e) (mondrian_rect_area r) (r :: P) hP (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr) have hknot := mondrian_large_prime_count_not_dvd c p e (r :: P).length (mondrian_rect_area r) hc hp hpc (by have := hP.1; omega) hA heq hcard have hcop : (p ^ (2 * e)).Coprime (r :: P).length := (hp.coprime_iff_not_dvd.mpr hknot).pow_left (2 * e) have hpowprod : p ^ (2 * e) ∣ (r :: P).length * mondrian_rect_area r := by rw [heq] have hnn : (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2 := by rw [Nat.mul_comm 2 e, pow_mul] ring rw [hnn] exact dvd_mul_right _ _ have hpow := hcop.dvd_mul_left.mp hpowprod have hpc' : c < p := by nlinarith have hd : ∀ s ∈ r :: P, p ^ e ∣ mondrian_rect_width s ∧ p ^ e ∣ mondrian_rect_height s := by intro s hs have hbs := mondrian_partition_bounds (c * p ^ e) (r :: P) hP s hs have hspow : p ^ (2 * e) ∣ mondrian_rect_area s := by rw [mondrian_defect_zero_equal (r :: P) hz s r hs hr] exact hpow exact mondrian_prime_power_dvd_sides c p e (mondrian_rect_width s) (mondrian_rect_height s) hp hpc' hbs.2.2.1 hbs.2.2.2.1 hbs.2.2.2.2.1 hbs.2.2.2.2.2 hspow refine ⟨(r :: P).map (mondrian_rect_div (p ^ e)), ?_⟩ exact mondrian_perfect_partition_div (p ^ e) c (pow_pos hp.pos e) (r :: P) (by simpa only [Nat.mul_comm] using hP) hz hd