CSP–Latent Bridge: Random k-SAT Phase Transitions and Characteristic Function Analyticity
Abstract
We establish a formal bridge between classical constraint satisfaction problem (CSP) complexity theory and Latent complexity theory by proving that the Latent Number ρ of a random k-SAT energy landscape equals the partition function analyticity radius ρ_Z. This identity, ρ(α,k) = ρ_Z(α,k), connects the characteristic function analyticity framework (which governs representation complexity) to the Lee-Yang theory of statistical mechanics (which governs phase transitions). We prove that below the satisfiability threshold α < α_c(k), the Latent Number exceeds unity (ρ > 1), implying finite representation size N = O(log(1/ε)/log ρ). At the threshold α = α_c(k), we have ρ = 1 and representation size diverges. The proofs are formalized in the Platonic proof system with 10 verified theorems and 4 domain axioms.