Retour sur le critère de Cohn

Dans l’article précédent on a considéré l’application
\[f:Z\rightarrow Z[X]\]
qui à tout entier $u\in Z$ dont l’écriture en base $b = 2$ (on peut prendre une autre base si l’on veut) est :
\[u= \pm (u_0+u_12+u_22^2+\dots + u_r2^r),\]
associe le polynôme de $Z[X]$ :
\[f_u(X)= \pm (u_0+u_1X+u_2X^2+\dots + u_rX^r).\]

Cette application $f$, bien que très naturelle, n’a pas beaucoup de propriétés sympathiques à part le remarquable critère de Cohn :

  1. $f$ est injective mais n’est pas surjective
  2. $f$ n’est pas un homomorphisme (ni pour l’addition, ni pour la multiplication)
  3. (Critère de Cohn) Si $u$ est premier, $f_u$ est irréductible.

On peut regarder de plus près ce qui se passe pour les irréductibles.
Certains entiers non premiers impairs ont une image par $f$ qui irréductible.

Par exemple, si $u=25$, $f_{25}(X)= 1+X^3+X^4$ est irréductible dans $Z[X]$.
Démonstration 1: Supposons
\[ 1+X^3+X^4=A(X)B(X) \]
S’il existe un facteur de degré 1 ce ne peut être que $X\pm 1$, donc c’est impossible. S’il a deux facteurs de degrés 2 alors :
\[f_{25}(X)= (X^2+aX +\epsilon)(X^2+bX +\epsilon)\]
avec $\epsilon =\pm 1$. Alors $a+b=0$ et
\[f_{25}(X)= (X^2+aX +\epsilon)(X^2-aX +\epsilon)= (X^2+\epsilon)^2-a^2X^2\]
donc $2\epsilon=\pm 2 = a^2$ ce qui est impossible.

Démonstration 2: $ 1 + 3^3+3^4=109$ qui est un nombre premier. Donc d’après le critère de Cohn le polynôme
$1+X^3+X^4$ est irréductible dans $Z[X]$.

La suite des nombres dont l’écriture binaire est un polynôme irréductible de $Z[X]$ est A206074.
Si l’on enlève les nombres premiers (ils sont tous contenus dans cette suite à cause de Cohn), on trouve A206075 :
1, 25, 55, 69, 77, 81, 87, 91, 115, 117, 121,…

Nombres premiers et polynômes irréductibles de $F_2[X]$

Le problème d’irréductibilité d’un polynôme de $Z[X]$ est difficile. Il plus difficile que le problème de la primalité dans $Z$ puisque ce dernier est un sous-problème du premier! Il existe des algorithmes (Lenstra) de factorisation dans $Z[X]$ basés sur LLL dont on parlera peut être plus tard.

Par contre pour les questions d’irréductibilité et de factorisation dans $F_2[X]$ on dispose de bons algorithmes.

On peut reprendre le problème précédent mais cette fois dans $F_2[X]$. Le critère d’irréductibilité de Cohn n’est plus vrai !
Regardons comment les choses se présentent.

On se donne un nombre premier et son développement binaire
\[p=a_0+a_12+ \dots + a_r2^r.\]
On lui associe canoniquement un polynôme binaire de $F_2[X]$:
\[A_p(X)= a_0+a_1X+\dots +a_rX^r\]
Ce polynôme n’est pas toujours irréductible dans \(F_2[X]\). Voici les premiers exemples :
\[\begin{array}{llll}
p & A_p & Irr & Raison \\
\hline
2 & X &oui\\
3 & 1+X &oui\\
5 & 1+ X^2 &non & =(1+X)^2\\
7 & 1+X+X^2 &oui\\
11 & 1+X+X^3 &oui \\
13 & 1+X^2+X^3 &oui \\
17 & 1+X^{4} &non & =(1+X)^4
\end{array}\]
La suite des nombres premiers correspondant à des polynômes irréductibles de $F_2[X]$ se trouve dans l’encyclopédie OEIS sous l’index : A091206 = 2, 3, 7, 11, 13, 19, 31, 37, 41, 47, 59, 61,…
Dans le même ordre d’idée une autre suite intéressante est celle des nombres associés à tous les polynômes irréductibles de \(F_2[X]\) par la méthode ci-dessus : elle a l’index A014580 = 2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, …
La première liste est simplement l’intersection de A091206 avec la liste des nombres premiers.

On peut étudier quelques cas. Prenons par exemple les nombres premiers de $16\leq p\leq 31$ :

Pour $p=17$ le polynôme de $F_2[X]$ correspondant est $1+X^4=(1+X)^4$ et donc n’est pas irréductible.

Pour 19 le polynôme associé est $1+X+X^4$ qui est irréductible dans $F_2[X]$.

Le polynôme réciproque $1+X^3+X^4$ est donc irréductible, mais qui correspond à 25 qui n’est pas premier!

Pour 23 , le polynôme correspondant est $P(X)=1+X+X^2+X^4$. Ce polynôme comporte 4 termes donc $X=1$ est une racine.
Il n’est pas irréductible.

Son polynôme réciproque $Q(X)= 1+X^2+X^3+X^4$ correspond à 29 et n’est pas irréductible non plus.

Enfin 31 correspond à $1+X+X^2+X^3+X^4$ qui est irréductible car correspondant aux racines 5-ièmes de l’unité qui se trouvent dans $F_{2^4}=F_{16}$.

Réduction mod 2

Soit $Z[X]\rightarrow F_2[X]$ l’homomorphisme naturel d’anneaux, qui à tout $P\in Z[X]$ associe $\overline{P} \in F_2[X]$ par réduction mod 2 des coefficients.

Malheureusement $P\in Z[X]$ est irréductible alors $\overline P$ n’est pas forcément irréductible.

Inversement, tout polynôme de $F_2[X]$ qui est irréductible a son image réciproque « canonique » (à coefficients 0 ou 1) qui est irréductible (en raisonnant par l’absurde).

Si on étudie cette liste les cas de 5 et 17 sont clairs par Frobenius. Mais d’autres cas sont plus complexes.

Ainsi 23 correspond au polynôme \( P= 1+X+X^2+X^4\). D’après le résultat de Cohn \(P\) est irréductible dans $Z[X]$.
Mais $\phi(P)$ n’est pas irréductible dans $F_2[X]$ puisque 1 est une racine :
\[P=(1+X)(1+X^2+X^3).\]

De même 29 correspond au polynôme réciproque de $Q= 1+X^2+X^3+X^4$. Ce polynôme se décompose dans \(F_2[X]\) :
\[Q=(1+X)(1+X+X^3).\]

Le critère d’irréductibilité d’Arthur Cohn

Ce résultat est étonnant mais va bien dans le sens de mon article précédent. Il relie deux mondes : l’arithmétique sur \(N\) et l’algèbre des polynômes \(Z[X]\). Etonnant parce que l’irréductibilité dans \(Z[X]\) est plus difficile que l’irrédictibilité dans \(N\).
Critère de Cohn :
Soit \(n\in N\) un nombre premier et son écriture en base \(b\geq 2\) :
\[n= a_0+a_1b+\cdots +a_kb^k,\]
(donc les \(a_i\) sont tous des entiers tels que \(0\leq a_i \leq b-1\)) alors le polynôme
\[f(X)= a_0+a_1X+\cdots +a_kX^k\]
est irréductible dans \(Z[X].\)

Arthur Cohn, élève d’Issai Schur, aurait démontré le cas « usuel » où \(b=10\). La démonstration fut donnée pour \(b=10\) par Polya et Szego et dans le cas d’une base quelconque \(b=2,3,4,…\) par J. BRILLHART, M. FILASETA et A. ODLYZKO en 1981.

Avant de donner une démonstration, disons un mot de la réciproque. Elle est fausse car un polynôme irréductible
\(f\in Z[X]\) ne correspond pas toujours au développement d’un nombre premier. Par exemple \(f(X)=X+1\) est irréductible mais \(f(3)=4\). De même \(f(X)=X^2+1\) donne \(f(3)=10\). Toutefois la conjecture de Bouniakovski, non prouvée à ce jour, est la suivante :

Conjecture : Si \(f\in Z[X]\) est irréductible, alors \(f(a)\) est premier pour une infinité d’entiers \(a\).

En d’autres termes la réciproque serait souvent vraie.
Lorsque \(f\) est de degré 1, la conjecture est démontrée : c’est le théorème de la progression arithmétique de Dirichlet !
Mais pour les degrés \(\geq 2\) on ne sait pas.

Démonstration en base \(b\geq 3\) du critère de Cohn :

Il est clair que si \(deg(f)= 0\), c’est-à-dire si \(b>n\), le critère est vrai par définition.
De même si \(deg(f)= 1\), on a \(f(X)=a_0+a_1X\) et
\(f(b)=n\). Par conséquent les 2 coefficients \(a_0\) et \(a_1\) sont premiers entre eux. Donc \(f\) est bien irréductible dans \(Z[X]\).
On peut donc supposer \(deg(f)\geq 2\).
L’idée clé du reste de la démonstration est de montrer que les racines de \(f\) se situent assez loin de la base \(b\).
Raisonnons par l’absurde et supposons que \(f(X)= R(X)S(X)\) avec \(R,S\in Z[X]\) de degré au moins 2. On a donc
\[n=R(b)S(b)\]
donc \(R(b)=1\) ou \(S(b)=1\). On peut supposer que \(R(b)=1\).
Supposons que \(b\) soit « assez loin » des racines. Plus précisément supposons que :

Lemme : Si \(\alpha\) une racine de \(f\) dans les complexes alors \[|b-\alpha|> 1.\]

Alors le polynôme \(R(X)\) peut s’écrire comme un produit sur certaines racines \(\alpha_i\):
\[R(X) =r_0+\dots +r_mX^m = r_m\prod_i(X-\alpha_i)\]
où \(r_m\), un entier \(\geq 1\), est le coefficients dominant de \(R\).
On en déduit \(|R(b)|= |r_k|\prod_i |b-\alpha_i|>1\). C’est une contradiction.

Reste donc à démontrer le lemme. On le fait dans le cas \(b \geq 3\) mais le cas \(b=2\) peut aussi se démontrer.

Soit \(z\) un complexe. On va évaluer
\[\left|\frac{f(z)}{z^n}\right|= \left| a_n+\frac{a_{n-1}}{z} +\dots + \frac{a_0}{z^n}\right| \]
On pose
\[U= a_n+\frac{a_{n-1}}{z} \]
\[V=\frac{a_{n-2}}{z^2} +\dots +\frac{a_0}{z^n}.\]
On sait que \(a_n\geq 1\) et \(a_n\geq 0\) donc, si on suppose \(Re(z)\geq 0\) on montre facilement que \(Re(U)\geq 1\).
D’autre part on peut borner \(V\) facilement si \(|z|>1\) par
\[V< \frac{b-1}{|z|^2-|z|}\] Par conséquent sous les deux conditions \(Re(z)\geq 0\) et \(|z|>1\) on a
\[\left|\frac{f(z)}{z^n}\right|=|U+V|> 1- \frac{b-1}{|z|^2-|z|}= \frac{|z|^2-|z|-(b-1)}{|z|^2-|z|}\]
Si en plus \(z\) est une racine de \(f\), le trinôme au numérateur sera négatif et donc
\[|z|<\frac{1 +\sqrt{4b-3}}{2}\] Il est alors facile d'en déduire que si \(b\geq 3\) alors \(|z-b|>1\).
On passe ensuite en revue les cas restant.
Si \(Re(z)\leq 0\) il est évident que \(|z-b|>1\) pour \(b\geq 2\).
Reste donc à étudier le cas où \(Re(z)> 0\) et \(|z|<1\) mais la encore \(|z-b|>1\) pour \(b\geq 3\).
La démonstration du lemme est terminée sous la condition que \(b\geq 3\).

La multiplication est commutative !

La multiplication des entiers est commutative : vous êtes d’accord ?

Pour le démontrer proprement on utilise les axiomes de Peano (dont la récurrence).

Je considère  maintenant  l’algorithme « ordinaire » de multiplication pour des chiffres écrits en base 2.

Question : Pourquoi cet algorithme est-il commutatif?

Voici par exemple la multiplication \(55\times 9=495\) écrite en base 2:
\[ \begin{array}{ccccccccc}
&&&1&1&0&1&1&1\\ &&&&& 1 & 0 & 0&1 \\ \hline &&&1&1&0&1&1&1 \\ 1&1&0&1&1&1&&& \\ \hline  1&1&1&1&0&1&1&1&1 \end{array} \]
Et nous pouvons ausi l’écrire
\[ \begin{array}{ccccccccc}
 &&&&&1&0&0&1 \\ &&&1&1&0&1&1&1 \\ \hline &&&&&1&0&0&1 \\&&&&1&0&0&1& \\&&&1&0&0&1&& \\&1&0&0&1&&&& \\1&0&0&1&&&&& \\ \hline  1&1&1&1&0&1&1&1&1 \end{array} \]
Si on regarde les deux déroulements de l’algorithme il n’est pas du tout évident que les deux résultats soient identiques !

Regardons les sommes (en décimal) de chacune des 9 colonnes sans faire la retenue. On trouve le même résultat dans les deux cas :
\[ \begin{array}{ccccccccc} 1&1&0&2&2&1&1&1&1 \end{array} \]
et c’est cela qui garantit le même résultat dans les deux cas ! Les sommes par colonnes sont identiques dans les deux cas. Et ceci n’est pas dû à la base 2 employée dans mon example. C’est vrai dans n’importe quelle base de numération (vous pouvez vérifier).

Voici une démonstration :
On écrit la multiplication :
\[\sum_{i\geq 0} a_i2^i \times \sum _{j \geq 0} b_j2^j \]
\[=\sum_{k\geq 0} \left(\sum_{i+j= k} a_ib_j\right) 2^k\]
et il est bien clair que le terme entre parenthèses ne dépend pas du tout de l’ordre dans lequel on développe l’algorithme car la multiplication des chiffres est commutative \(a_ib_j=b_ja_i\). C’est pour cela que l’algorithme usuel est bien commutatif !

C’est aussi d’une certaine façon la justifiction de la multiplication « égyptienne ».
Je vais m’intéresser maintenant à l’aspect « binaire » de la multiplication.
On applique la règle \(1+1=0\). L’algorithme devient
\[ \begin{array}{ccccccccc}
&&&1&1&0&1&1&1\\ &&&&& 1 & 0 & 0&1 \\ \hline &&&1&1&0&1&1&1 \\ 1&1&0&1&1&1&&& \\ \hline  1&1&0&0&0&1&1&1&1 \end{array} \]
Et nous pouvons ausi l’écrire
\[ \begin{array}{ccccccccc}
 &&&&&1&0&0&1 \\ &&&1&1&0&1&1&1 \\ \hline &&&&&1&0&0&1 \\&&&&1&0&0&1& \\&&&1&0&0&1&& \\&1&0&0&1&&&& \\1&0&0&1&&&&& \\ \hline  1&1&0&0&0&1&1&1&1 \end{array} \]
Sans surprise cela reste commutatif. En effet l’algorithme traduit maintenant la multiplication suivante dans l’algèbre \(F_2[X]\) :
\[(X^5+X^4+X^2+X+1)(X^3+1)= X^8+X^7+X^3+X^2+X+1.\]
Je vais expliquer mon intérêt pour ces considérations dans mon prochain article.