Morgana0_0 Jun 20 at 21:14

Последовательность Фибоначчи как ЛРП или что делать, если хочется найти период у бесконечной последовательности?

Easy

3 min

1.1K

Entertaining tasksMathematics*Popular science

Что же такое ЛРП или линейная рекуррентная последовательность? Последовательность, которую можно задать рекуррентным уравнением $s_{n+k} = a_{k-1}s_{n+k-1} + ... + a_{0}s_{k}$ , где коэффициенты - фиксированные элементы поля и есть ЛРП над полем .

Сопровождающая матрица ЛРП выглядит следующим образом:

$A = \begin{pmatrix} 0 & 0 & 0 & \cdots & 0 & a_0 \\ 1 & 0 & 0 & \cdots & 0 & a_1 \\ 0 & 1 & 0 & \cdots & 0 & a_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & a_{k-1} \end{pmatrix}$ .

Её характеристический многочлен: $f(x) = |xE - A| = x^k - a_{k-1}x^{k-1} - \ldots - a_1x_1 - a_0$

Упражняться в теории ЛРП мы будем не на случайных примерах, а искать так называемый период Пизано, то есть период последовательности Фибоначчи по простому модулю. Про сам этот период написано довольно много, но моё домашнее задание было достаточно конкретным, продемонстрировать связь порядка и периода. Я же, в качестве бонуса, опишу стратегию поведения и для случая когда правило "порядок это период" не актуально.

mod 2

Над полем F_2 характеристический многочлен имеет следующий вид: . Известно, что минимальный период ЛРП с неприводимым характеристическим многочленом (а он неприводим) при ненулевом начальном состоянии равен порядку многочлена . Есть два способа найти порядок:

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

Второй быстрее. 2^2 - 1 = 3 - число простое, нетрудно, используя матрицу, убедиться, что период в точности 3.

$A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix};$ $A^2 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix};$ $A^3 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = E.$

Также продемонстрируем это выписав саму последовательность Ф: 011011011011...

mod 3

Над полем F_3 характеристический многочлен уже имеет вид: . Опять же по теории искомый порядок делитель числа . Убеждаемся, что ни 2, ни 4 не подходят, то бишь искомый период ЛРП 8. Продемонстрируем это с помощью матриц:

$A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix};$ $A^2 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix};$ $A^3 =\begin{pmatrix} 1 & 2 \\ 2 & 0 \end{pmatrix};$ $A^4 = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix};$ $A^5 = \begin{pmatrix} 0 & 2 \\ 2 & 2 \end{pmatrix};$

$A^6 = \begin{pmatrix} 2 & 2 \\ 2 & 1 \end{pmatrix};$ $A^7 = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix};$ $A^8 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}= E.$

Снова продемонстрируем это выписав саму последовательность Ф: 01120221011...

mod 11

Над полем F_3 характеристический многочлен тоже имеет вид: , отличие в том, что теперь он приводим. . Что же делать в таком случае, ведь ранее приводимые методы работают только для неприводимых многочленов, в этом случае применима следующая теорема:

Пусть $f_1, f_2, \ldots, f_k$ таковы, что, если $i\neq j$ , ord() = , тогда ord(), где = НОК().

Порядки же теперь будем искать, так сказать, "по старинке". То есть будем искать минимальные и такие, что $x^{l_1} - 1$ и $x^{l_2} - 1$ делятся на и соответственно, причём достаточно перебирать только делители числа . Путём перебора нетрудно получить, что , а . Следовательно, .

!!! В переборе также может помочь то, что порядок многочлена равен порядку его корня в мультипликативной группе соответствующего поля $F_{p^n}$ (в нашем случае p = 11, а n = 1).

mod 5

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

Так в чём же проблема?

Проблема в том, что над полем характеристический многочлен является полным квадратом: , а на такой случай у нас теории нет.

Для ответа на вопрос какой же всё-таки период обратимся к истокам. Доказательство формулы можно найти здесь https://www.fq.math.ca/Scanned/1-2/robinson.pdf. Мне оно кажется исчерпывающим и не требующим дополнительных комментариев, так что ограничимся лишь формулировкой (Я немного перефразирую автора дабы не заставлять читателя предварительно знакомиться с обозначениями оригинальной статьи).

Пусть - индекс первого, отличного от начального элемента, нуля в последовательности Фибоначчи , где модуль по которому рассматривается последовательность, тогда, если $(f_{n(N) + 1}, N) = 1$ , то , где $f_{n(N) + 1}^{m(N)} \equiv 1$ (mod ).

Посмотрим на примере при N = 5: 0112303314044320224101123

Не забываем, что индексирование здесь начинается с нуля, то есть , следующий элемент последовательности тройка, которая взаимно проста с пятью, то есть можно найти :

$3^1 \equiv 3$ (mod 5)
$3^2 \equiv 4$ (mod 5)
$3^3 \equiv 2$ (mod 5)
$3^4 \equiv 1$ (mod 5) $\Rightarrow m(5) = 4$ .

То есть период нашей последовательности $T(5) = n(5)m(5) = 5 \cdot 4 = 20$ .

Оказывается

x^2 -x - 1 = (x - y)^2 над полем F_p эквивалентно системе сравнений

$\begin{cases} -1 \equiv -2y \text{ mod p} \\ -1 \equiv y^2 \text{ mod p} \\ -2y \equiv y^2 \text{ mod p} \end{cases} \Rightarrow -2 \equiv y \text{ mod p, т.к. } y<p \Rightarrow (y, p) = 1, \text{ то есть } -1 \equiv 4 \text{ mod p},$

что возможно лишь при . То есть мы рассмотрели все возможные случаи!

P.s. а ещё у меня есть тг канал с другими не менее интересными заметками https://t.me/mathematuchka

Hubs: