Distance-Shell Tomography: Geometric Certificates for Fault-Tolerant Sensing, Moment Compression, and Hypercube Equalization

Abstract

Distance-shell tomography observes an anonymous integer population on a graph through the multiset of its distances to each labelled sensor. Its ambiguities are signed integer trades, and every sensor either detects a trade or is blind to it. We develop this detector calculus into exact theorems for three questions: how much redundancy survives lost reports, how far reports can be compressed, and how few sensors suffice to equalize every outside pair. On the n × n grid, recovery of all populations of mass at most two after one sensor erasure is, once the four corners are instrumented, equivalent to a family of interval cuts, and the minimum number of sensors is exactly ⌈3(n + 1)/2⌉ for every n ≥ 3; without the corner requirement we prove the lower bound ⌈(3n − 4)/2⌉, one larger when n ≡ 2 (mod 4), and exhibit placements attaining it for every 5 ≤ n ≤ 20. All but four monitors may report a single distance sum. On a d-dimensional Hamming product with d ≥ 1 with at least two values per coordinate, a single kth distance moment has population capacity exactly 2^k − 1 for k < d and unrestricted capacity for k ≥ d. On Q_d, its report distance is exactly 2^(d − k) when d ≥ 2k ≥ 2 and the population bound satisfies 2^(k − 1) ≤ h < 2^k. For hypercubes of dimension divisible by four we prove 2^(n − 1) + n/2 − 1 ≤ ξ(Q_n) ≤ 2^(n − 1) + n/2 for the equidistant dimension, refuting a conjectured exponential correction and leaving an additive gap of one; the upper value is exact for n = 8, 12, 16. The same certificate method proves the even bishop-board conjecture γ₂(B_n) = 2n and contradicts three further sourced conjectured statements. Complete proofs, a Lean development whose principal endpoints pass three independent kernels, and reproducible exact computations accompany the results.