Guesswork Under Linear Constraints: Exact Exponent for Coset Decoding

We establish the exact exponential growth rate of the $\rho$-th moment of the constrained guesswork $G_{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{e}\mathrm{t}}$ – the rank of the true noise vector within its syndrome coset of a random binary linear code under i.i.d.\ Bernoulli$(p)$ noise: ${\lim }_{n\to \mathrm{\infty }}\frac{1}{n}{\log }_2\text{Eb}\text{\hspace{0.17em}⁣}\left[G_{\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{e}\mathrm{t}}^{\rho }\right]=\rho h_{\frac{1}{1+\rho }}(p)+\rho (R-1),\rho >0,$ where $h_{\alpha }(p)$ is the binary Rényi entropy and $R=k\mathrm{/}n$ is the code rate. The exponent shifts down by exactly $\rho (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(\delta )$; (ii)~the exact exponent for $L_n$-list (``$k$-th’') constrained guesswork; and (iii)~a sharp second-order refinement of order $\rho {\log }_{2}n$. Beyond the binary i.i.d.\ setting, we prove a universality theorem: for any code ensemble $\mathcal{E}$ whose weight enumerator concentrates at rate $g_{\mathcal{E}}(\delta )$, the guesswork exponent equals $(1+\rho ){\psi }_{1\mathrm{/}(1+\rho )}(g_{\mathcal{E}})-\rho {\psi }_1(g_{\mathcal{E}})$, where ${\psi }_{\alpha }(g)={\sup }_{\delta }[g(\delta )+\alpha \mathrm{\ell }(\delta )]$. As concrete applications, we instantiate this theorem for the $q$-ary extension, ${\mathrm{\Lambda }}_q(\rho )=\rho h_{1\mathrm{/}(1+\rho )}^{(q)}(P)+\rho (R-1){\log }_{2}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.