Алгебра последовательностей над конечным полем

Определение 1. Последовательностью элементов поля F_p называем любое отображение множества неотрицательных целых чисел N ₀ в поле F_p:

a: N ₀ ® F_p.                                                   (1)

Последовательность (1) обозначаем  или . Множество всех последовательностей вида (1) обозначается через s, последовательность, все члены которой равны нулю обозначаем через 0.

Определение 2. Суммой последовательностей ,   называется последовательность .

Определение 3. Произведением последовательности  на элемент c Î F_p называется последовательность .

Определение 4. Сдвигом последовательности  называется последовательность , обозначаемая T ·a, такая, что для любого x Î N ₀ .

Для любого целого неотрицательного числа k Î N ₀ символом T^k обозначается k -я степень оператора T, т.о. T^k ·a определяется условием:

T^k ·{a _x } ={a _{x + k} }.

Определение 5. Пусть g (l) = b ₀l ⁿ + b ₁l ^{n -1} + …+ b_{n - 1}l + b_n Î F_p [l] – многочлен с коэффициентами из поля F_p. Полиномиальным оператором называется такой оператор, обозначаемый символом g, который определен на последовательностях aÎ s, по правилу:

g ·a = b = {b _x }Î s,

где для любого   x Î N ₀

 b _x  = b ₀a _{x + n} + b ₁a _{x + n -1} + …+ b_{n- 1}a _{x + 1} + b_n a _x,

таким образом,

g ·{a _x } = b ₀a _{x + n} + b ₁a _{x + n -1} + …+ b_{n - 1}a _{x + 1} + b_n a _x.

Последнее равенство через оператор сдвига можно записать следующим образом:

g ·a = b ₀ Tⁿ ·a + b ₁ T^{n- 1}·a + …+ b_{n- 1} T ·a + b_n a _x.

Через W(s) обозначим множество всех полиномиальных операторов.

Примеры. Пусть

a = {1,2,1,0,0,1,1,2,2,1,1,1,0,0,0,1,…}, b = {0,1,1,1,2,2,0,1,2,1,0,1,0,1,2,1,…}

две последовательности над полем F ₃, g (l) = l³ + l² + 2l +1Î F ₃[l]. Тогда

a + b = {1,0,2,1,2,0,1,0,1,2,1,2,0,1,2,2,…},

2a = {2,1,2,0,0,2,2,1,1,2,2,2,0,0,0,2,…},

T ·a = {2,1,0,0,1,1,2,2,1,1,1,0,0,0,1,…},

T ² ·a = {1,0,0,1,1,2,2,1,1,1,0,0,0,1,…},

T ³ ·a = {0,0,1,1,2,2,1,1,1,0,0,0,1,…},

g ·a = {0,1,0,2,2,1,2,0,0,1,0,1,1,…},

Теорема 1. Система (s, +) – абелева аддитивная группа.

Доказательство. По определению 2 операция сложения последовательностей из   s бинарная алгебраическая, и для нее выполняются ассоциативный и коммутативный законы. Нулевым элементом является последовательность           0 = {0}, противоположным элементом для последовательности  является последовательность .

Теорема 2. Система (s, +, F_p) – векторное пространство над полем F_p, замкнутое относительно сдвига.

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

Теорема 3. Многочлены g (l) и h (l) равны тогда и только тогда, когда равны соответствующие им полиномиальные операторы g и h, т.е.

g (l) = h (l) Û ("aÎ s)[ g ·a = h ·a].

Доказательство. Пусть

g (l) = b ₀ + b ₁l ^k + …+ b_{k- 1}l ^{k -1} + b_k l ^k, h (l) = c ₀ + c ₁l + …+ c_{m- 1}l ^{m -1} + c_m l ^m   Î F_p [l].

Пусть   g (l) = h (l). Тогда k = m и b_i = c_i для любого i = 0, 1,…, k. Поэтому для любой последовательности aÎ s имеем

g ·a = b ₀ a + b ₁ T ·a + …+ b_k T^k ·a = c ₀a + c ₁ T ·a + …+  c_m T^m ·a = h ·a.

Пусть ("aÎ s)[ g ·a = h ·a]. Докажем, что g (l) = h (l). Для определенности пусть k £ m. Далее пусть g ·d = a = {a _x }, g ·d = b = {b _x }. Для каждого неотрицательного числа j выберем последовательность d с условиями: d _x = 0, x ¹ j и d _j = 1.

Если j £ k, то получаем

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

g ·d₀ = b ₀ d₀ + b ₁ T ·d₀ + …+ b_k T^k ·d₀ = b ₀ d₀ + b ₁d₁ + …+ b_k d _k  = b _j,

h ·d = c ₀d + c ₁ T ·d + …+ b_mT^m · d  ,

h ·d₀ = c ₀d₀ + c ₁ T ¹·d₀ + …+ c_m T^m ·d₀ = c ₀d₀ + c ₁d₁ + …+ c_m d _m = c_j.

Отсюда получаем b_j = c_j для j = 0, 1,…, k.

Если k < j £ m, то получаем

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

g ·d₀ = b ₀ d₀ + b ₁ T ·d₀ + …+ b_k T^k ·d₀ = b ₀ d₀ + b ₁d₁ + …+ b_k d _k = 0,

h ·d = c ₀d + c ₁ T ·d + …+ b_mT^m · d,

h ·d₀ = c ₀d₀ + c ₁ T ¹·d₀ + …+ c_m T^m ·d₀ = c ₀d₀ + c ₁d₁ + …+ c_m d _m = c_j.

Отсюда получаем c_j = 0 для j = k – 1,…, m. Таким образом, соответствующие коэффициенты многочленов g (l) и h (l) равны и поэтому g (l) = h (l).

Теорема 4. Для любых многочленов g (l) и h (l)Î F_p [l] и для   любых последовательностей  a, bÎ s справедливы равенства:

1) g ·(a + b) = g ·a + g ·b;

2) (g + h)·a = g ·a + h ·a;

3) g ·(h ·a) = (gh)·a.

Доказательство. 1. Пусть a = {a _x }, b = {b _x }, g (l) = b ₀ + b ₁l + …+ b_{k - 1}l ^{k -1} + b_k l ^k Î F_p [l]. Так как для любого x Î N ₀

g ·(a _x + b _x) = b ₀ (a _x + b _x) + b ₁ T ·(a _x + b _x) + …+ b_k T^k ·(a _x + b _x) =

= b ₀ (a _x + b _x) + b ₁(a _{x +1} + b _{x +1}) + …+ b_k (a _x+k + b _x+k) =

= (b ₀ a _x + b ₁a _{x +1} + …+ b_k a _x+k) + (b ₀ b _x + b ₁b _{x +1} + …+ b_k b _x+k) =

= (b ₀ a _x + b ₁ T ·a _x + …+ b_k T^k ·a _x) + (b ₀b _x + b ₁ T ·b _x + …+ b_k T^k b _x) = g ·a _x + g ·b _x,

то g ·(a + b) = g ·a + g ·b.

2. Пусть a = {a _x }, g (l) = b ₀ + b ₁l + …+ b_k l ^k,   h (l) = c ₀ + c ₁l + …+ c_m l ^m Î F_p [l], k £ m. Для каждого i, k < i £ m, положим b_i = 0. Тогда g (l)+ h (l) = (b ₀ + c ₀)+ (b ₁+ c ₁)l + …+ (b_m + c_m)l ^m. Так как для любого x Î N ₀

(g + h)·a _x = (b ₀+ c ₀ )a _x + (b ₁+ c ₁) T ·a _x + …+(b_m + c_m) T^m ·a _x =

= (b ₀+ c ₀ )a _x + (b ₁+ c ₁)a _{x +1} + …+(b_m + c_m)a _x+m =

= (b ₀ a _x + b ₁a _{x +1} + …+ b_m a _x+m) + (c ₀ a _x + c ₁a _{x +1} + …+ c_m a _x+m) =

= (b ₀ a _x + b ₁ T ·a _x + …+ b_m T^m ·a _x) + (c ₀ a _x + c ₁ T ·a _x + …+ c_m T^m ·a _x) = g ·a _x + h ·a _x,

то (g + h)·a = g ·a + h ·a.

3. Пусть a = {a _x }, g (l) = b ₀ + b ₁l + …+ b_k l ^k, h (l) = c ₀ + c ₁l + …+ c_m l ^m Î F_p [l].

Тогда для любого x Î N ₀

h ·a _x = c ₀a _x + c ₁ T ·a _x + …+ c_mT^m ·a _x =  

Поэтому

g ·(h ·a) = b ₀(c ₀ a _x + c ₁a _{x +1} + …+  c_m a _x+m) + b ₁(c ₀ a _{x +1} + c ₁a _{x +2} + …+  c_m a _{x + m +1}) +…+

. + b_k (c ₀ a _{x + k} + c ₁a _{x +1+ k} + …+  c_m a _{x+m + k} ) = .

Отсюда получаем, что g ·(h ·a) = (gh)·a.

Теорема 5. Система полиномиальных операторов (W(s), +, ×) образует кольцо, изоморфное кольцу многочленов F_p [l].

Доказательство. С многочленом g (l) = b ₀ + b ₁l + …+ b_k l ^k  Î F_p [l] сопоставим полиномиальный оператор линейный

g = b ₀ + b ₁ T + …+ b_k T^k Î W(s).

В силу теоремы 3 это соответствие взаимно однозначное. Операции сложения и умножения для операторов g, h Î W(s) определяем соотношениями:

g + h = u Û ("dÎ s)[ u ·d= g ·d + h ·d],

g · h = v Û ("dÎ s)[ v ·d= g ·(h ·d)].

Тогда по теореме 5 получаем, отображение g (l)® g сумме и произведению многочленов из F_p [l] ставит в соответствие сумму и произведение операторов из W(s). Следовательно, указанное отображение является изоморфизмом.