Binärvektor

Ich habe eine Menge von binären Vektoren S = { s 1 , … , s n } ⊆ { 0 , 1 } k ∖ { 1 k } und einen Zielvektor t = 1 k, der der All- One -Vektor ist.$n$$S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$$t = 1^k$

Vermutung: Wenn als lineare Kombination von Elementen von S über Z / q Z für alle Primzahlen q geschrieben werden kann , dann kann t als lineare Kombination von S über Z geschrieben werden , dh es gibt eine lineare Kombination mit ganzzahligen Koeffizienten die Summen t über Z .$t$$S$$\mathbb{Z}/q\mathbb{Z}$ $q$$t$$S$$\mathbb{Z}$$t$$\mathbb{Z}$

Ist das wahr? Kommt es jemandem bekannt vor? Ich bin mir nicht einmal sicher, welche Schlüsselwörter ich bei der Suche nach Literatur zu diesem Thema verwenden soll. Daher ist jede Eingabe willkommen.

Beachten Sie, dass das Umgekehrte sicherlich gilt: Wenn für ganze Zahlen a i ist , ergibt die Auswertung der gleichen Summe mod q für jeden Modul q immer noch Gleichheit; Daher impliziert eine lineare Kombination mit ganzzahligen Koeffizienten die Existenz einer linearen Kombination für alle Module.$t = \sum_{i=1}^n \alpha_i s_i$$a_i$$q$$q$

Edit 14-12-2017 : Die Vermutung war anfangs stärker und behauptete die Existenz einer linearen Kombination über wenn t eine lineare Kombination mod q für alle Primzahlen q ist . Dies wäre in meiner algorithmischen Anwendung leichter auszunutzen gewesen, stellt sich jedoch als falsch heraus. Hier ist ein Gegenbeispiel. s 1 , … , s n sind durch die Zeilen dieser Matrix gegeben:$\mathbb{Z}$$t$$q$$q$$s_1, \ldots, s_n$

$\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 hat bestätigt, dass der Vektor in der Spanne dieser Vektoren mod q für die ersten 1000 Primzahlen liegt, was ich als ausreichenden Beweis dafür nehme, dass dies für alle Primzahlen der Fall ist. Es gibt jedoch keine ganzzahlige lineare Kombination über Z : Die obige Matrix hat den vollen Rang über R und die einzigartige Schreibweise ( 1 , 1 , 1 , 1 , 1 , 1 ) als lineare Kombination von $t = (1,1,1,1,1,1)$$q$$\mathbb{Z}$$\mathbb{R}$$(1,1,1,1,1,1)$ über R wird unter VerwendungKoeffizienten ( 1 / 2 , 1 / 2 , 1 / 2 , - 1 / 2 , - 1 / 2 , 1 / 2 ) . (Sie können t jedoch nichtals lineare Kombination dieser Vektoren mod 4 schreiben, so dass dies nicht der aktualisierten Form der Vermutung widerspricht.)$(s_1, \ldots, s_6)$$\mathbb{R}$$(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$$t$$4$

Die überarbeitete Vermutung ist wahr, selbst unter entspannten Bedingungen für und t - sie können beliebige ganzzahlige Vektoren sein (solange die Menge S endlich ist). Beachten Sie, dass, wenn wir die Vektoren von S in einer Matrix anordnen , die Frage einfach nach der Lösbarkeit des linearen Systems S x = t in den ganzen Zahlen fragt , daher werde ich das Problem als solches unten formulieren.$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$

Dies kann auf mindestens zwei Arten nachgewiesen werden.

Beweis 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. die Theorie der torsionsfreien abelschen Gruppen,

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$

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