Application of Gauss sums to calculate the exact values of the number of appearances of elements on cycles of linear rec.pdf Введение Решается задача получения точных значений частот N(z,u) появлений элемента z поля P = GF(q) среди элементов u(0), u(1), ..., u(T - 1) линейной рекуррентной последовательности (ЛРП) u = (u(i))°=0 над полем P с неприводимым характеристическим многочленом f (x) E P[x] степени m и периода T = (qm - 1)/d [1, 2]. На число d накладывается следующее условие: d делит pJ + 1 для некоторого натурального числа j, где p - характеристика поля. В этом случае говорят, что число p полупримитивно по модулю d [3]. Такие последовательности u получаются в результате регулярной выборки с шагом d из ЛРП максимального периода qm - 1 [4, 5]. В [6, теоремы 6, 7] с использованием сумм Гаусса данная задача решена для случая, когда P - простое поле, т. е. q = p. При этом выписаны только типы распределений, но не указано значение N(z, u) при каждой конкретной ЛРП u. Позже, в работе [3], задача была решена для случая, когда z = 0, а P - произвольное поле. Полное решение рассматриваемой задачи приводится в [7, теорема 1.1], однако при доказательстве в самом начале работы автор использовал ошибочное равенство (2.3) для суммы Гаусса, которое привело к ошибочным формулам. Отметим также, что случай, когда d = 2, а P - произвольное поле, рассмотрен в [1, теорема23, с. 359], где выписаны только возможные типы распределений. Цель данной работы - обобщить известные факты о частотах N(z,u) и изложить доказательства в рамках одной статьи. Основными результатами являются теоремы 4, 5, 7, 8, 9, в частности, позволяющие получить полное решение поставленной задачи в ситуации, когда d - простое число. 1. Некоторые свойства характеров конечных полей Укажем некоторые свойства характеров конечных полей и дадим необходимые определения. Доказательства приведённых результатов подробно изложены в [2]. Пусть (G, •) - конечная абелева группа с нейтральным элементом е. Характером группы G называется любой гомоморфизм х группы G в мультипликативную группу C* поля комплексных чисел. Обозначим G множество всех характеров группы G. Множество G не пусто, так как там содержится, например, характер Хо, определённый равенствами x0(g) = 1 для всех g E G. Характер х0 называется тривиальным, а все остальные характеры из множества G называются нетривиальными. Зададим операцию произведения характеров, положив для любых Х1,Х2 E G Х1 • Х2 = Х, где Х : G ^ C и X(g) = X1(g)X2(g) для всех g E G. Тогда (G, •) -конечная абелева группа, изоморфная группе G. Обратным к характеру х E G является характер Х (сопряжённый к характеру х), определённый равенством x(g) = x(g) для всех g E G, где черта означает комплексное сопряжение. Пусть Х - произвольный нетривиальный характер конечной абелевой группы G, тогда справедливо соотношение e x(g)=(G если Х=хо- (1) geG [ ° если Х = Хо. Пусть H - подгруппа конечной абелевой группы G. Обозначим через A множество всех характеров х группы G, которые удовлетворяют условию x(h) = 1 для всех h E H. В этом случае говорят, что характер Х аннулирует подгруппу H. Тогда A является подгруппой группы G и имеет место равенство A = Л Рассмотрим конечное поле P = GF(q) из q элементов, где q = ps, p - простое число. С полем P связаны две абелевы группы: (P*, ■) -мультипликативная группа поля P и (P, +) - аддитивная группа поля P. Рассмотрим характеры аддитивной группы поля P. Такие характеры будем называть аддитивными характерами поля P. Для каждого элемента b Е P рассмотрим отображение хь : P ^ C*, осуществляемое по правилу Xb(x) = e для всех x Е P, где trp - функция следа из поля P в простое подполе. Тогда группа аддитивных характеров поля P имеет вид {хь : b Е P}. При b = 0 получим тривиальный характер хо, а при b = e - характер Xe, который называется каноническим аддитивным характером поля P. В дальнейшем будет полезна конструкция поднятия аддитивного характера х поля P = GF(q). Пусть х = Xb, где b Е P, b = 0; Q = GF(qm) -расширение степени m поля P. Зададим отображение х' : Q ^ C*, осуществляемое для всех z Е Q по правилу Az) = х« (z)). (3) Тогда It \ --_ х (z) = e p , z Е Q, а значит, х' является нетривиальным аддитивным характером поля Q. Характер х' называется поднятием характера х до поля Q. Если х - канонический аддитивный характер поля P, то его поднятие до поля Q также будет каноническим аддитивным характером поля Q. Рассмотрим теперь группу мультипликативных характеров поля P = GF(q). Группа P* циклическая, поэтому группа мультипликативных характеров - циклическая группа, порождённая характером фф1, который задаётся по правилу ф\(gk) = e2niА, k = 0,1,... ,q - 2, где g - некоторый примитивный элемент поля P. Для всех j Е {0,1,... ,q - 2} обозначим через "j характер , тогда группа мультипликативных характеров поля P имеет вид {ф0,ф1,... ,"q-2} = (ф1). Характер ф0 является тривиальным. Пусть P = GF(q), ф - мультипликативный характер поля P, а х - аддитивный характер поля P. Сумма Гаусса С(ф,х) определяется следующим равенством: С(ф,х)= Е "(cMc). ceP * Теорема 1. Для сумм Гаусса справедливы следующие соотношения: {q - 1, если ф = х = Xо, -1, если ф = фо, х = хо, ^ если ф = х = хо; если ф = фо, х = хо, то |С(Ф,х)1 = Vq; если х - произвольный аддитивный характер поля P = GF(q), то для всех c Е P* х(^ = ^Е G^^Mc), (4) q - 1 ф где суммирование осуществляется по всем мультипликативным характерам ф поля P. 2 nitrp(bx) 2. Сведение задачи к исследованию сумм Гаусса Пусть u = (u(i))°=0 -произвольная чисто периодическая последовательность элементов поля P = GF(q) периода T(u). Для каждого элемента z Е P обозначим через N(z,u) число появлений z среди элементов u(0), u(1), ..., u(T(u) - 1). Покажем, что исследование частоты N(z,u) сводится к исследованию суммы T (u)-1 a(u) = Е х(-cz) Е x(cu(i)) ceP* i=o где х - нетривиальный аддитивный характер поля P. С использованием равенства (1) и описания всех аддитивных характеров поля P получим T (u)-1 1 N(z,u)= Е ^ X(c(u(i) - z)), i=o q ceP откуда N (z,u) = T(ul + OM. (5) q q Для каждого элемента z Е P обозначим Az - отображение из поля P в множество C*, задаваемое по правилу Az(x) = х(-zx) для всех x Е P. Очевидно, что Az является аддитивным характером поля P. Обозначим через Lp(f) множество всех ЛРП над полем P с характеристическим многочленом f (x). Приведём результаты работы [3] (см. также [2, теорема 8.84]). С целью полноты изложения дадим их доказательство в удобных для нас обозначениях. Часть фрагментов доказательства будет использоваться в дальнейшем. Теорема 2. Пусть f (x) -неприводимый многочлен степени m над полем P = = GF(q), f(x) = x, t = T(f) = (qm - 1)/d, а - корень f(x) в поле Q = GF(qm), u - ненулевая ЛРП из множества Lp(f), имеющая представление u(i) = trqm(ааг), i ^ 0, a Е Q. Тогда (u) = - ^ + ^ E -'(a)G(-', х'), (6) а при z = 0 az(u) = d - d £ ^'(a)G(?//,x/) + d E -'(a)G(V/, x')G(-, Az), (7) где - - ограничение характера -' на поле P; A - группа мультипликативных характеров поля Q, аннулирующих элемент а; -00 - её нейтральный элемент; B - её подгруппа, состоящая из характеров, аннулирующих группу P*, причём qm - 1 qm - 1 |A| = q--, |B| q t [t,q - 1] Доказательство. Заметим, что элемент a в представлении элементов ЛРП u с использованием функции след из условия теоремы - однозначно определённый ненулевой элемент поля Q. Тогда если х/ - поднятие характера х до поля Q, определённое равенством (3), то t-1 az(u) = Е Х(-1cz)E x'(caai). ceP* i=o С использованием соотношения (4) представим az (u) в виде az(u)= Z х(-cz)Ef EG^X^W) ceP* i=o у- - 1 ф' где суммирование ведётся по всем мультипликативным характерам ф/ поля Q. Изменив порядок суммирования, получим 1 t-i az(u) = --7 E x(-cz) E С(ф/, хОФ^а) - ФЧ^). (8) - - 1 ceP * ф' i=o Заметим, что если ф/(а) = 1, то так как ord а = t, справедливы равенства £ ф/Cai) = £ (Ф/(«)), = (ф/(а))'- 1 = ф/(а,) - 1 = ф/(е) - 1 = 0. i=o i=o Ф/(а) - 1 Ф/(а) - 1 Ф/(а) - 1 Таким образом, в правой части равенства (8) достаточно ограничиться суммированием по всем мультипликативным характерам ф/, для которых ф/(а) = 1. Значит, az(u) = -m^ Е х(-cz) Е G^Mca). - - 1 ceP * ф'еА Тогда az(u) = d £ Ф^МФ^О Е ф/(c)Лz(c) = d Е ф^С^хОС^Л), (9) d Ф'еА ceP * d Ф'еА где ф - ограничение характера ф/ на поле P. Пусть z = 0, тогда характер Л,г тривиален и, согласно теореме 1, С(ФА) = (- - 1, если ф = ф°, I 0, если ф = ф°. Множество B состоит из всех мультипликативных характеров ф/ поля Q, для которых выполнены соотношения ф/(а) = 1, ф^) = 1 для всех c G P*. Тогда, согласно равенству (9), получим a°(u) = i-1 Е ФЧа)С(ф,х/). (10) d Ф'ев Найдём |B |. Пусть 9 - примитивный элемент поля P, тогда множество B состоит из всех мультипликативных характеров ф/ поля Q, для которых ф/(а) = 1 и ф/(9) = 1, т. е. таких характеров, которые аннулируют группу H = (а, 9), порождённую элементами а и 9. Порядок h группы H равен [ord а, - - 1] = [t, - - 1], поэтому, согласно равенству (2), I = -m - 1 -m - 1 h [t,- - 1]' Выделив в равенстве (10) отдельно слагаемое, соответствующее тривиальному характеру ф° G B, и воспользовавшись теоремой 1, будем иметь a° (u) + = i-i E ф/(а)С(ф^/,х/). a a ф'ев\{ф0} Пусть теперь z - 0, тогда Az является нетривиальным аддитивным характером поля P и, согласно теореме 1, 0(ф, Az) - -1 для всех ф' € B. Тогда из равенства (9) получим az(u) - -1 Е Ф'(а)С(ф',x') + ^ Е ^'(a)G(^j',x')G(^,Az). d ф'ев d ф'еА\в Выделяя отдельно слагаемое, соответствующее тривиальному характеру ф0, согласно теореме 1, получим az(u) - - - -d Е Ф(a)G(tjj', x') + d Y, tf(a)G(J/,x!)G№,Ax). а а ф/ев\{ф'о} d ф'еА\в Осталось заметить, что множество A состоит из всех мультипликативных характеров, которые аннулируют группу {а), поэтому, согласно равенству (2), qm 1 qm 1 | A| - - q-1. ord а t Теорема доказана. ■ 3. Линейные рекурренты максимального периода Приведём первый простейший случай, когда теорема 2 позволяет найти точные значения частот появлений элементов на циклах ЛРП. Пусть P - GF(q), f (x) € P[x] -многочлен максимального периода T(f) - qm - 1. Каждая ненулевая ЛРП u € Lp (f) является ЛРП максимального периода T(u) - - qm - 1. Как показано в теореме 2, в этом случае |A| - |B| - 1, a0(u) - q - 1, а при z - 0 выполнено az(u) - 1. Таким образом, из равенства (5) получим хорошо известный результат [4, 5] для числа N(z, u) появлений элемента z € P среди элементов u(0), u(1), ..., u(T(f) - 1): N(z, u) m1 qm 1 - 1, если z - 0, qm-1, если z - 0. Отметим, что в работах [4, 5] для доказательства этих формул используется комбинаторный метод. 4. Линейные рекурренты периода (qm - 1)/2 Пусть P - GF(q), где q - нечётное число, f (x) -неприводимый многочлен степени m над полем P, имеющий период T(f) - (qm - 1)/2. Получим точные значения для числа N(z,u) появлений элемента z € P среди элементов u(0), u(1), ..., u(T(f) - 1) для всех ЛРП u € LP (f). Нам понадобятся некоторые дополнительные сведения о суммах Гаусса над конечными полями. Рассмотрим отображение n : P* ^ C*, определённое для всех а € P* по правилу 1 , если a является квадратом в поле P, П(а) - \ р - 1, если a не является квадратом в поле P. Отображение n является мультипликативным характером поля P, имеющим порядок 2. Характер n называется квадратичным мультипликативным характером поля P. Если y - примитивный элемент поля P, то n(a) - 1 тогда и только тогда, когда a G (72), где (72) = H - группа порядка (q -1)/2, порождённая элементом 72. Согласно равенству (2), п является единственным нетривиальным характером, аннулирующим группу H. Для суммы Гаусса С(ф,х), где ф = п, а х - канонический аддитивный характер поля P, можно точно вычислить её значение. Теорема 3 [2, теорема 5.15]. Пусть P = GF(q), где q = ps, p - простое число, s G N. Тогда (-1)s-1^q, если p = 1 (mod 4), (-1)s-1is^q, если p = 3 (mod 4). Нам понадобится несколько вспомогательных результатов. Лемма 1. Пусть п - квадратичный характер поля P = GF(q), q = ps, p - простое число, s G N, e - единица поля P. Тогда 1 , если p = 1 (mod 4) , !(-1)s, если p = 3 (mod 4). Доказательство. Пусть 7 - примитивный элемент поля P, тогда элемент Y(q-1)/2 отличен от e и является решением уравнения x2 = e. Значит, 7(q-1)/2 = -e и п(-e) = п(т(q-1)/2) = (п(т))(?-1)/2 = (-1)(q-1)/2, так как 7 не является квадратом в поле P. Таким образом, п(-e) = 1 тогда и только тогда, когда (q - 1)/2 - чётное число. Это равносильно тому, что 4 \ (ps - 1) = (p - 1)(1 + p + ... + ps-i). Если p = 1 (mod 4), то данное соотношение верно для всех s G N. Если p = 3 (mod 4), то p-1 = 2 (mod 4), и рассматриваемое соотношение выполнено, если 2 \ (1+p+.. .+ps-i), т. е. если s - чётное число. ■ Лемма 2. Пусть п' - квадратичный характер поля Q = GF(qm), где q - нечётное число, ф - ограничение характера п' на поле P = GF(q). Тогда 1) если m - нечётное число, то ф = п - квадратичный характер поля P; 2) если m - чётное число, то ф = ф0 - тривиальный характер поля P. Доказательство. Пусть 7' и 7 - примитивные элементы полей Q и P соответственно. Так как ф аннулирует группу H = (72), то из равенства (2) либо ф = п, либо ф = ф0. Характер п' аннулирует группу H' = ((7')2), поэтому ф = ф0 тогда и только тогда, когда P* -подгруппа группы H'. Это выполнено, только если q - 1 делит (qm - 1)/2 = (q - 1)(1 + q + ... + qm-1)/2, т.е. если m - чётное число. ■ Докажем теорему, обобщающую на случай произвольного q результаты из [6, теорема 7], где рассматривается ситуация, когда q = p - простое число. Теорема 4. Пусть f (x) - неприводимый многочлен степени m = 2А +1 над полем P = GF(q), где q = ps, p - нечётное простое число, s G N. Тогда если T(f) = (qm - 1)/2 и ненулевая ЛРП u G Lp(f) имеет представление u(i) = trQ(aai), i ^ 0, то N (0, u) = ^-, если p = 1 (mod 4), , если p = 3 (mod 4), 2 где П - квадратичный характер поля Q = GF(qm). Доказательство. Согласно соотношению (5), справедливо равенство N (z,u) = + 1 ^ (u), q q где T (u)-1 (u) = E x(-cz) E xMO^ (n) ceP* i=o X - канонический аддитивный характер поля P. Изучим величину az (u). 1) Пусть z = 0. Тогда из равенства (6) получим *o(u) = - ^ + Е -^G^xO, (12) 2 2 } где х/ и -00 - канонический аддитивный и тривиальный мультипликативный характеры поля Q соответственно; B - множество всех мультипликативных характеров -/ поля Q, аннулирующих группу (а, 7), порождённую корнем а многочлена f (x) и примитивным элементом 7 поля P. Так как 0/(а) = 1 для каждого характера -/ Е B и |(a)| = T(f) = (qm - 1)/2, то из (2) либо -/ = п/, либо -/ = 00. Согласно доказательству леммы 2, число q - 1 не делит (qm - 1)/2, а значит, (а) = (а, 7). Таким образом, (a,Y) = Q*, B = {00} и из равенства (12) получим () q - 1 N (0 ) T (u) + ^(u) qm-1 - 1 (u) = - ~, N (0,u) = ~ + - = . 2) Пусть z = 0. Тогда из равенства (7) и соотношения B = {-0} будем иметь ^z (u) = 1 + 1 Е -/(a)G(-/,x/)G(-,Az), 2 2 ф'ел\{ф'0} где A - множество всех мультипликативных характеров -/ поля Q, аннулирующих группу (а); - - ограничение характера -/ на поле P; Az - аддитивный характер поля P, определённый равенством Az(x) = x(-zx), x Е P. Как отмечалось при доказательстве п. 1, элемент а аннулируется только характерами - /, п/. Значит, A = {-/, п/}. Поэтому с использованием леммы 2 и равенства п/ = П получим ^z (u) = 1 + 1 n/(a)G(n/,x/)G(n,Az). Для суммы Гаусса G(n, Az) имеем G(n,Az)= Е n(c)Az(c) = Е П(с)Х(-1cz) = Е П(-bz-1)X(b) = ceP * ceP * beP* = n(-z-1)G(n,x) = n(-e)n(z-1)G(n,x) = n(-e)n(z)G(n,x). а если z = 0, то qm-1 + n'(az)q N (z,u) = < л 2 qm-1 + n'(az)(-1)AsqA Таким образом, a(u) = 1 + 2n'(az)n(-e)G(n, x)G(n', x'). (13) Согласно теореме 3 и лемме 1, П(-e)G(n,x) f(-1)S-1/q, если p - 1 (mod4), |-i^v^q, если p = 3 (mod 4), ' Г(-1)ms-1qm/2, если p = 1 (mod 4), (П,Х ) |(-1)ms-1imsqm/2, если p = 3 (mod 4). Тогда из равенства (13) получим 1 + n'(az)q(m+1)/2 если p = 1 (mod 4), если p = 3 (mod 4), az (u) = < 2 1 + (-1)mV(az )i(m+1)sq(m+1)/2 2 , а значит, согласно (11), qm-1 + n'(az)qA если p = 1 (mod 4), , если p = 3 (mod 4). N (z,u) = + *M = < qq 2 qm-1 + n'(az)(-1)AsqA 2 Теорема доказана. ■ Следствие 1. В условиях теоремы 4 имеют место соотношения qm-1 _ 1 qm- 1 i qA N(0, u) = q 1, N(z,u) = q-, z Е P*, причём у каждой ЛРП u для половины элементов z Е P* в последней формуле надо взять знак «+», а для другой половины - знак « -». Рассмотрим теперь случай, когда m - чётное число. Следующая теорема обобщает на случай произвольного q результаты из [6, теорема 7]. Теорема 5. Пусть f (x) -неприводимый многочлен степени m = 2А над полем P = GF(q), где q = ps, p - нечётное простое число, s Е N. Тогда если T(f) = (qm - 1)/2 и ненулевая ЛРП u Е (f) имеет представление u(i) = trQ(aai), i ^ 0, то qm-1 - (q - 1)n'(a)qA-1 - 1 если p = 1 (mod 4), если p = 3 (mod 4), N(0, u) = а если z = 0, то 2 qm-1 - (q - 1)n'(a)(-1)AsqA-1 - 1 2 qm-1 + n'(a)qA-1 _1 ( A -, если p = 1 (mod 4), N(z, u) = 2 qm-1 + n'(a)(-1)AsqA-1 если p = 3 (mod 4), 2 где n' - квадратичный характер поля Q = GF(qm) Доказательство. С использованием доказательства леммы 2 при чётном m имеем P* -подгруппа группы (а), поэтому в обозначениях доказательства теоремы 4 B = м, ,n'} = A. 1) Пусть z = 0. Из равенства (12) получим *0(u) = - ^ + ^ n'(a)G(n/,X/), если p = 1 (mod 4), если p = 3 (mod 4). а значит, согласно теореме 3, ' -(q - 1)(1 + n/ (a)qm/2) 2 0o(u) = < - (q - 1)(1 + n/(a)imsqm/2) 2 Тогда будем иметь N (0,u) = ZM + ^M qq qm-1 - (q - 1)n/(a)qA-1 - 1 если p = 1 (mod 4), если p = 3 (mod 4). 2 qm-1 - (q - 1)n/ (a)(-1)AsqA-1 - 1 2 2) Пусть z = 0. Из равенства (7) получим ^ (u) = 1 - 1 n/(a)G(n/ ,Х/), а значит, согласно теореме 3, ' 1 + n/(a)qm/2 (u) = < если p = 1 (mod 4), 2 1 + n/(a)imsqm/2 , если p = 3 (mod 4). 2 Тогда будем иметь N (z,u) = T(u) + ^M qq qm-1 + n/(a)qA-1 если p = 1 (mod 4), 2 As^A-1 qm-1 + n/(a)(-1)Asq -, если p = 3 (mod 4). 2 Теорема доказана. ■ Следствие 2. В условиях теоремы 5 имеют место соотношения ^ qm-1 ± (q - 1)qA-1 - 1 Л„ , qm-1 т qA-1 с р* N(0,u) =---, N(z,u) =---, z E P , причём у каждой ЛРП u все элементы z E P* появляются одинаково часто. 5. Суммы Гаусса в полупримитивном случае Пусть P = GF(q) -поле порядка q = ps, где p - простое число, s Е N, f (x) - неприводимый многочлен степени m над полем P, f (x) = x. Рассмотрим ситуацию, когда T(f) = (qm - 1)/d, где d - делитель числа qm - 1, причём найдётся натуральное число j, такое, что d | (pj + 1). Так как ранее был изучен случай d = 1 и 2, далее будем рассматривать случай d > 2. Найдём точные значения для числа N(z,u) появлений элемента z Е P среди элементов u(0), u(1), ..., u(T(f) - 1) в каждой ненулевой ЛРП u Е LP(f). Отметим, что в этом случае T(u) = T(f). Нам понадобится ряд вспомогательных результатов. Лемма 3. Пусть число p полупримитивно по модулю d, q = ps, d | (qm - 1), d > 2 и l = min{j Е N : d | (p + 1)}. Тогда 2l | sm. Доказательство. Рассмотрим кольцо Z/d классов вычетов по модулю d. Из условия следует, что для класса в = [p]d справедливы равенства fims = [1]d, в1 = [-1]d, в21 = [1]d. Пусть k = ord в - мультипликативный порядок элемента в. Покажем, что k = 2l, тогда отсюда будет следовать, что 2l | sm. Ясно, что k | 2l. Допустим, что k < 2l, тогда k ^ l и из равенств вk = [1]d, в1 = [-1]d получим вк + в1 = вk([1]d + в1-к) = [0]d. В силу обратимости элемента в отсюда будем иметь в1-к = [-1]d. (14) Так как d > 2, то [1]d = [- 1]d, а значит, l - k = 0. Покажем, что k = 0. В случае k = 0 имеем в = [1]d, d | (p - 1), d | (pl + 1), следовательно, d | (pl + p), d | p(p1-1 + 1) и, значит, d | (p1-1 + 1). Чтобы не получить противоречие с выбором l в условии, имеем l = 1, что приводит к противоречию с условием на d. Таким образом, k = 0, и в равенстве (14) получаем 0 < l - k < l, что противоречит выбору l. ■ Доказательство следующего результата подробно изложено в [2, теорема 5.16]. Лемма 4 (теорема Штикельбергера). Пусть в условиях леммы 3 гф - мультипликативный характер порядка d в поле T = GF(p21), х - канонический аддитивный характер поля T, тогда i i Й - p + 1 - -p1, если а чётно, a --- нечётно, °(ф-х)={^ .. dp1 + ! p1, если d нечётно или --- чётно. d Следствие 3. В условиях леммы 4 для каждого i = 1, 2, . . . , d - 1 {< ЛМ 1 А " p1 + 1 (-1)'p1, если d чётно, a --- нечётно, G(фi'X) = i , „ . dp1 + 1 .. p , если d нечётно или - чётно. d Доказательство. Пусть Gi = С(ф'1, х), di = ord ф^ где i =1, 2,... ,d - 1. Тогда d = pl + 1 = (p1 + 1)(d,i) (15) i (d, i) di d Рассмотрим несколько случаев. 1) Если d - нечётное число, то из равенств (15) получим di - нечётное число, di | (pl + 1). Тогда по лемме 4 Gi = p 2) Если d - чётное число и (p1 + 1)/d - чётное число, то, согласно (15), (p1 + 1)/dj - чётное число, и по лемме 4 G = p1. 3) Если d - чётное число, а (p1 + 1)/d - нечётное число, то рассмотрим два случая: за) если i - чётное число, то, согласно (15), (p1 + 1)/dj - чётное число, и по лемме 4 G = p1; зб) если i - нечётное число, то, согласно (15), (p1 + 1)/dj - нечётное число, и по лемме 4 G = -p1. Следствие доказано. ■ Нам понадобится конструкция поднятия мультипликативного характера. Пусть T = GF(q1) и Q = GF(q2) -расширение степени r поля T, т.е. q2 = q[. Определим норму элемента a Е Q* над полем T следующим равенством: 2 r-1 ql-1 Ч2-1 N2 (a) = a ■ aq1 ■ a?1 ■ ■ ■ aq1 = a «1-1 = a «1-1. Так как (N^2(a))q1-1 = e, таким образом определено отображение N® : Q* ^ T*, которое обладает следующими свойствами: 1) Nq2(ab) = N® (a)N® (b) для всех a, b Е Q*; 2) Nq2 сюръективно. Пусть - - мультипликативный характер поля T. Рассмотрим отображение -' : Q* ^ C*, осуществляемое по правилу -'(a) = -(N2(a)), a Е Q*. Из свойства 1 для нормы получим, что -' является мультипликативным характером поля Q. Его называют поднятием мультипликативного характера - до поля Q. Обозначим -o и -0 тривиальные мультипликативные характеры полей T и Q соответственно. Заметим, что для каждого k Е N0 справедливы равенства (-')k(a) = (-'(a))k = (-(N2(a)))k = -k(N£(a)), a Е Q*. (16) Отсюда с учётом сюръективности отображения N^2 получим, что (-')k = -0 тогда и только тогда, когда -k = -0. Таким образом, для порядков характеров - и -' имеем ord - = ord -'. (17) Следующий результат подробно доказан в [2, теорема 5.14]. Лемма 5 (теорема Дэвенпорта - Хассе). Пусть х - аддитивный, а - - мультипликативный характеры поля T = GF(q1), не являющиеся одновременно тривиальными. Тогда если Q = GF(q2) -расширение степени r поля T и х',-' - поднятия характеров х и - соответственно до поля Q, то ',х') = (-1)r-1G(-, х)г. Теорема 6. Пусть простое число p полупримитивно по модулю d, d > 2, d | (qm - 1), q = ps и число l выбрано так, как в лемме 3. Тогда если -' - мультипликативный характер поля Q = GF(qm), имеющий порядок d, а х' - канонический аддитивный характер поля Q, то для всех i = 1, 2, . . . , d - 1 {(-1)(i+1)r-1qm/2, если d чётно, a p-+- нечётно, dp1 + 1 (-1)r 1qm/2, если d нечётно или --- чётно, d где r = (ms)/(2l). Доказательство. Из леммы 3 следует, что поле T = GF(p21) является подполем поля Q. Так как d \ (p21 - 1), в циклической группе всех мультипликативных характеров поля T есть подгруппа порядка d. Разные характеры из этой подгруппы имеют разные поднятия до поля Q, которые, согласно (17), имеют такие же порядки. Таким образом, найдётся мультипликативный характер ф поля T, такой, что ord ф = d и его поднятие до поля Q совпадает с ф'. Кроме того, согласно (16), поднятие характера фг до поля Q будет совпадать с характером (ф')г для всех i = 1, 2,... , d - 1. Для завершения доказательства остаётся воспользоваться следствием 3 и леммой 5. ■ Лемма 6. Пусть в условиях теоремы 6 d( -натуральный делитель числа d, ф' = = (ф')^/Й1, y - примитивный элемент поля Q. Тогда для каждого a G Q*: 1) ф( (a) = 1 тогда и только тогда, когда a G (Ydl); 2) ф' (a) = -1 тогда и только тогда, когда d( - чётное число, a G (Ydl) и a G (Ydl/2); 3) ф' (a-1) = (-1)£ для некоторого е G No тогда и только тогда, когда ф' (a) = = (-1)£. Доказательство. 1) Рассмотрим группу всех мультипликативных характеров поля Q, аннулирующих подгруппу (Ydl) группы Q*. Из равенства (2) следует, что её порядок равен d(. Таким образом, группа (ф'), имеющая порядок d(, совпадает с группой всех характеров, аннулирующих группу (Ydl). Так как ф' -её образующий, то ф' (a) = 1 тогда и только тогда, когда a G (Ydl). 2) Равенство ф'(a) = -1 равносильно тому, что (ф'(a))2 = ф'(a2) = 1, а ф'(a) = 1, т. е. по п. 1 a2 G (Ydl) и a G (Ydl). Если d( - нечётное число, то соотношение (ф'(a))dl = = (-1)dl = -1 противоречит условию ord ф' = d. Пусть d( -чётное число. Опишем все элементы a G Q*, такие, что a2 G (ydl). Используя представление a = Ys, где s = 0,1,... , qm - 2, получим, что Y2s G (Ydl) тогда и только тогда, когда d( \ 2s, т. е. (di/2) \ s. Таким образом, a = Ydlt/2, где t = 0,1,..., (2(qm - 1)/di) - 1, или a G (Ydl/2). 3) Доказательство непосредственно следует из п. 1 и 2. ■ 6. Полупримитивный случай. Нулевые элементы на циклах Рассмотрим вопрос о распределении нулей на циклах ЛРП. Следующая теорема обобщает результаты [3, формулы (3.2)], где указаны только типы распределений, но не получены условия, при которых каждая конкретная ЛРП u имеет данный тип. Теорема 7. Пусть f (x) - неприводимый многочлен степени m над полем GF(q), q = ps, p - простое число, s G N, T(f) = (qm - 1)/d, d > 2, число p полупримитивно по модулю d, d( = ((qm - 1)/(q - 1),d), r = (ms)/(2l), где l определено в лемме 3. Тогда для каждой ненулевой ЛРП u G LP(f), имеющей представление u(i) = trQ(aal), i ^ 0, справедливо: 1) если dr/d( -чётное, или d - нечётное, или (p1 + 1)/d - чётное, то qm-i + (-1)r (q - 1)qm/2-i - 1 d , dA ---, если a G (Y ), d + (-1)r-i (q - 1)(di - 1)qm/2-i - 1 N (0, u) qm-1 если a G (Ydl); d 2) если dr/d1 -нечётное, d - чётное, (p1 + 1)/d - нечётное, то d1 -чётное и f-m-i + (-1)r(- - 1)-m/2-i - 1 _ -, если a G (Ydl) или a G d N(0, u) -1 + (-1)r-1(- - 1)(di - 1)-m/2-i - 1 , . dn , d1/2\ -------r^---, если a G (ydl) и a G (Ydl/2). d Доказательство. С использованием равенства (5) получим N (0, u) = + Ом, q q t (/)-i где a°(u) = £ Z x(cu(i)); x - канонический аддитивный характер поля P. Из раceP* i=° венства (6) будем иметь a°(u) = - i-d + i-1 E ф^С^хО, d d ф^в^ф',} где x/ и ф° - канонический аддитивный и тривиальный мультипликативный характеры поля Q соответственно; B - множество всех мультипликативных характеров ф/ поля Q, аннулирующих группу (а, y), порождённую корнем а многочлена f (x) и примитивным элементом y поля P. Порядок группы (а, y) делится на (-m - 1)/d, а значит, он равен (-m - 1)/d/, где d/ -делитель d. Как показано при доказательстве теоремы 2, f7m - 1 d( f7m - 1) d/ = |B| = ----- = 7-(- ((-m - 1)/d, - - 1) = 1 1 [(-m - 1)/d,- - 1] (-m - 1)(- - 1)VW " )Ч ' d -((-m - 1)/d, - - 1) = (-" - 1,d(- - 1)) = ((-m - 1)/(- - 1),d) = di. - - 1 - - 1 Тогда группа B является циклической группой, порождённой характером ^)d/dl = ф/, где ф/ - мультипликативный характер порядка d поля Q = GF(-m). Заметим, что если характеры пробегают всю группу B, то характеры, сопряжённые к ним, также пробегают всю группу B, поэтому -- 1 -- 1 dl-1 a°(u) = - + Е (ф/№)£((# )i,x/) = d d i=1 1 1 dl - 1 = -+ ^ Е (ф/)i(a-1 )С((ф)i, x/) = (18) 1 1 dl - 1 - + £ (ф/)di/dl(a-1)^^)^^,Х/). d d i=1 Рассмотрим два случая. Случай 1. Пусть d - нечётное число или (p1 + 1)/d - чётное число. Тогда по теореме 6 .7-1 /у - 1 dl-1 а - 1 f , dl-i N a°(u) = - L- + L £ (ф/)i(a-1)(-1)r-i-m/2 = ^ 1-1 + (-1)r-i-m/2 £ (ф/(a-1))i ao(u) - ^ (-1 + (-1)rqm/2 + (-1)r-1qm/2 IE (ф1 (a-1))*) . (19) а значит, Заметим, что *-1 f (ф1 (a-1))d1 - 1 если ф' (a-1) -1 Е(Ф1 (a-1))* - i ф'(a-1) - 1 , если ф1 (a ) -1, *=0 [db если ф1 (a-1) -1, а так как ord ф' - d1, то -1 Е (Ф1 (a-1))* - Тогда из равенства (19) и леммы 6 получим (^ (-1 + (-1)rqm/2) , если a € {ydl), 00 (u) - < q d 1 ( (-1 + (-1)r-1(d1 - 1)qm/2) , если a € {y"1 ). Подставляя найденные значения a0(u) в равенство для частот N(0,u), получим I qm-1 - 1 + (-1)r (q - 1)qm/2-1 dlX n (0 u) - qm-!+^u) - f-d-' если a € {Yd1) N(0,u)- dq + q - i qm-1 - 1 + (-1)r-1(q - 1)(d1 - 1)qm/2-1 d ---, если a € {y ). d Случай 2. Пусть d - чётное число, (p1 + 1)/d - нечётное число. Из равенства (18) с использованием теоремы 6 будем иметь 00(u) - ^^ ^-1 + "е (Ф1 (a-1))i(-1)(w+1)r-1qm/2^ , где k - d/d1. Тогда 00(u) - ^ (-1 + (-1)r-1qm/2dE (Ф1 (a-1)(-1)kr)*) , dt-^,..^ I > - 1, если ф1 (a-1) - (-1)k^ и значит, 00(u) - ^ (-1 + (-1)rqm/2 + (-1)r-1qm/2IE (ф1 (a-1)(-1)kr. Заметим, что (Ф1 (a-1)(-1)kr)dl - 1 E (Ф1 (a-1 )(-1)kr)* - i ф'(a-1)(-1)kr - 1 *=0 1 d1, если ф1 (a-1) -(-1)kr. di-1 - - 10, если ф1 (a-1) - 1, *=0 4T14 ld1, если ф1 (a-1) - 1. Так как d - чётное число и ord = d1, то (^ (a-1)(-1)kr )d1 = (^1 )d1 (a-1)(-1)krd1 = (-1)dr = 1, поэтому ( H

Скачать электронную версию публикации

Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра: учебник. Т. 2. М.: Гелиос АРВ, 2003. 416c.

Лидл Р., Нидеррайтер Г. Конечные поля. М.: Мир, 1988.

McEliece R. J. Irreducible cyclic codes and Gauss sums // Combinatorics. 1975. P. 185-202.

Цирлер Н. Линейные возвратные последовательности // Кибернетический сборник. 1963. №6. C. 55-79.

Лаксов Д. Линейные рекуррентные последовательности над конечными полями // Математика. Сборник переводов. 1967. Т. 11. №6. С. 145-158.

Baumert L. D. and McEliece R. J. Weights of irreducible cyclic codes // Information and Control. 1972. V. 20. P. 158-175.

Nelubin A. S. Distribution of elements on cycles of linear recurrences over Galois fields // Formal Power Series and Algebraic Combinatorics. 12-th Intern. Conf. FPSAC. Moscow, 2000. P. 534-542.