AFTD Auto-Formalizing Theoretical Domains

mondrian_prime_pow_gap

theoremverified

For p at least two, c less than p, and r at least two, c * (r + 1) is less than p to the r.

Statement

theorem mondrian_prime_pow_gap (c p r : ℕ) (hp : 2 ≤ p) (hpc : c < p)
    (hr : 2 ≤ r) : (r + 1) * c < p ^ r
Source
Helper for OP-280 and mondrian_perfect_partition_large_prime_iff. Related work: arXiv:2610.19193, Section 1 (perfect partitions and scaling); arXiv:2007.09639, Theorem 4.1 (available shapes and prime-power exclusions).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1
  • mondrian_large_prime_count_not_dvdIf enough distinct shapes of a common area fit in a c times p to the e square to account for its area, a prime p greater than c cannot…

The proof, explained

We reparametrize r ≥ 2 as r = j + 2 for j ∈ ℕ, reducing the goal to showing (j + 3) * c < p ^ (j + 2) by induction on j. The base case j = 0 simplifies to 3 * c < p ^ 2, which holds by checking c ∈ {0, 1} when p = 2, and using 3 * c < 3 * p ≤ p ^ 2 when p ≥ 3. In the induction step, the bound (j + 4) * c ≤ 2 * (j + 3) * c ≤ p * ((j + 3) * c) combines with the induction hypothesis scaled by p to complete the proof.

  1. The inequality (r + 1) * c < p ^ r reduces to showing that (j + 3) * c < p ^ (j + 2) for all j ∈ ℕ.

    Since r ≥ 2, we can write r = 2 + j for some j ∈ ℕ using Nat.exists_eq_add_of_le. Substituting this into (r + 1) * c and p ^ r and rearranging addition transforms the original inequality into (j + 3) * c < p ^ (j + 2).

    lines 3–5

    uses Nat.exists_eq_add_of_le, Nat.add_comm, Nat.add_left_comm, Nat.add_assoc

      suffices h : ∀ j : ℕ, (j + 3) * c < p ^ (j + 2) by
        obtain ⟨j, rfl⟩ := Nat.exists_eq_add_of_le hr
        simpa [Nat.add_comm, Nat.add_left_comm, Nat.add_assoc] using h j
  2. We set up an induction on j to establish (j + 3) * c < p ^ (j + 2) for all j ∈ ℕ.

    We introduce the variable j and proceed by mathematical induction on j.

    lines 6–7

      intro j
      induction j with
  3. For the base case j = 0, the inequality 3 * c < p ^ 2 holds.

    When j = 0, the claim simplifies to 3 * c < p * p using Nat.zero_add and pow_two. We split into two cases: if p = 2, then c < 2 forces c to be 0 or 1, and in both cases 3 * c < 4 holds by computation. If p ≠ 2, then 3 ≤ p since p ≥ 2; multiplying by p via Nat.mul_le_mul_right yields 3 * p ≤ p * p, and since c < p, linear arithmetic gives 3 * c < 3 * p ≤ p * p.

    lines 8–15

    uses Nat.zero_add, pow_two, Nat.mul_le_mul_right

      | zero =>
        simp only [Nat.zero_add, pow_two]
        by_cases hp2 : p = 2
        · subst p
          interval_cases c <;> norm_num
        · have hp3 : 3 ≤ p := by omega
          have hm := Nat.mul_le_mul_right p hp3
          omega
  4. In the induction step, (j + 4) * c ≤ p * ((j + 3) * c).

    Because 2 ≤ p, multiplying on the right by (j + 3) * c yields 2 * ((j + 3) * c) ≤ p * ((j + 3) * c) using Nat.mul_le_mul_right. Nonlinear arithmetic then deduces (j + 4) * c ≤ p * ((j + 3) * c), relying on the fact that j + 4 ≤ 2 * (j + 3) = 2 * j + 6 for any natural number j.

    lines 16–19

    uses Nat.mul_le_mul_right

      | succ j ih =>
        have hle : (j + 4) * c ≤ p * ((j + 3) * c) := by
          have hm := Nat.mul_le_mul_right ((j + 3) * c) hp
          nlinarith
  5. The induction step is completed: (j + 1 + 3) * c < p ^ (j + 1 + 2).

    We chain three steps: (j + 1 + 3) * c = (j + 4) * c ≤ p * ((j + 3) * c) by the previous inequality, which is strictly less than p * p ^ (j + 2) by multiplying the induction hypothesis by p > 0 using Nat.mul_lt_mul_of_pos_left, which in turn equals p ^ (j + 1 + 2) by pow_succ and Nat.mul_comm.

    lines 20–23

    uses Nat.add_assoc, Nat.mul_lt_mul_of_pos_left, Nat.mul_comm, pow_succ

        calc
          (j + 1 + 3) * c ≤ p * ((j + 3) * c) := by simpa [Nat.add_assoc] using hle
          _ < p * p ^ (j + 2) := Nat.mul_lt_mul_of_pos_left ih (by omega)
          _ = p ^ (j + 1 + 2) := by simpa only [Nat.mul_comm] using (pow_succ p (j + 2)).symm
Nat.exists_eq_add_of_le
If m ≤ n for natural numbers, then n = m + k for some natural number k.
Nat.add_comm
Addition of natural numbers is commutative: n + m = m + n.
Nat.add_left_comm
In a sum of natural numbers, the first two terms can be swapped: n + (m + k) = m + (n + k).
Nat.add_assoc
Addition of natural numbers is associative: n + m + k = n + (m + k).
Nat.zero_add
Adding zero on the left leaves a natural number unchanged: 0 + n = n.
pow_two
The square of an element in a monoid equals the element multiplied by itself: a ^ 2 = a * a.
Nat.mul_le_mul_right
If n ≤ m, then multiplying on the right by k preserves the inequality: n * k ≤ m * k.
Nat.mul_lt_mul_of_pos_left
If n < m and k > 0, then multiplying on the left by k preserves the strict inequality: k * n < k * m.
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
pow_succ
In a monoid, the (n + 1)-th power equals the n-th power multiplied by the base: a ^ (n + 1) = a ^ n * a.

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_pow_gap (c p r : ℕ) (hp : 2 ≤ p) (hpc : c < p)    (hr : 2 ≤ r) : (r + 1) * c < p ^ r := by  suffices h : ∀ j : ℕ, (j + 3) * c < p ^ (j + 2) by    obtain ⟨j, rfl⟩ := Nat.exists_eq_add_of_le hr    simpa [Nat.add_comm, Nat.add_left_comm, Nat.add_assoc] using h j  intro j  induction j with  | zero =>    simp only [Nat.zero_add, pow_two]    by_cases hp2 : p = 2    · subst p      interval_cases c <;> norm_num    · have hp3 : 3 ≤ p := by omega      have hm := Nat.mul_le_mul_right p hp3      omega  | succ j ih =>    have hle : (j + 4) * c ≤ p * ((j + 3) * c) := by      have hm := Nat.mul_le_mul_right ((j + 3) * c) hp      nlinarith    calc      (j + 1 + 3) * c ≤ p * ((j + 3) * c) := by simpa [Nat.add_assoc] using hle      _ < p * p ^ (j + 2) := Nat.mul_lt_mul_of_pos_left ih (by omega)      _ = p ^ (j + 1 + 2) := by simpa only [Nat.mul_comm] using (pow_succ p (j + 2)).symm
See it in the graphDiscuss this resultChallenge it