mondrian_prime_power_shape_bound
For k at least two and positive A with k times A equal to the area of a p-power square, the number of available shapes is at most the p-adic exponent of k.
Statement
theorem mondrian_prime_power_shape_bound (p e k A : ℕ) (hp : Nat.Prime p)
(hk : 2 ≤ k) (hA : 0 < A) (heq : k * A = (p ^ e) ^ 2) :
(mondrian_factor_shapes (p ^ e) A).card ≤ k.factorization p- 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 5
- mondrian_dvd_prime_pow_eqA divisor x of a power of a prime p is p to its own p-adic exponent.
- mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- mondrian_mem_factor_shapesA dimension pair belongs to the available shape set exactly when its product is the nonzero area A, its first dimension is at most its…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- mondrian_no_perfect_prime_powerNo square whose integer side length is a prime power has a perfect admissible partition.
The proof, explained
To bound the number of available factor shapes of area A fitting into a p^e × p^e square, the proof maps each valid shape (d.1, d.2) injectively to the p-adic valuation of its shorter side, v_p(d.1). Because k * A = (p^e)^2 and k ≥ 2, every divisor of A is a pure power of p, and the geometric constraints d.1 ≤ d.2 ≤ p^e together with d.1 * d.2 < (p^e)^2 force v_p(d.1) into the half-open integer interval [e - v_p(k), e). Since a power of p is determined by its exponent and the second dimension is uniquely determined by area, this mapping is injective, so the number of shapes cannot exceed the interval's size, which is at most v_p(k).
The numbers k, A, and p^e are non-zero.
Linear arithmetic establishes k ≠ 0 from k ≥ 2 and A ≠ 0 from A > 0. Since p is prime, p ≠ 0, and any power of a non-zero element in a reduced monoid with zero is non-zero (`pow_ne_zero`), giving p^e ≠ 0.
uses
pow_ne_zerohave hkne : k ≠ 0 := by omega have hAne : A ≠ 0 := by omega have hnne : p ^ e ≠ 0 := pow_ne_zero e hp.ne_zero
The area A divides p^(2 * e).
By exponent rules and commutativity of multiplication (`pow_mul`, `Nat.mul_comm`), (p^e)^2 = p^(2 * e). Substituting the hypothesis k * A = (p^e)^2, we obtain k * A = p^(2 * e). Because A divides k * A (`dvd_mul_left`), A divides p^(2 * e).
uses
pow_mul,Nat.mul_comm,dvd_mul_lefthave hApow : A ∣ p ^ (2 * e) := by have hnp : (p ^ e) ^ 2 = p ^ (2 * e) := by rw [← pow_mul, Nat.mul_comm e 2] rw [← hnp, ← heq] exact dvd_mul_left A k
The sum of the p-adic valuations of k and A is 2 * e.
Applying the p-adic factorization to both sides of k * A = (p^e)^2 via `congrArg`, the left-hand side expands to v_p(k) + v_p(A) by the additivity of factorization on positive integers (`Nat.factorization_mul`, `Finsupp.add_apply`). The right-hand side simplifies to 2 * e by the power rule for factorizations (`Nat.factorization_pow`, `Finsupp.smul_apply`, `smul_eq_mul`) and the prime valuation v_p(p) = 1 (`Nat.factorization_pow_self`).
uses
congrArg,Nat.factorization_mul,Finsupp.add_apply,Nat.factorization_pow,Finsupp.smul_apply,smul_eq_mul,Nat.factorization_pow_selfhave hvals : k.factorization p + A.factorization p = 2 * e := by have hf := congrArg (fun z : ℕ => z.factorization p) heq rw [Nat.factorization_mul hkne hAne, Finsupp.add_apply, Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul, Nat.factorization_pow_self hp] at hf exact hf
The map f(d) = v_p(d.1) sends each valid factor shape d into the discrete interval [e - v_p(k), e).
Let d = (d.1, d.2) be a factor shape of area A in a square of side p^e (`mondrian_mem_factor_shapes`). Since d.1 * d.2 = A > 0, both d.1 and d.2 are strictly positive (`Nat.pos_of_mul_pos_right`, `Nat.pos_of_mul_pos_left`). Each divides A (`Dvd.intro`) and therefore divides p^(2 * e) (`dvd_trans`). By `mondrian_dvd_prime_pow_eq`, any divisor of a power of p is a power of p, so d.1 = p^(v_p(d.1)) and d.2 = p^(v_p(d.2)). Because k ≥ 2, we have A = (p^e)^2 / k < (p^e)^2; if d.1 ≥ p^e, then d.1 * d.2 ≥ (p^e)^2 > A (`Nat.mul_le_mul`), which is a contradiction. Hence d.1 < p^e, meaning v_p(d.1) < e (`Nat.pow_lt_pow_iff_right`). Similarly, d.2 ≤ p^e gives v_p(d.2) ≤ e (`Nat.pow_le_pow_iff_right`). Taking the p-adic valuation of d.1 * d.2 = A gives v_p(d.1) + v_p(d.2) = v_p(A) (`congrArg`, `Nat.factorization_mul`, `Nat.ne_of_gt`, `Finsupp.add_apply`). Combining this with v_p(k) + v_p(A) = 2 * e and v_p(d.2) ≤ e yields v_p(d.1) = v_p(A) - v_p(d.2) ≥ 2 * e - v_p(k) - e = e - v_p(k). Thus f(d) lies in [e - v_p(k), e) (`Finset.mem_coe`, `Finset.mem_Ico`).
uses
mondrian_mem_factor_shapes,Nat.pos_of_mul_pos_right,Nat.pos_of_mul_pos_left,Dvd.intro,dvd_trans,mondrian_dvd_prime_pow_eq,Nat.mul_le_mul,Nat.pow_lt_pow_iff_right,Nat.pow_le_pow_iff_right,congrArg,Nat.factorization_mul,Nat.ne_of_gt,Finsupp.add_apply,Finset.mem_coe,Finset.mem_Icolet f := fun d : ℕ × ℕ => d.1.factorization p have hmap : Set.MapsTo f ↑(mondrian_factor_shapes (p ^ e) A) ↑(Finset.Ico (e - k.factorization p) e) := by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (p ^ e) A d).mp hd 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) have hxdvd : d.1 ∣ p ^ (2 * e) := (Dvd.intro d.2 hprod).trans hApow have hydvd : d.2 ∣ p ^ (2 * e) := by apply dvd_trans _ hApow exact ⟨d.1, by nlinarith [hprod]⟩ have hxpow := mondrian_dvd_prime_pow_eq p (2 * e) d.1 hp hxdvd have hypow := mondrian_dvd_prime_pow_eq p (2 * e) d.2 hp hydvd have hxlt : d.1 < p ^ e := by have hAlt : A < (p ^ e) ^ 2 := by nlinarith by_contra hnot have hle : p ^ e ≤ d.1 := by omega have hmul := Nat.mul_le_mul hle (hle.trans hord) nlinarith have hxe : d.1.factorization p < e := by apply (Nat.pow_lt_pow_iff_right hp.one_lt).mp simpa only [← hxpow] using hxlt have hye : d.2.factorization p ≤ e := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp simpa only [← hypow] using hn have hxyval : d.1.factorization p + d.2.factorization p = A.factorization p := by have hh := congrArg (fun z : ℕ => z.factorization p) hprod simpa only [Nat.factorization_mul (Nat.ne_of_gt hx) (Nat.ne_of_gt hy), Finsupp.add_apply] using hh simp only [f, Finset.mem_coe, Finset.mem_Ico] omega
The map f is injective on the set of factor shapes.
Suppose two shapes x and y satisfy f(x) = f(y), so v_p(x.1) = v_p(y.1). Because x.1 and y.1 divide A ∣ p^(2 * e) (`mondrian_mem_factor_shapes`, `Dvd.intro`), they are prime powers of p (`mondrian_dvd_prime_pow_eq`), which implies x.1 = p^(v_p(x.1)) = p^(v_p(y.1)) = y.1 (`congrArg`). Since x.1 > 0 (`Nat.pos_of_mul_pos_right`) and x.1 * x.2 = A = y.1 * y.2 = x.1 * y.2, canceling x.1 gives x.2 = y.2 (`Nat.eq_of_mul_eq_mul_left`). Matching both coordinates gives x = y (`Prod.ext`).
uses
mondrian_mem_factor_shapes,Dvd.intro,mondrian_dvd_prime_pow_eq,congrArg,Nat.pos_of_mul_pos_right,Prod.ext,Nat.eq_of_mul_eq_mul_lefthave hinj : Set.InjOn f ↑(mondrian_factor_shapes (p ^ e) A) := by intro x hx y hy hxy obtain ⟨hxp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A x).mp hx obtain ⟨hyp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A y).mp hy have hxdvd : x.1 ∣ p ^ (2 * e) := (Dvd.intro x.2 hxp).trans hApow have hydvd : y.1 ∣ p ^ (2 * e) := (Dvd.intro y.2 hyp).trans hApow have hw : x.1 = y.1 := by rw [mondrian_dvd_prime_pow_eq p (2 * e) x.1 hp hxdvd, mondrian_dvd_prime_pow_eq p (2 * e) y.1 hp hydvd] exact congrArg (fun u => p ^ u) hxy 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 number of available shapes is at most v_p(k).
By injectivity of f, the cardinality of the set of factor shapes is bounded by the cardinality of the target interval [e - v_p(k), e) (`Finset.card_le_card_of_injOn`). The size of this interval is e - (e - v_p(k)) ≤ v_p(k) (`Nat.card_Ico`), which establishes the theorem.
uses
Finset.card_le_card_of_injOn,Nat.card_Icohave hc := Finset.card_le_card_of_injOn f hmap hinj have hcard : (Finset.Ico (e - k.factorization p) e).card ≤ k.factorization p := by simp only [Nat.card_Ico] omega exact hc.trans hcard
pow_ne_zero- A power of a non-zero element in a reduced monoid with zero is non-zero.
pow_mul- Powers of powers satisfy (a^m)^n = a^(m * n).
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
dvd_mul_left- An element divides any product of which it is a factor: a ∣ b * a.
congrArg- Functions preserve equality: if a₁ = a₂, then f(a₁) = f(a₂).
Nat.factorization_mul- The prime factorization of a product of positive integers is the sum of their factorizations.
Finsupp.add_apply- Evaluation of a sum of finitely supported functions is the sum of their evaluations: (g₁ + g₂) a = g₁ a + g₂ a.
Nat.factorization_pow- The prime factorization of n^k is k times the factorization of n.
Finsupp.smul_apply- Evaluation of a scalar multiple of a finitely supported function: (b • v) a = b • v a.
smul_eq_mul- Scalar multiplication in a multiplicative structure is standard multiplication: a • b = a * b.
Nat.factorization_pow_self- For a prime p, the p-adic valuation of p^n is n.
mondrian_mem_factor_shapes- A pair d is a valid factor shape of area A in an n × n square iff d.1 * d.2 = A, A ≠ 0, d.1 ≤ d.2, and d.2 ≤ n.
Nat.pos_of_mul_pos_right- If a product of natural numbers is positive, then its first factor is positive.
Nat.pos_of_mul_pos_left- If a product of natural numbers is positive, then its second factor is positive.
Dvd.intro- If a * c = b, then a divides b.
dvd_trans- Divisibility is transitive: if a ∣ b and b ∣ c, then a ∣ c.
mondrian_dvd_prime_pow_eq- Any divisor of a prime power p^e is uniquely given by p^(v_p(x)).
Nat.mul_le_mul- Multiplication preserves the order ≤ on natural numbers.
Nat.pow_lt_pow_iff_right- For a base greater than one, a^n < a^m iff n < m.
Nat.pow_le_pow_iff_right- For a base greater than one, a^n ≤ a^m iff n ≤ m.
Nat.ne_of_gt- If b < a, then a ≠ b.
Finset.mem_coe- Coercion from Finset to Set preserves membership.
Finset.mem_Ico- An element x belongs to the half-open interval [a, b) iff a ≤ x and x < b.
Prod.ext- Two ordered pairs are equal if their corresponding components are equal.
Nat.eq_of_mul_eq_mul_left- A positive factor can be canceled from the left of an equation: if n > 0 and n * m = n * k, then m = k.
Finset.card_le_card_of_injOn- An injective map from a finite set s to a finite set t implies |s| ≤ |t|.
Nat.card_Ico- The cardinality of the discrete interval [a, b) is b - a.
- Factor shapes of area A in a square of side p^e are represented formally as pairs of dimensions (d.1, d.2) satisfying d.1 * d.2 = A, d.1 ≤ d.2, and d.2 ≤ p^e.
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_power_shape_bound (p e k A : ℕ) (hp : Nat.Prime p) (hk : 2 ≤ k) (hA : 0 < A) (heq : k * A = (p ^ e) ^ 2) : (mondrian_factor_shapes (p ^ e) A).card ≤ k.factorization p := by have hkne : k ≠ 0 := by omega have hAne : A ≠ 0 := by omega have hnne : p ^ e ≠ 0 := pow_ne_zero e hp.ne_zero have hApow : A ∣ p ^ (2 * e) := by have hnp : (p ^ e) ^ 2 = p ^ (2 * e) := by rw [← pow_mul, Nat.mul_comm e 2] rw [← hnp, ← heq] exact dvd_mul_left A k have hvals : k.factorization p + A.factorization p = 2 * e := by have hf := congrArg (fun z : ℕ => z.factorization p) heq rw [Nat.factorization_mul hkne hAne, Finsupp.add_apply, Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul, Nat.factorization_pow_self hp] at hf exact hf let f := fun d : ℕ × ℕ => d.1.factorization p have hmap : Set.MapsTo f ↑(mondrian_factor_shapes (p ^ e) A) ↑(Finset.Ico (e - k.factorization p) e) := by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (p ^ e) A d).mp hd 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) have hxdvd : d.1 ∣ p ^ (2 * e) := (Dvd.intro d.2 hprod).trans hApow have hydvd : d.2 ∣ p ^ (2 * e) := by apply dvd_trans _ hApow exact ⟨d.1, by nlinarith [hprod]⟩ have hxpow := mondrian_dvd_prime_pow_eq p (2 * e) d.1 hp hxdvd have hypow := mondrian_dvd_prime_pow_eq p (2 * e) d.2 hp hydvd have hxlt : d.1 < p ^ e := by have hAlt : A < (p ^ e) ^ 2 := by nlinarith by_contra hnot have hle : p ^ e ≤ d.1 := by omega have hmul := Nat.mul_le_mul hle (hle.trans hord) nlinarith have hxe : d.1.factorization p < e := by apply (Nat.pow_lt_pow_iff_right hp.one_lt).mp simpa only [← hxpow] using hxlt have hye : d.2.factorization p ≤ e := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp simpa only [← hypow] using hn have hxyval : d.1.factorization p + d.2.factorization p = A.factorization p := by have hh := congrArg (fun z : ℕ => z.factorization p) hprod simpa only [Nat.factorization_mul (Nat.ne_of_gt hx) (Nat.ne_of_gt hy), Finsupp.add_apply] using hh simp only [f, Finset.mem_coe, Finset.mem_Ico] omega have hinj : Set.InjOn f ↑(mondrian_factor_shapes (p ^ e) A) := by intro x hx y hy hxy obtain ⟨hxp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A x).mp hx obtain ⟨hyp, _, _, _⟩ := (mondrian_mem_factor_shapes (p ^ e) A y).mp hy have hxdvd : x.1 ∣ p ^ (2 * e) := (Dvd.intro x.2 hxp).trans hApow have hydvd : y.1 ∣ p ^ (2 * e) := (Dvd.intro y.2 hyp).trans hApow have hw : x.1 = y.1 := by rw [mondrian_dvd_prime_pow_eq p (2 * e) x.1 hp hxdvd, mondrian_dvd_prime_pow_eq p (2 * e) y.1 hp hydvd] exact congrArg (fun u => p ^ u) hxy 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 hc := Finset.card_le_card_of_injOn f hmap hinj have hcard : (Finset.Ico (e - k.factorization p) e).card ≤ k.factorization p := by simp only [Nat.card_Ico] omega exact hc.trans hcard