normalized_tree_rank_partial_sync_counterexample
Full partial synchronization can fail after one-vertex extension even when the input has the stated analytic invariants and its first three ranks match a rooted 19-vertex tree.
Statement
theorem normalized_tree_rank_partial_sync_counterexample : ∃ u a : ℕ → ℝ, normalized_tree_rank_partial_mixture u a ∧ (let g : ℕ → ℝ := fun k => (20 - (k : ℝ)) * u k + (k : ℝ) * a (k - 1); let q : ℕ → ℝ := fun k => (20 - (k : ℝ)) * u k + (k : ℝ) * u (k - 1); g 5 * q 4 + g 4 * q 5 < g 6 * q 3 + g 3 * q 6)
- Source
- A synthetic obstruction to an abstract closure argument for OP-1399.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- normalized_tree_rank_partial_mixtureNormalized sequences with the first three ranks of a particular 19-vertex rooted tree, binomial bounds, likelihood order, bounded-mixture…
The proof, explained
The theorem is proved by constructing an explicit counterexample pair of sequences u and a. Their initial values match the normalized rank parameters of a rooted 19-vertex tree up to degree 2, followed by geometric decay with ratio 47/54 through degree 6, and zero thereafter. All twelve conditions defining a normalized tree rank partial mixture—including boundedness, support on {0, ..., 6}, ratio monotonicity, log-concavity of u - a, log-concavity of all mixtures a + t(u - a), and a cross-term inequality—are verified by finite case exhaustion and arithmetic. Finally, evaluating the one-vertex extension sequences g and q at degrees 3, 4, 5, and 6 by exact rational arithmetic confirms the strict failure of partial synchronization: g(5)q(4) + g(4)q(5) < g(6)q(3) + g(3)q(6).
The sequence normalized_psw_a vanishes for all k > 6.
For k > 6, the conditions k = 0, k = 1, and k ≤ 6 in the definition of normalized_psw_a are all false by linear integer arithmetic (omega), so the conditional definition simplifies directly to 0.
private theorem normalized_psw_a_zero (k : ℕ) (h : 6 < k) : normalized_psw_a k = 0 := by simp [normalized_psw_a, show k ≠ 0 by omega, show k ≠ 1 by omega, show ¬ k ≤ 6 by omega]
The sequence normalized_psw_u vanishes for all k > 6.
Similarly, for k > 6, omega proves k ≠ 0, k ≠ 1, and ¬(k ≤ 6), so normalized_psw_u k simplifies directly to 0.
private theorem normalized_psw_u_zero (k : ℕ) (h : 6 < k) : normalized_psw_u k = 0 := by simp [normalized_psw_u, show k ≠ 0 by omega, show k ≠ 1 by omega, show ¬ k ≤ 6 by omega]
The candidate sequences satisfy the initial value constraints at k = 0, 1, 2.
We split the definition of normalized_tree_rank_partial_mixture into its twelve constituent goals. The first six goals—prescribing a(0) = 1, u(0) = 1, a(1) = 18/19, u(1) = 1, u(2) = 56/57, and a(2) = 47/57 to match a rooted 19-vertex tree—are verified directly by norm_num from the definitions of normalized_psw_a and normalized_psw_u.
private theorem normalized_psw_input_valid : normalized_tree_rank_partial_mixture normalized_psw_u normalized_psw_a := by refine ⟨by norm_num [normalized_psw_a], by norm_num [normalized_psw_u], by norm_num [normalized_psw_a], by norm_num [normalized_psw_u], by norm_num [normalized_psw_u], by norm_num [normalized_psw_a], ?_, ?_, ?_, ?_, ?_, ?_⟩
For all k, the bounds 0 ≤ normalized_psw_a k ≤ normalized_psw_u k ≤ 1 hold.
We split into cases on k ≤ 6. For k ≤ 6, interval_cases tests each k ∈ {0, ..., 6} individually and norm_num checks the inequalities on the explicit rational values. For k > 6, normalized_psw_a_zero and normalized_psw_u_zero reduce both sequences to 0, satisfying 0 ≤ 0 ≤ 0 ≤ 1.
uses
normalized_psw_a_zero,normalized_psw_u_zero· intro k by_cases hk : k ≤ 6 · interval_cases k <;> norm_num [normalized_psw_a, normalized_psw_u] · have h : 6 < k := by omega simp [normalized_psw_a_zero k h, normalized_psw_u_zero k h]
For all k > 6, both normalized_psw_a k = 0 and normalized_psw_u k = 0.
This is immediate from the helper lemmas normalized_psw_a_zero and normalized_psw_u_zero.
uses
normalized_psw_a_zero,normalized_psw_u_zero· intro k hk simp [normalized_psw_a_zero k hk, normalized_psw_u_zero k hk]
For all i < j, the ratio monotonicity inequality a(j) * (u(i) - a(i)) ≤ a(i) * (u(j) - a(j)) holds.
We split on j ≤ 6. If j ≤ 6, then i < j implies i ≤ 6, and all pairs 0 ≤ i < j ≤ 6 are verified by exhaustive case analysis (interval_cases) and rational arithmetic (norm_num). If j > 6, then a(j) = 0 and u(j) = 0 by normalized_psw_a_zero and normalized_psw_u_zero, so both sides simplify to 0.
uses
normalized_psw_a_zero,normalized_psw_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 [normalized_psw_a, normalized_psw_u] at * · have hj' : 6 < j := by omega simp [normalized_psw_a_zero j hj', normalized_psw_u_zero j hj']
The difference sequence u - a is log-concave: (u(k) - a(k)) * (u(k+2) - a(k+2)) ≤ (u(k+1) - a(k+1))^2 for all k.
We split on k ≤ 4. If k ≤ 4, interval_cases and norm_num verify the inequality for k ∈ {0, 1, 2, 3, 4}. If k > 4, then k + 2 > 6, so u(k+2) and a(k+2) vanish by normalized_psw_u_zero and normalized_psw_a_zero; the left-hand side reduces to 0 using sub_self and mul_zero, while the right-hand side is a square and hence non-negative by sq_nonneg.
uses
normalized_psw_a_zero,normalized_psw_u_zero,sub_self,mul_zero,sq_nonneg· intro k by_cases hk : k ≤ 4 · interval_cases k <;> norm_num [normalized_psw_a, normalized_psw_u] · have h : 6 < k + 2 := by omega simp only [normalized_psw_a_zero (k+2) h, normalized_psw_u_zero (k+2) h, sub_self, mul_zero] exact sq_nonneg _
Every convex combination sequence a + t * (u - a) with t ∈ [0, 1] is log-concave. automation
For t ∈ [0, 1] and k, we split on k ≤ 4. For k ≤ 4, evaluating the sequences at k, k+1, k+2 via interval_cases and norm_num produces five quadratic inequalities in t; nlinarith closes each one using the non-negativity of squares (sq_nonneg) and of t * (1 - t) (mul_nonneg). For k > 4, k + 2 > 6 implies the k+2 term vanishes by normalized_psw_a_zero and normalized_psw_u_zero; after simplifying with sub_self, mul_zero, and add_zero, the left side is 0 and the right side is non-negative by sq_nonneg.
uses
normalized_psw_a_zero,normalized_psw_u_zero,sub_self,mul_zero,add_zero,sq_nonneg,mul_nonneg· intro t ht0 ht1 k by_cases hk : k ≤ 4 · interval_cases k <;> norm_num [normalized_psw_a, normalized_psw_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 [normalized_psw_a_zero (k+2) h, normalized_psw_u_zero (k+2) h, sub_self, mul_zero, add_zero] exact sq_nonneg _
For all 1 ≤ j ≤ i, the cross-term inequality a(i+1) * u(j-1) + a(j-1) * u(i+1) ≤ a(i) * u(j) + a(j) * u(i) holds.
We split on i ≤ 6. If i ≤ 6, then j ≤ i implies j ≤ 6, and all pairs 1 ≤ j ≤ i ≤ 6 are checked by interval_cases and norm_num. If i > 6, then both i > 6 and i + 1 > 6, so all terms with index i or i+1 vanish by normalized_psw_a_zero and normalized_psw_u_zero, reducing both sides to 0.
uses
normalized_psw_a_zero,normalized_psw_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 [normalized_psw_a, normalized_psw_u] at * · have h0 : 6 < i := by omega have h1 : 6 < i+1 := by omega simp [normalized_psw_a_zero i h0, normalized_psw_u_zero i h0, normalized_psw_a_zero (i+1) h1, normalized_psw_u_zero (i+1) h1]
There exist sequences u and a satisfying the mixture invariants whose one-vertex extension strictly fails partial synchronization at degree pair (5, 4) versus (6, 3).
We instantiate the existential witness with normalized_psw_u and normalized_psw_a, provide the validity proof normalized_psw_input_valid, and compute the one-vertex extension sequences g(k) = (20 - k) u(k) + k a(k-1) and q(k) = (20 - k) u(k) + k u(k-1) via norm_num, confirming that g(5) * q(4) + g(4) * q(5) < g(6) * q(3) + g(3) * q(6).
uses
normalized_psw_input_validtheorem normalized_tree_rank_partial_sync_counterexample : ∃ u a : ℕ → ℝ, normalized_tree_rank_partial_mixture u a ∧ (let g : ℕ → ℝ := fun k => (20 - (k : ℝ)) * u k + (k : ℝ) * a (k - 1); let q : ℕ → ℝ := fun k => (20 - (k : ℝ)) * u k + (k : ℝ) * u (k - 1); g 5 * q 4 + g 4 * q 5 < g 6 * q 3 + g 3 * q 6) := by refine ⟨normalized_psw_u, normalized_psw_a, normalized_psw_input_valid, ?_⟩ norm_num [normalized_psw_u, normalized_psw_a]
normalized_psw_a_zero- For any natural number k > 6, the normalized sequence value normalized_psw_a k equals 0.
normalized_psw_u_zero- For any natural number k > 6, the normalized sequence value normalized_psw_u k equals 0.
normalized_psw_input_valid- The candidate sequences normalized_psw_u and normalized_psw_a satisfy all twelve defining conditions of normalized_tree_rank_partial_mixture.
sub_self- Subtracting any element from itself yields zero: a - a = 0.
mul_zero- Multiplying any element by zero yields zero: a * 0 = 0.
sq_nonneg- The square of any element in an ordered semiring is non-negative: 0 ≤ a ^ 2.
add_zero- Adding zero to any element leaves it unchanged: a + 0 = a.
mul_nonneg- The product of two non-negative elements in an ordered semiring is non-negative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a * b.
- In Step 8 (lines 32–38), verifying log-concavity of the convex combinations a + t(u - a) on [0, 1] reduces to checking five quadratic inequalities in t with large rational coefficients, which is closed by the non-linear arithmetic tactic nlinarith using certificates of non-negativity for t, 1 - t, and squares.
- Across multiple steps (Steps 4, 6, 7, 8, 9), bounds and inequalities on low degrees (indices up to 6) are established by exhaustive finite case analysis using interval_cases combined with 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 normalized_psw_u (k : ℕ) : ℝ := if k = 0 then 1 else if k = 1 then 1 else if k ≤ 6 then (56 / 57) * (47 / 54) ^ (k - 2) else 0private noncomputable def normalized_psw_a (k : ℕ) : ℝ := if k = 0 then 1 else if k = 1 then 18 / 19 else if k ≤ 6 then (47 / 57) * (47 / 54) ^ (k - 2) else 0private theorem normalized_psw_a_zero (k : ℕ) (h : 6 < k) : normalized_psw_a k = 0 := by simp [normalized_psw_a, show k ≠ 0 by omega, show k ≠ 1 by omega, show ¬ k ≤ 6 by omega]private theorem normalized_psw_u_zero (k : ℕ) (h : 6 < k) : normalized_psw_u k = 0 := by simp [normalized_psw_u, show k ≠ 0 by omega, show k ≠ 1 by omega, show ¬ k ≤ 6 by omega]private theorem normalized_psw_input_valid : normalized_tree_rank_partial_mixture normalized_psw_u normalized_psw_a := by refine ⟨by norm_num [normalized_psw_a], by norm_num [normalized_psw_u], by norm_num [normalized_psw_a], by norm_num [normalized_psw_u], by norm_num [normalized_psw_u], by norm_num [normalized_psw_a], ?_, ?_, ?_, ?_, ?_, ?_⟩ · intro k by_cases hk : k ≤ 6 · interval_cases k <;> norm_num [normalized_psw_a, normalized_psw_u] · have h : 6 < k := by omega simp [normalized_psw_a_zero k h, normalized_psw_u_zero k h] · intro k hk simp [normalized_psw_a_zero k hk, normalized_psw_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 [normalized_psw_a, normalized_psw_u] at * · have hj' : 6 < j := by omega simp [normalized_psw_a_zero j hj', normalized_psw_u_zero j hj'] · intro k by_cases hk : k ≤ 4 · interval_cases k <;> norm_num [normalized_psw_a, normalized_psw_u] · have h : 6 < k + 2 := by omega simp only [normalized_psw_a_zero (k+2) h, normalized_psw_u_zero (k+2) h, sub_self, mul_zero] exact sq_nonneg _ · intro t ht0 ht1 k by_cases hk : k ≤ 4 · interval_cases k <;> norm_num [normalized_psw_a, normalized_psw_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 [normalized_psw_a_zero (k+2) h, normalized_psw_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 [normalized_psw_a, normalized_psw_u] at * · have h0 : 6 < i := by omega have h1 : 6 < i+1 := by omega simp [normalized_psw_a_zero i h0, normalized_psw_u_zero i h0, normalized_psw_a_zero (i+1) h1, normalized_psw_u_zero (i+1) h1]theorem normalized_tree_rank_partial_sync_counterexample : ∃ u a : ℕ → ℝ, normalized_tree_rank_partial_mixture u a ∧ (let g : ℕ → ℝ := fun k => (20 - (k : ℝ)) * u k + (k : ℝ) * a (k - 1); let q : ℕ → ℝ := fun k => (20 - (k : ℝ)) * u k + (k : ℝ) * u (k - 1); g 5 * q 4 + g 4 * q 5 < g 6 * q 3 + g 3 * q 6) := by refine ⟨normalized_psw_u, normalized_psw_a, normalized_psw_input_valid, ?_⟩ norm_num [normalized_psw_u, normalized_psw_a]