petrial_R_log_concavity_growth_ineq
For every natural number m ≥ 4, (441 * m ^ 2 + 525 * m + 24) * 2 ^ m < 16 * 11 ^ m.
Statement
theorem petrial_R_log_concavity_growth_ineq (m : ℕ) (hm : 4 ≤ m) :
(441 * m ^ 2 + 525 * m + 24) * 2 ^ m < 16 * 11 ^ m- Source
- arXiv:2611.07503 Theorem 8
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
Read back from the Lean
For every natural number $m$, if $m \ge 4$, then $(441 m^2 + 525 m + 24) \cdot 2^m < 16 \cdot 11^m$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The inequality is proved by induction on $m \ge 4$ after scaling both sides by $11^4$ to work with integers. Factoring the quadratic as $(21k+1)(21k+24)$ allows one to bound the ratio between successive terms times 2 by 11. An inductive chain then bounds the scaled expression by $9180 \cdot 16 \cdot 11^m < 16 \cdot 11^4 \cdot 11^m$, from which cancelling the factor $11^4$ concludes the proof.
For all $k \in \mathbb{N}$, $441 k^2 + 525 k + 24 = (21k + 1)(21k + 24)$.
The quadratic polynomial factors into the product of two linear terms, as verified by polynomial expansion (`ring`).
have hfac : ∀ k : ℕ, 441 * k ^ 2 + 525 * k + 24 = (21 * k + 1) * (21 * k + 24) := by intro k; ring
For all $k \ge 1$, $2(21(k+1) + 1)(21(k+1) + 24) \le 11(21k + 1)(21k + 24)$.
This bounds the growth ratio of consecutive polynomial terms times $2$ by $11$. Expanding the difference yields $3969 k^2 + 2961 k - 1716$, which is non-negative for all integers $k \ge 1$ using $k^2 \ge 0$ (`sq_nonneg`), verified by non-linear arithmetic (`nlinarith`).
uses
sq_nonneghave hstep : ∀ k : ℕ, 1 ≤ k → 2 * ((21 * (k + 1) + 1) * (21 * (k + 1) + 24)) ≤ 11 * ((21 * k + 1) * (21 * k + 24)) := by intro k hk nlinarith [sq_nonneg (k:ℤ), hk]
For all $k \ge 4$, $(441 k^2 + 525 k + 24) \cdot 2^k \cdot 11^4 \le 9180 \cdot 16 \cdot 11^k$.
Proved by induction on $k \ge 4$ (`Nat.le_induction`). The base case $k = 4$ holds with equality, since $441(4)^2 + 525(4) + 24 = 9180$ and $2^4 = 16$, confirmed by evaluation (`norm_num`). In the inductive step from $n$ to $n+1$, factoring via `hfac` and expanding $2^{n+1} = 2^n \cdot 2$ (`pow_succ`) yields a factor of $2(21(n+1)+1)(21(n+1)+24)$, which is bounded by $11(21n+1)(21n+24)$ using the previous step (`Nat.mul_le_mul_right`). Then the induction hypothesis bounds $(21n+1)(21n+24) \cdot 2^n \cdot 11^4$ by $9180 \cdot 16 \cdot 11^n$ (`Nat.mul_le_mul_left`), which rearranges to $9180 \cdot 16 \cdot 11^{n+1}$.
uses
Nat.le_induction,pow_succ,Nat.mul_le_mul_right,Nat.mul_le_mul_lefthave key : ∀ k : ℕ, 4 ≤ k → (441 * k ^ 2 + 525 * k + 24) * 2 ^ k * 11 ^ 4 ≤ 9180 * 16 * 11 ^ k := by intro k hk refine Nat.le_induction ?base ?step k hk · norm_num · intro n hn ih rw [hfac n] at ih rw [hfac (n+1)] rw [pow_succ, pow_succ] have hs : 2 * ((21 * (n + 1) + 1) * (21 * (n + 1) + 24)) ≤ 11 * ((21 * n + 1) * (21 * n + 24)) := hstep n (by omega) calc (21 * (n + 1) + 1) * (21 * (n + 1) + 24) * (2 ^ n * 2) * 11 ^ 4 = (2 * ((21 * (n + 1) + 1) * (21 * (n + 1) + 24))) * (2 ^ n * 11 ^ 4) := by ring _ ≤ (11 * ((21 * n + 1) * (21 * n + 24))) * (2 ^ n * 11 ^ 4) := by exact Nat.mul_le_mul_right _ hs _ = 11 * ((21 * n + 1) * (21 * n + 24) * 2 ^ n * 11 ^ 4) := by ring _ ≤ 11 * (9180 * 16 * 11 ^ n) := by exact Nat.mul_le_mul_left 11 ih _ = 9180 * 16 * (11 ^ n * 11) := by ring
$9180 \cdot 16 < 16 \cdot 11^4$.
Direct numerical inequality: $9180 < 11^4 = 14641$, so $146880 < 234256$, verified by computation (`norm_num`).
have hconst : 9180 * 16 < 16 * 11 ^ 4 := by norm_num
$(441 m^2 + 525 m + 24) \cdot 2^m \cdot 11^4 < (16 \cdot 11^4) \cdot 11^m$.
Chaining the induction bound for $m \ge 4$ with the strict inequality $9180 \cdot 16 < 16 \cdot 11^4$ multiplied on the right by $11^m > 0$ (`pow_pos`) via `Nat.mul_lt_mul_of_pos_right`.
uses
Nat.mul_lt_mul_of_pos_right,pow_poshave h1 : (441 * m ^ 2 + 525 * m + 24) * 2 ^ m * 11 ^ 4 < (16 * 11 ^ 4) * 11 ^ m := by calc (441 * m ^ 2 + 525 * m + 24) * 2 ^ m * 11 ^ 4 ≤ 9180 * 16 * 11 ^ m := key m hm _ < (16 * 11 ^ 4) * 11 ^ m := Nat.mul_lt_mul_of_pos_right hconst (pow_pos (by norm_num) m)
$(441 m^2 + 525 m + 24) \cdot 2^m < 16 \cdot 11^m$.
After commuting factors so the right-hand side is $(16 \cdot 11^m) \cdot 11^4$, cancelling the common positive factor $11^4$ (`Nat.lt_of_mul_lt_mul_right`) yields the desired inequality.
uses
Nat.lt_of_mul_lt_mul_rightrw [show (16 * 11 ^ 4) * 11 ^ m = (16 * 11 ^ m) * 11 ^ 4 by ring] at h1 exact Nat.lt_of_mul_lt_mul_right h1
sq_nonneg- the square of any element in an ordered semiring is non-negative ($a^2 \ge 0$)
Nat.le_induction- mathematical induction on natural numbers starting from a base value: if $P(m)$ holds and $P(n) \implies P(n+1)$ for all $n \ge m$, then $P(n)$ holds for all $n \ge m$
pow_succ- successor power identity for monoids: $a^{n+1} = a^n \cdot a$
Nat.mul_le_mul_right- multiplication on the right by a natural number preserves non-strict inequality: if $n \le m$, then $n \cdot k \le m \cdot k$
Nat.mul_le_mul_left- multiplication on the left by a natural number preserves non-strict inequality: if $n \le m$, then $k \cdot n \le k \cdot m$
Nat.mul_lt_mul_of_pos_right- multiplying a strict inequality of natural numbers on the right by a strictly positive number preserves strict inequality: if $n < m$ and $k > 0$, then $n \cdot k < m \cdot k$
pow_pos- powers of a strictly positive element are strictly positive: if $a > 0$, then $a^n > 0$ for all $n$
Nat.lt_of_mul_lt_mul_right- cancellation of a right factor in a strict inequality of natural numbers: if $b \cdot a < c \cdot a$, then $b < c$
- To avoid fractions and remain entirely within natural number arithmetic, the induction hypothesis in `key` is scaled by $11^4$.
- The step inequality `hstep` is proved by `nlinarith` after casting $k$ to $\mathbb{Z}$ to establish the non-negativity of the quadratic difference.
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.
/-- The growth inequality (441 * m^2 + 525 * m + 24) * 2^m < 16 * 11^m for m >= 4 used in the proof of Theorem 8. -/theorem petrial_R_log_concavity_growth_ineq (m : ℕ) (hm : 4 ≤ m) : (441 * m ^ 2 + 525 * m + 24) * 2 ^ m < 16 * 11 ^ m := by have hfac : ∀ k : ℕ, 441 * k ^ 2 + 525 * k + 24 = (21 * k + 1) * (21 * k + 24) := by intro k; ring have hstep : ∀ k : ℕ, 1 ≤ k → 2 * ((21 * (k + 1) + 1) * (21 * (k + 1) + 24)) ≤ 11 * ((21 * k + 1) * (21 * k + 24)) := by intro k hk nlinarith [sq_nonneg (k:ℤ), hk] have key : ∀ k : ℕ, 4 ≤ k → (441 * k ^ 2 + 525 * k + 24) * 2 ^ k * 11 ^ 4 ≤ 9180 * 16 * 11 ^ k := by intro k hk refine Nat.le_induction ?base ?step k hk · norm_num · intro n hn ih rw [hfac n] at ih rw [hfac (n+1)] rw [pow_succ, pow_succ] have hs : 2 * ((21 * (n + 1) + 1) * (21 * (n + 1) + 24)) ≤ 11 * ((21 * n + 1) * (21 * n + 24)) := hstep n (by omega) calc (21 * (n + 1) + 1) * (21 * (n + 1) + 24) * (2 ^ n * 2) * 11 ^ 4 = (2 * ((21 * (n + 1) + 1) * (21 * (n + 1) + 24))) * (2 ^ n * 11 ^ 4) := by ring _ ≤ (11 * ((21 * n + 1) * (21 * n + 24))) * (2 ^ n * 11 ^ 4) := by exact Nat.mul_le_mul_right _ hs _ = 11 * ((21 * n + 1) * (21 * n + 24) * 2 ^ n * 11 ^ 4) := by ring _ ≤ 11 * (9180 * 16 * 11 ^ n) := by exact Nat.mul_le_mul_left 11 ih _ = 9180 * 16 * (11 ^ n * 11) := by ring have hconst : 9180 * 16 < 16 * 11 ^ 4 := by norm_num have h1 : (441 * m ^ 2 + 525 * m + 24) * 2 ^ m * 11 ^ 4 < (16 * 11 ^ 4) * 11 ^ m := by calc (441 * m ^ 2 + 525 * m + 24) * 2 ^ m * 11 ^ 4 ≤ 9180 * 16 * 11 ^ m := key m hm _ < (16 * 11 ^ 4) * 11 ^ m := Nat.mul_lt_mul_of_pos_right hconst (pow_pos (by norm_num) m) rw [show (16 * 11 ^ 4) * 11 ^ m = (16 * 11 ^ m) * 11 ^ 4 by ring] at h1 exact Nat.lt_of_mul_lt_mul_right h1