AFTD Auto-Formalizing Theoretical Domains

mondrian_sorted_pairs_eq_of_shared

theoremverified

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

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.

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

    lines 5–6

    uses Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left

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

    lines 7–11

    uses Nat.eq_of_mul_eq_mul_left, Prod.ext

      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
  3. 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.

    lines 12–18

    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
  4. 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.

    lines 19–25

    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
  5. 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.

    lines 26–29

    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

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