AFTD Auto-Formalizing Theoretical Domains

mondrian_partition_normalized_prime_free_width_mod

theoremverified

In an admissible n-square partition with every width divisible by positive d and with constant normalized area C, the number of normalized widths indivisible by prime p, multiplied by the p-free part of C, is congruent modulo p to (n/d) times floor(n/p^v_p(C)).

Statement

theorem mondrian_partition_normalized_prime_free_width_mod (n p d C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))
    (hp : Nat.Prime p) (hd : 0 < d) (hP : mondrian_is_partition n P)
    (hwidth : ∀ r ∈ P, d ∣ mondrian_rect_width r)
    (harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C) :
    Nat.ModEq p
      ((P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d))) *
        (C / p ^ C.factorization p))
      ((n / d) * (n / p ^ C.factorization p))
Source
Helper for OP-280 and mondrian_perfect_min_width_layer_count, from the normalized floor moment for arXiv:2610.19193, Section 1.
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_moment_div_widthIf positive d divides every tile width in an admissible n-square partition, dividing all widths in the quotient-row moment by d gives…
  • 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_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_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_areaThe area |R| = width × height of a rectangle.
Used by 1

The proof, explained

We define an auxiliary functional for each rectangle r in the partition: f(r) = (w_r / d) * (floor(y_{2,r} / q) - floor(y_{1,r} / q)), where q = p^{v_p(C)} is the prime-power factor of the normalized area C. For rectangles whose normalized width w_r / d is divisible by p, f(r) is divisible by p; for those not divisible by p, coprimality forces q to divide the height, so f(r) simplifies exactly to C / q. Summing f(r) across the entire partition yields both the count times C / q modulo p and, via a global partition moment identity, the total (n/d) * floor(n/q), establishing the desired congruence.

  1. Define the prime-power factor q = p^{v_p(C)}, the p-free part u = C/q, the per-rectangle weighted floor functional f, and the predicate selecting rectangles whose normalized width is not divisible by p, and note that q > 0.

    We set q = p^{v_p(C)} and u = C / q. For each rectangle r with vertical span [y_1, y_2] and normalized width w_r / d, we define f(r) = (w_r / d) * (floor(y_2 / q) - floor(y_1 / q)). The predicate pred(r) tests whether p does not divide w_r / d. Since p is prime, p > 0, so q = p^{v_p(C)} > 0 by `pow_pos`.

    lines 9–14

    uses pow_pos

      let q := p ^ C.factorization p
      let u := C / q
      let f := fun r : ℕ × ℕ × ℕ × ℕ => ((mondrian_rect_width r / d : ℕ) : ℤ) *
        (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))
      let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬ p ∣ mondrian_rect_width r / d)
      have hq : 0 < q := pow_pos hp.pos _
  2. For any rectangle r ∈ P whose normalized width is divisible by p, the term f(r) is divisible by p, so f(r) ≡ 0 (mod p).

    We begin establishing that p ∣ f(r) - if pred(r) then u else 0 for every rectangle r ∈ P. Splitting on whether p ∣ (w_r / d): if it does, pred(r) is false, so the target reduces to p ∣ f(r). Since f(r) has w_r / d as an integer factor, `dvd_mul_of_dvd_left` shows that p divides f(r).

    lines 15–21

    uses dvd_mul_of_dvd_left

      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 / d
        · have hwZ : (p : ℤ) ∣ ((mondrian_rect_width r / d : ℕ) : ℤ) := 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 : ℕ) : ℤ)))
  3. For any rectangle r ∈ P whose normalized width is not divisible by p, f(r) = u, completing the proof that f(r) ≡ if pred(r) then u else 0 (mod p) for all r ∈ P.

    When p does not divide w_r / d, q = p^{v_p(C)} is coprime to w_r / d. Since (w_r / d) * h_r = C and q ∣ C by `Nat.ordProj_dvd`, coprimality implies q ∣ h_r. Applying `mondrian_rect_floor_contribution` to an auxiliary rectangle of width w_r / d and height h_r (using y_1 ≤ y_2 from `hP` via `Nat.le_of_lt`), the weighted floor difference evaluates exactly to ((w_r / d) * h_r) / q = C / q = u. Since pred(r) is true, f(r) - u = u - u = 0, which is divisible by p.

    lines 22–38

    uses Nat.ordProj_dvd, mondrian_rect_floor_contribution, Nat.le_of_lt

        · have hcop : q.Coprime (mondrian_rect_width r / d) :=
            (hp.coprime_iff_not_dvd.mpr hw).pow_left _
          have hqh : q ∣ mondrian_rect_height r := by
            apply hcop.dvd_mul_left.mp
            rw [harea r hr]
            exact Nat.ordProj_dvd C p
          let v : ℕ × ℕ × ℕ × ℕ := (0, mondrian_rect_width r / d, r.2.2.1, r.2.2.2)
          have he := mondrian_rect_floor_contribution v
            (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh
          change ((mondrian_rect_width r / d : ℕ) : ℤ) *
            (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) =
              (((mondrian_rect_width r / d) * mondrian_rect_height r / q : ℕ) : ℤ) at he
          rw [harea r hr] at he
          simp only [f, pred, hw, not_false_eq_true, decide_true, if_true]
          change (p : ℤ) ∣ _ - (C / q : ℕ)
          rw [he]
          simp
  4. Summing over the partition, ∑_{r ∈ P} f(r) is congruent modulo p to u times the count of rectangles with normalized width indivisible by p.

    Applying `mondrian_list_sum_count_mod` to the list P and the term-by-term divisibility condition establishes that p divides ∑_{r ∈ P} f(r) - (count of rectangles satisfying pred) * u.

    line 39

    uses mondrian_list_sum_count_mod

      have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred hterm
  5. The sum ∑_{r ∈ P} f(r) equals (n/d) * floor(n/q), so p ∣ (n/d) * floor(n/q) - (count) * u.

    By `mondrian_partition_floor_moment_div_width`, the sum of (w_r / d) * (floor(y_2 / q) - floor(y_1 / q)) over the partition of an n × n square evaluates globally to (n/d) * floor(n/q). Rewriting this identity into the previous divisibility relation replaces the sum with (n/d) * floor(n/q).

    lines 40–42

    uses mondrian_partition_floor_moment_div_width

      have hmoment := mondrian_partition_floor_moment_div_width n q d P hd hP hwidth
      change (P.map f).sum = ((n / d : ℕ) : ℤ) * ((n / q : ℕ) : ℤ) at hmoment
      rw [hmoment] at hsum
  6. The count of rectangles with normalized width indivisible by p, multiplied by C / p^{v_p(C)}, is congruent modulo p to (n/d) * floor(n / p^{v_p(C)}).

    Using `Nat.modEq_iff_dvd.mpr`, the integer divisibility relation p ∣ (n/d) * floor(n/q) - (count) * u is converted into the congruence (count) * u ≡ (n/d) * floor(n/q) (mod p) over natural numbers.

    line 43

    uses Nat.modEq_iff_dvd.mpr

      exact Nat.modEq_iff_dvd.mpr (by exact_mod_cast hsum)
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 factor p^(v_p(n)) divides n for any natural numbers n and p.
mondrian_rect_floor_contribution
When the height of a rectangle is a multiple of q > 0, its width times the floor difference of its vertical endpoints divided by q equals its area divided by q.
Nat.le_of_lt
A strict inequality a < b between natural numbers implies a ≤ b.
mondrian_list_sum_count_mod
If every element of a list satisfies f(r) ≡ u [MOD p] when a boolean predicate holds and f(r) ≡ 0 [MOD p] otherwise, then the sum of f(r) over the list is congruent modulo p to u times the count of elements satisfying the predicate.
mondrian_partition_floor_moment_div_width
In an admissible partition of an n-square whose rectangle widths are all divisible by d, the sum of (w_r / d) * (floor(y_{2,r}/q) - floor(y_{1,r}/q)) over all rectangles equals (n/d) * floor(n/q).
Nat.modEq_iff_dvd.mpr
An integer divisibility relation n ∣ b - a implies the modular congruence a ≡ b [MOD n] on natural numbers.

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_normalized_prime_free_width_mod (n p d C : ℕ) (P : List (ℕ × ℕ × ℕ × ℕ))    (hp : Nat.Prime p) (hd : 0 < d) (hP : mondrian_is_partition n P)    (hwidth : ∀ r ∈ P, d ∣ mondrian_rect_width r)    (harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C) :    Nat.ModEq p      ((P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d))) *        (C / p ^ C.factorization p))      ((n / d) * (n / p ^ C.factorization p)) := by  let q := p ^ C.factorization p  let u := C / q  let f := fun r : ℕ × ℕ × ℕ × ℕ => ((mondrian_rect_width r / d : ℕ) : ℤ) *    (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ))  let pred := fun r : ℕ × ℕ × ℕ × ℕ => decide (¬ p ∣ mondrian_rect_width r / d)  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 / d    · have hwZ : (p : ℤ) ∣ ((mondrian_rect_width r / d : ℕ) : ℤ) := 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 / d) :=        (hp.coprime_iff_not_dvd.mpr hw).pow_left _      have hqh : q ∣ mondrian_rect_height r := by        apply hcop.dvd_mul_left.mp        rw [harea r hr]        exact Nat.ordProj_dvd C p      let v : ℕ × ℕ × ℕ × ℕ := (0, mondrian_rect_width r / d, r.2.2.1, r.2.2.2)      have he := mondrian_rect_floor_contribution v        (Nat.le_of_lt (hP.2.1 r hr).2) q hq hqh      change ((mondrian_rect_width r / d : ℕ) : ℤ) *        (((r.2.2.2 / q : ℕ) : ℤ) - ((r.2.2.1 / q : ℕ) : ℤ)) =          (((mondrian_rect_width r / d) * mondrian_rect_height r / q : ℕ) : ℤ) at he      rw [harea r hr] at he      simp only [f, pred, hw, not_false_eq_true, decide_true, if_true]      change (p : ℤ) ∣ _ - (C / q : ℕ)      rw [he]      simp  have hsum := mondrian_list_sum_count_mod P (p : ℤ) (u : ℤ) f pred hterm  have hmoment := mondrian_partition_floor_moment_div_width n q d P hd hP hwidth  change (P.map f).sum = ((n / d : ℕ) : ℤ) * ((n / q : ℕ) : ℤ) at hmoment  rw [hmoment] at hsum  exact Nat.modEq_iff_dvd.mpr (by exact_mod_cast hsum)
See it in the graphDiscuss this resultChallenge it