normalized_binary_tree_prefix_ulc_counterexample
Even with bounded-mixture ULC, likelihood order, and full partial synchronization, normalized sequences having initial counts U=(1,100,4760) and A=(1,80,3160) can have a non-ULC one-vertex extension.
Statement
theorem normalized_binary_tree_prefix_ulc_counterexample : ∃ u a : ℕ → ℝ, normalized_binary_tree_prefix_input u a ∧ (let g : ℕ → ℝ := fun k => (101 - (k : ℝ)) * u k + (k : ℝ) * a (k - 1); g 5 ^ 2 < g 4 * g 6)
- Source
- A synthetic obstruction to a binary-extension argument for OP-1399.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- normalized_binary_tree_prefix_inputThe normalized sequences have specified first three ranks, bounded support, likelihood order, log-concavity of every bounded mixture, and…
The proof, explained
The theorem is proved by exhibiting explicit finite-support rational sequences u and a, supported on {0, ..., 6} and {0, ..., 5} respectively. The proof first verifies that u and a satisfy all the axioms of a normalized binary tree prefix input—initial counts, normalization bounds, likelihood order, bounded-mixture ultra-log-concavity, and full partial synchronization—via finite case exhaustion and interval arithmetic on [0, 1]. Finally, it evaluates the one-vertex extension g(k) = (101 - k)u_k + k a_{k-1} at indices k = 4, 5, 6 by exact rational arithmetic, showing that g(5)^2 < g(4) g(6) and thus providing a counterexample to log-concavity.
The sequence a(k) vanishes for all k > 6.
By definition, binary_tree_prefix_a is given by a chain of if-then-else conditions for k = 0, ..., 5 and is 0 otherwise. When k > 6, linear arithmetic (omega) verifies that k does not equal any index from 0 to 5, so the conditional expression simplifies directly to 0.
private theorem binary_tree_prefix_a_zero (k : ℕ) (h : 6 < k) : binary_tree_prefix_a k = 0 := by simp [binary_tree_prefix_a, show k ≠ 0 by omega, show k ≠ 1 by omega, show k ≠ 2 by omega, show k ≠ 3 by omega, show k ≠ 4 by omega, show k ≠ 5 by omega]
The sequence u(k) vanishes for all k > 6.
Similarly, binary_tree_prefix_u branches on k = 0, ..., 6 and evaluates to 0 otherwise. When k > 6, linear arithmetic confirms that k is not equal to any index from 0 to 6, simplifying the definition to 0.
private theorem binary_tree_prefix_u_zero (k : ℕ) (h : 6 < k) : binary_tree_prefix_u k = 0 := by simp [binary_tree_prefix_u, show k ≠ 0 by omega, show k ≠ 1 by omega, show k ≠ 2 by omega, show k ≠ 3 by omega, show k ≠ 4 by omega, show k ≠ 5 by omega, show k ≠ 6 by omega]
The sequences u and a satisfy the six required initial values at indices 0, 1, and 2.
The conditions a(0) = 1, u(0) = 1, a(1) = 4/5, u(1) = 1, u(2) = 476/495, and a(2) = 316/495 are verified by direct numerical evaluation of the conditional definitions of u and a.
private theorem binary_tree_prefix_input_valid : normalized_binary_tree_prefix_input binary_tree_prefix_u binary_tree_prefix_a := by refine ⟨by norm_num [binary_tree_prefix_a], by norm_num [binary_tree_prefix_u], by norm_num [binary_tree_prefix_a], by norm_num [binary_tree_prefix_u], by norm_num [binary_tree_prefix_u], by norm_num [binary_tree_prefix_a], ?_, ?_, ?_, ?_, ?_⟩
For all k, the bounds 0 ≤ a(k) ≤ u(k) ≤ 1 hold.
We split into cases on whether k ≤ 6. For k ≤ 6, the seven cases k ∈ {0, ..., 6} are verified by evaluating the rational constants. For k > 6, both a(k) = 0 and u(k) = 0 by binary_tree_prefix_a_zero and binary_tree_prefix_u_zero, so the inequality 0 ≤ 0 ≤ 0 ≤ 1 holds trivially.
uses
binary_tree_prefix_a_zero,binary_tree_prefix_u_zero· intro k by_cases hk : k ≤ 6 · interval_cases k <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] · have h : 6 < k := by omega simp [binary_tree_prefix_a_zero k h, binary_tree_prefix_u_zero k h]
Both sequences vanish beyond index 6: for all k > 6, a(k) = 0 and u(k) = 0.
This is an immediate consequence of the vanishing lemmas binary_tree_prefix_a_zero and binary_tree_prefix_u_zero.
uses
binary_tree_prefix_a_zero,binary_tree_prefix_u_zero· intro k hk simp [binary_tree_prefix_a_zero k hk, binary_tree_prefix_u_zero k hk]
The sequences satisfy the likelihood order: for all i < j, a(j) * (u(i) - a(i)) ≤ a(i) * (u(j) - a(j)).
We consider whether j ≤ 6. If j ≤ 6, then i ≤ 6 as well because i < j, and all 21 pairs (i, j) with 0 ≤ i < j ≤ 6 are checked by finite case exhaustion and numerical evaluation. If j > 6, then a(j) = 0 and u(j) = 0 by binary_tree_prefix_a_zero and binary_tree_prefix_u_zero, reducing the inequality to 0 ≤ 0.
uses
binary_tree_prefix_a_zero,binary_tree_prefix_u_zero· intro i j hij by_cases hj : j ≤ 6 · have hi : i ≤ 6 := by omega interval_cases i <;> interval_cases j <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] at * · have hj' : 6 < j := by omega simp [binary_tree_prefix_a_zero j hj', binary_tree_prefix_u_zero j hj']
All convex mixtures of a and u are log-concave: for every t ∈ [0, 1] and every k, the mixture m(k) = a(k) + t * (u(k) - a(k)) satisfies m(k) * m(k+2) ≤ m(k+1)^2.
We case-split on whether k ≤ 4. For each k ∈ {0, 1, 2, 3, 4}, substituting the rational values leaves a quadratic polynomial inequality in t on [0, 1], which is established by nonlinear arithmetic using sq_nonneg and mul_nonneg. For k > 4, k + 2 > 6 implies that a(k+2) = 0 and u(k+2) = 0 by binary_tree_prefix_a_zero and binary_tree_prefix_u_zero; the left-hand side reduces to 0 using sub_self, mul_zero, and add_zero, while the right-hand side is a square, hence non-negative by sq_nonneg.
uses
sq_nonneg,mul_nonneg,binary_tree_prefix_a_zero,binary_tree_prefix_u_zero,sub_self,mul_zero,add_zero· intro t ht0 ht1 k by_cases hk : k ≤ 4 · interval_cases k <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] <;> nlinarith [sq_nonneg t, sq_nonneg (1-t), mul_nonneg ht0 (show 0 ≤ 1-t by linarith)] · have h : 6 < k + 2 := by omega simp only [binary_tree_prefix_a_zero (k+2) h, binary_tree_prefix_u_zero (k+2) h, sub_self, mul_zero, add_zero] exact sq_nonneg _
The full partial synchronization condition holds: for all 1 ≤ j ≤ i, a(i+1) * u(j-1) + a(j-1) * u(i+1) ≤ a(i) * u(j) + a(j) * u(i).
We case-split on whether i ≤ 6. If i ≤ 6, then j ≤ 6, and all 21 pairs 1 ≤ j ≤ i ≤ 6 are checked by exhaustive rational arithmetic. If i > 6, then both i > 6 and i + 1 > 6, so a(i) = u(i) = a(i+1) = u(i+1) = 0 by binary_tree_prefix_a_zero and binary_tree_prefix_u_zero, simplifying both sides to 0.
uses
binary_tree_prefix_a_zero,binary_tree_prefix_u_zero· intro i j hj hji by_cases hi : i ≤ 6 · have hj' : j ≤ 6 := by omega interval_cases i <;> interval_cases j <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] at * · have h0 : 6 < i := by omega have h1 : 6 < i+1 := by omega simp [binary_tree_prefix_a_zero i h0, binary_tree_prefix_u_zero i h0, binary_tree_prefix_a_zero (i+1) h1, binary_tree_prefix_u_zero (i+1) h1]
There exist normalized prefix sequences u and a satisfying all conditions whose one-vertex extension fails log-concavity at index 5.
We instantiate the existential statement with binary_tree_prefix_u and binary_tree_prefix_a, which satisfy all prefix input conditions by binary_tree_prefix_input_valid. For the one-vertex extension sequence g(k) = (101 - k) * u(k) + k * a(k-1), direct rational computation of g(4), g(5), and g(6) verifies the strict inequality g(5)^2 < g(4) * g(6), demonstrating that g fails to be log-concave.
uses
binary_tree_prefix_input_validtheorem normalized_binary_tree_prefix_ulc_counterexample : ∃ u a : ℕ → ℝ, normalized_binary_tree_prefix_input u a ∧ (let g : ℕ → ℝ := fun k => (101 - (k : ℝ)) * u k + (k : ℝ) * a (k - 1); g 5 ^ 2 < g 4 * g 6) := by refine ⟨binary_tree_prefix_u, binary_tree_prefix_a, binary_tree_prefix_input_valid, ?_⟩ norm_num [binary_tree_prefix_u, binary_tree_prefix_a]
binary_tree_prefix_a_zero- For any natural number k > 6, the prefix sequence a(k) is equal to 0.
binary_tree_prefix_u_zero- For any natural number k > 6, the prefix sequence u(k) is equal to 0.
binary_tree_prefix_input_valid- The explicit sequences u and a satisfy all conditions required of a normalized binary tree prefix input.
sq_nonneg- The square of any real number is non-negative.
mul_nonneg- The product of two non-negative numbers is non-negative.
sub_self- Subtracting any element of an additive group from itself yields zero.
mul_zero- Multiplying any element by zero yields zero.
add_zero- Adding zero to any element leaves it unchanged.
- For k ≤ 4 in the mixture log-concavity condition, nlinarith verifies quadratic inequalities in t on [0, 1] using positive linear combinations of squares.
- The verification of the prefix conditions on the non-zero indices relies on automated finite case exhaustion (interval_cases) combined with exact rational arithmetic (norm_num).
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.
private noncomputable def binary_tree_prefix_u (k : ℕ) : ℝ := if k = 0 then 1 else if k = 1 then 1 else if k = 2 then 476 / 495 else if k = 3 then 10338 / 13475 else if k = 4 then 77401 / 1307075 else if k = 5 then 42527 / 15057504 else if k = 6 then 160541 / 1192052400 else 0private noncomputable def binary_tree_prefix_a (k : ℕ) : ℝ := if k = 0 then 1 else if k = 1 then 4 / 5 else if k = 2 then 316 / 495 else if k = 3 then 6863 / 13475 else if k = 4 then 19627 / 1307075 else if k = 5 then 2777 / 6273960 else 0private theorem binary_tree_prefix_a_zero (k : ℕ) (h : 6 < k) : binary_tree_prefix_a k = 0 := by simp [binary_tree_prefix_a, show k ≠ 0 by omega, show k ≠ 1 by omega, show k ≠ 2 by omega, show k ≠ 3 by omega, show k ≠ 4 by omega, show k ≠ 5 by omega]private theorem binary_tree_prefix_u_zero (k : ℕ) (h : 6 < k) : binary_tree_prefix_u k = 0 := by simp [binary_tree_prefix_u, show k ≠ 0 by omega, show k ≠ 1 by omega, show k ≠ 2 by omega, show k ≠ 3 by omega, show k ≠ 4 by omega, show k ≠ 5 by omega, show k ≠ 6 by omega]private theorem binary_tree_prefix_input_valid : normalized_binary_tree_prefix_input binary_tree_prefix_u binary_tree_prefix_a := by refine ⟨by norm_num [binary_tree_prefix_a], by norm_num [binary_tree_prefix_u], by norm_num [binary_tree_prefix_a], by norm_num [binary_tree_prefix_u], by norm_num [binary_tree_prefix_u], by norm_num [binary_tree_prefix_a], ?_, ?_, ?_, ?_, ?_⟩ · intro k by_cases hk : k ≤ 6 · interval_cases k <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] · have h : 6 < k := by omega simp [binary_tree_prefix_a_zero k h, binary_tree_prefix_u_zero k h] · intro k hk simp [binary_tree_prefix_a_zero k hk, binary_tree_prefix_u_zero k hk] · intro i j hij by_cases hj : j ≤ 6 · have hi : i ≤ 6 := by omega interval_cases i <;> interval_cases j <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] at * · have hj' : 6 < j := by omega simp [binary_tree_prefix_a_zero j hj', binary_tree_prefix_u_zero j hj'] · intro t ht0 ht1 k by_cases hk : k ≤ 4 · interval_cases k <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] <;> nlinarith [sq_nonneg t, sq_nonneg (1-t), mul_nonneg ht0 (show 0 ≤ 1-t by linarith)] · have h : 6 < k + 2 := by omega simp only [binary_tree_prefix_a_zero (k+2) h, binary_tree_prefix_u_zero (k+2) h, sub_self, mul_zero, add_zero] exact sq_nonneg _ · intro i j hj hji by_cases hi : i ≤ 6 · have hj' : j ≤ 6 := by omega interval_cases i <;> interval_cases j <;> norm_num [binary_tree_prefix_a, binary_tree_prefix_u] at * · have h0 : 6 < i := by omega have h1 : 6 < i+1 := by omega simp [binary_tree_prefix_a_zero i h0, binary_tree_prefix_u_zero i h0, binary_tree_prefix_a_zero (i+1) h1, binary_tree_prefix_u_zero (i+1) h1]theorem normalized_binary_tree_prefix_ulc_counterexample : ∃ u a : ℕ → ℝ, normalized_binary_tree_prefix_input u a ∧ (let g : ℕ → ℝ := fun k => (101 - (k : ℝ)) * u k + (k : ℝ) * a (k - 1); g 5 ^ 2 < g 4 * g 6) := by refine ⟨binary_tree_prefix_u, binary_tree_prefix_a, binary_tree_prefix_input_valid, ?_⟩ norm_num [binary_tree_prefix_u, binary_tree_prefix_a]