Probleme – La récurrence forte est une induction bien fondée

1. Les deux principes n'en font qu'un.

La récurrence forte dit : si pour tout $n$, « $P$ vraie sur tous les $m<n$ » entraîne « $P$ vraie en $n$ », alors $P$ est vraie sur $\mathbb{N}$.

L'induction bien fondée dit : si $⪯$ est bien fondé sur $E$ et si pour tout $x$, « $P$ vraie sur tous les $y\prec x$ » entraîne « $P$ vraie en $x$ », alors $P$ est vraie sur $E$.

Prenons $E=\mathbb{N}$ et $⪯$ l'ordre usuel : les deux énoncés sont le même texte. Et la démonstration du cours s'applique mot pour mot : si $P$ était fausse quelque part, l'ensemble des contre-exemples serait une partie non vide de $\mathbb{N}$, donc admettrait un plus petit élément $n_0$ ; tous les $m<n_0$ vérifieraient $P$, donc $n_0$ aussi, contradiction.

Remarque qui lève une confusion fréquente. La récurrence forte n'a pas de « cas de base » séparé. Il est contenu dans l'hypothèse : pour $n=0$, « $P$ vraie sur tous les $m<0$ » est vraie par vacuité, et l'hypothèse exige donc de prouver $P(0)$ sans rien supposer. Le cas de base n'a pas disparu, il a été absorbé — exactement comme, dans l'induction structurelle, les assertions sont les éléments minimaux.

2. L'existence de la décomposition. Soit $P(n)$ : « $n\ge 1$ est un produit fini de nombres premiers ». Par récurrence forte.

Soit $n\ge 1$ et supposons $P$ vraie sur $1,\dots ,n-1$. Si $n=1$, c'est le produit vide — convention qui évite un cas particulier et qui n'est pas un artifice : le produit vide vaut $1$. Si $n$ est premier, c'est un produit à un facteur. Sinon $n=ab$ avec $1<a,b<n$ ; par hypothèse de récurrence, $a$ et $b$ sont des produits de premiers, et leur concaténation en donne un pour $n$. C'est ici que la récurrence forte est indispensable : $a$ et $b$ ne sont pas $n-1$, ils sont n'importe où en dessous de $n$.

(* Renvoie la liste croissante des facteurs premiers de n, avec repetition.
   Precondition : n >= 1. Postcondition : le produit de la liste vaut n
   et tous ses elements sont premiers ; n = 1 donne la liste vide. *)
let rec facteurs n =
  if n = 1 then []
  else
    let rec plus_petit_diviseur d =
      if d * d > n then n                    (* aucun diviseur <= racine : n premier *)
      else if n mod d = 0 then d
      else plus_petit_diviseur (d + 1)
    in
    let p = plus_petit_diviseur 2 in
    p :: facteurs (n / p)

3. Preuves et coût.

Terminaison de plus_petit_diviseur : variant $n-d^2$, ou plus simplement le nombre d'entiers restant à essayer jusqu'à $\lfloor \sqrt{n}\rfloor$, qui décroît de $1$ à chaque appel.

Terminaison de facteurs : variant $n$ lui-même. Le facteur $p$ trouvé vaut au moins $2$, donc $n/p\le n/2<n$, et $n/p\ge 1$. C'est bien la récurrence forte qui prouve la terminaison, pas une récurrence simple : l'appel ne porte pas sur $n-1$.

Correction de plus_petit_diviseur : invariant « aucun entier de $2$ à $d-1$ ne divise $n$ ». S'il sort par $d^2>n$, alors $n$ n'a aucun diviseur $\le \sqrt{n}$ autre que $1$ ; il n'en a donc aucun du tout, car un diviseur $a>\sqrt{n}$ apporterait le codiviseur $n/a<\sqrt{n}$. Donc $n$ est premier, et le rendre est correct. S'il sort par $n\mathrm{mod}d=0$, $d$ est le plus petit diviseur $>1$, donc premier — car un diviseur de $d$ serait un diviseur plus petit de $n$.

Correction de facteurs : par récurrence forte. Le produit de la liste rendue vaut $p\times (n/p)=n$, et tous ses éléments sont premiers puisque $p$ l'est et que ceux de l'appel récursif le sont par hypothèse.

Complexité. Chaque appel à plus_petit_diviseur coûte $O(\sqrt{n})$ ; il y a au plus ${\log }_{2}n$ appels récursifs, l'argument étant au moins divisé par $2$. Total : $O(\sqrt{n}\log n)$ dans le pire cas, atteint pour $n$ premier — où l'unique parcours va jusqu'à $\sqrt{n}$.

Vérification, mesurée. Pour tout $n$ de $1$ à $20000$ : le produit des facteurs rendus vaut $n$, et tous sont premiers. Quelques valeurs : $60=2\times 2\times 3\times 5$, $1024=2^{10}$, $123456=2^6\times 3\times 643$, et $999983$ est premier.

Ce que le problème a montré au-delà de l'arithmétique. La récurrence forte n'est pas une variante commode de la récurrence : c'est l'induction sur $(\mathbb{N},\le )$, au même titre que l'induction structurelle est l'induction sur l'ordre induit. Un seul théorème, et l'on change seulement l'ordre bien fondé. C'est ce que le cours annonçait, et c'est ce qui rend le chapitre transverse.

Un mot sur ce que ce problème n'a pas prouvé : l'unicité de la décomposition. Elle est vraie, mais elle ne se déduit pas de cette récurrence — il y faut le lemme d'Euclide. Confondre les deux est l'erreur classique du théorème fondamental de l'arithmétique.