AFTD Auto-Formalizing Theoretical Domains

petrial_R_log_concavity_growth_ineq

theoremverified

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

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.

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

    lines 4–5

      have hfac : ∀ k : ℕ, 441 * k ^ 2 + 525 * k + 24 = (21 * k + 1) * (21 * k + 24) := by
        intro k; ring
  2. 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`).

    lines 6–10

    uses sq_nonneg

      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]
  3. 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}$.

    lines 11–29

    uses Nat.le_induction, pow_succ, Nat.mul_le_mul_right, Nat.mul_le_mul_left

      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
  4. $9180 \cdot 16 < 16 \cdot 11^4$.

    Direct numerical inequality: $9180 < 11^4 = 14641$, so $146880 < 234256$, verified by computation (`norm_num`).

    line 30

      have hconst : 9180 * 16 < 16 * 11 ^ 4 := by norm_num
  5. $(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`.

    lines 31–34

    uses Nat.mul_lt_mul_of_pos_right, pow_pos

      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)
  6. $(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.

    lines 35–36

    uses Nat.lt_of_mul_lt_mul_right

      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
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$

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

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