Уравнение Пелля с параметром

[dmd]

(тайминги)

Замерил время выполнения для $l$ в диапазоне 2..10^4:

? \r ppl.gp
? ppl()
time = 1min, 55,441 ms.
?
? \r ppl.gp
? ppl()
time = 24,228 ms.

1 мин. 55 сек. - код с проверкой if(bnfcertify(Q),,

24 сек. - код без bnfcertify.

А в Maple сколько проверка этого диапазона выполняется?

bnfcertify приходится включать, когда коэффициент при $y$ становится достаточно большим, т.к. иначе bnfinit имеет проблемы с вычислением фундаментальной единицы.

[nnosipov]

dmd
В Maple я реализовал тот примитивный алгоритм, который описал выше.

> FloorSqrt:=proc(N)
> local x,x_next;
> if N=0 then return 0 end if;
> x:=iquo(N+1,2); x_next:=iquo(x+iquo(N,x),2);
> while x>x_next do
> x:=x_next; x_next:=iquo(x+iquo(N,x),2)
> end do;
> return x 
> end proc:
> for l from 2 to 10^4 do if FloorSqrt(l+1)^2<>l+1 then for y from 1 to evalf(sqrt(l)) do if
> FloorSqrt((l^2+l)*y^2-l^2+1)^2=(l^2+l)*y^2-l^2+1 then print(l,y); fi; od; fi; od;

На процессоре i3 диапазон $l \in [2,10^4]$ был обработан за 34 с. Можно сделать то же самое на PARI (процедура FloorSqrt там уже есть, естественно) и сравнить. Высокоинтеллектуальные штуки типа

bnfinit

--- стоит ли овчинка выделки?

Для начала хочется хотя бы убедиться, что небольших (до, условно, миллиарда) контрпримеров нет.

[dmd]

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

Пусть $x>1$ и $y>1$ таковы, что

$$ y^4+4(x^2-1)(y^2-1)=z^2 $$

для некоторого $z>1$ (все числа целые). Предположим, что число

$$ D=\frac{y^2-2+z}{2(y^2-1)} $$

оказалось целым. Верно ли, что $D$ является точным квадратом? (Условие целочисленности $D$ существенно: если $x=4$, $y=2$, то $z=14$ и $D=8/3$ --- не точный квадрат. Новый параметр $D$ связан со старым $l$ так: $D=l+1$.)

$x=44,y=3,z=249,D=16$

[nnosipov]

dmd в сообщении #1411077 писал(а):

$x=44,y=3,z=249,D=16$

Здесь $D$ точный квадрат. А хочется наоборот, чтобы $D$ не было точным квадратом. Контрпример нужен.

[Andrey A]

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

Контрпример...

Вряд ли тут есть контрпример. Вернемся к уравнению $x^2-(l^2+l)y^2=-(l^2-1)$ и будем исходить из из предположения, что любой остаток вида $z=p^2-(l^2+l)q^2$, не превышающий по абсолютной величине $l^2+l$ соответствует если не подходящей, то хотя бы промежуточной дроби разложения $\sqrt{l^2+l}$ ($p,q$ вз. просты). Вроде бы это верно для любых разложений, но могу ошибаться. Требуемое разложение можно записать в общем виде: $\sqrt{l^2+l}=l,(2,2l)=\dfrac{1}{0},\dfrac{l}{1},\dfrac{2l+1}{2},...$ Тут выписаны три подходящие дроби, включая нулевую. Этого достаточно, поскольку период из двух знаков. Выпишем соответствующие остатки:

$z_0=1^2-(l^2+l)\cdot 0^2=1$
$z_1=l^2-(l^2+l)\cdot 1^2=-l$
$z_2=(2l+1)^2-(l^2+l)\cdot 2^2=1$

Нужного остатка $1-l^2$ в этом списке нет, значит переходим к промежуточным дробям. Возьмем первым знаком не $l$, а некоторое $u<l$, тогда первой дробью будет $\dfrac{u}{1}$. Запишем уравнение $u^2-(l^2+l)\cdot 1^2=1-l^2$. Получаем $l=u^2-1$ (то, чего хотелось избежать). Второй знак можно не проверять, поскольку там будут положительные остатки, а вот в третьем знаке имеем $2l-1$ вариантов. Тут нужно воспользоваться формулой рекуррентной зависимости для квадратичных вычетов $z_{n+1}=\dfrac{a_{n+1}}{a_n}(a_{n+1}a_n+1)z_n+(a_{n+1}a_n+1)z_{n-1}-\dfrac{a_{n+1}}{a_n}z_{n-2}$ (об этом было здесь). Подставляя в нее $a_{n+1}=u,a_n=2,z_n=1,z_{n-1}=-l,z_{n-2}=1$, получаем уравнение $u^2-(2u+1)l=1-l^2$ или $u^2-2lu+l^2-l-1=0.$ Отсюда $u=l\pm \sqrt{l+1}$ и опять же $l=(u-l)^2-1.$ Если нет ошибки в допущении, это доказательство.

Уравнение $(2)$ из предыдущих постов приводит тем же путем к новому уравнению $(y-d(u+1))^2-d(d-1)(u+1)^2=2-d$. Тут аргументом берем уже $d$, а это не любое число, поскольку $y^2 \equiv 2 \mod d$ (двойка и простые вида $8k \pm 1$ в каноническом разложении https://oeis.org/A057126). Но ведет оно себя похоже, а применив еще раз описанный метод, получаем $d=1$. Всё сходится.

[nnosipov]

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

будем исходить из из предположения, что любой остаток вида $z=p^2-(l^2+l)q^2$, не превышающий по абсолютной величине $l^2+l$ соответствует если не подходящей, то хотя бы промежуточной дроби разложения $\sqrt{l^2+l}$ ($p,q$ вз. просты).

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

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

Уравнение $(2)$ из предыдущих постов приводит тем же путем к новому уравнению $(y-d(u+1))^2-d(d-1)(u+1)^2=2-d$.

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

[Andrey A]

Где-то читал, но теперь уже не вспомню. Там речь шла о том, что если рациональная точка попадает в некий интервал, то является подходящей дробью, и как следствие вот о промежуточных. Доказательство несложное, просто меня эта сторона дела не сильно интересовала. Ну и потом можно взять граничный случай: $p^2-mq^2=1$, "самая точная" дробь $\dfrac{p}{q}=a_1,a_2,...,a_n$. Следующий знак $2a_1$, и тогда "самая неточная" дробь $\dfrac{P}{Q}=a_1,a_2,...,a_n,a_1 \pm 1$ соответствует случаю $P^2-mQ^2=1-m$. Почти самая. Любая другая с непревышающим знаменателем попадает между "точной" и "неточной" и должна быть как минимум промежуточной. Ну, это я так мыслю) Мало ли вспомню, дам ссылку. Слишком уж складно для лжедоказательства.

[nnosipov]

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

Мало ли вспомню, дам ссылку.

Да, было бы неплохо.

[Andrey A]

Было бы неплохо, но ссылку я Вам к сожалению не дам, поскольку допущение ложное. Каюсь. Вот контрпример: $2931^2-913\cdot 97^2=344<913.$
$\dfrac{2931}{97}=30,4,1,1,1,1,1,2=\dfrac{30}{1},\dfrac{121}{4},\dfrac{151}{5},\dfrac{272}{9},\dfrac{423}{14},\dfrac{695}{23},\dfrac{1118}{37},\dfrac{2931}{97},...$ что не совпадает в последних $3$-х знаках с разложением
$\sqrt{913}=30,4,1,1,1,2,1,1,6,7,2,2,19,...$ а хотелось в одном. Таким образом доказательство не интересно, поскольку не описывает всех объектов и, значит, ничего не доказывает. Такие дела.

[wrest]

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

Вот этот кондовый алгоритм. Чтобы проверить, будет ли уравнение $x^2-(l^2+l)y^2=1-l^2$ разрешимо при данном $l>1$, достаточно выяснить, есть ли у этого уравнения решения $(x,y)$, где $1 \leqslant y \leqslant \sqrt{l}$. Последнее решается полным перебором $y$ в указанных границах (для каждого такого $y$ выясняем, будет ли число $(l^2+l)y^2+1-l^2=l^2(y^2-1)+ly^2+1$ точным квадратом).

До $l<10^8$ простых нет.
PARI:

topic136100(lstart,lfinish)={
forprime(l=lstart,lfinish,
   l2=l^2;
   for(y=2,sqrtint(l),
     y2=y^2;
     if(issquare(l2*(y2-1)+l*y2+1),print("l=",l," y=",y)
   )))
}

Запуск:
? topic136100(5,10^8)
? ##
*** last result computed in 5h, 24min, 47,520 ms.
?

-- 19.08.2019, 17:36 --

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

На процессоре i3 диапазон $l \in [2,10^4]$ был обработан за 34 с.

Ну так если идти только по простым $l$, то будет быстрее У меня ноутбук считает диапазон до $10^4$ за $48$ мс

-- 19.08.2019, 18:16 --

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

Это и есть главная интрига. Гипотезу я формулирую так: уравнение

$$x^2-(l^2+l)y^2=-(l^2-1)$$

разрешимо в целых числах $x$, $y$ только если $l$ есть точный квадрат минус один. Здесь нужны компьютерные эксперименты (мне думается, есть контрпример).

Вот код для PARI, который проверяет является ли найденное решение $l$ точным квадратом минус один.

topic136100_2(lstart,lfinish)={
for(l=lstart,lfinish,
   l2=l^2;
   for(y=2,sqrtint(l),
     y2=y^2;
     if(issquare(l2*(y2-1)+l*y2+1), if(!issquare(l+1),print("l=",l," y=",y)
   ))))
}

До $l<10^6$ других $l$ не найдено.

[nnosipov]

wrest
Большое спасибо в любом случае . Я сейчас еще раз попытаюсь объяснить, что мне нужно.

Во-первых, если $l \geqslant 5$ --- простое число, то уравнение $x^2-(l^2+l)y^2=-l^2+1$ действительно не имеет решений $(x,y)$ в целых числах. Это я УМЕЮ ДОКАЗЫВАТЬ. (Иначе и не стал бы помещать как задачу в "Олимпиадный раздел".) Любой желающий это тоже может сделать, доказательство не является сложным и сколь нибудь новым. Это такая мелкая задачка для затравки. Конечно, можно на всякий случай проверить и убедиться, что

wrest в сообщении #1411155 писал(а):

До $l<10^8$ простых нет.

но их и дальше не будет, вот зуб даю

Во-вторых, если $l$ имеет вид $t^2-1$, то уравнение $x^2-(l^2+l)y^2=-l^2+1$ имеет решение $(x,y)=(t,1)$. Давайте такие значения $l$ называть тривиальными. Таким образом, тривиальные значения $l$ --- это $3,8,15,24,35$ и т.д.

В-третьих, а что же нужно? Очень хотелось бы найти хотя бы одно НЕ тривиальное значение $l$, для которого уравнение $x^2-(l^2+l)y^2=-l^2+1$ тоже было бы разрешимым! Для начала можно искать такое $l$ в каком-нибудь разумном диапазоне типа $2 \leqslant l \leqslant 10^8$.

wrest, если бы Вы слегка подправили Вашу PARI-программу (убрали бы там forprime), то на Вашем мощном компьютере мы бы за несколько часов точно узнали бы, есть ли нетривиальные значения $l$ в диапазоне $2 \leqslant l \leqslant 10^8$.

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

Черт, пока набирал, Вы уже сделали. Отлично, большое спасибо! Теперь я могу мучить свой компьютер.

[wrest]

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

есть ли нетривиальные значения $l$ в диапазоне $2 \leqslant l \leqslant 10^8$.

Ну я уже запустил расчет до $10^8$, завтра ответ будет. Так что можете запускать дальше (начиная с $l=10^8$)

[nnosipov]

wrest
Спасибо. Надеюсь, Вы прикинули время выполнения, и оно не зашкаливает.

[wrest]

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

Спасибо. Надеюсь, Вы прикинули время выполнения, и оно не зашкаливает.

До миллиона получилось - 8 минут. Внешний цикл растет линейно, внутренний в корень раз. Да, до завтра не досчитает...
Так что перезапустил, до $10^7$

[nnosipov]

Окей. Хотя бы зафиксируем такой результат. А дальше нужны новые идеи.