Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?

The revised conjecture is true, even under relaxed constraints on $S$ and $t$they may be arbitrary integer vectors (as long as the set $S$ is finite). Notice that if we arrange the vectors from $S$ into a matrix, the question simply asks about the solvability of the linear system $$Sx=t$$ in the integers, hence I will formulate the problem as such below.

Proposition: Let $S\in\mathbb Z^{k\times n}$ and $t\in\mathbb Z^k$. Then the linear system $Sx=t$ is solvable in $\mathbb Z$ if and only if it is solvable in $\mathbb Z/q\mathbb Z$ for all prime powers $q$.

This can be proved in at least two ways.

Proof 1:

For any prime $p$, the solvability of the system modulo each $p^m$ implies that it is solvable in the ring of $p$-adic integers $\mathbb Z_p$. (There is a minor problem in that the solutions are not unique, hence given solutions mod $p^m$ and mod $p^{m'}$ need not be compatible. This can be sorted out e.g. using the compactness of $\mathbb Z_p$, or using Knigs lemma.)

Consequently, the system is also solvable in the product $$\hat{\mathbb Z}=\prod_{p\text{ prime}}\mathbb Z_p,$$ i.e., the ring of profinite integers. I claim that this implies its solvability in $\mathbb Z$.

Notice that solvability of the system (i.e., $\exists x\,Sx=t$) is expressible as a (primitive positive) first-order sentence in the language of abelian groups, augmented with a constant $1$ so that we can define $t$. Now, one can check that the complete first-order theory of the structure $(\mathbb Z,+,1)$ can be axiomatized as follows (its an order-free version of Presburgers arithmetic, or rather, of the theory of $\mathbb Z$-groups):

1. the theory of torsion-free abelian groups,

2. the axioms $\forall x\,px\ne1$ for each prime $p$,

3. the axioms $\forall x\,\exists y\,(x=py\lor x=py+1\lor\dots\lor x=py+(p-1))$ for each prime $p$.

However, all these axioms hold in $\hat{\mathbb Z}$ as well. Thus, the structures $(\mathbb Z,+,1)$ and $(\hat{\mathbb Z},+,1)$ are elementarily equivalent, and the solvability of $Sx=t$ in $\hat{\mathbb Z}$ implies its solvability in $\mathbb Z$.

In fact, we do not actually need the full axiomatization of $(\mathbb Z,+,1)$ above: it is enough to observe that $\hat{\mathbb Z}$ satisfies the axioms 2., which means that $\mathbb Z$ is a pure subgroup of $\hat{\mathbb Z}$, and therefore a pure $\mathbb Z$-submodule.

Proof 2:

There exist matrices $M\in\mathrm{GL}(k,\mathbb Z)$ and $N\in\mathrm{GL}(n,\mathbb Z)$ such that the matrix $S'=MSN$ is in the Smith normal form. Put $t'=Mt$. If $x$ is a solution of $Sx=t$, then $x'=N^{-1}x$ is a solution of $S'x'=t'$, and conversely, if $x'$ is a solution of $S'x'=t'$, then $x=Nx'$ is a solution of $Sx=t$. (This equivalence holds over any commutative ring, as $M,M^{-1},N,N^{-1}$ are integer matrices.)

Thus, we may assume without loss of generality that $S$ is a diagonal matrix (meaning that the excess rows or columns are zero if $k\ne n$). Then the system $Sx=t$ is unsolvable in $\mathbb Z$ only if

1. for some nonzero diagonal entry $s_{ii}$ of $S$, the corresponding entry $t_i$ of $t$ is not divisible by $s_{ii}$, or

2. for some $i$, the $i$th row of $S$ is zero, but $t_i\ne0$.

Let $q$ be a prime power such that $q\nmid t_i$, and, in the first case, $q\mid s_{ii}$. Then the system $Sx=t$ is not solvable in $\mathbb Z/q\mathbb Z$.

Solved by user6959 (14,773 )
Dec 14, 2017 at 15:38