Оптимизация целочисленного базиса

[Rak so dna]

Есть базис:

( 47181809400, 10357977778, -39759467544, -217450964419, -135313064995, -95455825392, -94473843294, 526242573073, 564188757142, -18696620057, 262186344706, -164946029767, -1090431330215, 300259094762, -35233336732, -82415146132, 24875358954, 236147584476, 189929668686, -222426877162, 35233336732 ),
( -1572726980, -4811324974, -7483135468, 19767195312, 26520939905, 13615401661, 3023921412, -22401154454, -88113235121, 13058678781, -26698507308, 18226076321, 110514389575, -44747016226, 8899502436, 10472229416, -4088177462, -32825874093, -16639323073, 34181642776, -8899502436 ),
( 22018177720, -1451256879596, -1297763348952, 2939707596618, 5774502694010, 1262459095204, 1362428429443, -6488253578156, -11271184322654, 2074606586609, -3889194022802, 2229178491479, 17759437900810, -8003681185489, 1505046453614, 1326541941384, -53789574018, -5014314183227, -2624887524647, 5186957371754, -1348560119104 ),
( 0, 36891906404, 35627336018, -75476091512, -158288050210, -38807316551, -38499628837, 170408568919, 321961093126, -56517873721, 100522046988, -41969680276, -492369662045, 200257730486, -33507348996, -33507348996, -3384557408, 131993965233, 77306945388, -136149383006, 33507348996 )

необходимо произвести его оптимизацию, в смысле уменьшения модулей чисел. Применяя наивный метод (составлял различные линейные комбинации и сокращал на НОД), за несколько часов насилования ПК, получил вот такое:

( 4, -12, -12, -1, 54, 3, 19, -45, -51, 13, 0, -39, 96, -15, -6, -4, 18, -12, -22, 12, 0 ),
( 0, 6, -12, -13, 15, 22, -3, 51, -96, 12, 12, -54, 45, 39, -18, -4, 12, 1, -19, 0, 4 ),
( -30988, 29398, 27022, 115630, -89273, 59608, -45435, -1, -241717, 618, -145392, 241747, 241718, -152474, 58836, 68732, -88234, -116248, -14173, 118370, -37744 ),
( -68732, 88234, 145392, 116248, -241747, 45435, 14173, -241718, 1, -115630, -118370, 152474, 241717, 89273, -29398, 37744, -58836, -618, -59608, -27022, 30988 )

После чего уменьшение модулей чисел прекратилось, по крайней мере для того диапазона коэффициентов линейных комбинаций, что я использовал $(100-1000)$.

Вопрос в том, можно ли ещё уменьшить числа базиса, и что по этому поводу говорит большая наука.

[dgwuqtj]

Есть алгоритм Ленстры — Ленстры — Ловаса, для редукции таких штук за полиномиальное время. Правда, получится не обязательно наименьший базис, а что-то близкое к нему. И можно руками проверить, получился ли LLL-редуцированный базис.

[Rak so dna]

dgwuqtj спасибо. Скачал PARI/GP, протестировал функцию

qflll(N,3)

на примере — получилось.

Далее ввёл исходный базис, получил:

[-6290907920 17646606508 5694794146 3592689736 -52204290590 15654290093 -26403943189 80803951103 -30491847358 -4283158597 -6271982244 30934625008 -50312103745 21269665582 2090660748 8381568668 -19737267256 690468861 10749653096 577188098 -2090660748]

[-1572726980 -4811324974 -7483135468 19767195312 26520939905 13615401661 3023921412 -22401154454 -88113235121 13058678781 -26698507308 18226076321 110514389575 -44747016226 8899502436 10472229416 -4088177462 -32825874093 -16639323073 34181642776 -8899502436]

[47181809400 -63425835030 -111014139580 -66498781395 181263035425 -17841192290 -17474585620 185425435235 -79733429110 94339127385 61142250730 -81006669215 -105692006125 -100256366210 31781361260 -15400448140 31644473770 -27840345990 35315777910 49871888850 -31781361260]

[-18872723760 95878992596 -5481812778 -186626601298 29113283950 146180813861 56009994702 227938837061 -465149652766 -9562616494 223275298862 -712752473909 237210815705 683639189959 -283073545634 -107714487364 187194553038 196189217792 -202190808563 -217793486084 126587211124]

Ну, такое себе...

Далее ввёл оптимизированный базис, получил:

[0 6 -12 -13 15 22 -3 51 -96 12 12 -54 45 39 -18 -4 12 1 -19 0 4]

[-4 18 0 -12 -39 19 -22 96 -45 -1 12 -15 -51 54 -12 0 -6 13 3 -12 4]

[-37216 63558 104174 -13177 -129581 9345 58963 -194056 134090 -101920 39634 -151175 59966 280756 -107944 -35720 44386 115097 -68308 -143808 72936]

[35720 -44386 -39634 -115097 151175 -58963 68308 -59966 194056 13177 143808 -280756 -134090 129581 -63558 -72936 107944 101920 -9345 -104174 37216]

что даже хуже, чем было...

[dgwuqtj]

Странно... Может, функция требует буквально базис в $\mathbb R^n$?

[dgwuqtj]

Я только сейчас заметил, что вы ещё сокращали на НОД. То есть если $X$ — ваш исходный набор векторов, то вас интересует базис не $\mathbb Z X$, а $\mathbb Q X$, но чтобы векторы оставались целочисленными? Тогда можно сначала найти хоть какой-то базис $\mathbb Z^n \cap \mathbb Q X$ (как модуля над $\mathbb Z$), а потом применять LLL. Я не уверен, что это будет на самом деле маленький базис (по сравнению с, скажем, результатом применения LLL к $\mathbb Z X$), но хотя бы выглядит разумно.

Чтобы получить базис $\mathbb Z^n \cap \mathbb Q X$, можно найти все уравнения на подпространство $\mathbb Q X$ (хоть методом Гаусса), а потом решить эту систему над $\mathbb Z$. Ну или взять матрицу $X$, привести к нормальной форме Смита, сократить числа на диагонали, и проделать все операции над столбцами (которые меняли базис в $\mathbb Z^n$, а не делали операции с векторами из $X$) в обратном порядке.

[Rak so dna]

dgwuqtj в сообщении #1663952 писал(а):

То есть если $X$ — ваш исходный набор векторов, то вас интересует базис не $\mathbb Z X$, а $\mathbb Q X$, но чтобы векторы оставались целочисленными?

Да.

[B@R5uk]

Rak so dna

Пусть вектора вашего целочисленного базиса задаются столбцами

$$X_i,\quad i=\overline{1,\;4}$$

Новый вектор Y улучшенного базиса задаётся так:

$$\sum_{i=1}^{4}b_iX_i=kY$$

где

$$b_i,\quad i=\overline{1,\;4}$$

это целочисленные коэффициенты линейной комбинации, по крайней мере один из которых не равен нулю, а их НОД равен единице. Коэффициент k — это общий целочисленный делитель столбца линейной комбинации. Он может быть единицей, но результирующий столбец Y, как правило, тем лучше, чем меньше величина

$$\frac{1}{k}\max_i\left|b_i\right|$$

Предположим, делитель k делится на простое число p. Тогда в левой части предыдущего равенства нужно смотреть не на сами 8 чисел, а только на их остатки по модулю p. Если не удастся подобрать такие остатки коэффициентов линейной комбинации по модулю p, чтобы ответ равнялся нулю, то никогда не выйдет получить делитель k, делящийся на простое число p. Для малых p это резко отсеивает число перебираемых "в лоб" коэффициентов линейной комбинации. Для больших p это ещё круче отсеивает число перебираемых делителей k, так как только те делители будут походить, которые составлены из степеней простых чисел, которые прошли проверку "на вшивость".

Отсеяв таким образом достаточное количество простых делителей (их не может быть очень много, так как столбцов четыре, то есть свободных переменных четыре, а удовлетворить надо целой куче равенств), можно получить достаточное количество "правильных" делителей k. Их, по идее, должно быть не очень много. Для каждого делителя получение соответствующих ему коэффициентов линейной комбинации не должно быть сложной задачей, так как их остатки по каждому простому делителю числа k известны из предыдущей проверки этого простого числа.

Тут, конечно, встаёт вопрос: "А до какого простого числа проводить проверку?" Или даже "Будут ли всё большие простые делители открывать новые возможности, или же процесс на каком-то моменте встанет и более лучшего результата не будет в принципе?" Если честно, то без понятия. Самому интересно.

Для дальнейшего уменьшения длины цифр можно заметить следующее. Пусть из столбцов базиса составлена матрица

$$\mathbb{X}=\left[X_1,\;X_2,\;X_3,\;X_4\right]$$

тогда если какая-нибудь её строка имеет НОД, отличный от единицы, то либо всю матрицу можно разделить на некоторый делитель этого НОДа, либо этот НОД можно вынести "за скобки" и работать с результатом как раньше. И только в конце внести вынесенные множители "под скобку". Правда, целевая функция, оценивающая качество результата, должна эти вынесенные множители учитывать. Не знаю, на сколько сильно конкретно этот момент поможет, но, возможно, он пригодится.

Отпишитесь, если моя идея как-то улучшила ваш поиск перебором.

[B@R5uk]

Rak so dna, мне кажется у вас в оптимизированном базисе в первом посте ошибка. Первая четвёрка координат векторов исходного базиса совместно делится на 10, в то время как каждый из векторов, не делится ни на 2, не на 5 целиком. Любой порождённый вектор, как бы он не сокращался, должен сохранить это свойство. В улучшенном базисе в первом посте у вас первая четвёрка уже на 5 не делится. Если я что-то недопонял, поправьте меня.

[B@R5uk]

Не, я был не прав. Нельзя выносить общий множитель из строки, более того, иногда может случится так, что столбцы не делились на множитель по отдельности, но результат их линейной комбинации будет делиться. Например:

$$\begin{pmatrix}0&2\\1&3\\3&3\end{pmatrix}\begin{pmatrix}-1\\1\end{pmatrix}=2\begin{pmatrix}1\\1\\0\end{pmatrix}$$

[Rak so dna]

B@R5uk во всех моих постах базис транспонирован (программно мне удобней работать с вектор-строками). Извините, если ввёл в заблуждение. Ошибок точно нет.

Проверить можно так:
Обозначим $A,B,C,D$ — строки исходного базиса, $A',B',C',D'$ — строки оптимизированного базиса,
тогда:
\begin{align*} &A' = A\cdot\frac{3}{78243167255} - B\cdot\frac{151}{78243167255} - C\cdot\frac{3}{78243167255} - D\cdot\frac{164}{78243167255} \\ &B' = A\cdot\frac{7}{78243167255} + B\cdot\frac{112}{78243167255} - C\cdot\frac{7}{78243167255} - D\cdot\frac{50}{15648633451} \\ &C' = -A\cdot\frac{26626}{78243167255} + B\cdot\frac{890517}{78243167255} + C\cdot\frac{10546}{78243167255} + D\cdot\frac{600823}{78243167255} \\ &D' = -A\cdot\frac{106462}{78243167255} + B\cdot\frac{21517}{7113015205} + C\cdot\frac{159}{15648633451} + D\cdot\frac{279166}{78243167255} \end{align*}