Система диофантовых уравнений

[alex55555]

Есть система из 64-х уравнений такого типа (не разобрался, как рисовать индексы):

$a_i_j b_k_l c_m_n + d_i_j e_k_l c_m_n + f_i_j g_k_l h_m_n = 0$

В 56 случаях имеем равенство нулю, а в 8 - равенство константам. Переменные участвуют в разных уравнениях по разному, то есть одни могут присутствовать четырежды, другие 16 раз и т.д. Всего переменных 48. Все их значения - целые числа из очень ограниченного диапазона.

Переменных меньше, чем уравнений, но в уравнениях присутствуют произведения, которые всё портят. Как видятся подходы к решению подобных систем уравнений?

[Andrey A]

Если переменных меньше чем уравнений, и они не пропорциональны, то система неразрешима ни в каких числах. Это даже проще чем с Latexом разобраться. Не рисуйте доллары. Индексы - нижнее подчеркивание, выделяете мышью строку и жмёте на кнопку math. Она слева вверху.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[alex55555]

Andrey A в сообщении #1355760 писал(а):

Если переменных меньше чем уравнений, и они не пропорциональны, то система неразрешима ни в каких числах.

Это для систем линейных уравнений. А здесь нелинейные зависимости. Хотя внутри, возможно, через непрослеженные зависимости есть возможность для возникновения линейных комбинаций части уравнений.

Или же поставим вопрос шире - куда гуглить (по каким ключевым словам) по решению систем нелинейных уравнений в целых числах? Они вед тоже диофантовы?

[Andrey A]

alex55555 в сообщении #1356148 писал(а):

Это для систем линейных уравнений

Во первых это неважно. "Переменных меньше чем уравнений" означает "слишком много данных". Это в думе можно не читать законы и не выполнять, а только писать. Во вторых, что у Вас система из 64-х нелинейных уравнений? Серьезно? Википедия тут не поможет. Попробуйте переназначить переменные так, чтобы система стала линейной, отбросив лишние уравнения. Если определитель системы $\Delta $ не равен нулю, и есть хотя бы один ненулевой свободный член, она имеет рациональные решения. Тогда можно начать думать, при каких значениях аргументов дроби окажутся сократимы. Задача из теории сравнений, но при таком количестве переменных, сразу говорю, практически неразрешимая. Если все свободные члены - нули, и получены рациональные решения, можно домножить их на знаменатель и получить целые. Но условием разрешимости однородной системы является $\Delta=0$. Понять при каких значениях аргументов это выполняется - очередная нетривиальная задача. Почитайте хотя бы Серпинского "О решении уравнений в целых числах" чтобы понять, с чем имеете дело.

[alex55555]

Andrey A в сообщении #1356189 писал(а):

alex55555 в сообщении #1356148 писал(а):

Это для систем линейных уравнений

Во первых это неважно.

То есть для нелинейных уравнений так же есть доказательство утверждения о необходимости равенства числа неизвестных числу уравнений?

Andrey A в сообщении #1356189 писал(а):

Попробуйте переназначить переменные так, чтобы система стала линейной, отбросив лишние уравнения.

На вывод одних переменных через другие при помощи 16-ти "свободных" уравнений приведёт к довольно страшным дробям. Хотя я не спорю, в этом направлении можно долго и упорно пытаться что-то сделать. Но именно долго.

В связи с этим подумалось о использовании системы "Максима" для такого вывода. Надо попробовать. Хотя в основе там всё же умножение, которое можно свести к такому виду:

$k(a+b+c+d)(e+f+g+h)=N$

И так 16 раз, со всеми $k$ уникальными и повторяющимися $a,b,c,d,e,f,g,h$. $N$ - целочисленные константы. В такой постановке переменных меньше, чем уравнений. Но за счёт дополнительных зависимостей можно получить те 64 уравнения.

Возможно для такой формы есть некие удобные преобразования, приводящие к линейному виду?

Andrey A в сообщении #1356189 писал(а):

Почитайте хотя бы Серпинского "О решении уравнений в целых числах" чтобы понять, с чем имеете дело.

Спасибо, почитаю.

[JohnDou]

Andrey A в сообщении #1355760 писал(а):

Если переменных меньше чем уравнений, и они не пропорциональны, то система неразрешима ни в каких числах.

Система

$$\left\{ \begin{array}{rcl} x+y &=& 3\\ xy&=&2 \\ 5^x&=& y+3\\ \end{array} \right.$$

Имеет решение $(1;2)$.

alex55555, вы сказали что диапазон решений ограничен. Может имеет смысл решать машинным перебором?

[alex55555]

JohnDou в сообщении #1356213 писал(а):

вы сказали что диапазон решений ограничен. Может имеет смысл решать машинным перебором?

Да, эта идея пришла сразу, но количество переменных - 48. Даже если по 2 значения у каждой переменной, то количество вариантов будет $2^4^8$, что даёт нам число с 15-ю нулями, делённое на 4. Миллион миллиардов итераций. Если итерация равна 1-й наносекунде, то имеем миллион секунд на все операции. Но в наносекунду все проверки никак не уложить. Так что сколько-то лет выйдет на проверку всего лишь для 2-х значений. А значений должно быть хотя бы 5, что даёт $5^4^8$, ну и означает невозможность перебора в принципе при нынешних технологиях.

-- 23.11.2018, 23:45 --

Да, выше про упрощённую постановку неправильно написал - там переменных больше, чем уравнений (те же 48 переменных и 16 уравнений).

[Andrey A]

alex55555 в сообщении #1356201 писал(а):

То есть для нелинейных уравнений так же есть доказательство утверждения о необходимости равенства числа неизвестных числу уравнений?

Это следует из общих соображений. Пусть имеется система, где переменных меньше чем уравнений. Откинем несколько произвольно выбранных уравнений так, чтобы число оставшихся сравнялось с числом переменных. Если ни одно уравнение образовавшейся системы не является следствием другого, то она либо по каким-то причинам неразрешима, либо имеет конкретные решения. Тогда либо изначальная система также неразрешима, либо полученные решения в общем случае будут противоречить откинутым уравнениям. Как раз и пример:

JohnDou в сообщении #1356213 писал(а):

Система

$$\left\{ \begin{array}{rcl} x+y &=& 3\\ xy&=&2 \\ 5^x&=& y+3\\ \end{array} \right.$$

Имеет решение $(1;2)$.

Без третьего уравнения имеем два решения: $x_1=1, y_1=2;x_2=2, y_2=1$, а третье как бы выбирает из двух решений первое :) В принципе оно следует уже из 1-го и 3-го уравнений, так что второе всё равно лишнее, но дело даже не в этом (можно подобрать и ловчее). Дело в том что если вместо двоек и троек подставить другие значения, система станет неразрешима. Об том и речь.

alex55555 в сообщении #1356276 писал(а):

Да, выше про упрощённую постановку неправильно написал - там переменных больше, чем уравнений (те же 48 переменных и 16 уравнений).

Ну вот, с этого надо было начинать. Всё-таки 16 не 64

[Someone]

alex55555 в сообщении #1356201 писал(а):

То есть для нелинейных уравнений так же есть доказательство утверждения о необходимости равенства числа неизвестных числу уравнений?

Такого доказательства нет ни для нелинейных, ни для линейных уравнений. Это утверждение попросту неверно.

Andrey A в сообщении #1356189 писал(а):

Но условием разрешимости однородной системы является $\Delta=0$.

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

Andrey A в сообщении #1356287 писал(а):

так что второе всё равно лишнее

Но заранее это неизвестно.

[Andrey A]

Someone в сообщении #1356306 писал(а):

Это для однородной системы линейных уравнений, в которой число уравнений равно числу неизвестных.

Ну так об этом и речь:

Andrey A в сообщении #1356189 писал(а):

Попробуйте переназначить переменные так, чтобы система стала линейной, отбросив лишние уравнения. Если...

Someone в сообщении #1356306 писал(а):

не условие разрешимости, а условие существования ненулевого решения.

Пусть так.

alex55555 в сообщении #1356201 писал(а):

$k(a+b+c+d)(e+f+g+h)=N$

Это случайно не идеальный кубоид пробивается?

[mihaild]

alex55555 в сообщении #1356276 писал(а):

Да, эта идея пришла сразу, но количество переменных - 48.

Перебор с отсечениями? Или даже попробовать посмотреть, какие переменные нужно зафиксировать, чтобы система стала линейной - их может оказаться сильно меньше 16.

Andrey A, вы можете четко сформулировать предлагаемое утверждение о разрешимости системы? О какой "пропорциональности уравнений" идет речь?
Для линейных уравнений есть ограничение на матрицу системы. Для нелинейных непонятно даже что такое "матрица системы".
(и понятно, что если мы разрешаем в левой части произвольные функции, то ничего интересного про разрешимость системы сказать не получится)

[Andrey A]

О пропорциональности, конечно, можно говорить только в случае линейной системы. В общем случае - об уравнениях, которые логически следуют одно из другого или из других (как в примере выше). О разрешимости произвольной системы речи не было, оговорки не лишние. Речь о неразрешимости системы по причине избыточности данных, и только.

[Tot]

Я бы в качестве первого шага решения рассмотрел бы означенную ТС систему уравнений и ОДЗ всех переменных по модулю 2.
alex55555, что выдаёт решатель задачи выполнимости (SAT-solver) на эту новую систему?
Вдруг повезёт и что-то в ОДЗ упростится.