Quelques bijections entre \( \mathbb{N} \) ou \( \mathbb{N}^* \) et \( \mathbb{N}[X] \) ou \( \mathbb{Z}[X] \) ...
Au nombre \[ n = \prod_{k=0}^{d} p_{i}^{e_i} \] |
on associe le polynôme \[ P_n(x) := \sum_{k=0}^{d} {e_i} x^{i} \] |
Cela suppose que les nombres premiers sont numérotés à partir de \( 0 \) : \( p_0 = 2, p_1 = 3, \dots \).
Exemple : \( 18 \), c'est \( 2 \times 3^2 \), ce que l'on peut aussi écrire \( p_0 \times p_1^2 \). On transforme ça en \( x^0 + 2 \times x^1 = 2x+1 \). Et donc avec cette bijection, \( 2x+1 \) est le polynôme numéro \( 18 \).
Sens nombre \( \longrightarrow \) polynôme | Sens polynôme \( \longrightarrow \) nombre |
|---|---|
| P(n)=my(f=factor(n));sum(i=1,#f~,f[i,2]*x^primepi(f[i,1]-1)) | a(p)=prod(k=0,poldegree(p),prime(1+k)^polcoeff(p,k)) |
| \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) | \(21\) | \(22\) | \(23\) | \(24\) | \(25\) | \(26\) | \(27\) | \(28\) | \(29\) | \(30\) |
| \(0\) | \(1\) | \(x\) | \(2\) | \(x^2\) | \(x + 1\) | \(x^3\) | \(3\) | \(2x\) | \(x^2 + 1\) | \(x^4\) | \(x + 2\) | \(x^5\) | \(x^3 + 1\) | \(x^2 + x\) | \(4\) | \(x^6\) | \(2x + 1\) | \(x^7\) | \(x^2 + 2\) | \(x^3 + x\) | \(x^4 + 1\) | \(x^8\) | \(x + 3\) | \(2x^2\) | \(x^5 + 1\) | \(3x\) | \(x^3 + 2\) | \(x^9\) | \(x^2 + x + 1\) |
Le souci avec les valuations \( p_i \)-adiques \( e_i \) précédentes est qu'elles sont positives ou nulles, or on aimerait bien pouvoir obtenir des coefficients de tous signes dans les polynômes.
Pour y remédier, on peut intercaler une bijection transformant les valuations en coefficients et qui ne soit pas l'identité, comme suit :
Au nombre \[ n = \prod_{k=0}^{d} p_{i}^{e_i} \] |
on associe le polynôme \[ P_n(x) := \sum_{k=0}^{d} {c_i} x^{i} \] |
où la fonction \( z \) qui convertit \( e_i \) en \( c_i = z(e_i) \) est donnée par :
\[ z: \mathbb{N} \to \mathbb{Z} \] \[ e \mapsto c = z(e) \] \[ \left \{ \begin{matrix} c & = & - e / 2 & \mbox{ si e est pair ;} \\ c & = & (e + 1) / 2 & \mbox{ si e est impair.} \\ \end{matrix} \right. \]Codage en PARI :
Sens nombre \( \longrightarrow \) polynôme | Sens polynôme \( \longrightarrow \) nombre |
|---|---|
| P(n)=my(f=factor(n));for(i=1,#f~,f[i,2]=apply(k->if(k%2==0,-k/2,(k+1)/2),f[i,2]));sum(i=1,#f~,f[i,2]*x^primepi(f[i,1]-1)) | a(p)=prod(k=0,poldegree(p),prime(1+k)^apply(c->if(c>0,2*c-1,-2*c),polcoeff(p,k))) |
Premières valeurs :
| \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) | \(21\) | \(22\) | \(23\) | \(24\) | \(25\) | \(26\) | \(27\) | \(28\) | \(29\) | \(30\) |
| \(0\) | \(1\) | \(x\) | \(-1\) | \(x^2\) | \(x + 1\) | \(x^3\) | \(2\) | \(-x\) | \(x^2 + 1\) | \(x^4\) | \(x - 1\) | \(x^5\) | \(x^3 + 1\) | \(x^2 + x\) | \(-2\) | \(x^6\) | \(-x + 1\) | \(x^7\) | \(x^2 - 1\) | \(x^3 + x\) | \(x^4 + 1\) | \(x^8\) | \(x + 2\) | \(-x^2\) | \(x^5 + 1\) | \(2x\) | \(x^3 - 1\) | \(x^9\) | \(x^2 + x + 1\) |
Partant de \( 0 \), générons tous les polynômes de \( \mathbb{N}[x] \) en itérant la méthode suivante :
On consigne dans une chaîne de caractères les opérations ainsi effectuées, dans l'ordre, en binaire :
Cependant, multiplier \( 0 \) par \( x \) donne \( 0 \)... c'est comme si on n'avait rien fait (= il n'y a pas vraiment de sous-arbre gauche pour \( 0 \) dans l'arbre ci-dessus). Donc les \( 0 \) à gauche de la chaîne de caractères sont omissibles.
On retrouve là une propriété de la numération. Par conséquent la chaîne de caractères représente un nombre \( n \) en base \( 2 \).
Exemple : \( x^2 + 2x \) s'obtient en faisant, depuis \( 0 \), la séquence d'opérations \( +1 \), \( \times x \), \( +1 \), \( +1 \), \( \times x \), ce qui donne \( 10110 \) en binaire, c'est-à-dire \( 22 \). Avec cette bijection, \( x^2+2x \) est le polynôme numéro \( 22 \).
Sens nombre \( \longrightarrow \) polynôme | Sens polynôme \( \longrightarrow \) nombre |
|---|---|
| P(n)=if(n==0,0,my(b=n%2,PP=P(n>>1));if(b,PP+1,x*PP)) | a(p)=if(p==0,0,if(polcoeff(p,0)!=0,2*a(p-1)+1,2*a(p/x))) |
| \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | \(18\) | \(19\) | \(20\) | \(21\) | \(22\) | \(23\) | \(24\) | \(25\) | \(26\) | \(27\) | \(28\) | \(29\) | \(30\) |
| \(0\) | \(1\) | \(x\) | \(2\) | \(x^2\) | \(x + 1\) | \(2x\) | \(3\) | \(x^3\) | \(x^2 + 1\) | \(x^2 + x\) | \(x + 2\) | \(2x^2\) | \(2x + 1\) | \(3x\) | \(4\) | \(x^4\) | \(x^3 + 1\) | \(x^3 + x\) | \(x^2 + 2\) | \(x^3 + x^2\) | \(x^2 + x + 1\) | \(x^2 + 2x\) | \(x + 3\) | \(2x^3\) | \(2x^2 + 1\) | \(2x^2 + x\) | \(2x + 2\) | \(3x^2\) | \(3x + 1\) | \(4x\) |
LR, 02/06/2022.