mondrian_prime_first_exponent_shape_bound
When the p-adic exponent of k is exactly one, at most c unordered shapes of area A fit in a c times p to the e square with area k times A and p exceeding c.
Statement
theorem mondrian_prime_first_exponent_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) (hr : k.factorization p = 1) :
(mondrian_factor_shapes (c * p ^ e) A).card ≤ 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 6
- mondrian_factor_shapesThe available unordered integer dimension pairs of positive area A that fit in an n-square, encoded in increasing order.
- mondrian_factorization_le_scaled_prime_powA positive integer at most c times p to the e has p-adic exponent at most e when the prime p exceeds c.
- 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…
- mondrian_sorted_pairs_eq_of_sharedTwo increasing positive factor pairs of the same nonzero area that share a side length are equal.
- 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_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
The proof establishes an upper bound of c on the number of valid Mondrian shapes of area A fitting in a c * p^e square by constructing an injection f from the set of shapes into the integer interval {1, ..., c}. Taking the p-adic valuation of k * A = (c * p^e)^2 shows that v_p(A) = 2e - 1. Because c < p and each coordinate of an admissible shape d = (d₁, d₂) is at most c * p^e, each coordinate's p-adic valuation is at most e, which forces exactly one coordinate to have valuation e. Dividing this unique coordinate by p^e yields an integer in {1, ..., c}, and this assignment is injective because an ordered factor pair of A is completely determined by any one of its components.
p does not divide c, and the p-adic valuation of A satisfies 1 + v_p(A) = 2e.
Since 0 < c < p, p cannot divide c, which implies that the p-adic exponent of c is zero. Taking the prime factorization at p of both sides of k * A = (c * p^e)^2 and expanding using v_p(k) = 1, v_p(c) = 0, and v_p(p^e) = e yields 1 + v_p(A) = 2(0 + e) = 2e.
uses
Nat.not_dvd_of_pos_of_lt,congrArg,Nat.factorization_mul,Nat.ne_of_gt,Finsupp.add_apply,Nat.factorization_pow,Finsupp.smul_apply,smul_eq_mul,pow_ne_zero,Nat.factorization_eq_zero_of_not_dvd,Nat.factorization_pow_selfhave hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc have hvals : 1 + A.factorization p = 2 * e := by have hf := congrArg (fun z : ℕ => z.factorization p) heq rw [Nat.factorization_mul (Nat.ne_of_gt hk) (Nat.ne_of_gt hA), Finsupp.add_apply, Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul, Nat.factorization_mul (Nat.ne_of_gt hc) (pow_ne_zero e hp.ne_zero), Finsupp.add_apply, Nat.factorization_eq_zero_of_not_dvd hcnot, Nat.factorization_pow_self hp, hr] at hf simpa using hf
Define the coordinate selection high and the reduction map f.
For any factor pair d = (d₁, d₂), define high(d) to be d₁ if v_p(d₁) = e and d₂ otherwise. Then define f(d) = high(d) / p^e, which divides out the p^e factor from that coordinate.
let high := fun d : ℕ × ℕ => if d.1.factorization p = e then d.1 else d.2 let f := fun d : ℕ × ℕ => high d / p ^ e
For every shape d, high(d) satisfies 0 < high(d) ≤ c * p^e and has p-adic valuation e.
Any valid shape d satisfies d₁ * d₂ = A with 0 < d₁ ≤ d₂ ≤ c * p^e. Since c < p, the helper lemma mondrian_factorization_le_scaled_prime_pow guarantees that both v_p(d₁) ≤ e and v_p(d₂) ≤ e. Because v_p(d₁) + v_p(d₂) = v_p(A) = 2e - 1, the two integer valuations sum to 2e - 1 and neither exceeds e, which forces exactly one of them to equal e (and the other e - 1). Therefore, high(d) picks the coordinate with valuation e, which is positive and bounded above by c * p^e.
uses
mondrian_mem_factor_shapes,Nat.pos_of_mul_pos_right,Nat.pos_of_mul_pos_left,mondrian_factorization_le_scaled_prime_pow,congrArg,Nat.factorization_mul,Nat.ne_of_gt,Finsupp.add_apply,if_pos,And.intro,if_neghave hhigh : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A, 0 < high d ∧ high d ≤ c * p ^ e ∧ (high d).factorization p = e := by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (c * 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 hxval := mondrian_factorization_le_scaled_prime_pow c p e d.1 hp hpc hx (hord.trans hn) have hyval := mondrian_factorization_le_scaled_prime_pow c p e d.2 hp hpc hy 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 by_cases hh : d.1.factorization p = e · simpa only [high, if_pos hh] using And.intro hx (And.intro (hord.trans hn) hh) · have hyval' : d.2.factorization p = e := by omega simpa only [high, if_neg hh] using And.intro hy (And.intro hn hyval')
For every shape d, high(d) = p^e * f(d).
Because high(d) has p-adic exponent e, factoring high(d) into its prime-p part and prime-to-p part via Nat.ordProj_mul_ordCompl_eq_self yields high(d) = p^e * (high(d) / p^e) = p^e * f(d).
uses
Nat.ordProj_mul_ordCompl_eq_selfhave hrec : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A, high d = p ^ e * f d := by intro d hd have hf := Nat.ordProj_mul_ordCompl_eq_self (high d) p rw [(hhigh d hd).2.2] at hf exact hf.symm
The function f maps shapes into the discrete interval {1, ..., c}. automation
We verify 1 ≤ f(d) ≤ c. If f(d) < 1, then f(d) = 0, which would imply high(d) = p^e * 0 = 0, contradicting high(d) > 0. If f(d) > c, then f(d) ≥ c + 1, so high(d) = p^e * f(d) ≥ p^e * (c + 1) > c * p^e, contradicting high(d) ≤ c * p^e. Both contradictions are discharged using linear and nonlinear arithmetic solvers (omega and nlinarith).
uses
pow_pos,Finset.mem_Icc.mpr,Nat.mul_zero,Nat.mul_le_mul_lefthave hmap : Set.MapsTo f ↑(mondrian_factor_shapes (c * p ^ e) A) ↑(Finset.Icc 1 c) := by intro d hd have hrec' := hrec d hd obtain ⟨hpos, hn, hv⟩ := hhigh d hd have hppos := pow_pos hp.pos e apply Finset.mem_Icc.mpr constructor · by_contra hn have hf0 : f d = 0 := by omega rw [hf0, Nat.mul_zero] at hrec' omega · by_contra hn have hm := Nat.mul_le_mul_left (p ^ e) (by omega : c + 1 ≤ f d) nlinarith
The map f is injective on the set of shapes. automation
If f(x) = f(y), then high(x) = p^e * f(x) = p^e * f(y) = high(y). This equality means that x and y share at least one coordinate (x₁ = y₁, x₁ = y₂, x₂ = y₁, or x₂ = y₂). Since x and y are both ordered pairs of factors of A, sharing any coordinate implies x = y by mondrian_sorted_pairs_eq_of_shared.
uses
mondrian_mem_factor_shapes,mondrian_sorted_pairs_eq_of_sharedhave hinj : Set.InjOn f ↑(mondrian_factor_shapes (c * p ^ e) A) := by intro x hx y hy he have hg : high x = high y := by rw [hrec x hx, hrec y hy, he] obtain ⟨hxp, _, hxo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A x).mp hx obtain ⟨hyp, _, hyo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A y).mp hy apply mondrian_sorted_pairs_eq_of_shared x y A hA hxp hyp hxo hyo dsimp [high] at hg split_ifs at hg <;> tauto
The number of shapes is at most c.
Since f is an injection from the set of valid shapes into {1, ..., c}, the cardinality of the domain is at most the cardinality of {1, ..., c}, which is c, by Finset.card_le_card_of_injOn.
uses
Finset.card_le_card_of_injOnhave hcard := Finset.card_le_card_of_injOn f hmap hinj simpa using hcard
And.intro- Proofs of a and b combine to prove the conjunction a ∧ b.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t injectively, then |s| ≤ |t|.
Finset.mem_Icc.mpr- If a ≤ x and x ≤ b, then x belongs to the closed discrete interval [a, b].
Finsupp.add_apply- The value of the sum of two finitely supported functions at an element is the sum of their individual values.
Finsupp.smul_apply- Evaluating the scalar multiple of a finitely supported function at an element equals the scalar multiple of the evaluated function.
Nat.factorization_mul- The prime factorization of the product of two positive integers is the sum of their individual prime factorizations.
Nat.factorization_pow- The prime factorization of n^k is k times the prime factorization of n.
Nat.factorization_pow_self- For a prime p, the exponent of p in the prime factorization of p^n is n.
Nat.factorization_eq_zero_of_not_dvd- If a prime p does not divide n, then the exponent of p in the prime factorization of n is zero.
Nat.mul_zero- Multiplying any natural number by zero yields zero.
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor preserves the inequality.
Nat.ne_of_gt- If b < a, then a ≠ b.
Nat.not_dvd_of_pos_of_lt- A positive natural number n is not divisible by any strictly larger natural number m.
Nat.ordProj_mul_ordCompl_eq_self- Multiplying the p-part of n, p^(v_p(n)), by the quotient n / p^(v_p(n)) recovers n.
Nat.pos_of_mul_pos_left- If a product a * b is strictly positive, then b is strictly positive.
Nat.pos_of_mul_pos_right- If a product a * b is strictly positive, then a is strictly positive.
congrArg- If two inputs are equal, the values of a function applied to them are equal.
if_pos- If a condition c is true, the if-then-else expression evaluates to the then-branch.
if_neg- If a condition c is false, the if-then-else expression evaluates to the else-branch.
mondrian_factorization_le_scaled_prime_pow- For a prime p > c and positive integer x ≤ c * p^e, the p-adic exponent of x is at most e.
mondrian_mem_factor_shapes- A pair d = (d₁, d₂) belongs to mondrian_factor_shapes n A if and only if d₁ * d₂ = A, A ≠ 0, d₁ ≤ d₂, and d₂ ≤ n.
mondrian_sorted_pairs_eq_of_shared- If two ordered factor pairs of A > 0 share at least one coordinate, then the two pairs are identical.
pow_ne_zero- A power of a non-zero element in a reduced monoid with zero is non-zero.
pow_pos- A strictly positive number raised to any power is strictly positive.
smul_eq_mul- Scalar multiplication of natural numbers agrees with standard multiplication.
- The interval bounds 1 ≤ f(d) ≤ c in Step 5 are proved by contradiction using arithmetic automation (omega and nlinarith).
- In Step 6, the case analysis showing that high(x) = high(y) forces x and y to share at least one coordinate is discharged by propositional automation (tauto).
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_first_exponent_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) (hr : k.factorization p = 1) : (mondrian_factor_shapes (c * p ^ e) A).card ≤ c := by have hcnot : ¬ p ∣ c := Nat.not_dvd_of_pos_of_lt hc hpc have hvals : 1 + A.factorization p = 2 * e := by have hf := congrArg (fun z : ℕ => z.factorization p) heq rw [Nat.factorization_mul (Nat.ne_of_gt hk) (Nat.ne_of_gt hA), Finsupp.add_apply, Nat.factorization_pow, Finsupp.smul_apply, smul_eq_mul, Nat.factorization_mul (Nat.ne_of_gt hc) (pow_ne_zero e hp.ne_zero), Finsupp.add_apply, Nat.factorization_eq_zero_of_not_dvd hcnot, Nat.factorization_pow_self hp, hr] at hf simpa using hf let high := fun d : ℕ × ℕ => if d.1.factorization p = e then d.1 else d.2 let f := fun d : ℕ × ℕ => high d / p ^ e have hhigh : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A, 0 < high d ∧ high d ≤ c * p ^ e ∧ (high d).factorization p = e := by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes (c * 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 hxval := mondrian_factorization_le_scaled_prime_pow c p e d.1 hp hpc hx (hord.trans hn) have hyval := mondrian_factorization_le_scaled_prime_pow c p e d.2 hp hpc hy 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 by_cases hh : d.1.factorization p = e · simpa only [high, if_pos hh] using And.intro hx (And.intro (hord.trans hn) hh) · have hyval' : d.2.factorization p = e := by omega simpa only [high, if_neg hh] using And.intro hy (And.intro hn hyval') have hrec : ∀ d ∈ mondrian_factor_shapes (c * p ^ e) A, high d = p ^ e * f d := by intro d hd have hf := Nat.ordProj_mul_ordCompl_eq_self (high d) p rw [(hhigh d hd).2.2] at hf exact hf.symm have hmap : Set.MapsTo f ↑(mondrian_factor_shapes (c * p ^ e) A) ↑(Finset.Icc 1 c) := by intro d hd have hrec' := hrec d hd obtain ⟨hpos, hn, hv⟩ := hhigh d hd have hppos := pow_pos hp.pos e apply Finset.mem_Icc.mpr constructor · by_contra hn have hf0 : f d = 0 := by omega rw [hf0, Nat.mul_zero] at hrec' omega · by_contra hn have hm := Nat.mul_le_mul_left (p ^ e) (by omega : c + 1 ≤ f d) nlinarith have hinj : Set.InjOn f ↑(mondrian_factor_shapes (c * p ^ e) A) := by intro x hx y hy he have hg : high x = high y := by rw [hrec x hx, hrec y hy, he] obtain ⟨hxp, _, hxo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A x).mp hx obtain ⟨hyp, _, hyo, _⟩ := (mondrian_mem_factor_shapes (c * p ^ e) A y).mp hy apply mondrian_sorted_pairs_eq_of_shared x y A hA hxp hyp hxo hyo dsimp [high] at hg split_ifs at hg <;> tauto have hcard := Finset.card_le_card_of_injOn f hmap hinj simpa using hcard