Low-degree hardness of recovery below the Kesten–Stigum threshold in planted 3-SAT

In planted random 3-SAT a uniformly random assignment x* is hidden and about αn clauses satisfied by x* are revealed. When the literal signs carry no single-variable information about x*, the exchangeable plantings form a one-parameter family constructed by Barthel et al., with pairwise literal correlation λ = (4p₀ − 1)/3 and Kesten–Stigum parameter κ = 6αλ². Above κ = 1 a spectral algorithm of Liu, Mohanty and Raghavendra achieves weak recovery in an ordered-triple variant of the model; below it, a result of Kunisky rules out detection by low coordinate-degree functions. We prove the corresponding statement for recovery. For p₀ < 1/4 there are δ, C > 0, depending only on |λ|, such that every function of coordinate degree D ≤ n^δ has squared correlation with x₁*x₂* at most (1/n)(1 + C·D^C/n) Σ_{t=1}^{D} κ^t, for all large n. Below the threshold, low-degree estimators thus do no better than a constant. The bound covers the satisfiable plantings, whose clause laws have zero entries, and their noisy versions, in which each truth pattern is replaced by a uniform one with a fixed probability. For p₀ > p_* ≈ 0.12121, a first-moment argument gives information-theoretic weak recovery in a window of densities below the threshold. The proof uses the Sohn–Wein certificate method. After a gauge transformation the latent variables form a product measure, and the block certificate has a closed form: each block term is the Möbius increment, over sub-blocks, of the posterior means E[x₁*x₂* | signs on the sub-block]. The certificate equations are therefore solvable even when zero entries make the block Gram matrices singular. A Cauchy estimate on a polydisc bounds each increment by |λ|^|B| times a constant depending only on |λ| and the excess of the block B.