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 $ {\bf x}\in\mathbb{F}_q^N $ over a known community partition is to be recovered from pooled observations $ {\bf y} = {\bf A}{\bf x} $ over the finite field $ \mathbb{F}_q $. The pooling matrix $ {\bf 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 $ {\bf 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^{*} = (N/(2K))\ln q $ as the solution of $ \alpha_{2K}(d) = 1/q $, at which the two bounds match to order $ \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\infty $. The analysis was restricted to the sparse signal regime $ K\to\infty $, $ K/N\to 0 $, $ \log q = o(K) $, and assumes noiseless observations; no practical decoder is proposed.