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

Mam zestaw wektorów binarnych i wektor docelowy który to wektor wszystkich.$n$$S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$$t = 1^k$

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$$S$$\mathbb{Z}/q\mathbb{Z}$ $q$$t$$S$$\mathbb{Z}$$t$$\mathbb{Z}$

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 = \sum_{i=1}^n \alpha_i s_i$$a_i$$q$$q$

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 $\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 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 , - $t = (1,1,1,1,1,1)$$q$$\mathbb{Z}$$\mathbb{R}$$(1,1,1,1,1,1)$$(s_1, \ldots, s_6)$$\mathbb{R}$$(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$$t$$4$, więc nie jest to sprzeczne ze zaktualizowaną formą przypuszczenia).

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$

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 .$S\in\mathbb Z^{k\times n}$$t\in\mathbb Z^k$$Sx=t$$\mathbb Z$$\mathbb Z/q\mathbb Z$$q$

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$$p^m$$p$ $\mathbb Z_p$$p^m$$p^{m'}$$\mathbb Z_p$

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 ):$\exists x\,Sx=t$$1$$t$$(\mathbb Z,+,1)$$\mathbb Z$

1. teoria wolnych od skręcania grup abelowych,

2. aksjomaty ∀ xp x ≠ 1 dla każdej liczby pierwszej p ,$\forall x\,px\ne1$$p$

3. aksjomaty ∀ x. Y( x = p y ∨ x = p y + 1 ∨ ⋯ ∨ x = p y + ( p - 1 ) ) dla każdej liczby pierwszej p .$\forall x\,\exists y\,(x=py\lor x=py+1\lor\dots\lor 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 .$\hat{\mathbb Z}$$(\mathbb Z,+,1)$$(\hat{\mathbb Z},+,1)$$Sx=t$$\hat{\mathbb Z}$$\mathbb 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ł .$(\mathbb Z,+,1)$$\hat{\mathbb Z}$$\mathbb Z$$\hat{\mathbb Z}$$\mathbb 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 $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$′ 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, gdy$S$$k\ne n$$Sx=t$$\mathbb Z$

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 lub$s_{ii}$$S$$t_i$$t$$s_{ii}$

2. dla niektórych i , i- ty rząd S wynosi zero, ale t i ≠ 0 .$i$$i$$S$$t_i\ne0$

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\nmid t_i$$q\mid s_{ii}$$Sx=t$$\mathbb Z/q\mathbb Z$