Линейные рекуррентные последовательности над конечным полем

Определение 1. Пусть p – простое число; a ₁, a ₂,…, a_n Î F_p, a_n ¹ 0. Уравнение вида

d _x+n = a ₁d _{x+n- 1} + a ₂d _{x+n- 2} + …+  a_n d _x                                              (1)

называется линейным рекуррентным уравнением над полем F_p порядка n. Многочлен

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

называется характеристическим многочленом уравнения (1). Последовательность d элементов поля F_p называется решением уравнения (1), если она удовлетворяет уравнению (1). Первые n членов последовательности d₀, d₁,…, d _{n - 1} последовательности называются начальными членами последовательности d. Они однозначно определяют всю последовательность d.

Решение линейного рекуррентного уравнения (1) называют также рекуррентной последовательностью.

Через s (f) = s _F (f) обозначаем множество всех решений уравнения (1) над полем F = F_p с характеристическим многочленом f.

Пример 1. Пусть p = 2, n = 2, f = l² - l -1. Список всех решений над полем F ₂ уравнения d _{x + 2} = d _{x + 1} + d _x приведен в таблице.

x	0	1	2	3	4	5	6	7	8	…
d x	0	0	0	0	0	0	0	0	0	…
d x	0	1	1	0	1	1	0	1	1	…
d x	1	0	1	1	0	1	1	0	1	…
d x	1	1	0	1	1	0	1	1	0	…

Пример 2. Пусть p = 3, n = 2, f = l² - l -1. Список всех решений над полем F ₃ уравнения d _{x + 2} = d _{x + 1} + d _x приведен в таблице.

x	0	1	2	3	4	5	6	7	8	9	…
d x	0	0	0	0	0	0	0	0	0	0	…
d x	0	1	1	2	0	2	2	1	0	1	…
d x	1	0	1	1	2	0	2	2	1	0	…
d x	0	2	2	1	0	1	1	2	0	2	…
d x	2	0	2	2	1	0	1	1	2	0	…
d x	1	1	2	0	2	2	1	0	1	1	…
d x	1	2	0	2	2	1	0	1	1	2	…
d x	2	1	0	1	1	2	0	2	2	1	…
d x	2	2	1	0	1	1	2	0	2	2	…

 

Теорема 1. Число всех решений линейного рекуррентного уравнения порядка n над полем F_p равно pⁿ, в том числе pⁿ - 1 ненулевых, т.о.

| s _F (f)| = pⁿ = p ^{deg f}.

Доказательство. Число решений уравнения (1) равно числу всевозможных различных наборов начальных членов (d₀, d₁,…, d _{n - 1}). Каждый такой набор есть размещение с повторениями из p элементов поля F_p. Следовательно, число решений уравнения равно pⁿ.

Теорема 2. Пусть d = {d _x }- какое-нибудь решение линейного рекуррентного уравнения (1), x, y – неотрицательные целые числа. Если

d _x = d _y , d _{x+ 1} = d _{y+ 1}, …, d _{x+n- 1} = d _{y+n- 1},                           (3)

то d _{x + n} = d _{y + n}, если к тому же x > 0, y > 0, то d _{x - 1} = d _{y - 1}.

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

d _x+n = a ₁d _{x+n- 1} + a ₂d _{x+n- 2} + …+  a_n d _x, d _y+n = a ₁d _{y+n- 1} + a ₂d _{y+n- 2} + …+  a_n d _y.

Тогда в силу равенств (3) получаем d _{x + n} = d _{y + n}.

Если x > 0, y > 0, то запишем уравнения (1) при x  равном x – 1 и y – 1

d _{x+n- 1} = a ₁d _{x+n- 2} + a ₂d _{x+n- 3} + …+  a_n d _{x- 1}, d _{y+n- 1} = a ₁d _{y+n- 2} + a ₂d _{y+n- 3} + …+  a_n d _{y - 1}.

Так как a_n ¹ 0, то в в силу равенств (3) получаем d _{x - 1} = d _{y - 1}.

Теорема 3. Пусть S (f) - система (s (f), +, F_p). Тогда:

1) система S (f)  – векторное пространство над полем F_p, замкнутое относительно сдвига;

2) для любого решения d Î s (f) и многочлена g Î F_p [l] имеем   g ·d Î s (f);

3) векторное пространство S (f)   изоморфно n -мерному координатному пространству V_n над полем F_p.                                                                       

Доказательство. 1.Пусть , b = {b _x }Î s (f). Тогда для любого неотрицательного числа x выполняются равенства

a _x+n = a ₁a _{x+n- 1} + a ₂a _{x+n- 2} + …+  a_n a _x, b _x+n = a ₁b _{x+n- 1} + a ₂b _{x+n- 2} + …+  a_n b _x.

Складывая эти равенства почленно, получаем равенство

a _x+n + b _x+n = a ₁(a _{x+n- 1} + b _{x+n- 1}) + a ₂(a _{x+n- 2} + b _{x+n- 2}) + …+  a_n (a _x + b _x),

которое показывает, что последовательность a+b = {a _x + b _x }Î s (f).

Умножая обе части равенства (1) на элемент c Î F_p, получаем равенство

c a _x+n = a ₁(c a _{x+n- 1}) + a ₂(c a _{x+n- 2}) + …+  a_n (c a _x),

которое показывает, что последовательность c a = { c a _x }Î s (f). Так как s (f) Ì s, а множество s является векторным пространством над F_p, то из доказанного выше следует, что s (f) – векторное пространство над полем F_p.

Так как для любой последовательности aÎ s (f), последовательность T ·a Î s (f)и так как любая последовательности Î s (f) может быть получена сдвигом последовательности b = {b _x }Î s (f), где для любого a = {a _x }, T ·a = b = {b _x }. имеем b _{x + 1} = a _x, а b₀ – произвольный элемент из F_p. Поэтому T · s = s.

2. Пусть d Î s (f) и многочлена g (l) = b ₀ + b ₁l + …+ b_k l ^k  Î F_p [l]. Тогда

g ·d = b ₀ d + b ₁ T ·d + …+ b_kT^k · d.

По доказательству первого пункта имеем  

d, T ·d,…, T^k · d, b ₀ d, b ₁ T ·d,…, b_kT^k · d, b ₀ d + b ₁ T ·d + …+ b_kT^k · d Î s (f).

Таким образом, g ·d Î s (f).

3. Зададим отображение Y: s (f) ® V_n по правилу:

Y(d) = (d₀, d₁,…, d _{n - 1}).

Это отображение Y является биекцией, в силу того, что любая рекуррентная последовательность однозначно определяется характеристическим уравнением и ее начальными членами. Далее из определения суммы последовательностей и произведения последовательности на число следует, что для любых последовательностей , b = {b _x }Î s (f) и любого c Î F_p выполняются свойства

Y(a + b) = Y({a _x } + {b _x }) = Y({a _x + b _x }) = (a₀ + b₀, a₁ + b₁,…, a _{n - 1} + b _{n - 1}) =

= (a₀, a₁,…, a _{n - 1} ) + (b₀, b₁,…, b _{n - 1}) = Y(a) + Y(b),

Y(с a) = Y(с {a _x }) = Y({ с a _x }) = (с a₀, с a₁,…, с a _{n - 1} ) = с (a₀, a₁,…, a _{n - 1} ) = с Y(a).

По определению отображение Y является изоморфизмом, а векторные пространства S (f)  и V_n изоморфные.

Так как dim V_n = n и S (f)  @ V_n, то dim S (f)= n и базис пространства S (f) состоит из n решений.

Определение 2. Решение d линейного рекуррентного уравнения (1) называется главным решением, если набор решений (d, T ·d,…, T^{n - 1}· d) является базисом пространства S (f).

Пример 3. Решение r = {r _x }Î s (f) уравнения (1) с начальными значениями

r₀ = r₁ = …= r _{n - 2} = 0, r _{n - 1} = 1

является главным, так как векторам r, T ·r,…, T^{n - 1}· r при отображении Y соответствуют векторы

(0, 0,…, 0, 1), (0, 0,…, 1, r _n), …, (1, r _n,…, r_{2 n -3}, r_{2 n -2}),

которые образуют базис пространства V_n. Тогда по свойству изоморфизма векторы r, T ·r,…, T^{n - 1}· r образуют базис пространства S (f) и решение d - главное.