Mam zestaw wektorów binarnych i wektor docelowy który to wektor wszystkich.n
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
t SS Z / q ZZ/qZ qq tt SS ZZ tt ZZ
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
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 n
( 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 )
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 , - 1
źródło
Odpowiedzi:
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.S t S S
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).p pm p Zp pm pm′ Zp
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 .
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=t 1 t (Z,+,1) Z
teoria wolnych od skręcania grup abelowych,
aksjomaty ∀ xp x ≠ 1 dla każdej liczby pierwszej p ,∀xpx≠1 p
aksjomaty ∀ x. Y( x = p y ∨ x = p y + 1 ∨ ⋯ ∨ x = p y + ( p - 1 ) ) dla każdej liczby pierwszej p .∀x∃y(x=py∨x=py+1∨⋯∨x=py+(p−1)) 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=t Z^ 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^ Z Z^ 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 SM∈GL(k,Z) N∈GL(n,Z) S′=MSN t′=Mt x Sx=t x′=N−1x ′ X ′ = 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).S′x′=t′ x′ S′x′=t′ x=Nx′ Sx=t M,M−1,N,N−1
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, gdyS k≠n Sx=t Z
jakiegoś niezerowe przekątnej wejścia s I I z S , odpowiedni wpis t i o t nie jest podzielna przez e i I lubsii S ti t sii
dla niektórych i , i- ty rząd S wynosi zero, ale t i ≠ 0 .i i S ti≠0
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 .q q∤ti
źródło