"Записки научных семинаров ПОМИ"

Том 432, стр. 58-67

Полиномиальная интерполяция над кольцами вычетов $Z_n$

Н. Н. Васильев, О. Канжелева

С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, наб. р. Фонтанки, д. 27, С.-Петербург 191023, Россия

nn.vasiliev@gmail.com

С.-Петербургский государственный политехнический университет, С.-Петербург, Россия; Google Corporation, Irvine, USA

olga.kanzheleva@gmail.com

Аннотация: Мы рассматриваем задачу полиномиальной интерполяции в кольцах вычетов $Z_n$. Случай общего $n$ легко сводится к случаю $p^k$ с помощью китайской теоремы об остатках. Однако в отличие от задачи интерполяции над полем, где результат может быть получен с помощью интерполяционной формулы Лагранжа, в случае кольца задача значительно сложнее. Не всякая функция над кольцом вычетов может быть представлена полиномом, а интерполяционный полином, если он все-таки существует, не является единственным. Полиномы, представляющие нулевую функцию, -- так называемые нуль-полиномы -- образуют идеал, не являющийся главным. С помощью системы Singular мы вычисляем базисы Грёбнера идеала нуль-полиномов в кольцах вычетов. Эти базисы позволяют приводить результат интерполяции к канонической форме, а также проверять имеющиеся теоретические оценки степени минимального нормированного нуль-полинома. Также мы описываем связь оценок мощности минимальных интерполяционных множеств, введенных в работе Гопалана, с оценками количества пермутационных полиномиальных функций над $Z_n$. В частности, выводится рекуррентная формула для количества пермутационных полиномиальных функций над кольцом вычетов. Библ. -- 3 назв.
Ключевые слова: кольцо вычетов, нуль-полиномы, многочлены Фробениуса, пермутационные полиномы над кольцом [residue ring, null polynomials, Frobenius polynomial, permutational polynomial over residue ring]

Полный текст(.pdf)