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}$?

Question

I have a set of $n$ binary vectors $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ and a target vector $t = 1^k$ which is the all-ones vector.

Conjecture: If $t$ can be written as a linear combination of elements of $S$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$, then $t$ can be written as a linear combination of $S$ over $\mathbb{Z}$, i.e., there is a linear combination with integer coefficients which sums to $t$ over $\mathbb{Z}$.

Is this true? Does it look familiar to anyone? I'm not even sure what keywords to use when searching for literature on this topic, so any input is appreciated.

Observe that the converse certainly holds: if $t = \sum_{i=1}^n \alpha_i s_i$ for integers $a_i$, then evaluating the same sum mod $q$ for any modulus $q$ still gives equality; hence a linear combination with integer coefficients implies the existence of a linear combination for all moduli.

Edit 14-12-2017: The conjecture was initially stronger, asserting the existence of a linear combination over $\mathbb{Z}$ whenever $t$ is a linear combination mod $q$ for all primes $q$. This would have been easier to exploit in my algorithmic application, but turns out to be false. Here is a counter-example. $s_1, \ldots, s_n$ are given by the rows of this matrix:

$\left( \begin{array}{cccccc} 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 \\ \end{array} \right)$

Mathematica verified that the vector $t = (1,1,1,1,1,1)$ is in the span of these vectors mod $q$ for the first 1000 primes, which I take as sufficient evidence that this is the case for all primes. However, there is no integer linear combination over $\mathbb{Z}$: the matrix above has full rank over $\mathbb{R}$ and the unique way to write $(1,1,1,1,1,1)$ as a linear combination of $(s_1, \ldots, s_6)$ over $\mathbb{R}$ is using coefficients $(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$. (You cannot write $t$ as a linear combination of these vectors mod $4$, though, so it does not contradict the updated form of the conjecture.)

Answer 1

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 König’s 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 (it’s an order-free version of Presburger’s 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$.