Не более пяти решений

[nnosipov]

Докажите, что для каждого целого $H>1$ уравнение $x(y^2-2x^2)+Hx+y+1=0$ имеет не более пяти решений $(x,y)$ в целых числах.

P.S. Сама задача несложная, но есть дополнительные вопросы. Верно ли, что число решений данного уравнения в целых числах равномерно ограничено при $H<0$? При $H=1$ уравнение имеет семь решений. Есть ли еще целые значения $H$, для которых уравнение имеет семь (или более) решений?

[dmd]

Пробую исследовать число решений для разных $H$.

Пусть $2xy+1=z$. Результант по $y$ преобразует в $1 - 4 x - 4 H x^2 + 8 x^4 = z^2$.

Pari/gp преобразует в форму Вейерштрасса

? ellfromeqn(1 - 4*x - 4*H*x^2 + 8*x^4 - y^2)
%1 = [0, -4*H, 0, -32, 128*H + 128]

но формулы преобразований мне неизвестны, поэтому лучше в Maple преобразовывать.

Дальше можно составить процедуру поиска решений, перебирая $H$.

[nnosipov]

dmd
С эллиптическими кривыми здесь далеко не уедешь. Задача отыскания целых точек на кривой

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

$1 - 4 x - 4 H x^2 + 8 x^4 = z^2$

гораздо сложнее исходной, которая рассчитана на школьников. Правда, в "Квант" ее не взяли --- типа, слишком сложная (но это на самом деле неправда).

-- Вс апр 12, 2020 22:49:33 --

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

но формулы преобразований мне неизвестны, поэтому лучше в Maple преобразовывать.

Они не помогут: при таком переходе целочисленность испортится (нас интересуют решения в целых числах, а не в рациональных).

[novichok2018]

nnosipov - Вы просто серьёзно интересуетесь олимпиадными задачами, или составляете некоторый текст по ним и конкретно по уравнениям в целых? Это как-то связано с характером работы - кружок, школа, репетиторство?

[nnosipov]

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

Для всего остального есть ЛС.

[dmd]

Решения для отрицательных $H$ можно в магме поискать. Насколько понимаю, если она не подвисла на конкретном $H$, значит гарантированно нашла все целые решения.

Т.к. $x\mid y+1$, то пусть $1+y+xt=0$.

Результант по $y$ даст $(x (t^2 - 2) + t)^2 = 2(1+H) - 2 t - H t^2 + t^3$.

(магма-код для >=6 решений)

SetClassGroupBounds("GRH");
for i in [1..10^6] do
  H:= -1*i;
  V:= [];
  S:= IntegralPoints(EllipticCurve([0,-H,0,-2,2*(H+1)]));
  for s in S do
    t:= s[1];
    x:= (s[2]-t)/(t^2-2);
    if x eq Floor(x) then
      y:= -1-x*t;
      V:= V cat [[x,y]];
    end if;
    x:= (-s[2]-t)/(t^2-2);
    if x eq Floor(x) then
      y:= -1-x*t;
      V cat:= [[x,y]];
    end if;
  end for;
  if #V ge 6 then
    printf "H = %o    ", H;
    for v in V do printf "%o,", v; end for;
    printf "\n";
  end if;
end for;

Для H=-1..-1000 семь решений нет, и только дважды по шесть решений:
H = -69 [ 0, -1 ],[ -1, -8 ],[ 5, -11 ],[ -7, 13 ],[ 2, -9 ],[ -1, 9 ],
H = -649 [ 0, -1 ],[ 1, 25 ],[ -17, -35 ],[ 19, 37 ],[ -3, 26 ],[ 1, -26 ],

[nnosipov]

dmd
Спасибо. Мне было бы интересно узнать, сколько времени тот magma-код будет проверять все отрицательные $H$ до $10^6$. Если Вы можете как-то оценить это время, сообщите, пожалуйста.

Наименьшее отрицательное $H$, для которого будет семь решений, я знаю: это $H=-1219919$. Других таких до $10^7$ нет. Хотелось бы проверить до $10^9$.

-- Пн апр 13, 2020 16:03:34 --

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

Для H=-1..-1000 семь решений нет, и только дважды по шесть решений:

Да, у меня так же.

[dmd]

nnosipov

(Оффтоп)

Можно вначале добавить
t0:= Realtime();
и перед
if #V ge 6 then
добавить
if #V ge 4 then printf "%o sec. H(#sol>=4) = %o \n", Realtime()-t0, H; end if;
Тогда будет примерно понятно, какая идёт итерация, сколько прошло времени и реально ли дождаться окончания.

[nnosipov]

dmd
Хорошо, тогда спрошу так: сколько у Вас времени заняла обработка первых тысячи значений $H$? Хотя бы примерно.

[dmd]

400 секунд. Но первые тысяча легкие. Не уверен, можно ли этим кодом добраться даже до 10^4, потому что на некоторых $H$ зависает конкретно. Хотя 1219919 проверилось за 6 сек.

[nnosipov]

dmd
Большое спасибо! Вот теперь понятно, что magma здесь не поможет.

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

Хотя 1219919 проверилось за 6 сек.

Это тоже слишком много. У меня (Maple, i3) за несколько миллисекунд.

Настоящий рекорд ($10^7$ значений $H$) получен на python (i7, 55 минут). Всем желающим поставить новый рекорд готов предоставить свой код на Maple (для оптимизации в чем угодно и как угодно). Код с математической точки зрения очень простой. На (Maple, i3) он обрабатывает $10^5$ значений $H$ за 192 сек.

[kotenok gav]

Ну, питон довольно медленнен. Надо тогда уж попросить Dmitriy40 о программе на ассемблере.

[nnosipov]

Ассемблер --- да я слов таких не знаю Главная проблема здесь --- это доказательность программы. Основной момент для оптимизации: нужно находить целую часть квадратного корня из натурального числа (это необходимо, потому что программа пачками решает обычные квадратные уравнения с целыми коэффициентами и в целых числах). И ничего более. Но нужен именно грамотный человек в программировании. Да, такой как Dmitriy40, тут я полностью согласен. Но как его заманить?

Кстати, мой бакалавр, который делал это на python, все-таки организовал там многопроцессность --- алгоритм хорошо параллелится. Все-таки не совсем примитивно делал, но это с моей дилетантской колокольни.

[Dmitriy40]

kotenok gav
Э нет, писать свою реализацию поиска целых/рациональных решений эллиптической кривой я не готов. А без этого мне пока непонятно до каких пределов перебирать переменные, да и перебор будет дооооолгим. Так что до ассемблера тут ещё много математики (в которой я откровенно не силён).

nnosipov
Для не слишком больших чисел, скажем до $10^{19..38}$, извлечение целочисленного квадратного корня не проблема, не быстро, но миллионы в секунду вполне реально (например до $10^{19}$ корень извлекается 15 млн.раз/с), это у меня уже давно написано. Плюс можно додумать как сделать вычисление действительного корня с проверкой целочисленности результата, возможно это будет даже быстрее. Остальные вычисления целочисленны соответственно ошибок не возникает (кроме случайных сбоев, которые лечить себе дороже).
Многопоточность тоже не проблема, самое примитивное — запустить в разных потоках разные значения $H$. Кстати если обойтись не слишком большими числами (опять же до $10^{19}$), то можно и на GPU запустить счёт, правда что именно там параллелить надо очень хорошо подумать.

[nnosipov]

Dmitriy40
Спасибо, что откликнулись. Вот это сильно обнадеживает:

Dmitriy40 в сообщении #1454221 писал(а):

Для не слишком больших чисел, скажем до $10^{19..38}$, извлечение целочисленного квадратного корня не проблема, не быстро, но миллионы в секунду вполне реально (например до $10^{19}$ корень извлекается 15 млн.раз/с), это у меня уже давно написано.

Мне нужно аккуратно прикинуть, насколько велики будут коэффициенты решаемых квадратных уравнений, если исходить из границы $10^9$. Надеюсь уложиться в Ваши размеры. Позже я напишу подробное изложение алгоритма; он в самом деле крайне примитивный, ничего общего с (действительно) очень сложным алгоритмом отыскания целых точек на эллиптической кривой общего вида. А сейчас выложу код на Maple, чтобы Вы могли чисто визуально (а может, и содержательно) понять, что с точки зрения математики здесь все примитивно.

Используются две вспомогательные процедуры. Первая находит целую часть квадратного корня из натурального $N$:

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:

Вторая решает квадратные уравнения $at^2+bt+c=0$ с целыми коэффициентами в целых числах:

solve_int:=proc(a,b,c)
local S,d,d2;
if a=0 and b=0 then return {} end if;
if a=0 then if irem(c,b)=0 then return {-c/b} else return {} end if end if;
S:={};
d:=b^2-4*a*c;
if d>=0 then d2:=FloorSqrt(d);
if d2^2=d then
if irem(-b+d2,2*a)=0 then S:=S union {(-b+d2)/2/a} end if;
if irem(-b-d2,2*a)=0 then S:=S union {(-b-d2)/2/a} end if;
end if;
end if;
return S;
end proc:

Ну и, собственно, сама программа:

runge:=proc(H)
local S,m,Q,k,res,x,y;
S:={[0,-1]};
m:=1+floor(evalf(abs(H)^(1/4)));
Q:=floor(evalf(m/(m^2-2)+sqrt((m+abs(H))/(m^2-2)+2/(m^2-2)^2)));

for k from -m to m do
res:=solve_int(k^2-2,2*k,H-k+1);
for x in res do S:=S union {[x,-k*x-1]} end do
end do;

for x from 1 to Q do
res:=solve_int(x,1,-2*x^3+H*x+1);
for y in res do S:=S union {[x,y]} end do
end do;
for x from -Q to -1 do
res:=solve_int(x,1,-2*x^3+H*x+1);
for y in res do S:=S union {[x,y]} end do
end do;

return S
end proc:

По существу, здесь решается две порции квадратных уравнения (выделены вертикальными пробелами), причем вторая порция --- это исходное уравнение, решаемое относительно $y$ (а $x$ в роли параметра, который перебирается в заранее вычисленных границах от $-Q$ до $Q$, исключая $x=0$). Первая порция квадратных уравнений зависит от вспомогательного параметра $k$ (который перебирается в заранее вычисленных границах от $-m$ до $m$), а неизвестным в уравнении является $x$ (по известному $k$ и найденному корню $x$ затем вычисляется $y$).

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