On définit la fonction Collatz $$C(x) = C_{[x]}(x)$$ où $$ \begin{align*} C_{[0]}(x) & = \frac x 2 \\ C_{[1]}(x) & = \frac 3 2 x + \frac 1 2. \end{align*} $$
Soit \(\newcommand{nat}{\mathbb N} x \in \nat\), alors on s'intéresse à 2 séquences $$x_i = C^i(x), i \text{ allant de } 0 \text{ à } n - 1$$ et $$C_i = C_{[x_i]}, i \text{ allant de } 0 \text{ à } n - 2.$$
L'ordre de \(x_i\) est \(n\), la longeur de la séquence et le \(m\)-ordre de \(x_i\) est l'ordre des termes de \(x_i\) congruents à \(m \mod 2\).
Une formule générale pour \(C^n(x)\), $$ \begin{equation} C^n(x) = \frac {3^\omega} {2^{\omega+\alpha_\omega}} x + \frac 1 2 \sum_{i=0}^{\omega-1} \frac {3^i} {2^{i+\alpha_i}}, \label{collatz} \end{equation} $$ où \(\omega\) est le nombre de \(C_j = C_{[1]}\) et \(\alpha_i\) est le nombre de \(C_j = C_{[0]}\) suivant le (\(\omega - i\))-ième \(C_{[1]}\), pour \(j\) allant de 0 à \(n - 1\) et \(i\) allant de 0 à \(\omega\). Pour le terme \(\alpha_\omega\), on le définit comme le nombre total de \(C_j = C_{[0]}\), pour \(j \lt n\).
Preuve: on peut facilement vérifier que l'équation est vrai pour $$ \begin{align*} C_{[0]}(x) &= \frac {3^0} {2^1} x + \frac 1 2 \sum_{i=0}^{-1} \frac {3^i} {2^{i+\alpha_i}} \\ C_{[0]}(x) &= \frac x 2 \end{align*} $$ et $$ \begin{align*} C_{[1]}(x) &= \frac {3^1} {2^{1+\alpha_1}} x + \frac 1 2 \sum_{i=0}^0 \frac {3^i} {2^{i+\alpha_i}} \\ C_{[1]}(x) &= \frac 3 2 x + \frac 1 2. \end{align*} $$
Supposons que la formule soit vrai pour une composition \(C^n\) de \(C_{[0]}\) et \(C_{[1]}\). Alors \(C_{[0]}(C^n(x))\) divise tous les termes de \(C^n(x)\) par 2 et incrémente tous les termes de \(\alpha_i\) par 1. Pour \(C_{[1]}\) on a: $$ \begin{align*} C_{[1]}(C^n(x)) &= \frac 3 2 (\frac {3^\omega} {2^{\omega+\alpha_\omega}} x + \frac 1 2 \sum_{i=0}^{\omega-1} \frac {3^i} {2^{i+\alpha_i}}) + \frac 1 2 \\ C_{[1]}(C^n(x)) &= \frac {3^{\omega + 1}} {2^{\omega + 1 + \alpha_\omega}} x + (\frac 3 {2^2} \sum_{i=0}^{\omega-1} \frac {3^i} {2^{i+\alpha_i}}) + \frac 1 2 \\ C_{[1]}(C^n(x)) &= \frac {3^{\omega + 1}} {2^{\omega + 1 + \alpha_\omega}} x + (\frac 1 2 \sum_{i=0}^{\omega-1} \frac {3^{i + 1}} {2^{i + 1 + \alpha_i}}) + \frac 1 2 \\ C_{[1]}(C^n(x)) &= \frac {3^{\omega + 1}} {2^{\omega + 1 + \alpha_\omega}} x + \frac 1 2 \sum_{i=0}^{\omega} \frac {3^{i}} {2^{i + \alpha_i}} \\ C_{[1]}(C^n(x)) &= \frac {3^{\omega'}} {2^{\omega' + \alpha_{\omega'}}} x + \frac 1 2 \sum_{i=0}^{\omega'-1} \frac {3^{i}} {2^{i + \alpha_i}}\\ \end{align*} $$ À noter que \(\alpha_{\omega'} = \alpha_\omega\) car aucun nouveau terme \(C_{[0]}\) n'a été introduit, et laisse ainsi les anciens termes de la suite \(\alpha_i\) inchangés.
Exemple, on prend \(x_0 = 6\) et \(n = 6\). Alors la séquence des \(x_i\) est ( 6, 3, 5, 8, 4, 2, 1) et la séquence des \(C_i\) est (\(C_{[0]}\), \(C_{[1]}\), \(C_{[1]}\), \(C_{[0]}\), \(C_{[0]}\), \(C_{[0]}\), \(C_{[1]}\)). On a \(\omega = 2\) et la séquence \(\alpha_i\) est (3, 3, 4). On obtient $$ \begin{align*} C^6(6) & = \frac {3^2} {2^{2+4}} 6 + \frac 1 2 \left( \frac {3^0} {2^{0+3}} + \frac {3^1} {2^{1+3}} \right) \\ & = 1. \end{align*} $$
Une forme alternative à l'équation \(\eqref{collatz}\) est: $$ \begin{equation} C^n(x) = \frac {3^\omega} {2^n} x + \frac {1} {2^n} \sum_{i=0}^{\omega-1} {2^{\beta_i} \cdot 3^i} \end{equation} $$ où \(\beta_i\) est le nombre de termes qui précèdent le (\(\omega - i\))-ième \(C_{[1]}\), ou ce qui est équivalent, l'index de ce terme dans \(C_j\).
Preuve: $$ \begin{align*} C^n(x) &= \frac {3^\omega} {2^{\omega+\alpha_\omega}} x + \frac {2^{\omega + \alpha_\omega - 1}} {2^{\omega + \alpha_\omega}} \sum_{i=0}^{\omega-1} \frac {3^i} {2^{i+\alpha_i}} \\ C^n(x) &= \frac {3^\omega} {2^{\omega+\alpha_\omega}} x + \frac {1} {2^{\omega + \alpha_\omega}} \sum_{i=0}^{\omega-1} \frac {2^{\omega + \alpha_\omega - 1} \cdot 3^i} {2^{i+\alpha_i}} \\ C^n(x) &= \frac {3^\omega} {2^{\omega+\alpha_\omega}} x + \frac {1} {2^{\omega + \alpha_\omega}} \sum_{i=0}^{\omega-1} {2^{\omega + \alpha_\omega - \alpha_i - i - 1} \cdot 3^i} \\ C^n(x) &= \frac {3^\omega} {2^{\omega+\alpha_\omega}} x + \frac {1} {2^{\omega + \alpha_\omega}} \sum_{i=0}^{\omega-1} {2^{\beta_i} \cdot 3^i} \\ C^n(x) &= \frac {3^\omega} {2^n} x + \frac {1} {2^n} \sum_{i=0}^{\omega-1} {2^{\beta_i} \cdot 3^i} \\ \end{align*} $$
Équation inverse: $$ \begin{equation} C^{-n}(x) = \frac {2^n} {3^\omega} x - \frac {1} {3^\omega} \sum_{i=0}^{\omega-1} {2^{\beta_i} \cdot 3^i} \end{equation} $$
On peut vouloir s'affranchir des termes \(x_i\) et simplement s'intéresser à l'ensemble des fonctions générées par \(g = C_{[0]}\) et \(h = C_{[1]}\) par composition, élargies au domaine \(\newcommand{ratio}{\mathbb Q}\ratio\). Nous dénoterons l'ensemble de ces fonctions par \(\newcommand{semigroupe}{\left< g, h \right>}\semigroupe\).
Relation de congruence, pour \(f \in \semigroupe\) et \(f^{-1}\), sa fonction inverse. Soit \(f_n \circ \cdots \circ f_2 \circ f_1 = f\), la factorisation de \(f\) en termes \(g\) et \(h\). On définit \(\omega\) étant l'ordre des \(f_i = h\). On pose \(S_f = \sum_{i=0}^{\omega - 1} {2^{\beta_i}3^i}\): $$ \begin{align} x &\equiv -3^{-\omega}S_f \pmod{2^{n}} \label{congruenceavant} \\ x &\equiv 2^{-n}S_f \pmod{3^{\omega}} \label{congruencearriere} \\ x &\equiv \left( 2^{n} \left[2^{-2n} \right]_{3^{\omega}} - 3^\omega \left[ 3^{-2\omega} \right]_{2^{n}} \right) S_f \pmod{2^{n}3^{\omega}} \label{congruence} \\ \end{align} $$
Si \(x \in \nat\) et \(x\) respecte la relation de congruence en \(\eqref{congruenceavant}\), alors \(f(x)\) est bien défini dans \(\nat\). Est-ce le cas pour tous les \(f_i(x)\)? Si \(x\) respecte la relation de congruence en \(\eqref{congruencearriere}\), alors \(f^{-1}(x)\) est bien défini dans \(\nat\) et si \(x\) respecte la relation de congruence en \(\eqref{congruence}\), alors autant \(f(x)\) que \(f^{-1}(x)\) sont bien définis dans \(\nat\).
Si \(\left[ -3^{-\omega} \right]_{2^n} = \left[ 2^{-n} \right]_{3^{\omega}}\), alors on a un cycle.
L'inégalité suivante fournit des bornes suppérieure et inférieure à une fonction \(C^n\). Pour \(x \geq 0\), $$ \begin{equation} (g^{\alpha_\omega} \circ h^\omega)(x) \leq C^n(x) \leq (h^\omega \circ g^{\alpha_\omega})(x) \label{suppremums} \end{equation} $$ où $$ \begin{align} (g^{\alpha_\omega} \circ h^\omega)(x) & = \frac {3^\omega} {2^{\omega + \alpha_\omega}} x + \frac {3^\omega - 2^\omega} {2^{\omega + \alpha_\omega}}, \\ (h^\omega \circ g^{\alpha_\omega})(x) & = \frac {3^\omega} {2^{\omega+\alpha_\omega}} x + \frac {3^\omega - 2^\omega} {2^{\omega}}, \end{align} $$
Pour une fonction \(f \in \semigroupe\), $$ \begin{equation} (g \circ f)(x) \leq (f \circ g)(x) \label{ordre} \end{equation} $$
Preuve: soit \(f(x) = ax + b\), alors: $$ \begin{align*} (g \circ f)(x) & = \frac a 2 x + \frac b 2 \\ (f \circ g)(x) & = \frac a 2 x + b \\ (g \circ f)(x) & \leq (f \circ g)(x) \end{align*} $$
La principale question qui nous intéresse au sujet de la fonction Collatz est de savoir s'il existe d'autres cycles que (1, 2) dans les entiers positifs. Autrement dit, existe-t-il une fonction \(f \in \semigroupe\) dont le point fixe est un entier positif différent de 1 et 2. S'il n'y en a pas, alors il ne peut y avoir d'autre cycle d'entiers positifs que (1, 2).
Voici la formule pour le calcul du point fixe d'une fonction \(f \in \semigroupe\): $$ \DeclareMathOperator{\Fix}{Fix} \begin{equation} \Fix_f = \frac {1} {2^{n} - 3^\omega} \sum_{i=0}^{\omega-1} {2^{\beta_i} \cdot 3^i} \label{pointfixe} \end{equation} $$
Calculons les points fixes de quelques fonctions de cet ensemble:
| Fonction | Point fixe |
|---|---|
| \(g\) | 0 |
| \(h\) | -1 |
| \(g \circ h\) | 2 |
| \(h \circ g\) | 1 |
| \(g \circ g\) | 0 |
| \(g \circ g \circ h\) | \(\frac 1 5\) |
| \(g \circ h \circ g\) | \(\frac 2 5\) |
| \(g \circ h \circ h\) | -5 |
| \(h \circ g \circ g\) | \(\frac 4 5\) |
| \(h \circ g \circ h\) | -7 |
| \(h \circ h \circ g\) | -10 |
| \(h \circ h \circ g \circ g\) | \(\frac 5 4\) |
Il est intéressant d'observer qu'il existe d'autres points fixes dans les entiers négatifs qui correspondent aux cycles (-1), (-5, -7, -10). Ces deux cycles sont en fait associés à une fonction soeur similaire à la fonction Collatz, mais où \(C_{[1]}(x) = \frac 3 2 x - \frac 1 2\). Nous y reviendrons plus tard.
Puisque nous sommes seulement intéressés par les cycles d'entiers positifs, nous devons trouver une condition pour que le point fixe soit plus grand que zéro. À partir de la formule \(\eqref{pointfixe}\), on voit qu'il est nécessaire et suffisant que \(2^{\omega + \alpha_\omega} \gt 3^\omega\).
Si \(\Fix_f = x\), alors \(\Fix_{f^n} = x\), pour tout \(x \gt 0\).
Si \((x_0, x_1, \ldots, x_{n-1})\) est un \(n\)-cycle et \((C_0, C_1, \ldots, C_{n-1})\) est sa séquence de fonctions associée, alors $$ \begin{gather*} \Fix_{C_{n-1} \circ \cdots \circ C_1 \circ C_0} = x_0 \\ \Fix_{C_0 \circ C_{n-1} \circ \cdots \circ C_1} = x_1 \\ \cdots \\ \Fix_{C_1 \circ C_0 \circ \cdots \circ C_{n-1}} = x_{n-1}. \end{gather*} $$
Un corrolaire est le suivant. Soit \(f \in \semigroupe\), \(f_i \in \{g, h\}\) et \(f = f_{n-1} \circ \cdots \circ f_1 \circ f_0\). Si \(\Fix_f \notin \nat\), alors \(f\), ni aucune rotation de \(f\) ne peuvent engendrer un cycle.
Il y a toute une classe de fonctions dans \(\semigroupe\) qui ne peuvent engendrer un cycle à cause du corrolaire précédent, ce qui réduit la recherce de manière significative. Soit \(S\), l'ensemble des fonctions dans \(\semigroupe\) telles que l'ordre des \(g\) qui composent \(f \in S\) est plus grand que \(\lceil \omega (\log_2 3 - 1) \rceil\), où \(\omega\) est l'ordre des \(h\). Alors aucune de ces fonctions ne peut engendrer un cycle.
Preuve: le point fixe a la forme \(\frac {2^\lambda \cdots K} {2^{\omega + \alpha_\omega} - 3^\omega}\) où \(\omega + \alpha_\omega \gt \lceil \omega \log_2 3 \rceil \). Le terme \(K\) est plus petit où égal à \(3^\omega - 2^\omega\), donc \(2^{\omega + \alpha_\omega} - 3^\omega \gt K\). Puisque \(2^{\omega + \alpha_\omega} - 3^\omega\) est impair, alors il ne divise pas \(2^\lambda\) ce qui implique que le point fixe est un rationel.
$$ 2^{\omega \log_2 3} - 3^\omega \gt 0 $$
$$ \begin{align*} \sum_{i=0}^{\omega - 1} {\left( \frac 3 2 \right)^i} & = \frac {1 - \left( \frac 3 2 \right)^{\omega}} {1 - \frac 3 2} \\ & = \frac {3^{\omega} - 2^{\omega}} {2^{\omega - 1}} \end{align*} $$