mondrian_rect_mul_cells
A cell belongs to a rectangle with coordinates multiplied by positive a exactly when its quotient cell belongs to the original rectangle.
Statement
theorem mondrian_rect_mul_cells (a : ℕ) (ha : 0 < a)
(r : ℕ × ℕ × ℕ × ℕ) (i j : ℕ) :
(i, j) ∈ mondrian_rect_cells (mondrian_rect_mul a r) ↔
(i / a, j / a) ∈ 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 2
- 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_mulMultiply all four rectangle coordinates by a.
- Used by 1
- mondrian_partition_mulMultiplying all rectangle coordinates by a positive integer a sends an admissible c-square partition to an admissible a times c square…
The proof, explained
The proof unfolds the definition of cell membership for both rectangles into coordinate inequalities bounding the cells in half-open intervals. Because the scaling factor a is strictly positive, the division inequalities defining membership of (i / a, j / a) in the original rectangle are equivalent to multiplication inequalities on i and j. Commuting the products aligns these bounds exactly with those defining membership of (i, j) in the scaled rectangle.
Membership of a cell in a rectangle reduces to coordinate inequalities on its indices.
Unfolding the definitions of rectangle scaling (mondrian_rect_mul), the cell set of a rectangle (mondrian_rect_cells), and membership in the Cartesian product of half-open intervals (Finset.mem_product, Finset.mem_Ico), the equivalence becomes (a * r₁ ≤ i ∧ i < a * r₂) ∧ (a * r₃ ≤ j ∧ j < a * r₄) ↔ (r₁ ≤ i / a ∧ i / a < r₂) ∧ (r₃ ≤ j / a ∧ j / a < r₄).
uses
mondrian_rect_mul,mondrian_rect_cells,Finset.mem_product,Finset.mem_Icosimp only [mondrian_rect_mul, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico]The bounds on the quotient cell (i / a, j / a) are equivalent to the bounds on (i, j) for the scaled rectangle.
Because a > 0 (by ha), integer division satisfies x ≤ y / a ↔ x * a ≤ y (via Nat.le_div_iff_mul_le) and x / a < y ↔ x < y * a (via Nat.div_lt_iff_lt_mul). Applying these equivalences to clear division in each coordinate bound, and commuting the factors (Nat.mul_comm), makes both sides of the equivalence identical.
uses
Nat.le_div_iff_mul_le,Nat.div_lt_iff_lt_mul,Nat.mul_commrw [Nat.le_div_iff_mul_le ha, Nat.div_lt_iff_lt_mul ha, Nat.le_div_iff_mul_le ha, Nat.div_lt_iff_lt_mul ha] simp only [Nat.mul_comm]
mondrian_rect_mul- Scales a rectangle by multiplying each of its four bounding coordinates by a given factor.
mondrian_rect_cells- The finite set of grid cells in a rectangle, defined as the Cartesian product of half-open intervals [r₁, r₂) × [r₃, r₄).
Finset.mem_product- A pair belongs to the Cartesian product of two finite sets if and only if its first component is in the first set and its second component is in the second set.
Finset.mem_Ico- An element belongs to the half-open interval [a, b) if and only if it is at least a and strictly less than b.
Nat.le_div_iff_mul_le- For a positive divisor k, x ≤ y / k if and only if x * k ≤ y in the natural numbers.
Nat.div_lt_iff_lt_mul- For a positive divisor k, x / k < y if and only if x < y * k in the natural numbers.
Nat.mul_comm- Multiplication of natural numbers is commutative (n * m = m * n).
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_mul_cells (a : ℕ) (ha : 0 < a) (r : ℕ × ℕ × ℕ × ℕ) (i j : ℕ) : (i, j) ∈ mondrian_rect_cells (mondrian_rect_mul a r) ↔ (i / a, j / a) ∈ mondrian_rect_cells r := by simp only [mondrian_rect_mul, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico] rw [Nat.le_div_iff_mul_le ha, Nat.div_lt_iff_lt_mul ha, Nat.le_div_iff_mul_le ha, Nat.div_lt_iff_lt_mul ha] simp only [Nat.mul_comm]