AFTD Auto-Formalizing Theoretical Domains

op_940_decreasing_ratios_not_all_property_p

theoremverifiedformalization

It is not the case that for every N ≥ 2 and all normalized recurrence coefficients a, b, c : Fin (N + 1) → ℝ with log-concave Newton profile and ratio sequence recurrence_ratio N b c non-increasing on positive indices (meaning that for all i j : Fin (N + 1) with 0 < i.val and i.val ≤ j.val, recurrence_ratio N b c j ≤ recurrence_ratio N b c i), property (P) holds.

Statement

theorem op_940_decreasing_ratios_not_all_property_p :
  ¬ (∀ (N : ℕ) (hN : 2 ≤ N) (a b c : Fin (N + 1) → ℝ),
    is_normalized_recurrence N a b c →
    is_log_concave_newton N (recurrence_profile N b c) →
    (∀ (i j : Fin (N + 1)), 0 < i.val → i.val ≤ j.val →
      recurrence_ratio N b c j ≤ recurrence_ratio N b c i) →
    has_property_p N a b c)
Formalizes
arXiv:2611.01561 Sec. 6, Other ratios
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • 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)…
  • linearization_coeffFor N : ℕ, a, b, c : Fin (N + 1) → ℝ, and m, n, k : Fin (N + 1), the linearization coefficient is the (n, k) entry of the matrix…
  • recurrence_matrixFor N : ℕ and a, b, c : Fin (N + 1) → ℝ, the tridiagonal matrix of size (N + 1) × (N + 1) has (i, j) entry equal to a i when j.val = i.val…
  • recurrence_polyThe sequence of real polynomials R_n for n : ℕ associated with N : ℕ and a, b, c : Fin (N + 1) → ℝ is defined by R_0 = 1, R_1 = X, and for…

Read back from the Lean

The theorem asserts the negation of the following statement: for every natural number $N \ge 2$ and all sequences $a, b, c : \{0, \dots, N\} \to \mathbb{R}$, if 1. $(a, b, c)$ is a normalized recurrence, 2. the sequence $d_i = b_i + c_i$ is Newton log-concave, and 3. the recurrence ratio $r_i = c_i / (b_i + c_i)$ is weakly decreasing for $i \ge 1$ (i.e., for all $0 < i \le j \le N$, $r_j \le r_i$), then $(a, b, c)$ has Property P (meaning all linearization coefficients are non-negative). In other words, it asserts that there exists a counterexample: a normalized recurrence with $N \ge 2$ having a Newton log-concave profile $b + c$ and weakly decreasing ratios $c_i / (b_i + c_i)$ for $i \ge 1$, which does not satisfy Property P.

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 theorem refutes the conjecture that normalized recurrence coefficients with a log-concave Newton profile and non-increasing ratios must satisfy property (P). The proof works by constructing an explicit counterexample for N = 2 with a = (1, 1/2, 0), b = (0, 0, 1/4), and c = (0, 1/2, 3/4). After verifying that these coefficients satisfy normalization, Newton log-concavity, and decreasing ratios, direct matrix and polynomial computation shows that the linearization coefficient at (2, 2, 2) is -1/8 < 0, contradicting property (P).

  1. Assume for contradiction that the conjecture holds for all N ≥ 2 and all admissible recurrence coefficients.

    The proof proceeds by contradiction, introducing the universal hypothesis H that asserts property (P) holds whenever the recurrence coefficients are normalized, have a log-concave Newton profile, and have non-increasing ratios.

    line 23

      intro H
  2. The coefficient vectors a, b, and c form a normalized recurrence for N = 2.

    The definition of a normalized recurrence requires boundary values a(0) = 1, b(0) = c(0) = a(2) = 0, row sums a(i) + b(i) + c(i) = 1, strict positivity a(i) > 0 for i < 2 and c(i) > 0 for i > 0, and non-negativity b(i) ≥ 0. The boundary values hold by definition, and the remaining conditions are verified across all indices i ∈ {0, 1, 2} using exhaustive case analysis (`fin_cases`) and arithmetic evaluation (`norm_num`).

    lines 24–38

      have h_norm : is_normalized_recurrence 2 op_940_decreasing_ratios_not_all_property_p_a
          op_940_decreasing_ratios_not_all_property_p_b
          op_940_decreasing_ratios_not_all_property_p_c := by
        refine ⟨rfl, rfl, rfl, rfl, ?_, ?_, ?_, ?_⟩
        · intro i; fin_cases i <;> norm_num [op_940_decreasing_ratios_not_all_property_p_a,
            op_940_decreasing_ratios_not_all_property_p_b, op_940_decreasing_ratios_not_all_property_p_c]
        · intro i hi; fin_cases i
          · norm_num [op_940_decreasing_ratios_not_all_property_p_a]
          · norm_num [op_940_decreasing_ratios_not_all_property_p_a]
          · revert hi; norm_num
        · intro i hi; fin_cases i
          · revert hi; norm_num
          · norm_num [op_940_decreasing_ratios_not_all_property_p_c]
          · norm_num [op_940_decreasing_ratios_not_all_property_p_c]
        · intro i; fin_cases i <;> norm_num [op_940_decreasing_ratios_not_all_property_p_b]
  3. The recurrence profile b + c has a log-concave Newton profile for N = 2.

    Log-concavity of the Newton profile requires non-negativity of the Newton coefficients for k ∈ [1, 2] and the Newton log-concavity inequalities for k ∈ [2, 2). For k = 1 and k = 2, the defining sums are expanded and evaluated to 1/2 ≥ 0 and 0 ≥ 0 respectively. The index interval [2, 2) is empty, so the second condition holds vacuously, which is discharged by linear integer arithmetic (`omega`).

    lines 39–59

    uses Finset.mem_Icc, Finset.sum_range_succ, Finset.sum_range_zero, Finset.mem_Ico

      have h_log : is_log_concave_newton 2 (recurrence_profile 2 op_940_decreasing_ratios_not_all_property_p_b
          op_940_decreasing_ratios_not_all_property_p_c) := by
        dsimp [is_log_concave_newton]
        constructor
        · intro k hk
          rw [Finset.mem_Icc] at hk
          rcases hk with ⟨h1, h2⟩
          interval_cases k
          · dsimp [newton_coeff]
            rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]
            dsimp [recurrence_profile, op_940_decreasing_ratios_not_all_property_p_b,
              op_940_decreasing_ratios_not_all_property_p_c]
            norm_num
          · dsimp [newton_coeff]
            rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]
            dsimp [recurrence_profile, op_940_decreasing_ratios_not_all_property_p_b,
              op_940_decreasing_ratios_not_all_property_p_c]
            norm_num
        · intro k hk
          rw [Finset.mem_Ico] at hk
          omega
  4. The ratio sequence c(i) / (b(i) + c(i)) is non-increasing on positive indices.

    For positive indices in Fin 3, the ratio is 1 at index 1 and 3/4 at index 2. Exhaustive case analysis on i and j with 0 < i ≤ j checks all valid pairs (namely (1, 1), (1, 2), and (2, 2)) and verifies that the ratio at j is at most the ratio at i in every case.

    lines 60–76

      have h_ratio : ∀ (i j : Fin 3), 0 < i.val → i.val ≤ j.val →
          recurrence_ratio 2 op_940_decreasing_ratios_not_all_property_p_b
            op_940_decreasing_ratios_not_all_property_p_c j ≤
          recurrence_ratio 2 op_940_decreasing_ratios_not_all_property_p_b
            op_940_decreasing_ratios_not_all_property_p_c i := by
        intro i j hi hij
        fin_cases i
        · revert hi; norm_num
        · fin_cases j
          · revert hij; norm_num
          · norm_num
          · dsimp [recurrence_ratio, op_940_decreasing_ratios_not_all_property_p_b,
              op_940_decreasing_ratios_not_all_property_p_c]; norm_num
        · fin_cases j
          · revert hij; norm_num
          · revert hij; norm_num
          · norm_num
  5. Under the assumed conjecture, the linearization coefficient for indices (2, 2, 2) must be non-negative.

    Specializing the assumed universal statement H to N = 2 and the explicit coefficients a, b, and c, all conditions are met, so property (P) must hold. By definition of property (P), every linearization coefficient is non-negative, in particular the coefficient at (2, 2, 2).

    lines 77–82

      have hP := H 2 (by norm_num) op_940_decreasing_ratios_not_all_property_p_a
        op_940_decreasing_ratios_not_all_property_p_b
        op_940_decreasing_ratios_not_all_property_p_c h_norm h_log h_ratio
      have h_nonneg : 0 ≤ linearization_coeff 2 op_940_decreasing_ratios_not_all_property_p_a
        op_940_decreasing_ratios_not_all_property_p_b
        op_940_decreasing_ratios_not_all_property_p_c 2 2 2 := hP 2 2 2
  6. The linearization coefficient for indices (2, 2, 2) is exactly -1/8.

    The linearization coefficient is defined as the (2, 2)-entry of the matrix polynomial evaluation P₂(M), where M is the recurrence matrix and P₂(X) = 2X² - 1. Unfolding the definitions, distributing the polynomial evaluation across algebraic operations via homomorphism lemmas, expanding the matrix product and difference entrywise, and computing the rational arithmetic yields -1/8.

    lines 83–93

    uses map_smul, map_sub, map_mul, Polynomial.aeval_X, Polynomial.aeval_C, Polynomial.aeval_one, Matrix.sub_apply, Matrix.mul_apply, Fin.sum_univ_three, Matrix.of_apply, Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply, Fin.ext_iff

      have h_val : linearization_coeff 2 op_940_decreasing_ratios_not_all_property_p_a
          op_940_decreasing_ratios_not_all_property_p_b
          op_940_decreasing_ratios_not_all_property_p_c 2 2 2 = -1/8 := by
        dsimp [linearization_coeff, recurrence_poly]
        simp only [map_smul, map_sub, map_mul, Polynomial.aeval_X, Polynomial.aeval_C, Polynomial.aeval_one]
        dsimp [recurrence_matrix, op_940_decreasing_ratios_not_all_property_p_a,
          op_940_decreasing_ratios_not_all_property_p_b, op_940_decreasing_ratios_not_all_property_p_c]
        simp only [Matrix.sub_apply, Matrix.mul_apply, Fin.sum_univ_three]
        simp only [Matrix.of_apply, Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply]
        simp only [Fin.ext_iff]
        norm_num
  7. A contradiction is reached, completing the refutation.

    Substituting the computed value -1/8 into the non-negativity inequality yields 0 ≤ -1/8, which is an immediate arithmetic contradiction and concludes the proof.

    lines 94–95

      rw [h_val] at h_nonneg
      norm_num at h_nonneg
Finset.mem_Icc
An element belongs to the closed discrete interval [a, b] if and only if a ≤ x ≤ b.
Finset.sum_range_succ
A sum over the range {0, ..., n} equals the sum over {0, ..., n - 1} plus the n-th term.
Finset.sum_range_zero
The sum of a function over the empty range of size 0 is zero.
Finset.mem_Ico
An element belongs to the half-open discrete interval [a, b) if and only if a ≤ x < b.
map_smul
A module homomorphism preserves scalar multiplication.
map_sub
An additive homomorphism preserves subtraction.
map_mul
A multiplicative homomorphism preserves products.
Polynomial.aeval_X
Evaluating the polynomial variable X at an element x yields x.
Polynomial.aeval_C
Evaluating a constant polynomial C(r) at x yields the scalar r embedded in the algebra.
Polynomial.aeval_one
Evaluating the constant polynomial 1 at an element yields 1.
Matrix.sub_apply
The (i, j)-entry of the difference of two matrices is the difference of their (i, j)-entries.
Matrix.mul_apply
The (i, k)-entry of a matrix product M N is the sum ∑_j M(i, j) * N(j, k).
Fin.sum_univ_three
A sum of a function over the three-element set Fin 3 equals f(0) + f(1) + f(2).
Matrix.of_apply
The (i, j)-entry of a matrix defined by a function f is f(i, j).
Algebra.algebraMap_eq_smul_one
The image of a scalar r under the canonical algebra map is r • 1.
Matrix.smul_apply
Scalar multiplication on a matrix acts entrywise: (r • A)(i, j) = r • A(i, j).
Matrix.one_apply
The (i, j)-entry of the identity matrix is 1 if i = j and 0 otherwise.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.

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

noncomputable def op_940_decreasing_ratios_not_all_property_p_a (i : Fin 3) : ℝ :=  if i.val = 0 then 1  else if i.val = 1 then 1/2  else 0noncomputable def op_940_decreasing_ratios_not_all_property_p_b (i : Fin 3) : ℝ :=  if i.val = 2 then 1/4  else 0noncomputable def op_940_decreasing_ratios_not_all_property_p_c (i : Fin 3) : ℝ :=  if i.val = 1 then 1/2  else if i.val = 2 then 3/4  else 0/-- Refutation of the decreasing-ratio property (P) conjecture for OP-940. -/theorem op_940_decreasing_ratios_not_all_property_p :  ¬ (∀ (N : ℕ) (hN : 2 ≤ N) (a b c : Fin (N + 1) → ℝ),    is_normalized_recurrence N a b c →    is_log_concave_newton N (recurrence_profile N b c) →    (∀ (i j : Fin (N + 1)), 0 < i.val → i.val ≤ j.val →      recurrence_ratio N b c j ≤ recurrence_ratio N b c i) →    has_property_p N a b c) := by  intro H  have h_norm : is_normalized_recurrence 2 op_940_decreasing_ratios_not_all_property_p_a      op_940_decreasing_ratios_not_all_property_p_b      op_940_decreasing_ratios_not_all_property_p_c := by    refine ⟨rfl, rfl, rfl, rfl, ?_, ?_, ?_, ?_⟩    · intro i; fin_cases i <;> norm_num [op_940_decreasing_ratios_not_all_property_p_a,        op_940_decreasing_ratios_not_all_property_p_b, op_940_decreasing_ratios_not_all_property_p_c]    · intro i hi; fin_cases i      · norm_num [op_940_decreasing_ratios_not_all_property_p_a]      · norm_num [op_940_decreasing_ratios_not_all_property_p_a]      · revert hi; norm_num    · intro i hi; fin_cases i      · revert hi; norm_num      · norm_num [op_940_decreasing_ratios_not_all_property_p_c]      · norm_num [op_940_decreasing_ratios_not_all_property_p_c]    · intro i; fin_cases i <;> norm_num [op_940_decreasing_ratios_not_all_property_p_b]  have h_log : is_log_concave_newton 2 (recurrence_profile 2 op_940_decreasing_ratios_not_all_property_p_b      op_940_decreasing_ratios_not_all_property_p_c) := by    dsimp [is_log_concave_newton]    constructor    · intro k hk      rw [Finset.mem_Icc] at hk      rcases hk with ⟨h1, h2⟩      interval_cases k      · dsimp [newton_coeff]        rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]        dsimp [recurrence_profile, op_940_decreasing_ratios_not_all_property_p_b,          op_940_decreasing_ratios_not_all_property_p_c]        norm_num      · dsimp [newton_coeff]        rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]        dsimp [recurrence_profile, op_940_decreasing_ratios_not_all_property_p_b,          op_940_decreasing_ratios_not_all_property_p_c]        norm_num    · intro k hk      rw [Finset.mem_Ico] at hk      omega  have h_ratio : ∀ (i j : Fin 3), 0 < i.val → i.val ≤ j.val →      recurrence_ratio 2 op_940_decreasing_ratios_not_all_property_p_b        op_940_decreasing_ratios_not_all_property_p_c j ≤      recurrence_ratio 2 op_940_decreasing_ratios_not_all_property_p_b        op_940_decreasing_ratios_not_all_property_p_c i := by    intro i j hi hij    fin_cases i    · revert hi; norm_num    · fin_cases j      · revert hij; norm_num      · norm_num      · dsimp [recurrence_ratio, op_940_decreasing_ratios_not_all_property_p_b,          op_940_decreasing_ratios_not_all_property_p_c]; norm_num    · fin_cases j      · revert hij; norm_num      · revert hij; norm_num      · norm_num  have hP := H 2 (by norm_num) op_940_decreasing_ratios_not_all_property_p_a    op_940_decreasing_ratios_not_all_property_p_b    op_940_decreasing_ratios_not_all_property_p_c h_norm h_log h_ratio  have h_nonneg : 0 ≤ linearization_coeff 2 op_940_decreasing_ratios_not_all_property_p_a    op_940_decreasing_ratios_not_all_property_p_b    op_940_decreasing_ratios_not_all_property_p_c 2 2 2 := hP 2 2 2  have h_val : linearization_coeff 2 op_940_decreasing_ratios_not_all_property_p_a      op_940_decreasing_ratios_not_all_property_p_b      op_940_decreasing_ratios_not_all_property_p_c 2 2 2 = -1/8 := by    dsimp [linearization_coeff, recurrence_poly]    simp only [map_smul, map_sub, map_mul, Polynomial.aeval_X, Polynomial.aeval_C, Polynomial.aeval_one]    dsimp [recurrence_matrix, op_940_decreasing_ratios_not_all_property_p_a,      op_940_decreasing_ratios_not_all_property_p_b, op_940_decreasing_ratios_not_all_property_p_c]    simp only [Matrix.sub_apply, Matrix.mul_apply, Fin.sum_univ_three]    simp only [Matrix.of_apply, Algebra.algebraMap_eq_smul_one, Matrix.smul_apply, Matrix.one_apply]    simp only [Fin.ext_iff]    norm_num  rw [h_val] at h_nonneg  norm_num at h_nonneg
See it in the graphDiscuss this resultChallenge it