mondrian_seven_rects_defect
With E = p² − 19q², the defect of the seven-rectangle dissection is 140|E|.
Statement
theorem mondrian_seven_rects_defect (p q : ℕ) (hpar : p % 2 = q % 2) (hqp : q < p)
(hp : p < 7 * q) :
(mondrian_defect (mondrian_seven_rects p q) : ℤ) = 140 * |(p : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2|- Source
- arXiv:2610.19193 (A Bounded-Defect Construction for the Mondrian Art Problem), Proposition 1, formula (4); serves mondrian_seven_rects_partition_defect.
- Verified
- 15 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
- 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_areaThe area |R| = width × height of a rectangle.
- Used by 3
- 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)…
- mondrian_seven_rects_defect_geWithin the seven-rectangle family, the defect is always at least 280 (in particular never 0): if p, q are odd then p² − 19q² ≡ 2 (mod 4),…
The proof, explained
Since $p$ and $q$ have the same parity and $q < p < 7q$, we write $p = q + 2s$ with $s < 3q$. Evaluating the areas of the seven rectangles in the dissection reveals that each area in $\mathbb{Z}$ has the form $1575q^2 + c_i F$, where $F = 2s^2 + 2qs - 9q^2 = \frac{1}{2}(p^2 - 19q^2)$ and the coefficients $c_i$ belong to $\{-105, -70, 0, 175\}$. A case split on the sign of $F$ determines which rectangle attains the maximum area and which attains the minimum area. In both cases, the difference between the maximum and minimum area evaluates to $(175 - (-105))|F| = 280|F| = 140|p^2 - 19q^2|$, establishing the defect formula.
$p$ can be written as $q + 2s$ for some $s < 3q$.
Because $p$ and $q$ have the same parity ($p \equiv q \pmod 2$) and $q < p$, their difference $p - q$ is positive and even, so $p = q + 2s$ with $s = (p - q) / 2$. The hypothesis $p < 7q$ translates to $q + 2s < 7q$, which gives $s < 3q$ by linear arithmetic (`omega`).
obtain ⟨s, rfl⟩ : ∃ s, p = q + 2 * s := ⟨(p - q) / 2, by omega⟩ have hs3 : s < 3 * q := by omega
The areas of the seven rectangles in `mondrian_seven_rects (q + 2 * s) q` evaluate to explicit factored forms in $q$ and $s$.
Unfolding the definitions of `mondrian_seven_rects`, `mondrian_rect_area`, `mondrian_rect_width`, and `mondrian_rect_height`, and simplifying list mapping with `List.map_cons`, `List.map_nil`, `List.cons.injEq`, and `and_true`, reduces the evaluation to verifying seven width-height products. Each linear factor simplifies to the required form by linear arithmetic (`omega`).
uses
mondrian_seven_rects,List.map_cons,List.map_nil,mondrian_rect_area,mondrian_rect_width,mondrian_rect_height,List.cons.injEq,and_truehave hmap : (mondrian_seven_rects (q + 2 * s) q).map mondrian_rect_area = [(63 * q + 14 * s) * (35 * q - 10 * s), (42 * q - 14 * s) * (60 * q + 15 * s), (56 * q + 14 * s) * (45 * q - 15 * s), (49 * q - 14 * s) * (45 * q + 10 * s), (63 * q) * (25 * q), (14 * s) * (25 * q + 25 * s), (14 * q + 14 * s) * (25 * s)] := by simp only [mondrian_seven_rects, List.map_cons, List.map_nil, mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, List.cons.injEq, and_true] refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> congr 1 <;> omega
The defect of the dissection is expressed as the difference between the maximum and minimum of the seven rectangle areas.
Rewriting with the definition of `mondrian_defect` and the computed list of areas `hmap` replaces the defect with the difference between the maximum and minimum elements of the list of seven areas.
uses
mondrian_defectrw [mondrian_defect, hmap]The four subtractions inside the rectangle dimensions do not underflow: $10s \le 35q$, $14s \le 42q$, $15s \le 45q$, and $14s \le 49q$.
Since $s < 3q$, each inequality follows directly by linear arithmetic (`omega`).
have c1 : 10 * s ≤ 35 * q := by omega have c2 : 14 * s ≤ 42 * q := by omega have c3 : 15 * s ≤ 45 * q := by omega have c4 : 14 * s ≤ 49 * q := by omega
With $F = 2s^2 + 2qs - 9q^2 \in \mathbb{Z}$, the quantity $p^2 - 19q^2$ equals $2F$.
We introduce the integer variable $F = 2s^2 + 2qs - 9q^2$. Substituting $p = q + 2s$, the expression $(q + 2s)^2 - 19q^2$ expands algebraically to $4s^2 + 4qs - 18q^2 = 2F$, verified by polynomial ring arithmetic (`ring`). We then rewrite the theorem's goal using this relation.
-- F = 2 s² + 2 q s − 9 q², so that p² − 19 q² = 2F obtain ⟨F, hF⟩ : ∃ F : ℤ, F = 2 * (s : ℤ) ^ 2 + 2 * (q : ℤ) * s - 9 * (q : ℤ) ^ 2 := ⟨_, rfl⟩ have hE : ((q + 2 * s : ℕ) : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 = 2 * F := by rw [hF]; push_cast; ring rw [hE]
When cast to $\mathbb{Z}$, the seven rectangle areas are $1575q^2 - 70F$, $1575q^2 - 105F$, $1575q^2 - 105F$, $1575q^2 - 70F$, $1575q^2$, $1575q^2 + 175F$, and $1575q^2 + 175F$.
Each product is expanded in $\mathbb{Z}$. Subtractions in natural numbers are converted to integer subtractions using `Nat.cast_sub` with the non-negativity bounds $c_1, \dots, c_4$. Expanding $F = 2s^2 + 2qs - 9q^2$ and simplifying by ring arithmetic (`ring`) shows that every area takes the form $1575q^2 + c_i F$ for coefficients $c_i \in \{-105, -70, 0, 175\}$.
uses
Nat.cast_subhave A1 : (((63 * q + 14 * s) * (35 * q - 10 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 70 * F := by rw [hF]; push_cast [Nat.cast_sub c1]; ring have A2 : (((42 * q - 14 * s) * (60 * q + 15 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 105 * F := by rw [hF]; push_cast [Nat.cast_sub c2]; ring have A3 : (((56 * q + 14 * s) * (45 * q - 15 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 105 * F := by rw [hF]; push_cast [Nat.cast_sub c3]; ring have A4 : (((49 * q - 14 * s) * (45 * q + 10 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 70 * F := by rw [hF]; push_cast [Nat.cast_sub c4]; ring have A5 : (((63 * q) * (25 * q) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 := by push_cast; ring have A6 : (((14 * s) * (25 * q + 25 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 + 175 * F := by rw [hF]; push_cast; ring have A7 : (((14 * q + 14 * s) * (25 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 + 175 * F := by rw [hF]; push_cast; ring
The area expressions and $q^2$ are abstracted into variables $x_1, \dots, x_7$ and $Q$.
We replace the seven explicit area expressions with names $x_1, \dots, x_7$ and substitute $Q = q^2$. This isolates the area comparisons to their linear dependence on $F$.
generalize (63 * q + 14 * s) * (35 * q - 10 * s) = x1 at A1 ⊢ generalize (42 * q - 14 * s) * (60 * q + 15 * s) = x2 at A2 ⊢ generalize (56 * q + 14 * s) * (45 * q - 15 * s) = x3 at A3 ⊢ generalize (49 * q - 14 * s) * (45 * q + 10 * s) = x4 at A4 ⊢ generalize (63 * q) * (25 * q) = x5 at A5 ⊢ generalize (14 * s) * (25 * q + 25 * s) = x6 at A6 ⊢ generalize (14 * q + 14 * s) * (25 * s) = x7 at A7 ⊢ clear hF hE generalize (q : ℤ) ^ 2 = Q at *
The argument divides into two cases: $F \ge 0$ and $F < 0$.
By linear order trichotomy (`le_or_gt`), either $0 \le F$ or $F < 0$.
uses
le_or_gtrcases le_or_gt 0 F with hF0 | hF0
When $F \ge 0$, the maximum area is $x_6$, the minimum area is $x_2$, and the defect is $140|E|$.
Because $F \ge 0$, the areas $1575Q + c_i F$ are ordered by their coefficients $c_i$. The maximal coefficient is $+175$ (giving $x_6$ as maximum) and the minimal coefficient is $-105$ (giving $x_2$ as minimum). Using `List.max?_eq_some_iff'` and `List.min?_eq_some_iff'`, membership in the list is decomposed by `List.mem_cons`, `List.not_mem_nil`, and `or_false`, with all comparisons verified by `omega`. The defect is therefore $x_6 - x_2 = (1575Q + 175F) - (1575Q - 105F) = 280F$. Since $F \ge 0$, we have $|2F| = 2F$ by `abs_of_nonneg`, so $140|2F| = 280F$, which matches.
uses
List.max?_eq_some_iff',List.min?_eq_some_iff',List.mem_cons,List.not_mem_nil,or_false,Option.getD_some,abs_of_nonneg· have hmax : [x1, x2, x3, x4, x5, x6, x7].max? = some x6 := by rw [List.max?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega have hmin : [x1, x2, x3, x4, x5, x6, x7].min? = some x2 := by rw [List.min?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega rw [hmax, hmin, Option.getD_some, Option.getD_some, abs_of_nonneg (by omega)] omega
When $F < 0$, the maximum area is $x_2$, the minimum area is $x_6$, and the defect is $140|E|$.
Because $F < 0$, the order of the coefficients reverses: the negative coefficient $-105$ yields the maximum area $x_2$, while $+175$ yields the minimum area $x_6$. Again, `List.max?_eq_some_iff'` and `List.min?_eq_some_iff'` identify the extremes, with membership checked by `List.mem_cons`, `List.not_mem_nil`, and `or_false`. The defect is $x_2 - x_6 = -280F$. Since $F < 0$, $|2F| = -2F$ by `abs_of_neg`, giving $140|2F| = -280F$, which concludes the proof.
uses
List.max?_eq_some_iff',List.min?_eq_some_iff',List.mem_cons,List.not_mem_nil,or_false,Option.getD_some,abs_of_neg· have hmax : [x1, x2, x3, x4, x5, x6, x7].max? = some x2 := by rw [List.max?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega have hmin : [x1, x2, x3, x4, x5, x6, x7].min? = some x6 := by rw [List.min?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega rw [hmax, hmin, Option.getD_some, Option.getD_some, abs_of_neg (by omega)] omega
mondrian_seven_rects- the dissection into seven rectangles $(x_1, x_2, y_1, y_2)$ parameterized by natural numbers $p$ and $q$
List.map_cons- mapping a function over a non-empty list applies it to the head and recurses on the tail: `List.map f (a :: l) = f a :: List.map f l`
List.map_nil- mapping a function over the empty list gives the empty list: `List.map f [] = []`
mondrian_rect_area- the area of a rectangle, defined as width times height
mondrian_rect_width- the width of a rectangle $(x_1, x_2, y_1, y_2)$, defined as $x_2 - x_1$
mondrian_rect_height- the height of a rectangle $(x_1, x_2, y_1, y_2)$, defined as $y_2 - y_1$
List.cons.injEq- two non-empty lists are equal if and only if their heads are equal and their tails are equal
and_true- conjunction with True simplifies: $(p \land \text{True}) \leftrightarrow p$
mondrian_defect- the defect of a dissection, defined as the maximum rectangle area minus the minimum rectangle area (defaulting to 0 on an empty list)
Nat.cast_sub- for natural numbers $m \le n$, the integer cast of their difference is the difference of their integer casts: $\uparrow(n - m) = \uparrow n - \uparrow m$
le_or_gt- in a linear order, either $a \le b$ or $b < a$
List.max?_eq_some_iff'- the maximum of a list of natural numbers is `some a` if and only if $a$ is in the list and every element $b$ in the list satisfies $b \le a$
List.min?_eq_some_iff'- the minimum of a list of natural numbers is `some a` if and only if $a$ is in the list and every element $b$ in the list satisfies $a \le b$
List.mem_cons- an element belongs to $b :: l$ if and only if it equals $b$ or belongs to $l$
List.not_mem_nil- the empty list contains no elements
or_false- disjunction with False simplifies: $(p \lor \text{False}) \leftrightarrow p$
Option.getD_some- extracting a value from `some a` with default fallback $b$ returns $a$: `(some a).getD b = a`
abs_of_nonneg- if $0 \le a$, then $|a| = a$
abs_of_neg- if $a < 0$, then $|a| = -a$
- The rectangle dimensions and area identities involve extensive polynomial and linear arithmetic over ℕ and ℤ, which Lean verifies using `omega`, `ring`, and `push_cast`.
- Before casting natural number subtractions into integer expressions, the proof explicitly proves four non-negativity bounds (c1 through c4) so that `Nat.cast_sub` can be applied without truncated subtraction issues.
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_defect (p q : ℕ) (hpar : p % 2 = q % 2) (hqp : q < p) (hp : p < 7 * q) : (mondrian_defect (mondrian_seven_rects p q) : ℤ) = 140 * |(p : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2| := by obtain ⟨s, rfl⟩ : ∃ s, p = q + 2 * s := ⟨(p - q) / 2, by omega⟩ have hs3 : s < 3 * q := by omega have hmap : (mondrian_seven_rects (q + 2 * s) q).map mondrian_rect_area = [(63 * q + 14 * s) * (35 * q - 10 * s), (42 * q - 14 * s) * (60 * q + 15 * s), (56 * q + 14 * s) * (45 * q - 15 * s), (49 * q - 14 * s) * (45 * q + 10 * s), (63 * q) * (25 * q), (14 * s) * (25 * q + 25 * s), (14 * q + 14 * s) * (25 * s)] := by simp only [mondrian_seven_rects, List.map_cons, List.map_nil, mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, List.cons.injEq, and_true] refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> congr 1 <;> omega rw [mondrian_defect, hmap] have c1 : 10 * s ≤ 35 * q := by omega have c2 : 14 * s ≤ 42 * q := by omega have c3 : 15 * s ≤ 45 * q := by omega have c4 : 14 * s ≤ 49 * q := by omega -- F = 2 s² + 2 q s − 9 q², so that p² − 19 q² = 2F obtain ⟨F, hF⟩ : ∃ F : ℤ, F = 2 * (s : ℤ) ^ 2 + 2 * (q : ℤ) * s - 9 * (q : ℤ) ^ 2 := ⟨_, rfl⟩ have hE : ((q + 2 * s : ℕ) : ℤ) ^ 2 - 19 * (q : ℤ) ^ 2 = 2 * F := by rw [hF]; push_cast; ring rw [hE] have A1 : (((63 * q + 14 * s) * (35 * q - 10 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 70 * F := by rw [hF]; push_cast [Nat.cast_sub c1]; ring have A2 : (((42 * q - 14 * s) * (60 * q + 15 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 105 * F := by rw [hF]; push_cast [Nat.cast_sub c2]; ring have A3 : (((56 * q + 14 * s) * (45 * q - 15 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 105 * F := by rw [hF]; push_cast [Nat.cast_sub c3]; ring have A4 : (((49 * q - 14 * s) * (45 * q + 10 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 - 70 * F := by rw [hF]; push_cast [Nat.cast_sub c4]; ring have A5 : (((63 * q) * (25 * q) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 := by push_cast; ring have A6 : (((14 * s) * (25 * q + 25 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 + 175 * F := by rw [hF]; push_cast; ring have A7 : (((14 * q + 14 * s) * (25 * s) : ℕ) : ℤ) = 1575 * (q : ℤ) ^ 2 + 175 * F := by rw [hF]; push_cast; ring generalize (63 * q + 14 * s) * (35 * q - 10 * s) = x1 at A1 ⊢ generalize (42 * q - 14 * s) * (60 * q + 15 * s) = x2 at A2 ⊢ generalize (56 * q + 14 * s) * (45 * q - 15 * s) = x3 at A3 ⊢ generalize (49 * q - 14 * s) * (45 * q + 10 * s) = x4 at A4 ⊢ generalize (63 * q) * (25 * q) = x5 at A5 ⊢ generalize (14 * s) * (25 * q + 25 * s) = x6 at A6 ⊢ generalize (14 * q + 14 * s) * (25 * s) = x7 at A7 ⊢ clear hF hE generalize (q : ℤ) ^ 2 = Q at * rcases le_or_gt 0 F with hF0 | hF0 · have hmax : [x1, x2, x3, x4, x5, x6, x7].max? = some x6 := by rw [List.max?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega have hmin : [x1, x2, x3, x4, x5, x6, x7].min? = some x2 := by rw [List.min?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega rw [hmax, hmin, Option.getD_some, Option.getD_some, abs_of_nonneg (by omega)] omega · have hmax : [x1, x2, x3, x4, x5, x6, x7].max? = some x2 := by rw [List.max?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega have hmin : [x1, x2, x3, x4, x5, x6, x7].min? = some x6 := by rw [List.min?_eq_some_iff'] refine ⟨by simp, ?_⟩ intro b hb simp only [List.mem_cons, List.not_mem_nil, or_false] at hb rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> omega rw [hmax, hmin, Option.getD_some, Option.getD_some, abs_of_neg (by omega)] omega