Nombres p-adiques

Sujet proposé par Dominique Perrin

perrinuniv-mlv.fr

Préambule

Les nombres p-adiques sont une extension des nombres rationnels qui est utilisée en théorie des nombres pour calculer modulo une puissance d'un nombre premier. Ces calculs permettent aussi d'obtenir des résultats pratiques sur des problèmes comme la factorisation des polynomes. On propose ici d'implémenter les opérations de base sur ces nombres.

Détail du sujet

Les nombres p-adiques sont des objets curieux, inventés par K. Hensel vers 1900 et qui font partie des constructions classiques en mathématiques. On se propose ici d'implémenter les opérations de base de cette arithmétique, qui est succintement décrite ci-dessous. Je renvoie à l'un des manuels comme [1] ou [3] pour une introduction plus complète à ce domaine.

L'idée de départ est la suivante. Étant donné un nombre premier p fixé, on considère que deux entiers x,y sont proches si leur différence est divisible par une puissance élevée de p. On pourra ainsi, pour p=2, approximer -1 par 2ⁿ-1 pour tout $n\geq 1$, et même représenter -1 par le développement binaire infini $\ldots 111$.

Ceci est une généralisation de la règle utilisée dans l'arithmétique interne des ordinateurs pour p=2 et appelée notation en complément à 2 (voir [2] p. 179).

De façon plus formelle, on considère les développements infinis de la forme

avec $k\geq 0$ et $0\leq x_i\le p$ pour $-k\leq i$. On peut aussi écrire à l'envers

$$x=\ldots x_1 x_0 . x_{-1}\cdots x_{-k}$$

de sorte qu'on retrouve la notation en base p. On montre que, muni des opérations arithmétiques usuelles sur les séries (avec une retenue), on obtient ainsi un corps, noté ${{\bf Q}}_p$ et appelé corps des nombres p-adiques.

On dit que x est un entier p-adique si k=0. On note ${{\bf Z}}_p$ l'ensemble des entiers p-adiques.

De façon encore plus formelle, pour tout entier $x\in {\bf Z}$, on note $\mbox{ord}_p(x)$ la plus grande puissance de p qui divise x. Pour un nombre rationnel x=a/b, on note $\mbox{ord}_p(x)=\mbox{ord}_p(a)-\mbox{ord}_p(b)$. On pose ensuite $\vert x\vert _p=p^{-\mbox{ord}_p(x)}$. On démontre que $\vert\ \vert _p$ est une norme sur ${\bf Q}$. On note ${{\bf Q}}_p$ le complété de l'ensemble ${\bf Q}$ des nombres rationnels pour la topologie associée à cette norme. On démontre que chaque élément de ${{\bf Q}}_p$, appelé nombre p-adique a un développement unique de la forme (1).

Quelques petits exercices. On a déja vu que, pour p=2

$$-1=\ldots 111$$

De plus

$$\frac{1}{3}=\ldots 011011$$

Comme on peut le vérifier (les nombres ayant un développement périodique sont encore les nombres rationnels). Un peu plus de travail montre que, pour p=7, on peut noter

$$\sqrt{2}=\ldots 213$$

En effet, on a

Il y a bien entendu une autre racine qui est $-\sqrt{2}=\ldots 454$.

En fait, on peut vérifier que si f(x) est un polynome à coefficients dans ${{\bf Z}}_p$, l'équation f(x)=0 a une solution dans ${{\bf Z}}_p$ dès qu'elle a une solution simple dans ${\bf Z}/p$ (Lemme de Hensel). Plus précisément, si a₀ est un entier tel que $f(a_0)\equiv 0 \bmod p$ et $f'(a_0)\not\equiv 0\bmod p$,il existe un unique entier p-adique a tel que

$$f(a)=0\mbox{ et } a\equiv a_0 \bmod p$$

La solution $a=a_0+a_1p+\cdots$ est donnée par l'algorithme suivant, analogue à la méthode de Newton. Soit $b_n=a_0+\cdots+a_np^n$. On a alors pour $n\geq 1$

Pour le calcul de $\sqrt{2}$, on a les formules

$$a_np^n\equiv \frac{1}{2}(\frac{1}{b_{n-1}}-b_{n-1})\bmod p^{n+1}$$

Les fonctions usuelles de l'analyse ont une version p-adique obtenue en utilisant le développement en série usuel quand il converge dans ${{\bf Q}}_p$. Ainsi, le logarithme p-adique défini par la formule usuelle

$$\log_p (1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}+\ldots$$

La série converge pour |x|_p<1 et diverge ailleurs. Par exemple

$$\log_7 (8)=\ldots5360$$

Dans le domaine de définition, on a encore $\log_p(ab)=\log_p(a)+\log_p(b)$. De ce fait, $\log_2(-1)=0$ puisque $2\log_2(-1)=\log_2(1)=0$.

On définit par la même méthode les fonctions $\exp_p$, $\sin_p$,$\cos_p$, $\ldots$

Travail demandé

On demande d'écrire un système permettant de calculer des nombres p-adiques avec un ensemble de fonctions. Les expressions seront représentées par des arbres syntaxiques comme l'arbre ci-dessous pour l'expression $(1+\sqrt{5})/2$.

 

Figure 1: L'arbre syntaxique de $(1+\sqrt{5})/2$

Les développements seront représentés sous la forme d'une paire (k,d) formée d'un entier et d'une liste chaînée avec

$$d=(x_{-k},x_{-k+1},\cdots)$$

pour x représenté sous la forme (1).

Le système doit comprendre au minimum

1.

Un module de saisie permettant de transformer une expression formée à partir de nombres entiers et d'opérateurs +,-,*,/ plus quelques fonctions comme la racine carrée et le logarithme en arbre syntaxique.

2.

Un module de fonctions opérant sur des listes chaînées représentant des développements p-adiques. et comprenant

• L'implémentation des opérations arithmétiques de base plus(x,y), moins(x,y), mult(x,y), div(x,y).
• L'implémentation des fonctions racine(x) et log(x) quand elles sont définies.

3.

Une fonction developpement(x,n) produisant les n premiers termes du développement du nombre p-adique x (représenté par un arbre syntaxique). Le développement sera représenté sous forme d'une liste chaînée.

La fonction developpement rend Echec si le développement ne converge pas.

On pourra, de façon optionnelle :

1.

Implémenter l'algoritme de résolution d'équations polynomiales par la méthode de Hensel (voir l'équation 2 ci-dessus).

2.

Implémenter les fonctions exp_p, sin_p, cos_p, ...

References

1

Fernando Q. Gouvêa, p-adic Numbers, Springer, 1991.

2

Donald Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, Addison Wesley 1969.

3

Neal Koblitz, p-adic Numbers, p-adic Analysis, and Zeta-functions, Springer, 1977.