mondrian_partition_width_dvd_of_height_two_chains
If 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 r≥2, then every tile width is divisible by d.
Statement
theorem mondrian_partition_width_dvd_of_height_two_chains (n d p r C : ℕ)
(P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P)
(hz : mondrian_defect P = 0) (hdn : d ∣ n) (hC : 0 < C)
(hr : 2 ≤ r) (hpr : r + 1 < p)
(hheight : ∀ u ∈ P, ¬ d ∣ mondrian_rect_width u → ∃ a : ℕ,
mondrian_rect_height u = C * p ^ a ∨ mondrian_rect_height u = C * r * p ^ a) :
∀ u ∈ P, d ∣ mondrian_rect_width u- Source
- For the three-prime extension of OP-280, arXiv:2610.19193, Section 1. This develops the proved mondrian_no_perfect_two_prime_area and the width-free signed-height relation from this session.
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- mondrian_partition_width_free_height_signed_relationIf d divides the square side and a selected tile has width indivisible by d, its height is a signed sum of heights of other, pairwise…
- mondrian_two_chain_signed_sum_ne_zeroA nonempty signed sum of distinct numbers drawn from the chains C*p^a and C*r*p^a cannot vanish when C is positive, r≥2 and p>r+1.
- mondrian_perfect_height_injectiveThe heights of the tiles in a perfect admissible square partition are pairwise distinct.
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
- mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
- Used by 2
- 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…
- mondrian_three_prime_common_area_sides_divideFor 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…
The proof, explained
The theorem is proved by contradiction: assume some rectangle u in the partition has width not divisible by d. A general relation for Mondrian partitions yields a signed sum of heights of other width-indivisible rectangles that equals the height of u. Prepending the height of u with a negative sign produces a list H of signed heights summing to 0. Since defect is 0, rectangle heights are unique, making all heights in H distinct; and because all width-indivisible rectangles have heights in two superincreasing chains, an arithmetic theorem shows no such non-trivial signed sum can vanish, yielding a contradiction.
Assume for contradiction that some tile in P has width not divisible by d.
We work classically and introduce an arbitrary tile u ∈ P. We assume for contradiction that d does not divide the width of u.
classical intro u hu by_contra hfree
There is a duplicate-free list L of signed tiles in P \ {u} with widths not divisible by d whose signed height sum equals the height of u.
Applying mondrian_partition_width_free_height_signed_relation with d ∣ n and the tile u ∈ P (whose width is not divisible by d) produces a list L of pairs of tiles and boolean signs. The tiles in L are distinct, all belong to P, are distinct from u, have widths not divisible by d, and their signed height sum equals the height of u.
uses
mondrian_partition_width_free_height_signed_relationobtain ⟨L, hLnd, hLmem, hLsum⟩ := mondrian_partition_width_free_height_signed_relation n d P hP hdn u hu hfreeDefine H as the list of signed heights consisting of (height(u), false) followed by the signed heights of L.
We package the heights into a single list H of pairs of heights and signs by prepending height(u) with sign false (representing a negative sign) to the signed heights from L.
let H := (mondrian_rect_height u, false) :: L.map (fun t => (mondrian_rect_height t.1, t.2))
The list of heights of tiles in L contains no duplicates.
Because the partition has defect 0, height is injective on P by mondrian_perfect_height_injective. Since the tiles in L are distinct and all belong to P, mapping the height function preserves duplicate-freeness via List.Nodup.map_on.
uses
List.Nodup.map_on,List.mem_map.mp,mondrian_perfect_height_injective,List.map_map,Function.comp_defhave hhnd : (L.map (fun t => mondrian_rect_height t.1)).Nodup := by have hh : ((L.map Prod.fst).map mondrian_rect_height).Nodup := by apply List.Nodup.map_on _ hLnd intro v hv w hw he obtain ⟨v', hv', rfl⟩ := List.mem_map.mp hv obtain ⟨w', hw', rfl⟩ := List.mem_map.mp hw exact mondrian_perfect_height_injective n P hP hz v'.1 (hLmem v' hv').1 w'.1 (hLmem w' hw').1 he simpa only [List.map_map, Function.comp_def] using hh
The height of u does not appear among the heights of the tiles in L.
If height(u) were the height of some tile t in L, then by injectivity of heights (mondrian_perfect_height_injective), t would equal u. However, every tile in L is known to be distinct from u, a contradiction.
uses
List.mem_map.mp,mondrian_perfect_height_injectivehave hhead : mondrian_rect_height u ∉ L.map (fun t => mondrian_rect_height t.1) := by intro hm obtain ⟨t, ht, he⟩ := List.mem_map.mp hm exact (hLmem t ht).2.1 (mondrian_perfect_height_injective n P hP hz t.1 (hLmem t ht).1 u hu he)
The list of heights in H has no duplicates.
Since height(u) is not among the heights of L and the heights in L are duplicate-free, prepending height(u) produces a duplicate-free list of heights by List.nodup_cons.mpr.
uses
List.map_cons,List.map_map,Function.comp_def,List.nodup_cons.mprhave hnd : (H.map Prod.fst).Nodup := by simpa only [H, List.map_cons, List.map_map, Function.comp_def] using (List.nodup_cons.mpr ⟨hhead, hhnd⟩)
Every height in H has the form C * p^a or C * r * p^a for some natural number a.
Every element of H is either the head (height(u), false) or comes from L. In both cases, the tile belongs to P and its width is not divisible by d (by the contradiction assumption for u, and by construction for L). Thus the hypothesis hheight applies to every element of H.
uses
List.mem_cons.mp,List.mem_map.mphave hrep : ∀ t ∈ H, ∃ a : ℕ, t.1 = C * p ^ a ∨ t.1 = C * r * p ^ a := by intro t ht rcases List.mem_cons.mp ht with he | ht · subst t exact hheight u hu hfree · obtain ⟨v, hv, rfl⟩ := List.mem_map.mp ht exact hheight v.1 (hLmem v hv).1 (hLmem v hv).2.2
The signed sum of the heights in H equals zero.
Expanding the definition of H, the head contributes -height(u) because its sign is false, while the tail contributes the signed sum of heights from L, which equals height(u). The sum evaluates to -height(u) + height(u) = 0.
uses
List.map_cons,List.sum_cons,List.map_map,Function.comp_def,Bool.false_eq_true,if_falsehave hzero : (H.map (fun t => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ))).sum = 0 := by simp only [H, List.map_cons, List.sum_cons, List.map_map, Function.comp_def, Bool.false_eq_true, if_false] rw [hLsum] ring
A contradiction is reached, proving that d divides the width of every tile in P.
By mondrian_two_chain_signed_sum_ne_zero, no non-empty list of distinct heights chosen from the two chains C * p^a and C * r * p^a can have a vanishing signed sum when C > 0, r ≥ 2, and p > r + 1. Since H is non-empty, has distinct heights, consists of chain elements, and sums to zero, this produces a contradiction.
uses
mondrian_two_chain_signed_sum_ne_zeroexact mondrian_two_chain_signed_sum_ne_zero p r C hC hr hpr H (by simp [H]) hnd hrep hzero
Bool.false_eq_true- The boolean false is not equal to true.
Function.comp_def- Definition of function composition: (f ∘ g)(x) = f(g(x)).
List.map_cons- Mapping a function over a non-empty list applies the function to the head and maps over the tail.
List.map_map- Mapping g over map f l equals mapping the composite g ∘ f over l.
List.mem_cons.mp- An element of a list a :: l is either equal to a or belongs to l.
List.mem_map.mp- If an element belongs to map f l, it is the image under f of some element of l.
List.Nodup.map_on- A mapped list map f l has no duplicates if l has no duplicates and f is injective on l.
List.nodup_cons.mpr- Prepending an element a to a duplicate-free list l preserves duplicate-freeness if a is not in l.
List.sum_cons- The sum of elements in a :: l equals the head a plus the sum of the tail l.
if_false- An if-then-else expression with a false condition evaluates to the else branch.
mondrian_partition_width_free_height_signed_relation- In a partition of an n × n square with d ∣ n, if a tile r has width not divisible by d, there exists a duplicate-free list of other tiles with widths not divisible by d whose signed height sum equals the height of r.
mondrian_perfect_height_injective- In a Mondrian partition with defect 0, rectangle height is injective: no two distinct rectangles have the same height.
mondrian_two_chain_signed_sum_ne_zero- A non-empty list of signed, distinct integers from two geometric chains C * p^a and C * r * p^a (with C > 0, r ≥ 2, and p > r + 1) cannot have a signed sum of zero.
- The list H is constructed with the head element (mondrian_rect_height u, false), where the boolean flag `false` represents a negative sign, allowing the signed relation to be formulated as a vanishing sum -height(u) + height(u) = 0.
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_partition_width_dvd_of_height_two_chains (n d p r C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ)) (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hdn : d ∣ n) (hC : 0 < C) (hr : 2 ≤ r) (hpr : r + 1 < p) (hheight : ∀ u ∈ P, ¬ d ∣ mondrian_rect_width u → ∃ a : ℕ, mondrian_rect_height u = C * p ^ a ∨ mondrian_rect_height u = C * r * p ^ a) : ∀ u ∈ P, d ∣ mondrian_rect_width u := by classical intro u hu by_contra hfree obtain ⟨L, hLnd, hLmem, hLsum⟩ := mondrian_partition_width_free_height_signed_relation n d P hP hdn u hu hfree let H := (mondrian_rect_height u, false) :: L.map (fun t => (mondrian_rect_height t.1, t.2)) have hhnd : (L.map (fun t => mondrian_rect_height t.1)).Nodup := by have hh : ((L.map Prod.fst).map mondrian_rect_height).Nodup := by apply List.Nodup.map_on _ hLnd intro v hv w hw he obtain ⟨v', hv', rfl⟩ := List.mem_map.mp hv obtain ⟨w', hw', rfl⟩ := List.mem_map.mp hw exact mondrian_perfect_height_injective n P hP hz v'.1 (hLmem v' hv').1 w'.1 (hLmem w' hw').1 he simpa only [List.map_map, Function.comp_def] using hh have hhead : mondrian_rect_height u ∉ L.map (fun t => mondrian_rect_height t.1) := by intro hm obtain ⟨t, ht, he⟩ := List.mem_map.mp hm exact (hLmem t ht).2.1 (mondrian_perfect_height_injective n P hP hz t.1 (hLmem t ht).1 u hu he) have hnd : (H.map Prod.fst).Nodup := by simpa only [H, List.map_cons, List.map_map, Function.comp_def] using (List.nodup_cons.mpr ⟨hhead, hhnd⟩) have hrep : ∀ t ∈ H, ∃ a : ℕ, t.1 = C * p ^ a ∨ t.1 = C * r * p ^ a := by intro t ht rcases List.mem_cons.mp ht with he | ht · subst t exact hheight u hu hfree · obtain ⟨v, hv, rfl⟩ := List.mem_map.mp ht exact hheight v.1 (hLmem v hv).1 (hLmem v hv).2.2 have hzero : (H.map (fun t => if t.2 then (t.1 : ℤ) else -(t.1 : ℤ))).sum = 0 := by simp only [H, List.map_cons, List.sum_cons, List.map_map, Function.comp_def, Bool.false_eq_true, if_false] rw [hLsum] ring exact mondrian_two_chain_signed_sum_ne_zero p r C hC hr hpr H (by simp [H]) hnd hrep hzero