AFTD Auto-Formalizing Theoretical Domains

mondrian_large_prime_descent

theoremverified

If c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the c-square.

Statement

theorem mondrian_large_prime_descent (c p e : ℕ) (hc : 0 < c)
    (hp : Nat.Prime p) (hpc : c < p) :
    (∃ P, mondrian_is_partition (c * p ^ e) P ∧ mondrian_defect P = 0) →
      ∃ Q, mondrian_is_partition c Q ∧ mondrian_defect Q = 0
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
Built on 18
  • mondrian_defectThe defect def(P) = max_{R∈P} |R| − min_{R∈P} |R| of a family of rectangles.
  • mondrian_defect_zero_equalAny two rectangles in a list of defect zero have equal area.
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • mondrian_large_prime_count_not_dvdIf enough distinct shapes of a common area fit in a c times p to the e square to account for its area, a prime p greater than c cannot…
  • mondrian_partition_boundsEvery rectangle of an admissible n-square partition has positive side lengths, upper coordinates at most n, and side lengths at most n.
  • mondrian_perfect_area_productIn a perfect n-square partition, the number of rectangles times the area of any member is n squared.
  • mondrian_perfect_partition_divDividing coordinates by a preserves perfect admissible partitions when a is positive and divides every tile side.
  • mondrian_prime_power_dvd_sidesIf p is prime and exceeds c, positive x and y at most c times p to the e whose product is divisible by p to the 2e must each be divisible…
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
  • mondrian_rect_divDivide all four rectangle coordinates by a using natural-number division.
  • mondrian_rect_heightThe height y₁ − y₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_rect_widthThe width x₁ − x₀ of the rectangle (x₀, x₁, y₀, y₁).
  • mondrian_shape_boundA partition of the n-square whose rectangles all have area A has at most as many members as available unordered dimension pairs.
  • mondrian_rect_congruentTwo rectangles are congruent when they have the same side lengths, possibly after a rotation (so 2×3 and 3×2 are congruent).
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • mondrian_rect_cellsThe unit cells [i,i+1]×[j,j+1] of the integer rectangle [x₀,x₁]×[y₀,y₁], recorded as r = (x₀, x₁, y₀, y₁); a cell is named by its…
Used by 2

The proof, explained

Assuming there exists a defect-0 partition P of a (c · p^e) × (c · p^e) square into non-congruent rectangles, all rectangles share the same area A and satisfy |P| · A = (c · p^e)². Since c < p and the non-congruence condition limits the number of available factorizations of A, the prime p cannot divide the rectangle count |P|. Consequently, p^(2e) is coprime to |P| and must divide the rectangle area A = width · height. Because each side length is at most c · p^e and c < p, p^e must divide both the width and height of every rectangle, allowing the entire partition to be scaled down by p^e into a defect-0 partition of the c × c square.

  1. Let P be a partition of the (c · p^e) × (c · p^e) square with defect 0.

    We assume the hypothesis: there exists a partition P of the square of side c · p^e (hP) with defect 0 (hz), meaning all rectangles in P have the same area.

    line 5

      rintro ⟨P, hP, hz⟩
  2. The partition P cannot be empty.

    By definition, any valid Mondrian partition contains at least two rectangles (|P| ≥ 2). If P were empty, its length would be 0, which contradicts 2 ≤ 0.

    lines 6–7

      cases P with
      | nil => have := hP.1; simp at this
  3. For any rectangle r ∈ P, its area is positive and satisfies |P| · area(r) = (c · p^e)².

    Since P is non-empty, we can pick a rectangle r ∈ P. Partition bounds (mondrian_partition_bounds) ensure that both dimensions of r are strictly positive and bounded by c · p^e, so the area of r is strictly positive (Nat.mul_pos). Since the defect is 0, every rectangle in P has area equal to area(r), so the sum of all rectangle areas equals |P| · area(r) = (c · p^e)² (mondrian_perfect_area_product).

    lines 8–12

    uses mondrian_partition_bounds, Nat.mul_pos, mondrian_perfect_area_product

      | cons r P =>
        have hr : r ∈ r :: P := by simp
        have hb := mondrian_partition_bounds (c * p ^ e) (r :: P) hP r hr
        have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1
        have heq := mondrian_perfect_area_product (c * p ^ e) (r :: P) hP hz r hr
  4. The prime p does not divide the number of rectangles |P|.

    Because all rectangles in P have equal area (mondrian_defect_zero_equal) and are pairwise non-congruent, the count |P| cannot exceed the number of distinct factorizations of area(r) that fit in the square (mondrian_shape_bound). Together with c < p and the total area equation, this bound implies that p does not divide |P| (mondrian_large_prime_count_not_dvd).

    lines 13–16

    uses mondrian_defect_zero_equal, mondrian_shape_bound, mondrian_large_prime_count_not_dvd

        have hcard := mondrian_shape_bound (c * p ^ e) (mondrian_rect_area r) (r :: P) hP
          (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr)
        have hknot := mondrian_large_prime_count_not_dvd c p e (r :: P).length
          (mondrian_rect_area r) hc hp hpc (by have := hP.1; omega) hA heq hcard
  5. p^(2e) is coprime to |P|.

    Since p is prime and does not divide |P|, p and |P| are coprime. Raising p to the power 2e preserves coprimality (pow_left).

    lines 17–18

    uses pow_left

        have hcop : (p ^ (2 * e)).Coprime (r :: P).length :=
          (hp.coprime_iff_not_dvd.mpr hknot).pow_left (2 * e)
  6. p^(2e) divides the area of r.

    Rewriting (c · p^e)² as p^(2e) · c² via exponent arithmetic (Nat.mul_comm, pow_mul), p^(2e) divides the total area |P| · area(r) (dvd_mul_right). Since p^(2e) is coprime to |P|, by Euclid's lemma p^(2e) must divide area(r).

    lines 19–27

    uses Nat.mul_comm, pow_mul, dvd_mul_right

        have hpowprod : p ^ (2 * e) ∣ (r :: P).length * mondrian_rect_area r := by
          rw [heq]
          have hnn : (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2 := by
            rw [Nat.mul_comm 2 e, pow_mul]
            ring
          rw [hnn]
          exact dvd_mul_right _ _
        have hpow := hcop.dvd_mul_left.mp hpowprod
        have hpc' : c < p := by nlinarith
  7. For every rectangle s ∈ P, p^e divides both the width and height of s.

    Every rectangle s ∈ P has area equal to area(r) (mondrian_defect_zero_equal), so p^(2e) divides width(s) · height(s). Furthermore, the dimensions of s are positive and at most c · p^e (mondrian_partition_bounds). Since c < p, the divisibility lemma mondrian_prime_power_dvd_sides forces p^e to divide both width(s) and height(s).

    lines 28–37

    uses mondrian_partition_bounds, mondrian_defect_zero_equal, mondrian_prime_power_dvd_sides

        have hd : ∀ s ∈ r :: P, p ^ e ∣ mondrian_rect_width s ∧
            p ^ e ∣ mondrian_rect_height s := by
          intro s hs
          have hbs := mondrian_partition_bounds (c * p ^ e) (r :: P) hP s hs
          have hspow : p ^ (2 * e) ∣ mondrian_rect_area s := by
            rw [mondrian_defect_zero_equal (r :: P) hz s r hs hr]
            exact hpow
          exact mondrian_prime_power_dvd_sides c p e (mondrian_rect_width s)
            (mondrian_rect_height s) hp hpc' hbs.2.2.1 hbs.2.2.2.1
            hbs.2.2.2.2.1 hbs.2.2.2.2.2 hspow
  8. Dividing every rectangle in P by p^e yields a defect-0 partition of the c × c square.

    We construct the candidate partition by dividing the coordinates of every rectangle in P by p^e. Since p^e > 0 (pow_pos) and p^e divides both dimensions of every rectangle, scaling down preserves the partition structure and zero defect, producing a valid defect-0 partition of the c × c square (mondrian_perfect_partition_div, with Nat.mul_comm adjusting the side length product p^e · c).

    lines 38–40

    uses pow_pos, mondrian_perfect_partition_div, Nat.mul_comm

        refine ⟨(r :: P).map (mondrian_rect_div (p ^ e)), ?_⟩
        exact mondrian_perfect_partition_div (p ^ e) c (pow_pos hp.pos e) (r :: P)
          (by simpa only [Nat.mul_comm] using hP) hz hd
mondrian_partition_bounds
Every rectangle in a partition of an n × n square has strictly positive width and height bounded above by n, and its coordinates lie within [0, n].
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
mondrian_perfect_area_product
In a defect-0 partition of an n × n square, the number of rectangles times the area of any rectangle equals the total area n².
mondrian_shape_bound
In a partition where every rectangle has area A, the number of rectangles is at most the number of non-congruent rectangular shapes of area A that fit in the n × n square.
mondrian_defect_zero_equal
In a partition with defect 0, all rectangles have identical area.
mondrian_large_prime_count_not_dvd
For prime p > c > 0, if k non-congruent rectangles of area A tile a (c · p^e) × (c · p^e) square, then p does not divide the rectangle count k.
pow_left
If a is coprime to b, then any power a^n is also coprime to b.
Nat.mul_comm
Multiplication of natural numbers is commutative: n · m = m · n.
pow_mul
Power of a power rule: a^(m · n) = (a^m)^n.
dvd_mul_right
Any number a divides the product a · b.
mondrian_prime_power_dvd_sides
If p > c is prime and positive integers x, y ≤ c · p^e satisfy p^(2e) ∣ x · y, then p^e divides x and p^e divides y.
pow_pos
Any power of a strictly positive number is strictly positive.
mondrian_perfect_partition_div
If a > 0 divides both dimensions of every rectangle in a defect-0 partition of an (a · c) × (a · c) square, dividing each rectangle by a yields a defect-0 partition of a c × c square.

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_large_prime_descent (c p e : ℕ) (hc : 0 < c)    (hp : Nat.Prime p) (hpc : c < p) :    (∃ P, mondrian_is_partition (c * p ^ e) P ∧ mondrian_defect P = 0) →      ∃ Q, mondrian_is_partition c Q ∧ mondrian_defect Q = 0 := by  rintro ⟨P, hP, hz⟩  cases P with  | nil => have := hP.1; simp at this  | cons r P =>    have hr : r ∈ r :: P := by simp    have hb := mondrian_partition_bounds (c * p ^ e) (r :: P) hP r hr    have hA := Nat.mul_pos hb.2.2.1 hb.2.2.2.1    have heq := mondrian_perfect_area_product (c * p ^ e) (r :: P) hP hz r hr    have hcard := mondrian_shape_bound (c * p ^ e) (mondrian_rect_area r) (r :: P) hP      (fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr)    have hknot := mondrian_large_prime_count_not_dvd c p e (r :: P).length      (mondrian_rect_area r) hc hp hpc (by have := hP.1; omega) hA heq hcard    have hcop : (p ^ (2 * e)).Coprime (r :: P).length :=      (hp.coprime_iff_not_dvd.mpr hknot).pow_left (2 * e)    have hpowprod : p ^ (2 * e) ∣ (r :: P).length * mondrian_rect_area r := by      rw [heq]      have hnn : (c * p ^ e) ^ 2 = p ^ (2 * e) * c ^ 2 := by        rw [Nat.mul_comm 2 e, pow_mul]        ring      rw [hnn]      exact dvd_mul_right _ _    have hpow := hcop.dvd_mul_left.mp hpowprod    have hpc' : c < p := by nlinarith    have hd : ∀ s ∈ r :: P, p ^ e ∣ mondrian_rect_width s ∧        p ^ e ∣ mondrian_rect_height s := by      intro s hs      have hbs := mondrian_partition_bounds (c * p ^ e) (r :: P) hP s hs      have hspow : p ^ (2 * e) ∣ mondrian_rect_area s := by        rw [mondrian_defect_zero_equal (r :: P) hz s r hs hr]        exact hpow      exact mondrian_prime_power_dvd_sides c p e (mondrian_rect_width s)        (mondrian_rect_height s) hp hpc' hbs.2.2.1 hbs.2.2.2.1        hbs.2.2.2.2.1 hbs.2.2.2.2.2 hspow    refine ⟨(r :: P).map (mondrian_rect_div (p ^ e)), ?_⟩    exact mondrian_perfect_partition_div (p ^ e) c (pow_pos hp.pos e) (r :: P)      (by simpa only [Nat.mul_comm] using hP) hz hd
See it in the graphDiscuss this resultChallenge it