mondrian_prime_shape_bound
If k times A is the area of a c times p to the e square and p exceeds c, at most c * (v_p(k) + 1) unordered shapes of area A fit in the square.
Statement
theorem mondrian_prime_shape_bound (c p e k A : ℕ) (hc : 0 < c)
(hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A)
(heq : k * A = (c * p ^ e) ^ 2) :
(mondrian_factor_shapes (c * p ^ e) A).card ≤ (k.factorization p + 1) * c- Source
- Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- mondrian_divisors_card_le_two_mul_of_le_sqAn integer D at most c squared has at most 2c positive divisors.
- mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- mondrian_ordered_prime_shape_boundThe number of ordered shapes of area A fitting in a c times p to the e square is at most the p-adic exponent of k plus one, times the…
- mondrian_ordered_shape_halfTwice the number of available unordered dimension pairs is at most one plus the number of ordered dimension pairs fitting in the square.
- mondrian_prime_cofactor_leWhen k times A is the area of a c times p to the e square with p greater than c, the p-free part of A is at most c squared.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- mondrian_large_prime_count_not_dvdIf enough distinct shapes of a common area fit in a c times p to the e square to account for its area, a prime p greater than c cannot…
The proof, explained
To bound the number of unordered rectangle shapes of area A that fit in a (c * p^e) × (c * p^e) square, the proof first bounds unordered shapes by half of the ordered factor pairs. The number of ordered factor pairs is then controlled by (v_p(k) + 1) times the number of divisors of the p-free cofactor A / p^(v_p(A)). Since c < p, this cofactor is at most c^2 and thus has at most 2c divisors, from which integer arithmetic yields the upper bound (v_p(k) + 1) * c.
Twice the number of valid unordered shapes is at most one more than the number of valid ordered factor pairs.
By `mondrian_ordered_shape_half`, each unordered shape {d₁, d₂} of area A corresponds to two ordered pairs (d₁, d₂) and (d₂, d₁) unless d₁ = d₂ (a square, which occurs at most once), so 2 * |S| ≤ |S_ord| + 1.
uses
mondrian_ordered_shape_halfhave h1 := mondrian_ordered_shape_half (c * p ^ e) AThe number of ordered factor pairs fitting in the square is at most (v_p(k) + 1) times the number of divisors of the cofactor A / p^(v_p(A)).
By `mondrian_ordered_prime_shape_bound`, the prime power factorization structure limits the valid ordered factor pairs to at most (v_p(k) + 1) * d(A / p^(v_p(A))), where d(·) counts divisors.
uses
mondrian_ordered_prime_shape_boundhave h2 := mondrian_ordered_prime_shape_bound c p e k A hc hp hpc hk hA heqThe cofactor A / p^(v_p(A)) is at most c^2, and consequently has at most 2c divisors.
By `mondrian_prime_cofactor_le`, removing the full p-part from A leaves a cofactor bounded by c^2 because c < p. Then `mondrian_divisors_card_le_two_mul_of_le_sq` bounds the number of divisors of any integer up to c^2 by 2c.
uses
mondrian_prime_cofactor_le,mondrian_divisors_card_le_two_mul_of_le_sqhave h3 := mondrian_prime_cofactor_le c p e k A hc hp hpc heq have h4 := mondrian_divisors_card_le_two_mul_of_le_sq (A / p ^ (A.factorization p)) c h3
The number of unordered shapes of area A fitting in the square is at most (v_p(k) + 1) * c.
Multiplying the divisor bound by v_p(k) + 1 via `Nat.mul_le_mul_left` gives |S_ord| ≤ 2c * (v_p(k) + 1). Combining this with 2 * |S| ≤ |S_ord| + 1 gives 2 * |S| ≤ 2c * (v_p(k) + 1) + 1; nonlinear integer arithmetic (`nlinarith`) closes the goal by dividing by 2.
uses
Nat.mul_le_mul_lefthave h5 := Nat.mul_le_mul_left (k.factorization p + 1) h4 nlinarith
mondrian_ordered_shape_half- Twice the number of unordered factor shapes of area A fitting in an n × n square is at most one more than the number of valid ordered factor pairs.
mondrian_ordered_prime_shape_bound- If k * A = (c * p^e)^2 with p prime and c < p, the number of ordered factor pairs of area A fitting in the (c * p^e) × (c * p^e) square is at most (v_p(k) + 1) times the number of divisors of the p-free cofactor A / p^(v_p(A)).
mondrian_prime_cofactor_le- If k * A = (c * p^e)^2 with p prime and c < p, the p-free cofactor A / p^(v_p(A)) is at most c^2.
mondrian_divisors_card_le_two_mul_of_le_sq- Any natural number D bounded by c^2 has at most 2c divisors.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers n ≤ m on the left by k preserves the inequality: k * n ≤ k * m.
- The final step relies on `nlinarith` to deduce $x \le M$ from $2x \le 2M + 1$ over the 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem mondrian_prime_shape_bound (c p e k A : ℕ) (hc : 0 < c) (hp : Nat.Prime p) (hpc : c < p) (hk : 0 < k) (hA : 0 < A) (heq : k * A = (c * p ^ e) ^ 2) : (mondrian_factor_shapes (c * p ^ e) A).card ≤ (k.factorization p + 1) * c := by have h1 := mondrian_ordered_shape_half (c * p ^ e) A have h2 := mondrian_ordered_prime_shape_bound c p e k A hc hp hpc hk hA heq have h3 := mondrian_prime_cofactor_le c p e k A hc hp hpc heq have h4 := mondrian_divisors_card_le_two_mul_of_le_sq (A / p ^ (A.factorization p)) c h3 have h5 := Nat.mul_le_mul_left (k.factorization p + 1) h4 nlinarith