AFTD Auto-Formalizing Theoretical Domains

mondrian_three_prime_common_area_sides_divide

theoremverified

For primes p,q,r with p>r+1, if q divides the square side and every tile in a perfect admissible partition has area q^s*r*p^a, then q divides both dimensions of every tile.

Statement

theorem mondrian_three_prime_common_area_sides_divide (n p q r a s : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q)
    (hr : Nat.Prime r) (hpr : r + 1 < p)
    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n)
    (harea : ∀ u ∈ P, mondrian_rect_area u = q ^ s * r * p ^ a) :
    ∀ u ∈ P, q ∣ mondrian_rect_width u ∧ q ∣ mondrian_rect_height u
Source
Helper for the three-prime extension of OP-280, arXiv:2610.19193 Section 1. This combines the width-free height cycle with the two superincreasing chains.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
Used by 1

The proof, explained

The proof first establishes that in any defect-zero partition where every tile has area q^s * r * p^a, the prime q must divide the width of every tile: if q did not divide the width, the prime factorisation forces all factors of q into the height, placing the height into a two-chain form that triggers a width-divisibility reduction theorem. Applying this lemma directly to the original partition shows q divides all tile widths. Finally, reflecting the partition across the diagonal exchanges width and height while preserving partition validity and tile areas; applying the width result to this transposed partition shows that q divides every tile's height as well.

  1. p ≠ r automation

    Since r + 1 < p and r ≥ 0, linear integer arithmetic (`omega`) immediately shows that p and r are distinct.

    line 7

      have hpne : p ≠ r := by omega
  2. For any defect-zero partition Q of the n × n square whose tiles all have area q^s * r * p^a, the prime q divides the width of every tile in Q.

    To apply `mondrian_partition_width_dvd_of_height_two_chains` with constant C = q^s, consider any tile u in Q whose width is not divisible by q. Since the tile area is width(u) * height(u) = q^s * r * p^a, all s factors of q must divide the height. By `mondrian_prime_free_height_two_chain_encoding`, the only remaining prime factors of the height can be p and r, which forces height(u) to equal q^s * p^b or q^s * r * p^b for some b. The reduction theorem then concludes that q divides the width of every tile in Q.

    lines 8–16

    uses mondrian_partition_width_dvd_of_height_two_chains, pow_pos, mondrian_prime_free_height_two_chain_encoding

      have hwidth : ∀ (Q : List (ℕ × ℕ × ℕ × ℕ)), mondrian_is_partition n Q →
          mondrian_defect Q = 0 →
          (∀ u ∈ Q, mondrian_rect_area u = q ^ s * r * p ^ a) →
          ∀ u ∈ Q, q ∣ mondrian_rect_width u := by
        intro Q hQ hQz hQA
        apply mondrian_partition_width_dvd_of_height_two_chains n q p r (q ^ s) Q hQ hQz hqn (pow_pos hq.pos s) hr.two_le hpr
        intro u hu hfree
        exact mondrian_prime_free_height_two_chain_encoding p q r a s (mondrian_rect_width u) (mondrian_rect_height u)
          hp hq hr hpne (hQA u hu) hfree
  3. For every tile u in P, q divides the width of u.

    Specializing the general width divisibility lemma to the given partition P, which has defect 0 and whose tiles all have area q^s * r * p^a, yields that q divides width(u) for every u ∈ P.

    line 17

      have hw := hwidth P hP hz harea
  4. In the coordinate-transposed partition, q divides the width of every tile.

    Transposing each rectangle across the diagonal via `mondrian_rect_swap` produces another admissible partition P_swap of the square (`mondrian_partition_swap`). For any tile in P_swap, which is the transpose of some tile v ∈ P (`List.mem_map.mp`), its area is height(v) * width(v) = width(v) * height(v) = q^s * r * p^a by commutativity of multiplication (`Nat.mul_comm`). Since all tiles in P_swap have identical area, its defect is 0 (`mondrian_defect_zero_of_equal`). Applying the general width divisibility lemma to P_swap shows that q divides the width of every tile in P_swap.

    lines 18–26

    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 : ∀ u ∈ P.map mondrian_rect_swap,
          mondrian_rect_area u = q ^ s * r * p ^ a := by
        intro u hu
        obtain ⟨v, hv, rfl⟩ := List.mem_map.mp hu
        simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height,
          mondrian_rect_swap, Nat.mul_comm] using harea v hv
      have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * r * p ^ a) hswapA
      have hh := hwidth (P.map mondrian_rect_swap) hswapP hswapZ hswapA
  5. For every tile u in P, q divides both the width and the height of u.

    Let u ∈ P. Divisibility of width(u) by q was established in step 3. The transposed tile swap(u) belongs to P_swap (`List.mem_map.mpr`), so q divides width(swap(u)) by step 4. Since width(swap(u)) is by definition height(u), q also divides height(u).

    lines 27–30

    uses List.mem_map.mpr

      intro u hu
      refine ⟨hw u hu, ?_⟩
      have hx := hh (mondrian_rect_swap u) (List.mem_map.mpr ⟨u, hu, rfl⟩)
      simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx
List.mem_map.mp
If an element is in the image of a list under a function, it is the image of some element in the original list.
List.mem_map.mpr
The image of any element in a list under a function belongs to the mapped list.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_defect_zero_of_equal
If every rectangle in a partition has the same area, the defect of the partition is zero.
mondrian_partition_width_dvd_of_height_two_chains
In an admissible defect-zero partition of an n × n square where d divides n, if every tile whose width is not divisible by d has height of the form C * p^a or C * r * p^a, then d divides the width of every tile.
mondrian_partition_swap
Transposing each rectangle in an admissible partition of an n × n square yields another admissible partition of the square.
mondrian_prime_free_height_two_chain_encoding
If p, q, r are primes with p ≠ r, and x * y = q^s * r * p^a with q not dividing x, then y has the form q^s * p^b or q^s * r * p^b for some natural number b.
pow_pos
A strictly positive base raised to any natural power is strictly positive.

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_three_prime_common_area_sides_divide (n p q r a s : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hq : Nat.Prime q)    (hr : Nat.Prime r) (hpr : r + 1 < p)    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) (hqn : q ∣ n)    (harea : ∀ u ∈ P, mondrian_rect_area u = q ^ s * r * p ^ a) :    ∀ u ∈ P, q ∣ mondrian_rect_width u ∧ q ∣ mondrian_rect_height u := by  have hpne : p ≠ r := by omega  have hwidth : ∀ (Q : List (ℕ × ℕ × ℕ × ℕ)), mondrian_is_partition n Q →      mondrian_defect Q = 0 →      (∀ u ∈ Q, mondrian_rect_area u = q ^ s * r * p ^ a) →      ∀ u ∈ Q, q ∣ mondrian_rect_width u := by    intro Q hQ hQz hQA    apply mondrian_partition_width_dvd_of_height_two_chains n q p r (q ^ s) Q hQ hQz hqn (pow_pos hq.pos s) hr.two_le hpr    intro u hu hfree    exact mondrian_prime_free_height_two_chain_encoding p q r a s (mondrian_rect_width u) (mondrian_rect_height u)      hp hq hr hpne (hQA u hu) hfree  have hw := hwidth P hP hz harea  have hswapP := mondrian_partition_swap n P hP  have hswapA : ∀ u ∈ P.map mondrian_rect_swap,      mondrian_rect_area u = q ^ s * r * p ^ a := by    intro u hu    obtain ⟨v, hv, rfl⟩ := List.mem_map.mp hu    simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height,      mondrian_rect_swap, Nat.mul_comm] using harea v hv  have hswapZ := mondrian_defect_zero_of_equal _ (q ^ s * r * p ^ a) hswapA  have hh := hwidth (P.map mondrian_rect_swap) hswapP hswapZ hswapA  intro u hu  refine ⟨hw u hu, ?_⟩  have hx := hh (mondrian_rect_swap u) (List.mem_map.mpr ⟨u, hu, rfl⟩)  simpa only [mondrian_rect_width, mondrian_rect_height, mondrian_rect_swap] using hx
See it in the graphDiscuss this resultChallenge it