mondrian_prime_square_cofactor_side_bound
A side q^2 times p^a fitting in a q times p^e square satisfies a plus floor(log_p(q)) plus one at most e, for distinct primes.
Statement
theorem mondrian_prime_square_cofactor_side_bound (p q e a : ℕ) (hp : Nat.Prime p)
(hq : Nat.Prime q) (hpq : p ≠ q) (h : q ^ 2 * p ^ a ≤ q * p ^ e) :
a + Nat.log p q + 1 ≤ e- 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 3
- mondrian_prime_log_gapFor distinct primes p and q, p to floor(log_p(q)) is strictly less than q, q is below the next power, and floor(log_p(q)) plus one is…
- 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_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 establishes the bound on the exponent by comparing powers of the prime p. First, cancelling a factor of q > 0 from the hypothesis q^2 * p^a ≤ q * p^e simplifies it to q * p^a ≤ p^e. Because p and q are distinct primes, q strictly exceeds p^(floor(log_p(q))), which after multiplying by p^a yields the strict inequality p^(floor(log_p(q)) + a) < q * p^a ≤ p^e. Finally, since base p > 1 is strictly monotone, this forces floor(log_p(q)) + a < e, which is equivalent over ℕ to a + floor(log_p(q)) + 1 ≤ e.
q * p^a ≤ p^e
Dividing both sides of the hypothesis q^2 * p^a ≤ q * p^e by q cancels a factor of q. Since q is prime, q > 0, so non-linear arithmetic (`nlinarith`) establishes q * p^a ≤ p^e.
have hc : q * p ^ a ≤ p ^ e := by nlinarith [hq.pos]
p^(Nat.log p q + a) < p^e
By `pow_add`, p^(Nat.log p q + a) = p^(Nat.log p q) * p^a. Because p and q are distinct primes, `mondrian_prime_log_gap` provides the strict inequality p^(Nat.log p q) < q. Since p is prime, p > 0, so p^a > 0 by `pow_pos`. Multiplying the strict inequality on the right by p^a via `Nat.mul_lt_mul_of_pos_right` gives p^(Nat.log p q) * p^a < q * p^a. Combining this with q * p^a ≤ p^e from the previous step by transitivity yields p^(Nat.log p q + a) < p^e.
uses
pow_add,Nat.mul_lt_mul_of_pos_right,mondrian_prime_log_gap,pow_poshave hh : p ^ (Nat.log p q + a) < p ^ e := by rw [pow_add] exact (Nat.mul_lt_mul_of_pos_right (mondrian_prime_log_gap p q hp hq hpq).1 (pow_pos hp.pos a)).trans_le hc
Nat.log p q + a < e, which implies a + Nat.log p q + 1 ≤ e
Because p is prime, p > 1. By `Nat.pow_lt_pow_iff_right`, the base-p exponential map is strictly monotone, so p^(Nat.log p q + a) < p^e implies Nat.log p q + a < e. For natural numbers, x < e is equivalent to x + 1 ≤ e, so linear integer arithmetic (`omega`) concludes a + Nat.log p q + 1 ≤ e.
uses
Nat.pow_lt_pow_iff_righthave := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hh omega
pow_add- In any monoid, powers add under multiplication: a^(m + n) = a^m * a^n.
Nat.mul_lt_mul_of_pos_right- For natural numbers, multiplying a strict inequality n < m on the right by a positive number k > 0 preserves strict inequality: n * k < m * k.
mondrian_prime_log_gap- For distinct primes p and q, the power p^(floor(log_p q)) is strictly less than q, which is strictly less than p^(floor(log_p q) + 1), and floor(log_p q) + 1 < q.
pow_pos- A positive element raised to any natural power remains strictly positive: a > 0 implies a^n > 0.
Nat.pow_lt_pow_iff_right- For any base a > 1, exponentiation of natural numbers is strictly monotone: 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_square_cofactor_side_bound (p q e a : ℕ) (hp : Nat.Prime p) (hq : Nat.Prime q) (hpq : p ≠ q) (h : q ^ 2 * p ^ a ≤ q * p ^ e) : a + Nat.log p q + 1 ≤ e := by have hc : q * p ^ a ≤ p ^ e := by nlinarith [hq.pos] have hh : p ^ (Nat.log p q + a) < p ^ e := by rw [pow_add] exact (Nat.mul_lt_mul_of_pos_right (mondrian_prime_log_gap p q hp hq hpq).1 (pow_pos hp.pos a)).trans_le hc have := (Nat.pow_lt_pow_iff_right hp.one_lt).mp hh omega