AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_prime_free_side_counts

theoremverified

In any perfect admissible partition of an integer n-square, every prime p dividing n divides both the number of tiles with width not divisible by p and the number with height not divisible by p.

Statement

theorem mondrian_perfect_prime_free_side_counts (n p : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n)
    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) :
    p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_width r)) ∧
      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 9
Used by 2

The proof, explained

The proof proceeds by considering whether the list of tiles P is empty. When P is empty, the counts are zero and the statement holds vacuously. When P is non-empty, the zero-defect condition guarantees that all tiles share the same strictly positive area as the initial tile r. The result then follows directly by applying previously proven theorems that establish prime divisibility for prime-free width and height counts in equiareal partitions.

  1. The claim holds trivially when the partition list P is empty. automation

    When P is empty, the count of tiles satisfying any condition evaluates to 0. Since every prime p divides 0, both divisibility conditions hold vacuously, and simplification closes the goal.

    lines 8–9

      cases P with
      | nil => simp
  2. In a non-empty partition r :: P, the tile r belongs to the partition and has strictly positive area.

    The tile r is trivially an element of r :: P. Applying mondrian_partition_bounds shows that r has strictly positive width and strictly positive height. By Nat.mul_pos, their product—the area of r—is strictly positive.

    lines 10–13

    uses mondrian_partition_bounds, Nat.mul_pos

      | cons r P =>
        have hr : r ∈ r :: P := by simp
        have hb := mondrian_partition_bounds n (r :: P) hP r hr
        have hApos := Nat.mul_pos hb.2.2.1 hb.2.2.2.1
  3. Every tile in r :: P has the same area as r.

    Because the partition has defect zero (hz), mondrian_defect_zero_equal implies that any two tiles in the partition have identical area. In particular, every tile s ∈ r :: P has area equal to mondrian_rect_area r.

    lines 14–15

    uses mondrian_defect_zero_equal

        have hA : ∀ s ∈ r :: P, mondrian_rect_area s = mondrian_rect_area r :=
          fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr
  4. p divides both the number of tiles with width not divisible by p and the number of tiles with height not divisible by p.

    With the area A = mondrian_rect_area r established to be strictly positive and constant across all tiles, the pair of goals is closed by invoking mondrian_partition_prime_free_width_count for the width count and mondrian_partition_prime_free_height_count for the height count.

    lines 16–19

    uses mondrian_partition_prime_free_width_count, mondrian_partition_prime_free_height_count

        exact ⟨mondrian_partition_prime_free_width_count n p (mondrian_rect_area r)
          (r :: P) hp hpn hApos hP hA,
          mondrian_partition_prime_free_height_count n p (mondrian_rect_area r)
          (r :: P) hp hpn hApos hP hA⟩
mondrian_partition_bounds
In an admissible partition of an n-square, every tile lies within the square and has strictly positive width and height bounded by n.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
mondrian_defect_zero_equal
If a partition has defect zero, any two tiles in the partition have equal area.
mondrian_partition_prime_free_width_count
In an admissible partition of an n-square where all tiles share the same positive area A, every prime p dividing n divides the number of tiles whose width is not divisible by p.
mondrian_partition_prime_free_height_count
In an admissible partition of an n-square where all tiles share the same positive area A, every prime p dividing n divides the number of tiles whose height is not divisible by p.

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_perfect_prime_free_side_counts (n p : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n)    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0) :    p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_width r)) ∧      p ∣ P.countP (fun r => decide (¬p ∣ mondrian_rect_height r)) := by  cases P with  | nil => simp  | cons r P =>    have hr : r ∈ r :: P := by simp    have hb := mondrian_partition_bounds n (r :: P) hP r hr    have hApos := Nat.mul_pos hb.2.2.1 hb.2.2.2.1    have hA : ∀ s ∈ r :: P, mondrian_rect_area s = mondrian_rect_area r :=      fun s hs => mondrian_defect_zero_equal (r :: P) hz s r hs hr    exact ⟨mondrian_partition_prime_free_width_count n p (mondrian_rect_area r)      (r :: P) hp hpn hApos hP hA,      mondrian_partition_prime_free_height_count n p (mondrian_rect_area r)      (r :: P) hp hpn hApos hP hA⟩
See it in the graphDiscuss this resultChallenge it