AFTD Auto-Formalizing Theoretical Domains

normalized_tree_rank_partial_sync_counterexample

theoremverified

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

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

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

    lines 6–7

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

    lines 8–9

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

    lines 11–12

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

    lines 13–17

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

    lines 18–19

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

    lines 20–25

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

    lines 26–31

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

    lines 32–38

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

    lines 39–45

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

    lines 47–49

    uses normalized_psw_input_valid

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

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