Geometrically Constrained Rank Profiles: Exact Adaptive Bayes Risk, Computational Hardness, and Lattice Optimization

This work studies finite-budget observation problems in which only geometrically admissible coordinates of a linear constraint field may be inspected. For a uniform finite-field null hypothesis versus a uniform linear-subspace alternative, the information available from a fixed support is characterized exactly by the surviving dual-constraint rank. The analysis derives an exact equal-prior Bayes error and shows that, when the feasible family of terminal supports is fixed in advance and is identical under both hypotheses, randomized history-dependent adaptation cannot outperform the best deterministic feasible support. For graph-gradient fields, the surviving rank reduces to the cycle-space dimension of the observed subgraph, transforming the statistical design problem into a connected combinatorial optimization problem. On general finite host graphs, the resulting decision problem is NP-complete. In contrast, the square lattice admits an exact finite-budget solution through classical polyomino isoperimetry. Higher-dimensional cubic lattices exhibit a bulk-minus-boundary scaling governed by a codimension-one correction. The work separates the classical coding-theoretic, graph-theoretic, and isoperimetric ingredients from the exact inference-to-optimization reduction developed for the stated observation model. A reproducibility package provides direct finite-graph verification of the combinatorial calculations.