mondrian_partition_prime_free_height_count
For an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of tiles whose height is not divisible by p is divisible by p.
Statement
theorem mondrian_partition_prime_free_height_count (n p A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hApos : 0 < A) (hP : mondrian_is_partition n P) (hA : ∀ r ∈ P, mondrian_rect_area r = A) : 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 7
- 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_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_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₁).
- Used by 1
- mondrian_perfect_prime_free_side_countsIn any perfect admissible partition of an integer n-square, every prime p dividing n divides both the number of tiles with width not…
The proof, explained
The theorem is proved by reduction to the horizontal case (`mondrian_partition_prime_free_width_count`) via diagonal symmetry. Exchanging the x- and y-coordinates of each rectangle transforms the partition into another admissible partition of the n-square while preserving each rectangle's area. Applying the width-divisibility theorem to this swapped partition shows that p divides the number of tiles with non-divisible swapped width. Because the width of a swapped rectangle is definitionally the height of the original rectangle, the claim follows immediately.
Reflecting each tile across the main diagonal yields another valid partition of the n-square.
Applying `mondrian_partition_swap` to the partition P establishes that exchanging the horizontal and vertical coordinates of each rectangle produces an admissible partition of the n × n square.
uses
mondrian_partition_swaphave hswap := mondrian_partition_swap n P hPEvery tile in the swapped partition retains the same area A.
For any rectangle r in the swapped list, `List.mem_map.mp` yields an original tile s ∈ P such that r is the coordinate swap of s. The area of r is its width times its height, which corresponds to the height times the width of s. By commutativity of multiplication (`Nat.mul_comm`), this product equals the original area of s, which is A by assumption.
uses
List.mem_map.mp,Nat.mul_commhave hAswap : ∀ r ∈ P.map mondrian_rect_swap, mondrian_rect_area r = A := by intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap, Nat.mul_comm] using hA s hs
The prime p divides the number of tiles in P whose swapped width is not divisible by p.
Applying `mondrian_partition_prime_free_width_count` to the swapped partition shows that p divides the count of tiles in `P.map mondrian_rect_swap` whose width is not a multiple of p. Rewriting with `List.countP_map` pulls the swap operation into the predicate, rephrasing this as a count over the original list P.
uses
mondrian_partition_prime_free_width_count,List.countP_maphave hc := mondrian_partition_prime_free_width_count n p A (P.map mondrian_rect_swap) hp hpn hApos hswap hAswap rw [List.countP_map] at hc
The condition that a swapped tile has width not divisible by p is equivalent to the condition that the original tile has height not divisible by p.
Using function extensionality (`funext`) and evaluating the function composition (`Function.comp_apply`), we compare the two boolean predicates. By `decide_eq_decide.mpr`, it suffices to show that the underlying divisibility statements are equivalent. Because the width of the swapped rectangle is definitionally equal to the height of the original rectangle, the equivalence holds by reflexivity (`rfl`).
uses
Function.comp_apply,decide_eq_decide.mprhave heq : ((fun r => decide (¬p ∣ mondrian_rect_width r)) ∘ mondrian_rect_swap) = (fun r => decide (¬p ∣ mondrian_rect_height r)) := by funext r simp only [Function.comp_apply] apply decide_eq_decide.mpr rfl
The prime p divides the number of tiles in P whose height is not divisible by p.
Rewriting the count in the divisibility hypothesis using the equality of predicates established in the previous step replaces the swapped-width condition with the original tile's height condition, concluding the proof.
rw [heq] at hc exact hc
mondrian_partition_swap- If P is an admissible partition of the n-square, then swapping the coordinates of each rectangle in P also yields an admissible partition of the n-square.
List.mem_map.mp- An element y belongs to the image List.map f l if and only if there exists an element x ∈ l such that f x = y.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_partition_prime_free_width_count- In an admissible partition of an n-square into rectangles of constant positive area A, for any prime p dividing n, the number of rectangles whose width is not divisible by p is divisible by p.
List.countP_map- Counting elements satisfying predicate p in a mapped list List.map f l is equal to counting elements in l satisfying the composite predicate p ∘ f.
Function.comp_apply- The application of a composite function (f ∘ g) x equals f (g x).
decide_eq_decide.mpr- If two propositions are logically equivalent, their boolean decision values are equal.
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_partition_prime_free_height_count (n p A : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n) (hApos : 0 < A) (hP : mondrian_is_partition n P) (hA : ∀ r ∈ P, mondrian_rect_area r = A) : p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_height r)) := by have hswap := mondrian_partition_swap n P hP have hAswap : ∀ r ∈ P.map mondrian_rect_swap, mondrian_rect_area r = A := by intro r hr obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap, Nat.mul_comm] using hA s hs have hc := mondrian_partition_prime_free_width_count n p A (P.map mondrian_rect_swap) hp hpn hApos hswap hAswap rw [List.countP_map] at hc have heq : ((fun r => decide (¬p ∣ mondrian_rect_width r)) ∘ mondrian_rect_swap) = (fun r => decide (¬p ∣ mondrian_rect_height r)) := by funext r simp only [Function.comp_apply] apply decide_eq_decide.mpr rfl rw [heq] at hc exact hc