Shortlist 2020, A6

Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : Slovakia

Concepts : Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 22 (page 24 du PDF)

Énoncé

Determine all functions \(f : \mathbb{Z} \to \mathbb{Z}\) such that

\[f^{a^2 + b^2}(a + b) = a f(a) + b f(b)\]

for every \(a, b \in \mathbb{Z}\).

Here, \(f^n\) denotes the \(n\)-th iteration of \(f\), i.e., \(f^0(x) = x\) and \(f^{n+1}(x) = f(f^n(x))\) for all \(n \geq 0\).

Indices : les idées clés

• Substitutions : \(E(0, b)\), \(E(a, -1)\), \(E(a, -a)\) et \(E(n, 1-n)\) fournissent \(f(-1) = 0\), la relation clé \(f^{a^2+1}(a-1) = f^{a^2}(a)\) et la parité de \(f\).
• Orbites : les orbites de \(a-1\) et de \(a\) ne diffèrent que d'un nombre fini de termes, donc soit toutes les orbites sont finies, soit toutes sont infinies.
• PGCD (cas des orbites finies) : la période de la suite \((f^k(0))\) divise \(\operatorname{pgcd}(2a^2, 2(a+1)^2) = 2\).
• Contre-exemple minimal (cas des orbites finies) : un \(m \neq 0\) avec \(f(m) \neq 0\) et \(|m|\) minimal mène à une contradiction.
• Décalage d'indices (cas des orbites infinies) : la différence \(X(a, b) = n - m\) lorsque \(f^n(a) = f^m(b)\) est bien définie, additive, et vaut \(b - a\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (une solution et une remarque).

Réponse : soit \(f(x) = 0\) pour tout \(x \in \mathbb{Z}\), soit \(f(x) = x + 1\) pour tout \(x \in \mathbb{Z}\).

Solution

Notons \(E(a, b)\) l'équation de l'énoncé. \(E(0, b)\) s'écrit \(f^{b^2}(b) = b f(b)\) ; pour \(b = -1\), cela donne \(f(-1) = -f(-1)\), donc \(f(-1) = 0\). Ensuite \(E(a, -1)\) s'écrit

\[f^{a^2+1}(a-1) = a f(a) = f^{a^2}(a), \tag{1}\]

la dernière égalité venant de \(E(0, a)\).

Pour \(x \in \mathbb{Z}\), appelons orbite de \(x\) l'ensemble \(\mathcal{O}(x) = \{x, f(x), f(f(x)), \ldots\} \subseteq \mathbb{Z}\). D'après (1), les orbites \(\mathcal{O}(a-1)\) et \(\mathcal{O}(a)\) ne diffèrent que d'un nombre fini de termes. Par conséquent, deux orbites quelconques ne diffèrent que d'un nombre fini de termes ; en particulier, soit toutes les orbites sont finies, soit toutes sont infinies.

Cas 1 : toutes les orbites sont finies. Alors \(\mathcal{O}(0)\) est fini. La substitution \(E(a, -a)\) donne

\[a\big(f(a) - f(-a)\big) = a f(a) - a f(-a) = f^{2a^2}(0) \in \mathcal{O}(0).\]

Pour \(|a| > \max_{z \in \mathcal{O}(0)} |z|\), cela impose \(f(a) = f(-a)\) et \(f^{2a^2}(0) = 0\). La suite \(\big(f^k(0)\big)_{k \geq 0}\) est donc purement périodique, de plus petite période \(T\) divisant \(2a^2\). De même, \(T\) divise \(2(a+1)^2\), d'où

\[T \mid \operatorname{pgcd}\big(2a^2, 2(a+1)^2\big) = 2,\]

c'est-à-dire \(f(f(0)) = 0\), et \(a\big(f(a) - f(-a)\big) = f^{2a^2}(0) = 0\) pour tout \(a\). Ainsi

\[f(a) = f(-a) \quad \text{pour tout } a \neq 0 ; \tag{2}\]

\[\text{en particulier, } f(1) = f(-1) = 0. \tag{3}\]

Ensuite, pour tout \(n \in \mathbb{Z}\), \(E(n, 1-n)\) donne

\[n f(n) + (1-n) f(1-n) = f^{n^2 + (1-n)^2}(1) = f^{2n^2 - 2n}(0) = 0, \tag{4}\]

car \(f(1) = 0\) et \(2n^2 - 2n\) est pair.

Supposons qu'il existe \(m \neq 0\) tel que \(f(m) \neq 0\), et choisissons-en un avec \(|m|\) minimal. Alors \(|m| > 1\) d'après (3) ; \(f(|m|) \neq 0\) d'après (2) ; et \(f(1 - |m|) \neq 0\) d'après (4) pour \(n = |m|\). Comme \(0 < |1 - |m|| = |m| - 1 < |m|\), cela contredit la minimalité. Donc \(f(n) = 0\) pour tout \(n \neq 0\). Enfin,

\[f(0) = f^3(0) = f^4(2) = 2f(2) = 0\]

(on utilise \(f(f(0)) = 0\), puis \(f(2) = 0\), puis \(E(0, 2)\)). La fonction nulle vérifie clairement l'équation : c'est la première réponse.

Cas 2 : toutes les orbites sont infinies. Comme \(\mathcal{O}(a)\) et \(\mathcal{O}(a-1)\) ne diffèrent que d'un nombre fini de termes pour tout \(a\), deux orbites \(\mathcal{O}(a)\) et \(\mathcal{O}(b)\) ont une infinité de termes communs, pour tous \(a, b \in \mathbb{Z}\).

Fixons provisoirement \(a, b \in \mathbb{Z}\). Montrons que tous les couples \((n, m)\) d'entiers positifs ou nuls tels que \(f^n(a) = f^m(b)\) ont la même différence \(n - m\). Sinon, on aurait \(f^n(a) = f^m(b)\) et \(f^p(a) = f^q(b)\) avec, disons, \(n - m > p - q\) ; alors, pour tout entier \(k \geq 0\),

\[f^{p+m+k}(b) = f^{p+n+k}(a) = f^{q+n+k}(b).\]

Ainsi \(f^{\ell + (n-m) - (p-q)}(b) = f^\ell(b)\) pour tout \(\ell\) assez grand : la suite \(\big(f^n(b)\big)\) est périodique à partir d'un certain rang, donc \(\mathcal{O}(b)\) est finie, ce qui est exclu.

Pour \(a, b \in \mathbb{Z}\), notons \(X(a, b)\) cette différence commune \(n - m\). D'après (1), \(X(a-1, a) = 1\). Par ailleurs, \(X(a, b) + X(b, c) = X(a, c)\) : si \(f^n(a) = f^m(b)\) et \(f^p(b) = f^q(c)\), alors \(f^{p+n}(a) = f^{p+m}(b) = f^{q+m}(c)\). Ces deux propriétés donnent \(X(a, b) = b - a\) pour tous \(a, b \in \mathbb{Z}\).

Or, en appliquant \(f\) aux deux membres de (1), on obtient \(f^{a^2+1}\big(f(a-1)\big) = f^{a^2}\big(f(a)\big)\), donc

\[1 = X\big(f(a-1), f(a)\big) = f(a) - f(a-1) \quad \text{pour tout } a \in \mathbb{Z}.\]

Comme \(f(-1) = 0\), une récurrence (dans les deux sens) donne \(f(x) = x + 1\) pour tout \(x \in \mathbb{Z}\).

Réciproquement, cette fonction convient : \(f^n(x) = x + n\) pour tout \(n \geq 0\), donc

\[f^{a^2+b^2}(a+b) = a + b + a^2 + b^2 = a f(a) + b f(b). \qquad \blacksquare\]

Remarques

Remarque. Il existe de nombreuses variantes de cette solution, mais la finitude des orbites semble être la distinction cruciale dans toutes. La disjonction de cas peut se faire autrement ; en particulier, certaines versions du cas 1 fonctionnent dès qu'il existe au moins une orbite finie. Le cas 2 est conceptuellement plus difficile que le cas 1.