A Tropical–Entropic Transfer Theorem for Log-Sum-Exp Dynamics on Finite Directed Graphs

The paper establishes a closed finite-dimensional transfer theorem between entropic log-sum-exp dynamics and max-plus tropical dynamics on finite directed graphs. The setting is a finite directed graph G = (V,E) with vertex set V = {1,2,...,n}; each directed edge j → i carries a real weight a_ij. For each vertex i, the in-neighborhood is J_i = {j ∈ V : (j,i) ∈ E}. Three assumptions are imposed. (H1) Nonempty bounded in-degree: for every i, J_i ≠ ∅, and d := max_i |J_i| < ∞. (H2) Strong connectivity: for every pair i,j ∈ V there exists a directed walk from j to i. (H3) Primitivity: there exists an integer p ≥ 1 such that for every pair i,j ∈ V there exists a directed walk of length exactly p from j to i. Equivalently, if P is the Boolean support matrix with P_ij = 1 when j ∈ J_i and P_ij = 0 otherwise, then P^p > 0. Because all exponential weights are strictly positive on existing edges, this is equivalent to S_τ^p > 0 for every τ > 0, where S_τ is the nonnegative matrix defined below. The integer p may be chosen from the support graph alone and does not depend on τ; a Wielandt-type bound gives p ≤ (n−1)^2+1. Thus primitivity is algorithmically decidable in polynomial time. (H3) implies (H2); both are kept for clarity. For τ > 0, the entropic or log-sum-exp operator T_τ : ℝ^n → ℝ^n is defined by (T_τ x)_i = τ log Σ_{j ∈ J_i} exp((a_ij + x_j)/τ). The tropical or max-plus operator T_0 : ℝ^n → ℝ^n is defined by (T_0 x)_i = max_{j ∈ J_i} (a_ij + x_j). The nonnegative matrix S_τ is defined by (S_τ)_ij = exp(a_ij/τ) if j ∈ J_i, and (S_τ)_ij = 0 otherwise. Then the exact identity holds: T_τ x = τ log(S_τ exp(x/τ)). This identity is exact, not approximate. By induction, T_τ^k x = τ log(S_τ^k exp(x/τ)). Define ρ_τ = ρ(S_τ), where ρ denotes spectral radius, and λ_τ = τ log ρ_τ. Define the tropical maximum cycle mean λ = max_{C cycle} W(C)/|C|, where W(C) is the sum of edge weights along the cycle C and |C| is its length. Since every closed walk decomposes into cycles, every closed walk Γ satisfies W(Γ) ≤ λ |Γ|. Define the normalized entropic operator R_τ x = T_τ x − λ_τ 1, where 1 is the vector of all ones. Then R_τ^k x = T_τ^k x − k λ_τ 1, and also R_τ x = τ log((S_τ/ρ_τ) exp(x/τ)), hence R_τ^k x = τ log((S_τ/ρ_τ)^k exp(x/τ)). The main theorem, called the Tropical–Entropic Transfer Certificate, assumes (H1), (H2), and (H3). It has several parts. First, the smoothing bound: for every x ∈ ℝ^n, 0 ≤ T_τ x − T_0 x ≤ τ log d · 1 entrywise. Second, the iteration comparison: for every k ≥ 0, T_0^k x ≤ T_τ^k x ≤ T_0^k x + k τ log d · 1 entrywise. Third, the tropical asymptotic rate: for every x ∈ ℝ^n and every i, lim_{k → ∞} (T_0^k x)_i / k = λ. A common overstatement is that W_k(i,j)/k → λ for every pair i,j under strong connectivity alone; this fails for periodic graphs, which may lack walks of certain exact lengths between certain pairs. The correct statement is for (T_0^k x)_i after maximizing over starting vertices. Fourth, the entropic asymptotic rate: for every x ∈ ℝ^n and every i, lim_{k → ∞} (T_τ^k x)_i / k = λ_τ. Fifth, the spectral gap: λ ≤ λ_τ ≤ λ + τ log d. Sixth, the entropic eigenvector: there exists x_τ ∈ ℝ^n, unique modulo addition of a scalar multiple of 1, such that T_τ x_τ = λ_τ + x_τ. Explicitly, if u_τ > 0 is a Perron–Frobenius eigenvector of S_τ, then x_τ = τ log u_τ. Seventh, the exponential transient certificate in exact form. Let p be such that S_τ^p > 0. Define M_p = max_{i,j} (S_τ^p)_ij, m_p = min_{i,j} (S_τ^p)_ij, κ_p = M_p/m_p ≥ 1, β_p = (κ_p−1)/(κ_p+1) ∈ [0,1). Case A: β_p > 0. Set θ = β_p^{1/p} ∈ (0,1). Then for every x ∈ ℝ^n there exists c_τ(x) ∈ ℝ such that for every k ≥ 0, ||T_τ^k x − (k λ_τ + x_τ + c_τ(x)1)||∞ ≤ C_x θ^k, with the explicit constant C_x = θ^{−(p−1)} δ(x,x_τ)(1 + 1/(1−θ)), where δ(x,y) = max_i (x_i−y_i) − min_i (x_i−y_i). Case B: β_p = 0. Then κ_p = 1, so S_τ^p = c 1 1^T for some c > 0. One may choose x_τ = 0. Define c_τ(x) = τ log((1/n) Σ_j exp(x_j/τ)). Then R_τ^p x = c_τ(x)1, and for every k ≥ p, R_τ^k x = c_τ(x)1. Therefore the error is exactly zero for k ≥ p. To express the result in exponential form for all k ≥ 0, choose any θ ∈ (0,1), for example θ = 1/2, and set C_x = max_{0 ≤ k < p} θ^{−k} ||R_τ^k x − c_τ(x)1||∞. Then for all k ≥ 0, ||T_τ^k x − (k λ_τ + c_τ(x)1)||∞ ≤ C_x θ^k. A closed-form but slightly more conservative choice is θ = 1/2 and C_x = 3 · 2^{p−1} δhat, where δhat ≥ δ(x,0) = max_i x_i − min_i x_i. Then the same bound holds. Note that p may be chosen from the support graph alone and does not depend on τ; however, the constants κ_p, θ, and C_x do depend on τ through S_τ and through the choice of p. Eighth, the tropical transient certificate: for every k ≥ 0, ||T_τ^k x − (k λ + x_τ + c_τ(x)1)||∞ ≤ C_x θ^k + k τ log d. The term k τ log d is unavoidable in general if one uses λ instead of λ_τ. Ninth, the cheap tropical certificate: there exists a constant B_x < ∞, depending on G, λ, and x but not on τ or k, such that for every k ≥ 0, ||T_τ^k x − k λ 1||∞ ≤ B_x + k τ log d. This certificate does not require x_τ, κ_p, or Birkhoff contraction, but it is weaker because of the accumulated term k τ log d. The proofs proceed as follows. For the smoothing bound, fix i and set M_i = (T_0 x)_i = max_{j ∈ J_i}(a_ij + x_j). Since J_i is nonempty, exp(M_i/τ) ≤ Σ_{j ∈ J_i} exp((a_ij + x_j)/τ) ≤ |J_i| exp(M_i/τ) ≤ d exp(M_i/τ). Taking τ log gives M_i ≤ (T_τ x)_i ≤ M_i + τ log d. Therefore 0 ≤ (T_τ x)_i − (T_0 x)_i ≤ τ log d for every i. Both T_τ and T_0 are monotone and additively homogeneous: if x ≤ y entrywise then T_τ x ≤ T_τ y and T_0 x ≤ T_0 y; and for every c ∈ ℝ, T_τ(x+c1)=T_τ x+c1 and T_0(x+c1)=T_0 x+c1. For the iteration comparison, let c = τ log d and prove by induction T_0^k x ≤ T_τ^k x ≤ T_0^k x + k c 1. The case k=0 is trivial. For the lower bound, by monotonicity and the smoothing bound, T_τ^{k+1}x = T_τ(T_τ^k x) ≥ T_τ(T_0^k x) ≥ T_0(T_0^k x) = T_0^{k+1}x. For the upper bound, by additive homogeneity and monotonicity, T_τ^{k+1}x ≤ T_τ(T_0^k x + k c 1) = T_τ(T_0^k x) + k c 1. Then by the smoothing bound, T_τ(T_0^k x) ≤ T_0(T_0^k x) + c 1 = T_0^{k+1}x + c 1. Thus T_τ^{k+1}x ≤ T_0^{k+1}x + (k+1)c 1, completing the induction. For the tropical asymptotic rate, for i,j ∈ V and k ≥ 0 let W_k(i,j) be the maximum weight of a walk of length k from j to i, with W_k(i,j) = −∞ if no such walk exists. Then (T_0^k x)_i = max_j {W_k(i,j)+x_j}. Define B_λ = max_{P path}(W(P)−λ|P|), where the maximum is over all simple paths, including the empty path. Hence B_λ ≥ 0 and B_λ < ∞ because there are finitely many simple paths and all weights are finite. For the upper bound, let π be any walk of length k. Erase closed subwalks recursively until a simple path P remains. The erased pieces are closed walks, and each closed walk decomposes into cycles. Since every cycle C satisfies W(C) ≤ λ|C|, every closed walk Γ satisfies W(Γ) ≤ λ|Γ|. Therefore W(π) ≤ W(P)+λ(k−|P|) = λk+(W(P)−λ|P|) ≤ λk+B_λ. Consequently, (T_0^k x)_i ≤ λk+B_λ+max_j x_j, so limsup_{k→∞}(T_0^k x)_i/k ≤ λ. For the lower bound, choose a simple critical cycle C* with length m and mean weight λ. Label its vertices cyclically as c_0,c_1,...,c_{m−1}, with edges c_r → c_{r+1 mod m}. Set v_0=c_0. For t=0,1,...,m−1, let σ_t be the weight of the path of length t on C* ending at v_0, starting from c_{−t mod m}. Put σ_0=0. Define M_C = max_{0≤t<m}|σ_t| < ∞. By strong connectivity, for each target vertex i there exists a simple path P_i from v_0 to i. Let ℓ_i=|P_i| ≤ n−1 and w_{P_i}=W(P_i). For k ≥ ℓ_i+m−1, choose t_k ∈ {0,...,m−1} such that t_k ≡ k−ℓ_i mod m, and set q_k=(k−ℓ_i−t_k)/m ≥ 0. Construct a walk π_k of length k ending at i: start at c_{−t_k mod m}, walk t_k steps along C* to v_0, traverse the full cycle C* q_k times, and then follow P_i from v_0 to i. Its length is t_k+q_k m+ℓ_i=k. Its weight satisfies W(π_k) ≥ σ_{t_k}+q_k m λ+w_{P_i} ≥ −M_C+λ(k−ℓ_i−t_k)+w_{P_i}. Thus W(π_k) ≥ λk − [λ(ℓ_i+t_k)+M_C−w_{P_i}]. Define B_low = max_i max_{0≤t<m} max{0, λ(ℓ_i+t)+M_C−w_{P_i}}. This is finite because m≤n, ℓ_i≤n−1, M_C<∞, and all weights are finite. Then W(π_k) ≥ λk−B_low. Since π_k ends at i and starts at some vertex j_k, (T_0^k x)_i ≥ W(π_k)+x_{j_k} ≥ λk−B_low+min_j x_j. Therefore liminf_{k→∞}(T_0^k x)_i/k ≥ λ. Combining upper and lower bounds gives lim_{k→∞}(T_0^k x)_i/k = λ. For the entropic asymptotic rate, use the classical Perron–Frobenius root convergence lemma: if S ≥ 0 is irreducible and z > 0, then for every i, lim_{k→∞}(S^k z)_i^{1/k} = ρ(S). Irreducibility is sufficient; primitivity is not required for this root-convergence statement. By (H2), the support graph is strongly connected, hence S_τ is irreducible. Let z = exp(x/τ) > 0. Then T_τ^k x = τ log(S_τ^k z). By the lemma, lim_{k→∞}(S_τ^k z)_i^{1/k} = ρ_τ. Taking τ log gives lim_{k→∞}(T_τ^k x)_i/k = τ log ρ_τ = λ_τ. For the spectral gap, from the iteration comparison, T_0^k x ≤ T_τ^k x ≤ T_0^k x + k τ log d · 1. Divide by k: (T_0^k x)/k ≤ (T_τ^k x)/k ≤ (T_0^k x)/k + τ log d · 1. Let k→∞ and use the tropical and entropic rate limits to obtain λ ≤ λ_τ ≤ λ+τ log d. An alternative proof via Collatz–Wielandt is available: for a nonnegative irreducible matrix S, ρ(S)=max_{v>0} min_i (Sv)_i/v_i = min_{v>0} max_i (Sv)_i/v_i. Apply with S=S_τ and v=exp(x/τ). For each i, (S_τ v)_i/v_i = Σ_{j∈J_i} exp((a_ij+x_j−x_i)/τ). The min–max characterization then yields, after taking τ log, the same two-sided bound λ ≤ λ_τ ≤ λ+τ log d, using only the elementary log-sum-exp inequalities max ≤ LSE ≤ max+log d. For the existence of the entropic eigenvector, under (H3), S_τ is primitive. By Perron–Frobenius, there exists u_τ > 0, unique up to positive scalar multiplication, such that S_τ u_τ = ρ_τ u_τ. Define x_τ = τ log u_τ. Then (T_τ x_τ)_i = τ log(S_τ exp(x_τ/τ))_i = τ log(S_τ u_τ)_i = τ log(ρ_τ u_{τ,i}) = λ_τ+x_{τ,i}. Hence T_τ x_τ = λ_τ+x_τ. Uniqueness modulo additive constants follows from uniqueness of