AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_prime_free_width_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 width is not divisible by p is divisible by p.

Statement

theorem mondrian_partition_prime_free_width_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_width 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
  • mondrian_is_partitionAn admissible Mondrian partition of the n×n square: at least two axis-parallel rectangles with positive integer side lengths, with…
  • mondrian_list_sum_count_modIf each integer list contribution is congruent modulo p to u when its predicate holds and to zero otherwise, their sum is congruent to u…
  • mondrian_partition_floor_momentFor every natural q, the sum of width times the difference of the quotient y coordinates across each tile in an admissible n-square…
  • mondrian_rect_areaThe area |R| = width × height of a rectangle.
  • mondrian_rect_floor_contributionWhen positive q divides a rectangle height, its width times the integer difference of quotient y coordinates is its area divided by q.
  • 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…
  • 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).
Used by 2

The proof, explained

To prove that the number N of rectangles whose width is not divisible by p is a multiple of p, we assign each rectangle r a floor-weighted functional f(r) = width(r) * (⌊y₂/q⌋ - ⌊y₁/q⌋), where q = p^(v_p(A)) and u = A/q. Locally, f(r) ≡ u (mod p) when p ∤ width(r) (because q must then divide height(r), making f(r) = u exactly) and f(r) ≡ 0 (mod p) when p ∣ width(r). Summing over the partition shows that the total sum of f(r) is congruent to N * u modulo p. Globally, the sum of f(r) over the entire n × n partition evaluates to n ⌊n/q⌋, which is divisible by p since p ∣ n. Equating these modulo p yields p ∣ N * u; because u is coprime to p by construction, p must divide N.

  1. Define the prime power q = p^(v_p(A)), the p-free part u = A/q, the floor functional f, and the predicate pred, and note that q > 0.

    We extract the full p-adic factor of the common area A by letting q = p^(v_p(A)), so that u = A/q is coprime to p. For each rectangle r = [x₁, x₂) × [y₁, y₂), the functional f(r) = (x₂ - x₁)(⌊y₂/q⌋ - ⌊y₁/q⌋) tracks its weighted floor contribution, and pred(r) tests whether p does not divide the width of r. Since p is prime, p > 0, so q > 0 by pow_pos.

    lines 8–13

    uses pow_pos

      let q := p ^ A.factorization p
      let u := A / q
      let f := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) *
        (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))
      let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬p ∣ mondrian_rect_width r)
      have hq : 0 < q := pow_pos hp.pos _
  2. For every rectangle r in P, f(r) is congruent modulo p to u if p ∤ width(r) and to 0 if p ∣ width(r).

    We split into cases based on whether p divides width(r): 1. If p ∣ width(r), then pred(r) is false (giving target 0). Since p divides the width, dvd_mul_of_dvd_left shows p divides f(r), so f(r) - 0 is divisible by p. 2. If p ∤ width(r), then pred(r) is true (giving target u). Since p does not divide the width, q = p^(v_p(A)) is coprime to width(r). Because q divides area(r) = A by Nat.ordProj_dvd, coprimality forces q to divide height(r). Using y₁ ≤ y₂ from Nat.le_of_lt, mondrian_rect_floor_contribution simplifies f(r) to exactly A / q = u. Hence f(r) - u = 0, which is divisible by p.

    lines 14–34

    uses dvd_mul_of_dvd_left, Nat.ordProj_dvd, mondrian_rect_floor_contribution, Nat.le_of_lt

      have hterm : ∀ r ∈ P, (p : ℤ) ∣ f r - if pred r then (u : ℤ) else 0 := by
        intro r hr
        by_cases hw : p ∣ mondrian_rect_width r
        · have hwZ : (p : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hw
          simpa only [f, pred, hw, not_true_eq_false, decide_false, Bool.false_eq_true,
            if_false, sub_zero] using dvd_mul_of_dvd_left hwZ
              ((((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)))
        · have hcop : q.Coprime (mondrian_rect_width r) :=
            (hp.coprime_iff_not_dvd.mpr hw).pow_left _
          have hqh : q ∣ mondrian_rect_height r := by
            apply hcop.dvd_mul_left.mp
            change q ∣ mondrian_rect_area r
            rw [hA r hr]
            exact Nat.ordProj_dvd A p
          have he := mondrian_rect_floor_contribution r
            (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh
          rw [hA r hr] at he
          simp only [f, pred, hw, not_false_eq_true, decide_true, if_true]
          change (p : ℤ) ∣ _ - (A / q : ℕ)
          rw [he]
          simp
  3. The sum of f(r) over all rectangles in P is congruent modulo p to N * u, where N is the count of rectangles with width not divisible by p.

    Applying mondrian_list_sum_count_mod to the list P aggregates the per-rectangle congruences, establishing that p divides ∑ f(r) - N * u.

    line 35

    uses mondrian_list_sum_count_mod

      have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred hterm
  4. The total sum ∑ f(r) over all rectangles in P is divisible by p.

    By the global moment identity mondrian_partition_floor_moment, the sum of f(r) over the partition of the n × n square equals n ⌊n / q⌋. Since p ∣ n by hypothesis, p divides this product by dvd_mul_of_dvd_left.

    lines 36–40

    uses mondrian_partition_floor_moment, dvd_mul_of_dvd_left

      have hmoment := mondrian_partition_floor_moment n q P hP
      have hnZ : (p : ℤ) ∣ (n : ℤ) := by exact_mod_cast hpn
      have hsumdiv : (p : ℤ) ∣ (P.map f).sum := by
        rw [show (P.map f).sum = (n : ℤ) * (n / q : ℕ) from hmoment]
        exact dvd_mul_of_dvd_left hnZ _
  5. The product N * u is divisible by p in the integers.

    Since p divides the total sum and also divides the difference ∑ f(r) - N * u, dvd_sub shows that p divides their difference. Ring arithmetic simplifies ∑ f(r) - (∑ f(r) - N * u) to N * u.

    lines 41–45

    uses dvd_sub

      have hprod : (p : ℤ) ∣ (P.countP pred : ℤ) * (u : ℤ) := by
        have hh := dvd_sub hsumdiv hsum
        have heq : (P.map f).sum - ((P.map f).sum - (P.countP pred : ℤ) * (u : ℤ)) =
            (P.countP pred : ℤ) * (u : ℤ) := by ring
        rwa [heq] at hh
  6. The number of rectangles in P whose width is not divisible by p is divisible by p.

    Casting the divisibility p ∣ N * u to natural numbers, the primality of p implies that p ∣ N or p ∣ u. But u = A / p^(v_p(A)) has all factors of p removed, so Nat.not_dvd_ordCompl (with A ≠ 0 from Nat.ne_of_gt) guarantees p does not divide u. Hence p must divide N.

    lines 46–49

    uses Nat.not_dvd_ordCompl, Nat.ne_of_gt

      have hprodN : p ∣ P.countP pred * u := by exact_mod_cast hprod
      rcases hp.dvd_mul.mp hprodN with hc | hu
      · exact hc
      · exact (Nat.not_dvd_ordCompl hp (Nat.ne_of_gt hApos) hu).elim
pow_pos
A strictly positive element raised to any natural power is strictly positive.
dvd_mul_of_dvd_left
If a divides b, then a divides b * c for any c.
Nat.ordProj_dvd
The prime power p^(v_p(n)) divides n.
mondrian_rect_floor_contribution
If q > 0 divides the height of rectangle r, then width(r) * (⌊y₂/q⌋ - ⌊y₁/q⌋) = area(r) / q.
Nat.le_of_lt
Strict inequality between natural numbers implies non-strict inequality.
mondrian_list_sum_count_mod
If each element r of a list satisfies f(r) ≡ u (mod p) when pred(r) holds and f(r) ≡ 0 (mod p) otherwise, then the sum of f(r) over the list is congruent modulo p to the count of satisfying elements times u.
mondrian_partition_floor_moment
For an admissible partition P of an n × n square, the sum of width(r) * (⌊y₂/q⌋ - ⌊y₁/q⌋) over all rectangles r in P equals n ⌊n / q⌋.
dvd_sub
If a divides b and a divides c, then a divides b - c.
Nat.not_dvd_ordCompl
For a prime p and non-zero n, p does not divide the p-free part n / p^(v_p(n)).
Nat.ne_of_gt
If b < a, then a ≠ b.

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_width_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_width r)) := by  let q := p ^ A.factorization p  let u := A / q  let f := fun r : ℕ × ℕ × ℕ × ℕ => (mondrian_rect_width r : ℤ) *    (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))  let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬p ∣ mondrian_rect_width r)  have hq : 0 < q := pow_pos hp.pos _  have hterm : ∀ r ∈ P, (p : ℤ) ∣ f r - if pred r then (u : ℤ) else 0 := by    intro r hr    by_cases hw : p ∣ mondrian_rect_width r    · have hwZ : (p : ℤ) ∣ (mondrian_rect_width r : ℤ) := by exact_mod_cast hw      simpa only [f, pred, hw, not_true_eq_false, decide_false, Bool.false_eq_true,        if_false, sub_zero] using dvd_mul_of_dvd_left hwZ          ((((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)))    · have hcop : q.Coprime (mondrian_rect_width r) :=        (hp.coprime_iff_not_dvd.mpr hw).pow_left _      have hqh : q ∣ mondrian_rect_height r := by        apply hcop.dvd_mul_left.mp        change q ∣ mondrian_rect_area r        rw [hA r hr]        exact Nat.ordProj_dvd A p      have he := mondrian_rect_floor_contribution r        (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh      rw [hA r hr] at he      simp only [f, pred, hw, not_false_eq_true, decide_true, if_true]      change (p : ℤ) ∣ _ - (A / q : ℕ)      rw [he]      simp  have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred hterm  have hmoment := mondrian_partition_floor_moment n q P hP  have hnZ : (p : ℤ) ∣ (n : ℤ) := by exact_mod_cast hpn  have hsumdiv : (p : ℤ) ∣ (P.map f).sum := by    rw [show (P.map f).sum = (n : ℤ) * (n / q : ℕ) from hmoment]    exact dvd_mul_of_dvd_left hnZ _  have hprod : (p : ℤ) ∣ (P.countP pred : ℤ) * (u : ℤ) := by    have hh := dvd_sub hsumdiv hsum    have heq : (P.map f).sum - ((P.map f).sum - (P.countP pred : ℤ) * (u : ℤ)) =        (P.countP pred : ℤ) * (u : ℤ) := by ring    rwa [heq] at hh  have hprodN : p ∣ P.countP pred * u := by exact_mod_cast hprod  rcases hp.dvd_mul.mp hprodN with hc | hu  · exact hc  · exact (Nat.not_dvd_ordCompl hp (Nat.ne_of_gt hApos) hu).elim
See it in the graphDiscuss this resultChallenge it