Finite-field pooling for community state inference: sample complexity bounds at the saturation point

We studied the sample complexity of community state inference, in which a $K$-sparse latent state vector $\mathbf{x}\in {\mathbb{F}}_q^N$ over a known community partition is to be recovered from pooled observations $\mathbf{y}=\mathbf{A}\mathbf{x}$ over the finite field ${\mathbb{F}}_q$. The pooling matrix $\mathbf{A}$ has a constant row weight of $d$, with modeling pools formed as linear combinations of exactly $d$ members. We derived necessary and sufficient conditions on the number of pooled observations $M$. Let ${\alpha }_t(d)$ denote the probability that a row of $\mathbf{A}$ misses a fixed set of size $t$. The lower bound, obtained from Fano's inequality, is governed by ${\alpha }_K(d)$; the upper bound, obtained under maximum a posteriori (MAP) decoding, is governed by ${\alpha }_{2K}(d)$, thus reflecting the worst-case overlap between two candidate supports of total size $2K$. Under the sparse-regime approximation ${\alpha }_{2K}(d)\approx e^{-2Kd/N}$, we identified the asymptotic saturation point $d^{\ast }=(N/(2K))\ln q$ as the solution of ${\alpha }_{2K}(d)=1/q$, at which the two bounds match to order $\mathrm{\Theta }(K{\log }_q(N/K))$ with a multiplicative gap bounded by a constant $C(q)$ that satisfies $C(q)\to 2$ as $q\to \mathrm{\infty }$. The analysis was restricted to the sparse signal regime $K\to \mathrm{\infty }$, $K/N\to 0$, $\log q=o(K)$, and assumes noiseless observations; no practical decoder is proposed.