<p>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.</p>

<blockquote>
  <p><strong>Proposition:</strong> 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$.</p>
</blockquote>

<p>This can be proved in at least two ways.</p>

<p><strong>Proof 1:</strong></p>

<p>For any prime $p$, the solvability of the system modulo each $p^m$ implies that it is solvable in the ring of <a href="https://en.wikipedia.org/wiki/P-adic_integer" rel="noreferrer">$p$-adic integers</a> $\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.)</p>

<p>Consequently, the system is also solvable in the product
$$\hat{\mathbb Z}=\prod_{p\text{ prime}}\mathbb Z_p,$$
i.e., the ring of <a href="https://en.wikipedia.org/wiki/Profinite_integer" rel="noreferrer">profinite integers</a>. I claim that this implies its solvability in $\mathbb Z$.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Presburger_arithmetic" rel="noreferrer">Presburger’s arithmetic</a>, or rather, of the theory of $\mathbb Z$-groups):</p>

<ol>
<li><p>the theory of torsion-free abelian groups,</p></li>
<li><p>the axioms $\forall x\,px\ne1$ for each prime $p$,</p></li>
<li><p>the axioms $\forall x\,\exists y\,(x=py\lor x=py+1\lor\dots\lor x=py+(p-1))$ for each prime $p$.</p></li>
</ol>

<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$.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Pure_subgroup" rel="noreferrer">pure subgroup</a> of $\hat{\mathbb Z}$, and therefore a <a href="https://en.wikipedia.org/wiki/Pure_submodule" rel="noreferrer">pure $\mathbb Z$-submodule</a>.</p>

<p><strong>Proof 2:</strong></p>

<p>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 <a href="https://en.wikipedia.org/wiki/Smith_normal_form" rel="noreferrer">Smith normal form</a>. 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.)</p>

<p>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</p>

<ol>
<li><p>for some nonzero diagonal entry $s_{ii}$ of $S$, the corresponding entry $t_i$ of $t$ is not divisible by $s_{ii}$, or</p></li>
<li><p>for some $i$, the $i$th row of $S$ is zero, but $t_i\ne0$.</p></li>
</ol>

<p>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$. </p>

CC BY-SA 3.0
2017-12-14T18:52:07.693Z
Thanks Emil for teaching me something new and interesting with your solution #1!
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-12-15T05:02:31.273Z
Ditto. Also, interestingly, the second solutions shows that it suffices to consider only those primes that divide the elementary divisors of $S$ (to handle all the $s_{ii}$, in case (1)), as well as one sufficiently large number (to handle case (2)).
Joshua Grochow
CC BY-SA 3.0
2017-12-15T09:13:25.983Z
Thanks a lot for this very insightful answer! I will be sure to acknowledge your insights if this finds its way into a paper.
Bart Jansen
CC BY-SA 3.0
2017-12-14T15:38:39.953Z
2017-12-14T16:13:48.903Z
2017-12-14T16:13:48.903Z
Emil Jeřábek
<p>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.</p>

<blockquote>
  <p>Conjecture: If $t$ can be written as a linear combination of elements of $S$ over $\mathbb{Z}/q\mathbb{Z}$ for all <strong>prime powers</strong> $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}$. </p>
</blockquote>

<p>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.</p>

<p>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.</p>

<p><strong>Edit 14-12-2017</strong>: 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:</p>

<p>$\left(
\begin{array}{cccccc}
 1 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 \\
 0 &amp; 1 &amp; 0 &amp; 1 &amp; 1 &amp; 1 \\
 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\
 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\
 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 \\
 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 1 \\
\end{array}
\right)$</p>

<p>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.)</p>

CC BY-SA 3.0
2017-12-13T11:04:50.763Z
The following weaker property holds by a simple compactness argument: $t$ is a *rational* linear combination of elements of $S$ if and only if it is a linear combination over $\mathrm{GF}_p$ for *all but finitely many* primes $p$. This is true more generally when $S$ and $t$ have integer coefficients, not just $0,1$.
Emil Jeřábek
CC BY-SA 3.0
2017-12-13T13:27:17.953Z
Another partial result (again, for arbitrary integer $S,t$): $t$ is an integer linear combination of $S$ iff it is a linear combination in each ring $\mathbb Z/q\mathbb Z$ for *prime powers* $q$.
Emil Jeřábek
CC BY-SA 3.0
2017-12-13T17:04:45.043Z
Emil: Could you explain how to obtain the second partial result, based on the assumption t is a linear combination modulo q for each prime power q?
Bart Jansen
CC BY-SA 3.0
2017-12-13T19:22:03.100Z
Are you trying to avoid assuming that $t$ can be written as a linear combination of elements of $S$ modulo $q$ for all prime *powers* $q$?  That seems like the more natural conjecture to me.
D.W.
CC BY-SA 3.0
2017-12-13T22:10:22.650Z
@BartJansen: Chinese Remainder the solutions mod $q$ until you get a solution mod a pretty big number $m$; for sufficiently large $m$, this will then be an integer solution as well (since all the numbers in the linear system of equations are bounded).
Joshua Grochow
CC BY-SA 3.0
2017-12-14T10:27:51.743Z
@BartJansen I know two diffent ways, actually, but neither quite fits in a comment. I'll post an answer later.
Emil Jeřábek
CC BY-SA 3.0
2017-12-14T10:31:38.760Z
@JoshuaGrochow I don't follow. If "pretty big" is all you need, it would suffice to take a pretty big prime. Or a pretty big power of a fixed prime. Neither of these implies the existence of solutions over the integers.
Emil Jeřábek
CC BY-SA 3.0
2017-12-14T11:48:34.627Z
The determinant of your example system is -4, which implies a solution for all odd primes.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-12-14T12:58:44.860Z
@EmilJerabek: ah, of course you are right (my silly mistake). But then it seems to me like all you get is something like a solution in the profinite integers (that is, in the p-adic integers for every p). I'm interested to see how your solution works.
Joshua Grochow
<reference-request><linear-algebra><finite-fields>
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}$?
Bart Jansen
# 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}$?

(Asked by: username_0 on 2017-12-13)

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.)

**Tags:** reference-request, linear-algebra, finite-fields

> **Comments:**
> **username_1**: The following weaker property holds by a simple compactness argument: $t$ is a *rational* linear combination of elements of $S$ if and only if it is a linear combination over $\mathrm{GF}_p$ for *all but finitely many* primes $p$. This is true more generally when $S$ and $t$ have integer coefficients, not just $0,1$.  
> **username_1**: Another partial result (again, for arbitrary integer $S,t$): $t$ is an integer linear combination of $S$ iff it is a linear combination in each ring $\mathbb Z/q\mathbb Z$ for *prime powers* $q$.  
> **username_0**: Emil: Could you explain how to obtain the second partial result, based on the assumption t is a linear combination modulo q for each prime power q?  
> **username_2**: Are you trying to avoid assuming that $t$ can be written as a linear combination of elements of $S$ modulo $q$ for all prime *powers* $q$?  That seems like the more natural conjecture to me.  
> **username_3**: @BartJansen: Chinese Remainder the solutions mod $q$ until you get a solution mod a pretty big number $m$; for sufficiently large $m$, this will then be an integer solution as well (since all the numbers in the linear system of equations are bounded).  
> **username_1**: @BartJansen I know two diffent ways, actually, but neither quite fits in a comment. I'll post an answer later.  
> **username_1**: @JoshuaGrochow I don't follow. If "pretty big" is all you need, it would suffice to take a pretty big prime. Or a pretty big power of a fixed prime. Neither of these implies the existence of solutions over the integers.  
> **username_4**: The determinant of your example system is -4, which implies a solution for all odd primes.  
> **username_3**: @EmilJerabek: ah, of course you are right (my silly mistake). But then it seems to me like all you get is something like a solution in the profinite integers (that is, in the p-adic integers for every p). I'm interested to see how your solution works.  

---

## 1 answers

### Answer by username_1 on 2017-12-14. Score: 8 | Accepted answer

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](https://en.wikipedia.org/wiki/P-adic_integer) $\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](https://en.wikipedia.org/wiki/Profinite_integer). 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](https://en.wikipedia.org/wiki/Presburger_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](https://en.wikipedia.org/wiki/Pure_subgroup) of $\hat{\mathbb Z}$, and therefore a [pure $\mathbb Z$-submodule](https://en.wikipedia.org/wiki/Pure_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](https://en.wikipedia.org/wiki/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$.

> **Comments:**
> **username_4**: Thanks Emil for teaching me something new and interesting with your solution #1!  
> **username_3**: Ditto. Also, interestingly, the second solutions shows that it suffices to consider only those primes that divide the elementary divisors of $S$ (to handle all the $s_{ii}$, in case (1)), as well as one sufficiently large number (to handle case (2)).  
> **username_0**: Thanks a lot for this very insightful answer! I will be sure to acknowledge your insights if this finds its way into a paper.  

---

