Quels sont quelques exemples de systèmes de numérotation pour lesquels il est facile de généraliser des polynômes de permutation?
J'écris un devoir sur les polynômes de permutation (PP). J'ai déjà exploré quelques généralisations et caractérisations des PP sur$\mathbb{Z}_p$ pour $p$ premier (et champs finis en général) et $\mathbb{Z}$. Je recherche un autre système de numérotation à analyser, idéalement un système où il est facile de dériver une forme générale pour n'importe quel PP. C'était facilement réalisable pour$\mathbb{Z}$ en utilisant les propriétés de base de la carte d'évaluation et pour $\mathbb{Z}_p$utilisant l'interpolation de Lagrange + techniques associées. J'aimerais que ce système de numérotation soit un corps non fini ou n'importe quel anneau commutatif avec l'unité. Si quelqu'un a des suggestions, ce serait très apprécié.
Réponses
Les éléments suivants me viennent à l'esprit.
Polynômes de permutation quadratique sur $\Bbb{Z}_m$.
Laisser $m>1$être n'importe quel entier. Considérons la fonction polynomiale quadratique$$ f:\Bbb{Z}_m\to\Bbb{Z}_m, x\mapsto ax+bx^2. $$ Prouvez ce qui suit (c'est relativement facile, demandez si vous avez besoin d'un indice).
Lemme. Si$\gcd(a,m)=1$ et $b$ est divisible par chaque facteur premier de $m$, puis $f$ est une permutation.
La raison pour laquelle je recommande cela est que de tels polynômes de permutation sont largement utilisés dans la norme LTE comme entrelaceurs de code turbo (la version de la norme qui a été finalisée en 2009, mises à jour en attente, et finalement cette partie est susceptible de devenir obsolète). En d'autres termes, à moins que mes informations ne soient "datées", il est probable que votre téléphone portable calcule ces permutations plusieurs millions de fois par seconde. La version de LTE dont je me souviens spécifiait une plage de valeurs pour$m$, chacun divisible par une puissance relativement élevée de deux, et une $(a,b)$ paire pour chacun de ces $m$. Les raisons de choisir de telles permutations sont un peu techniques, mais je pense que cette application est trop cool pour passer.
L'idée a été introduite dans
J. Sun et OY Takeshita, «Interleavers for turbo codes using permutation polynomials over integer rings», IEEE Trans. Inf. Théorie, vol. 51, no. 1, pp. 101-119, janvier 2005.
C'est derrière le paywall IEEE, mais j'espère que votre institut y aura accès. Probablement toute référence aux minutes 3GPP et / ou aux spécifications que j'ai utilisées à l'époque sont obsolètes. Quand je travaillais pour un gros joueur cellulaire à l'époque, j'étudiais un peu plus intensément les permutations inverses :-)