AFTD Auto-Formalizing Theoretical Domains

op_1721_eventual_log_concavity_failure

theoremverified

For every real p strictly between 0 and 1, let q = 1 - p, r(d) = Nat.ceil (d / q^d), u(d) = q^(2d), b(d, j) = (r(d).choose j : ℝ) * u(d)^j * (1 - u(d))^(r(d) - j) * q^j + (r(d).choose (j + 1) : ℝ) * u(d)^(j + 1) * (1 - u(d))^(r(d) - (j + 1)) * (1 - q^(j + 1)), and ratio(d) = (b(d, d))^2 / (b(d, d - 1) * b(d, d + 1)). If ratio(d) tends to 4 * q / (1 + q)^2 as d tends to infinity, then there exists d0 such that for all d >= d0, ratio(d) < 1, failing log-concavity.

Statement

theorem op_1721_eventual_log_concavity_failure (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) :
    let q := 1 - p
    let r (d : ℕ) := Nat.ceil ((d : ℝ) / q ^ d)
    let u (d : ℕ) := q ^ (2 * d)
    let b (d : ℕ) (j : ℕ) :=
      (r d).choose j * u d ^ j * (1 - u d) ^ (r d - j) * q ^ j +
        (r d).choose (j + 1) * u d ^ (j + 1) * (1 - u d) ^ (r d - (j + 1)) * (1 - q ^ (j + 1))
    let ratio (d : ℕ) := (b d d) ^ 2 / (b d (d - 1) * b d (d + 1))
    Filter.Tendsto ratio Filter.atTop (nhds (4 * q / (1 + q) ^ 2)) →
      ∃ d₀ : ℕ, ∀ d ≥ d₀, ratio d < 1
Source
arXiv:2106.02330, OP-1721
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For every real number $p$ satisfying $0 < p < 1$, define: - $q = 1 - p$, - $r(d) = \lceil d / q^d \rceil$ for $d \in \mathbb{N}$, - $u(d) = q^{2d}$ for $d \in \mathbb{N}$, - $b(d, j) = \binom{r(d)}{j} (u(d))^j (1 - u(d))^{r(d) - j} q^j + \binom{r(d)}{j+1} (u(d))^{j+1} (1 - u(d))^{r(d) - (j+1)} (1 - q^{j+1})$ for $d, j \in \mathbb{N}$, - $\text{ratio}(d) = \frac{(b(d, d))^2}{b(d, d-1) \cdot b(d, d+1)}$ for $d \in \mathbb{N}$. If $\text{ratio}(d)$ tends to $\frac{4q}{(1+q)^2}$ as $d \to \infty$ (along Filter.atTop), then there exists $d_0 \in \mathbb{N}$ such that for all $d \ge d_0$, $\text{ratio}(d) < 1$.

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 argument is purely topological and algebraic. From p ∈ (0, 1), we have q = 1 - p ∈ (0, 1), which implies (1 - q)² > 0 and hence 4q / (1 + q)² < 1. Because ratio(d) converges to this limit value strictly less than 1, standard properties of limits in ordered spaces ensure that ratio(d) is eventually strictly less than 1, establishing the eventual failure of log-concavity.

  1. Introduce the defined quantities q, r, u, b, ratio and the convergence hypothesis h.

    We introduce the let-bound definitions and the assumption that ratio(d) converges to 4q/(1+q)² as d → ∞ into the local context.

    line 12

      intro q r u b ratio h
  2. 0 < q

    Since q = 1 - p and p < 1, linear arithmetic over ℝ shows that 0 < 1 - p, so q is strictly positive.

    lines 13–15

      have hq0 : 0 < q := by
        show 0 < 1 - p
        linarith
  3. q < 1

    Since q = 1 - p and p > 0, linear arithmetic over ℝ shows that 1 - p < 1, so q is strictly less than 1.

    lines 16–18

      have hq1 : q < 1 := by
        show 1 - p < 1
        linarith
  4. 4q / (1 + q)² < 1

    Because (1 + q)² > 0, clearing the denominator via div_lt_one reduces the inequality to 4q < (1 + q)². This is equivalent to (1 - q)² > 0, which holds by non-linear arithmetic because q < 1 implies 1 - q ≠ 0.

    lines 19–21

    uses div_lt_one, sq_pos_of_ne_zero, ne_of_gt

      have hlt : 4 * q / (1 + q) ^ 2 < 1 := by
        rw [div_lt_one (by positivity)]
        nlinarith [sq_pos_of_ne_zero (ne_of_gt hq0), hq1]
  5. ratio(d) < 1 holds eventually along Filter.atTop.

    Because ratio(d) converges to a limit strictly less than 1 in an ordered space, tendsto_order.1 implies that ratio(d) is eventually strictly less than 1.

    line 22

    uses tendsto_order.1

      have hev := (tendsto_order.1 h).2 1 hlt
  6. There exists d₀ such that ratio(d) < 1 for all d ≥ d₀.

    Rewriting with Filter.eventually_atTop translates the filter statement that ratio(d) < 1 eventually into the explicit existential threshold claim ∃ d₀, ∀ d ≥ d₀, ratio d < 1, completing the proof.

    line 23

    uses Filter.eventually_atTop

      rwa [Filter.eventually_atTop] at hev
div_lt_one
For a positive denominator b > 0, the quotient a / b < 1 if and only if a < b.
sq_pos_of_ne_zero
The square of any non-zero element in an ordered ring is strictly positive.
ne_of_gt
If a > b, then a ≠ b.
tendsto_order.1
If a function converges to a limit L in an ordered topological space, then for any a' > L it is eventually strictly less than a'.
Filter.eventually_atTop
A property holds eventually along Filter.atTop if and only if it holds for all elements greater than or equal to some threshold.

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

/-- Convergence to 4q/(1+q)^2 implies eventual failure of matching-number log-concavity -/theorem op_1721_eventual_log_concavity_failure (p : ℝ) (hp0 : 0 < p) (hp1 : p < 1) :    let q := 1 - p    let r (d : ℕ) := Nat.ceil ((d : ℝ) / q ^ d)    let u (d : ℕ) := q ^ (2 * d)    let b (d : ℕ) (j : ℕ) :=      (r d).choose j * u d ^ j * (1 - u d) ^ (r d - j) * q ^ j +        (r d).choose (j + 1) * u d ^ (j + 1) * (1 - u d) ^ (r d - (j + 1)) * (1 - q ^ (j + 1))    let ratio (d : ℕ) := (b d d) ^ 2 / (b d (d - 1) * b d (d + 1))    Filter.Tendsto ratio Filter.atTop (nhds (4 * q / (1 + q) ^ 2)) →      ∃ d₀ : ℕ, ∀ d ≥ d₀, ratio d < 1 := by  intro q r u b ratio h  have hq0 : 0 < q := by    show 0 < 1 - p    linarith  have hq1 : q < 1 := by    show 1 - p < 1    linarith  have hlt : 4 * q / (1 + q) ^ 2 < 1 := by    rw [div_lt_one (by positivity)]    nlinarith [sq_pos_of_ne_zero (ne_of_gt hq0), hq1]  have hev := (tendsto_order.1 h).2 1 hlt  rwa [Filter.eventually_atTop] at hev
See it in the graphDiscuss this resultChallenge it