AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_square_cofactor_side_bound

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  1. 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.

    line 4

      have hc : q * p ^ a ≤ p ^ e := by nlinarith [hq.pos]
  2. 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.

    lines 5–8

    uses pow_add, Nat.mul_lt_mul_of_pos_right, mondrian_prime_log_gap, pow_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
  3. 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.

    lines 9–10

    uses Nat.pow_lt_pow_iff_right

      have := (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

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
See it in the graphDiscuss this resultChallenge it