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

[пианист]

А если попробовать сгруппировать?
Типа такого:
$(i,j,k,l) = I$,
$(m,n) = J$,
$a_{ij}b_{kl} + d_{ij}e_{kl} = x_I$,
$c_{mn} = y_J$,
$f_{ij}g_{kl} = z_I$,
$h_{mn} = t_J$.
Тогда
$x_Iy_J + z_It_J = 0$,
$\frac{x_I}{z_I} = - \frac{t_J}{y_J}$..

[grizzly]

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

$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$

Сейчас известно, что уравнений 16, а переменных 48. Я пытаюсь понять закономерность расстановки индексов, чтобы развернуть данное уравнение в 16 нужных, и пока это у меня не очень получается. Поэтому я предложил бы выписать систему в полном виде. Надеюсь, что на этапе выписывания многое может упроститься (я не удивлюсь, если того уравнения, на которое мы здесь смотрим, в системе вообще не окажется).

[alex55555]

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

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

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

Это следует из общих соображений.

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

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

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

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

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

Я писал про упрощённую постановку, после которой добавляются другие условия. Вот эти новые ограничения и дают нам 64 уравнения. А переменных всё так же 48.

-- 24.11.2018, 17:06 --

mihaild в сообщении #1356315 писал(а):

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

Если понимать перебор с отсечениями как перебор ограниченного количества неизвестных с дальнейшим решением системы уравнений за счёт подстановки вариантов перебора, то да, этот путь перспективен. Но пока я додумался лишь до (оценочно) довольно длительных вычислений. То есть переборное пространство сужено, а потом есть уже аналитическое решение. Но время вычисления получается где-то неделя плюс-минус лапоть. Это плохое время. Хотя и в принципе допустимое. Но сложность здесь такая - вот закончилась неделя ожидания и выдан ответ - решений нет. Что это означает? Возможно решений действительно нет. Возможно в программе допущена ошибка. Возможно в преобразованиях формул допущена ошибка. Возможно вместо перебора 5-ти вариантов нужно было всего-лишь перебрать 6 вариантов и решение было бы найдено. И который из вариантов правильный? В результате требуется новая итерация на очередную неделю, а потом ещё и ещё. И до каких пор? В общем - не очень эффективный вариант.

[Someone]

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

Я писал про упрощённую постановку, после которой добавляются другие условия.

Что значит — "добавляются другие условия"? Вы для "упрощения" системы часть уравнений выкинули, а потом их "добавили"?

[alex55555]

Tot в сообщении #1356351 писал(а):

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

Я не специалист по системам компьютерной алгебры, поэтому так просто понять, что им и как подать, что бы они выдали просто решение, пока не могу. Пытался вчера поиграться с "Максимой", но далее simplify не ушёл. Хотя даже этот simplify выдал в общем-то очевидное преобразование, которое я раньше не видел (ибо лес большой, деревьев много). Пока даже с терминологией там не разобрался, отчасти это английские термины, отчасти даже в русском варианте мне не знакомые. Даже в вашем сообщении не понял, что такое ОДЗ - область допустимых значений? А почему подобласть по модулю два чем-то лучше других?

SAT-Solver вполне гуглится, но относится к разрешимости булевых выражений. Как связать решение уравнений в целых числах с булевыми выражениями?

-- 24.11.2018, 17:22 --

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

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

Я писал про упрощённую постановку, после которой добавляются другие условия.

Что значит — "добавляются другие условия"? Вы для "упрощения" системы часть уравнений выкинули, а потом их "добавили"?

Система порождается от указанной в том сообщении базовой формулы. Она приведена, потому что очень простая. Упрощение в данном контексте следует понимать как показ основы, от чего всё начинается. Но это не полная система ограничений.

-- 24.11.2018, 17:26 --

пианист в сообщении #1356382 писал(а):

А если попробовать сгруппировать?

Выглядит интересно, но суть не понял :)

Тем не менее, в 8-ми уравнениях с правой стороны присутствует ненулевое значение. Его тоже можно включить в переменные, но подойдёт и просто вариант с единицей. То есть ограничения на эту переменную сильнее, чем на остальные.

-- 24.11.2018, 17:40 --

grizzly в сообщении #1356391 писал(а):

Я пытаюсь понять закономерность расстановки индексов, чтобы развернуть данное уравнение в 16 нужных, и пока это у меня не очень получается. Поэтому я предложил бы выписать систему в полном виде.

Да, в полном виде всё проще :)

На самом деле я для себя не представляю систему в том виде, в котором показал выше. Это было упрощение для сокращения количества формул. Плюс тогда я ещё не знал, как индексы ставить (хоть и субъективный момент, но на решение о "упрощении" вопроса повлиял). Там закономерность такая - 64 уравнения получаются сложением произвольно взятых четырёх из упрощенного варианта. При этом плюсы между значениями не важны. Индексы получатся немного другие, но когда писал первое сообщение, интересен был вариант общего решения именно произвольных систем. Сейчас, как я понял из обсуждения, ситуация такая, что общего решения нет. Поэтому да, для выявления частных решений нужна строгая постановка, которую я в первом сообщении не дал.

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

[Someone]

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

Система порождается от указанной в том сообщении базовой формулы. Она приведена, потому что очень простая. Упрощение в данном контексте следует понимать как показ основы, от чего всё начинается. Но это не полная система ограничений.

В общем, я понял, что никто из обсуждающих не понимает, что же именно нужно решать, и пытается что-то советовать в меру своих телепатических способностей. На месте модератора я, возможно, закрыл бы тему. Как бессмысленную.

Давайте Вы напишете систему в полном виде, указав, какие буквы обозначают неизвестные, какие — коэффициенты, какие значения могут принимать индексы и так далее, чтобы всем было понятно, что за систему Вы решаете. Это не означает, что все $64$ уравнения должны быть написаны явно, но вся система должна однозначно восстанавливаться. Например, система из $10$ уравнений гравитационного поля в ОТО записывается в виде $R_{ij}-\frac 12g_{ij}R=\frac{8\pi k}{c^4}T_{ij}$ и восстанавливается по этой записи однозначно, поскольку про каждую букву точно известно, что она обозначает.

[Tot]

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

Даже в вашем сообщении не понял, что такое ОДЗ - область допустимых значений? А почему подобласть по модулю два чем-то лучше других?

SAT-Solver вполне гуглится, но относится к разрешимости булевых выражений. Как связать решение уравнений в целых числах с булевыми выражениями?

Да, область допустимых значений.
По модулю 2 у Вас для перебора ровно 48 бит, а не больше.
Умножение заменяете на И(конъюнкция), сложение - на ИСКЛЮЧАЮЩЕЕ ИЛИ.
И булеву систему даёте решателю задачи выполнимости. Есть надежда, что решение
будет получено быстрее полного перебора.
Если решение булевой системы нет, то нет решения и у Вашей системы.
Если есть, но небольшое число решений, то одинаковое значение у хотя бы одной переменной во всех решениях сужает ОДЗ Вашей системы.

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

[alex55555]

Tot в сообщении #1356549 писал(а):

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

Вы угадали

Там всё сводится к попытке найти коэффициенты, при которых четыре суммы четырёх произведений дадут четыре искомых значения. Ну а остальное лишь обычные преобразования. Выглядит это так:

$$\begin{bmatrix} a & b \\ c & d \end{bmatrix}\cdot \begin{bmatrix} e & f \\ g & h \end{bmatrix}=\begin{bmatrix} ae+bg=r_1 & af+bh=r_2 \\ ce+dg=r_3 & cf+dh=r_4 \end{bmatrix}$$

При этом, например $ae+bg$, можно получить так:

$(a+b)(e+g)=ae+be+ag+bg=p_x$

$p_x-be-ag=ae+bg=r_1$

В таком примере имеем одно умножение для получения $p_x$ и три умножения для получения $r_1$. Для получения же четырёх значений через четыре умножения нужно точно таким же способом скомбинировать четыре результата умножения двух сумм, но с разными коэффициентами. Для начала (если решений нет, то можно расширить суммы до всех элементов всех матриц) можно взять суммы всех элементов из первой матрицы, умножить их на коэффициенты и затем полученную сумму умножить на такую же для второй матрицы:

$$\begin{bmatrix} a & b & c & d \end{bmatrix}\cdot \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}=a_1a+a_2b+a_3c+a_4d$$

$$\begin{bmatrix} e & f & g & h \end{bmatrix}\cdot \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix}=b_1e+b_2f+b_3g+b_4h$$

Перемножение получившихся матриц даст нам вариант подстановки в набор сумм произведений. При изменении коэффициентов $a_i$ и $b_j$ мы получим все возможные варианты для подстановки в комбинацию из четырёх умножений, дающую четыре значения $r_k$. Но сначала для каждого варианта в комбинации нужно задать дополнительный общий коэффициент $k_i_j$ так, что бы сумма произведений давала именно нужный нам $r_k$.

Здесь нужно обратить внимание на практическую сторону задачи. Зачем нужно именно четыре умножения? Потому что 8 существующих (или 7 Штрассеновских) - это дорого с точки зрения вычислительных затрат, либо количества кремния. При этом операции сдвига (умножение на $2^x$) очень дёшевы, дешевле сложения, которое в свою очередь много дешевле умножения. Так же дешёвым является и умножение на константу, например - умножение на 5 даёт сдвиг на два разряда и одно сложение. Поэтому для практических решений подходит множество коэффициентов $a_i$ и $b_j$, особенно, если они будут степенями двойки. То же самое относится и к коэффициенту $k_i_j$, а так же к коэффициенту при $r_i$, который в идеале должен быть равен единице, но так же может быть отрицательным (дешёвая операция смены знака) или степенью двойки (дешёвая операция деления на степень двойки).

Исходя из таких ограничений получаем:

$$\begin{pmatrix}\begin{bmatrix} a & b & c & d \end{bmatrix}\cdot \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}\end{pmatrix}\cdot\begin{pmatrix}\begin{bmatrix} e & f & g & h \end{bmatrix}\cdot \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix}\end{pmatrix}=p$$

При этом сами значения элементов матриц нам не интересны, нам их находить не нужно, а на получаемые далее уравнения они никак не влияют. Поэтому их более не упоминаем.

Введём множество всех вариантов перемножения коэффициентов и обозначим его $P$:

$p \in P$

Далее берём произвольные четыре элемента множества $P$ и получаем составляющие для комбинирования в виде суммы, с целью получить все $r_i$. При этом уберём и из $r_i$ начальные значения из перемножаемых матриц, поскольку в сумме произведений нас будут интересовать лишь коэффициенты при значениях, а не сами значения.

$$\begin{bmatrix} p_1 & p_2 & p_3 & p_4 \end{bmatrix}\cdot \begin{bmatrix} k_1_1 & k_2_1 & k_3_1 & k_4_1 \\ k_1_2 & k_2_2 & k_3_2 & k_4_2 \\ k_1_3 & k_2_3 & k_3_3 & k_4_3 \\ k_1_4 & k_2_4 & k_3_4 & k_4_4 \end{bmatrix}=\begin{bmatrix}r_1 & r_2 & r_3 & r_4\end{bmatrix}=s$$

Из системы $s$ имеем те самые 64 уравнения, о которых говорилось выше. То есть при сложении каждого $p_i$ имеем сумму произведений трёх коэффициентов - a_i_j, b_k_l, k_m_n. После сложения группируем суммы произведений троек коэффициентов и приравниваем их к нулю в 12 случая и к единице в 4-х случаях (но если $r_i$ решено тоже перебирать, то получаем ещё четыре переменных).

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

[alex55555]

Да, забыл момент - для 7-ми умножений аналогичная система имеет множество решений, одно из них нашёл Штрассен. По аналогии следует думать, что и система для 4-х умножений должна иметь решения. Хотя в последнем случае степень свободы системы ограничена, что может оказаться фатальным.

[alex55555]

И если уж думать о расширении использования способа, то для матриц $3\cdot3$ получим 9 умножений вместо 27, для $4\cdot4$ - 16 вместо 64, и так далее. На больших матрицах разница $n^2$ вместо $n^3$, хотя тот же Штрассен предложил как это получить из матрицы $2\cdot2$ для матрицы любого размера. Но там нужны дополнительные преобразования, а если система уравнений будет иметь общее решение, то можно будет просто вычислить коэффициенты и не заниматься преобразованиями. Поэтому общее решение очень интересно.

ЗЫ. Выше ошибку допустил, сказал, что 8 переменных добавится, если учитываем $r_i$, но добавится лишь 4, ведь коэффициенты при членах каждой целевой суммы равны.

[Tot]

Обратил внимание на эту задачу ещё лет десять назад. Но тогда додумался только до перебора в булевом варианте. Там похоже из 48 булевых переменных 4 будут зависимые. Но и даже сейчас переборная задача на 44 переменных, которую нужно посчитать несколько раз, являлась бы хорошей нагрузкой для домашнего суперкомпьютера на несколько TFLOPS.
Переменные в итоге могут оказаться очень большими целыми числами, но и в варианте перемножения матриц по модулю небольшой степени двойки(вплоть до размера машинного слова) задача крайне важна для практической алгоритмики. Может в таком варианте уже кто-нибудь получил результат, а до русскоязычной аудитории ещё информация не дошла?
Продолжаю ждать и пытаться написать собственную программу решателя задачи выполнимости.

[alex55555]

Tot в сообщении #1356948 писал(а):

Там похоже из 48 булевых переменных 4 будут зависимые.

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

Tot в сообщении #1356948 писал(а):

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

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

Потом такой момент - из 48-и реально нужно перебирать лишь 16. Это при $r_i=1$. Если $r_i$\ne$1$, то перебирать нужно уже 20 переменных, из которых 4 должны быть степенями двойки, а остальные произвольными целыми. После выбора 16/20 значений остальные коэффициенты просто вычисляются подстановкой.

Tot в сообщении #1356948 писал(а):

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

Для всего лишь 5-ти значений коэффициентов имеем $5^1^6$ вариантов, это 152 миллиарда - уже хватит прилично подумать. А что бы варианты были в диапазоне $[[phone], -2147483648]$ понадобится $4294967296^1^6$ вариантов.

Tot в сообщении #1356948 писал(а):

Продолжаю ждать и пытаться написать собственную программу решателя задачи выполнимости.

Здесь принципиальный момент - перебором много не наищешься. Было бы очень и очень интересно найти именно аналитическое решение. Ибо вспомним про $4294967296^1^6$ вариантов.

[Tot]

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

Но интересно - почему вы так решили?

Это моё предположение. Матрицу произведения двух матриц 2 на 2 разложим на сумму двух матриц, не меняя слагаемые местами. В каждой из двух полученных матриц обратим внимание на
вертикальную/горизонтальную симметрию/асимметрию. При числе умножений равном числу элементов матрицы надо бы как-то это учитывать. Отсюда предположение о четырёх зависимых переменных.

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

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

Нет. Если не будет решения, то не будет решения полной системы. В противном случае возможны варианты. Да и искать решение кто будет? Находите решение по модулю 2, подставляете его в систему по модулю 4, общую двойку выносите и сокращаете, не забывая сократить её и в модуле. Получаете булеву систему на вторые биты решения, потом аналогичным образом на третьи и так далее на всё количество битов, которое понадобится.

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

Потом такой момент - из 48-и реально нужно перебирать лишь 16.

Нет. У Вас нелинейная система. Выражаем переменную из уравнения по модулю 2, а вдруг там возникает неопределённость при делении на ноль? Тогда эту переменную тоже нужно перебирать. Так что перебор всех переменных.

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

Здесь принципиальный момент - перебором много не наищешься. Было бы очень и очень интересно найти именно аналитическое решение.

Почитайте эту статью про NP задачи на хабре. Подвижки в решении переборных задач без перебора теоретически не исключены. Через диофантовы уравнения можно записать любую задачу, имеющую решение(счётное множество), в том числе гипотезы Била, Ландау и Римана. Только вот с аналитическими решениями дела обстоят почти никак, за исключением нескольких, самых простых случаев.

[alex55555]

Tot в сообщении #1357005 писал(а):

Если не будет решения, то не будет решения полной системы. В противном случае возможны варианты.

Спасибо за уточнение.

Tot в сообщении #1357005 писал(а):

Находите решение по модулю 2, подставляете его в систему по модулю 4, общую двойку выносите и сокращаете, не забывая сократить её и в модуле. Получаете булеву систему на вторые биты решения, потом аналогичным образом на третьи и так далее на всё количество битов, которое понадобится.

Тоже полезным образом "разжевали", спасибо.

Tot в сообщении #1357005 писал(а):

Выражаем переменную из уравнения по модулю 2, а вдруг там возникает неопределённость при делении на ноль? Тогда эту переменную тоже нужно перебирать. Так что перебор всех переменных.

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

Tot в сообщении #1357005 писал(а):

Подвижки в решении переборных задач без перебора теоретически не исключены. Через диофантовы уравнения можно записать любую задачу, имеющую решение(счётное множество), в том числе гипотезы Била, Ландау и Римана. Только вот с аналитическими решениями дела обстоят почти никак, за исключением нескольких, самых простых случаев.

А вот это самое полезное. То есть я всё же надеялся на моё незнание и наличие ответов у кого-то другого. Но теперь вы меня уверили, что надежды беспочвенны. Это отсекает очередную ветвь моего алгоритма перебора

Ну и про SAT-solver тоже полезное предложение. Я как раз читаю на близкую тему (более общую) и постепенно дойду до полного понимания вашего предложения. Но ваша подсказка создала дополнительную мотивацию, показав применимость прочитанного (и самое главное - того, что предстоит прочитать).

Видимо попробую переборы для диапазона $[-1,1]$ (быстро по времени), а потом его можно будет расширить в сторону SAT-solver-а (по сути одна задача, но с изменением операции сложения на логическое или, хотя в полном виде всё же должна работать не с числами). В общем программа перебора у меня в планах, но понятно, на ряду с чтением и прочими занятиями.