mondrian_prime_power_side_log_bound
A pure p-power side fitting in a q times p^e square has exponent at most e plus floor(log_p(q)).
Statement
theorem mondrian_prime_power_side_log_bound (p q e a : ℕ) (hp : Nat.Prime p)
(h : p ^ a ≤ q * p ^ e) : a ≤ e + Nat.log p q- 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- Used by 3
- mondrian_prime_area_shape_boundFor 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.
- mondrian_prime_free_area_shape_boundFor 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…
- mondrian_prime_square_area_free_shape_boundFor distinct primes p and q and t+r=2e, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square have a side…
The proof, explained
The proof bounds p^a strictly above by a single power of p using the upper bound property of the discrete logarithm: since p > 1, q < p^(⌊log_p(q)⌋ + 1), which leads to p^a ≤ q * p^e < p^(⌊log_p(q)⌋ + 1 + e). By the strict monotonicity of powers with base p > 1, the exponent a must be strictly less than ⌊log_p(q)⌋ + 1 + e. Linear integer arithmetic on natural numbers then yields a ≤ e + ⌊log_p(q)⌋.
p^a < p^(Nat.log p q + 1 + e)
Since p is prime, p > 1, so by the definition of the discrete logarithm, q < p^(Nat.log p q + 1). Multiplying both sides by the positive quantity p^e and combining with the hypothesis p^a ≤ q * p^e gives p^a < p^(Nat.log p q + 1) * p^e. Rewriting the product of powers on the right as p^(Nat.log p q + 1 + e) yields the desired bound.
uses
Nat.mul_lt_mul_of_pos_right,Nat.lt_pow_succ_log_self,pow_pos,pow_addhave hh := h.trans_lt (Nat.mul_lt_mul_of_pos_right (Nat.lt_pow_succ_log_self hp.one_lt q) (pow_pos hp.pos e)) rw [← pow_add] at hh
a < Nat.log p q + 1 + e
Since the base p is strictly greater than 1, the power function is strictly monotone. Thus, the inequality p^a < p^(Nat.log p q + 1 + e) implies the same strict inequality between the exponents.
uses
Nat.pow_lt_pow_iff_righthave := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hha ≤ e + Nat.log p q
From the strict inequality of natural numbers a < Nat.log p q + 1 + e, linear integer arithmetic immediately concludes that a ≤ e + Nat.log p q.
omega
Nat.mul_lt_mul_of_pos_right- Multiplying a strict inequality between natural numbers by a positive natural number preserves the strict inequality.
Nat.lt_pow_succ_log_self- For base b > 1 and any natural number x, x is strictly less than b^(⌊log_b(x)⌋ + 1).
pow_pos- A positive element raised to any natural power is strictly positive.
pow_add- The product of powers with the same base equals the base raised to the sum of the exponents: a^(m + n) = a^m * a^n.
Nat.pow_lt_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_power_side_log_bound (p q e a : ℕ) (hp : Nat.Prime p) (h : p ^ a ≤ q * p ^ e) : a ≤ e + Nat.log p q := by have hh := h.trans_lt (Nat.mul_lt_mul_of_pos_right (Nat.lt_pow_succ_log_self hp.one_lt q) (pow_pos hp.pos e)) rw [← pow_add] at hh have := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hh omega