Свойства решений линейного рекуррентного уравнения

Пусть

d _{x + n}  = a ₁d _{x+n- 1}+…+ a_{n+ 1}d _{n +1} + a_n d _n;                                 (1)

f (l) = l ⁿ - a ₁l ^{n - 1} - …+ a_n Î F_p [l] –

Пусть V_n – n -мерное векторное пространство над полем F_p; 0 – нулевой вектор пространства, a·b - скалярное произведение векторов a и b Î V_n; c - характер аддитивной группы поля ; c₀ – главный характер аддитивной группы поля .

Для каждого j Î {0, 1,…, n -1}  - решение уравнения (1) с начальными значениями:

,

где A – матрица рекурсивного уравнения (1); B – матрица, транспонированная к матрице A. Имеем

.

Пусть d^{( j )} , 0 £ j £ k – все различные решения уравнения (1), такие что ни одно из них не может быть получено сдвигом из другого; их множество условимся обозначать символом L (f), таким образом, L (f) = {d^{( j )} |  0 £ j £ k }. Пусть

t_j = t(d^{( j )});

.                                          (2)

Теорема 1. Множество векторов

                                 (3)

совпадает с множеством всех векторов пространства V_n.

Доказательство. Так как (3) Í V_n, то достаточно показать, что любой вектор a = (a₀, a₁, …, a _{n - 1}) Î V_n принадлежит (3). Вектор a можно взять в качестве начального значения решения уравнения (1) и по нему построить решение уравнения (1). Так как среди начальных значений (2) содержаться все возможные, отличные друг от друга с точностью до сдвига, то вектор a содержится среди векторов (3).

Теорема 2. Справедливы равенства

a) " x Î Z A ·D _x = D _{x + 1};

b) " x Î Z A^x ·D₀ = D _{x .}

Доказательство.   a)

.

b) Из a) последовательно получаем

A^x ·D₀ = A^{x- 1}·(A ·D₀) = A^{x- 1}·D₁ = …= A ·D _{x- 1} = D _x.

Теорема 3. " x Î Z," y Î Z

.                            (4)

Доказательство.   При фиксированном y равенство (4) верно при x = 0, x = 1, …, x = n -1:

Далее

.

Таким образом, решения d _{x + y} и b _x ·D _y равны при n последовательных значениях переменного x. Следовательно, они равны при любых x Î Z.

Теорема 4. Справедливы равенства

c) " x Î Z B ·b _x = b _{x + 1};

d) " x Î Z B^x ·b₀ = b _{x .}

Доказательство.   a) В равенстве (4) полагаем y = 1, заменяем d _x на r _x ^{( k )} и получим

.                       (5)

В равенстве (5) полагаем последовательно k = 0, k = 1, …, k = n -1:

Таким образом, получаем

b _{x + 1} = B ·b _x

и равенство a) доказано.

b) Из a) последовательно получаем

B^x ·b₀ = B^{x- 1}·(B ·b₀) = B^{x- 1}·b₁ = …= B ·b _{x- 1} = b _x.

Теорема 5. " x Î Z

.                       (6)

Доказательство.   Из равенства (1) имеем

 

Теорема 6. Справедливы утверждения:

a) Если d - главное решение уравнения (1), то для любого x Î Z векторы D _x, D _{x + 1}, …, D _{x + n - 1} линейно независимы над полем F_p.

b) для любого x Î Z векторы b _x, b _{x + 1}, …, b _{x + n - 1} линейно независимы над полем F_p.

Доказательство.   a) Докажем, что векторы D _x, D _{x + 1}, …, D _{x + n - 1}линейно независимы над полем F_p. Допустим противное, что существуют не все равные нулю элементы c ₁, c ₂, …, c_n поля F_p, что

c ₁D _x + c ₂D _{x + 1} + …+ c_n D _{x + n - 1} = 0.                                 (7)

Умножая обе части этого равенства на A ^{- x}, по теореме 2 получим

c ₁D₀ + c ₂D₁ + …+ c_n D _{n - 1} = 0.

Последнее невозможно, так как при изоморфном отображении t пространства S (f) на V_n базису (d, T ·d, …, T^{n - 1}·d) отвечает набор (D₀, D₁, …,D _{n - 1}). При изоморфизме линейно независимая система векторов переходит в линейно независимую систему.

b) Допустим противное, что существуют не все равные нулю элементы c ₁, c ₂, …, c_n поля F_p, что

c ₁b _x + c ₂b _{x + 1} + …+ c_n b _{x + n - 1} = 0.                                 (7)

Умножая обе части этого равенства на B ^{- x}, по теореме 5 получим

c ₁b₀ + c ₂b₁ + …+ c_n b _{n - 1} = 0.

Последнее невозможно, так как векторы (b₀, b₁, …,b _{n - 1}) линейно независимы над полем F_p.

Теорема 7. t(b) = t.

Доказательство.   Так как примитивный период главного решения уравнения (1) равен t, а главное решение базис пространства S (f), то

" x Î Z [d _{x + t} = d _x ]

для любого решения d уравнения (1). Следовательно,

" x Î Z [b _{x + t} = b _x ].

С другой стороны, если

" x Î Z [b _{x + m} = b _x ],

то

" x Î Z [r _{x + m} ^{( j )} = r _x ^{( j )}]

для каждого j = 0,…, n - 1 и в частности для j = n – 1. А так как r^{( n - 1)} – главное решение уравнения (1), то m ³ t.