mondrian_interval_div
An integer cell i belongs to the coordinatewise quotient of an interval precisely when the last cell of its a-block belongs to the original interval, for a positive.
Statement
theorem mondrian_interval_div (a x y i : ℕ) (ha : 0 < a) :
(x / a ≤ i ∧ i < y / a) ↔
x ≤ a * (i + 1) - 1 ∧ a * (i + 1) - 1 < y- 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- Used by 2
- 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…
- mondrian_rect_div_cellsMembership in a coordinatewise divided rectangle is equivalent to membership of the corresponding last cell of the original square block.
The proof, explained
The proof clears the division by a to express the membership of i in the quotient interval in terms of the original coordinate bounds. Specifically, x / a ≤ i and i < y / a are rewritten as x < a * (i + 1) and a * (i + 1) ≤ y. Because a > 0 implies a * (i + 1) > 0, these bounds are equivalent over ℕ to x ≤ a * (i + 1) - 1 and a * (i + 1) - 1 < y by discrete integer arithmetic.
x / a ≤ i ↔ x < a * (i + 1)
By Nat.lt_succ_iff, the inequality x / a ≤ i is equivalent to x / a < i + 1. Since a > 0, clearing the division using Nat.div_lt_iff_lt_mul yields x < (i + 1) * a, and commuting the factors with Nat.mul_comm produces x < a * (i + 1).
uses
Nat.lt_succ_iff,Nat.div_lt_iff_lt_mul,Nat.mul_commhave h1 : x / a ≤ i ↔ x < a * (i + 1) := by rw [← Nat.lt_succ_iff, Nat.div_lt_iff_lt_mul ha, Nat.mul_comm]
i < y / a ↔ a * (i + 1) ≤ y
By Nat.lt_iff_add_one_le, the strict inequality i < y / a is equivalent to i + 1 ≤ y / a. Because a > 0, Nat.le_div_iff_mul_le transforms this into (i + 1) * a ≤ y, which becomes a * (i + 1) ≤ y after commuting the product with Nat.mul_comm.
uses
Nat.lt_iff_add_one_le,Nat.le_div_iff_mul_le,Nat.mul_commhave h2 : i < y / a ↔ a * (i + 1) ≤ y := by rw [Nat.lt_iff_add_one_le, Nat.le_div_iff_mul_le ha, Nat.mul_comm]
(x / a ≤ i ∧ i < y / a) ↔ (x ≤ a * (i + 1) - 1 ∧ a * (i + 1) - 1 < y)
Substituting the two previous equivalences reduces the left-hand side to x < a * (i + 1) ∧ a * (i + 1) ≤ y. Because a > 0 and i + 1 > 0, their product a * (i + 1) is strictly positive by Nat.mul_pos. For any positive integer M = a * (i + 1), the bounds x < M and M ≤ y are equivalent over the natural numbers to x ≤ M - 1 and M - 1 < y, so the linear integer arithmetic decision procedure omega finishes the proof.
uses
Nat.mul_posrw [h1, h2] have hp : 0 < a * (i + 1) := Nat.mul_pos ha (by omega) omega
Nat.lt_succ_iff- For natural numbers m and n, m < n + 1 if and only if m ≤ n.
Nat.div_lt_iff_lt_mul- For k > 0, integer division x / k < y is equivalent to x < y * k.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Nat.lt_iff_add_one_le- For natural numbers m and n, m < n if and only if m + 1 ≤ n.
Nat.le_div_iff_mul_le- For k > 0, x ≤ y / k is equivalent to x * k ≤ y.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
- In natural number arithmetic, subtraction truncates at zero (0 - 1 = 0), so the equivalences M - 1 < y ↔ M ≤ y and x ≤ M - 1 ↔ x < M require M > 0. Establishing 0 < a * (i + 1) is necessary before omega can complete the proof.
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_interval_div (a x y i : ℕ) (ha : 0 < a) : (x / a ≤ i ∧ i < y / a) ↔ x ≤ a * (i + 1) - 1 ∧ a * (i + 1) - 1 < y := by have h1 : x / a ≤ i ↔ x < a * (i + 1) := by rw [← Nat.lt_succ_iff, Nat.div_lt_iff_lt_mul ha, Nat.mul_comm] have h2 : i < y / a ↔ a * (i + 1) ≤ y := by rw [Nat.lt_iff_add_one_le, Nat.le_div_iff_mul_le ha, Nat.mul_comm] rw [h1, h2] have hp : 0 < a * (i + 1) := Nat.mul_pos ha (by omega) omega