Wektor binarny w ponad dla wszystkich głównych mocy w ponad ?

11

Mam zestaw wektorów binarnych i wektor docelowy który to wektor wszystkich.n nS = { s 1 , , s n } { 0 , 1 } k{ 1 k } S={s1,,sn}{0,1}k{1k}t = 1 kt=1k

Przypuszczenie: Jeśli można zapisać jako liniową kombinację elementów nad dla wszystkich mocy pierwszych , to można zapisać jako liniową kombinację przez , tzn. istnieje kombinacja liniowa ze współczynnikami całkowitymi, które sumują się do przez .t tS SZ / q ZZ/qZ q qt tS SZZ t tZZ

Czy to prawda? Czy komukolwiek to wygląda? Nie jestem nawet pewien, jakich słów kluczowych użyć, szukając literatury na ten temat, więc wszelkie uwagi są mile widziane.

Zauważ, że odwrotność z pewnością się utrzymuje: jeśli dla liczb całkowitych , to ocena tej samej sumy mod dla dowolnego modułu nadal daje równość; stąd kombinacja liniowa ze współczynnikami całkowitymi implikuje istnienie kombinacji liniowej dla wszystkich modułów.t = n i = 1 α i s i t=ni=1αisia iai q qqq

Edytuj 14-12-2017 : Początkowo przypuszczenie było silniejsze, twierdząc, że istnieje kombinacja liniowa nad ilekroć jest modem kombinacji liniowej dla wszystkich liczb pierwszych . Byłoby to łatwiejsze do wykorzystania w mojej aplikacji algorytmicznej, ale okazuje się fałszywe. Oto kontrprzykład. są podane przez wiersze tej macierzy:Z t q q s 1 , , s nZtqqs1,,sn

( 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 )100001010001001001111010111100111111

Mathematica zweryfikowała, że ​​wektor znajduje się w zakresie tych wektorów mod dla pierwszych 1000 liczb pierwszych, co uważam za wystarczający dowód, że tak jest w przypadku wszystkich liczb pierwszych. Jednak nie istnieje całkowita kombinacja liniowa nad : powyższa macierz ma pełną pozycję nad i unikalny sposób pisania jako kombinację liniową z nad używa współczynników . (Nie można zapisać jako liniowej kombinacji tych wektorów modT = ( 1 , 1 , 1 , 1 , 1 , 1 ) Q Z R ( 1 , 1 , 1 , 1 , 1 , 1 ), ( s 1 , ... , s 6 ) R ( 1 / 2 , 1 / 2 , 1 / 2 , - 1 / 2 , - 1t=(1,1,1,1,1,1)qZR(1,1,1,1,1,1)(s1,,s6)R/2,1/2)(1/2,1/2,1/2,1/2,1/2,1/2)tt44, więc nie jest to sprzeczne ze zaktualizowaną formą przypuszczenia).

Bart Jansen
źródło
1
Następujący słabszy parametr zawiera prosty argument zwartości: jest racjonalną liniową kombinacją elementów wtedy i tylko wtedy, gdy jest to kombinacja liniowa nad dla wszystkich, ale skończonych wielu liczb pierwszych . Jest to bardziej ogólne, gdy i mają współczynniki całkowite, a nie tylko . t S G F p p S t 0 , 1tSGFppSt0,1
Emil Jeřábek,
1
Kolejny wynik cząstkowy (ponownie, dla dowolnej liczby całkowitej S , t ): t jest całkowitą kombinacją liniową S iff, jest to kombinacja liniowa w każdym pierścieniu Z / q Z dla liczb pierwszych q . S,ttSZ/qZ q
Emil Jeřábek
3
@BartJansen Właściwie znam dwa różne sposoby, ale żadne nie pasuje do komentarza. Odpowiem później.
Emil Jeřábek
2
@JoshuaGrochow Nie podążam. Jeśli potrzebujesz „dość dużego”, wystarczy wziąć całkiem dużą liczbę pierwszą. Lub całkiem duża moc stałej liczby pierwszej. Żadne z nich nie sugeruje istnienia rozwiązań nad liczbami całkowitymi.
Emil Jeřábek
3
Wyznacznikiem twojego przykładowego systemu jest -4, co sugeruje rozwiązanie dla wszystkich nieparzystych liczb pierwszych.
Kristoffer Arnsfelt Hansen

Odpowiedzi:

8

Skorygowana hipoteza jest prawdziwa, nawet przy łagodnych ograniczeniach S i t - mogą być dowolnymi wektorami całkowitymi (o ile zbiór S jest skończony). Zauważ, że jeśli ułożymy wektory z S w macierz, pytanie po prostu pyta o rozpuszczalność układu liniowego S x = t w liczbach całkowitych, dlatego sformułuję problem jako taki poniżej.StSS

Sx=t

Propozycja: Pozwolić S Z k x n i t Z k . Wtedy układ liniowy S x = t można rozwiązać w Z wtedy i tylko wtedy, gdy można go rozwiązać w Z / q Z dla wszystkich mocy pierwotnych q .SZk×ntZkSx=tZZ/qZq

Można to udowodnić na co najmniej dwa sposoby.

Dowód 1:

Dla każdego głównego p The rozwiązalność systemu modulo każdy s m oznacza, że rozpuszczalny w pierścieniu P -adic całkowite Z P . (Nie jest to problem niewielki, że rozwiązania nie są unikalne, stąd podane rozwiązania mod p m , a mod p m ' nie musi być zgodny. Może to być załatwione na przykład za pomocą zwartości Z p , albo używając lematu König).ppmp ZppmpmZp

W związku z tym, system jest również rozpuszczalny w produkcie Z = Π P  pierwsza Z p , to znaczy pierścień proskończonych całkowitymi . I twierdzą, że oznacza to, jego wypłacalność w Z .

Z^=p primeZp,
Z

Zauważ, że rozwiązalność systemu (tj. xS x = t ) można wyrazić jako (pierwotnie pozytywne) zdanie pierwszego rzędu w języku grup abelowych, powiększone o stałą 1 , abyśmy mogli zdefiniować t . Teraz można sprawdzić, czy pełną teorię pierwszego rzędu struktury ( Z , + , 1 ) można aksjatyzować w następujący sposób (jest to bezobsługowa wersjaarytmetyki Presburgera, a raczej teorii grup Z ):xSx=t1t(Z,+,1)Z

  1. teoria wolnych od skręcania grup abelowych,

  2. aksjomaty xp x 1 dla każdej liczby pierwszej p ,xpx1p

  3. aksjomaty x. Y( x = p y x = p y + 1 x = p y + ( p - 1 ) ) dla każdej liczby pierwszej p .xy(x=pyx=py+1x=py+(p1))p

Jednak wszystkie te aksjomaty trzymać w Z , jak również. Tak więc, struktury ( Z , + , 1 ) i ( Z , + , 1 ) są podstawowo równe, zaś rozwiązywalności S x = t w Z oznacza jego wypłacalność w Z .Z^(Z,+,1)(Z^,+,1)Sx=tZ^Z

W rzeczywistości, w rzeczywistości nie potrzebują pełnej aksjomatyzacji ( Z , + , 1 ) powyżej: wystarczy zauważyć, że Z. spełnia aksjomaty 2., co oznacza, że Z jest czysta podgrupa z Z , a więc czysty Z- podmoduł .(Z,+,1)Z^ZZ^Z

Dowód 2:

Istnieją macierze M G L ( k , Z ) i N G L ( n , Z ) takie, że macierz S = M S N ma postać normalną Smitha . Umieść t = M t . Jeśli x jest rozwiązaniem S x = t , to x = N - 1 x jest rozwiązaniem SMGL(k,Z)NGL(n,Z)S=MSNt=MtxSx=tx=N1xX = t i odwrotnie, jeśli x jest rozwiązaniem S x = t , to x = N x jest rozwiązaniem S x = t . (Ta równoważność obowiązuje nad każdym pierścieniem przemiennym, ponieważ M , M - 1 , N , N - 1 są macierzami całkowitymi).Sx=txSx=tx=NxSx=tM,M1,N,N1

Możemy zatem założyć bez utraty ogólności, że S jest macierzą diagonalną (co oznacza, że ​​nadmiarowe rzędy lub kolumny są zerowe, jeśli k n ). Wtedy system S x = t jest nierozwiązywalny w Z tylko wtedy, gdySknSx=tZ

  1. jakiegoś niezerowe przekątnej wejścia s I I z S , odpowiedni wpis t i o t nie jest podzielna przez e i I lubsiiStitsii

  2. dla niektórych i , i- ty rząd S wynosi zero, ale t i0 .iiSti0

Niech q będzie siłą pierwszą taką, że q t i , w pierwszym przypadku q s i i . Następnie System S x = t jest rozpuszczalny w Z / q Z .qqti

Emil Jeřábek
źródło
1
Dzięki Emil za nauczenie mnie czegoś nowego i interesującego z twoim rozwiązaniem nr 1!
Kristoffer Arnsfelt Hansen
Tak samo. Co ciekawe, drugie rozwiązanie pokazuje, że wystarczy wziąć pod uwagę tylko te liczby pierwsze, które dzielą elementarne dzielniki S (aby obsłużyć wszystkie s i i , w przypadku (1)), a także jedną wystarczająco dużą liczbę (aby obsłużyć przypadek (2)).
Joshua Grochow
Bardzo dziękuję za tę bardzo wnikliwą odpowiedź! Z pewnością potwierdzę twoje spostrzeżenia, jeśli trafią one do gazety.
Bart Jansen,