mondrian_prime_pow_gap
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- 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.
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).
uses
Nat.exists_eq_add_of_le,Nat.add_comm,Nat.add_left_comm,Nat.add_assocsuffices 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
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.
intro j induction j with
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.
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 omegaIn 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.
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 nlinarithThe 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.
uses
Nat.add_assoc,Nat.mul_lt_mul_of_pos_left,Nat.mul_comm,pow_succcalc (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
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_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