mondrian_rect_div_cells
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.
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.
uses
mondrian_rect_div,mondrian_rect_cells,Finset.mem_product,Finset.mem_Icosimp only [mondrian_rect_div, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico]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.
uses
mondrian_interval_divrw [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).
- After rewriting both coordinates with `mondrian_interval_div`, the left-hand and right-hand sides become identical, so the `rw` tactic automatically closes the goal by reflexivity.
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_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]