Longueur minimale des cycles

Vous êtes ici : Accueil / Cours / Dossiers mathématiques / La conjecture de Syracuse

Longueur minimale des cycles de Syracuse

Le but est de trouver une expression de $M(k)$ tel que si tous les entiers naturels inférieurs à $M(k)$ vérifient la conjecture de Syracuse, alors il n’existe pas de suite périodique non triviale de période $k$ .

Autrement dit, soit $\mathbf{I}$ l’ensemble des entiers naturels impairs

$[\forall u_0 \in \mathbf{I} / u_0 \leq M(k), \exists n \in \mathbf{N} / u_n = 1 ] \Rightarrow [\forall u_0 \in \mathbf{I}, u_k \not = u_0]$

Proposition 1 :

Soit $f$ une fonction de $\mathbf{N}^n$ dans $\mathbf{N}$ telle que

$\forall (a_1,a_2,..,a_n) \in \mathbf{N}^n, \forall (i,j)\ \mbox{tel que}\ 1 \leq i \leq j \leq n$

$\left\{\begin{array}{lr} f(a_1,a_2,..,a_i+1, .., a_n) < f(a_1,a_2,..,a_i, .., a_n) & (1)\\ f(a_1,a_2,..,a_i+1, .., a_j, .., a_n) > f(a_1,a_2,..,a_i, .. ,a_j+1, .., a_n) & (2) \end{array} \right.$

Le maximum de la fonction tel que la contrainte $\sum_{i=1}^{n} a_i \geq k$ soit vérifiée est atteint pour $( a_1,a_2,..,a_n ) = ( k, 0, ..., 0 )$

Démonstration :

L’expression (1) traduit simplement le fait que la fonction atteigne son maximum pour $(a_1,a_2,...,a_n)$ = $(0,0,...,0)$ .

L’expression (2) traduit le fait que l’accroissement de variable $a_1$ fait décroître moins rapidement la fonction que $a_2$ , elle même moins que $a_3$ ... jusqu’à $a_n$ .

Raisonnons par l’absurde.

S’il au moins $i$ différent de 1 tel que $a_i \not = 0$ et le maximum est atteint pour le nuplet $(a_1,a_2,...,a_n)$ .

Alors, prenons $a^{'}_1 = a_1 + a_i$ et $a^{'}_i = 0$ .

D’après (2), $f( a^{'}_1, a_2,.., a^{'}_i,..,a_n ) > f( a_1, a_2,.., a_i,..,a_n )$

et $a^{'}_1 + a_2 + .. + a^{'}_i + .. + a_n = a_1 + a_2 +..+ a_i +..+ a_n \geq k$

Ainsi, le maximum n’était pas atteint pour ce nuplet, donc le nuplet pour lequel le maximum est atteint est $(k,0,...,0)$ .

Nous nommerons « fonction de la forme F1 » toute fonction vérifiant les conditions précédentes.

Proposition 2 :

Si la suite $(u_n)$ et périodique de période $n$ , alors $u_0$ vérifie l’égalité suivante :

$u_0 = \sum_{i=0}^{n-1} \frac{3^{i}}{\left(\prod_{j=0}^{i} 2^{a_{n-j}}\right)\left(1-\frac{3^n}{\prod_{j=1}^{n} 2^{a_j}}\right)}$

Démonstration :

Reprenons l’égalité (3) de l’étude de la suite $(a_n)$ . $u_0$ vérifie l’égalité suivante :

$u_0\left(1-\frac{3^n}{\prod_{i=1}^{n} 2^{a_i}}\right) = \sum_{i=0}^{n-1} \frac{3^{i}}{\prod_{j=0}^{i} 2^{a_{n-j}}}$

En isolant $u_0$ , l’équation devient

$u_0 = \sum_{i=0}^{n-1} \frac{3^{i}}{\left(\prod_{j=0}^{i} 2^{a_{n-j}}\right)\left(1-\frac{3^n}{\prod_{j=1}^{n} 2^{a_j}}\right)}$

Proposition 3 : Les variables $a_i$ sont des entiers naturels strictements positifs tels que

$a_0 + a_1 + ... + a_n > \frac{n\ln 3}{\ln 2}$

Démonstration :

Sachant que tous les termes de la suite $(u_n)$ sont impairs, $3u_n+1$ est pair, donc les $a_i$ sont strictement positifs, donc minorés par 1.

$u_0$ étant positif, $\left(1-\frac{3^n}{\prod_{i=0}^{n} 2^{a_i}}\right)$ doit l’être également.

Ainsi, $\left(\prod_{i=1}^{n} 2^{a_i} > 3^n\right)$

Ou autrement dit $(a_1 + a_2 + ... + a_n)\ln 2 > n\ln 3$

D’où le résultat de la proposition

Proposition 4 : Le terme $u_0$ atteint son maximum pour $( a_1, a_2,..., a_n) = \left([\frac{n\ln 3}{\ln 2}]-n+2, 1, ...., 1 \right)$

Démonstration :

Etant donné que le nombre $n$ est fixé, si un des $a_i$ croît, $\left(1-\frac{3^n}{\prod_{j=1}^{n} 2^{a_j}}\right)$ croît également ainsi que $\left(\prod_{j=0}^{i} 2^{a_{n-j}}\right)$ .

D’autre part, si $j$ est supérieur à $i$ , $a_j$ fait décroître $u_n$ plus rapidement que $a_i$ .

En effet, d’après l’égalité (3) de l’étude de la suite $(a_n)$ , la partie $\left(\prod_{j=0}^{i} 2^{a_{n-j}}\right)$ montre clairement que $a_n$ sera présent dans tous les termes de la somme, $a_{n-1}$ dans $n-1$ termes, ...

Le maximum de la fonction est atteint pour les $a_i$ minimums tels que l’inégalité du lemme des contraintes soit vérifié, et les $a_i$ soient non nuls.

Nous nous trouvons avec une fonction de la forme F1, donc la proposition \reftheoreme-du-maximum peut s’appliquer. La contrainte est $k=\frac{n\ln 3}{\ln 2}$ .

Ainsi, le maximum est atteint pour

$(a_1,a_2,a_3....a_n) = (a_1,1,1...1)\ \mbox{tel que}\ a_0 + a_1 + ... + a_n > \frac{n\ln 3}{\ln 2}$

Donc $(n-1 + a_1)\ln 2 > n\ln 3$

Ainsi la valeur minimum de $a_1$ est $[\frac{n\ln 3}{\ln 2}]-n+2$

La valeur maximum que prends la fonction est donc atteinte en

$(a_1,a_2,a_3....a_n) = ([\frac{n\ln 3}{\ln 2}]-n+2,1,1...1)$

Théoreme 5 :

Soit M(n) tel que

$M(n) = \frac{\left(2^{[\frac{n\ln 3}{\ln 2}]+1}\right)\left(\left(\frac{3}{2}\right)^{n-1}-1\right) + 3^{n-1}}{\left(2^{[\frac{n\ln 3}{\ln 2}]+1} -3^n\right)}$

Alors

$[\forall u_0 \in \mathbf{I} / u_0 \leq M(k), \exists n \in \mathbf{N} / u_n = 1 ] \Rightarrow [\forall u_0 \in \mathbf{I}, u_k \not = u_0]$

Démonstration :

Revenons à l’égalité de la proposition \reflemme-de-la-fonction :

$u_0 = \sum_{i=0}^{n-1} \frac{3^{i}}{\left(\prod_{j=0}^{i} 2^{a_{n-j}}\right)\left(1-\frac{3^n}{\prod_{j=1}^{n} 2^{a_j}}\right)}$

Elle peut également s’écrire comme suit :

$u_0 = \sum_{i=0}^{n-2} \frac{3^{i}}{\left(\prod_{j=0}^{i} 2^{a_{n-j}}\right)\left(1-\frac{3^n}{\prod_{j=1}^{n} 2^{a_j}}\right)} + \frac{3^{n-1}}{\left(2^{a_1}\prod_{j=0}^{n-2} 2^{a_{n-j}}\right)\left(1-\frac{3^n}{\prod_{j=1}^{n} 2^{a_j}}\right)}$

En remplaçant les $a_i$ par leurs valeurs pour obtenir le maximum de la fonction, nous obtenons

$u_0 \leq \sum_{i=0}^{n-2} \frac{3^{i}}{\left(2^{i+1}\right)\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)} + \frac{3^{n-1}}{\left(2^{[\frac{n\ln 3}{\ln 2}]-n+2}2^{n-1}\right)\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)}$

Nous pouvons simplifier le second terme. L’inégalité devient alors

$u_0 \leq \sum_{i=0}^{n-2} \frac{3^{i}}{\left(2^{i+1}\right)\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)} + \frac{3^{n-1}}{\left(2^{[\frac{n\ln 3}{\ln 2}]+1}\right)\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)}$

Le membre gauche est égal à la somme des $n-1$ premiers termes d’une suite géométrique de premier terme $\frac{1}{2*\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)}$ et de raison $\frac{3}{2}$

L’inégalité peut donc s’exprimer ainsi :

$u_0 \leq \frac{1}{2*\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)}\frac{1-\left(\frac{3}{2}\right)^{n-1}}{1-\frac{3}{2}} + \frac{3^{n-1}}{\left(2^{[\frac{n\ln 3}{\ln 2}]+1}\right)\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)}$

Et en la simplifiant, la formule devient

$u_0 \leq \frac{\left(\frac{3}{2}\right)^{n-1}-1}{\left(1-\frac{3^n}{2^{[\frac{n\ln 3}{\ln 2}]+1}}\right)} + \frac{3^{n-1}}{\left(2^{[\frac{n\ln 3}{\ln 2}]+1} -3^n\right)}$

En mettant le tout en facteur commun

$u_0 \leq \frac{\left(2^{[\frac{n\ln 3}{\ln 2}]+1}\right)\left(\left(\frac{3}{2}\right)^{n-1}-1\right) + 3^{n-1}}{\left(2^{[\frac{n\ln 3}{\ln 2}]+1} -3^n\right)}$

Donc en définissant

$M(n) = \frac{\left(2^{[\frac{n\ln 3}{\ln 2}]+1}\right)\left(\left(\frac{3}{2}\right)^{n-1}-1\right) + 3^{n-1}}{\left(2^{[\frac{n\ln 3}{\ln 2}]+1} -3^n\right)}$

$[\forall u_0 \in \mathbf{I} / u_0 \leq M(k), \exists n \in \mathbf{N} / u_n = 1] \Rightarrow [\forall u_0 \in \mathbf{I}, u_k \not = u_0]$

Remarque : Ce résultat peut être amélioré en prenant en compte le fait que le plus petit entier naturel appartenant à un cycle trivial a une durée de vol en altitude infinie.

Antécédents de 1 par F

Etude des antécédents de 1 par la fonction de Syracuse

Dossiers mathématiques

La conjecture de Syracuse

Annonces

Derniers articles

Articles populaires

Liens

Accueil

Envoyer à un ami

Télécharger

Plan du site

Rechercher

Le site

Divers