AFTD Auto-Formalizing Theoretical Domains

mondrian_seven_rects_is_partition

theoremverified

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.

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

    lines 4–7

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

    lines 8–14

    uses Finset.disjoint_left, Finset.mem_product, Finset.mem_Ico

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

    lines 15–20

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

    line 21

      refine ⟨by simp, ?_, ?_, ?_⟩
  5. 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.

    lines 22–24

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

    lines 25–31

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

    lines 32–38

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

    lines 39–60

    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.

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