Два точных квадрата в последовательности

[mathematician123]

Для целого числа $d > 1$ определим последовательность $\{x_n\} $:

$$x_0 = 1, \quad x_1 = d^2$$

$$x_{i+1} = d^2 x_i - x_{i-1}$$

Пусть числа $x_k$ и $x_{k+1}$ оказались точными квадратами. Верно ли, что $k = 0$?
Мне удалось доказать, что $x_k$ не может быть точным квадратом, если $2 \le k \le 7$. Доказательство использует метод зажатия между двумя квадратами. Например,

$$ (2d^6 - 5d^2 - 1)^2 < 4x_6 = 4d^{12} - 20d^8 + 24d^4 - 4 < (2d^6 - 5d^2)^2$$

То есть, даже одиночные квадраты встречаются редко, но доказать не получается.

[Andrey A]

Для такой последовательности выполняется $x_n^2-1=x_{n-1}x_{n+1}.$ Если $x_k=a^2,x_{k+1}=b^2$, должно быть верно $a^4\equiv 1 \mod b^2$ и $b^4\equiv 1 \mod a^2$. Пелль-перевертыш ) Слабо в такое верится, но доказательства сходу не вижу. Противоречие угадывается именно по величине.

[mathematician123]

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

Для такой последовательности выполняется $x_n^2-1=x_{n-1}x_{n+1}.$ Если $x_k=a^2,x_{k+1}=b^2$, должно быть верно $a^4\equiv 1 \mod b^2$ и $b^4\equiv 1 \mod a^2$.

Есть ещё соотношение $x_{k+1}^2 + x_k^2 - d^2 x_k x_{k+1} - 1 = 0$ и, следовательно, $a^4 + b^4 - d^2a^2b^2 - 1 = 0$. Это уравнение я и хотел решить. Его можно решить прыжками Виета или сведением к уравнению Пелля. Отсюда и получилась формула для $\{x_n\}$.

[gris]

mathematician123, не касаясь теоретических аспектов, поинтересуюсь чисто бытовым вопросом.
А вообще квадраты после второго элемента встречаются? Вы сказали, что "даже одиночные квадраты встречаются редко", но по первоначальному взгляду их вообще нет. Или как раз два первых элемента и имелись в виду?
Последовательность растёт очень быстро и далеко заглянуть не удаётся.
Просто любопытство Есть ли обнадёживающие примеры?

[mathematician123]

gris в сообщении #1586574 писал(а):

А вообще квадраты после второго элемента встречаются?

Я проверил все пары $(n, d)$, для которых $2 \le d \le 10$ и $2 \le n \le 1000$, а также $d = 2$ и $2 \le n \le 5000$. Квадратов не нашёл.

[Andrey A]

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

должно быть верно $a^4\equiv 1 \mod b^2$ и $b^4\equiv 1 \mod a^2$.

Вольфрам говорит решений нет. Интересно откуда он знает?

mathematician123
Да, злобную штуку Вы придумали, поздравляю (уравнение имеется в виду). А с этими последовательностями я, помнится, и на форум пришел 10 лет назад. Делимость для членов $x_n$ определена как для Фибоначчи: $v \mid w \Rightarrow x_v \mid x_w.$ Но растет $x_n$ сильно быстрее, поэтому каждый член имеет по 2-3 собственных простых делителя. Это (в том числе это) и мешает возникновению квадратов, но кто знает... Всплывет же квадрат в 12-м Фибоначчи.

[mathematician123]

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

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

должно быть верно $a^4\equiv 1 \mod b^2$ и $b^4\equiv 1 \mod a^2$.

Вольфрам говорит решений нет. Интересно откуда он знает?

Очень интересно. Эта система сравнений эквивалентна уравнению

$$a^4 + b^4 - 1 = ma^2b^2$$

Решениями уравнения $x^2 + y^2 - 1 = mxy$ являются пары $(x_i, x_{i+1})$, где $x_0 = 1$, $x_1 = m$, $x_{i+1} = mx_i - x_{i-1}$. И утверждается, что если в этой последовательности встретились два подряд квадрата, то это $x_0$ и $x_1$. То есть, это даже более сильное утверждение чем то, которое я изначально сформулировал.

[Andrey A]

mathematician123 в сообщении #1586863 писал(а):

$$a^4 + b^4 - 1 = ma^2b^2$$

Тем более, что $a=1$ удовлетворяет как системе, так и Вашему уравнению $(m=b^2)$ при любом $b.$ Строго говоря, решения есть.

[mathematician123]

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

Вольфрам говорит решений нет
. Интересно откуда он знает?

Попробовал рассмотреть систему $a^{n} \equiv 1 \pmod{b^2}$, $b^{n} = 1 \pmod{a^2}$ при различных $n$. Вот, что выдал Вольфрам:
n = 6
n = 8
Для $n = 10$, $n = 14$ "решений нет". Когда решения находятся, то они находятся быстро, а после ничего не находится. Например, для $n = 6$ есть решение $(3, 2)$, после которого в пределах 10000 других решений нет.
В общем, всё очень загадочно.

[Руст]

Эта задача о последовательностях Люка с характеристическим уравнением

$$x_n=ax_{n-1}-x_{n-2}, \ a\in N, \ a\ge 3 \ y_1=\frac{a+\sqrt{a^2-4}}{4}, y_2=a-y_1=\frac{1}{y_1}.$$

Решение с начальными условиями $x_0=1,x_1=a$ выражаются формулой:

$$x_n=U_{n+1}=\frac{y_1^{n+1}-y_2^{n+1}}{y_1-y_2}.$$

Введем еще решение $V_n=y_1^n+y_2^n, \ V_0=2, V_1=a.$
Имеет место

$$V_n=x_n-x_{n-2}, \ x_{2n+1}=x_nV_{n+1}=x_n(x_{n+1}-x_{n-1})=x_n(ax_n-2x_{n-1}), \ V_{2n}=V_n^2-2.$$

Если $p|x_{n+1}, p|x_n\to p|x_{n-1}\to ...p|x_0=1$. Отсюда следует, что $x_n,V_{n+1}$ так же взаимно просты.
Если $x_{2n+1}$ является квадратом, то квадратами являются $x_n$ и $V_{n+1}$.
Следовательно, $x_{2n+1}$ не является квадратом при $n\ge 1$.
Еще $(y_1-y_2)^2x_{2n}=(y_1-y_2)(y_1^{2n+1}-y_2^{2n+1})=V_{n+1}^2-v_n^2=(V_{n+1}-V_n)(V_{n+1}+V_n)$

$$x_{2n}=x_nV_n-1=x_n(x_n-x_{n-2})-1$$

Случай $x_{2n}$ можно свести к последовательности $x_n^{(1)}$четности c $A=y_1^2+y_2^2=a^2-2$
$x_{2n}=(a^2-2)x_{2n-2}-x_{2n-4}$. Проще найти модуль (не обязательно простой) $p$ с малым периодом и показать $(\frac{x_{2n}}{p})=-1$.
Случай р=8 соответствует рассмотрению четных номеров по модулю 8 и исключение членов $x_{4n+2} как кандидатов.
В вашем случае достаточно рассмотреть по модулям $2^k$. Для более общей последовательности по простым делителям $V_{2^k}$ для различных $k$.

[Andrey A]

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

Отсюда следует, что $x_n,V_{n+1}$ так же взаимно просты.

$12$-е Фибоначчи делится на $6$-е, конечно, но множители не вз. просты: $144=8 \cdot 18.$ А само как раз квадрат ;)

[mathematician123]

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

Если $p|x_{n+1}, p|x_n\to p|x_{n-1}\to ...p|x_0=1$. Отсюда следует, что $x_n,V_{n+1}$ так же взаимно просты.
Если $x_{2n+1}$ является квадратом, то квадратами являются $x_n$ и $V_{n+1}$.
Следовательно, $x_{2n+1}$ не является квадратом при $n\ge 1$.

$x_3 = a^3 - 2a$ является квадратом при $a = 338$. При этом $\gcd(x_n, V_{n+1}) = 2$.

-- 29.03.2023, 21:45 --

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

Случай р=8 соответствует рассмотрению четных номеров по модулю 8 и исключение членов $x_{4n+2} как кандидатов.

Вот тут тоже не понял. $x_{4n+2}$ можно представить как многочлен от $a^2$ со свободным членом -1. Соответственно если $2 \mid a$ или $p \mid a$ для $p \equiv 3 \pmod{4}$, то получаем противоречие. Как получить противоречие в случае когда $a$ делится только на простые вида $4k+1$ я не вижу. В случае $a = 5$ рассмотрение по модулю 8 даёт только делимость $3 \mid 4n+3$.

-- 29.03.2023, 22:22 --

mathematician123 в сообщении #1587417 писал(а):

В случае $a = 5$ рассмотрение по модулю 8 даёт только делимость $3 \mid 4n+3$.

Хотя я сейчас попробовал рассмотреть случай $a = 5$ и $2 \mid n$ по модулям $2^k$ при различных $k$. И при подходящем выборе $k$ получается, что $x_{2n}$ содержит двойку в нечётной степени либо $x_{2n} = 2^{2m}(8h+r)$, где $r \in \{3, 5, 7\}$, и, значит, $x_{2n}$ не квадрат. Неужели так всегда будет?

[Руст]

Да, я поленился с делителем 2 и возможность $gcd(x_n,V_{n+1})=2$. Требует отдельного рассмотрения.

$$x_n=V_{k}x_{n-k}-x_{n-2k}$$

. Если $p|V_k$, то $V_{n}=-V_{n-2k}\mod p$.

$$V_{2k}=V_k^2-2 \to (\frac{2}{p})=1 \forall p|V_{2k}$$

Так как будет делитель [math]$p=7\mod 8, \ p|V_{2k}$ то $x_{4k}=-1\mod p$
Следовательно $x_{8k+4}$ не квадрат.

[Rak so dna]

mathematician123 в сообщении #1586482 писал(а):

Мне удалось доказать, что $x_k$ не может быть точным квадратом, если $2 \le k \le 7$. Доказательство использует метод зажатия между двумя квадратами.

Продолжил вашу серию для $x_{4n-2}$:

$$(p_2-1)^2<1^2\cdot x_2<p_2^2 \quad \text{для} \quad d\geqslant2$$

$$(p_6-1)^2<2^2\cdot x_6<p_6^2 \quad \text{для} \quad d\geqslant2$$

$$(p_{10}-1)^2<8^2\cdot x_{10}<p_{10}^2 \quad \text{для} \quad d\geqslant2$$

$$(p_{14}-1)^2<16^2\cdot x_{14}<p_{14}^2 \quad \text{для} \quad d\geqslant2$$

$$(p_{18}-1)^2<128^2\cdot x_{18}<p_{18}^2 \quad \text{для} \quad d\geqslant3$$

$$(p_{22}-1)^2<256^2\cdot x_{22}<p_{22}^2 \quad \text{для} \quad d\geqslant3$$

$$(p_{26}-1)^2<1024^2\cdot x_{26}<p_{26}^2 \quad \text{для} \quad d\geqslant5$$

(Выражения для p)

$$p_2 = d^2$$

$$p_6 = 2d^6-5d^2$$

$$p_{10} = 8d^{10}-36d^6+31d^2$$

$$p_{14} = 16d^{14}-104d^{10}+190d^6-85d^2$$

$$p_{18} = 128d^{18}-1088d^{14}+3056d^{10}-3144d^6+859d^2$$

$$p_{22} = 256d^{22}-2688d^{18}+10208d^{14}-16848d^{10}+11254d^6-2083d^2$$

$$p_{26} = 1024d^{26}-12800d^{22}+61312d^{18}-140352d^{14}+155352d^{10}-73212d^6+9771d^2$$

Если предположить, что такая картина будет и дальше, то для поиска $x_n=a^2$ для конкретного $n$ достаточно проверять лишь несколько первых $d$

Последовательность 1,2,8,16,128,...

[mathematician123]

Rak so dna в сообщении #1587626 писал(а):

Если предположить, что такая картина будет и дальше, то для поиска $x_n=a^2$ для конкретного $n$ достаточно проверять лишь несколько первых $d$

Так и будет. Можно доказать такое утверждение: если $\deg(f) = 2n > 0$ и старший коэффициент многочлена $f(x)$ является точным квадратом, то существует многочлен $g(x)$ с рациональными коэффициентами, такой что $\deg(f - g^2) < \frac{\deg(f)}{2}$. Идея доказательства в том, что мы у $g(x)$ сначала подбираем коэффициент при $x^n$ так, чтобы при возведении в квадрат у разности $f - g^2$ сократился коэффициент при $x^{2n}$. Потом подбираем коэффициент при $x^{n-1}$ так, чтобы при возведении в квадрат у разности $f - g^2$ сократился коэффициент при $x^{2n-1}$. Потом подбираем коэффициент при $x^{n-2}$ так, чтобы при возведении в квадрат у разности $f - g^2$ сократился коэффициент при $x^{2n-2}$. И т.д. Также из этого алгоритма следует, что если простое число делит знаменатель некоторого коэффициета $g(x)$, то оно делит 2 или старший коэффициент $f(x)$.
В нашем случае $x_{2n}$ является многочленом степени $2n$ со старшим коэффициентом 1. Значит, $2^s x_{2n}$ при некотором $s$ можно зажать между квадратами. Ещё нужно исключить случай, когда $x_{2n}$ квадратом многочлена, но это не сложно сделать.