AFTD Auto-Formalizing Theoretical Domains

normalized_binary_tree_prefix_ulc_counterexample

theoremverified

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.

  1. 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.

    lines 10–11

    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]
  2. 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.

    lines 12–13

    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]
  3. 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.

    lines 15–16

    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], ?_, ?_, ?_, ?_, ?_⟩
  4. 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.

    lines 17–21

    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]
  5. 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.

    lines 22–23

    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]
  6. 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.

    lines 24–29

    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']
  7. 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.

    lines 30–36

    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 _
  8. 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.

    lines 37–43

    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]
  9. 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.

    lines 45–47

    uses binary_tree_prefix_input_valid

    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]
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.

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

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]
See it in the graphDiscuss this resultChallenge it