AFTD Auto-Formalizing Theoretical Domains

mondrian_two_prime_area_sides_dvd

theoremverified

For a perfect admissible square partition with common area q^s*p^t and q dividing the square side, both dimensions of every tile are divisible by q.

Statement

theorem mondrian_two_prime_area_sides_dvd (n p q s t : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q)
    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n)
    (harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) :
    ∀ r ∈ P, q ∣ mondrian_rect_width r ∧ q ∣ mondrian_rect_height r
Source
For OP-280, arXiv:2610.19193, Section 1. Related work: arXiv:2007.09639, Theorem 4.1; HAL:hal-05729522v2, Lemma 2.3 (primitive cross sections and common-side descent). The periodic residue argument and the uniform two-prime common-area exclusion are developed here.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
  • mondrian_defect_zero_of_equalA rectangle list whose members all have the same area has defect zero, including the empty list.
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • mondrian_partition_swapExchanging the x and y coordinate pairs of every rectangle preserves an admissible partition of the n-square.
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
  • mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_swapExchange the x and y coordinate pairs of an integer rectangle.
  • mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_two_prime_area_width_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, every tile width is divisible by q.
Used by 3

The proof, explained

The theorem is proved by combining the width divisibility result with symmetry across the diagonal. First, the auxiliary theorem mondrian_two_prime_area_width_dvd directly shows that q divides the width of every rectangle in the partition. Reflecting the partition across the diagonal produces another valid defect-0 partition with identical tile areas, so applying the same width divisibility result to the reflected partition shows that q divides the width of every reflected rectangle. Since the width of a reflected tile is the height of the original tile, q divides both dimensions of every rectangle in the partition.

  1. For every rectangle in P, q divides its width.

    Applying the previously proved theorem mondrian_two_prime_area_width_dvd directly to the partition P establishes that q divides the width of every rectangle, since P is a defect-0 partition of the n × n square with q ∣ n and all tiles having area q^s * p^t.

    line 6

    uses mondrian_two_prime_area_width_dvd

      have hw := mondrian_two_prime_area_width_dvd n p q s t P hp hq hP hz hqn harea
  2. The swapped partition is a valid partition of the n × n square with defect 0 and common tile area q^s * p^t.

    Reflecting each rectangle across the diagonal via mondrian_rect_swap produces another partition of the square (mondrian_partition_swap). For each rectangle r in this swapped partition, r is the swap of some tile u ∈ P (List.mem_map.mp). Coordinate swapping interchanges width and height, so by commutativity of multiplication (Nat.mul_comm), the area of r equals the area of u, namely q^s * p^t. Since all tiles in the swapped partition have equal area, its defect is 0 by mondrian_defect_zero_of_equal.

    lines 7–15

    uses mondrian_partition_swap, List.mem_map.mp, Nat.mul_comm, mondrian_defect_zero_of_equal

      have hswapP := mondrian_partition_swap n P hP
      have hswapA : ∀ r ∈ P.map mondrian_rect_swap,
          mondrian_rect_area r = q ^ s * p ^ t := by
        intro r hr
        obtain ⟨u, hu, rfl⟩ := List.mem_map.mp hr
        have hh := harea u hu
        simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height,
          mondrian_rect_swap, Nat.mul_comm] using hh
      have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * p ^ t) hswapA
  3. For every rectangle in the swapped partition, q divides its width.

    Applying mondrian_two_prime_area_width_dvd to the swapped partition (which was shown to be valid, have defect 0, and have all tile areas equal to q^s * p^t) establishes that q divides the width of every swapped tile.

    lines 16–17

    uses mondrian_two_prime_area_width_dvd

      have hh := mondrian_two_prime_area_width_dvd n p q s t (P.map mondrian_rect_swap)
        hp hq hswapP hswapZ hqn hswapA
  4. For every rectangle r ∈ P, q divides both the width and the height of r.

    Fix an arbitrary tile r ∈ P. We already know that q divides its width. Furthermore, swapping r produces an element of the swapped partition (List.mem_map.mpr), so q divides the width of the swapped rectangle. Since the width of the swapped rectangle is definitionally the height of r, q divides the height of r as well.

    lines 18–21

    uses List.mem_map.mpr

      intro r hr
      refine ⟨hw r hr, ?_⟩
      have hx := hh (mondrian_rect_swap r) (List.mem_map.mpr ⟨r, hr, rfl⟩)
      simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx
mondrian_two_prime_area_width_dvd
In a defect-0 partition of an n × n square where every tile has area q^s * p^t (for primes p and q) and q divides n, the prime q divides the width of every tile.
mondrian_partition_swap
Swapping the x- and y-coordinates of each rectangle in a partition of an n × n square yields another valid partition of the same square.
List.mem_map.mp
If an element belongs to the image of a list under a function f, then it is equal to f(a) for some element a in the original list.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_defect_zero_of_equal
If every rectangle in a list has the same area, then the defect of the list is zero.
List.mem_map.mpr
If an element has the form f(a) for some element a in a list, then it belongs to the mapped list.

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_two_prime_area_sides_dvd (n p q s t : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q)    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n)    (harea : ∀ r ∈ P, mondrian_rect_area r = q ^ s * p ^ t) :    ∀ r ∈ P, q ∣ mondrian_rect_width r ∧ q ∣ mondrian_rect_height r := by  have hw := mondrian_two_prime_area_width_dvd n p q s t P hp hq hP hz hqn harea  have hswapP := mondrian_partition_swap n P hP  have hswapA : ∀ r ∈ P.map mondrian_rect_swap,      mondrian_rect_area r = q ^ s * p ^ t := by    intro r hr    obtain ⟨u, hu, rfl⟩ := List.mem_map.mp hr    have hh := harea u hu    simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height,      mondrian_rect_swap, Nat.mul_comm] using hh  have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * p ^ t) hswapA  have hh := mondrian_two_prime_area_width_dvd n p q s t (P.map mondrian_rect_swap)    hp hq hswapP hswapZ hqn hswapA  intro r hr  refine ⟨hw r hr, ?_⟩  have hx := hh (mondrian_rect_swap r) (List.mem_map.mpr ⟨r, hr, rfl⟩)  simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx
See it in the graphDiscuss this resultChallenge it