Двоичный вектор

У меня есть набор из $n$ двоичных векторов $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ и целевой вектор $t = 1^k$ который является вектором «все единицы».

Гипотеза: если $t$ можно записать как линейную комбинацию элементов $S$ над $\mathbb{Z}/q\mathbb{Z}$ для всех простых степеней $q$ , то $t$ можно записать как линейную комбинацию $S$ над $\mathbb{Z}$ , т. Е. Существует линейная комбинация с целыми коэффициентами который суммирует к $t$ над $\mathbb{Z}$ .

Это правда? Это кому-нибудь знакомо? Я даже не уверен, какие ключевые слова использовать при поиске литературы по этой теме, поэтому любые отзывы приветствуются.

Заметим, что верно и обратное утверждение: если $t = \sum_{i=1}^n \alpha_i s_i$ для целых чисел $a_i$ , то вычисление той же суммы mod $q$ для любого модуля $q$ все еще дает равенство; следовательно, линейная комбинация с целыми коэффициентами подразумевает существование линейной комбинации для всех модулей.

Изменить 14-12-2017 : гипотеза изначально была сильнее, утверждая существование линейной комбинации по $\mathbb{Z}$ всякий раз, когда $t$ является линейной комбинацией mod $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 проверила, что вектор находится в диапазоне этих векторов mod q для первых 1000 простых чисел, что я считаю достаточным доказательством того, что это имеет место для всех простых чисел. Тем не менее, нет целочисленной линейной комбинации по Z : матрица выше имеет полный ранг по R и уникальный способ записи ( 1 , 1 , 1 , 1 , 1 , 1 ) в виде линейной комбинации $t = (1,1,1,1,1,1)$$q$$\mathbb{Z}$$\mathbb{R}$$(1,1,1,1,1,1)$ над R использует коэффициенты ( 1 / 2 , 1 / 2 , 1 / 2 , - 1 / 2 , - 1 / 2 , 1 / 2 ) . (Вы не можете написать t как линейную комбинацию этих векторов mod 4 , хотя, так что это не противоречит обновленной форме гипотезы.)$(s_1, \ldots, s_6)$$\mathbb{R}$$(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$$t$$4$

Пересмотренная гипотеза верна даже при ослабленных ограничениях на и t - они могут быть произвольными целочисленными векторами (при условии, что множество S конечно). Обратите внимание, что если мы упорядочим векторы из S в матрицу, вопрос просто задает вопрос о разрешимости линейной системы S x = t в целых числах, поэтому я сформулирую задачу как таковую ниже.$S$$t$$S$$S$

Предложение: Пусть и t ∈ Z k . Тогда линейная система S x = t разрешима в Z тогда и только тогда, когда она разрешима в Z / q Z для всех простых степеней q .$S\in\mathbb Z^{k\times n}$$t\in\mathbb Z^k$$Sx=t$$\mathbb Z$$\mathbb Z/q\mathbb Z$$q$

Это можно доказать, по крайней мере, двумя способами.

Доказательство 1:

Для любого простого числа разрешимость системы по модулю каждого p m означает, что она разрешима в кольце p -адических целых чисел Z p . (Существует небольшая проблема в том, что решения не являются уникальными, поэтому данные решения mod p m и mod p m ′ не обязательно должны быть совместимыми. Это можно разобрать, например, используя компактность Z p или лемму Кенига.)$p$$p^m$$p$ $\mathbb Z_p$$p^m$$p^{m'}$$\mathbb Z_p$

Следовательно, система также решаемая в произведении Z = Π р  простого Z р , то есть, кольцо проконечных целых чисел . Я утверждаю, что это подразумевает его разрешимость в Z

Обратите внимание, что разрешимость системы (т. ) выражается как (примитивно положительное) предложение первого порядка на языке абелевых групп, дополненное константой 1, чтобы мы могли определить t . Теперь можно проверить, что полная теория первого порядка структуры ( Z , + , 1 ) может быть аксиоматизирована следующим образом (это беспорядочная версияарифметики Пресбургера, а точнее, теории Z- групп):$\exists x\,Sx=t$$1$$t$$(\mathbb Z,+,1)$$\mathbb Z$

1. теория абелевых групп без кручения,

2. аксиомы для каждого простого числа p ,$\forall x\,px\ne1$$p$

3. аксиомы для каждого простого р .$\forall x\,\exists y\,(x=py\lor x=py+1\lor\dots\lor x=py+(p-1))$$p$

Тем не менее, все эти аксиомы в Z , а также. Таким образом, структуры ( Z , + , 1 )$\hat{\mathbb Z}$$(\mathbb Z,+,1)$ и элементарно эквивалентны, и разрешимость S х = т в Z следует его разрешимость в Z .$(\hat{\mathbb Z},+,1)$$Sx=t$$\hat{\mathbb Z}$$\mathbb Z$

На самом деле нам не нужна полная аксиоматизация выше: достаточно заметитьчто Z удовлетворяют аксиомы 2. Это означаетчто Z являетсячистой подгруппойв Z , иследовательно,чистый Z- подмодуль.$(\mathbb Z,+,1)$$\hat{\mathbb Z}$$\mathbb Z$$\hat{\mathbb Z}$$\mathbb Z$

Доказательство 2:

Существуют матрицы и N ∈ G L ( n , Z ) такие, что матрица S ′ = M S N находится в нормальной форме Смита . Положим t ′ = M t . Если x является решением S x = t , то x ′ = N - 1 x является решением $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 ′ является решением S ′ х ' = т $S'x'=t'$$x'$$S'x'=t'$ , то является решением S x = t . (Эта эквивалентность имеет место для любого коммутативного кольца, поскольку M , M - 1 , N , N - 1 являются целочисленными матрицами.)$x=Nx'$$Sx=t$$M,M^{-1},N,N^{-1}$

Таким образом, мы можем предположить без ограничения общности, что - диагональная матрица (что означает, что лишние строки или столбцы равны нулю, если k ≠ n ). Тогда система S x = t неразрешима в Z только в том случае, если$S$$k\ne n$$Sx=t$$\mathbb Z$

1. для некоторой ненулевой диагональной записи из S соответствующая запись t i из t не делится на s i i , или$s_{ii}$$S$$t_i$$t$$s_{ii}$

2. для некоторого , то я й строки S равна нулю, но т I ≠ 0 .$i$$i$$S$$t_i\ne0$

Пусть - простая степень, такая что q ∤ t $q$$q\nmid t_i$ , и, в первом случае, . Тогда система S х = т не разрешимы в Z / д Z .$q\mid s_{ii}$$Sx=t$$\mathbb Z/q\mathbb Z$