Свойства линейных и полилинейных рекуррент над кольцами Галуа (I)

Предлагаемая работа является продолжением статьи тех же авторов “Псевдослучайные и полилинейные последовательности” [8]. В работе рассматриваются новые проблемы, связанные с оценками рангов координатных последовательностей линейных и полилинейных рекуррент над кольцами Галуа и с изучением распределений знаков на циклах линейных рекуррент над кольцами вычетов.
В первой части (раздел 1) впервые публикуется полное изложение математического аппарата для исследования алгебраических свойств координатных последовательностей линейных рекуррент над кольцами Галуа, в основе которого лежат метод сечений и понятие формальной полиномиальной дистанции. Используя разработанный математический аппарат, удалось существенно усилить нижние оценки рангов координатных последовательностей линейных рекуррент максимального периода над кольцом вычетов $\mathbb Z_{p^n}$, полученные ранее в работах А. А. Нечаева, Z. D. Dai, D. Gollmann, и обобщить их на произвольные примарные кольца вычетов. Принципиальным продвижением является получение нижних оценок рангов координатных последовательностей для более широких классов законов рекурсии.
Во второй части статьи (разделы 2 и 3), которая будет опубликована в третьем томе “Трудов по дискретной математике”, с использованием оценок сумм характеров с полиномиальными аргументами будут усилены оценки частот появления элементов в линейных рекуррентах над кольцом $\mathbb Z_{p^2}$, рассмотрены некоторые вопросы теории полилинейных рекуррентных последовательностей над полями и кольцами Галуа и получены оценки рангов координатных последовательностей $k$-максимальной рекурренты над примарным кольцом вычетов $\mathbb Z_{p^n}$.