Каковы некоторые примеры систем счисления, для которых легко обобщить многочлены перестановки?
Я пишу задание по перестановочным многочленам (PP). Я уже исследовал довольно много обобщений и характеристик PP$\mathbb{Z}_p$ для $p$ простые (и конечные поля в целом) и $\mathbb{Z}$. Я ищу другую систему нумерации для анализа, в идеале такую, в которой легко вывести общую форму для любого PP. Это было легко сделать для$\mathbb{Z}$ используя основные свойства оценочной карты и для $\mathbb{Z}_p$с использованием методов интерполяции Лагранжа +. Я бы хотел, чтобы эта система нумерации была неконечным полем или любым коммутативным кольцом с единицей. Если у кого-то есть предложения, мы будем очень признательны.
Ответы
На ум приходит следующее.
Квадратичные многочлены подстановки на $\Bbb{Z}_m$.
Позволять $m>1$быть любым целым числом. Рассмотрим квадратичную полиномиальную функцию$$ f:\Bbb{Z}_m\to\Bbb{Z}_m, x\mapsto ax+bx^2. $$ Докажите следующее (это относительно просто, спросите, нужна ли вам подсказка).
Лемма. Если$\gcd(a,m)=1$ и $b$ делится на все простые множители числа $m$, тогда $f$ это перестановка.
Причина, по которой я рекомендую это, заключается в том, что такие полиномы перестановки широко используются в стандарте LTE в качестве перемежителей турбокода (версия стандарта, которая была завершена в 2009 году, ожидаются обновления, и в конечном итоге эта часть, вероятно, устареет). Другими словами, если моя информация не «устарела», скорее всего, ваш мобильный телефон вычисляет такие перестановки несколько миллионов раз в секунду. В версии LTE, которую я помню, был указан диапазон значений для$m$, каждый из которых делится на относительно высокую степень двойки, и оптимизированный $(a,b)$ пара для каждого такого $m$. Причины выбора таких перестановок носят технический характер, но я думаю, что это приложение слишком круто, чтобы пройти его.
Идея была представлена в
Дж. Сан и О. Ю. Такешита, «Перемежители для турбокодов, использующие многочлены перестановки над целочисленными кольцами», IEEE Trans. Инф. Теория, том 51, вып. 1. С. 101–119, январь 2005 г.
Это стоит за платным доступом IEEE, но, надеюсь, у вашего института есть доступ. Вероятно, любые ссылки на минуты и / или спецификации 3GPP, которые я использовал в тот день, устарели. Когда я работал на тогдашнего крупного сотового плеера, я изучал обратные перестановки более интенсивно :-)