Integer solutions to interval linear equations and unique measurement

Abstract:

Every system of $n$ linearly independent homogeneous linear equations in $n+1$ unknowns with coefficients in $\{1,0,-1\}$ has a unique (up to multiplication by $-1$) non-zero solution vector $d= (d_1, d_2, \ldots , d_{n+1} )$ in which the $d_j$’s are integers with no common divisor greater than 1. It is known that, for large $n$, $| \sum d_j |$ can be arbitrarily greater than $2^n$. We prove that if every equation, written as $\sum _A x_i - \sum _B x_i =0$, is such that $A$ and $B$ are intervals of contiguous indices, then $|\sum d_j | \le 2^n$. This confirms conjectures of the author and Fred Roberts that arose in the theory of unique finite measurement.