AFTD Auto-Formalizing Theoretical Domains

mondrian_seven_rects_defect

theoremverified

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.

  1. $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`).

    lines 4–5

      obtain ⟨s, rfl⟩ : ∃ s, p = q + 2 * s := ⟨(p - q) / 2, by omega⟩
      have hs3 : s < 3 * q := by omega
  2. 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`).

    lines 6–12

    uses mondrian_seven_rects, List.map_cons, List.map_nil, mondrian_rect_area, mondrian_rect_width, mondrian_rect_height, List.cons.injEq, and_true

      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
  3. 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.

    line 13

    uses mondrian_defect

      rw [mondrian_defect, hmap]
  4. 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`).

    lines 14–17

      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
  5. 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.

    lines 18–21

      -- 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]
  6. 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\}$.

    lines 22–34

    uses Nat.cast_sub

      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
  7. 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$.

    lines 35–43

      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 *
  8. 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$.

    line 44

    uses le_or_gt

      rcases le_or_gt 0 F with hF0 | hF0
  9. 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.

    lines 45–58

    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
  10. 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.

    lines 59–72

    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$

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

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
See it in the graphDiscuss this resultChallenge it