op_940_decreasing_ratios_not_all_property_p
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).
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.
intro HThe 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`).
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]
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`).
uses
Finset.mem_Icc,Finset.sum_range_succ,Finset.sum_range_zero,Finset.mem_Icohave 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
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.
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
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).
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
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.
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_iffhave 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
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.
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.
- For N = 2, the half-open interval [2, N) = [2, 2) in the definition of Newton log-concavity is empty, so the quadratic log-concavity inequalities hold vacuously and only the non-negativity of Newton coefficients needed to be verified.
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.
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