mondrian_perfect_prime_free_side_counts
In any perfect admissible partition of an integer n-square, every prime p dividing n divides both the number of tiles with width not divisible by p and the number with height not divisible by p.
Statement
theorem mondrian_perfect_prime_free_side_counts (n p : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) : p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_width r)) ∧ p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_height r))
- Source
- Helper for OP-280: modular shape inventories for the zero-defect question in arXiv:2610.19193, Section 1. The weighted row and prime-free count argument is developed here; it supplements the available-shape counting in arXiv:2311.02385, Section 3.
- 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_partition_prime_free_height_countFor an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of…
- mondrian_partition_prime_free_width_countFor an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of…
- 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₁).
- Used by 2
- mondrian_perfect_min_width_layer_countFor a perfect admissible n-square partition and prime p dividing n, suppose b is the minimum p-adic exponent of tile widths. Then b is at…
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
The proof, explained
The proof proceeds by considering whether the list of tiles P is empty. When P is empty, the counts are zero and the statement holds vacuously. When P is non-empty, the zero-defect condition guarantees that all tiles share the same strictly positive area as the initial tile r. The result then follows directly by applying previously proven theorems that establish prime divisibility for prime-free width and height counts in equiareal partitions.
The claim holds trivially when the partition list P is empty. automation
When P is empty, the count of tiles satisfying any condition evaluates to 0. Since every prime p divides 0, both divisibility conditions hold vacuously, and simplification closes the goal.
cases P with | nil => simp
In a non-empty partition r :: P, the tile r belongs to the partition and has strictly positive area.
The tile r is trivially an element of r :: P. Applying mondrian_partition_bounds shows that r has strictly positive width and strictly positive height. By Nat.mul_pos, their product—the area of r—is strictly positive.
uses
mondrian_partition_bounds,Nat.mul_pos| cons r P => have hr : r ∈ r :: P := by simp have hb := mondrian_partition_bounds n (r :: P) hP r hr have hApos := Nat.mul_pos hb.2.2.1 hb.2.2.2.1Every tile in r :: P has the same area as r.
Because the partition has defect zero (hz), mondrian_defect_zero_equal implies that any two tiles in the partition have identical area. In particular, every tile s ∈ r :: P has area equal to mondrian_rect_area r.
uses
mondrian_defect_zero_equalhave hA : ∀ s ∈ r :: P, mondrian_rect_area s = mondrian_rect_area r := fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr
p divides both the number of tiles with width not divisible by p and the number of tiles with height not divisible by p.
With the area A = mondrian_rect_area r established to be strictly positive and constant across all tiles, the pair of goals is closed by invoking mondrian_partition_prime_free_width_count for the width count and mondrian_partition_prime_free_height_count for the height count.
uses
mondrian_partition_prime_free_width_count,mondrian_partition_prime_free_height_countexact ⟨mondrian_partition_prime_free_width_count n p (mondrian_rect_area r) (r :: P) hp hpn hApos hP hA, mondrian_partition_prime_free_height_count n p (mondrian_rect_area r) (r :: P) hp hpn hApos hP hA⟩
mondrian_partition_bounds- In an admissible partition of an n-square, every tile lies within the square and has strictly positive width and height bounded by n.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
mondrian_defect_zero_equal- If a partition has defect zero, any two tiles in the partition have equal area.
mondrian_partition_prime_free_width_count- In an admissible partition of an n-square where all tiles share the same positive area A, every prime p dividing n divides the number of tiles whose width is not divisible by p.
mondrian_partition_prime_free_height_count- In an admissible partition of an n-square where all tiles share the same positive area A, every prime p dividing n divides the number of tiles whose height is not divisible by p.
- The case analysis on whether P is empty is a formal artifact: the definition mondrian_is_partition requires 2 ≤ P.length, so P can never be empty for an admissible partition. Performing `cases P` is simply the most direct way in Lean to extract a concrete tile r ∈ P to serve as an area reference.
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.
open scoped BigOperatorstheorem mondrian_perfect_prime_free_side_counts (n p : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) : p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_width r)) ∧ p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_height r)) := by cases P with | nil => simp | cons r P => have hr : r ∈ r :: P := by simp have hb := mondrian_partition_bounds n (r :: P) hP r hr have hApos := Nat.mul_pos hb.2.2.1 hb.2.2.2.1 have hA : ∀ s ∈ r :: P, mondrian_rect_area s = mondrian_rect_area r := fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr exact ⟨mondrian_partition_prime_free_width_count n p (mondrian_rect_area r) (r :: P) hp hpn hApos hP hA, mondrian_partition_prime_free_height_count n p (mondrian_rect_area r) (r :: P) hp hpn hApos hP hA⟩