Binärvektor

11

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.nS={s1,,sn}{0,1}k{1k}t=1k

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 .tSZ/qZ qtSZtZ

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=i=1nαisiaiqq

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:Ztqqs1,,sn

(100111010111001111000011000101111001)

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)qZR(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.)(s1,,s6)R(1/2,1/2,1/2,1/2,1/2,1/2)t4

Bart Jansen
quelle
1
Die folgende schwächere Eigenschaft gilt für ein einfaches Kompaktheitsargument: ist genau dann eine rationale lineare Kombination von Elementen von S, wenn es sich um eine lineare Kombination über G F p für alle bis auf endlich viele Primzahlen p handelt . Dies gilt allgemeiner, wenn S und t ganzzahlige Koeffizienten haben, nicht nur 0 , 1 . tSGFppSt0,1
Emil Jeřábek 3.0
1
Ein weiteres Teilergebnis (wiederum für eine beliebige ganze Zahl ): t ist eine ganzzahlige lineare Kombination von S, wenn es sich um eine lineare Kombination in jedem Ring Z / q Z für Primzahlen q handelt . S,ttSZ/qZ q
Emil Jeřábek 3.0
3
@BartJansen Ich kenne eigentlich zwei verschiedene Wege, aber keiner passt ganz in einen Kommentar. Ich werde später eine Antwort posten.
Emil Jeřábek 3.0
2
@ JoshuaGrochow Ich folge nicht. Wenn "ziemlich groß" alles ist, was Sie brauchen, würde es ausreichen, eine ziemlich große Primzahl zu nehmen. Oder eine ziemlich große Kraft einer festen Primzahl. Keines davon impliziert die Existenz von Lösungen über die ganzen Zahlen.
Emil Jeřábek 3.0
3
Die Determinante Ihres Beispielsystems ist -4, was eine Lösung für alle ungeraden Primzahlen impliziert.
Kristoffer Arnsfelt Hansen

Antworten:

8

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

Sx=t

SZk×ntZkSx=tZZ/qZq

Dies kann auf mindestens zwei Arten nachgewiesen werden.

Beweis 1:

ppmp ZppmpmZp

Z^=p primeZp,
Z

xSx=t1t(Z,+,1)Z

  1. die Theorie der torsionsfreien abelschen Gruppen,

  2. xpx1p

  3. xy(x=pyx=py+1x=py+(p1))p

Z^(Z,+,1)(Z^,+,1)Sx=tZ^Z

(Z,+,1)Z^ZZ^Z

Beweis 2:

MGL(k,Z)NGL(n,Z)S=MSNt=MtxSx=tx=N1xSx=txSx=tx=NxSx=tM,M1,N,N1

SknSx=tZ

  1. siiStitsii

  2. iiSti0

qqti S x = t Z / q Z.qsiiSx=tZ/qZ

Emil Jeřábek 3.0
quelle
1
Danke Emil, dass du mir mit deiner Lösung # 1 etwas Neues und Interessantes beigebracht hast!
Kristoffer Arnsfelt Hansen
Das Gleiche gilt. Interessanterweise zeigt die zweite Lösung auch, dass es ausreicht, nur die Primzahlen zu berücksichtigen, die die Elementarteiler von teilen (um alle in Fall (1) zu behandeln), sowie eine ausreichend große Zahl (um zu behandeln) Fall (2)). s i iSsii
Joshua Grochow
Vielen Dank für diese sehr aufschlussreiche Antwort! Ich werde Ihre Erkenntnisse mit Sicherheit anerkennen, wenn dies in ein Papier gelangt.
Bart Jansen