Shortlist 2015, A5¶
Domaine : Algèbre · Difficulté : ★★★★☆ · Proposé par : U.S.A.
Concepts : Sommes, télescopage et transformation d'Abel · Divisibilité, PGCD et algorithme d'Euclide · Équations fonctionnelles : substitutions, injectivité, surjectivité
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 17 (page 18 du PDF)
Énoncé¶
Let \(2\mathbb{Z} + 1\) denote the set of odd integers. Find all functions \(f : \mathbb{Z} \to 2\mathbb{Z} + 1\) satisfying
for every \(x, y \in \mathbb{Z}\).
Indices : les idées clés
- Opérateurs de différence : avec \(\Delta_t g(x) = g(x+t) - g(x)\), l'équation devient \(\Delta_{f(x)} f(a) = \Delta_{f(x)} f\big(2x - a - f(x)\big)\), et l'on raisonne sur les périodes et « quasi-périodes » de \(f\).
- Sommes, télescopage et transformation d'Abel : en sommant \(k\) copies de la relation, les différences télescopent et donnent \(\Delta_{kf(x)}\).
- Divisibilité, PGCD et algorithme d'Euclide : une fonction \(a\)-périodique et \(b\)-périodique est \(\operatorname{pgcd}(a,b)\)-périodique ; on montre par l'absurde, avec une puissance de premier \(p^\alpha\), que la plus petite quasi-période divise toutes les valeurs de \(f\).
- Équations fonctionnelles : substitutions, injectivité, surjectivité : le changement de variable \(a = x + y\) et la substitution \(y = 0\) (qui donne \(2f(u) = f(u + f(u)) + f(u - f(u))\)).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2015 (une solution et une remarque).
Réponse. On fixe un entier impair \(d > 0\), un entier \(k\) et des entiers impairs \(\ell_0, \ell_1, \ldots, \ell_{d-1}\). La fonction définie par
convient, et ce sont toutes les solutions.
Solution¶
Toutes les fonctions considérées vont de \(\mathbb{Z}\) dans \(\mathbb{Z}\). Pour une fonction \(g\) et un entier \(t \neq 0\), on pose
Pour \(a, b\) non nuls, \(\Delta_a \Delta_b g = \Delta_b \Delta_a g\). De plus, si \(\Delta_a g = 0\) et \(\Delta_b g = 0\), alors \(\Delta_{a+b} g = 0\) et \(\Delta_{at} g = 0\) pour tout entier \(t \neq 0\). On dit que \(g\) est \(t\)-quasi-périodique si \(\Delta_t g\) est constante (autrement dit \(\Delta_1 \Delta_t g = 0\), ou encore \(\Delta_1 g\) est \(t\)-périodique) ; \(t\) est alors une quasi-période de \(g\). Une quasi-période de \(g\) est une période de \(\Delta_1 g\) ; donc si \(g\) est quasi-périodique, sa plus petite quasi-période positive divise toutes ses quasi-périodes.
Soit \(f\) une solution. En posant \(a = x + y\), l'équation se réécrit
Soient \(b\) un entier et \(k\) un entier positif. En appliquant (2) avec \(a = b, b + f(x), \ldots, b + (k-1)f(x)\) et en sommant, les deux membres télescopent :
Le même argument vaut pour \(k\) négatif, d'où
Lemme 1. Pour \(x \neq y\) entiers, la fonction \(\Delta_{\operatorname{ppcm}(f(x), f(y))} f\) est \(2(y - x)\)-périodique.
Preuve. Soit \(L = \operatorname{ppcm}(f(x), f(y))\). En appliquant (3) deux fois (avec \(x\), puis avec \(y\)) :
Lemme 2. Soit \(g\) une fonction et \(t, s\) des entiers non nuls tels que \(\Delta_{ts} g = 0\) et \(\Delta_t \Delta_t g = 0\). Alors \(\Delta_t g = 0\).
Preuve. On peut supposer \(s > 0\). Pour tout entier \(a\), comme \(\Delta_t \Delta_t g = 0\),
La somme de ces \(s\) nombres égaux vaut \(\Delta_{ts} g(a) = 0\), donc chacun est nul. \(\square\)
Étape 1 : \(f\) est quasi-périodique. Soit \(Q = \operatorname{ppcm}(f(0), f(1))\). D'après le lemme 1, \(g = \Delta_Q f\) est \(2\)-périodique : elle est constante sur les pairs et constante sur les impairs. De plus, (3) avec \(M = Q\) et \(x = b = 0\) donne \(g(0) = g(-Q)\). Comme \(Q\) est impair, \(0\) et \(-Q\) sont de parités différentes : les deux constantes coïncident, \(g\) est constante, et \(Q\) est une quasi-période de \(f\).
Étape 2 : en notant \(T\) la plus petite quasi-période positive de \(f\), on a \(T \mid f(x)\) pour tout \(x\). Comme \(Q\) est une quasi-période impaire, \(T \mid Q\) est impair. Supposons par l'absurde qu'il existe un premier impair \(p\), un entier \(\alpha \geq 1\) et un entier \(u\) tels que \(p^\alpha \mid T\) mais \(p^\alpha \nmid f(u)\). Avec \(x = u\), \(y = 0\) dans l'équation, \(2f(u) = f\big(u + f(u)\big) + f\big(u - f(u)\big)\), donc \(p^\alpha\) ne divise pas la valeur de \(f\) en l'un des points \(u + f(u)\) ou \(u - f(u)\) ; notons \(v\) ce point.
Soit \(L = \operatorname{ppcm}(f(u), f(v))\). Comme \(|u - v| = |f(u)|\), le lemme 1 donne \(\Delta_{2f(u)} \Delta_L f = 0\). Ainsi \(\Delta_L f\) est \(2f(u)\)-périodique, et aussi \(T\)-périodique (car \(\Delta_T \Delta_L f = \Delta_L \Delta_T f = 0\), \(\Delta_T f\) étant constante) ; elle est donc \(\operatorname{pgcd}(T, 2f(u))\)-périodique : \(\Delta_{\operatorname{pgcd}(T, 2f(u))} \Delta_L f = 0\). De même, \(\Delta_{\operatorname{pgcd}(T, 2f(u))} f\) est \(L\)-périodique et \(T\)-périodique, d'où \(\Delta_{\operatorname{pgcd}(T, L)} \Delta_{\operatorname{pgcd}(T, 2f(u))} f = 0\). Comme \(p^\alpha \nmid L\) et \(p^\alpha \nmid 2f(u)\) (\(p\) impair), les nombres \(\operatorname{pgcd}(T, 2f(u))\) et \(\operatorname{pgcd}(T, L)\) divisent tous deux \(T/p\). On obtient \(\Delta_{T/p} \Delta_{T/p} f = 0\), donc \(\Delta_{T/p} \Delta_{T/p} \Delta_1 f = 0\).
Comme \(\Delta_T \Delta_1 f = 0\), le lemme 2 appliqué à \(\Delta_1 f\) (avec \(t = T/p\), \(s = p\)) donne \(\Delta_{T/p} \Delta_1 f = 0\) : \(f\) est \((T/p)\)-quasi-périodique, ce qui contredit la minimalité de \(T\).
Étape 3 : description de \(f\). Soit \(d\) le PGCD de toutes les valeurs de \(f\) ; \(d\) est impair. D'après l'étape 2, \(T \mid d\), donc \(d\) est une quasi-période de \(f\) et \(\Delta_d f\) est constante. Cette constante est paire (différence de deux impairs) et divisible par \(d\) ; comme \(d\) est impair, on peut l'écrire \(2dk\) avec \(k\) entier. Pour \(i = 0, 1, \ldots, d-1\), posons \(\ell_i = f(i)/d\), qui est impair. Alors
Toute solution est donc de la forme annoncée.
Réciproque. Il suffit de vérifier (2). Pour une telle fonction, chaque \(f(x)\) est divisible par \(d\), et \(\Delta_{md} f = 2kmd\) est constante ; donc \(\Delta_{f(x)} f\) est constante, et les deux membres de (2) sont égaux. \(\blacksquare\)
Remarques¶
Remarque 1 (autre ordre des étapes). On peut aussi dire que \(g\) est \(t\)-pseudo-périodique si \(\Delta_t \Delta_t g = 0\). La plus petite pseudo-période positive divise toutes les pseudo-périodes : si \(t \neq s\) sont des pseudo-périodes, alors \(\Delta_t \Delta_t \Delta_s g = \Delta_{ts} \Delta_s g = 0\), donc \(\Delta_t \Delta_s g = 0\) par le lemme 2, et en prenant des différences \(\Delta_t \Delta_{t-s} g = \Delta_s \Delta_{t-s} g = 0\), d'où \(\Delta_{t-s} \Delta_{t-s} g = 0\). Le lemme 1 donne \(\Delta_{2(y-x)} \Delta_{\operatorname{ppcm}(f(x), f(y))} f = 0\), donc \(f\) est pseudo-périodique de pseudo-période \(\operatorname{ppcm}(2(y-x), f(x), f(y))\). Si \(T'\) est la plus petite pseudo-période, on montre comme à l'étape 2 que \(T' \mid 2f(x)\) pour tout \(x\), puis que \(\Delta_{T'} \Delta_2 f = 0\) (le lemme 1 fournit \(s\) avec \(\Delta_s \Delta_2 f = 0\), d'où \(\Delta_{T's} \Delta_2 f = 0\) et on conclut par le lemme 2). Il reste un travail supplémentaire pour éliminer les facteurs \(2\) des indices et obtenir une quasi-période impaire divisant toutes les valeurs de \(f\) ; on termine alors comme à l'étape 3.