mondrian_prime_free_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 pure p-power area p^t fit in the q times p^e square.
Statement
theorem mondrian_prime_free_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) (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 7
- 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…
- 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…
- 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
The proof bounds the number of valid rectangle shapes of pure prime-power area p^t that fit inside a q * p^e square. Because each rectangle has area p^t, unique factorization implies both side lengths must be pure powers of p whose exponents sum to t. The conditions that the shorter side is at most the longer side, and the longer side fits within the square (at most q * p^e), constrain the exponent of the shorter side to an integer interval of length at most r + ⌊log_p(q)⌋, using the relation t + r = 2e. Applying an interval bound on prime-power side exponents (mondrian_shape_exponent_interval_bound) then limits the total number of shapes to at most r + ⌊log_p(q)⌋ + 1.
Every valid rectangle of area p^t has side lengths that are pure powers of p whose exponents sum to t.
We introduce S as the set of valid shapes mondrian_factor_shapes (q * p^e) (p^t), meaning pairs (d.1, d.2) with d.1 * d.2 = p^t, d.1 ≤ d.2, and d.2 ≤ q * p^e. Since p^t > 0, both sides are positive (via Nat.pos_of_mul_pos_right, Nat.pos_of_mul_pos_left, and pow_pos). As each side divides the prime power p^t, mondrian_dvd_prime_pow_eq implies d.1 = p^(v_p(d.1)) and d.2 = p^(v_p(d.2)). Applying congrArg with the valuation function v_p and simplifying with Nat.factorization_mul and Nat.factorization_pow_self shows the exponents sum to t: v_p(d.1) + v_p(d.2) = t.
uses
mondrian_mem_factor_shapes,Nat.pos_of_mul_pos_right,pow_pos,Nat.pos_of_mul_pos_left,mondrian_dvd_prime_pow_eq,congrArg,Nat.factorization_mul,Nat.factorization_pow_selflet S := mondrian_factor_shapes (q * p ^ e) (p ^ t) have hpow : ∀ d ∈ S, d.1 = p ^ d.1.factorization p ∧ d.2 = p ^ d.2.factorization p ∧ d.1.factorization p + d.2.factorization p = t := 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 pow_pos hp.pos t) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact pow_pos hp.pos t) have hxpow := mondrian_dvd_prime_pow_eq p t d.1 hp ⟨d.2, hprod.symm⟩ have hypow := mondrian_dvd_prime_pow_eq p t d.2 hp ⟨d.1, by nlinarith [hprod]⟩ have hh := congrArg (fun z : ℕ => z.factorization p) hprod have hv : d.1.factorization p + d.2.factorization p = t := by simpa [Nat.factorization_mul (by omega : d.1 ≠ 0) (by omega : d.2 ≠ 0), Nat.factorization_pow_self hp, hp.factorization_self] using hh exact ⟨hxpow, hypow, hv⟩
The number of shapes in S is bounded above by (e + 1) - (e - r - ⌊log_p(q)⌋).
We apply mondrian_shape_exponent_interval_bound with the shorter side d.1 = 1 * p^(v_p(d.1)) and exponent function v_p(d.1) over the interval [e - r - Nat.log p q, e]. For any shape d ∈ S, the upper bound d.2 ≤ q * p^e gives v_p(d.2) ≤ e + Nat.log p q by mondrian_prime_power_side_log_bound. The ordering d.1 ≤ d.2 gives v_p(d.1) ≤ v_p(d.2) by Nat.pow_le_pow_iff_right. Since v_p(d.1) + v_p(d.2) = t and t + r = 2e, linear arithmetic (omega) verifies both v_p(d.1) ≤ e (from 2 * v_p(d.1) ≤ t ≤ 2e) and v_p(d.1) = t - v_p(d.2) ≥ 2e - r - (e + Nat.log p q) = e - r - Nat.log p q.
uses
mondrian_shape_exponent_interval_bound,pow_pos,mondrian_mem_factor_shapes,mondrian_prime_power_side_log_bound,Nat.pow_le_pow_iff_righthave hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (p ^ t) 1 (e - r - Nat.log p q) e S (pow_pos hp.pos t) (fun _ h => h) Prod.fst (fun d => d.1.factorization p) (by intro d hd exact ⟨Or.inl rfl, by simpa using (hpow d hd).1⟩) (by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd obtain ⟨hxpow, hypow, hv⟩ := hpow d hd have hb : d.2.factorization p ≤ e + Nat.log p q := mondrian_prime_power_side_log_bound p q e _ hp (by simpa [← hypow] using hn) have hab : d.1.factorization p ≤ d.2.factorization p := (Nat.pow_le_pow_iff_right hp.one_lt).mp (by simpa [← hxpow, ← hypow] using hord) constructor <;> omega)
Simplifying the arithmetic bound completes the proof.
Unfolding the definition of S in the bound, linear integer arithmetic (omega) simplifies (e + 1) - (e - r - Nat.log p q) to at most r + Nat.log p q + 1, closing the goal.
dsimp [S] at hh omega
mondrian_mem_factor_shapes- A pair d = (d.1, d.2) belongs to mondrian_factor_shapes n A 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 a * b is positive, then a is positive.
pow_pos- A positive number raised to any power is positive.
Nat.pos_of_mul_pos_left- If a product a * b is positive, then b is positive.
mondrian_dvd_prime_pow_eq- Any divisor x of a prime power p^e has the form p^(v_p(x)).
congrArg- Equality is preserved under applying a function: if a = b, then f(a) = f(b).
Nat.factorization_mul- The prime factorization of a product of positive integers is the sum of their individual factorizations: v_p(a * b) = v_p(a) + v_p(b).
Nat.factorization_pow_self- For a prime p, the p-adic valuation of p^n is n: v_p(p^n) = n.
mondrian_shape_exponent_interval_bound- If a subset S of valid factor shapes has one side of the form C * p^(f d) with exponent f(d) confined to [lo, hi], then |S| ≤ hi + 1 - lo.
mondrian_prime_power_side_log_bound- If p is prime and p^a ≤ q * p^e, then the exponent a is at most e + ⌊log_p(q)⌋.
Nat.pow_le_pow_iff_right- For 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_free_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) (p ^ t)).card ≤ r + Nat.log p q + 1 := by let S := mondrian_factor_shapes (q * p ^ e) (p ^ t) have hpow : ∀ d ∈ S, d.1 = p ^ d.1.factorization p ∧ d.2 = p ^ d.2.factorization p ∧ d.1.factorization p + d.2.factorization p = t := 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 pow_pos hp.pos t) have hy : 0 < d.2 := Nat.pos_of_mul_pos_left (by rw [hprod]; exact pow_pos hp.pos t) have hxpow := mondrian_dvd_prime_pow_eq p t d.1 hp ⟨d.2, hprod.symm⟩ have hypow := mondrian_dvd_prime_pow_eq p t d.2 hp ⟨d.1, by nlinarith [hprod]⟩ have hh := congrArg (fun z : ℕ => z.factorization p) hprod have hv : d.1.factorization p + d.2.factorization p = t := by simpa [Nat.factorization_mul (by omega : d.1 ≠ 0) (by omega : d.2 ≠ 0), Nat.factorization_pow_self hp, hp.factorization_self] using hh exact ⟨hxpow, hypow, hv⟩ have hh := mondrian_shape_exponent_interval_bound p (q * p ^ e) (p ^ t) 1 (e - r - Nat.log p q) e S (pow_pos hp.pos t) (fun _ h => h) Prod.fst (fun d => d.1.factorization p) (by intro d hd exact ⟨Or.inl rfl, by simpa using (hpow d hd).1⟩) (by intro d hd obtain ⟨hprod, _, hord, hn⟩ := (mondrian_mem_factor_shapes _ _ d).mp hd obtain ⟨hxpow, hypow, hv⟩ := hpow d hd have hb : d.2.factorization p ≤ e + Nat.log p q := mondrian_prime_power_side_log_bound p q e _ hp (by simpa [← hypow] using hn) have hab : d.1.factorization p ≤ d.2.factorization p := (Nat.pow_le_pow_iff_right hp.one_lt).mp (by simpa [← hxpow, ← hypow] using hord) constructor <;> omega) dsimp [S] at hh omega