AFTD Auto-Formalizing Theoretical Domains

op_940_dim2_property_p_constant_ratio

theoremverifiedformalization

For N = 2 and any normalized recurrence coefficients a, b, c : Fin 3 → ℝ with log-concave Newton profile, if the ratio sequence is constant (r_1 = r_2), then property (P) holds.

Statement

theorem op_940_dim2_property_p_constant_ratio
    (a b c : Fin 3 → ℝ)
    (hrec : is_normalized_recurrence 2 a b c)
    (hlog : is_log_concave_newton 2 (recurrence_profile 2 b c))
    (hconst : recurrence_ratio 2 b c ⟨1, by decide⟩ = recurrence_ratio 2 b c ⟨2, by decide⟩) :
    has_property_p 2 a b c
Formalizes
arXiv:2611.01561 Thm 3.1
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • is_normalized_recurrenceFor N : ℕ and a, b, c : Fin (N + 1) → ℝ, the recurrence is normalized if a 0 = 1, b 0 = 0, c 0 = 0, a N = 0, a i + b i + c i = 1 for all i…
  • is_log_concave_newtonFor N : ℕ and d : Fin (N + 1) → ℝ, the profile has log-concave Newton coefficients if newton_coeff N d k ≥ 0 for all 1 ≤ k ≤ N and…
  • recurrence_profileFor N : ℕ, b, c : Fin (N + 1) → ℝ, and i : Fin (N + 1), the profile is b i + c i.
  • recurrence_ratioFor N : ℕ, b, c : Fin (N + 1) → ℝ, and i : Fin (N + 1), the ratio is c i / (b i + c i).
  • has_property_pFor N : ℕ and a, b, c : Fin (N + 1) → ℝ, property (P) holds if linearization_coeff N a b c m n k ≥ 0 for all m, n, k : Fin (N + 1).
  • newton_coeffFor N : ℕ, d : Fin (N + 1) → ℝ, and k : ℕ, the k-th Newton coefficient is the sum over i from 0 to k of (-1)^(k - i) * (k choose i) * d(i)…
  • op_940_dim2_property_p_of_ratio_conditionFor N = 2 and any normalized recurrence coefficients a, b, c : Fin 3 → ℝ, property (P) holds whenever the profile at 1 multiplied by (1 +…

Read back from the Lean

For any sequences of coefficients $a, b, c : \mathrm{Fin}\ 3 \to \mathbb{R}$, assume: 1. $(a, b, c)$ is a normalized recurrence for $N = 2$: - $a_0 = 1$, $b_0 = 0$, $c_0 = 0$, and $a_2 = 0$, - for all $i \in \{0, 1, 2\}$, $a_i + b_i + c_i = 1$, - $a_i > 0$ for $i < 2$ (i.e. $a_0 > 0$ and $a_1 > 0$), - $c_i > 0$ for $i > 0$ (i.e. $c_1 > 0$ and $c_2 > 0$), - $b_i \ge 0$ for all $i \in \{0, 1, 2\}$. 2. The recurrence profile $d_i = b_i + c_i$ is Newton log-concave for $N = 2$: - $\sum_{i=0}^k (-1)^{k-i} \binom{k}{i} (b_i + c_i) \ge 0$ for $k \in \{1, 2\}$, - and for all $k \in [2, 2)$ (vacuously), the squared Newton coefficient is at least the product of its adjacent Newton coefficients. 3. The recurrence ratio is constant at indices 1 and 2: $$\frac{c_1}{b_1 + c_1} = \frac{c_2}{b_2 + c_2}.$$ Then $(a, b, c)$ has Property P for $N = 2$: for all $m, n, k \in \{0, 1, 2\}$, the $(n, k)$-entry of the matrix $P_m(M)$ is nonnegative, where: - $M$ is the $3 \times 3$ tridiagonal matrix with main diagonal $(b_0, b_1, b_2)$, superdiagonal $(a_0, a_1)$, and subdiagonal $(c_1, c_2)$, - $P_m$ is the $m$-th orthogonal polynomial defined by $P_0 = 1$, $P_1(X) = X$, and $P_2(X) = \frac{1}{a_1} ((X - b_1) X - c_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 proof reduces the goal to verifying the dimension-2 ratio inequality $d_1(1 + r_1 r_2) + r_2(1 - r_2) \le 1$ via `op_940_dim2_property_p_of_ratio_condition`. The boundary values $d_0 = 0$ and $d_2 = 1$ are computed from the normalization hypotheses. Log-concavity of the Newton profile implies that the second finite difference $d_0 - 2 d_1 + d_2 = 1 - 2 d_1$ is non-negative, giving $d_1 \le 1/2$. Using the constant ratio hypothesis $r_1 = r_2$, the quantity $1 - [d_1(1 + r_1 r_2) + r_2(1 - r_2)]$ is rewritten as a sum of squares and non-negative factors $(1/2 - d_1)(1 + r_2^2) + \frac{1}{2}(1 - r_2)^2 \ge 0$, which completes the proof.

  1. The recurrence profile at index 0 is 0: $d_0 = 0$.

    After verifying the bounds on the indices in the hypothesis, we compute the profile at 0. By definition, the recurrence profile at 0 is $b_0 + c_0$. The normalization hypothesis `hrec` provides $b_0 = 0$ and $c_0 = 0$, so their sum is 0 by `add_zero`.

    lines 6–12

    uses add_zero

        (hconst : recurrence_ratio 2 b c ⟨1, by decide⟩ = recurrence_ratio 2 b c ⟨2, by decide⟩) :
        has_property_p 2 a b c := by
      have hprof_0 : recurrence_profile 2 b c ⟨0, by decide⟩ = 0 := by
        rcases hrec with ⟨ha0, hb0, hc0, ha2, hsum, ha_pos, hc_pos, hb_nonneg⟩
        dsimp [recurrence_profile]
        change b ⟨0, Nat.zero_lt_succ 2⟩ + c ⟨0, Nat.zero_lt_succ 2⟩ = 0
        rw [hb0, hc0, add_zero]
  2. The recurrence profile at index 2 is 1: $d_2 = 1$.

    By definition, the recurrence profile at 2 is $b_2 + c_2$. The normalization condition guarantees $a_2 + b_2 + c_2 = 1$, and since $a_2 = 0$, linear arithmetic shows that $b_2 + c_2 = 1$.

    lines 13–19

      have hprof_2 : recurrence_profile 2 b c ⟨2, by decide⟩ = 1 := by
        rcases hrec with ⟨ha0, hb0, hc0, ha2, hsum, ha_pos, hc_pos, hb_nonneg⟩
        dsimp [recurrence_profile]
        change b ⟨2, Nat.lt_succ_self 2⟩ + c ⟨2, Nat.lt_succ_self 2⟩ = 1
        have hs := hsum ⟨2, Nat.lt_succ_self 2⟩
        rw [ha2] at hs
        linarith
  3. The second Newton coefficient of the recurrence profile is given by $d_0 - 2 d_1 + d_2$.

    Unfolding the definition of `newton_coeff` at $k = 2$ gives the sum $\sum_{i=0}^2 (-1)^{2-i} \binom{2}{i} d_i$. Expanding the sum over the range with `Finset.sum_range_succ` and `Finset.sum_range_zero`, simplifying, and rearranging terms with ring arithmetic yields $d_0 - 2 d_1 + d_2$.

    lines 20–26

    uses Finset.sum_range_succ, Finset.sum_range_zero

      have hnewton : newton_coeff 2 (recurrence_profile 2 b c) 2 =
          recurrence_profile 2 b c ⟨0, by decide⟩ - 2 * recurrence_profile 2 b c ⟨1, by decide⟩ +
            recurrence_profile 2 b c ⟨2, by decide⟩ := by
        dsimp [newton_coeff]
        rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]
        simp
        ring
  4. The second Newton coefficient is non-negative: $\mathrm{newton\_coeff}(2, d, 2) \ge 0$.

    The log-concavity assumption `hlog` asserts that all Newton coefficients for indices $k \in \{1, 2\}$ are non-negative. In particular, since $2 \in [1, 2]$, the coefficient at $k = 2$ is non-negative.

    lines 27–29

      have hlog2 : 0 ≤ newton_coeff 2 (recurrence_profile 2 b c) 2 := by
        have h2 : (2 : ℕ) ∈ Finset.Icc 1 2 := by simp
        exact hlog.1 2 h2
  5. The recurrence profile at index 1 is at most $1/2$: $d_1 \le 1/2$.

    Substituting the explicit expansion $d_0 - 2 d_1 + d_2$ and the boundary values $d_0 = 0$ and $d_2 = 1$ into $0 \le \mathrm{newton\_coeff}(2, d, 2)$ yields $0 \le 1 - 2 d_1$, from which linear arithmetic concludes $d_1 \le 1/2$.

    lines 30–32

      have hprof_1_le : recurrence_profile 2 b c ⟨1, by decide⟩ ≤ 1 / 2 := by
        rw [hnewton, hprof_0, hprof_2] at hlog2
        linarith
  6. The key ratio inequality $d_1(1 + r_1 r_2) + r_2(1 - r_2) \le 1$ holds.

    Letting $r_1, r_2$ be the recurrence ratios and $d_1$ the profile value at 1, the assumption of constant ratios gives $r_1 = r_2$. Algebraic rearrangement shows that $1 - [d_1(1 + r_2^2) + r_2(1 - r_2)] = (1/2 - d_1)(1 + r_2^2) + \frac{1}{2}(1 - r_2)^2$. Both terms in this sum are non-negative: the first because $d_1 \le 1/2$ and $1 + r_2^2 \ge 0$ (using `mul_nonneg`), and the second because it is a square scaled by $1/2$. Hence the difference is non-negative, establishing the inequality.

    lines 33–48

    uses mul_nonneg

      set r1 := recurrence_ratio 2 b c ⟨1, by decide⟩
      set r2 := recurrence_ratio 2 b c ⟨2, by decide⟩
      set d1 := recurrence_profile 2 b c ⟨1, by decide⟩
      have hineq : d1 * (1 + r1 * r2) + r2 * (1 - r2) ≤ 1 := by
        have hr1 : r1 = r2 := hconst
        rw [hr1]
        have hid : 1 - (d1 * (1 + r2 * r2) + r2 * (1 - r2)) =
            (1/2 - d1) * (1 + r2 * r2) + (1/2) * (1 - r2)^2 := by ring
        have h1 : 0 ≤ (1/2 - d1) * (1 + r2 * r2) := by
          apply mul_nonneg
          · linarith
          · have : 1 + r2 * r2 = 1 + r2^2 := by ring
            rw [this]
            positivity
        have h2 : 0 ≤ (1/2 : ℝ) * (1 - r2)^2 := by positivity
        linarith
  7. Property (P) holds for $(a, b, c)$ in dimension $N = 2$.

    Applying the reduction theorem `op_940_dim2_property_p_of_ratio_condition` to the normalized recurrence coefficients and the verified ratio inequality yields property (P).

    line 49

    uses op_940_dim2_property_p_of_ratio_condition

      exact op_940_dim2_property_p_of_ratio_condition a b c hrec hineq
add_zero
Adding zero to an element leaves it unchanged ($a + 0 = a$).
Finset.sum_range_succ
The sum of a function over the range of size $n + 1$ equals the sum over the range of size $n$ plus the term at index $n$.
Finset.sum_range_zero
The sum of a function over an empty range of indices (size 0) is zero.
mul_nonneg
The product of two non-negative numbers is non-negative.
op_940_dim2_property_p_of_ratio_condition
For a normalized recurrence in dimension 2, if the profile and ratio sequences satisfy $d_1(1 + r_1 r_2) + r_2(1 - r_2) \le 1$, then property (P) holds.

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

/-- Baseline property (P) for constant ratios in dimension N = 2. -/theorem op_940_dim2_property_p_constant_ratio    (a b c : Fin 3 → ℝ)    (hrec : is_normalized_recurrence 2 a b c)    (hlog : is_log_concave_newton 2 (recurrence_profile 2 b c))    (hconst : recurrence_ratio 2 b c ⟨1, by decide⟩ = recurrence_ratio 2 b c ⟨2, by decide⟩) :    has_property_p 2 a b c := by  have hprof_0 : recurrence_profile 2 b c ⟨0, by decide⟩ = 0 := by    rcases hrec with ⟨ha0, hb0, hc0, ha2, hsum, ha_pos, hc_pos, hb_nonneg⟩    dsimp [recurrence_profile]    change b ⟨0, Nat.zero_lt_succ 2⟩ + c ⟨0, Nat.zero_lt_succ 2⟩ = 0    rw [hb0, hc0, add_zero]  have hprof_2 : recurrence_profile 2 b c ⟨2, by decide⟩ = 1 := by    rcases hrec with ⟨ha0, hb0, hc0, ha2, hsum, ha_pos, hc_pos, hb_nonneg⟩    dsimp [recurrence_profile]    change b ⟨2, Nat.lt_succ_self 2⟩ + c ⟨2, Nat.lt_succ_self 2⟩ = 1    have hs := hsum ⟨2, Nat.lt_succ_self 2⟩    rw [ha2] at hs    linarith  have hnewton : newton_coeff 2 (recurrence_profile 2 b c) 2 =      recurrence_profile 2 b c ⟨0, by decide⟩ - 2 * recurrence_profile 2 b c ⟨1, by decide⟩ +        recurrence_profile 2 b c ⟨2, by decide⟩ := by    dsimp [newton_coeff]    rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]    simp    ring  have hlog2 : 0 ≤ newton_coeff 2 (recurrence_profile 2 b c) 2 := by    have h2 : (2 : ℕ) ∈ Finset.Icc 1 2 := by simp    exact hlog.1 2 h2  have hprof_1_le : recurrence_profile 2 b c ⟨1, by decide⟩ ≤ 1 / 2 := by    rw [hnewton, hprof_0, hprof_2] at hlog2    linarith  set r1 := recurrence_ratio 2 b c ⟨1, by decide⟩  set r2 := recurrence_ratio 2 b c ⟨2, by decide⟩  set d1 := recurrence_profile 2 b c ⟨1, by decide⟩  have hineq : d1 * (1 + r1 * r2) + r2 * (1 - r2) ≤ 1 := by    have hr1 : r1 = r2 := hconst    rw [hr1]    have hid : 1 - (d1 * (1 + r2 * r2) + r2 * (1 - r2)) =        (1/2 - d1) * (1 + r2 * r2) + (1/2) * (1 - r2)^2 := by ring    have h1 : 0 ≤ (1/2 - d1) * (1 + r2 * r2) := by      apply mul_nonneg      · linarith      · have : 1 + r2 * r2 = 1 + r2^2 := by ring        rw [this]        positivity    have h2 : 0 ≤ (1/2 : ℝ) * (1 - r2)^2 := by positivity    linarith  exact op_940_dim2_property_p_of_ratio_condition a b c hrec hineq
See it in the graphDiscuss this resultChallenge it