2026/06/30 by Hassan Tavakoli
#cs.IT #cs.GT #math.CO #math.IT #math.PR
We establish the exact exponential growth rate of the ρ-th moment of the constrained guesswork Gcoset -- the rank of the true noise vector within its syndrome coset of a random binary linear code under i.i.d. Bernoulli(p) noise: \( limn→∞ (1)/(n)log2\Eb [Gcosetρ] = ρ h(1)/(1+ρ)(p) + ρ(R-1), ρ>0, \) where hα(p) is the binary Rényi entropy and R=k/n is the code rate. The exponent shifts down by exactly ρ(1-R) relative to the unconstrained Arıkan--Merhav exponent, with each of the n(1-R) parity checks contributing equally. Finite-length simulations confirm convergence from below. We further establish: (i)~a transfer theorem expressing the partition-function exponent in terms of an arbitrary weight-enumerator growth rate g(δ); (ii)~the exact exponent for Ln-list (``k-th'') constrained guesswork; and (iii)~a sharp second-order refinement of order ρlog2 n. Beyond the binary i.i.d. setting, we prove a universality theorem: for any code ensemble E whose weight enumerator concentrates at rate gE(δ), the guesswork exponent equals (1+ρ)ψ1/(1+ρ)(gE)-ρ ψ1(gE), where ψα(g)=supδ[g(δ)+αℓ(δ)]. As concrete applications, we instantiate this theorem for the q-ary extension, Λq(ρ)=ρ h(q)1/(1+ρ)(P)+ρ(R-1)log2 q, and for Gallager's regular LDPC ensemble, obtaining a closed-form guesswork exponent via an exact finite-length identity for the ensemble-average weight enumerator.