AFTD Auto-Formalizing Theoretical Domains

mondrian_rect_div_cells

theoremverified

Membership in a coordinatewise divided rectangle is equivalent to membership of the corresponding last cell of the original square block.

Statement

theorem mondrian_rect_div_cells (a : ℕ) (ha : 0 < a)
    (r : ℕ × ℕ × ℕ × ℕ) (i j : ℕ) :
    (i, j) ∈ mondrian_rect_cells (mondrian_rect_div a r) ↔
      (a * (i + 1) - 1, a * (j + 1) - 1) ∈ mondrian_rect_cells r
Source
Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • mondrian_interval_divAn integer cell i belongs to the coordinatewise quotient of an interval precisely when the last cell of its a-block belongs to the…
  • 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_divDivide all four rectangle coordinates by a using natural-number division.
Used by 1
  • mondrian_partition_divAn admissible partition of the a times c square, with every tile side a multiple of positive a, becomes an admissible partition of the…

The proof, explained

The equivalence is proved by decomposing two-dimensional rectangle cell membership into independent one-dimensional interval conditions on each coordinate. Unfolding definitions reduces the statement to pairs of coordinate inequalities, which are then matched by applying the one-dimensional division equivalence `mondrian_interval_div` separately to each coordinate axis.

  1. Membership in the divided rectangle and membership of the scaled point in r both reduce to coordinatewise half-open interval inequalities.

    Unfolding the definitions of rectangle division (`mondrian_rect_div`) and the set of cells in a rectangle (`mondrian_rect_cells`), and expanding membership in a Cartesian product (`Finset.mem_product`) of half-open intervals (`Finset.mem_Ico`), expresses each side as a conjunction of inequalities: (r.1 / a ≤ i ∧ i < r.2.1 / a) ∧ (r.2.2.1 / a ≤ j ∧ j < r.2.2.2 / a) on the left, and (r.1 ≤ a * (i + 1) - 1 ∧ a * (i + 1) - 1 < r.2.1) ∧ (r.2.2.1 ≤ a * (j + 1) - 1 ∧ a * (j + 1) - 1 < r.2.2.2) on the right.

    lines 5–6

    uses mondrian_rect_div, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico

      simp only [mondrian_rect_div, mondrian_rect_cells,
        Finset.mem_product, Finset.mem_Ico]
  2. The two sides are equivalent, completing the proof.

    Applying the one-dimensional division equivalence `mondrian_interval_div` to the horizontal coordinate (with bounds r.1 and r.2.1) and to the vertical coordinate (with bounds r.2.2.1 and r.2.2.2) replaces the divided-coordinate inequalities on the left with the scaled-cell inequalities on the right. Both sides become identical, closing the equivalence.

    lines 7–8

    uses mondrian_interval_div

      rw [mondrian_interval_div a r.1 r.2.1 i ha,
        mondrian_interval_div a r.2.2.1 r.2.2.2 j ha]
Finset.mem_Ico
An element x belongs to the half-open interval [a, b) if and only if a ≤ x and x < b.
Finset.mem_product
An ordered pair belongs to the Cartesian product s ×ˢ t of two finite sets if and only if its first component is in s and its second component is in t.
mondrian_interval_div
For a > 0, an integer i satisfies x / a ≤ i < y / a if and only if the last cell in block i, namely a * (i + 1) - 1, satisfies x ≤ a * (i + 1) - 1 < y.
mondrian_rect_cells
The set of grid cells belonging to a rectangle r = (x₁, x₂, y₁, y₂) is the Cartesian product of half-open intervals [x₁, x₂) ×ˢ [y₁, y₂).
mondrian_rect_div
Coordinatewise division of a rectangle r = (x₁, x₂, y₁, y₂) by a yields the rectangle (x₁ / a, x₂ / a, y₁ / a, y₂ / 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_rect_div_cells (a : ℕ) (ha : 0 < a)    (r : ℕ × ℕ × ℕ × ℕ) (i j : ℕ) :    (i, j) ∈ mondrian_rect_cells (mondrian_rect_div a r) ↔      (a * (i + 1) - 1, a * (j + 1) - 1) ∈ mondrian_rect_cells r := by  simp only [mondrian_rect_div, mondrian_rect_cells,    Finset.mem_product, Finset.mem_Ico]  rw [mondrian_interval_div a r.1 r.2.1 i ha,    mondrian_interval_div a r.2.2.1 r.2.2.2 j ha]
See it in the graphDiscuss this resultChallenge it