AFTD Auto-Formalizing Theoretical Domains

mondrian_perfect_min_width_layer_count

theoremverified

For a perfect admissible n-square partition and prime p dividing n, suppose b is the minimum p-adic exponent of tile widths. Then b is at most v_p(n), and the number of tiles in that minimum layer is congruent modulo p to the tile count if b=v_p(n), and to zero if b<v_p(n).

Statement

theorem mondrian_perfect_min_width_layer_count (n p b : ℕ)
    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n)
    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0)
    (hmin : ∀ r ∈ P, p ^ b ∣ mondrian_rect_width r)
    (hex : ∃ r ∈ P, ¬ p ^ (b + 1) ∣ mondrian_rect_width r) :
    b ≤ n.factorization p ∧
      Nat.ModEq p (P.countP (fun r => decide (¬p ^ (b + 1) ∣ mondrian_rect_width r)))
        (if b = n.factorization p then P.length else 0)
Source
Next step of the modular inventory route for OP-280, arXiv:2610.19193, Section 1. The minimum-layer strengthening is derived here on paper and tested in experiments 5295 and 5296; it is not yet Lean-proved.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 16

The proof, explained

The proof scales the tile widths of the partition by the minimal power $d = p^b$, normalizing the partition so that the tiles in the minimal width layer are precisely those with scaled width coprime to $p$. The common divisor $d$ must divide the square side $n$, giving $b \le v_p(n)$. A normalized modular relation equates the count of these minimal tiles (scaled by the $p$-free tile area $u$) to $N \cdot (n/q) \pmod p$, where $N = n/p^b$. When $b = v_p(n)$, $N$ is coprime to $p$ and the total area product implies $N \cdot (n/q) = |P| \cdot u$, forcing the count to be congruent to $|P| \pmod p$; when $b < v_p(n)$, $p$ divides $N$, driving the right-hand side to $0 \pmod p$.

  1. The partition $P$ contains at least one rectangle $z$.

    Because $P$ is a valid partition of the $n$-square, its definition guarantees $|P| \ge 2$. Thus $P$ is non-empty, so there exists some rectangle $z \in P$.

    lines 9–12

      obtain ⟨z, hzP⟩ : ∃ z, z ∈ P := by
        cases P with
        | nil => have := hP.1; simp at this
        | cons z P => exact ⟨z, by simp⟩
  2. Define the scaling divisor $d = p^b$, the reference tile area $A$, the scaled area $C = A/d$, the scaled square size $N = n/d$, the maximal prime power $q = p^{v_p(C)}$ dividing $C$, the $p$-free part $u = C/q$, the tile count $k = |P|$, and the count $\text{cnt}$ of tiles whose scaled width is coprime to $p$.

    These definitions set up the normalized parameters for applying modular reduction: dividing tile widths by $d$ standardizes the minimum $p$-adic layer to valuation zero, where divisibility by $p$ can be counted directly.

    lines 13–20

      let d := p ^ b
      let A := mondrian_rect_area z
      let C := A / d
      let N := n / d
      let q := p ^ C.factorization p
      let u := C / q
      let k := P.length
      let cnt := P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d))
  3. The quantities $d, n, A, C$ are strictly positive, $d \mid n$, the bound $b \le v_p(n)$ holds, and the exact division identities $d \cdot C = A$ and $d \cdot N = n$ hold.

    Since $p$ is prime, $d = p^b > 0$ by `pow_pos`. From the partition bounds on $z \in P$ (`mondrian_partition_bounds`), $n > 0$ and $A > 0$. Since $d$ divides the width of $z$, it divides $A$ (`dvd_mul_of_dvd_left`), making $C = A/d > 0$ by `Nat.div_pos`. Because $d$ divides the width of every tile in the partition, $d \mid n$ by `mondrian_common_width_divides_side`. Since $n \ne 0$, $p^b \mid n$ is equivalent to $b \le v_p(n)$. The product identities $d \cdot C = A$ and $d \cdot N = n$ follow from exact division (`Nat.mul_div_cancel'`).

    lines 21–30

    uses pow_pos, mondrian_partition_bounds, Nat.mul_pos, dvd_mul_of_dvd_left, Nat.div_pos, Nat.le_of_dvd, mondrian_common_width_divides_side, Nat.mul_div_cancel'

      have hd : 0 < d := pow_pos hp.pos b
      have hzb := mondrian_partition_bounds n P hP z hzP
      have hn : 0 < n := hzb.2.2.1.trans_le hzb.2.2.2.2.1
      have hA : 0 < A := Nat.mul_pos hzb.2.2.1 hzb.2.2.2.1
      have hAd : d ∣ A := dvd_mul_of_dvd_left (hmin z hzP) _
      have hC : 0 < C := Nat.div_pos (Nat.le_of_dvd hA hAd) hd
      have hdn : d ∣ n := mondrian_common_width_divides_side n d P hP hmin
      have hbd : b ≤ n.factorization p := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mp hdn
      have hdC : d * C = A := Nat.mul_div_cancel' hAd
      have hdN : d * N = n := Nat.mul_div_cancel' hdn
  4. For every tile $r \in P$, the scaled width and unscaled height give area $(\text{width}(r)/d) \cdot \text{height}(r) = C$.

    Multiplying the scaled area expression by $d$ recovers the unscaled area $\text{area}(r)$ by `Nat.mul_div_cancel'`. Since the partition has defect 0, all tiles have identical area, so $\text{area}(r) = A = d \cdot C$ by `mondrian_defect_zero_equal`. Cancelling the common factor $d > 0$ using `Nat.eq_of_mul_eq_mul_left` proves that every tile has scaled area $C$.

    lines 31–39

    uses Nat.eq_of_mul_eq_mul_left, Nat.mul_assoc, Nat.mul_div_cancel', mondrian_defect_zero_equal

      have harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C := by
        intro r hr
        apply Nat.eq_of_mul_eq_mul_left hd
        calc
          d * ((mondrian_rect_width r / d) * mondrian_rect_height r) = mondrian_rect_area r := by
            rw [← Nat.mul_assoc, Nat.mul_div_cancel' (hmin r hr)]
            rfl
          _ = A := mondrian_defect_zero_equal P hz r z hr hzP
          _ = d * C := hdC.symm
  5. The congruence $\text{cnt} \cdot u \equiv N \cdot (n/q) \pmod p$ holds, and $u$ is coprime to $p$.

    Applying `mondrian_partition_normalized_prime_free_width_mod` to the normalized partition yields the modular relation $\text{cnt} \cdot u \equiv N \cdot (n/q) \pmod p$. Since $u = C / p^{v_p(C)}$ is the $p$-free part of $C \ne 0$, $p \nmid u$ by `Nat.not_dvd_ordCompl`, so $u$ is coprime to $p$.

    lines 40–43

    uses mondrian_partition_normalized_prime_free_width_mod, Nat.not_dvd_ordCompl

      have hmod := mondrian_partition_normalized_prime_free_width_mod n p d C P hp hd hP hmin harea
      change Nat.ModEq p (cnt * u) (N * (n / q)) at hmod
      have hunit : p.Coprime u := hp.coprime_iff_not_dvd.mpr
        (Nat.not_dvd_ordCompl hp (by omega : C ≠ 0))
  6. The count $\text{cnt}$ equals the number of tiles in $P$ whose width is not divisible by $p^{b+1}$.

    For any tile $r$, its width is a multiple of $d = p^b$. Hence $p \mid (\text{width}(r)/d)$ is equivalent via `Nat.mul_dvd_mul_iff_left` to $d \cdot p \mid \text{width}(r)$, which is $p^{b+1} \mid \text{width}(r)$ by `pow_succ`. Negating this equivalence and summing over $P$ with `List.countP_congr` identifies $\text{cnt}$ with the number of tiles having $p$-adic width exponent exactly $b$.

    lines 44–53

    uses List.countP_congr, decide_eq_true_eq, not_congr, Nat.mul_div_cancel', pow_succ, Nat.mul_dvd_mul_iff_left

      have hcount : cnt = P.countP (fun r => decide (¬ p ^ (b + 1) ∣ mondrian_rect_width r)) := by
        apply List.countP_congr
        intro r hr
        simp only [decide_eq_true_eq]
        apply not_congr
        have hw : d * (mondrian_rect_width r / d) = mondrian_rect_width r := Nat.mul_div_cancel' (hmin r hr)
        have he : p ^ (b + 1) = d * p := by rw [pow_succ]
        rw [he]
        conv_rhs => rw [← hw]
        exact (Nat.mul_dvd_mul_iff_left hd).symm
  7. Discharge the inequality $b \le v_p(n)$ and rewrite the remaining goal in terms of $\text{cnt}$.

    The first conjunct of the theorem, $b \le v_p(n)$, was already established as `hbd`. Replacing the filter in the second conjunct with `cnt` reduces the problem to evaluating $\text{cnt} \pmod p$.

    lines 54–55

      refine ⟨hbd, ?_⟩
      rw [← hcount]
  8. If $b = v_p(n)$, then $\text{cnt} \equiv |P| \pmod p$.

    When $b = v_p(n)$, $N = n / p^{v_p(n)}$ is not divisible by $p$ by `Nat.not_dvd_ordCompl`, so $q = p^{v_p(C)}$ is coprime to $N$. The total area identity $|P| \cdot A = n^2$ (`mondrian_perfect_area_product`) scales down to $k \cdot C = N \cdot n$. Since $q \mid C$, $q$ divides $N \cdot n$, and coprimality with $N$ implies $q \mid n$. Dividing $k \cdot C = N \cdot n$ by $q$ yields $k \cdot u = N \cdot (n/q)$. Substituting this into the normalized congruence gives $\text{cnt} \cdot u \equiv k \cdot u \pmod p$. Because $u$ is coprime to $p$, cancelling $u$ with `Nat.ModEq.cancel_right_of_coprime` concludes $\text{cnt} \equiv k \pmod p$.

    lines 56–80

    uses if_pos, Nat.not_dvd_ordCompl, Nat.eq_of_mul_eq_mul_left, mondrian_perfect_area_product, dvd_mul_of_dvd_right, Nat.ordProj_dvd, Nat.mul_div_cancel', pow_pos, congrArg, Nat.ModEq.cancel_right_of_coprime

      by_cases hb : b = n.factorization p
      · rw [if_pos hb]
        have hNnot : ¬ p ∣ N := by
          simpa only [N, d, hb] using Nat.not_dvd_ordCompl hp (by omega : n ≠ 0)
        have hnorm : k * C = N * n := by
          apply Nat.eq_of_mul_eq_mul_left hd
          calc
            d * (k * C) = k * A := by rw [← hdC]; ring
            _ = n ^ 2 := mondrian_perfect_area_product n P hP hz z hzP
            _ = d * (N * n) := by rw [← hdN]; ring
        have hcop : q.Coprime N := (hp.coprime_iff_not_dvd.mpr hNnot).pow_left _
        have hqn : q ∣ n := hcop.dvd_mul_left.mp (by
          rw [← hnorm]
          exact dvd_mul_of_dvd_right (Nat.ordProj_dvd C p) k)
        have hqC : q * u = C := Nat.mul_div_cancel' (Nat.ordProj_dvd C p)
        have hqN : q * (n / q) = n := Nat.mul_div_cancel' hqn
        have hprod : k * u = N * (n / q) := by
          apply Nat.eq_of_mul_eq_mul_left (pow_pos hp.pos (C.factorization p))
          calc
            q * (k * u) = k * C := by rw [← hqC]; ring
            _ = N * n := hnorm
            _ = N * (q * (n / q)) := congrArg (fun v => N * v) hqN.symm
            _ = q * (N * (n / q)) := by ring
        rw [← hprod] at hmod
        exact Nat.ModEq.cancel_right_of_coprime hunit hmod
  9. If $b < v_p(n)$, then $\text{cnt} \equiv 0 \pmod p$.

    When $b < v_p(n)$, we have $b + 1 \le v_p(n)$, so $p^{b+1} \mid n$. Since $p^{b+1} = d \cdot p$ and $n = d \cdot N$, cancelling $d$ via `Nat.mul_dvd_mul_iff_left` gives $p \mid N$. It follows that $N \cdot (n/q)$ is divisible by $p$, so $N \cdot (n/q) \equiv 0 \cdot u \pmod p$ by `Nat.zero_mul`. The normalized congruence becomes $\text{cnt} \cdot u \equiv 0 \cdot u \pmod p$, and cancelling the coprime factor $u$ via `Nat.ModEq.cancel_right_of_coprime` gives $\text{cnt} \equiv 0 \pmod p$.

    lines 81–91

    uses if_neg, pow_succ, Nat.mul_dvd_mul_iff_left, Nat.zero_mul, dvd_mul_of_dvd_left, Nat.ModEq.cancel_right_of_coprime

      · rw [if_neg hb]
        have hba : b + 1 ≤ n.factorization p := by omega
        have hpow : p ^ (b + 1) ∣ n := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mpr hba
        have hN : p ∣ N := by
          have hh : d * p ∣ d * N := by
            rw [hdN]
            simpa only [d, pow_succ] using hpow
          exact (Nat.mul_dvd_mul_iff_left hd).mp hh
        have hzero : Nat.ModEq p (N * (n / q)) (0 * u) := by
          simpa only [Nat.zero_mul] using (dvd_mul_of_dvd_left hN (n / q)).modEq_zero_nat
        exact Nat.ModEq.cancel_right_of_coprime hunit (hmod.trans hzero)
congrArg
A function applied to equal inputs produces equal outputs: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
decide_eq_true_eq
The boolean expression `decide P` evaluates to `true` if and only if proposition $P$ holds.
dvd_mul_of_dvd_left
If $a$ divides $b$, then $a$ divides $b \cdot c$.
dvd_mul_of_dvd_right
If $a$ divides $b$, then $a$ divides $c \cdot b$.
if_neg
If condition $c$ is false, then `if c then t else e` equals $e$.
if_pos
If condition $c$ is true, then `if c then t else e` equals $t$.
List.countP_congr
If two predicates agree on all elements of a list, counting elements satisfying each predicate gives the same number.
mondrian_common_width_divides_side
If a divisor $d$ divides the width of every rectangle in a partition of an $n \times n$ square, then $d$ divides $n$.
mondrian_defect_zero_equal
In a partition with zero defect, all rectangles have the same area.
mondrian_partition_bounds
Every rectangle in an $n$-square partition has strictly positive dimensions bounded above by $n$.
mondrian_partition_normalized_prime_free_width_mod
For an $n$-square partition where all tile widths are multiples of $d$ and scaled tile area is $C$, the count of tiles whose scaled width is not divisible by $p$ multiplied by the $p$-free part of $C$ is congruent modulo $p$ to $(n/d) \cdot (n/p^{v_p(C)})$.
mondrian_perfect_area_product
In a defect-zero partition of an $n \times n$ square, the number of rectangles times the area of any single rectangle equals $n^2$.
Nat.div_pos
If $0 < b \le a$, then the integer quotient $a / b$ is strictly positive.
Nat.eq_of_mul_eq_mul_left
Multiplying both sides of an equality by a strictly positive natural number preserves equality.
Nat.le_of_dvd
If $m \mid n$ and $n > 0$, then $m \le n$.
Nat.ModEq.cancel_right_of_coprime
In modular arithmetic, a factor coprime to the modulus can be cancelled from both sides: $a \cdot c \equiv b \cdot c \pmod m$ implies $a \equiv b \pmod m$ when $\gcd(m, c) = 1$.
Nat.mul_assoc
Multiplication of natural numbers is associative: $(n \cdot m) \cdot k = n \cdot (m \cdot k)$.
Nat.mul_div_cancel'
If $n$ divides $m$, then $n \cdot (m / n) = m$.
Nat.mul_dvd_mul_iff_left
For $a > 0$, $a \cdot b \mid a \cdot c$ if and only if $b \mid c$.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Nat.not_dvd_ordCompl
For a prime $p$ and non-zero natural number $n$, $p$ does not divide the prime-free component $n / p^{v_p(n)}$.
Nat.ordProj_dvd
The prime power factor $p^{v_p(n)}$ divides $n$.
Nat.zero_mul
Zero multiplied by any natural number is zero.
not_congr
An equivalence of propositions $P \leftrightarrow Q$ implies an equivalence of their negations $\neg P \leftrightarrow \neg Q$.
pow_pos
A strictly positive natural number raised to any power is strictly positive.
pow_succ
For any base $a$ and natural exponent $n$, $a^{n+1} = a^n \cdot a$.

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_perfect_min_width_layer_count (n p b : ℕ)    (P : List (ℕ × ℕ × ℕ × ℕ)) (hp : Nat.Prime p) (hpn : p ∣ n)    (hP : mondrian_is_partition n P) (hz : mondrian_defect P = 0)    (hmin : ∀ r ∈ P, p ^ b ∣ mondrian_rect_width r)    (hex : ∃ r ∈ P, ¬ p ^ (b + 1) ∣ mondrian_rect_width r) :    b ≤ n.factorization p ∧      Nat.ModEq p (P.countP (fun r => decide (¬p ^ (b + 1) ∣ mondrian_rect_width r)))        (if b = n.factorization p then P.length else 0) := by  obtain ⟨z, hzP⟩ : ∃ z, z ∈ P := by    cases P with    | nil => have := hP.1; simp at this    | cons z P => exact ⟨z, by simp⟩  let d := p ^ b  let A := mondrian_rect_area z  let C := A / d  let N := n / d  let q := p ^ C.factorization p  let u := C / q  let k := P.length  let cnt := P.countP (fun r => decide (¬ p ∣ mondrian_rect_width r / d))  have hd : 0 < d := pow_pos hp.pos b  have hzb := mondrian_partition_bounds n P hP z hzP  have hn : 0 < n := hzb.2.2.1.trans_le hzb.2.2.2.2.1  have hA : 0 < A := Nat.mul_pos hzb.2.2.1 hzb.2.2.2.1  have hAd : d ∣ A := dvd_mul_of_dvd_left (hmin z hzP) _  have hC : 0 < C := Nat.div_pos (Nat.le_of_dvd hA hAd) hd  have hdn : d ∣ n := mondrian_common_width_divides_side n d P hP hmin  have hbd : b ≤ n.factorization p := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mp hdn  have hdC : d * C = A := Nat.mul_div_cancel' hAd  have hdN : d * N = n := Nat.mul_div_cancel' hdn  have harea : ∀ r ∈ P, (mondrian_rect_width r / d) * mondrian_rect_height r = C := by    intro r hr    apply Nat.eq_of_mul_eq_mul_left hd    calc      d * ((mondrian_rect_width r / d) * mondrian_rect_height r) = mondrian_rect_area r := by        rw [← Nat.mul_assoc, Nat.mul_div_cancel' (hmin r hr)]        rfl      _ = A := mondrian_defect_zero_equal P hz r z hr hzP      _ = d * C := hdC.symm  have hmod := mondrian_partition_normalized_prime_free_width_mod n p d C P hp hd hP hmin harea  change Nat.ModEq p (cnt * u) (N * (n / q)) at hmod  have hunit : p.Coprime u := hp.coprime_iff_not_dvd.mpr    (Nat.not_dvd_ordCompl hp (by omega : C ≠ 0))  have hcount : cnt = P.countP (fun r => decide (¬ p ^ (b + 1) ∣ mondrian_rect_width r)) := by    apply List.countP_congr    intro r hr    simp only [decide_eq_true_eq]    apply not_congr    have hw : d * (mondrian_rect_width r / d) = mondrian_rect_width r := Nat.mul_div_cancel' (hmin r hr)    have he : p ^ (b + 1) = d * p := by rw [pow_succ]    rw [he]    conv_rhs => rw [← hw]    exact (Nat.mul_dvd_mul_iff_left hd).symm  refine ⟨hbd, ?_⟩  rw [← hcount]  by_cases hb : b = n.factorization p  · rw [if_pos hb]    have hNnot : ¬ p ∣ N := by      simpa only [N, d, hb] using Nat.not_dvd_ordCompl hp (by omega : n ≠ 0)    have hnorm : k * C = N * n := by      apply Nat.eq_of_mul_eq_mul_left hd      calc        d * (k * C) = k * A := by rw [← hdC]; ring        _ = n ^ 2 := mondrian_perfect_area_product n P hP hz z hzP        _ = d * (N * n) := by rw [← hdN]; ring    have hcop : q.Coprime N := (hp.coprime_iff_not_dvd.mpr hNnot).pow_left _    have hqn : q ∣ n := hcop.dvd_mul_left.mp (by      rw [← hnorm]      exact dvd_mul_of_dvd_right (Nat.ordProj_dvd C p) k)    have hqC : q * u = C := Nat.mul_div_cancel' (Nat.ordProj_dvd C p)    have hqN : q * (n / q) = n := Nat.mul_div_cancel' hqn    have hprod : k * u = N * (n / q) := by      apply Nat.eq_of_mul_eq_mul_left (pow_pos hp.pos (C.factorization p))      calc        q * (k * u) = k * C := by rw [← hqC]; ring        _ = N * n := hnorm        _ = N * (q * (n / q)) := congrArg (fun v => N * v) hqN.symm        _ = q * (N * (n / q)) := by ring    rw [← hprod] at hmod    exact Nat.ModEq.cancel_right_of_coprime hunit hmod  · rw [if_neg hb]    have hba : b + 1 ≤ n.factorization p := by omega    have hpow : p ^ (b + 1) ∣ n := (hp.pow_dvd_iff_le_factorization (by omega : n ≠ 0)).mpr hba    have hN : p ∣ N := by      have hh : d * p ∣ d * N := by        rw [hdN]        simpa only [d, pow_succ] using hpow      exact (Nat.mul_dvd_mul_iff_left hd).mp hh    have hzero : Nat.ModEq p (N * (n / q)) (0 * u) := by      simpa only [Nat.zero_mul] using (dvd_mul_of_dvd_left hN (n / q)).modEq_zero_nat    exact Nat.ModEq.cancel_right_of_coprime hunit (hmod.trans hzero)
See it in the graphDiscuss this resultChallenge it