AFTD Auto-Formalizing Theoretical Domains

mondrian_two_prime_area_width_dvd

theoremverified

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

Statement

theorem mondrian_two_prime_area_width_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
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 7
Used by 1
  • mondrian_two_prime_area_sides_dvdFor a perfect admissible square partition with common area q^s*p^t and q dividing the square side, both dimensions of every tile are…

The proof, explained

The theorem reduces the global divisibility property to a local arithmetic condition via mondrian_partition_width_dvd_of_height_prime_chain. That lemma guarantees that q divides every tile's width in the partition provided that any counterexample tile has height of the form q^s * p^a. Since each tile has area width * height = q^s * p^t, any tile whose width is coprime to q must absorb all q-factors into its height, immediately matching this required form by mondrian_prime_free_height_encoding.

  1. To show that q divides the width of every tile in P, it suffices to show that any tile whose width is not divisible by q has height of the form q^s * p^a for some exponent a.

    We apply mondrian_partition_width_dvd_of_height_prime_chain with divisor d = q, prime p, and constant C = q^s. Since P is a defect-free partition of a square of side n, q divides n, p is prime, and q^s > 0 (by pow_pos, since the prime q is strictly positive), the lemma reduces the conclusion to showing that every tile r ∈ P with width not divisible by q has height q^s * p^a for some a.

    line 6

    uses mondrian_partition_width_dvd_of_height_prime_chain, pow_pos

      apply mondrian_partition_width_dvd_of_height_prime_chain n q p (q ^ s) P hP hz hqn hp (pow_pos hq.pos s)
  2. Any tile r ∈ P whose width is not divisible by q has height equal to q^s * p^a for some exponent a.

    Let r be a tile in P and assume q does not divide its width. The area of r is width(r) * height(r) = q^s * p^t. Applying mondrian_prime_free_height_encoding to this product, the fact that q is prime and does not divide width(r) implies that all factors of q must belong to height(r), so height(r) = q^s * p^a for some a.

    lines 7–9

    uses mondrian_prime_free_height_encoding

      intro r hr hqr
      exact mondrian_prime_free_height_encoding p q s t (mondrian_rect_width r) (mondrian_rect_height r)
        hp hq (harea r hr) hqr
mondrian_partition_width_dvd_of_height_prime_chain
In a defect-free partition of an n × n square where d divides n and p is prime, if every tile whose width is not divisible by d has height equal to C * p^a for a fixed C > 0 and varying a, then every tile's width is divisible by d.
pow_pos
A positive integer raised to any natural power is strictly positive.
mondrian_prime_free_height_encoding
If x * y = q^s * p^t for primes p, q and q does not divide x, then y must be of the form q^s * p^a for some natural number a.

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_width_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 := by  apply mondrian_partition_width_dvd_of_height_prime_chain n q p (q ^ s) P hP hz hqn hp (pow_pos hq.pos s)  intro r hr hqr  exact mondrian_prime_free_height_encoding p q s t (mondrian_rect_width r) (mondrian_rect_height r)    hp hq (harea r hr) hqr
See it in the graphDiscuss this resultChallenge it