AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_prime_free_height_count

theoremverified

For an admissible n-square partition into rectangles of one common positive integer area, and every prime p dividing n, the number of tiles whose height is not divisible by p is divisible by p.

Statement

theorem mondrian_partition_prime_free_height_count (n p A : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n)
    (hApos : 0 < A) (hP : mondrian_is_partition n P)
    (hA : ∀ r ∈ P, mondrian_rect_area r = A) :
    p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_height r))
Source
Helper for OP-280: modular shape inventories for the zero-defect question in arXiv:2610.19193, Section 1. The weighted row and prime-free count argument is developed here; it supplements the available-shape counting in arXiv:2311.02385, Section 3.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
Used by 1

The proof, explained

The theorem is proved by reduction to the horizontal case (`mondrian_partition_prime_free_width_count`) via diagonal symmetry. Exchanging the x- and y-coordinates of each rectangle transforms the partition into another admissible partition of the n-square while preserving each rectangle's area. Applying the width-divisibility theorem to this swapped partition shows that p divides the number of tiles with non-divisible swapped width. Because the width of a swapped rectangle is definitionally the height of the original rectangle, the claim follows immediately.

  1. Reflecting each tile across the main diagonal yields another valid partition of the n-square.

    Applying `mondrian_partition_swap` to the partition P establishes that exchanging the horizontal and vertical coordinates of each rectangle produces an admissible partition of the n × n square.

    line 8

    uses mondrian_partition_swap

      have hswap := mondrian_partition_swap n P hP
  2. Every tile in the swapped partition retains the same area A.

    For any rectangle r in the swapped list, `List.mem_map.mp` yields an original tile s ∈ P such that r is the coordinate swap of s. The area of r is its width times its height, which corresponds to the height times the width of s. By commutativity of multiplication (`Nat.mul_comm`), this product equals the original area of s, which is A by assumption.

    lines 9–13

    uses List.mem_map.mp, Nat.mul_comm

      have hAswap : ∀ r ∈ P.map mondrian_rect_swap, mondrian_rect_area r = A := by
        intro r hr
        obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr
        simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height,
          mondrian_rect_swap, Nat.mul_comm] using hA s hs
  3. The prime p divides the number of tiles in P whose swapped width is not divisible by p.

    Applying `mondrian_partition_prime_free_width_count` to the swapped partition shows that p divides the count of tiles in `P.map mondrian_rect_swap` whose width is not a multiple of p. Rewriting with `List.countP_map` pulls the swap operation into the predicate, rephrasing this as a count over the original list P.

    lines 14–16

    uses mondrian_partition_prime_free_width_count, List.countP_map

      have hc := mondrian_partition_prime_free_width_count n p A (P.map mondrian_rect_swap)
        hp hpn hApos hswap hAswap
      rw [List.countP_map] at hc
  4. The condition that a swapped tile has width not divisible by p is equivalent to the condition that the original tile has height not divisible by p.

    Using function extensionality (`funext`) and evaluating the function composition (`Function.comp_apply`), we compare the two boolean predicates. By `decide_eq_decide.mpr`, it suffices to show that the underlying divisibility statements are equivalent. Because the width of the swapped rectangle is definitionally equal to the height of the original rectangle, the equivalence holds by reflexivity (`rfl`).

    lines 17–22

    uses Function.comp_apply, decide_eq_decide.mpr

      have heq : ((fun r => decide (¬p ∣ mondrian_rect_width r)) ∘ mondrian_rect_swap) =
          (fun r => decide (¬p ∣ mondrian_rect_height r)) := by
        funext r
        simp only [Function.comp_apply]
        apply decide_eq_decide.mpr
        rfl
  5. The prime p divides the number of tiles in P whose height is not divisible by p.

    Rewriting the count in the divisibility hypothesis using the equality of predicates established in the previous step replaces the swapped-width condition with the original tile's height condition, concluding the proof.

    lines 23–24

      rw [heq] at hc
      exact hc
mondrian_partition_swap
If P is an admissible partition of the n-square, then swapping the coordinates of each rectangle in P also yields an admissible partition of the n-square.
List.mem_map.mp
An element y belongs to the image List.map f l if and only if there exists an element x ∈ l such that f x = y.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
mondrian_partition_prime_free_width_count
In an admissible partition of an n-square into rectangles of constant positive area A, for any prime p dividing n, the number of rectangles whose width is not divisible by p is divisible by p.
List.countP_map
Counting elements satisfying predicate p in a mapped list List.map f l is equal to counting elements in l satisfying the composite predicate p ∘ f.
Function.comp_apply
The application of a composite function (f ∘ g) x equals f (g x).
decide_eq_decide.mpr
If two propositions are logically equivalent, their boolean decision values 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

open scoped BigOperatorstheorem mondrian_partition_prime_free_height_count (n p A : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n)    (hApos : 0 < A) (hP : mondrian_is_partition n P)    (hA : ∀ r ∈ P, mondrian_rect_area r = A) :    p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_height r)) := by  have hswap := mondrian_partition_swap n P hP  have hAswap : ∀ r ∈ P.map mondrian_rect_swap, mondrian_rect_area r = A := by    intro r hr    obtain ⟨s, hs, rfl⟩ := List.mem_map.mp hr    simpa only [mondrian_rect_area, mondrian_rect_width, mondrian_rect_height,      mondrian_rect_swap, Nat.mul_comm] using hA s hs  have hc := mondrian_partition_prime_free_width_count n p A (P.map mondrian_rect_swap)    hp hpn hApos hswap hAswap  rw [List.countP_map] at hc  have heq : ((fun r => decide (¬p ∣ mondrian_rect_width r)) ∘ mondrian_rect_swap) =      (fun r => decide (¬p ∣ mondrian_rect_height r)) := by    funext r    simp only [Function.comp_apply]    apply decide_eq_decide.mpr    rfl  rw [heq] at hc  exact hc
See it in the graphDiscuss this resultChallenge it