Vecteur binaire

J'ai un ensemble de $n$ vecteurs binaires $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ et un vecteur cible $t = 1^k$ qui est le vecteur tout-en-un.

Conjecture: si peut être écrit comme une combinaison linéaire d'éléments de S sur Z / q Z pour toutes les puissances premières q , alors t peut être écrit comme une combinaison linéaire de S sur Z , c'est-à-dire qu'il existe une combinaison linéaire avec des coefficients entiers qui sommes à t sur Z .$t$$S$$\mathbb{Z}/q\mathbb{Z}$ $q$$t$$S$$\mathbb{Z}$$t$$\mathbb{Z}$

Est-ce vrai? Cela vous semble-t-il familier? Je ne sais même pas quels mots clés utiliser lors de la recherche de documentation sur ce sujet, donc toute contribution est appréciée.

Remarquez que l'inverse est certainement vrai: si $t = \sum_{i=1}^n \alpha_i s_i$ pour les entiers $a_i$ , alors évaluer la même somme mod $q$ pour tout module $q$ donne toujours l'égalité; par conséquent, une combinaison linéaire avec des coefficients entiers implique l'existence d'une combinaison linéaire pour tous les modules.

Edit 14-12-2017 : La conjecture était initialement plus forte, affirmant l'existence d'une combinaison linéaire sur $\mathbb{Z}$ chaque fois que $t$ est une combinaison linéaire mod $q$ pour tous les nombres premiers $q$ . Cela aurait été plus facile à exploiter dans mon application algorithmique, mais s'avère faux. Voici un contre-exemple. $s_1, \ldots, s_n$ sont donnés par les lignes de cette matrice:

$\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 a vérifié que le vecteur est dans l'intervalle de ces vecteurs mod q pour les 1000 premiers nombres premiers, ce que je prends comme preuve suffisante que c'est le cas pour tous les nombres premiers. Cependant, il n'y a pas de combinaison linéaire entière sur Z : la matrice ci-dessus a un rang complet sur R et la façon unique d'écrire ( 1 , 1 , 1 , 1 , 1 , 1 ) comme une combinaison linéaire de $t = (1,1,1,1,1,1)$$q$$\mathbb{Z}$$\mathbb{R}$$(1,1,1,1,1,1)$ sur R estutilisantcoefficients ( 1 / 2 , 1 / 2 , 1 / 2 , - 1 / 2 , - 1 / 2 , 1 / 2 ) . (Vous ne pouvez pas écrire t comme une combinaison linéaire de ces vecteurs mod 4 , cependant, cela ne contredit pas la forme mise à jour de la conjecture.)$(s_1, \ldots, s_6)$$\mathbb{R}$$(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$$t$$4$

La conjecture révisée est vraie, même sous des contraintes assouplies sur et t - ils peuvent être des vecteurs entiers arbitraires (tant que l'ensemble S est fini). Notez que si nous organisons les vecteurs de S dans une matrice, la question pose simplement la solvabilité du système linéaire S x = t dans les entiers, donc je formulerai le problème comme tel ci-dessous.$S$$t$$S$$S$

$S\in\mathbb Z^{k\times n}$$t\in\mathbb Z^k$$Sx=t$$\mathbb Z$$\mathbb Z/q\mathbb Z$$q$

Cela peut être prouvé de deux manières au moins.

Preuve 1:

$p$$p^m$$p$ $\mathbb Z_p$$p^m$$p^{m'}$$\mathbb Z_p$

$\exists x\,Sx=t$$1$$t$$(\mathbb Z,+,1)$$\mathbb Z$

1. la théorie des groupes abéliens sans torsion,

2. $\forall x\,px\ne1$$p$

3. $\forall x\,\exists y\,(x=py\lor x=py+1\lor\dots\lor x=py+(p-1))$$p$

$\hat{\mathbb Z}$$(\mathbb Z,+,1)$$(\hat{\mathbb Z},+,1)$$Sx=t$$\hat{\mathbb Z}$$\mathbb Z$

$(\mathbb Z,+,1)$$\hat{\mathbb Z}$$\mathbb Z$$\hat{\mathbb Z}$$\mathbb Z$

Preuve 2:

$M\in\mathrm{GL}(k,\mathbb Z)$$N\in\mathrm{GL}(n,\mathbb Z)$$S'=MSN$$t'=Mt$$x$$Sx=t$$x'=N^{-1}x$$S'x'=t'$$x'$$S'x'=t'$$x=Nx'$$Sx=t$$M,M^{-1},N,N^{-1}$

$S$$k\ne n$$Sx=t$$\mathbb Z$

1. $s_{ii}$$S$$t_i$$t$$s_{ii}$

2. $i$$i$$S$$t_i\ne0$

$q$$q\nmid t_i$ S x = t Z / q $q\mid s_{ii}$$Sx=t$$\mathbb Z/q\mathbb Z$