すべてのプライマリ・パワー$ q $ $ Rightarrow $ $ t $ span(S)$ over $のバイナリ・ベクトル$ t $の$ span(S)$ over $ mathbb {Z}/q mathbb {Z} $ mathbb {Z} $?

私はバイナリベクトル$ S = {s_1、 ldots、s_n } subseteq {0,1 } ^ k
setminus {1 ^ k } $とターゲットベクトル$ tのセットを持っています= 1 ^ k
$はすべて1のベクトルです。

予想:$ t $は、すべての素数 $ qに対して$ S $/$ mathbb {Z}/q
mathbb {Z} $の要素の線形結合として記述できる$ $ mathbb {Z}
$の線形結合として書くことができます。すなわち$ $ mathbb {Z} $以上の$ t
$に掛け合う整数係数を持つ線形結合があります。

これは本当ですか?それは誰にもよく知られていますか?私はこのトピックに関する文献を検索する際にどのようなキーワードを使用するのかも分からないので、どんな入力も感謝しています。

$ t = sum_ {i = 1} ^ n alpha_i s_i $を整数$ a_i $とすると、任意のモジュラス$
q $に対して同じ和のmod $ q
$を評価すると等しくなります。したがって、整数係数との線形結合は、すべてのモジュラスに対する線形結合の存在を意味する。

Edit 14-12-2017: The conjecture was initially
stronger, asserting the existence of a linear combination over
$mathbb{Z}$ whenever $t$ is a linear combination mod $q$ for all
primes $q$. This would have been easier to exploit in my
algorithmic application, but turns out to be false. Here is a
counter-example. $s_1, ldots, s_n$ are given by the rows of this
matrix:

$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はベクトル$ t =(1,1,1,1,1,1)$が最初の1000個の素数についてこれらのベクトルmod $
q $のスパンにあることを検証した。これは、これが十分であるという証拠として取るすべての素数に対して。しかし、$ mathbb
{Z} $以上の整数線形結合はありません。上記の行列は$ mathbb {R}
$以上の完全なランクを持ち、$(1,1,1,1,1,1
)$は係数$(1/2、1/2、1/2、-1/2、-1/2)を使用しているので、$(s_1、 ldots、s_6)
2、1/2)$である。 ($ t $は、これらのベクトルmod $ 4
$の線形結合として書くことはできませんので、更新された形の予想と矛盾しません。)

ベストアンサー

$ S $と$ t $の緩和された制約のもとでさえ、($ S
$が有限である限り)任意の整数ベクトルであっても、改訂された推測は真です。 $ S
$から行列にベクトルを配置すると、問題は単純に線形システムの解法性について尋ねることに注意してください $$ Sx = t $$
したがって、私は以下のように問題を定式化する。

命題: $ S in mathbb Z ^ {k times n} $と$ t
in mathbb Z ^ k $としましょう。線形システム$ Sx = t $は、すべての素力$ q $に対して$
mathbb Z/q mathbb Z $で解くことができる場合にのみ、$ mathbb Z $で解ける。

これは、少なくとも2つの方法で証明できます。

プルーフ1:

任意のプライム$ p $に対して、各$ p ^ m $を法とするシステムの解法は、 $ p $ -adicの整数 $
mathbb Z_p $。 (解決法が一意ではないという点で小さな問題があるので、mod $ p ^ m $とmod $ p ^
{m ‘} $は互換性がある必要はありません。 mathbb Z_p $、またはKönigの補題を使用します)。

その結果、システムはまた、製品内で解決可能である $$ hat { mathbb Z} = prod_ {p
text {素数}} mathbb Z_p、$$ すなわち、 profinite整数の環。私は、これは$ mathbb Z
$での解法を意味すると主張する。

システムの可解性(すなわち、$ 、Sx = t
$が存在する)は、アーベルグループの言語で(原始的な陽性)一次文として表現可能であり、$ 1 $を一定にすることで定義できる$ t
$。さて、以下のように構造$( mathbb
Z、+、1)$の完全な1次の理論が公理化できることを確認することができます(

  1. ねじれのないアーベル群の理論

プルーフ2:

行列$ S ‘= MSN $が存在するように、行列$ M in mathrm {GL}(k、 mathbb Z)$と$
N in mathrm {GL}(n、 mathbb Z)

スミスの標準形式。 $ 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 $
$なら余分な行または列がゼロであることを意味する)であると仮定してもよい。それから、システム$ Sx = t $は$ mathbb
Z $で解けません。

    $ s_ {ii} $、またはによって割り切れない$ t_i $の$ t_i $は、 >

  1. 一部の$ i $の場合、$ S $の$ i $行はゼロですが、$ t_i ne0 $です。

$ qを$ q nmid t_i $のような素数とし、最初のケースを$ q mid s_ {ii}
$とする。そして、システム$ Sx = t $は$ mathbb Z/q mathbb Z $で解くことができません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です