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

Abstract

We study recovery of nonnegative integer populations on a known graph from complete distance histograms at labelled sensors. For every n ≥ 6, an alternating boundary placement of n−2 sensors is optimal throughout its exact recovery range: its first ambiguous mass is n−3 for even n and n−2 for odd n. Its complete integer kernel has four explicit parameters, giving a four-variable description of every observation fibre. A Laurent-polynomial boundary-response method and an at-most-one-zero-interior-row bound prove these results uniformly. The Lean companion proves the universal kernel, exact threshold, sensor optimality and population-fibre theorem, together with general trade and Cartesian-product results. The paper also supplies the rational normalization and exact decoder, with separate reference-implementation checks. Source, exact certificates, statement rendering and validation reports are included. Paper/data: CC BY 4.0; original code additionally MIT.