mondrian_seven_rects_is_partition
For positive integers p, q of the same parity with q < p < 7q, the seven rectangles R₁, …, R₇ have positive integer sides, partition the 105q × 105q square, and are pairwise noncongruent.
Statement
theorem mondrian_seven_rects_is_partition (p q : ℕ) (hpar : p % 2 = q % 2) (hqp : q < p)
(hp : p < 7 * q) :
mondrian_is_partition (105 * q) (mondrian_seven_rects p q)- Source
- arXiv:2610.19193 (A Bounded-Defect Construction for the Mondrian Art Problem), Sec. 2 (the dissection (3) is a partition) and Proposition 1 (pairwise noncongruence); serves mondrian_seven_rects_partition_defect.
- Verified
- 15 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
- mondrian_seven_rectsThe seven rectangles R₁, …, R₇ of the generic dissection of the n×n square, n = 105q, with a = 7(7q−p), b = 42q, c = 7(7q+p), d = 5(8q−p),…
- 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…
- 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).
- Used by 2
- mondrian_pell_family_defect_280For n₀ = 315, n₁ = 106785, n_{j+2} = 340n_{j+1} − n_j: for every j the n_j×n_j square has a Mondrian partition into seven pairwise…
- mondrian_seven_rects_partition_defectLet p, q be positive integers of the same parity with q < p < 7q, n = 105q and E = p² − 19q². The seven rectangles R₁, …, R₇ of (2)–(3)…
The proof, explained
The proof establishes that the seven parameterized rectangles form a valid Mondrian partition of the 105q × 105q square for any positive integers p, q of the same parity with q < p < 7q. After establishing four arithmetic identities and a general geometric separation criterion for disjointness, the partition condition is split into non-degeneracy, pairwise disjointness and non-congruence, and coverage of the square. Each condition is verified by case analysis on the rectangles and resolved via integer linear arithmetic using Lean's omega tactic, with coverage settled by a coordinate-based decision tree.
Four linear arithmetic identities hold relating the coordinate parameters to multiples of q and p.
Under the conditions that p and q share parity with q < p < 7q, we establish four algebraic relations: 7(7q - p) + 7p = 49q (for coordinate a), 5(8q - p) + 5p = 40q (for coordinate d), 5(13q - p) + 5p = 65q (for coordinate e), and 2 · ⌊15(7q + p) / 2⌋ = 105q + 15p (for coordinate f, which is an integer because 7q + p is even). All four identities follow directly by linear integer arithmetic.
have ha : 7 * (7 * q - p) + 7 * p = 49 * q := by omega have hd : 5 * (8 * q - p) + 5 * p = 40 * q := by omega have he : 5 * (13 * q - p) + 5 * p = 65 * q := by omega have hf : 2 * (15 * (7 * q + p) / 2) = 105 * q + 15 * p := by omega
A geometric criterion for disjointness of two axis-aligned rectangles.
If two rectangles r = [x₁, x₂) × [y₁, y₂) and s = [x'₁, x'₂) × [y'₁, y'₂) are separated horizontally (x₂ ≤ x'₁ or x'₂ ≤ x₁) or vertically (y₂ ≤ y'₁ or y'₂ ≤ y₁), their cell sets are disjoint. Rewriting disjointness with Finset.disjoint_left and expanding cell membership in the Cartesian product of intervals, an element in the intersection would satisfy contradictory linear inequalities, which omega refutes.
uses
Finset.disjoint_left,Finset.mem_product,Finset.mem_Icohave hdisj : ∀ r s : ℕ × ℕ × ℕ × ℕ, (r.2.1 ≤ s.1 ∨ s.2.1 ≤ r.1 ∨ r.2.2.2 ≤ s.2.2.1 ∨ s.2.2.2 ≤ r.2.2.1) → Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s) := by intro r s h rw [Finset.disjoint_left] rintro ⟨x, y⟩ h1 h2 simp only [mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico] at h1 h2 omega
The list of seven rectangles is rewritten using compact coordinate names a, d, e, f, c.
Unfolding mondrian_seven_rects, we introduce abbreviations for the five key division lines: a = 7(7q - p), d = 5(8q - p), e = 5(13q - p), f = 15(7q + p) / 2, and c = 7(7q + p). This simplifies the coordinates of the seven rectangles and re-expresses the goal and earlier identities in terms of these parameters.
unfold mondrian_seven_rects generalize 7 * (7 * q - p) = a at ha ⊢ generalize 5 * (8 * q - p) = d at hd ⊢ generalize 5 * (13 * q - p) = e at he ⊢ generalize 15 * (7 * q + p) / 2 = f at hf ⊢ generalize hc : 7 * (7 * q + p) = c
The partition property reduces to non-degeneracy, pairwise disjointness/non-congruence, and square coverage.
The definition mondrian_is_partition requires four conditions: that the list has length at least 2, that every rectangle has strictly positive width and height, that rectangles are pairwise disjoint and non-congruent, and that their union equals the (105q) × (105q) grid. The length condition 2 ≤ 7 is discharged immediately by simplification, leaving the remaining three properties as subgoals.
refine ⟨by simp, ?_, ?_, ?_⟩
Every rectangle in the collection has strictly positive width and height.
For each rectangle r in the 7-element list, we case-split on which rectangle it is. In each of the seven cases, the positivity requirements x₁ < x₂ and y₁ < y₂ reduce to linear inequalities in p and q (such as a < 105q and 0 < d), which follow from q < p < 7q and are closed by omega.
uses
List.mem_cons,List.not_mem_nil,or_false· intro r hr simp only [List.mem_cons, List.not_mem_nil, or_false] at hr rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> dsimp only <;> omega
The seven rectangles are pairwise disjoint and pairwise non-congruent.
Expanding the pairwise relation over the 7-element list yields 21 pairs of distinct rectangles, each requiring proofs of disjointness and non-congruence. Each disjointness goal is discharged by the geometric criterion hdisj, checking the coordinate separation with omega. Each non-congruence goal expands the definition of congruence (matching side lengths up to rotation) and is refuted by omega from the parameter bounds q < p < 7q.
uses
List.pairwise_cons,List.mem_cons,List.not_mem_nil,or_false,forall_eq_or_imp,forall_eq,List.Pairwise.nil,and_true· simp only [List.pairwise_cons, List.mem_cons, List.not_mem_nil, or_false, forall_eq_or_imp, forall_eq, List.Pairwise.nil, and_true] and_intros all_goals first | exact fun _ h => h.elim | exact hdisj _ _ (by dsimp only; omega) | (simp only [mondrian_rect_congruent, mondrian_rect_width, mondrian_rect_height]; omega)
Every cell in any of the seven rectangles lies within the 105q × 105q square.
By extensionality on cells (x, y), coverage reduces to two inclusions. For the forward inclusion (⊆), suppose a cell (x, y) belongs to some rectangle r in the list. Splitting across the seven rectangles, the bounds x₁ ≤ x < x₂ and y₁ ≤ y < y₂ guarantee that x < 105q and y < 105q, verified in each case by omega.
uses
Finset.mem_biUnion,List.mem_toFinset,List.mem_cons,List.not_mem_nil,or_false,Finset.mem_product,Finset.mem_Ico,Finset.mem_range· ext ⟨x, y⟩ simp only [Finset.mem_biUnion, List.mem_toFinset, List.mem_cons, List.not_mem_nil, or_false, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico, Finset.mem_range] constructor · rintro ⟨r, hr, h⟩ rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> dsimp only at h <;> omega
Every cell in the 105q × 105q square is covered by one of the seven rectangles.
For the reverse inclusion (⊇), given a cell (x, y) with x < 105q and y < 105q, a decision tree on the coordinates identifies which rectangle contains it: testing y < d routes to R₂ (if x < a) or R₁; testing y < e routes to R₂ (if x < a), R₆ (if x < 42q), or R₅; testing y < f routes to R₂ (if x < a), R₆ (if x < 42q), R₇ (if x < c), or R₄; and if y ≥ f, testing x < c routes to R₃ or R₄. In each branch, omega verifies that (x, y) satisfies the boundary conditions of the selected rectangle.
uses
Or.inl,Or.inr· intro h by_cases h1 : y < d · by_cases h2 : x < a · exact ⟨_, Or.inr (Or.inl rfl), by dsimp only; omega⟩ · exact ⟨_, Or.inl rfl, by dsimp only; omega⟩ by_cases h3 : y < e · by_cases h2 : x < a · exact ⟨_, Or.inr (Or.inl rfl), by dsimp only; omega⟩ by_cases h4 : x < 42 * q · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl rfl))))), by dsimp only; omega⟩ · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inl rfl)))), by dsimp only; omega⟩ by_cases h5 : y < f · by_cases h2 : x < a · exact ⟨_, Or.inr (Or.inl rfl), by dsimp only; omega⟩ by_cases h4 : x < 42 * q · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl rfl))))), by dsimp only; omega⟩ by_cases h6 : x < c · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr rfl))))), by dsimp only; omega⟩ · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inl rfl))), by dsimp only; omega⟩ by_cases h6 : x < c · exact ⟨_, Or.inr (Or.inr (Or.inl rfl)), by dsimp only; omega⟩ · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inl rfl))), by dsimp only; omega⟩
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_product- A pair belongs to a Cartesian product of finite sets if and only if its first coordinate belongs to the first set and its second coordinate belongs to the second.
Finset.mem_Ico- A value belongs to the half-open interval [a, b) if and only if it is at least a and strictly less than b.
List.mem_cons- An element belongs to a prepended list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil- No element belongs to the empty list.
or_false- Disjunction with false is logically equivalent to the original proposition: (P ∨ False) ↔ P.
List.pairwise_cons- A relation holds pairwise on a :: l if and only if a is related to every element of l and the relation holds pairwise on l.
forall_eq_or_imp- A universal quantification over a = a' ∨ Q a is equivalent to the property at a' together with universal quantification over Q a.
forall_eq- A universal quantification over elements equal to a' is equivalent to evaluating the predicate at a'.
List.Pairwise.nil- Any relation holds pairwise vacuously on the empty list.
and_true- Conjunction with true is logically equivalent to the original proposition: (P ∧ True) ↔ P.
Finset.mem_biUnion- An element belongs to an indexed union of finite sets if and only if it belongs to one of the component sets.
List.mem_toFinset- An element belongs to the finite set formed from a list if and only if it belongs to the list.
Finset.mem_range- A natural number belongs to the range {0, …, n - 1} if and only if it is strictly less than n.
Or.inl- From a proof of A, deduce A ∨ B.
Or.inr- From a proof of B, deduce A ∨ B.
- The pairwise disjointness and non-congruence checks in Step 6, as well as the rectangle coverage in Steps 7 and 8, involve dozens of arithmetic cases that Lean resolves using the `omega` decision procedure.
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_seven_rects_is_partition (p q : ℕ) (hpar : p % 2 = q % 2) (hqp : q < p) (hp : p < 7 * q) : mondrian_is_partition (105 * q) (mondrian_seven_rects p q) := by have ha : 7 * (7 * q - p) + 7 * p = 49 * q := by omega have hd : 5 * (8 * q - p) + 5 * p = 40 * q := by omega have he : 5 * (13 * q - p) + 5 * p = 65 * q := by omega have hf : 2 * (15 * (7 * q + p) / 2) = 105 * q + 15 * p := by omega have hdisj : ∀ r s : ℕ × ℕ × ℕ × ℕ, (r.2.1 ≤ s.1 ∨ s.2.1 ≤ r.1 ∨ r.2.2.2 ≤ s.2.2.1 ∨ s.2.2.2 ≤ r.2.2.1) → Disjoint (mondrian_rect_cells r) (mondrian_rect_cells s) := by intro r s h rw [Finset.disjoint_left] rintro ⟨x, y⟩ h1 h2 simp only [mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico] at h1 h2 omega unfold mondrian_seven_rects generalize 7 * (7 * q - p) = a at ha ⊢ generalize 5 * (8 * q - p) = d at hd ⊢ generalize 5 * (13 * q - p) = e at he ⊢ generalize 15 * (7 * q + p) / 2 = f at hf ⊢ generalize hc : 7 * (7 * q + p) = c refine ⟨by simp, ?_, ?_, ?_⟩ · intro r hr simp only [List.mem_cons, List.not_mem_nil, or_false] at hr rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> dsimp only <;> omega · simp only [List.pairwise_cons, List.mem_cons, List.not_mem_nil, or_false, forall_eq_or_imp, forall_eq, List.Pairwise.nil, and_true] and_intros all_goals first | exact fun _ h => h.elim | exact hdisj _ _ (by dsimp only; omega) | (simp only [mondrian_rect_congruent, mondrian_rect_width, mondrian_rect_height]; omega) · ext ⟨x, y⟩ simp only [Finset.mem_biUnion, List.mem_toFinset, List.mem_cons, List.not_mem_nil, or_false, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico, Finset.mem_range] constructor · rintro ⟨r, hr, h⟩ rcases hr with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> dsimp only at h <;> omega · intro h by_cases h1 : y < d · by_cases h2 : x < a · exact ⟨_, Or.inr (Or.inl rfl), by dsimp only; omega⟩ · exact ⟨_, Or.inl rfl, by dsimp only; omega⟩ by_cases h3 : y < e · by_cases h2 : x < a · exact ⟨_, Or.inr (Or.inl rfl), by dsimp only; omega⟩ by_cases h4 : x < 42 * q · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl rfl))))), by dsimp only; omega⟩ · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inl rfl)))), by dsimp only; omega⟩ by_cases h5 : y < f · by_cases h2 : x < a · exact ⟨_, Or.inr (Or.inl rfl), by dsimp only; omega⟩ by_cases h4 : x < 42 * q · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inl rfl))))), by dsimp only; omega⟩ by_cases h6 : x < c · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inr (Or.inr (Or.inr rfl))))), by dsimp only; omega⟩ · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inl rfl))), by dsimp only; omega⟩ by_cases h6 : x < c · exact ⟨_, Or.inr (Or.inr (Or.inl rfl)), by dsimp only; omega⟩ · exact ⟨_, Or.inr (Or.inr (Or.inr (Or.inl rfl))), by dsimp only; omega⟩