Distance-Shell Tomography on Graphs: Integer Trades and Optimal Grid Sensing

Abstract

We study recovery of a nonnegative integer population on a known graph from the complete distance histogram at each labelled sensor. Multiplicities are retained, but target identities and correspondence between sensors are unavailable. For every n ≥ 6, exactly n − 2 sensors suffice to distinguish all populations of mass at most two on the n × n Cartesian grid. We prove that an alternating placement on opposite boundaries has integer observation kernel isomorphic to ℤ⁴, with a coordinate-extraction inverse. Its first ambiguous population has mass n − 3 for even n and n − 2 for odd n. The resulting four-variable description of every observation fibre gives an exact decoder and separates fixed rational nullity from a growing integer ambiguity threshold. For general graphs, invisible integer trades characterize bounded recovery, and two sensors admit a distance-level cycle characterization. A full-factor Cartesian-product theorem identifies the lifted kernel as a direct sum of factor kernels and preserves every population recovery bound. The accompanying Lean development proves the general trade and product results and, for every n ≥ 6, the complete integer grid kernel, sharp recovery threshold, optimal sensor count, and four-parameter description of equal-observation populations.