mondrian_sorted_pairs_eq_of_shared
Two increasing positive factor pairs of the same nonzero area that share a side length are equal.
Statement
theorem mondrian_sorted_pairs_eq_of_shared (x y : ℕ × ℕ) (A : ℕ)
(hA : 0 < A) (hxp : x.1 * x.2 = A) (hyp : y.1 * y.2 = A)
(hxo : x.1 ≤ x.2) (hyo : y.1 ≤ y.2)
(h : x.1 = y.1 ∨ x.1 = y.2 ∨ x.2 = y.1 ∨ x.2 = y.2) : x = 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
Quot.soundpropext- Used by 2
- mondrian_shape_exponent_interval_boundA family of distinct sorted factor pairs that can be encoded by a chosen side C times p to an exponent in [lo,hi] has at most hi plus one…
- mondrian_prime_first_exponent_shape_boundWhen the p-adic exponent of k is exactly one, at most c unordered shapes of area A fit in a c times p to the e square with area k times A…
The proof, explained
We first deduce that both coordinates of x are strictly positive because their product equals the positive area A. We then case-split on which pair of coordinates coincides. When the matching coordinates are in the same position (x.1 = y.1 or x.2 = y.2), cancelling that factor from the equal area equations immediately shows the other coordinates match. When the matching coordinates are cross-paired (x.1 = y.2 or x.2 = y.1), cancellation swaps the remaining coordinates, which together with the sorting conditions x.1 ≤ x.2 and y.1 ≤ y.2 forces all four coordinates to be equal.
Both coordinates of x are strictly positive: 0 < x.1 and 0 < x.2.
Since the area A is strictly positive and x.1 * x.2 = A, the product x.1 * x.2 is strictly positive by linear arithmetic. By Nat.pos_of_mul_pos_right and Nat.pos_of_mul_pos_left, it follows that both factors x.1 and x.2 are strictly positive.
uses
Nat.pos_of_mul_pos_right,Nat.pos_of_mul_pos_lefthave hx1 : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2) have hx2 : 0 < x.2 := Nat.pos_of_mul_pos_left (by omega : 0 < x.1 * x.2)
If x.1 = y.1, then x = y.
We case-split on the hypothesis h that x and y share a coordinate. In the first case, x.1 = y.1. Since x.1 * x.2 = A and y.1 * y.2 = A, we have x.1 * x.2 = x.1 * y.2. Cancelling the factor x.1 > 0 using Nat.eq_of_mul_eq_mul_left yields x.2 = y.2. By Prod.ext, the two pairs are equal.
uses
Nat.eq_of_mul_eq_mul_left,Prod.extrcases h with h | h | h | h · have h2 : x.2 = y.2 := by apply Nat.eq_of_mul_eq_mul_left hx1 rw [hxp, h, hyp] exact Prod.ext h h2
If x.1 = y.2, then x = y.
In the second case, x.1 = y.2. Using commutativity of multiplication, x.1 * x.2 = A = y.2 * y.1 = x.1 * y.1. Cancelling x.1 > 0 with Nat.eq_of_mul_eq_mul_left gives x.2 = y.1. We now have x.1 ≤ x.2 = y.1 ≤ y.2 = x.1, so all four coordinates are equal. Linear arithmetic (omega) establishes x.1 = y.1 and x.2 = y.2, and Prod.ext concludes x = y.
uses
Nat.eq_of_mul_eq_mul_left,Nat.mul_comm,Prod.ext· have h2 : x.2 = y.1 := by apply Nat.eq_of_mul_eq_mul_left hx1 calc x.1 * x.2 = A := hxp _ = y.2 * y.1 := by rw [Nat.mul_comm, hyp] _ = x.1 * y.1 := by rw [h] apply Prod.ext <;> omega
If x.2 = y.1, then x = y.
In the third case, x.2 = y.1. Using commutativity, x.1 * x.2 = A = y.2 * y.1 = y.2 * x.2. Cancelling x.2 > 0 on the right using Nat.eq_of_mul_eq_mul_right gives x.1 = y.2. Then y.1 = x.2 ≥ x.1 = y.2 ≥ y.1, which forces x.1 = y.1 and x.2 = y.2 by linear arithmetic (omega). Applying Prod.ext concludes that x = y.
uses
Nat.eq_of_mul_eq_mul_right,Nat.mul_comm,Prod.ext· have h1 : x.1 = y.2 := by apply Nat.eq_of_mul_eq_mul_right hx2 calc x.1 * x.2 = A := hxp _ = y.2 * y.1 := by rw [Nat.mul_comm, hyp] _ = y.2 * x.2 := by rw [h] apply Prod.ext <;> omega
If x.2 = y.2, then x = y.
In the final case, x.2 = y.2. Substituting gives x.1 * x.2 = y.1 * x.2. Cancelling x.2 > 0 on the right with Nat.eq_of_mul_eq_mul_right yields x.1 = y.1. Combining the two coordinate equalities with Prod.ext gives x = y.
uses
Nat.eq_of_mul_eq_mul_right,Prod.ext· have h1 : x.1 = y.1 := by apply Nat.eq_of_mul_eq_mul_right hx2 rw [hxp, h, hyp] exact Prod.ext h1 h
Nat.pos_of_mul_pos_right- If the product a * b of two natural numbers is strictly positive, then a is strictly positive.
Nat.pos_of_mul_pos_left- If the product a * b of two natural numbers is strictly positive, then b is strictly positive.
Nat.eq_of_mul_eq_mul_left- If n > 0 and n * m = n * k for natural numbers, then m = k (cancellation on the left).
Nat.eq_of_mul_eq_mul_right- If m > 0 and n * m = k * m for natural numbers, then n = k (cancellation on the right).
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Prod.ext- Two ordered pairs are equal if their first components are equal and their second components are equal.
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_sorted_pairs_eq_of_shared (x y : ℕ × ℕ) (A : ℕ) (hA : 0 < A) (hxp : x.1 * x.2 = A) (hyp : y.1 * y.2 = A) (hxo : x.1 ≤ x.2) (hyo : y.1 ≤ y.2) (h : x.1 = y.1 ∨ x.1 = y.2 ∨ x.2 = y.1 ∨ x.2 = y.2) : x = y := by have hx1 : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2) have hx2 : 0 < x.2 := Nat.pos_of_mul_pos_left (by omega : 0 < x.1 * x.2) rcases h with h | h | h | h · have h2 : x.2 = y.2 := by apply Nat.eq_of_mul_eq_mul_left hx1 rw [hxp, h, hyp] exact Prod.ext h h2 · have h2 : x.2 = y.1 := by apply Nat.eq_of_mul_eq_mul_left hx1 calc x.1 * x.2 = A := hxp _ = y.2 * y.1 := by rw [Nat.mul_comm, hyp] _ = x.1 * y.1 := by rw [h] apply Prod.ext <;> omega · have h1 : x.1 = y.2 := by apply Nat.eq_of_mul_eq_mul_right hx2 calc x.1 * x.2 = A := hxp _ = y.2 * y.1 := by rw [Nat.mul_comm, hyp] _ = y.2 * x.2 := by rw [h] apply Prod.ext <;> omega · have h1 : x.1 = y.1 := by apply Nat.eq_of_mul_eq_mul_right hx2 rw [hxp, h, hyp] exact Prod.ext h1 h