mondrian_ordered_prime_shape_bound
The 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 number of divisors of the p-free part of A, when k times A is the square area and p exceeds c.
Statement
theorem mondrian_ordered_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) : (A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e)).card ≤ (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card
- 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 1
- mondrian_prime_pair_encodingFor an equal-area factor pair fitting in a c times p to the e square with p greater than c, the p-adic exponent of its first side lies…
- Used by 1
- mondrian_prime_shape_boundIf 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…
The proof, explained
The proof bounds the number of ordered shapes fitting in the square by defining an injection f(d₁, d₂) = (v_p(d₁), d₁ / p^(v_p(d₁))) from the set of valid divisor pairs into [e - v_p(k), e] × divisors(A / p^(v_p(A))). The image constraints follow from a previous lemma (mondrian_prime_pair_encoding), and injectivity holds because the prime power and p-free part reconstruct d₁, which in turn uniquely determines d₂ = A / d₁. The desired bound then follows directly by computing the cardinality of this Cartesian product.
The encoding function f(d₁, d₂) = (v_p(d₁), d₁ / p^(v_p(d₁))) maps every valid shape in S into the product set [e - v_p(k), e] × divisors(A / p^(v_p(A))).
Let S be the set of divisor pairs (d₁, d₂) of A fitting in a c * p^e square, so d₁ * d₂ = A with d₁, d₂ ≤ c * p^e. Since A > 0, both d₁ and d₂ are strictly positive. Applying the lemma mondrian_prime_pair_encoding, the p-adic valuation v_p(d₁) is bounded between e - v_p(k) and e, while the p-free part d₁ / p^(v_p(d₁)) divides the p-free part A / p^(v_p(A)). Thus f maps S into the Cartesian product of the integer interval [e - v_p(k), e] and the divisors of A / p^(v_p(A)).
uses
Finset.mem_filter.mp,Nat.mem_divisorsAntidiagonal.mp,Nat.pos_of_mul_pos_right,Nat.pos_of_mul_pos_left,mondrian_prime_pair_encoding,Finset.mem_product.mpr,Finset.mem_Icc.mprlet f := fun d : ℕ × ℕ => (d.1.factorization p, d.1 / p ^ (d.1.factorization p)) let S := A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e) have hmap : Set.MapsTo f ↑S ↑(Finset.Icc (e - k.factorization p) e ×ˢ (A / p ^ (A.factorization p)).divisors) := by intro d hd obtain ⟨hdA, hxn, hyn⟩ := Finset.mem_filter.mp hd have hprod := (Nat.mem_divisorsAntidiagonal.mp hdA).1 have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by omega : 0 < d.1 * d.2) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by omega : 0 < d.1 * d.2) obtain ⟨hlo, hup, hmem⟩ := mondrian_prime_pair_encoding c p e k A d.1 d.2 hc hp hpc hk hA heq hx hy hxn hyn hprod exact Finset.mem_product.mpr ⟨Finset.mem_Icc.mpr ⟨hlo, hup⟩, hmem⟩
The encoding function f is injective on S.
Suppose f(x) = f(y) for shapes x, y ∈ S. Reconstructing each first coordinate from its p-adic valuation and p-free part via Nat.ordProj_mul_ordCompl_eq_self shows x₁ = y₁. Since both pairs satisfy x₁ * x₂ = A and y₁ * y₂ = A with x₁ > 0, cancelling x₁ from x₁ * x₂ = x₁ * y₂ yields x₂ = y₂. By Prod.ext, x = y, so f is injective on S.
uses
congrArg,Nat.ordProj_mul_ordCompl_eq_self,Nat.mem_divisorsAntidiagonal.mp,Finset.mem_filter.mp,Nat.pos_of_mul_pos_right,Prod.ext,Nat.eq_of_mul_eq_mul_lefthave hinj : Set.InjOn f ↑S := by intro x hx y hy he have hw := congrArg (fun z : ℕ × ℕ => p ^ z.1 * z.2) he dsimp [f] at hw simp only [Nat.ordProj_mul_ordCompl_eq_self] at hw have hxp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hx).1).1 have hyp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hy).1).1 have hxpos : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2) apply Prod.ext hw apply Nat.eq_of_mul_eq_mul_left hxpos rw [hxp, hw, hyp]
The cardinality of S is bounded by (v_p(k) + 1) * |divisors(A / p^(v_p(A)))|.
By Finset.card_le_card_of_injOn, the injectivity of f implies that |S| is at most the cardinality of the codomain product. The size of this Cartesian product is the length of the interval, (e + 1) - (e - v_p(k)), times the number of divisors of the p-free part of A. Because (e + 1) - (e - v_p(k)) ≤ v_p(k) + 1 by linear arithmetic, multiplying by the divisor count preserves the inequality, concluding the proof.
uses
Finset.card_le_card_of_injOn,Nat.mul_le_mul_righthave hcard := Finset.card_le_card_of_injOn f hmap hinj calc S.card ≤ (Finset.Icc (e - k.factorization p) e ×ˢ (A / p ^ (A.factorization p)).divisors).card := hcard _ = (e + 1 - (e - k.factorization p)) * (A / p ^ (A.factorization p)).divisors.card := by simp _ ≤ (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card := Nat.mul_le_mul_right _ (by omega)
Finset.mem_filter.mp- An element belongs to a filtered set if and only if it belongs to the original set and satisfies the filter predicate.
Nat.mem_divisorsAntidiagonal.mp- If a pair of numbers belongs to the antidiagonal of divisors of n, their product equals n.
Nat.pos_of_mul_pos_right- If the product of two natural numbers is positive, then the first factor is positive.
Nat.pos_of_mul_pos_left- If the product of two natural numbers is positive, then the second factor is positive.
mondrian_prime_pair_encoding- For rectangle dimensions x and y at most c * p^e with x * y = A and k * A = (c * p^e)^2 where c < p, the p-adic valuation of x is bounded between e - v_p(k) and e, and the p-free part of x divides the p-free part of A.
Finset.mem_product.mpr- A pair belongs to the Cartesian product of two finite sets if its first component is in the first set and its second component is in the second set.
Finset.mem_Icc.mpr- A number belongs to the closed interval [a, b] if it is greater than or equal to a and less than or equal to b.
congrArg- Applying a function to equal inputs yields equal outputs.
Nat.ordProj_mul_ordCompl_eq_self- Multiplying the prime power p^(v_p(n)) by the p-free part n / p^(v_p(n)) reconstructs n.
Prod.ext- Two pairs are equal if their first components are equal and their second components are equal.
Nat.eq_of_mul_eq_mul_left- A positive common factor on the left of an equality of natural numbers can be cancelled.
Finset.card_le_card_of_injOn- If a function maps a finite set injectively into another finite set, the cardinality of the domain is at most the cardinality of the codomain.
Nat.mul_le_mul_right- Multiplying both sides of an inequality of natural numbers by a number on the right preserves the inequality.
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_ordered_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) : (A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e)).card ≤ (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card := by let f := fun d : ℕ × ℕ => (d.1.factorization p, d.1 / p ^ (d.1.factorization p)) let S := A.divisorsAntidiagonal.filter (fun d => d.1 ≤ c * p ^ e ∧ d.2 ≤ c * p ^ e) have hmap : Set.MapsTo f ↑S ↑(Finset.Icc (e - k.factorization p) e ×ˢ (A / p ^ (A.factorization p)).divisors) := by intro d hd obtain ⟨hdA, hxn, hyn⟩ := Finset.mem_filter.mp hd have hprod := (Nat.mem_divisorsAntidiagonal.mp hdA).1 have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by omega : 0 < d.1 * d.2) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by omega : 0 < d.1 * d.2) obtain ⟨hlo, hup, hmem⟩ := mondrian_prime_pair_encoding c p e k A d.1 d.2 hc hp hpc hk hA heq hx hy hxn hyn hprod exact Finset.mem_product.mpr ⟨Finset.mem_Icc.mpr ⟨hlo, hup⟩, hmem⟩ have hinj : Set.InjOn f ↑S := by intro x hx y hy he have hw := congrArg (fun z : ℕ × ℕ => p ^ z.1 * z.2) he dsimp [f] at hw simp only [Nat.ordProj_mul_ordCompl_eq_self] at hw have hxp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hx).1).1 have hyp := (Nat.mem_divisorsAntidiagonal.mp (Finset.mem_filter.mp hy).1).1 have hxpos : 0 < x.1 := Nat.pos_of_mul_pos_right (by omega : 0 < x.1 * x.2) apply Prod.ext hw apply Nat.eq_of_mul_eq_mul_left hxpos rw [hxp, hw, hyp] have hcard := Finset.card_le_card_of_injOn f hmap hinj calc S.card ≤ (Finset.Icc (e - k.factorization p) e ×ˢ (A / p ^ (A.factorization p)).divisors).card := hcard _ = (e + 1 - (e - k.factorization p)) * (A / p ^ (A.factorization p)).divisors.card := by simp _ ≤ (k.factorization p + 1) * (A / p ^ (A.factorization p)).divisors.card := Nat.mul_le_mul_right _ (by omega)