AFTD Auto-Formalizing Theoretical Domains

mondrian_rect_mul_cells

theoremverified

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.

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

    line 5

    uses mondrian_rect_mul, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico

      simp only [mondrian_rect_mul, mondrian_rect_cells, Finset.mem_product, Finset.mem_Ico]
  2. 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.

    lines 6–8

    uses Nat.le_div_iff_mul_le, Nat.div_lt_iff_lt_mul, Nat.mul_comm

      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]
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

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