Два точных квадрата

[lel0lel]

nnosipov в сообщении #1415151 писал(а):

$x^6+2x^5+1=y^4-2y^3-y$

Попробую использовать подсказку.
Рассмотрим

$$(a x^3 + b x^2 + c x + d)^2= a^2 x^6+ 2 a b x^5 + (b^2 + 2 a c) x^4 + 2(b c + a d) x^3 + (c^2 + 2 b d) x^2+ 2 c d x +d^2.$$

Выберем коэффициенты таким образом, чтобы при больших значениях $x$ записанное выражение как можно меньше отличалось от $x^6+2x^5-1$. Для этого нужно решить систему ${a = 1, a b = 1, 2 a c + b^2 = 0, b c + a d = 0}$. Возьмём решение $a=1, b=1,c=-1/2,d=-1/2.$ Тогда имеем:

$$x^6+2x^5-1=\left(x^3 + x^2 - \frac{x -1}{2}\right)^2 - \frac{5}{4} x^2 + \frac{1}{2}x - \frac{5}{4}.$$

Поступая аналогично: $y^4-2y^3-y=(y^2-y-1/2)^2-2y-1/4.$ Исходное уравнение принимает вид:

$$\left(2x^3 +2 x^2 - x +1\right)^2 - 5 x^2 + 2x -5=(2y^2-2y-1)^2-8y-1.$$

Таким образом, решена задача

nnosipov в сообщении #1415253 писал(а):

"зажать между двумя квадратами"

если нигде не ошибся в арифметике.

(Оффтоп)

Спасибо за задачу и подсказку к ней

[dmd]

Тогда интереснее вариант, чтоб между квадратами был Пелль:

$(2 x^3 + 2 x^2 - x + 1)^2 - 5 x^2 + 2 x + 3=(2 y^2 - 2 y + 1)^2 - 8 y^2 - 1$.

Обозначим $z=8 y^2 - 5 x^2 + 2 x + 4$.

Перебирая $z$ решаем Пелля $(5 x - 1)^2 - 10 (2 y)^2 = 21 - 5 z$.

Решив Пелля решаем квадратный Туе $A^2-B^2=z$.

Решив Туе проверяем $A=2 y^2 - 2 y + 1$ и $B=2 x^3 + 2 x^2 - x + 1$.

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

[lel0lel]

Всё гораздо проще.
Лемма. Пусть для целых чисел $a, b, с$ верно $a^2-b^2=d$, тогда
1) $d=0$ при $a=b$;
2) $|d|\geq\max({2|a|-1,2|b|-1})$ при $a\ne b$.

Теперь нужно исправить ошибку, которую я допустил -- вместо $x^6+2x^5+1$ использовал $x^6+2x^5-1$. Итак, исходному уравнению $x^6+2x^5+1=y^4-2y^3-y$ соответствует

$$\left(2x^3 +2 x^2 - x +1\right)^2 - 5 x^2 + 2x +3=(2y^2-2y-1)^2-8y-1.$$

В терминах леммы $d=5x^2-2x-8y-4$ и если есть целочисленные решения, то должен выполняться один из двух пунктов. Проверка первого не даёт целых решений. Согласно второму имеем неравенство $|5x^2-2x-8y+4|>2|2x^3 +2 x^2 - x +1|-1$, которое при больших значениях $|x|$ и $y$, выражаемом из исходного уравнения (асимптотически $|y|\sim |x|^{3/2}$), не даёт решений. Таким образом нужно проверить только маленькие значения $|x|$.

Если наводить аккуратность, то следует показать, что уже при $|x|>4$ будет верно $|y|<x^2$.

[nnosipov]

lel0lel в сообщении #1415503 писал(а):

Всё гораздо проще.

Согласен. Но есть еще более простой путь. Более подробно прокомментирую позже, сейчас надо бежать на работу.

Сначала замечание технического характера. Для школьников извлечение квадратного корня из многочлена методом неопределенных коэффициентов --- вполне адекватный способ. Но для студентов и далее можно (и, наверное, нужно) использовать разложение в ряд Лорана в окрестности бесконечности функции, равной квадратному корню из данного многочлена (например, $\sqrt{x^6+2x^5+1}$). Системы компьютерной алгебры делают это автоматически: в Maple соответствующая команда имеет вид

series(sqrt(x^6+2*x^5+1),x=infinity);

Таким образом, "зажать между квадратами" технически очень легко.

Теперь по поводу предложенного lel0lel рассуждения: все хорошо, но есть один неприятный момент --- это использование оценок типа $y \sim |x|^{3/2}$. Эти оценки надо получить, причем желательно в конструктивном виде --- в виде конкретных неравенств. А это лишняя морока. Поэтому предлагаю еще подумать и модернизировать рассуждение (это не слишком сложный, но вполне содержательный еще один шаг).

Во всяком случае, как я понял, данный сюжет не является слишком популярным и наше обсуждение может быть полезным. В конечном итоге мы сможем понять, как можно решать диофантовы уравнения вида $F(x)=G(y)$ при некоторых ограничениях на многочлены $F$ и $G$. Классические примеры типа $y^2=x^4+x^3+x^2+x+1$ --- это простейшие частные случаи и потому хорошо известны.

[lel0lel]

За техническое замечание спасибо (буду в дальнейшем использовать), просто первое что пришло в голову извлекать корень рабоче-крестьянским методом.

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

nnosipov в сообщении #1415269 писал(а):

$$z^2=y^4+8Hy^3-12y^2+4,\eqno(*)$$

есть способ решения за порядка $H^{3/2}$ проверочных тестов.

[nnosipov]

lel0lel в сообщении #1417110 писал(а):

есть способ решения за порядка $H^{3/2}$ проверочных тестов.

Очень интересно! Вы меня серьезно заинтриговали. Напишите, если нетрудно, можно в ЛС.

-- Вт сен 24, 2019 21:27:28 --

lel0lel в сообщении #1417110 писал(а):

опять приходится прибегать к оценкам

Без оценок здесь не обойтись в любом случае. Хочется, чтобы они давались более-менее легко.

[lel0lel]

Рассмотрим решение уравнения в натуральных числах и $H>2$. В этом случае выкладки будут простые и наглядна идея уменьшения числа проверок. Преобразовав уравнение, имеем

$$z^2=(y^2+4Hy-2(4H^2+3))^2+(64H^3+48H)y-64H^4-96H^2-32.$$

Далее замена $z=y^2+4Hy-2(4H^2+3)+x$. Заметим, что при $H>2$ и $y>H^{3/2}$ справедливо $(64H^3+48H)y-64H^4-96H^2-32>0$ и $y^2+4Hy-2(4H^2+3)>0,$ следовательно в этом случае $x>0$. Сделав подстановку и раскрыв скобки:

$$2x(y^2+4Hy-2(4H^2+3))+x^2=(64H^3+48H)y-64H^4-96H^2-32.$$

При $x>8H^{3/2}$ и $y>8H^{3/2}$ уравнение не имеет решений (при желании можно привести более аккуратные оценки). Таким образом, остаётся проверить разрешимость уравнения при $0\leqslant y\leqslant 8H^{3/2}$, а также при $0\leqslant x\leqslant 8H^{3/2}$.

[nnosipov]

lel0lel
А случай $y<0$ Вы рассматривали?

[lel0lel]

Можно попробовать так: пусть $A=\left\lceil H^{3/2}\right\rceil$, тогда

$$z^2=(y^2+4Hy-8H^2-A)^2+\left(2A-12\right) y^2+(8A H+ 64 H^3) y-64H^4-16A H^2-A^2+4.$$

В этом случае предложенная схема должна сработать и для отрицательных $y$. Проверки нужно будет сделать для $|x|<c A$, затем для $|y|<c A$, где $c$ некоторое число.

[nnosipov]

lel0lel в сообщении #1417433 писал(а):

В этом случае предложенная схема должна сработать и для отрицательных $y$.

Как говорит мой преподаватель английского, с этим нужно переспать. (Аккуратно написать все необходимые оценки.) В любом случае это отличная идея. Вчера у меня появилась другая идея (по-видимому, это просто более наглядный вариант Вашей идеи). Дело в том, что мы можем считать, что $z=y^2+4Hy-2(4H^2+3)+x \geqslant 0$ (банальность, но она работает). Иными словами, вместе с уравнением

$$2x(y^2+4Hy-2(4H^2+3))+x^2=(64H^3+48H)y-64H^4-96H^2-32 \eqno(*)$$

у нас есть и неравенство $y^2+4Hy-2(4H^2+3)+x \geqslant 0$. Так вот, это неравенство и отрезает наиболее проблемную (неограниченную влево) часть кривой $(*)$. И тогда действительно

lel0lel в сообщении #1417433 писал(а):

Проверки нужно будет сделать для $|x|<c A$, затем для $|y|<c A$, где $c$ некоторое число.

Таким образом, можно существенно сэкономить при решении уравнения $(*)$.

[nnosipov]

Возвращаясь к уравнению $x^6+2x^5+1=y^4-2y^3-y$, с которым мы до конца, как кажется, не разобрались. Напомню, в чем проблема: хочется избежать явных оценок для значений функции $y=y(x)$, задаваемой уравнением, при больших $x$.

Ну и параллельно еще один вопрос на попутно возникшую вторую тему этого топика: как экономить на вычислениях при решении диофантовых уравнений. Рассмотрим уравнение $xy^2-Hx^2-y=0 \; \eqno(*)$, где $H \geqslant 1$ --- параметр (оно, с точностью до обозначений, взято из статьи Stroeker R., de Weger B. Solving elliptic diophantine equations: the general cubic case // Acta Arith. 1999. Vol. 87. P. 339—365, где предлагалось решать это уравнение сведением его к уравнению Морделла). Решая его как квадратное относительно $x$, мы получим уравнение $y^4-4Hy=z^2$, которое (благодаря идее lel0lel) можно решить за $O(H^{1/2})$ извлечений квадратного корня (для сравнения: стандартный алгоритм требует $O(H)$ таких операций). Вместе с тем, исходное уравнение $\eqno(*)$ можно решить за $O(H^{1/3})$ извлечений квадратного корня. Есть ли более быстрый способ?