Polynomial interpolation over residue rings ℤ∕nℤ
N.N. Vasilyev
(St.Petersburg Department of V.A.Steklov Institute of Mathematics, Russian Acad. of Sci.)
E-mail address: vasiliev@pdmi.ras.ru
O.Yu. Kanzheleva
(St. Petersburg State Polytechnical University)
E-mail address: olga.kanzheleva@gmail.com
We consider the problems of polynomial interpolation and p-adic approximation over the residue rings ℤ∕nℤ. The general case can be easily reduced to the case of n = pk due to chinese reminder theorem. In contrast to the interpolation problem over the fields the case of the rings is much more complicated due to the existence of non-zero polynomials represented zero-function [1] . Also the result of interpolation is not unique in general case. We compute in the frame of CAS system Singular the Groebner bases of ideals of null-polynomials over residue rings. It allow us to get a canonical form for the results of interpolation. We describe also a connection between estimations of cardinality of the interpolating sets introduced in [2], and the total number of the permutational polynomials over the ring. As a consequence we give a recurrent formula for the number of permutation polynomials over ℤ∕pkℤ.
[1] S.Li "Null Polynomials modulo m" — arXiv:math/0510217v2 [math.NT]
[2] P.Gopalan "Query-efficient algorithms for polynomial interpolation over composites" — SIAM J. Comput. 38(3), pp. 1033-1057 (2008)
Полиномиальная интерполяция над кольцами вычетов ℤ∕nℤ
Н.Н. Васильев
(Санкт Петербургское Отделение Математического Института им. В.А. Стеклова РАН)
E-mail address: vasiliev@pdmi.ras.ru
О.Ю. Канжелева
(Санкт Петербургский Государственный Политехнический Университет)
E-mail address: olga.kanzheleva@gmail.com
Мы рассматриваем задачи полиномиальной интерполяции и p-адической аппроксимации в кольцах вычетов ℤ∕nℤ. Случай общего n легко сводится к случаю n = pk с помощью китайской теоремы об остатках. Однако, в отличие от задачи интерполяции над полем, где результат может быть получен с помощью интерполяционной формулы Лагранжа, в случае кольца задача значительно сложнее. Не всякая функция над кольцом вычетов может быть представлена полиномом, а интерполяционный полином, если он все-таки существует, не является единственным. Множество полиномов, представляющих нулевую функцию — так называемые нуль-полиномы, образуют идеал, не являющийся главным, причем о степенях образующих этого идеала мало что известно. Неизвестна, например, даже степень минимального нормированного нуль-полинома над ℤ∕nℤ. С помощью системы Singular мы вычисляем базисы Грёбнера идеала нуль-полиномов в кольцах вычетов. Эти базисы позволяют приводить результат интерполяции к канонической форме, а также проверять имеющиеся теоретические оценки степени минимального нормированного нуль-полинома. Также мы описываем связь оценок мощности минимальных интерполяционных множеств, введенных в [2], с оценками количества перестановочных полиномов над ℤ∕pkℤ. В частности, выводится рекуррентная формула для количества перестановочных полиномов над кольцом вычетов.