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

11

У меня есть набор из n двоичных векторов S={s1,,sn}{0,1}k{1k} и целевой вектор t=1k который является вектором «все единицы».

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

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

Заметим, что верно и обратное утверждение: если t=i=1nαisi для целых чисел ai , то вычисление той же суммы mod q для любого модуля q все еще дает равенство; следовательно, линейная комбинация с целыми коэффициентами подразумевает существование линейной комбинации для всех модулей.

Изменить 14-12-2017 : гипотеза изначально была сильнее, утверждая существование линейной комбинации по Z всякий раз, когда t является линейной комбинацией mod q для всех простых чисел q . Это было бы проще использовать в моем алгоритмическом приложении, но оказалось ложным. Вот контрпример. s1,,sn задаются строками этой матрицы:

(100111010111001111000011000101111001)

Mathematica проверила, что вектор находится в диапазоне этих векторов mod q для первых 1000 простых чисел, что я считаю достаточным доказательством того, что это имеет место для всех простых чисел. Тем не менее, нет целочисленной линейной комбинации по Z : матрица выше имеет полный ранг по R и уникальный способ записи ( 1 , 1 , 1 , 1 , 1 , 1 ) в виде линейной комбинации (t=(1,1,1,1,1,1)qZR(1,1,1,1,1,1) над R использует коэффициенты ( 1 / 2 , 1 / 2 , 1 / 2 , - 1 / 2 , - 1 / 2 , 1 / 2 ) . (Вы не можете написать t как линейную комбинацию этих векторов mod 4 , хотя, так что это не противоречит обновленной форме гипотезы.)(s1,,s6)R(1/2,1/2,1/2,1/2,1/2,1/2)t4

Барт Янсен
источник
1
Следующее более слабое свойство имеет место в силу простого аргумента компактности: является рациональной линейной комбинацией элементов из S тогда и только тогда, когда она является линейной комбинацией над G F p для всех, кроме конечного числа простых чисел p . Это верно в более общем случае, когда S и t имеют целочисленные коэффициенты, а не только 0 , 1 . tSGFppSt0,1
Эмиль Йержабек
1
Другой частичный результат (опять же, для произвольного целого числа ): t является целочисленной линейной комбинацией S, если она является линейной комбинацией в каждом кольце Z / q Z для простых степеней q . S,ttSZ/qZ q
Эмиль Йержабек
3
@BartJansen Я знаю два разных способа, но ни один из них не подходит для комментария. Я отправлю ответ позже.
Эмиль Йержабек
2
@ JoshuaGrochow Я не подписан. Если все, что вам нужно, это «довольно большое», достаточно взять довольно большое простое число. Или довольно большая сила фиксированного простого числа. Ни один из них не подразумевает существование решений по целым числам.
Эмиль Йержабек
3
Определитель вашей примерной системы равен -4, что подразумевает решение для всех нечетных простых чисел.
Кристоффер Арнсфельт Хансен

Ответы:

8

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

Sx=t

Предложение: Пусть и t Z k . Тогда линейная система S x = t разрешима в Z тогда и только тогда, когда она разрешима в Z / q Z для всех простых степеней q .SZk×ntZkSx=tZZ/qZq

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

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

Для любого простого числа разрешимость системы по модулю каждого p m означает, что она разрешима в кольце p -адических целых чисел Z p . (Существует небольшая проблема в том, что решения не являются уникальными, поэтому данные решения mod p m и mod p m не обязательно должны быть совместимыми. Это можно разобрать, например, используя компактность Z p или лемму Кенига.)ppmp ZppmpmZp

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

Z^=p primeZp,
Z .

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

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

  2. аксиомы для каждого простого числа p ,xpx1p

  3. аксиомы для каждого простого р .xy(x=pyx=py+1x=py+(p1))p

Тем не менее, все эти аксиомы в Z , а также. Таким образом, структуры ( Z , + , 1 )Z^(Z,+,1) и элементарно эквивалентны, и разрешимость S х = т в Z следует его разрешимость в Z .(Z^,+,1)Sx=tZ^Z

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

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

Существуют матрицы и N G L ( n , Z ) такие, что матрица S = M S N находится в нормальной форме Смита . Положим t = M t . Если x является решением S x = t , то x = N - 1 x является решением SMGL(k,Z)NGL(n,Z)S=MSNt=MtxSx=tx=N1x и, наоборот, если x является решением S х ' = т 'Sx=txSx=t , то является решением S x = t . (Эта эквивалентность имеет место для любого коммутативного кольца, поскольку M , M - 1 , N , N - 1 являются целочисленными матрицами.)x=NxSx=tM,M1,N,N1

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

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

  2. для некоторого , то я й строки S равна нулю, но т I0 .iiSti0

Пусть - простая степень, такая что q t iqqti , и, в первом случае, . Тогда система S х = т не разрешимы в Z / д Z .qsiiSx=tZ/qZ

Эмиль Йержабек
источник
1
Спасибо Эмилю за то, что он научил меня чему-то новому и интересному с вашим решением № 1!
Кристоффер Арнсфельт Хансен
То же самое. Кроме того, что интересно, второе решение показывает, что достаточно рассмотреть только те простые числа, которые делят элементарные делители (для обработки всех s i i в случае (1)), а также одно достаточно большое число (для обработки случая (2)). Ssii
Джошуа
Большое спасибо за этот очень проницательный ответ! Я буду уверен, чтобы признать ваши идеи, если это найдет свой путь в газете.
Барт Янсен