mondrian_prime_area_shape_bound
For distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
Statement
theorem mondrian_prime_area_shape_bound (p q e t r : ℕ) (hp : Nat.Prime p)
(hq : Nat.Prime q) (hpq : p ≠ q) (htr : t + r = 2 * e) :
(mondrian_factor_shapes (q * p ^ e) (q * p ^ t)).card ≤ r + Nat.log p q + 1- Source
- Helper for OP-280 and mondrian_no_perfect_prime_mul_prime_pow. Related work: arXiv:2610.19193, Section 1 (the zero-defect question); arXiv:2007.09639, Theorem 4.1 (prime-power and small prime-product exclusions).
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- mondrian_distinct_prime_not_dvd_powA prime q distinct from p does not divide any power of p.
- 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…
- mondrian_prime_free_factor_pair_encodingIn a positive factor pair of q^s times p^t whose first side is indivisible by q, that side is a pure p-power and the other side contains…
- mondrian_prime_power_side_log_boundA pure p-power side fitting in a q times p^e square has exponent at most e plus floor(log_p(q)).
- mondrian_shape_exponent_interval_boundA family of distinct sorted factor pairs that can be encoded by a chosen side C times p to an exponent in [lo,hi] has at most hi plus one…
- mondrian_two_prime_factor_pair_encodingA positive factor pair of q^s times p^t has complementary q exponents summing to s and p exponents summing to t.
- 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_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
The proof, explained
To bound the number of shapes of area q * p^t fitting into a square of side q * p^e, each shape is partitioned into a side coprime to q and a side divisible by q. Because p ≠ q, exactly one side is a pure prime power p^f, while the other side is q * p^(t - f). The square-fitting condition forces p^f ≤ q * p^e and q * p^(t - f) ≤ q * p^e, which restricts the exponent f to the integer interval [e - r, e + ⌊log_p(q)⌋] using t + r = 2e. An interval cardinality bound on the exponent f then proves there are at most r + ⌊log_p(q)⌋ + 1 such shapes.
Define the set of valid rectangle shapes S, the side g(d) coprime to q, the remaining side o(d), and the p-adic exponent f(d) of g(d).
We let S be the set of shapes of area q * p^t fitting into a square of side q * p^e. For any shape d, g(d) selects the side coprime to q (taking d.2 if q ∣ d.1 and d.1 otherwise), o(d) selects the side divisible by q, and f(d) is the exponent of p in g(d).
let S := mondrian_factor_shapes (q * p ^ e) (q * p ^ t) let g := fun d : ℕ × ℕ => if q ∣ d.1 then d.2 else d.1 let o := fun d : ℕ × ℕ => if q ∣ d.1 then d.1 else d.2 let f := fun d => (g d).factorization p
For any shape d ∈ S, its area is d.1 * d.2 = q * p^t, its dimensions satisfy d.1 ≤ d.2 ≤ q * p^e, and both side lengths are strictly positive.
Unpacking membership d ∈ S using mondrian_mem_factor_shapes gives d.1 * d.2 = q * p^t and d.1 ≤ d.2 ≤ q * p^e. Since p and q are prime, q * p^t is strictly positive (by Nat.mul_pos and pow_pos), so both d.1 and d.2 are strictly positive by Nat.pos_of_mul_pos_right and Nat.pos_of_mul_pos_left.
uses
mondrian_mem_factor_shapes,Nat.pos_of_mul_pos_right,Nat.pos_of_mul_pos_left,Nat.mul_pos,pow_poshave hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧ g d = p ^ f d ∧ o d = q * p ^ ((o d).factorization p) ∧ f d + (o d).factorization p = t ∧ g d ≤ q * p ^ e ∧ o d ≤ q * p ^ e := by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t)) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t))
At least one of the sides d.1, d.2 is not divisible by q.
By mondrian_two_prime_factor_pair_encoding, the powers of q in d.1 and d.2 sum to 1, meaning one side has exponent 0 and the other has exponent 1. If d.1 has exponent 0, then d.1 is a power of p (via pow_zero and one_mul); since p ≠ q, q does not divide any power of p by mondrian_distinct_prime_not_dvd_pow, so q ∤ d.1. The symmetric argument holds if d.2 has exponent 0.
uses
mondrian_two_prime_factor_pair_encoding,pow_zero,one_mul,mondrian_distinct_prime_not_dvd_powhave hfree : ¬ q ∣ d.1 ∨ ¬ q ∣ d.2 := by obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t 1 d.1 d.2 hp hq hpq hx hy (by simpa using hprod) have hbc' : b = 0 ∨ c = 0 := by omega rcases hbc' with hb | hc · left rw [hxb, hb, pow_zero, one_mul] exact mondrian_distinct_prime_not_dvd_pow p q (d.1.factorization p) hp hq hpq · right rw [hyc, hc, pow_zero, one_mul] exact mondrian_distinct_prime_not_dvd_pow p q (d.2.factorization p) hp hq hpq
For every shape d ∈ S, the side g(d) is p^(f d) and o(d) is q * p^(v_p(o d)), with exponents summing to t and both sides bounded by q * p^e.
We split into cases based on whether q ∣ d.1: if so, q ∤ d.2, and mondrian_prime_free_factor_pair_encoding (with Nat.mul_comm) yields d.2 = p^(v_p(d.2)) and d.1 = q * p^(v_p(d.1)); if not, the same lemma yields d.1 = p^(v_p(d.1)) and d.2 = q * p^(v_p(d.2)). In both cases, g(d) and o(d) match these forms, their exponents sum to t, and both sides satisfy the upper bound q * p^e. The conclusion is assembled using And.intro, Or.inr, and Or.inl.
uses
mondrian_prime_free_factor_pair_encoding,Nat.mul_comm,And.intro,Or.inr,Or.inlby_cases hh : q ∣ d.1 · have hfree' : ¬ q ∣ d.2 := hfree.resolve_left (by simpa using hh) have h := mondrian_prime_free_factor_pair_encoding p q t 1 d.2 d.1 hp hq hpq hy hx (by simpa [Nat.mul_comm] using hprod) hfree' simpa [g, o, f, hh] using And.intro (Or.inr rfl : d.2 = d.1 ∨ d.2 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro hn (hord.trans hn))))) · have h := mondrian_prime_free_factor_pair_encoding p q t 1 d.1 d.2 hp hq hpq hx hy (by simpa using hprod) hh simpa [g, o, f, hh] using And.intro (Or.inl rfl : d.1 = d.1 ∨ d.1 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro (hord.trans hn) hn))))
The exponent f(d) satisfies e - r ≤ f(d) ≤ e + ⌊log_p(q)⌋, which bounds the cardinality |S| by (e + ⌊log_p(q)⌋) + 1 - (e - r).
We apply mondrian_shape_exponent_interval_bound with area q * p^t > 0 (via Nat.mul_pos and pow_pos), C = 1, and interval bounds lo = e - r and hi = e + Nat.log p q. For any d ∈ S, g(d) = p^(f d) ≤ q * p^e gives f(d) ≤ e + Nat.log p q via mondrian_prime_power_side_log_bound. Meanwhile, o(d) = q * p^(v_p(o d)) ≤ q * p^e implies p^(v_p(o d)) ≤ p^e, so v_p(o d) ≤ e by Nat.pow_le_pow_iff_right. Since f(d) + v_p(o d) = t and t + r = 2e, linear arithmetic (omega) implies f(d) = t - v_p(o d) ≥ (2e - r) - e = e - r.
uses
mondrian_shape_exponent_interval_bound,Nat.mul_pos,pow_pos,mondrian_prime_power_side_log_bound,Nat.pow_le_pow_iff_righthave hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q * p ^ t) 1 (e - r) (e + Nat.log p q) S (Nat.mul_pos hq.pos (pow_pos hp.pos t)) (fun _ h => h) g f (by intro d hd; exact ⟨(hg d hd).1, by simpa using (hg d hd).2.1⟩) (by intro d hd obtain ⟨_, hgp, hop, hv, hgn, hon⟩ := hg d hd have ha := mondrian_prime_power_side_log_bound p q e (f d) hp (by rwa [← hgp]) have hb : (o d).factorization p ≤ e := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp have := hon rw [hop] at this nlinarith [hq.pos] constructor <;> omega)
The number of valid factor shapes is at most r + ⌊log_p(q)⌋ + 1.
Unfolding S via dsimp [S], the bound becomes |mondrian_factor_shapes (q * p^e) (q * p^t)| ≤ e + Nat.log p q + 1 - (e - r). Linear arithmetic (omega) cancels e, simplifying the upper bound directly to r + Nat.log p q + 1.
dsimp [S] at hh omega
mondrian_mem_factor_shapes- A pair of dimensions d = (d.1, d.2) belongs to the factor shapes of area A fitting into a square of side n if and only if 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 a * b is strictly positive, then a is strictly positive.
Nat.pos_of_mul_pos_left- If a product of natural numbers a * b is strictly positive, then b is strictly positive.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
pow_pos- Any natural power of a strictly positive number is strictly positive.
mondrian_two_prime_factor_pair_encoding- If positive integers x and y satisfy x * y = q^s * p^t for distinct primes p and q, then the exponents of q in x and y sum to s, their p-adic valuations sum to t, and both numbers are products of powers of q and p.
pow_zero- Any number raised to the power 0 is 1.
one_mul- Multiplying any number by 1 leaves it unchanged.
mondrian_distinct_prime_not_dvd_pow- A prime q cannot divide any power of a distinct prime p.
mondrian_prime_free_factor_pair_encoding- If positive integers x and y satisfy x * y = q^s * p^t for distinct primes p and q, and q does not divide x, then x is a pure power of p and y contains the full factor of q^s.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
And.intro- Given proofs of propositions A and B, construct a proof of A ∧ B.
Or.inr- Given a proof of proposition B, construct a proof of the disjunction A ∨ B.
Or.inl- Given a proof of proposition A, construct a proof of the disjunction A ∨ B.
mondrian_shape_exponent_interval_bound- If each rectangle shape in a subset S has a side of the form C * p^(f d) with f(d) in the integer interval [lo, hi], then the cardinality of S is at most hi + 1 - lo.
mondrian_prime_power_side_log_bound- If p is prime and p^a ≤ q * p^e, then a ≤ e + ⌊log_p(q)⌋.
Nat.pow_le_pow_iff_right- For a base a > 1, a^n ≤ a^m if and only if n ≤ m.
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_area_shape_bound (p q e t r : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) (htr : t + r = 2 * e) : (mondrian_factor_shapes (q * p ^ e) (q * p ^ t)).card ≤ r + Nat.log p q + 1 := by let S := mondrian_factor_shapes (q * p ^ e) (q * p ^ t) let g := fun d : ℕ × ℕ => if q ∣ d.1 then d.2 else d.1 let o := fun d : ℕ × ℕ => if q ∣ d.1 then d.1 else d.2 let f := fun d => (g d).factorization p have hg : ∀ d ∈ S, (g d = d.1 ∨ g d = d.2) ∧ g d = p ^ f d ∧ o d = q * p ^ ((o d).factorization p) ∧ f d + (o d).factorization p = t ∧ g d ≤ q * p ^ e ∧ o d ≤ q * p ^ e := by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd have hx : 0 < d.1 := Nat.pos_of_mul_pos_right (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t)) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact Nat.mul_pos hq.pos (pow_pos hp.pos t)) have hfree : ¬ q ∣ d.1 ∨ ¬ q ∣ d.2 := by obtain ⟨b, c, hbc, hxb, hyc, hv⟩ := mondrian_two_prime_factor_pair_encoding p q t 1 d.1 d.2 hp hq hpq hx hy (by simpa using hprod) have hbc' : b = 0 ∨ c = 0 := by omega rcases hbc' with hb | hc · left rw [hxb, hb, pow_zero, one_mul] exact mondrian_distinct_prime_not_dvd_pow p q (d.1.factorization p) hp hq hpq · right rw [hyc, hc, pow_zero, one_mul] exact mondrian_distinct_prime_not_dvd_pow p q (d.2.factorization p) hp hq hpq by_cases hh : q ∣ d.1 · have hfree' : ¬ q ∣ d.2 := hfree.resolve_left (by simpa using hh) have h := mondrian_prime_free_factor_pair_encoding p q t 1 d.2 d.1 hp hq hpq hy hx (by simpa [Nat.mul_comm] using hprod) hfree' simpa [g, o, f, hh] using And.intro (Or.inr rfl : d.2 = d.1 ∨ d.2 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro hn (hord.trans hn))))) · have h := mondrian_prime_free_factor_pair_encoding p q t 1 d.1 d.2 hp hq hpq hx hy (by simpa using hprod) hh simpa [g, o, f, hh] using And.intro (Or.inl rfl : d.1 = d.1 ∨ d.1 = d.2) (And.intro h.1 (And.intro h.2.1 (And.intro h.2.2 (And.intro (hord.trans hn) hn)))) have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (q * p ^ t) 1 (e - r) (e + Nat.log p q) S (Nat.mul_pos hq.pos (pow_pos hp.pos t)) (fun _ h => h) g f (by intro d hd; exact ⟨(hg d hd).1, by simpa using (hg d hd).2.1⟩) (by intro d hd obtain ⟨_, hgp, hop, hv, hgn, hon⟩ := hg d hd have ha := mondrian_prime_power_side_log_bound p q e (f d) hp (by rwa [← hgp]) have hb : (o d).factorization p ≤ e := by apply (Nat.pow_le_pow_iff_right hp.one_lt).mp have := hon rw [hop] at this nlinarith [hq.pos] constructor <;> omega) dsimp [S] at hh omega