Vetor binário

I tem um conjunto de binário vectores S = { s 1 , ... , s n } ⊆ { 0 , 1 } k ∖ { 1 k } e um vector alvo t = 1 k , que é o vector de todos-onas.$n$$S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$$t = 1^k$

Conjectura: Se pode ser escrito como uma combinação linear de elementos de S sobre Z / q Z para todas as potências primárias q , então t pode ser escrito como uma combinação linear de S sobre Z , ou seja, existe uma combinação linear com coeficientes inteiros que somas para t mais de Z .$t$$S$$\mathbb{Z}/q\mathbb{Z}$ $q$$t$$S$$\mathbb{Z}$$t$$\mathbb{Z}$

Isso é verdade? Parece familiar para alguém? Não tenho certeza de quais palavras-chave usar ao pesquisar literatura sobre esse tópico, portanto, qualquer entrada é apreciada.

Observe que o inverso certamente vale: se $t = \sum_{i=1}^n \alpha_i s_i$ para números inteiros $a_i$ , então avalia a mesma soma mod $q$ para qualquer módulo $q$ ainda dá igualdade; portanto, uma combinação linear com coeficientes inteiros implica a existência de uma combinação linear para todos os módulos.

Edit 14-12-2017 : A conjectura era inicialmente mais forte, afirmando a existência de uma combinação linear sobre $\mathbb{Z}$ sempre que $t$ é uma combinação linear mod $q$ para todos os primos $q$ . Isso teria sido mais fácil de explorar em meu aplicativo algorítmico, mas acaba sendo falso. Aqui está um contra-exemplo. $s_1, \ldots, s_n$ são dados pelas linhas desta matriz:

$\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)$

O Mathematica verificou que o vetor está no intervalo desses vetores mod q para os primeiros 1000 primos, o que tomo como evidência suficiente de que esse é o caso de todos os primos. No entanto, não existe uma combinação linear inteira sobre Z : a matriz acima tem uma classificação completa sobre R e a maneira exclusiva de escrever ( 1 , 1 , 1 , 1 , 1 , 1 ) como uma combinação linear de $t = (1,1,1,1,1,1)$$q$$\mathbb{Z}$$\mathbb{R}$$(1,1,1,1,1,1)$ ao longo R é utilizando coeficientes ( 1 / 2 , 1 / 2 , 1 / 2 , - 1 / 2 , - 1 / 2 , 1 / 2 ) . (Você não pode escrever t como uma combinação linear desses vetores, mod 4 , portanto, isso não contradiz a forma atualizada da conjectura.)$(s_1, \ldots, s_6)$$\mathbb{R}$$(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$$t$$4$

A conjectura revisada é verdadeira, mesmo sob restrições relaxadas em e t - elas podem ser vetores inteiros arbitrários (desde que o conjunto S seja finito). Observe que, se organizarmos os vetores de S em uma matriz, a pergunta simplesmente perguntará sobre a solvabilidade do sistema linear S x = t nos números inteiros; portanto, formularei o problema como tal abaixo.$S$$t$$S$$S$

Proposição: Let e t ∈ Z k . Então o sistema linear S x = t é solucionável em Z se e somente se for solucionável em Z / q Z para todas as potências primárias q .$S\in\mathbb Z^{k\times n}$$t\in\mathbb Z^k$$Sx=t$$\mathbb Z$$\mathbb Z/q\mathbb Z$$q$

Isso pode ser provado de pelo menos duas maneiras.

Prova 1:

Para qualquer primo , a solvabilidade do sistema modulo cada p m implica que é solúvel no anel de p números inteiros -adic Z p . (Não é um problema menor em que as soluções não são únicos, as soluções, por conseguinte, dada mod p m e mod p m ' não necessita de ser compatível. Isto pode ser resolvido por exemplo, usando a compacidade de Z p , ou usando Lema de Konig.)$p$$p^m$$p$ $\mathbb Z_p$$p^m$$p^{m'}$$\mathbb Z_p$

Por conseguinte, o sistema também é solúvel no produto Z = Π p  privilegiada Z p , isto é, o anel de números inteiros profinitos . Eu afirmo que isso implica a sua solvabilidade em Z .

Observe que a solvabilidade do sistema (ou seja, $\exists x\,Sx=t$$1$$t$$(\mathbb Z,+,1)$$\mathbb Z$

1. a teoria dos grupos abelianos livres de torção,

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$

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