11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek supports Monica Dec 13 '17 at 11:04
  • 1
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek supports Monica Dec 13 '17 at 13:27
  • 3
    $\begingroup$ @BartJansen I know two diffent ways, actually, but neither quite fits in a comment. I'll post an answer later. $\endgroup$ – Emil Jeřábek supports Monica Dec 14 '17 at 10:27
  • 2
    $\begingroup$ @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. $\endgroup$ – Emil Jeřábek supports Monica Dec 14 '17 at 10:31
  • 3
    $\begingroup$ The determinant of your example system is -4, which implies a solution for all odd primes. $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 14 '17 at 11:48
8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Thanks Emil for teaching me something new and interesting with your solution #1! $\endgroup$ – Kristoffer Arnsfelt Hansen Dec 14 '17 at 18:52
  • $\begingroup$ 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)). $\endgroup$ – Joshua Grochow Dec 15 '17 at 5:02
  • $\begingroup$ Thanks a lot for this very insightful answer! I will be sure to acknowledge your insights if this finds its way into a paper. $\endgroup$ – Bart Jansen Dec 15 '17 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.