Over-learning forces instability for at most five agents: trace bounds for ρ(A-E) and a quartic threshold

trace bound for the Averaging-plus-Learning operator: for any entrywise-nonnegative A and any real vector E of learning rates, if every complex eigenvalue of A - diagonal E has modulus below s then sumᵢ (E i - A i i)² < n*s²; contrapositively n*s² <= sumᵢ (E i - A i i)² forces an eigenvalue of modulus at least s, and a single agent already suffices (n*s² <= (E i0 - A i0 i0)²). Equivalently rho(A - E) >= sqrt((sumᵢ (E i - A i i)²)/n)

the source's open Problem 2.20 is TRUE for every n <= 4: if A is row-substochastic (in particular row-stochastic) and E is any real diagonal (in particular the nonnegative one of the Problem) with 3 <= E(i) for some i, and 0 < n <= 4, then rho(A - E) >= 1

a sqrt-n threshold replacing the source's exponential one: for row-substochastic A and any real diagonal E, 1 + sqrt n <= E(i) for some i forces rho(A - E) >= 1; equivalently fₙ(R) >= (R-1)⁺/sqrt n, so fₙ(R) > 1 as soon as R > 1 + sqrt n, where the source's own bound needs R > (n 2ⁿ + 3n - 1)/2

dimension-free corollary: for row-substochastic A, if EVERY agent has learning rate at least c + 1 with c >= 0, then rho(A - E) >= c; in particular all rates at least 2 force rho >= 1, at every n and with no symmetry or isolation hypothesis

many fast learners: for row-substochastic A, if a finite set S of agents all have 3 <= E(i) and n <= 4*|S|, then rho(A - E) >= 1 – at every n, however large

the source's own Appendix-A counterexample to the threshold 2, kernel-checked: for A = [[1/5,0,4/5],[1,0,0],[0,1/5,4/5]] and E = diag(1/2, 0, 2) the characteristic polynomial of A - E is (t + 4/5)(t² + 7t/10 - 1/5) and every complex eigenvalue has modulus < 23/25 = 0.92, so the threshold 3 in the Problem cannot be lowered to 2

too-large negative control: for A = I₃ and E = diag(3, 0, 0) the characteristic polynomial of A - E is (t + 2)(t - 1)², so the spectrum is -2, 1; the hypothesis of SRA2 is satisfiable (E(1) = 3) and its conclusion cannot be strengthened past rho >= R - 1 = 2, in particular 'E(i) >= 3 forces rho >= 5/2' is false at n = 3

measured numerical map of the source's extremal function at R = 3 (row-stochastic A, maxᵢ E(i) = 3): min rho found is 2.000 at n = 2, 1.8078 at n = 3, 1.7756 at n = 4, 1.7835 at n = 5 – so f₃(3) < 2, and the source's exact formula fₙ(R) = (R-1)⁺ (its Theorem A.12, proved for n = 1, 2) does NOT extend to n = 3; the values stay far above 1, consistent with a positive answer to the Problem

the Problem holds whenever the fast learner's influence set is small: for row-substochastic A, if an injection f: Fin m -> Fin n has out-closed image (A (f a) j = 0 whenever j is outside the image), 0 < m <= 4, and 3 <= E (f a0) for some a0, then rho(A - E) >= 1 – at every n. The supporting lemma is that a singular principal submatrix on an out-closed set forces the whole matrix to be singular, hence the spectrum of the restriction embeds

the source's open Problem 2.20 is TRUE for every n <= 5: if A is row-substochastic (in particular row-stochastic, as in the Problem) and E is any real diagonal (in particular the nonnegative one) with 3 <= E(i0) for some i0, and 0 < n <= 5, then rho(A - E) >= 1. Proved by the fourth-power trace bound tr((A-E)⁴) >= sumᵢ dᵢ⁴ - 4 sumᵢ max(dᵢ,0) rᵢ (where dᵢ = E(i) - A(i,i) and rᵢ = (sumⱼ A(i,j)) - A(i,i) is agent i's outgoing averaging weight) together with the fast-learner constraint rᵢ0 <= dᵢ0 - 2

a quartic threshold replacing the square-root one: for row-substochastic A and any real diagonal E, if some agent has 3 <= E(i0) with 5n <= (E(i0) - 1)⁴ – equivalently E(i0) >= 1 + (5n)^(1/4) – then rho(A - E) >= 1. In the source's language fₙ(R) > 1 as soon as R > 1 + (5n)^(1/4), where SRA3 needs R > 1 + sqrt n and the source's own Theorem A.11 needs R > Rbarₙ = (n 2ⁿ + 3n - 1)/2

f₃(3) < 2, now a theorem: the row-stochastic A = [[9/10,1/10,0],[0,0,1],[1,0,0]] with the nonnegative diagonal E = (3, 5/4, 5/4), for which maxᵢ E(i) = E(1) = 3 as Definition A.5 requires, has every complex eigenvalue of E - A of modulus below 2. Hence f₃(3) < 2 = (3-1)⁺ and the source's exact formula fₙ(R) = (R-1)⁺ (its Theorem A.12, for n = 1, 2) does NOT extend to n = 3

a reusable quadratic Lyapunov certificate in the family's SpecLT vocabulary: if q: Cⁿ -> R is positive off the origin, homogeneous of degree 2 under complex scaling (q(mu. v) = norm(mu)² q(v)), and the real matrix M contracts it by s² (q(M v) < s² q(v) for every v /= 0), with 0 <= s, then every complex eigenvalue of M has modulus below s. Instantiated for the f₃(3) witness at P = [[128,-16,16],[-16,6,-4],[16,-4,8]] with the exact sum-of-squares identity 4q(v) - q(Mv) = (1/4200)|168v0-43v1+60v2|² + (11/5712)|68v1+15v2|² + (601/272)|v2|²

the level-2,4 trace method provably stops at n = 6: the exact 7x7 row-stochastic A with A(0,0) = 1, A(1,2) = A(2,3) = A(3,1) = A(4,5) = A(5,6) = A(6,4) = 1 and E = (3, 7/10, 7/10, 7/10, 7/10, 7/10, 7/10) satisfies the Problem's hypothesis and has tr((A-E)²) = 347/50 = 6.94 and tr((A-E)⁴) = 3203/5000 = 0.6406, both below n = 7, while rho(A-E) >= 2 so it is not a counterexample to the Problem; moreover on that instance the fourth-power estimate underlying SRA10 is EXACTLY TIGHT (the bound equals the trace), so the gap between n <= 5 and the method's ceiling is not slack in the estimates

the source's open Problem 2.20 is TRUE for every n <= 6: if A is row-substochastic (in particular row-stochastic, as in the Problem) and E is any real diagonal (in particular the nonnegative one) with 3 <= E(i0) for some i0, and 0 < n <= 6, then rho(A - E) >= 1. Proved by keeping the triangle masses tᵢ = (F³)(i,i) in the level-4 trace bound (F = offDiag A) and capping their total on the n-1 <= 5 non-fast agents: the vertex-deletion identity tr(F³) = 3 tᵢ0 + tr(G³) plus the triangle-mass bound tr(G³) <= 3 floor(5/3) = 3 gives sum_(j!= i0) tⱼ <= 2x - 1, and Cauchy-Schwarz against the masses closes the chain at 7.002 against a target of 6

the quartic threshold constant drops from 5 to 4: for row-substochastic A and any real diagonal E, if some agent has 3 <= E(i0) with 4n <= (E(i0) - 1)⁴ – equivalently E(i0) >= 1 + (4n)^(1/4) – then rho(A - E) >= 1. In the source's language fₙ(R) > 1 as soon as R > 1 + (4n)^(1/4), where SRA11 needs R > 1 + (5n)^(1/4), SRA3 needs R > 1 + sqrt n, and the source's own Theorem A.11 needs R > (n 2ⁿ + 3n - 1)/2. The constant 4 is exact for this chain

the level-2,4,6 trace method provably stops at n = 7: the exact 8x8 row-stochastic A with A(0,0) = 1, A(1,2) = A(2,3) = A(3,1) = A(4,5) = A(5,6) = A(6,4) = A(7,1) = 1 and E = (3, 1/20, 1/20, 1/20, 21/20, 21/20, 21/20, 0) satisfies the Problem's hypothesis (E >= 0 with maxᵢ E(i) = E(0) = 3) and has |tr((A-E)ᵐ)| < 8 for EVERY m <= 6 – the traces are -53/10, 1463/200, -21893/4000, 515723/80000, -4286153/1600000, 145769183/32000000 – while rho(A-E) >= 2, so it is not a counterexample. Hence no certificate of the form '|tr(Zᵐ)| >= n for some m <= 6' settles n = 8

the triangle-mass bound: for an entrywise-nonnegative F with zero diagonal and row sums at most 1, and any finite index set s, the total weight of the closed 3-walks inside s – sum over a,b,c in s of F(a,b) F(b,c) F(c,a) – is at most 3 floor(|s|/3); in particular tr(F³) <= 3 floor(n/3). Sharp: floor(n/3) vertex-disjoint weight-1 triangles attain it