AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_prime_free_shape_count_bound

theoremverified

In an admissible equal-area partition, any selected collection of tiles each having a side indivisible by q has cardinality at most the number of available unordered shapes having such a side.

Statement

theorem mondrian_partition_prime_free_shape_count_bound (n A q : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (hP : mondrian_is_partition n P) (hA : ∀ r ∈ P, mondrian_rect_area r = A)
    (pred : (ℕ × ℕ × ℕ × ℕ) → Bool)
    (hpred : ∀ r ∈ P, pred r → ¬ q ∣ mondrian_rect_width r ∨ ¬ q ∣ mondrian_rect_height r) :
    P.countP pred ≤ ((mondrian_factor_shapes n A).filter
      (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2)).card
Source
Helper for OP-280 and mondrian_no_perfect_prime_mul_prime_pow. Related work: arXiv:2610.19193, Section 1 (the zero-defect question); arXiv:2007.09639, Theorem 4.1 (prime-power and small prime-product exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • mondrian_mem_factor_shapesA dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its…
  • 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_rect_areaThe area |R| = width × height of a rectangle.
  • 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).
  • 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_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 1

The proof, explained

The proof maps each rectangle in the partition to its canonical unordered shape $(\min(w, h), \max(w, h))$. Because all tiles in a Mondrian partition are pairwise non-congruent, rectangles with identical shapes must be identical, making the resulting list of shapes duplicate-free. Each selected rectangle yields a valid factor shape of area $A$ bounded by $n$ that inherits the property of having a dimension not divisible by $q$. Comparing cardinalities via the resulting subset inclusion bounds the number of selected tiles by the number of admissible shapes.

  1. Define a canonical shape map $f(r) = (\min(w(r), h(r)), \max(w(r), h(r)))$ sending each rectangle to its sorted dimensions.

    To represent rectangles up to rotation, we define $f$ to associate each rectangle $r$ with its unordered dimensions sorted in non-decreasing order.

    lines 7–8

      let f := fun r => (min (mondrian_rect_width r) (mondrian_rect_height r),
        max (mondrian_rect_width r) (mondrian_rect_height r))
  2. Two rectangles with the same canonical shape are congruent.

    Assuming $f(r) = f(s)$, applying the first and second projections via `congrArg Prod.fst` and `congrArg Prod.snd` gives $\min(w(r), h(r)) = \min(w(s), h(s))$ and $\max(w(r), h(r)) = \max(w(s), h(s))$. Unfolding the definition of congruence and using linear integer arithmetic (`omega`) to case-split on the relative order of side lengths proves that either the dimensions coincide directly or with width and height swapped.

    lines 9–15

    uses congrArg, Prod.fst, Prod.snd

      have hinj : ∀ r s, f r = f s → mondrian_rect_congruent r s := by
        intro r s he
        have h1 := congrArg Prod.fst he
        have h2 := congrArg Prod.snd he
        dsimp [f] at h1 h2
        unfold mondrian_rect_congruent
        omega
  3. The list of canonical shapes of the selected tiles contains no duplicate elements.

    By `List.nodup_iff_pairwise_ne` and `List.pairwise_map`, having no duplicates in the mapped list is equivalent to distinct rectangles having distinct shapes. Since a Mondrian partition requires distinct tiles to be pairwise non-congruent, and having equal shapes implies congruence, no two distinct tiles in the partition can map to the same shape.

    lines 16–20

    uses List.nodup_iff_pairwise_ne, List.pairwise_map

      have hn : ((P.filter pred).map f).Nodup := by
        rw [List.nodup_iff_pairwise_ne, List.pairwise_map]
        apply (hP.2.2.1.filter pred).imp
        intro a b hh he
        exact hh.2 (hinj _ _ he)
  4. The shapes of the selected rectangles form a subset of the factor shapes of area $A$ in an $n \times n$ square having at least one side not divisible by $q$.

    For any shape $d = f(r)$ coming from a tile $r \in P$ satisfying `pred r` (unpacked via `List.mem_toFinset.mp`, `List.mem_map.mp`, and `List.mem_filter.mp`), we establish membership in the filtered factor shapes via `Finset.mem_filter.mpr`. First, `mondrian_mem_factor_shapes` requires $f(r)$ to have area $A$, non-zero area, sorted components, and upper bound $n$. The area condition $\min(w, h) \cdot \max(w, h) = A$ follows from `min_mul_max` and the equal-area hypothesis `hA`. Since the partition guarantees positive dimensions (`mondrian_partition_bounds`, `Nat.mul_pos`), the area is non-zero (`Nat.ne_of_gt`), and the bounds on dimensions hold automatically. Second, from the hypothesis `hpred`, at least one of $w(r)$ or $h(r)$ is indivisible by $q$. A case split on $w(r) \le h(r)$ using `min_eq_left`, `max_eq_right`, `min_eq_right`, and `max_eq_left` transfers this indivisibility property directly to the sorted pair $f(r)$.

    lines 21–38

    uses List.mem_toFinset.mp, List.mem_map.mp, List.mem_filter.mp, Finset.mem_filter.mpr, mondrian_mem_factor_shapes, min_mul_max, mondrian_partition_bounds, Nat.ne_of_gt, Nat.mul_pos, min_eq_left, max_eq_right, min_eq_right, max_eq_left

      have hsub : ((P.filter pred).map f).toFinset ⊆ (mondrian_factor_shapes n A).filter
          (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2) := by
        intro d hd
        obtain ⟨r, hr, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hd)
        obtain ⟨hrP, hrpred⟩ := List.mem_filter.mp hr
        obtain ⟨hx, hy, hw, hh, hwn, hhn⟩ := mondrian_partition_bounds n P hP r hrP
        apply Finset.mem_filter.mpr
        constructor
        · apply (mondrian_mem_factor_shapes n A (f r)).mpr
          refine ⟨?_, ?_, by dsimp [f]; omega, by dsimp [f]; omega⟩
          · dsimp [f]; rw [min_mul_max]; exact hA r hrP
          · rw [← hA r hrP]; exact Nat.ne_of_gt (Nat.mul_pos hw hh)
        · have ht := hpred r hrP hrpred
          dsimp [f]
          by_cases hwh : mondrian_rect_width r ≤ mondrian_rect_height r
          · simpa [min_eq_left hwh, max_eq_right hwh] using ht
          · simpa [min_eq_right (by omega : mondrian_rect_height r ≤ mondrian_rect_width r),
              max_eq_left (by omega : mondrian_rect_height r ≤ mondrian_rect_width r)] using ht.symm
  5. The number of selected rectangles is at most the number of available factor shapes satisfying the condition.

    By monotonicity of cardinality (`Finset.card_le_card`), the set of shapes of selected tiles has size bounded by the target set. Because the shape list has no duplicates, its set cardinality equals the list length (`List.toFinset_card_of_nodup`). Since mapping $f$ preserves list length (`List.length_map`), this length equals the number of rectangles in $P$ satisfying the predicate (`List.countP_eq_length_filter`), establishing the bound.

    lines 39–40

    uses Finset.card_le_card, List.toFinset_card_of_nodup, List.length_map, List.countP_eq_length_filter

      have hc := Finset.card_le_card hsub
      simpa only [List.toFinset_card_of_nodup hn, List.length_map, ← List.countP_eq_length_filter] using hc
congrArg
If two inputs are equal, applying any function to both preserves equality.
Prod.fst
The first projection of an ordered pair: $(a, b).1 = a$.
Prod.snd
The second projection of an ordered pair: $(a, b).2 = b$.
List.nodup_iff_pairwise_ne
A list contains no duplicate elements if and only if all pairs of elements at distinct positions are unequal.
List.pairwise_map
Mapping a function over a list preserves a pairwise relation if and only if the original list satisfies the relation composed with the function.
List.mem_toFinset.mp
An element belongs to a finite set converted from a list only if it is an element of that list.
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 list.
List.mem_filter.mp
An element in a filtered list belongs to the original list and satisfies the filtering predicate.
mondrian_partition_bounds
Every tile in an admissible partition of an $n \times n$ square has strictly positive width and height bounded by $n$.
Finset.mem_filter.mpr
An element belongs to a filtered finite set if it belongs to the set and satisfies the filtering predicate.
mondrian_mem_factor_shapes
A pair $(d_1, d_2)$ is an available factor shape of area $A$ in an $n \times n$ grid if and only if $d_1 d_2 = A$, $A \neq 0$, $d_1 \le d_2$, and $d_2 \le n$.
min_mul_max
For any linearly ordered numbers, the product of their minimum and maximum equals their standard product: $\min(a, b) \cdot \max(a, b) = a \cdot b$.
Nat.ne_of_gt
A strictly greater natural number cannot equal the lesser one; in particular, a positive number is non-zero.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
min_eq_left
If $a \le b$, then $\min(a, b) = a$.
max_eq_right
If $a \le b$, then $\max(a, b) = b$.
min_eq_right
If $b \le a$, then $\min(a, b) = b$.
max_eq_left
If $b \le a$, then $\max(a, b) = a$.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the larger set.
List.toFinset_card_of_nodup
A duplicate-free list has the same number of elements as its conversion to a finite set.
List.length_map
Mapping a function over a list does not change the length of the list.
List.countP_eq_length_filter
The count of elements satisfying a predicate in a list equals the length of the list filtered by that predicate.

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_partition_prime_free_shape_count_bound (n A q : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (hP : mondrian_is_partition n P) (hA : ∀ r ∈ P, mondrian_rect_area r = A)    (pred : (ℕ × ℕ × ℕ × ℕ) → Bool)    (hpred : ∀ r ∈ P, pred r → ¬ q ∣ mondrian_rect_width r ∨ ¬ q ∣ mondrian_rect_height r) :    P.countP pred ≤ ((mondrian_factor_shapes n A).filter      (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2)).card := by  let f := fun r => (min (mondrian_rect_width r) (mondrian_rect_height r),    max (mondrian_rect_width r) (mondrian_rect_height r))  have hinj : ∀ r s, f r = f s → mondrian_rect_congruent r s := by    intro r s he    have h1 := congrArg Prod.fst he    have h2 := congrArg Prod.snd he    dsimp [f] at h1 h2    unfold mondrian_rect_congruent    omega  have hn : ((P.filter pred).map f).Nodup := by    rw [List.nodup_iff_pairwise_ne, List.pairwise_map]    apply (hP.2.2.1.filter pred).imp    intro a b hh he    exact hh.2 (hinj _ _ he)  have hsub : ((P.filter pred).map f).toFinset ⊆ (mondrian_factor_shapes n A).filter      (fun d => ¬ q ∣ d.1 ∨ ¬ q ∣ d.2) := by    intro d hd    obtain ⟨r, hr, rfl⟩ := List.mem_map.mp (List.mem_toFinset.mp hd)    obtain ⟨hrP, hrpred⟩ := List.mem_filter.mp hr    obtain ⟨hx, hy, hw, hh, hwn, hhn⟩ := mondrian_partition_bounds n P hP r hrP    apply Finset.mem_filter.mpr    constructor    · apply (mondrian_mem_factor_shapes n A (f r)).mpr      refine ⟨?_, ?_, by dsimp [f]; omega, by dsimp [f]; omega⟩      · dsimp [f]; rw [min_mul_max]; exact hA r hrP      · rw [← hA r hrP]; exact Nat.ne_of_gt (Nat.mul_pos hw hh)    · have ht := hpred r hrP hrpred      dsimp [f]      by_cases hwh : mondrian_rect_width r ≤ mondrian_rect_height r      · simpa [min_eq_left hwh, max_eq_right hwh] using ht      · simpa [min_eq_right (by omega : mondrian_rect_height r ≤ mondrian_rect_width r),          max_eq_left (by omega : mondrian_rect_height r ≤ mondrian_rect_width r)] using ht.symm  have hc := Finset.card_le_card hsub  simpa only [List.toFinset_card_of_nodup hn, List.length_map, ← List.countP_eq_length_filter] using hc
See it in the graphDiscuss this resultChallenge it